np hard, np complete, polynomial and non polynomial

NP hard problems and Satisfiability of Boolean formulas in 3-conjunctive
normal form is NP-complete. The argument used here is to show that SAT ϵ NP
applies equally well here to show that 3-CNF-SAT ϵ
NP and The problem we shall use, is the circuit-satisfiability problem, in
which we are given a Boolean combinational circuit composed of
AND, OR, and NOT gates, and we wish to know whether there
exists some set of Boolean inputs to this circuit that causes its
output to be 1

1. P, NP, NP-HARD AND
NP-COMPLETE
Algorithms & Complexity

2. Complexity definitions: A Review

⚫Big-Oh
⚫Big-Theta
⚫Big - Omega

3. Big Oh (O)




•f(n)= O(g(n)) iff there exist
positive constants c and n
0

such that f(n) ≤ cg(n) for all
n ≥ n
0

•O-notation to give an upper
bound on a function

4. Omega Notation (Ω)

Bigoh(O) provides an asymptotic
upper bound on a function.

Omega(Ω) provides an
asymptotic lower bound on a
function.

5. Theta Notation (θ)

Theta notation is used when
function f can be bounded both
from above and below by the
same function g

6. Complexity graph

7. Polynomial-Time Algorithms
⚫On an input of size n the worst-case running time is O(n
k
)
for some constant k like O(n
2
), O(n
3
), O(1), O(n lg n), O(2
n
),
O(n
n
), O(n!)
⚫Polynomial time: O(n
2
), O(n
3
), O(1), O(n lg n)
⚫Not in polynomial time: O(2
n
), O(n
n
), O(n!)
⚫Are some problems solvable in polynomial time?
⚫Yes: many algorithms provide polynomial-time solutions to some
problems.
⚫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
⚫Most problems that do not yield polynomial-time
algorithms are either optimization or decision problems.

8. Optimization / Decision Problems
⚫Optimization Problems
⚫An optimization problem tries to find an optimal solution. An
optimization problem is one which asks, “What is the optimal solution to
problem X?”
⚫Examples:
⚫Minimum Spanning Tree (MST),
⚫Travelling salesperson,
⚫Max flow Min Cut
⚫and many more……….
⚫Decision Problems
⚫An decision problem is one with yes / no answer
⚫Examples:
⚫Sum of Subsets,
⚫Does a graph G have a MST of weight ≤ W?
⚫Whether a graph has a vertex cover of a given size k?

9. Cont…
⚫Many problems will have Optimization and Decision versions.
⚫Eg: Traveling salesperson problem
⚫Optimization: find Hamiltonian cycle of minimum weight.
(A Hamiltonian cycle is a cycle in an undirected graph that visits
each vertex exactly once and also returns to the starting vertex.)
⚫Decision: is there a Hamiltonian cycle of weight ≤ k
⚫Some problems are decidable, but intractable:
as they grow large, we are unable to solve them in reasonable time.
⚫So question arises: is there a polynomial-time algorithm that solves
the problem?

10. The Class P
P: the class of decision 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
⚫Sample Problems in P
⚫Sorting
⚫Searching
⚫MST and many more…….

11. 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
⚫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”
⚫Some example
▪MST, Hamiltonian Cycle (Traveling Salesman), Vertex Cover
▪Satisfiability (SAT)
⚫the problem of deciding whether a given Boolean formula is satisfiable

12. RELATION BETWEEN P, NP, NP-HARD
AND NP-COMPLETE








NP
PROBLEMS
P
PROBLEMS
NP HARD
PROBLEMS
NP COMPLETE
PROBLEMS
* All the problems in the
yellow boundary are
NP-Hard problems but
those which also come in
NP are NP-Complete

13. How to show the class NP
⚫The class NP consists of those problems that are
“verifiable” in polynomial time.
⚫If we were somehow given a “certificate” of a solution,
then we could verify that the certificate is correct in
time polynomial in the size of the input to the problem.
⚫Example, for 3-CNF satisfiability, a certificate would
be an assignment of values to variables. We could
check in polynomial time that this assignment satisfies
the Boolean formula.

14. Hamiltonian cycles is in NP
⚫Determining whether a directed graph has a Hamiltonian
cycle does not have a polynomial time algorithm (yet!)
⚫However if someone was to give you a certificate (sequence
of vertices), determining whether or not that sequence forms
a Hamiltonian cycle can be done in polynomial time
⚫Therefore Hamiltonian cycles are in NP

15. Circuit Satisfiability

16. The Satisfiability (SAT) Problem
⚫Given a Boolean expression on n variables, can we assign values
such that the expression has truth assignment or expression is
TRUE?
⚫A truth assignment for a Boolean combinational circuit is a set of
Boolean input values.
⚫We say that a one-output Boolean combinational circuit is
satisfiable if it has truth assignment that causes the output of the
circuit to be 1.
⚫Example:



