Cook's versus Valiant's hypothesis

DOI10.1016/S0304-3975(99)00183-8zbMATH Open0943.68070MaRDI QIDQ1978701FDOQ1978701

Peter Bürgisser

Publication date: 4 June 2000

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

Recommendations

• scientific article; zbMATH DE number 1136078
• scientific article; zbMATH DE number 1375589
• Completeness and reduction in algebraic complexity theory

zbMATH Keywords

NP-completenessalgebraic complexityreduction modulo primeselimination of constants

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (14)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1978701)