On the P vs NP question: a proof of inequality

MaRDI QIDQ5091709zbMATH OpenFDO

Authors Angelo Raffaele Meo

Publication date 26 July 2022

Full work available at URL https://arxiv.org/abs/1802.05484

zbMATH Keywords

NP-completeconjunctive normal formcore function3SAT

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Switching theory, applications of Boolean algebras to circuits and networks (94C11) Applications of graph theory to circuits and networks (94C15) Boolean functions (06E30) Complexity of computation (including implicit computational complexity) (03D15) Boolean functions (94D10) Networks and circuits as models of computation; circuit complexity (68Q06)

Recommendations

• scientific article; zbMATH DE number 4001486
• scientific article; zbMATH DE number 3978381
• A short essay towards if P not equal NP
• \(\mathrm P \overset {?} {=} \mathrm{NP}\)
• Fast-Growing Functions and the P vs. NP Question

Cited in

(9)

• Some Theorems Concerning the Core Function
• scientific article; zbMATH DE number 62443 (Why is no real title available?)
• A simple proof that the \((n^{2} - 1)\)-puzzle is hard
• scientific article; zbMATH DE number 7676615 (Why is no real title available?)
• Fast-Growing Functions and the P vs. NP Question
• What one has to know when attacking \(\mathsf {P}\) vs. \(\mathsf {NP}\) (extended abstract)
• scientific article; zbMATH DE number 7683979 (Why is no real title available?)
• scientific article; zbMATH DE number 218550 (Why is no real title available?)
• A comment on \('NP=P?'\) and restricted partitions

This page was built for publication: On the P vs NP question: a proof of inequality

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