On P vs. NP and geometric complexity theory
From MaRDI portal
Publication:3016252
DOI10.1145/1944345.1944346zbMath1327.68111OpenAlexW2060880193MaRDI QIDQ3016252
Publication date: 14 July 2011
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1944345.1944346
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (16)
Algorithms for Group Isomorphism via Group Extensions and Cohomology ⋮ Non-commutative Edmonds' problem and matrix semi-invariants ⋮ Sparse multivariate polynomial interpolation on the basis of Schubert polynomials ⋮ On vanishing of Kronecker coefficients ⋮ Interactions of computational complexity theory and mathematics ⋮ Geometric complexity theory. III: On deciding nonvanishing of a Littlewood-Richardson coefficient ⋮ Generalized Littlewood-Richardson coefficients for branching rules of \(\mathrm{GL}(n)\) and extremal weight crystals ⋮ Complexity classes and completeness in algebraic geometry ⋮ Obstructions to combinatorial formulas for plethysm ⋮ Algebraic independence in positive characteristic: A $p$-adic calculus ⋮ No occurrence obstructions in geometric complexity theory ⋮ Jacobian Hits Circuits: Hitting Sets, Lower Bounds for Depth-$D$ Occur-$k$ Formulas and Depth-3 Transcendence Degree-$k$ Circuits ⋮ On the Symmetries of and Equivalence Test for Design Polynomials. ⋮ Geometric complexity theory V: Efficient algorithms for Noether normalization ⋮ Geometric Complexity Theory IV: nonstandard quantum group for the Kronecker problem ⋮ Unifying known lower bounds via geometric complexity theory
This page was built for publication: On P vs. NP and geometric complexity theory
