2007/11/07 by Alfredo von Reckow, von Reckow, Alfredo
Computer Science · #AI-based Problem Solving and Planning #Computational Complexity (cs.CC) #F.1.3 #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #Logic, Reasoning, and Knowledge #Rough Sets and Fuzzy Logic #cs.CC #cs.LO
paper · pdf · doi:10.48550/arxiv.0711.1177
arxiv created 2007/11/07 · openalex publication_date 2007/11/07 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In order to prove that the P of problems is different to the NP class, we consider the satisfability problem of propositional calculus formulae, which is an NP-complete problem. It is shown that, for every search algorithm A, there is a set E(A) containing propositional calculus formulae, each of which requires the algorithm A to take non-polynomial time to find the truth-values of its propositional letters satisfying it. Moreover, E(A)'s size is an exponential function of n, which makes it impossible to detect such formulae in a polynomial time. Hence, the satisfability problem does not have a polynomial complexity