Complexity barriers as independence

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

Authors: Antonina Kolokolova 

Publication date: 6 September 2024

Recommendations

• Algebrization: a new barrier in complexity theory
• scientific article; zbMATH DE number 58312
• \(\mathrm P \overset {?} {=} \mathrm{NP}\)
• An axiomatic approach to algebrization
• Affine relativization: unifying the algebrization and relativization barriers

zbMATH Keywords

Peano arithmeticTuring machinerandom oracleinteractive proofsatisfying assignment

Mathematics Subject Classification ID

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

Cites Work

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

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)