Approximate counting in bounded arithmetic

DOI10.2178/JSL/1191333850zbMath1123.03051OpenAlexW2125894854MaRDI QIDQ5422312

Emil Jeřábek

Publication date: 17 October 2007

Published in: Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://projecteuclid.org/euclid.jsl/1191333850

zbMATH Keywords

bounded arithmeticBoolean circuitsrandomized complexity classesapproximate counting of setsdual weak pigeonhole principle

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) First-order arithmetic and fragments (03F30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Randomized algorithms (68W20)

Related Items (14)

Expander Construction in VNC1 ⋮ Approximate counting and NP search problems ⋮ Typical forcings, NP search problems and an extension of a theorem of Riis ⋮ Uniform proofs of ACC representations ⋮ Collapsing modular counting in bounded arithmetic and constant depth propositional proofs ⋮ Expander construction in \(\mathrm{VNC}^1\) ⋮ On counting propositional logic and Wagner's hierarchy ⋮ ON THE EXISTENCE OF STRONG PROOF COMPLEXITY GENERATORS ⋮ Circuit lower bounds in bounded arithmetics ⋮ A Tight Karp-Lipton Collapse Result in Bounded Arithmetic ⋮ Feasibly constructive proofs of succinct weak circuit lower bounds ⋮ Polynomial time ultrapowers and the consistency of circuit lower bounds ⋮ Unprovability of circuit upper bounds in Cook's theory PV ⋮ On measure quantifiers in first-order arithmetic

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• BPP and the polynomial hierarchy
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• Complexity classes without machines: on complete languages for UP
• Bounded arithmetic and the polynomial hierarchy
• A uniform approach to define complexity classes
• Hardness vs randomness
• Dual weak pigeonhole principle, Boolean complexity, and derandomization
• Relating the bounded arithmetic and polynomial time hierarchies
• Structures interpretable in models of bounded arithmetic
• The strength of sharply bounded induction
• Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
• Computational Complexity of Probabilistic Turing Machines
• Provability of the pigeonhole principle and the existence of infinitely many primes
• A new proof of the weak pigeonhole principle

This page was built for publication: Approximate counting in bounded arithmetic