Does NP not equal P?

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

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...

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

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.

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.

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 ...

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...

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 ...

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.

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...