Is P=NP?

From Mathsreach

Jump to: navigation, search

Are complexity classes P and NP equivalent?

Simply: If positive solutions to a yes/no problem can be verified quickly, can they
also be computed quickly?

Example: Does some subset of the set {−2, −3, 15, 14, 7, −10} add up to zero?
Yes, and it’s easy to check that {−2, −3, −10, 15} does, with simple addition.
Verifying that a subset adds up to zero can be much faster than finding the subset in
the first place. How to find such a subset when the set itself is large is called the
subset-sum problem. This is an example of a problem in the class NP (nondeterministic
polynomial time). Verifying the answer is an example of a problem in  the class P (polynomial time).

Discipline: Computational complexity theory, which deals with the resources,
such as time (expressed in the number of steps) and space (expressed as memory),
needed to solve a given problem.

Incentive: $US1million, one of the seven Millennium Prize Problems of the USAbased
Clay Mathematics Institute.

Unusual aspect: Involves a computer that has never been built. Turing machines, first
described by English mathematician and cryptographer Alan Turing in 1936, were
a thought experiment to simulate the logic of any computer that could possibly be

Consequences: Remarkably, a polynomial-time solution to a problem
in NP would provide polynomial-time solutions to all problems in NP. If P=NP,
then this would simplify many currently intractable mathematical problems in
fields as varied as operations research, logistics and biology. On the other hand,
a proof that P ≠ NP would show that many common problems cannot be
solved efficiently, moving the attention of researchers to partial solutions or other
problems. As experts believe that P ≠ NP, this is happening already.

NZIMA link: 2004 Logic and Computation programme.

Published in IMAges 3 - October 2007