Robust simulations and significant separations

DOI10.1016/j.ic.2017.07.002zbMath1376.68049arXiv1012.2034MaRDI QIDQ2407096

Rahul Santhanam, Lance J. Fortnow

Publication date: 28 September 2017

Published in: Information and Computation, Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1012.2034

Mathematics Subject Classification ID

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

Related Items

Lower bounds on the complexity of \(\mathsf{MSO}_1\) model-checking, NEXP Does Not Have Non-uniform Quasipolynomial-Size ACC Circuits of o(loglogn) Depth

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A Turing machine time hierarchy
• Non-deterministic exponential time has two-prover interactive protocols
• Turing machines that take advice
• Short propositional formulas represent nondeterministic computations
• Hardness vs randomness
• Time-space tradeoffs for satisfiability
• In search of an easy witness: Exponential time vs. probabilistic polynomial time.
• Uniformly hard languages.
• A generic time hierarchy with one bit of advice
• A note on the circuit complexity of PP
• Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses
• Improving exhaustive search implies superpolynomial lower bounds
• Circuit-size lower bounds and non-reducibility to sparse sets
• Time-space lower bounds for satisfiability
• Unconditional Lower Bounds against Advice
• Separating Nondeterministic Time Complexity Classes
• Natural proofs
• Easiness assumptions and hardness tests: Trading time for zero error