Arithmetization: A new method in structural complexity theory

DOI10.1007/BF01200057zbMath0774.68040MaRDI QIDQ685721

László Babai, Lance J. Fortnow

Publication date: 10 October 1993

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

zbMATH Keywords

multivariate polynomials; arithmetic straight line programs; structural complexity theory

Mathematics Subject Classification ID

68Q60: Specification and verification (program logics, model checking, etc.)

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

Related Items

A la recherche de la definition de la complexite d'espace pour le calcul des polynomes a la maniere de Valiant, A nonadaptive NC checker for permutation group intersection, Computational arithmetic geometry. I: Sentences nearly in the polynomial hierarchy, Integer circuit evaluation is PSPACE-complete, Approximate evaluations of characteristic polynomials of Boolean functions, Interactive proof systems and alternating time-space complexity, Non-deterministic exponential time has two-prover interactive protocols, \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs, Probabilistically checkable proofs and their consequences for approximation algorithms, Recursion theoretic characterizations of complexity classes of counting functions, Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity, Competing provers yield improved Karp-Lipton collapse results, Randomized proofs in arithmetic, Cook's versus Valiant's hypothesis, Characterizing Valiant's algebraic complexity classes, A note on the circuit complexity of PP

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