Document Open Access Logo

Boundaries of VP and VNP

Authors Joshua A. Grochow, Ketan D. Mulmuley, Youming Qiao

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2016.34.pdf
  • Filesize: 0.57 MB
  • 14 pages

Document Identifiers

Author Details

Joshua A. Grochow
Ketan D. Mulmuley
Youming Qiao

Cite As Get BibTex

Joshua A. Grochow, Ketan D. Mulmuley, and Youming Qiao. Boundaries of VP and VNP. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 34:1-34:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ICALP.2016.34

Abstract

One fundamental question in the context of the geometric complexity theory approach to the VP vs. VNP conjecture is whether VP = !VP, where VP is the class of families of polynomials that can be computed by arithmetic circuits of polynomial degree and size, and VP is the class of families of polynomials that can be approximated infinitesimally closely by arithmetic circuits of polynomial degree and size. The goal of this article is to study the conjecture in (Mulmuley, FOCS 2012) that !VP is not contained in VP.

Towards that end, we introduce three degenerations of VP (i.e., sets of points in VP), namely the stable degeneration Stable-VP, the Newton degeneration Newton-VP, and the p-definable one-parameter degeneration VP*. We also introduce analogous degenerations of VNP. We show that Stable-VP subseteq Newton-VP subseteq VP* subseteq VNP, and Stable-VNP = Newton-VNP = VNP* = VNP. The three notions of degenerations and the proof of this result shed light on the problem of separating VP from VP.

Although we do not yet construct explicit candidates for the polynomial families in !VP\VP, we prove results which tell us where not to look for such families. Specifically, we demonstrate that the families in Newton-VP \VP based on semi-invariants of quivers would have to be nongeneric by showing that, for many finite quivers (including some wild ones), Newton degeneration of any generic semi-invariant can be computed by a circuit of polynomial size. We also show that the Newton degenerations of perfect matching Pfaffians, monotone arithmetic circuits over the reals, and Schur polynomials have polynomial-size circuits.

Subject Classification

Keywords
  • geometric complexity theory
  • arithmetic circuit
  • border complexity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Genrich R. Belitskii and Vladimir V. Sergeichuk. Complexity of matrix problems. Linear Algebra Appl., 361:203-222, 2003. Ninth Conference of the International Linear Algebra Society (Haifa, 2001). URL: http://dx.doi.org/10.1016/S0024-3795(02)00391-9.
  2. D. Bini. Relations between exact and approximate bilinear algorithms. Applications. Calcolo, 17(1):87-97, 1980. URL: http://dx.doi.org/10.1007/BF02575865.
  3. P. Bürgisser. The complexity of factors of multivariate polynomials. Found. Comput. Math., pages 369-396, 2004. Google Scholar
  4. P. Bürgisser, M. Clausen, and M.A. Shokrollahi. Algebraic Complexity Theory. A series of comprehensive studies in mathematics. Springer, 1997. Google Scholar
  5. P. Bürgisser, J. Landsberg, L. Manivel, and J. Weyman. An overview of mathematical issues arising in the geometric complexity theory approach to VP ̸ = VNP. SIAM Journal on Computing, 40(4):1179-1209, 2011. Google Scholar
  6. H. Derksen and J. Weyman. Semi-invariants of quivers and saturation for Littlewood-Richardson coefficients. Journal of the American Mathematical Society, 13(3):467-479, 2000. Google Scholar
  7. H. Derksen and J. Weyman. Quiver representations. Notices of the American Mathematical Society, 52(2):200-206, 2005. Google Scholar
  8. M. Domokos and A. Zubkov. Semi-invariants of quivers as determinants. Transformation groups, 6(1):9-24, 2001. Google Scholar
  9. J. Edmonds. Maximum matching and a polyhedron with 0, l-vertices. J. Res. Nat. Bur. Standards B, 69(1965):125-130, 1965. Google Scholar
  10. J. A. Grochow. Symmetry and equivalence relations in classical and geometric complexity theory. PhD thesis, University of Chicago, Chicago, IL, 2012. Google Scholar
  11. J. A. Grochow. Unifying known lower bounds via geometric complexity theory. Computational Complexity, 24:393-475, 2015. Special issue on IEEE CCC 2014. URL: http://dx.doi.org/10.1007/s00037-015-0103-x.
  12. D. Hilbert. Über die vollen Invariantensysteme. Math. Ann., 42:313-370, 1893. Google Scholar
  13. E. Kaltofen and P. Koiran. Expressing a fraction of two determinants as a determinant. In Symbolic and Algebraic Computation, International Symposium, ISSAC 2008, Linz/Hagenberg, Austria, July 20-23, 2008, Proceedings, pages 141-146, 2008. URL: http://dx.doi.org/10.1145/1390768.1390790.
  14. N. Kayal and R. Saptharishi. A selection of lower bounds for arithmetic circuits. Progress in Computer Science and Applied Logic, 26, 2014. Google Scholar
  15. G. Kempf. Instability in invariant theory. Annals of Mathematics, 108(2):299-316, 1978. Google Scholar
  16. F. Kirwan. Cohomology of Quotients in Symplectic and Algebraic Geometry. Mathematical Notes 31. Princeton University Press, 1984. Google Scholar
  17. J. M. Landsberg. An introduction to geometric complexity theory. Newsletter Eur. Math. Soc., pages 10-18, 2016. Preprint available as arXiv:1509.02503 [math.AG]. Google Scholar
  18. Joseph M. Landsberg, Laurent Manivel, and Nicolas Ressayre. Hypersurfaces with degenerate duals and the geometric complexity theory program. Comment. Math. Helv., 88(2):469-484, 2013. Preprint available as arXiv:1004.4802 [math.AG]. URL: http://dx.doi.org/10.4171/CMH/292.
  19. G. Malod and N. Portier. Characterizing Valiant’s algebraic complexity classes. J. Complex., 24(1):16-38, 2008. Google Scholar
  20. T. Mignon and N. Ressayre. A quadratic bound for the determinant and permanent problem. International Mathematics Research Notices, pages 4241-4253, 2004. Google Scholar
  21. K. Mulmuley. Geometric complexity theory V: Equivalence between black-box derandomization of polynomial identity testing and derandomization of Noether’s Normalization Lemma. In Revised version under preparation. Preliminary version: FOCS, 2012. Google Scholar
  22. K. Mulmuley and M. Sohoni. Geometric complexity theory I: an approach to the P vs. NP and related problems. SIAM J. Comput., 31(2):496-526, 2001. Google Scholar
  23. K. Mulmuley and M. Sohoni. Geometric complexity theory II: towards explicit obstructions for embeddings among class varieties. SIAM J. Comput., 38(3):1175-1206, 2008. Google Scholar
  24. D. Mumford, J. Fogarty, and F. Kirwan. Geometric invariant theory. Springer-Verlag, 1994. Google Scholar
  25. Ran Raz and Amir Yehudayoff. Lower bounds and separations for constant depth multilinear circuits. Comput. Complexity, 18(2):171-207, 2009. Google Scholar
  26. V. Strassen. Vermeidung von divisionen. Journal für die reine und angewandte Mathematik, 264:184-202, 1973. Google Scholar
  27. L. G. Valiant. Completeness classes in algebra. In Proceedings of the eleventh annual ACM symposium on Theory of computing, STOC'79, pages 249-261, New York, NY, USA, 1979. ACM. URL: http://dx.doi.org/10.1145/800135.804419.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact