Complexity barriers as independence
From MaRDI portal
Publication:6599290
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)
Recommendations
Cites work
- scientific article; zbMATH DE number 424614 (Why is no real title available?)
- scientific article; zbMATH DE number 440483 (Why is no real title available?)
- scientific article; zbMATH DE number 5604094 (Why is no real title available?)
- scientific article; zbMATH DE number 4059391 (Why is no real title available?)
- scientific article; zbMATH DE number 176527 (Why is no real title available?)
- scientific article; zbMATH DE number 3557241 (Why is no real title available?)
- scientific article; zbMATH DE number 3562523 (Why is no real title available?)
- scientific article; zbMATH DE number 559220 (Why is no real title available?)
- scientific article; zbMATH DE number 1144041 (Why is no real title available?)
- scientific article; zbMATH DE number 806753 (Why is no real title available?)
- scientific article; zbMATH DE number 819737 (Why is no real title available?)
- scientific article; zbMATH DE number 3363526 (Why is no real title available?)
- A second-order system for polytime reasoning based on Grädel's theorem.
- A simple proof of Toda's theorem
- Algebraic methods for interactive proof systems
- Algebrization: a new barrier in complexity theory
- An axiomatic approach to algebrization
- Approximate counting by hashing in bounded arithmetic
- Approximate counting in bounded arithmetic
- Are there interactive protocols for co-NP languages?
- Circuit lower bounds for Merlin-Arthur classes
- Computational Complexity
- Dual weak pigeonhole principle, Boolean complexity, and derandomization
- Existence and feasibility in arithmetic
- Expressing versus proving: relating forms of complexity in logic
- IP = PSPACE
- Logical foundations of mathematics and computational complexity. A gentle introduction
- Natural proofs
- Non-deterministic exponential time has two-prover interactive protocols
- Nonuniform ACC circuit lower bounds
- On Independence of Variants of the Weak Pigeonhole Principle
- On the Computational Complexity of Algorithms
- PP is as Hard as the Polynomial-Time Hierarchy
- Parity, circuits, and the polynomial-time hierarchy
- Paths, Trees, and Flowers
- Probabilistic checking of proofs
- Proof verification and the hardness of approximation problems
- Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
- Relationships between nondeterministic and deterministic tape complexities
- 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
- Systems of Logic Based on Ordinals†
- The black-box query complexity of polynomial summation
- The complexity of theorem-proving procedures
- The random oracle hypothesis is false
- Two-Tape Simulation of Multitape Turing Machines
- Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic
- \(\Sigma_ 1^ 1\)-formulae on finite structures
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)
