September 10, 2002
Stephen Cook posited SAT is NP-Complete in 1971. If SAT is NP-Complete then, as is generally accepted, any polynomial solution of it must also present a polynomial solution of all NP decision problems. It is here argued, however, that NP is not of necessity equivalent to P where it is shown that SAT is contained in P. This due to a paradox, of nature addressed by both Godel and Russell, in regards to the P-NP system in total.
Similar papers 1
August 12, 2002
This paper considers the question of P = NP in context of the polynomial time SAT algorithm. It posits proposition dependent on existence of conjectured problem that even where the algorithm is shown to solve SAT in polynomial time it remains theoretically possible for there to yet exist a non-deterministically polynomial (NP) problem for which the algorithm does not provide a polynomial (P) time solution. The paper leaves open as subject of continuing research the question o...
November 25, 2005
The open question, P=NP?, was presented by Cook (1971). In this paper, a proof that P is not equal to NP is presented. In addition, it is shown that P is not equal to the intersection of NP and co-NP. Finally, the exact inclusion relationships between the classes P, NP and co-NP are presented.
October 28, 2008
SAT is not in P, is true and provable in a simply consistent extension B' of a first order theory B of computing, with a single finite axiom characterizing a universal Turing machine. Therefore, P is not equal to NP, is true and provable in a simply consistent extension B" of B.
January 21, 2010
Removed by arXiv administration. This article was plagiarized directly from Stephen Cook's description of the problem for the Clay Mathematics Institute. See http://gauss.claymath.org:8888/millennium/P_vs_NP/pvsnp.pdf for the original text.
November 14, 2023
This article finds the answer to the question: for any problem from which a non-deterministic algorithm can be derived which verifies whether an answer is correct or not in polynomial time (complexity class NP), is it possible to create an algorithm that finds the right answer to the problem in polynomial time (complexity class P)? For this purpose, this article shows a decision problem and analyzes it to demonstrate that this problem does not belong to the complexity class P...
July 23, 2009
This paper demonstrates that P \not= NP. The way was to generalize the traditional definitions of the classes P and NP, to construct an artificial problem (a generalization to SAT: The XG-SAT, much more difficult than the former) and then to demonstrate that it is in NP but not in P (where the classes P and NP are generalized and called too simply P and NP in this paper, and then it is explained why the traditional classes P and NP should be fixed and replaced by these genera...
April 7, 2008
The purpose of this article is to examine and limit the conditions in which the P complexity class could be equivalent to the NP complexity class. Proof is provided by demonstrating that as the number of clauses in a NP-complete problem approaches infinity, the number of input sets processed per computation performed also approaches infinity when solved by a polynomial time solution. It is then possible to determine that the only deterministic optimization of a NP-complete pr...
September 26, 2011
In this paper we discusses the relationship between the known classes P and NP. We show that the difficulties in solving problem "P versus NP" have methodological in nature. An algorithm for solving any problem is sensitive to even small changes in its formulation. As we will shown in the paper, these difficulties are exactly in the formulation of some problems of the class NP.
January 15, 2024
We distinguish finitarily between algorithmic verifiability, and algorithmic computability, to show that Goedel's 'formally' unprovable, but 'numeral-wise' provable, arithmetical proposition [(Ax)R(x)] can be finitarily evidenced as: algorithmically verifiable as 'always' true, but not algorithmically computable as 'always' true. Hence, though [R(x)] is algorithmically verifiable as a tautology, it is not algorithmically computable as a tautology by any Turing machine, whethe...
September 30, 2022
In this article, we discuss the question of whether P equals NP, we do not follow the line of research of many researchers, which is to try to find such a problem Q, and the problem Q belongs to the class of $\mathcal{NP}$-complete, if the problem Q is proved to belong to $\mathcal{P}$, then $\mathcal{P}$ and $\mathcal{NP}$ are the same, if the problem Q is proved not to belong to $\mathcal{P}$, then $\mathcal{P}$ and $\mathcal{NP}$ are separated. Our research strategy in thi...