�ݺ�ߣ

P, NP, NP-Hard & NP-complete
problems
Prof. Shaik Naseera
Department of CSE
JNTUACEK, Kalikiri
1

Objectives
• P, NP, NP-Hard and NP-Complete
• Solving 3-CNF Sat problem
• Discussion of Gate Questions
2

Types of Problems
• Trackable
• Intrackable
• Decision
• Optimization
3
Trackable : Problems that can be solvable
in a reasonable(polynomial) time.
Intrackable : Some problems are
intractable, as they grow large, we are
unable to solve them in reasonable time.

Tractability
• What constitutes reasonable time?
– Standard working definition: polynomial time
– On an input of size n the worst-case running
time is O(nk) for some constant k
– O(n2), O(n3), O(1), O(n lg n), O(2n), O(nn), O(n!)
– Polynomial time: O(n2), O(n3), O(1), O(n lg n)
– Not in polynomial time: O(2n), O(nn), O(n!)
• Are all problems solvable in polynomial
time?
– No: Turing’s “Halting Problem” is not solvable
by any computer, no matter how much time is
given.
4

Optimization/Decision Problems
• Optimization Problems
– An optimization problem is one which asks,
“What is the optimal solution to problem X?”
– Examples:
• 0-1 Knapsack
• Fractional Knapsack
• Minimum Spanning Tree
• Decision Problems
– An decision problem is one with yes/no answer
– Examples:
• Does a graph G have a MST of weight  W?
5

Optimization/Decision Problems
• An optimization problem tries to find an optimal solution
• A decision problem tries to answer a yes/no question
• Many problems will have decision and optimization versions
– Eg: Traveling salesman problem
• optimization: find hamiltonian cycle of minimum
weight
• decision: is there a hamiltonian cycle of weight  k
6

P, NP, NP-Hard, NP-Complete
-Definitions
7

The Class P
P: the class of problems that have polynomial-time
deterministic algorithms.
– That is, they are solvable in O(p(n)), where p(n) is a
polynomial on n
– A deterministic algorithm is (essentially) one that always
computes the correct answer
8

Sample Problems in P
• MST
• Sorting
• Others?
9

The class NP
NP: the class of decision problems that are solvable in
polynomial time on a nondeterministic machine (or with
a nondeterministic algorithm)
– (A determinstic computer is what we know)
– A nondeterministic computer is one that can “guess” the right
answer or solution
• Think of a nondeterministic computer as a parallel
machine that can freely spawn an infinite number of
processes
• Thus NP can also be thought of as the class of
problems “whose solutions can be verified in polynomial time”
• Note that NP stands for “Nondeterministic
Polynomial-time”
10

Sample Problems in NP
• MST
• Others?
– Traveling Salesman
– Graph Coloring
– Satisfiability (SAT)
• the problem of deciding whether a given
Boolean formula is satisfiable
11

P And NP Summary
• P = set of problems that can be solved in
polynomial time
– Examples: Fractional Knapsack, …
• NP = set of problems for which a solution can be
verified in polynomial time
– Examples: Fractional Knapsack,…, TSP, CNF
SAT, 3-CNF SAT
• Clearly P  NP
• Open question: Does P = NP?
– P ≠ NP

NP-hard
• What does NP-hard mean?
– A lot of times you can solve a problem by reducing it to
a different problem. I can reduce Problem B to
Problem A if, given a solution to Problem A, I can easily
construct a solution to Problem B. (In this case,
"easily" means "in polynomial time.“).
• A problem is NP-hard if all problems in NP
are polynomial time reducible to it, ...
•
Every problem in NP is reducible to HC in
polynomial time. Ex:- TSP is reducible to
HC.
13
Example: lcm(m, n) = m * n / gcd(m, n),
B A
Ex:- Hamiltonian Cycle

NP-complete problems
• A problem is NP-complete if the problem is
both
– NP-hard, and
– NP.

Reduction
• A problem R can be reduced to another
problem Q if any instance of R can be
rephrased to an instance of Q, the
solution to which provides a solution to the
instance of R
– This rephrasing is called a transformation
• Intuitively: If R reduces in polynomial time
to Q, R is “no harder to solve” than Q
• Example: lcm(m, n) = m * n / gcd(m, n),
lcm(m,n) problem is reduced to gcd(m, n)
problem

NP-Hard and NP-Complete
• If R is polynomial-time reducible to Q,
we denote this R p Q
• Definition of NP-Hard and NP-
Complete:
– If all problems R  NP are polynomial-time
reducible to Q, then Q is NP-Hard
– We say Q is NP-Complete if Q is NP-Hard
and Q  NP
• If R p Q and R is NP-Hard, Q is also
NP-Hard

Summary
• P is set of problems that can be solved by a
deterministic Turing machine in Polynomial
time.
• NP is set of problems that can be solved by
a Non-deterministic Turing Machine in
Polynomial time. P is subset of NP (any
problem that can be solved by
deterministic machine in polynomial time
can also be solved by non-deterministic
machine in polynomial time) but P≠NP.
18

• Some problems can be translated into one
another in such a way that a fast solution to
one problem would automatically give us a fast
solution to the other.
• There are some problems that every single
problem in NP can be translated into, and a fast
solution to such a problem would automatically
give us a fast solution to every problem in NP.
This group of problems are known as NP-
Complete. Ex:- Clique
• A problem is NP-hard if an algorithm for solving
it can be translated into one for solving any NP-
problem (nondeterministic polynomial time)
problem. NP-hard therefore means "at least as
hard as any NP-problem," although it might, in
fact, be harder.
19

First NP-complete problem—
Circuit Satisfiability (problem
definition)
• Boolean combinational circuit
– Boolean combinational elements, wired
together
– Each element, inputs and outputs (binary)
– Limit the number of outputs to 1.
– Called logic gates: NOT gate, AND gate, OR
gate.
– true table: giving the outputs for each
setting of inputs
– true assignment: a set of boolean inputs.
– satisfying assignment: a true assignment
causing the output to be 1.
20

Circuit Satisfiability
Problem: definition
• Circuit satisfying problem: given a boolean
combinational circuit composed of AND,
OR, and NOT, is it stisfiable?
• CIRCUIT-SAT={<C>: C is a satisfiable
boolean circuit}
• Implication: in the area of computer-aided
hardware optimization, if a subcircuit
always produces 0, then the subcircuit can
be replaced by a simpler subcircuit that
omits all gates and just output a 0.
21

22
Two instances of circuit satisfiability problems

Solving circuit-satisfiability
problem
• Intuitive solution:
– for each possible assignment, check
whether it generates 1.
– suppose the number of inputs is k, then
the total possible assignments are 2k.
So the running time is (2k). When the
size of the problem is (k), then the
running time is not polynomial.
23

24
Example of reduction of CIRCUIT-SAT to SAT
= x10(x10(x7 x8 x9))
(x9(x6  x7))
(x8(x5  x6))
(x7(x1 x2 x4))
(x6 x4))
(x5(x1  x2))
(x4x3)
REDUCTION: = x10= x7 x8 x9=(x1 x2 x4)  (x5  x6) (x6  x7)
=(x1 x2 x4)  ((x1  x2)  x4) (x4  (x1 x2 x4))=….

Conversion to 3 CNF
• The result is that in ', each clause has at most
three literals.
• Change each clause into conjunctive normal form as
follows:
– Construct a true table, (small, at most 8 by 4)
– Write the disjunctive normal form for all true-table items
evaluating to 0
– Using DeMorgan law to change to CNF.
• The resulting '' is in CNF but each clause has 3 or
less literals.
• Change 1 or 2-literal clause into 3-literal clause as
follows:
– If a clause has one literal l, change it to (lpq)(lpq)
(lpq) (lpq).
– If a clause has two literals (l1 l2), change it to (l1 l2 p) 
(l1 l2 p).
25

26
Example of a polynomial-time reduction:
We will reduce the
3CNF-satisfiability problem
to the
CLIQUE problem

27
3CNF formula:
)
(
)
(
)
(
)
( 6
5
4
4
6
3
6
5
3
3
2
1 x
x
x
x
x
x
x
x
x
x
x
x 










Each clause has three literals
3CNF-SAT ={ : is a satisfiable
3CNF formula}
w w
Language:
literal
clause

28
A 5-clique in graph
CLIQUE = { : graph
contains a -clique}

 k
G, G
k
G
Language:

29
)
(
)
(
)
(
)
( 4
3
2
3
2
1
4
2
1
4
2
1 x
x
x
x
x
x
x
x
x
x
x
x 










Clause 2
Clause 1
Clause 3
1
x
2
x
1
x 2
x 4
x
1
x
2
x
3
x
2
x
4
x
4
x
3
x
Transform formula to graph.
Example:
Clause 4
Create Nodes:

30
)
(
)
(
)
(
)
( 4
3
2
3
2
1
4
2
1
4
2
1 x
x
x
x
x
x
x
x
x
x
x
x 










1
x
2
x
1
x 2
x 4
x
1
x
2
x
2
x
4
x
4
x
3
x
3
x
Add link from a literal to a literal in every
other clause, except the complement



31
)
(
)
(
)
(
)
( 4
3
2
3
2
1
4
2
1
4
2
1 x
x
x
x
x
x
x
x
x
x
x
x 










1
x
2
x
1
x 2
x 4
x
1
x
2
x
3
x
2
x
4
x
4
x
3
x
Resulting Graph

32
1
0
0
1
4
3
2
1




x
x
x
x
1
)
(
)
(
)
(
)
( 4
3
2
3
2
1
4
2
1
4
2
1 










 x
x
x
x
x
x
x
x
x
x
x
x
1
x
2
x
1
x 2
x 4
x
1
x
2
x
3
x
2
x
4
x
4
x
3
x
The formula is satisfied if and only if
the Graph has a 4-clique
The objective is to find a clique of size 4,
where 4 is the number of clauses.
End of Proof

33
Theorem:
If: a. Language is NP-complete
b. Language is in NP
c. is polynomial time reducible to
A
A B
B
Then: is NP-complete
B

34
Corollary: CLIQUE is NP-complete
Proof:
b. CLIQUE is in NP
c. 3CNF-SAT is polynomial reducible to CLIQUE
a. 3CNF-SAT is NP-complete
Apply previous theorem with
A=3CNF-SAT and B=CLIQUE
(shown earlier)

44
Explanation: The problem of finding
whether there exist a Hamiltonian
Cycle or not is NP Hard and NP
Complete Both.
Finding a Hamiltonian cycle in a
graph G = (V,E) with V divisible by 3
is also NP Hard.
Q. No. 10
There exist: search problem

�ݺ�ߣ

DAA.pdf

Recommended

More Related Content

Similar to DAA.pdf (20)

More from Arivukkarasu Dhanapal (6)

Recently uploaded (20)

DAA.pdf