NP and reduction

P

P is the set of all decision problems that can be solved in
Polynomial time.

Extended Church-Turing Thesis

Any realistic model of computation can be efficiently
simulated by a Turing machine.
(The ECT is probably false!Probable counter-example: Quantum computing,However, the ECT is true for the classic models of computation
underlying our laptops)

NP problem

We do not know of polynomial-time algorithms for these problems, and we cannot prove that no
polynomial-time algorithm exists.

NP stands for Nondeterministic Polynomial time.

NP is a set of problems that there is a polynomial-time algorithm that verify if a solution to the problem is correct.
Note that showing that a problem is in NP does not mean that the problem can be solved in polynomial time. It only means that a proposed solution can be verified in polynomial time.

All problems in P are also in NP, we do not know if P=NP.

NP-hardness

We say that a problem Y is NP-hard if every problem in NP can be Karp-reduced to Y. To prove NP-hardness for Y we only have to find
one other NP-hard problem X and reduce X to Y.

NP-complete problem

A large class of problems in this “gray area” has been characterized,
and it has been proved that they are equivalent in the following sense: a polynomial-time algorithm for any one of them would imply the existence of a polynomial-time algorithm for all of them. These are the NP-complete problems.

Every problem in NP can be reduced to X. We will call such an X an NP-complete problem.

To prove a problem is np-complete, we need to prove it lies in Np and it is np-hard. In NP is proved by verifying the solution in polynomial time. Np-hard is proved by using Karp-reduction from known NP-hard problem.

the NP-complete problems are the hardest problems in NP

The Cook-Levin Theorem

The Sat problem is NP-hard.

Hamiltonian Cycle

Reduction from Sat to Hamiltonian Cycle.

Travelling Salesman

Reduction from Hamiltonian Cycle

Graph Coloring

Graph Coloring is NP-hard.
2-coloring is not NP-hard.

Vertex Cover

we say that a set of nodes S is a vertex cover if every edge e has at least one end in S.

Set Cover

Given a set U of n elements, a collection S1,…, Sm of subsets of U, and
a number k, does there exist a collection of at most k of these sets whose
union is equal to all of U?

CoNP

The complexity class CoNP consists of all problems where a “no” answer can be efficiently verified.
For every NP-complete problem there is a
corresponding CoNP-complete problem.

We do not know if NP=CoNP.

PSPACE

The complexity class PSPACE consists of all problems that can
be solved by an algorithm using at most a polynomial amount of
space.
It is strongly believed that NP != PSPACE, but we do not even
know with certainty whether P != PSPACE or not!

For many 2-player games like Geography, deciding if there is a
winning strategy from a given position is a PSPACE problem

BPP and ZPP

BPP

BPP (Bounded-error Probabilistic Polynomial-time)
consists of all decision problems for which there is a
polynomial-time randomized algorithms that is correct with
probability at least 2=3 on all instances.

ZPP

ZPP (Zero-error Probabilistic Polynomial Time)
consists of all decision problems for which there is a Las Vegas
algorithm running in expected polynomial time.
It is widely believed that P = ZPP = BPP but all three could be
different.