⚫Seems simple enough, but no known deterministic polynomial
time algorithm exists.
⚫But Easy to verify in polynomial time!

17. 2-CNF satisfiability vs. 3-CNF satisfiability:
⚫A Boolean formula contains variables whose values are 0 or 1;
Boolean connectives such as ∧ (AND), ∨ (OR), and ¬ (NOT);
and parentheses.
⚫A Boolean formula is satisfiable if there exists some assignment
of the values 0 and 1 to its variables that causes it to evaluate to
1.
⚫A Boolean formula is in k-conjunctive normal form, or k-CNF,
if it is the AND of clauses of ORs of exactly k variables or their
negations.
⚫For example, the boolean formula
(x1 ∨ ¬x2) ∧ (¬x1 ∨ x3) ∧ (¬x2 ∨ ¬x3) is in 2-CNF.
⚫It has the satisfying assignment x1 = 1; x2 = 0; x3 = 1.
⚫Although we can determine in polynomial time whether a
2-CNF formula is satisfiable, we shall see later that
determining whether a 3-CNF formula is satisfiable is
NP-complete.

18. CNF satisfiability is NP
⚫This problem is in NP. Nondeterministic algorithm:
⚫Guess truth assignment
⚫Check certificate (assignment) to see if it satisfies CNF
(conjunctive normal form) formula
⚫Example:
(A∨¬B ∨ ¬C ) ∧ (¬A ∨ B) ∧ (¬ B ∨ D ∨ F ) ∧ (F ∨ ¬ D)
⚫Truth assignments:
A B C D F
1.0 1 1 0 0
2.1 0 0 0 1
3.1 1 0 0 1
4.... (how many more?)

Checking phase: Θ(n)

19. Review: P And NP Summary
⚫P = set of problems that can be solved in polynomial time
⚫Examples: Searching, Sorting , MST , …..
⚫NP = set of problems for which a solution can be verified in polynomial time
⚫Examples: Vertex cover, Hamiltonian Cycle, CNF SAT, 3-CNF SAT, ….
⚫Clearly P ⊆ NP
⚫Open question: Does P = NP?
⚫It is not hard to show that every problem in P is also in NP, but it is unclear
whether every problem in NP is also in P.
⚫P vs NP Problem:- If it is easy to check that a solution to a problem is
correct, is it also easy to solve the problem? This is the essence of the P vs
NP question.
⚫Example of the NP problem (Hamiltonian Path Problem): given N cities to
visit, how can one do this without visiting a city twice? If you give me a
solution, I can easily check that it is correct. But I cannot so easily find a
solution!!!

20. One example …..
⚫Students believe that every problem assigned to them is
NP-complete in difficulty level, as they have to find the
solutions.
⚫Teaching Assistants, on the other hand, find that their job is
only as hard as NP, as they only have to verify the student’s
answers.
⚫ When some students confound the TAs, even verification
becomes hard.
⚫What is P here??

21. What is not in NP?
⚫Undecidable problems
⚫Given a polynomial with integer coefficients, does it have integer roots
⚫Impossible to check for all the integers
⚫Even a non-deterministic TM has to have a finite number of states!
⚫More on decidability later
⚫Tautology
⚫A Boolean formula that is true for all possible assignments
⚫Here just one ‘verifier’ will not work. You have to try all possible
values

22. 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

24. NP - hard
⚫What are the hardest problems in NP?


⚫That notation means that L
1
is reducible in polynomial time
to L
2
.
⚫The less than symbol basically means that the time taken to
solve L
1
is no worse that a polynomial factor away from the
time taken to solve L
2
.
⚫A problem (a language L) is said to NP-hard if every
problem in NP can be poly time reduced to it.

25. NP-complete problems(whose status is unknown)
⚫

26. 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 ????

27. A first NP-complete problem
⚫Cook’s theorem (1971): CNF-SAT is NP-complete (A first
NP-complete problem)
⚫Because the technique of reduction relies on having a problem
already known to be NP-complete in order to prove a different
problem NP-complete, we need a “first” NP-complete problem.
⚫The problem we shall use, is the circuit-satisfiability problem, in
which we are given a Boolean combinational circuit composed of
AND, OR, and NOT gates, and we wish to know whether there
exists some set of Boolean inputs to this circuit that causes its
output to be 1.

28. NP-complete problems: A Hierarchal
Figure The structure of NP-completeness proofs. All proofs ultimately follow
by reduction from the NP-completeness of CIRCUIT-SAT.

29. 3-CNF-SAT is NP-complete
⚫Satisfiability of Boolean formulas in 3-conjunctive
normal form is NP-complete.
⚫Proof:-
⚫ The argument used here is to show that SAT ϵ NP
applies equally well here to show that 3-CNF-SAT ϵ
NP.
⚫Next, we need to show that SAT ≤p 3-CNF-SAT.