AM_exp (NP coNP)/poly
From MaRDI portal
Publication:1029043
Recommendations
- \(\mathrm P \overset {?} {=} \mathrm{NP}\)
- An Isomorphism Between Subexponential and Parameterized Complexity Theory
- \(S_{k,\text{exp}}\) does not prove \(\text{NP} = \text{co-NP}\) uniformly
- \(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\)
- Beyond \(\mathbf{P}^{\mathbf{NP}}=\mathbf{NEXP}\)
- Pf ≠ NPf for almost all f
- Consequences of the provability of NP ⊆ P/poly
- scientific article; zbMATH DE number 1342223
- A PCP characterization of NP with optimal amortized query complexity
- With Quasilinear Queries EXP Is Not Polynomial Time Turing Reducible to Sparse Sets
Cites work
- A taxonomy of complexity classes of functions
- Algebraic methods for interactive proof systems
- An oracle builder's toolkit
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
- Circuit-size lower bounds and non-reducibility to sparse sets
- scientific article; zbMATH DE number 1335875 (Why is no real title available?)
- scientific article; zbMATH DE number 610968 (Why is no real title available?)
- scientific article; zbMATH DE number 1962842 (Why is no real title available?)
- scientific article; zbMATH DE number 1405686 (Why is no real title available?)
- IP = PSPACE
- New Collapse Consequences of NP Having Small Circuits
- New lowness results for ZPP\(^{\text{NP}}\) and other complexity classes.
- Non-deterministic exponential time has two-prover interactive protocols
- On relativized exponential and probabilistic complexity classes
- Proof verification and the hardness of approximation problems
- Strong and robustly strong polynomial-time reducibilities to sparse sets
- Strong nondeterministic polynomial-time reducibilities
Cited in
(3)
This page was built for publication: AM\(_{\text{exp}}\nsubseteq (\text{NP} \cap \text{coNP})\)/poly
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1029043)
