11-08-2012, 10:34 AM
THE P VERSUS NP PROBLEM
p vs np.pdf (Size: 172.07 KB / Downloads: 34)
Statement of the Problem
The P versus NP problem is to determine whether every language accepted
by some nondeterministic algorithm in polynomial time is also accepted by some
(deterministic) algorithm in polynomial time. To define the problem precisely it
is necessary to give a formal model of a computer. The standard computer model
in computability theory is the Turing machine, introduced by Alan Turing in 1936
[37]. Although the model was introduced before physical computers were built, it
nevertheless continues to be accepted as the proper computer model for the purpose
of defining the notion of computable function.
Informally the class P is the class of decision problems solvable by some algorithm
within a number of steps bounded by some fixed polynomial in the length of the
input. Turing was not concerned with the efficiency of his machines, rather his
concern was whether they can simulate arbitrary algorithms given sufficient time. It
turns out, however, Turing machines can generally simulate more efficient computer
models (for example, machines equipped with many tapes or an unbounded random
access memory) by at most squaring or cubing the computation time. Thus P is a
robust class and has equivalent definitions over a large class of computer models.
Here we follow standard practice and define the class P in terms of Turing machines.
Formally the elements of the class P are languages. Let be a finite alphabet
(that is, a finite nonempty set) with at least two elements, and let be the set
of finite strings over . Then a language over is a subset L of . Each Turing
machine M has an associated input alphabet . For each string w in there is
a computation associated with M with input w. (The notions of Turing machine
and computation are defined formally in the appendix.) We say that M accepts w
if this computation terminates in the accepting stateStatement of the Problem.
History and Importance
The importance of the P vs NP question stems from the successful theories of
NP-completeness and complexity-based cryptography, as well as the potentially
stunning practical consequences of a constructive proof of P = NP.
The theory of NP-completeness has its roots in computability theory, which
originated in the work of Turing, Church, G¨odel, and others in the 1930s. The
computability precursors of the classes P and NP are the classes of decidable and
c.e. (computably enumerable) languages, respectively. We say that a language L is
c.e. (or semi-decidable) iff L = L(M) for some Turing machine M.
The Conjecture and Attempts to Prove It
Most complexity theorists believe that P 6= NP. Perhaps this can be partly
explained by the potentially stunning consequences of P = NP mentioned above,
but there are better reasons. We explain these by considering the two possibilities
in turn: P = NP and P 6= NP.
Suppose first that P = NP and consider how one might prove it. The obvious
way is to exhibit a polynomial-time algorithm for 3-SAT or one of the other
thousand or so known NP-complete problems, and, indeed, many false proofs have
been presented in this form. There is a standard toolkit available [7] for devising
polynomial-time algorithms, including the greedy method, dynamic programming,
reduction to linear programming, etc. These are the subjects of a course on algorithms,
typical in undergraduate computer science curriculums. Because of their
importance in industry, a vast number of programmers and engineers have attempted
to find efficient algorithms for NP-complete problems over the past 30
years, without success. There is a similar strong motivation for breaking the cryptographic
schemes that assume P 6= NP for their security.
p vs np.pdf (Size: 172.07 KB / Downloads: 34)
Statement of the Problem
The P versus NP problem is to determine whether every language accepted
by some nondeterministic algorithm in polynomial time is also accepted by some
(deterministic) algorithm in polynomial time. To define the problem precisely it
is necessary to give a formal model of a computer. The standard computer model
in computability theory is the Turing machine, introduced by Alan Turing in 1936
[37]. Although the model was introduced before physical computers were built, it
nevertheless continues to be accepted as the proper computer model for the purpose
of defining the notion of computable function.
Informally the class P is the class of decision problems solvable by some algorithm
within a number of steps bounded by some fixed polynomial in the length of the
input. Turing was not concerned with the efficiency of his machines, rather his
concern was whether they can simulate arbitrary algorithms given sufficient time. It
turns out, however, Turing machines can generally simulate more efficient computer
models (for example, machines equipped with many tapes or an unbounded random
access memory) by at most squaring or cubing the computation time. Thus P is a
robust class and has equivalent definitions over a large class of computer models.
Here we follow standard practice and define the class P in terms of Turing machines.
Formally the elements of the class P are languages. Let be a finite alphabet
(that is, a finite nonempty set) with at least two elements, and let be the set
of finite strings over . Then a language over is a subset L of . Each Turing
machine M has an associated input alphabet . For each string w in there is
a computation associated with M with input w. (The notions of Turing machine
and computation are defined formally in the appendix.) We say that M accepts w
if this computation terminates in the accepting stateStatement of the Problem.
History and Importance
The importance of the P vs NP question stems from the successful theories of
NP-completeness and complexity-based cryptography, as well as the potentially
stunning practical consequences of a constructive proof of P = NP.
The theory of NP-completeness has its roots in computability theory, which
originated in the work of Turing, Church, G¨odel, and others in the 1930s. The
computability precursors of the classes P and NP are the classes of decidable and
c.e. (computably enumerable) languages, respectively. We say that a language L is
c.e. (or semi-decidable) iff L = L(M) for some Turing machine M.
The Conjecture and Attempts to Prove It
Most complexity theorists believe that P 6= NP. Perhaps this can be partly
explained by the potentially stunning consequences of P = NP mentioned above,
but there are better reasons. We explain these by considering the two possibilities
in turn: P = NP and P 6= NP.
Suppose first that P = NP and consider how one might prove it. The obvious
way is to exhibit a polynomial-time algorithm for 3-SAT or one of the other
thousand or so known NP-complete problems, and, indeed, many false proofs have
been presented in this form. There is a standard toolkit available [7] for devising
polynomial-time algorithms, including the greedy method, dynamic programming,
reduction to linear programming, etc. These are the subjects of a course on algorithms,
typical in undergraduate computer science curriculums. Because of their
importance in industry, a vast number of programmers and engineers have attempted
to find efficient algorithms for NP-complete problems over the past 30
years, without success. There is a similar strong motivation for breaking the cryptographic
schemes that assume P 6= NP for their security.