NP-Hard Problems

[attachment=17993]

Efficient’ Problems
A generally-accepted minimum requirement for an algorithm to be considered ‘efficient’ is that its
running time is polynomial: O(nc) for some constant c, where n is the size of the input.1 Researchers
recognized early on that not all problems can be solved this quickly, but we had a hard time figuring
out exactly which ones could and which ones couldn’t. there are several so-called NP-hard problems,
which most people believe cannot be solved in polynomial time, even though nobody can prove a
super-polynomial lower bound.



P, NP, and co-NP
A decision problem is a problem whose output is a single boolean value: YES or NO.2 Let me define three
classes of decision problems:
 P is the set of decision problems that can be solved in polynomial time.3 Intuitively, P is the set of
problems that can be solved quickly.
 NP is the set of decision problems with the following property: If the answer is YES, then there is
a proof of this fact that can be checked in polynomial time. Intuitively, NP is the set of decision
problems where we can verify a YES answer quickly if we have the solution in front of us.
 co-NP is the opposite of NP. If the answer to a problem in co-NP is NO, then there is a proof of this
fact that can be checked in polynomial time.
For example, the circuit satisfiability problem is in NP. If the answer is YES, then any set of m input
values that produces TRUE output is a proof of this fact; we can check the proof by evaluating the circuit
in polynomial time. It is widely believed that circuit satisfiability is not in P or in co-NP, but nobody
actually knows.



21.4 Reductions and SAT
To prove that a problem is NP-hard, we use a reduction argument. Reducing problem A to another
problem B means describing an algorithm to solve problem A under the assumption that an algorithm for
problem B already exists. You’re already used to doing reductions, only you probably call it something
else, like writing subroutines or utility functions, or modular programming. To prove something is
NP-hard, we describe a similar transformation between problems, but not in the direction that most
people expect.
You should tattoo the following rule of onto the back of your hand.



Maximum Independent (from 3SAT)
For the next few problems we consider, the input is a simple, unweighted graph, and the problem asks
for the size of the largest or smallest subgraph satisfying some structural property.
Let G be an arbitrary graph. An independent set in G is a subset of the vertices of G with no edges
between them. The maximum independent set problem, or simply MAXINDSET, asks for the size of the
largest independent set in a given graph.