Cook's versus Valiant's hypothesis

DOI10.1016/S0304-3975(99)00183-8zbMath0943.68070MaRDI QIDQ1978701

Peter Bürgisser

Publication date: 4 June 2000

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

NP-completenessalgebraic complexityreduction modulo primeselimination of constants

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (12)

Some complete and intermediate polynomials in algebraic complexity theory ⋮ Dual VP classes ⋮ Most secant varieties of tangential varieties to Veronese varieties are nondefective ⋮ Towards a tight hardness-randomness connection between permanent and arithmetic circuit identity testing ⋮ Lower bounds for the determinantal complexity of explicit low degree polynomials ⋮ On the algebraic complexity of some families of coloured Tutte polynomials ⋮ Kolmogorov Complexity Theory over the Reals ⋮ Counting complexity classes for numeric computations. II: Algebraic and semialgebraic sets ⋮ No occurrence obstructions in geometric complexity theory ⋮ Algebraic Complexity Classes ⋮ Lower Bounds for the Determinantal Complexity of Explicit Low Degree Polynomials ⋮ $$P\mathop{ =}\limits^{?}NP$$

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• Arithmetization: A new method in structural complexity theory
• NP is as easy as detecting unique solutions
• Feasible arithmetic computations: Valiant's hypothesis
• Completeness and reduction in algebraic complexity theory
• Hilbert's Nullstellensatz is in the polynomial hierarchy
• Fast Parallel Computation of Polynomials Using Few Processors
• Finding the number of factors of a polynomial
• The Complexity of Enumeration and Reliability Problems
• On the Power of Real Turing Machines over Binary Inputs
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• The complexity of theorem-proving procedures
• Number fields

This page was built for publication: Cook's versus Valiant's hypothesis