Robust simulations and significant separations
From MaRDI portal
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
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
Circuit Lower Bounds for Nondeterministic Quasi-polytime from a New Easy Witness Lemma, Relations and equivalences between circuit lower bounds and karp-lipton theorems, Circuit lower bounds from NP-hardness of MCSP under turing reductions, Lower bounds on the complexity of \(\mathsf{MSO}_1\) model-checking, Proving that \(\mathrm{prBPP}=\mathrm{prP}\) is as hard as proving that ``almost NP is not contained in P/poly, Robust simulations and significant separations, Complexity with Rod, 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
- \(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\)
- 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.
- Robust simulations and significant separations
- 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
- Nondeterministic Separations
- 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