Beyond P^NP=NEXP

DOI10.1007/3-540-59042-0_110MaRDI QIDQ4596658zbMATH OpenOpenAlexFDO

Authors S. Fenner, Lance Fortnow

Publication date 4 December 2017

Published in STACS 95 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-59042-0_110

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Two oracles that force a big crunch
• scientific article; zbMATH DE number 4011940
• Relativizations comparing NP and exponential time
• scientific article; zbMATH DE number 1775405
• On relativized nondeterministic polynomial-time bounded computations

Cited in

(9)

• AM\(_{\text{exp}}\nsubseteq (\text{NP} \cap \text{coNP})\)/poly
• What one has to know when attacking \(\mathsf {P}\) vs. \(\mathsf {NP}\) (extended abstract)
• P ≠ NP ∩ co-NP for Infinite Time Turing Machines
• Beyond NP
• On the cutting edge of relativization: the resource bounded injury method
• Automata, Languages and Programming
• scientific article; zbMATH DE number 7676615 (Why is no real title available?)
• Two oracles that force a big crunch
• \(S_{k,\text{exp}}\) does not prove \(\text{NP} = \text{co-NP}\) uniformly

This page was built for publication: Beyond \(\mathbf{P}^{\mathbf{NP}}=\mathbf{NEXP}\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4596658)