\(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 (2)

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

This page was built for publication: \(P\) versus \(NP\) and geometry