Arithmetization: A new method in structural complexity theory

DOI10.1007/BF01200057zbMath0774.68040OpenAlexW1964234068MaRDI QIDQ685721

László Babai, Lance J. Fortnow

Publication date: 10 October 1993

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01200057

zbMATH Keywords

multivariate polynomialsarithmetic straight line programsstructural complexity theory

Mathematics Subject Classification ID

Specification and verification (program logics, model checking, etc.) (68Q60) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (22)

Probabilistically checkable proofs and their consequences for approximation algorithms ⋮ Recursion theoretic characterizations of complexity classes of counting functions ⋮ The complexity of weighted counting for acyclic conjunctive queries ⋮ A structured view on weighted counting with relations to counting, quantum computation and applications ⋮ EPiC: efficient privacy-preserving counting for MapReduce ⋮ Cook's versus Valiant's hypothesis ⋮ Shorter arithmetization of nondeterministic computations ⋮ New collapse consequences of NP having small circuits ⋮ Interactive proof systems and alternating time-space complexity ⋮ Non-deterministic exponential time has two-prover interactive protocols ⋮ Characterizing Valiant's algebraic complexity classes ⋮ A nonadaptive NC checker for permutation group intersection ⋮ Computational arithmetic geometry. I: Sentences nearly in the polynomial hierarchy ⋮ Competing provers yield improved Karp-Lipton collapse results ⋮ Integer circuit evaluation is PSPACE-complete ⋮ Approximate evaluations of characteristic polynomials of Boolean functions ⋮ Randomized proofs in arithmetic ⋮ Succinct Algebraic Branching Programs Characterizing Non-uniform Complexity Classes ⋮ A la recherche de la definition de la complexite d'espace pour le calcul des polynomes a la maniere de Valiant ⋮ A note on the circuit complexity of PP ⋮ Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity ⋮ \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• Non-deterministic exponential time has two-prover interactive protocols
• NP is as easy as detecting unique solutions
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• The polynomial-time hierarchy
• Gap-definable counting classes
• PP is closed under intersection
• Random-Self-Reducibility of Complete Sets
• The Knowledge Complexity of Interactive Proof Systems
• Alternation
• #P-COMPLETENESS VIA MANY-ONE REDUCTIONS
• Counting classes: Thresholds, parity, mods, and fewness

This page was built for publication: Arithmetization: A new method in structural complexity theory