What one has to know when attacking P vs.NP

DOI10.1016/J.JCSS.2019.06.004MaRDI QIDQ2009642zbMATH OpenOpenAlexFDO

Authors 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 complexitydeterminismnondeterminismP vs. NPprovabilityrandomization

Mathematics Subject Classification ID

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

Recommendations

• What one has to know when attacking \(\mathsf {P}\) vs. \(\mathsf {NP}\) (extended abstract)
• \({\mathcal P}\), \({\mathcal{NP}}\) and mathematics -- a computational complexity perspective
• \(\mathrm P \overset {?} {=} \mathrm{NP}\)
• Towards NP-P via proof complexity and search
• Concerning existential definition of the class NP: Theoretical analysis of an alternative approach

Cites work

• Classes of Recursively Enumerable Sets and Their Decision Problems
• scientific article; zbMATH DE number 5604094 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3489106 (Why is no real title available?)
• scientific article; zbMATH DE number 3188505 (Why is no real title available?)
• Information-Theoretic Limitations of Formal Systems
• IP = PSPACE
• Logical basis for information theory and probability theory
• Natural proofs
• Nondeterministic Space is Closed under Complementation
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• The knowledge complexity of interactive proof-systems
• The method of forced enumeration for nondeterministic automata

Cited in

(3)

• What one has to know when attacking \(\mathsf {P}\) vs. \(\mathsf {NP}\) (extended abstract)
• Why is the \(\mathrm{P}=?\mathrm{NP}\) question so difficult
• Kolmogorov complexity and nondeterminism versus determinism for polynomial time computations

This page was built for publication: What one has to know when attacking \(\mathsf{P}\) vs.\(\mathsf{NP}\)

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