\(P\) versus \(NP\) and geometry

DOI10.1016/j.jsc.2010.06.015zbMath1208.68129arXiv0910.2443OpenAlexW2962792978MaRDI QIDQ607059

Joseph M. Landsberg

Publication date: 19 November 2010

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0910.2443

zbMATH Keywords

determinantGrassmannianspinorpermanentexpository articlegeometric complexity theoryholographic algorithmsNPP

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational aspects in algebraic geometry (14Q99)

Related Items

Bounded-rank tensors are defined in bounded degree, Geometric complexity theory: an introduction for geometers

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Geometric complexity theory. III: On deciding nonvanishing of a Littlewood-Richardson coefficient
• Nonvanishing of Kronecker coefficients for rectangular shapes.
• The stabilizer of immanants
• Basis collapse in holographic algorithms
• Permanent and determinant
• A note on the determinant and permanent problem
• Linear transformations that preserve immanants
• On the projective geometry of rational homogeneous varieties
• Completeness and reduction in algebraic complexity theory
• Construction and classification of complex simple Lie algebras via projective geometry
• Expressiveness of matchgates.
• Holographic algorithms without matchgates
• Hypersurfaces with degenerate duals and the geometric complexity theory program
• Valiant's holant theorem and matchgate tensors
• Characterizing Valiant's algebraic complexity classes
• On linear preservers of immanants
• Geometric Complexity Theory I: An Approach to thePvs.NPand Related Problems
• Quantum Circuits That Can Be Simulated Classically in Polynomial Time
• Holographic Algorithms
• On Symmetric Signatures in Holographic Algorithms
• Some Results on Matchgates and Holographic Algorithms
• Geometric Complexity Theory II: Towards Explicit Obstructions for Embeddings among Class Varieties
• COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
• Quantum computers that can be simulated classically in polynomial time
• Geometric Complexity Theory IV: nonstandard quantum group for the Kronecker problem
• Dimer problem in statistical mechanics-an exact result
• Holographic Algorithms: The Power of Dimensionality Resolved
• Automata, Languages and Programming
• Theory and Applications of Models of Computation