# Is P=NP?

### From Mathsreach

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

constructed.

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