ID: cs/0209015

Does NP not equal P?

September 10, 2002

View on ArXiv

Similar papers 4

A Polynomial Time Algorithm for SAT

March 29, 2007

84% Match
Sergey Gubin
Computational Complexity
Discrete Mathematics
Data Structures and Algorith...
Logic in Computer Science

Article presents the compatibility matrix method and illustrates it with the application to P vs NP problem. The method is a generalization of descriptive geometry: in the method, we draft problems and solve them utilizing the image creation technique. The method reveals: P = NP = PSPACE

Find SimilarView on arXiv

On the principal impossibility to prove P=NP

November 15, 2012

84% Match
Natalia L. Malinina
Computational Complexity

The material of the article is devoted to the most complicated and interesting problem -- a problem of P = NP?. This research was presented to mathematical community in Hyderabad during International Congress of Mathematicians. But there it was published in a very brief form, so this article is an attempt to give those, who are interested in the problem, my reasoning on the theme. It is not a proof in full, because it is very difficult to prove something, which is not provabl...

Find SimilarView on arXiv

The Complexity of X3SAT: P = NP = PSPACE

December 10, 2020

84% Match
Latif Salum
Computational Complexity

This paper shows that P = NP = PSPACE. It also tackles Graph Isomorphism.

Find SimilarView on arXiv

Critique of J. Kim's "P is not equal to NP by Modus Tollens"

April 22, 2014

84% Match
Dan Hassin, Adam Scrivener, Yibo Zhou
Computational Complexity

This paper is a critique of version three of Joonmo Kim's paper entitled "P is not equal to NP by Modus Tollens. [arXiv:1403.4143v3]" After summarizing Kim's proof, we note that the logic that Kim uses is inconsistent, which provides evidence that the proof is invalid. To show this, we will consider two reasonable interpretations of Kim's definitions, and show that "P is not equal to NP" does not seem to follow in an obvious way using any of them.

Find SimilarView on arXiv

P is not equal to NP by Modus Tollens

March 17, 2014

84% Match
Joonmo Kim
Computational Complexity

An artificially designed Turing Machine algorithm $\mathbf{M}_{}^{o}$ generates the instances of the satisfiability problem, and check their satisfiability. Under the assumption $\mathcal{P}=\mathcal{NP}$, we show that $\mathbf{M}_{}^{o}$ has a certain property, which, without the assumption, $\mathbf{M}_{}^{o}$ does not have. This leads to $\mathcal{P}\neq\mathcal{NP}$ $ $ by modus tollens.

Find SimilarView on arXiv

Inquiry of P-reduction in Cook's 1971 Paper -- from Oracle machine to Turing machine

April 30, 2019

84% Match
JianMing Zhou, Yu Li
Other Computer Science

In this paper, we inquire the key concept P-reduction in Cook's theorem and reveal that there exists the fallacy of definition in P-reduction caused by the disguised displacement of NDTM from Oracle machine to Turing machine. The definition or derivation of P-reduction is essentially equivalent to Turing's computability. Whether NP problems might been reduced to logical forms (tautology or SAT) or NP problems might been reduced each other, they have not been really proven in ...

Find SimilarView on arXiv

Case Study of the Proof of Cook's theorem - Interpretation of A(w)

April 30, 2019

84% Match
Yu Li
Computational Complexity

Cook's theorem is commonly expressed such as any polynomial time-verifiable problem can be reduced to the SAT problem. The proof of Cook's theorem consists in constructing a propositional formula A(w) to simulate a computation of TM, and such A(w) is claimed to be CNF to represent a polynomial time-verifiable problem w. In this paper, we investigate A(w) through a very simple example and show that, A(w) has just an appearance of CNF, but not a true logical form. This case stu...

Find SimilarView on arXiv

Principle of Conservation of Computational Complexity

December 4, 2017

83% Match
Gerald Friedland, Alfredo Metere
Computational Complexity

In this manuscript, we derive the principle of conservation of computational complexity. We measure computational complexity as the number of binary computations (decisions) required to solve a problem. Every problem then defines a unique solution space measurable in bits. For an exact result, decisions in the solution space can neither be predicted nor discarded, only transferred between input and algorithm. We demonstrate and explain this principle using the example of the ...

Find SimilarView on arXiv

We must know -- We shall know

April 17, 2020

83% Match
Jacob Zimbarg Sobrinho
Logic

In this article, I focus on the resiliency of the P=?NP problem. The main point to deal with is the change of the underlying logic from first to second-order logic. In this manner, after developing the initial steps of this change, I can hint that the solution goes in the direction of the coincidence of both classes, i.e., P=NP.

Find SimilarView on arXiv

Computer-Simulation Model Theory (P= NP is not provable)

June 20, 2019

83% Match
Rasoul Ramezanian
Computational Complexity
Formal Languages and Automat...
Logic in Computer Science
Logic

The simulation hypothesis says that all the materials and events in the reality (including the universe, our body, our thinking, walking and etc) are computations, and the reality is a computer simulation program like a video game. All works we do (talking, reasoning, seeing and etc) are computations performed by the universe-computer which runs the simulation program. Inspired by the view of the simulation hypothesis (but independent of this hypothesis), we propose a new met...

Find SimilarView on arXiv