New collapse consequences of NP having small circuits
From MaRDI portal
Publication:4645178
DOI10.1007/3-540-60084-1_74zbMath1412.68067OpenAlexW1573868303MaRDI QIDQ4645178
Osamu Watanabe, Johannes Köbler
Publication date: 10 January 2019
Published in: Automata, Languages and Programming (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/3-540-60084-1_74
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Arithmetization: A new method in structural complexity theory
- Non-deterministic exponential time has two-prover interactive protocols
- Some consequences of non-uniform conditions on uniform classes
- Nonuniform proof systems: A new framework to describe nonuniform and probabilistic complexity classes
- On self-reducibility and weak P-selectivity
- Strong nondeterministic polynomial-time reducibilities
- Relativized circuit complexity
- Complexity and structure
- Random generation of combinatorial structures from a uniform distribution
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
- On sparse hard sets for counting classes
- Universal classes of hash functions
- On hiding information from an oracle
- Locating \(P\)/poly optimally in the extended low hierarchy
- Computation times of NP sets of different densities
- Sets with small generalized Kolmogorov complexity
- Oracles and queries that are sufficient for exact learning
- Queries and concept learning
- Self-reducibility
- The polynomial-time hierarchy and sparse oracles
- Self-reducible sets of small density
- Robustness of probabilistic computational complexity classes under definitional perturbations
- Circuit-size lower bounds and non-reducibility to sparse sets
- On relativized exponential and probabilistic complexity classes
- Computational Complexity of Probabilistic Turing Machines
- Algebraic methods for interactive proof systems
