Complexity barriers as independence

DOI10.1007/978-3-319-43669-2_10zbMATH Open1544.68081MaRDI QIDQ6599290

Antonina Kolokolova

Publication date: 6 September 2024

zbMATH Keywords

Peano arithmeticTuring machinerandom oracleinteractive proofsatisfying assignment

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The black-box query complexity of polynomial summation
• Non-deterministic exponential time has two-prover interactive protocols
• \(\Sigma_ 1^ 1\)-formulae on finite structures
• Are there interactive protocols for co-NP languages?
• The random oracle hypothesis is false
• A second-order system for polytime reasoning based on Grädel's theorem.
• Dual weak pigeonhole principle, Boolean complexity, and derandomization
• Relationships between nondeterministic and deterministic tape complexities
• Expressing versus proving: relating forms of complexity in logic
• Algebrization
• Proof verification and the hardness of approximation problems
• Nonuniform ACC Circuit Lower Bounds
• Parity, circuits, and the polynomial-time hierarchy
• PP is as Hard as the Polynomial-Time Hierarchy
• Approximate counting by hashing in bounded arithmetic
• Probabilistic checking of proofs
• Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• Algebraic methods for interactive proof systems
• IP = PSPACE
• Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
• Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic
• Logical Foundations of Mathematics and Computational Complexity
• An axiomatic approach to algebrization
• Computational Complexity
• On the Computational Complexity of Algorithms
• Paths, Trees, and Flowers
• Approximate counting in bounded arithmetic
• On Independence of Variants of the Weak Pigeonhole Principle
• Two-Tape Simulation of Multitape Turing Machines
• Existence and feasibility in arithmetic
• The complexity of theorem-proving procedures
• Systems of Logic Based on Ordinals^†
• Natural proofs

This page was built for publication: Complexity barriers as independence

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