Does NP not equal P?

This article discusses completeness of Boolean Algebra as First Order Theory in Goedel's meaning. If Theory is complete then any possible transformation is equivalent to some transformation using axioms, predicates etc. defined for this theory. If formula is to be proved (or disproved) then it has to be reduced to axioms. If every transformation is deducible then also optimal transformation is deducible. If every transformation is exponential then optimal one is too, what all...

We show that, if PA has no non-standard models, then P=/=NP. We then give an elementary proof that PA has no non-standard models.

In complexity theory, there exists a famous unsolved problem whether NP can be P or not. In this paper, we discuss this aspect in SAT (satisfiability) problem, and it is shown that the SAT can be solved in plynomial time by means of quantum algorithm.

This paper discusses why P and NP are likely to be different. It analyses the essence of the concepts and points out that P and NP might be diverse by sheer definition. It also speculates that P and NP may be unequal due to natural laws.

The notion of nondeterminism has disappeared from the current definition of NP, which has led to ambiguities in understanding NP, and caused fundamental difficulties in studying the relation P versus NP. In this paper, we question the equivalence of the two definitions of NP, the one defining NP as the class of problems solvable by a nondeterministic Turing machine in polynomial time, and the other defining NP as the class of problems verifiable by a deterministic Turing mach...

This paper refutes the validity of the polynomial-time algorithm for solving satisfiability proposed by Sergey Gubin. Gubin introduces the algorithm using 3-SAT and eventually expands it to accept a broad range of forms of the Boolean satisfiability problem. Because 3-SAT is NP-complete, the algorithm would have implied P = NP, had it been correct. Additionally, this paper refutes the correctness of his polynomial-time reduction of SAT to 2-SAT.

In this paper we present simplified proofs of our results NP = coNP = PSPACE.

The P=?NP problem is philosophically solved by showing P is equal to NP in the random access with unit multiply (MRAM) model. It is shown that the MRAM model empirically best models computation hardness. The P=?NP problem is shown to be a scientific rather than a mathematical problem. The assumptions involved in the current definition of the P?=NP problem as a problem involving non deterministic Turing Machines (NDTMs) from axiomatic automata theory are criticized. The proble...

The question of whether the complexity class P is equal to the complexity class NP has been a seemingly intractable problem for over 4 decades. It has been clear that if an algorithm existed that would solve the problems in the NP class in polynomial time then P would equal NP. However, no one has yet been able to create that algorithm or to successfully prove that such an algorithm cannot exist. The algorithm that will be presented in this paper solves the 3-satisfiability o...

This paper demonstrates the relativity of Computability and Nondeterministic; the nondeterministic is just Turing's undecidable Decision rather than the Nondeterministic Polynomial time. Based on analysis about TM, UM, DTM, NTM, Turing Reducible, beta-reduction, P-reducible, isomorph, tautology, semi-decidable, checking relation, the oracle and NP-completeness, etc., it reinterprets The Church-Turing Thesis that is equivalent of the Polynomial time and actual time; it redef...