P is not equal to NP
2013 (English)Report (Other academic)
The problem of computing whether any formula of propositional logic is satisfiable is not in P. Therefore, P is not equal to NP. The proofs are informal about formal proofs in a first-order theory B axiomatizing Turing’s theory of computing. However, the informal proofs can be converted into formal proofs in Hilbert’s proof theory, and proved using a theorem prover.
Place, publisher, year, edition, pages
Uppsala: Department of Informatics and media , 2013. , 7 p.
Research report / Uppsala University, Department of Information Science, ISSN 1403-7572 ; 2013:5
Computer and Information Science
IdentifiersURN: urn:nbn:se:uu:diva-208283OAI: oai:DiVA.org:uu-208283DiVA: diva2:651748
This report is an updated version of a report with the same title published in 2008. (See http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-86762.)2013-09-272013-09-272013-11-13Bibliographically approved