Abstract
In [25,27] Valiant developed an algebraic analogue of the theory of NP-completeness for computations with polynomials over a field. We further develop this theory in the spirit of structural complexity and obtain analogues of well-known results by Baker, Gill, and Solovay [1], Ladner [18], and Schöning [23,24].
We show that if Valiant's hypothesis is true, then there is a p-definable family, which is neither p-computable nor VNP-complete. More generally, we define the posets of p-degrees and c-degrees of p-definable families and prove that any countable poset can embedded in either of them, provided Valiant's hypothesis is true. Moreover, we establish the existence of minimal pairs for VP in VNP.
Over finite fields, we give a specific example of a family of polynomials which is neither VNP-complete nor p-computable, provided the polynomial hierarchy does not collapse.
We define relativized complexity classes VPh and VNPh and construct complete families in these classes. Moreover, we prove that there is a p-family h satisfying VPh = VNPh.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
References
T. Baker, J. Gill, and R. Solovay. Relativizations of the P =?NP question. SIAM J. Comp., 4:431–442, 1975.
S. Ben-David, K. Meer, and C. Michaux. A note on non-complete problems in NPℝ. Preprint, 1996.
C.H. Bennett and J. Gill. Relative to a random oracle A, PA ≠ NPA ≠ co-NPA with probability 1. SIAM J. Comp., 10:96–113, 1981.
L. Blum, F. Cucker, M. Shub, and S. Smale. Algebraic Settings for the Problem “P ≠ NP?”. In The mathematics of numerical analysis, number 32 in Lectures in Applied Mathematics, pages 125–144. Amer. Math. Soc., 1996.
L. Blum, M. Shub, and S. Smale. On a theory of computation and complexity over the real numbers. Bull. Amer. Math. Soc., 21:1–46, 1989.
P. Bürgisser. Cook's versus Valiant's hypothesis. Preprint, University of Zurich, 1997.
P. Bürgisser. Some complete families of polynomials. Manuscript, 1997.
P. Bürgisser, M. Clausen, and M.A. Shokrollahi. Algebraic Complexity Theory. Number 315 in Grundlehren der mathematischen Wissenschaften. Springer Verlag, 1996.
J. Cai and L.A. Hemachandra. On the power of parity polynomial time. In Proc. STACS'89, number 349 in LNCS, pages 229–239. Springer Verlag, 1989.
O. Chapuis and P. Koiran. Saturation and Stability in the Theory of Computation over the Reals. Preprint, 1997.
S.A. Cook. The complexity of theorem proving procedures. In Proc. 3rd ACM STOC, pages 151–158, 1971.
T. Emerson. Relativizations of the P=?NP question over the reals (and other ordered rings). Theoret. Comp. Sci., 133:15–22, 1994.
W. Feller. An introduction to probability theory and its applications, volume 2. John Wiley & Sons, 1971.
J. von zur Gathen. Feasible arithmetic computations: Valiant's hypothesis. J. Symb. Comp., 4:137–172, 1987.
J. Heintz and J. Morgenstern. On the intrinsic complexity of elimination theory. Journal of Complexity, 9:471–498, 1993.
R.M. Karp and R.J. Lipton. Turing machines that take advice. In Logic and Algorithmic: An international Symposium held in honor of Ernst Specker, pages 255–273. Monogr. No. 30 de l'Enseign. Math., 1982.
P. Koiran. Hilbert's Nullstellensatz is in the polynomial hierarchy. J. Compl., 12:273–286, 1996.
R.E. Ladner. On the structure of polynomial time reducibility. J. ACM, 22:155–171, 1975.
Landweber, Lipton, and Robertson. On the structure of sets in NP and other complexity classes. Theoret. Comp. Sci., 15:181–200, 1981.
G. Malajovich and K. Meer. On the structure of NPℂ. SIAM J. Comp. to appear.
C.H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.
C.H. Papadimitriou and S. Zachos. Two remarks on the power of counting. In Proc. 6th GI conference in Theoretical Computer Science, number 145 in LNCS, pages 269–276. Springer Verlag, 1983.
U. Schöning. A uniform approach to obtain diagonal sets in complexity classes. Theoret. Comp. Sci., 18:95–103, 1982.
U. Schöning. Minimal pairs for P. Theoret. Comp. Sci., 31:41–48, 1984.
L.G. Valiant. Completeness classes in algebra. In Proc. 11th ACM STOC, pages 249–261, 1979.
L.G. Valiant. The complexity of computing the permanent. Theoret. Comp. Sci., 8:189–201, 1979.
L.G. Valiant. Reducibility by algebraic projections. In Logic and Algorithmic: an International Symposium held in honor of Ernst Specker, volume 30, pages 365–380. Monographies de l'Enseignement Mathématique, 1982.
L.G. Valiant and V.V. Vazirani. NP is as easy as detecting unique solutions. Theoret. Comp. Sci., 47:85–93, 1986.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1998 Springer-Verlag
About this paper
Cite this paper
Bürgisser, P. (1998). On the structure of valiant's complexity classes. In: Morvan, M., Meinel, C., Krob, D. (eds) STACS 98. STACS 1998. Lecture Notes in Computer Science, vol 1373. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0028561
Download citation
DOI: https://doi.org/10.1007/BFb0028561
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-64230-5
Online ISBN: 978-3-540-69705-3
eBook Packages: Springer Book Archive