Comparing EQP and MOD_{p^k}P using Polynomial Degree Lower Bounds
| dc.creator | de Graaf, M. | |
| dc.creator | Valiant, P. | |
| dc.date | 2002-11-27 | |
| dc.date.accessioned | 2026-07-07T06:05:37Z | |
| dc.date.available | 2026-07-07T06:05:37Z | |
| dc.description | We show that an oracle A that contains either 1/4 or 3/4 of all strings of length n can be used to separate EQP from the counting classes MOD_{p^k}P. Our proof makes use of the degree of a representing polynomial over the finite field of size p^k. We show a linear lower bound on the degree of this polynomial. We also show an upper bound of O(n^{1/log_p m}) on the degree over the ring of integers modulo m, whenever m is a squarefree composite with largest prime factor p. | |
| dc.description | 10 pages, no figures | |
| dc.identifier | https://arxiv.org/abs/quant-ph/0211179 | |
| dc.identifier | http://arxiv.org/abs/quant-ph/0211179 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/90691 | |
| dc.subject | Quantum Physics | |
| dc.subject | Computational Complexity | |
| dc.title | Comparing EQP and MOD_{p^k}P using Polynomial Degree Lower Bounds | |
| dc.type | text |