What one has to know when attacking \(\mathsf{P}\) vs.\(\mathsf{NP}\)

DOI10.1016/j.jcss.2019.06.004zbMath1436.68126OpenAlexW2967942453MaRDI QIDQ2009642

Peter Rossmanith, Juraj Hromkovič

Publication date: 29 November 2019

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2019.06.004

zbMATH Keywords

computational complexitydeterminismrandomizationprovabilitynondeterminismP vs. NP

Mathematics Subject Classification ID

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

Cites Work

• The method of forced enumeration for nondeterministic automata
• Nondeterministic Space is Closed under Complementation
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• IP = PSPACE
• The knowledge complexity of interactive proof-systems
• Information-Theoretic Limitations of Formal Systems
• Logical basis for information theory and probability theory
• Classes of Recursively Enumerable Sets and Their Decision Problems
• Natural proofs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item