P, NP, and NP-Complete Problems

Dr. Ajay Pratap

Asst. Professor, Dept. of CSE, IIT (BHU), Varanasi, India

[email protected]
 Computational complexity theory
⚫ Fields in
⚫ Theoretical Computer Science
⚫ Analysis ofAlgorithms
⚫ An algorithm solves a computation problem by mathematical steps.
⚫ Acomputational problem (such as an algorithm) is a task solved by a computer.
⚫ Focuses on classifying computational problems according to the resource usage
⚫ Resource usage: amount of resources needed to solve computational problem,
⚫ Resources: such as time and storage.

https://en.wikipedia.org/wiki/Computational_complexity_theory
 Single Source Shortest-Paths Implementation

Easy
Medium
Hard

ROBERT SEDGEWICK | KEVIN WAYNE. Algorithms 4th Edition, https://algs4.cs.princeton.edu/44sp/

 Single Source Shortest-Paths Implementation

ROBERT SEDGEWICK | KEVIN WAYNE. Algorithms 4th Edition, https://algs4.cs.princeton.edu/44sp/

 Deterministic algorithm
⚫ Given a particular input, will always produce the same output, with the underlying
machine always passing through the same sequence of states.
⚫ State machine: a state describes what a machine is doing at a particular instant in time.
⚫ State machines pass in a discrete manner from one state to another.
⚫ Enter the input, initial state or start state.
⚫ Current state determines what will be next state, the set of states is
predetermined.
⚫ Finding a random number is deterministic, it always returns a
random number. Finding odd or even, sorting, finding max, etc.
are deterministic. Most of the algorithms used in practice are
deterministic in nature.

https://en.wikipedia.org/wiki/Deterministic_algorithm
 Non-deterministic algorithm

•The non-deterministic algorithm works on guessing.

•For some input, nondeterministic algorithms may produce different

outcomes every time.

•The nondeterministic algorithm operates in two phases: guessing and

verification.

•After guessing the answer, the algorithm verifies its correctness.

•In the non-deterministic algorithm, each state has a probability of a

different outcome on the same input.
https://codecrucks.com/deterministic-and-non-deterministic-
algorithms/
Non-deterministic algorithm
 P (Polynomial) Time Problems
⚫ Contains all decision problems that can be solved deterministically using a
polynomial time (polynomial amount of computation time).
⚫ A problem is in P-complete, if it is in P
⚫ P is the class of computational problems that are "efficiently solvable" or
"tractable".
⚫ Class P,typically take all the "tractable" problems for a sequential algorithm,
⚫ But, in reality, some problems not known to be solved in polynomial P time.

https://en.wikipedia.org/wiki/P_(complexity)
https://en.wikipedia.org/wiki/P-complete
 P (Polynomial) Time Problems
⚫ Programmable Function (or method) is polynomial-time
⚫ if completes in constant-time or polynomial time,
⚫ then the entire algorithm takes polynomial time.
⚫ Polynomial-time algorithms:
⚫ Minimum SpanningTree: Kruskal's O(E lgV) and Prim’s O(E +V lgV) algorithm
⚫ Shortest PathAlgorithms: Djikstra’s O(ElgV) and Bellman-Ford’s O(EV) algorithm

https://en.wikipedia.org/wiki/P_(complexity)
https://en.wikipedia.org/wiki/P-complete
 NP - Naming convention
⚫ Classification
⚫ Hardest  NP-Hard
⚫ Hard  NP-Complete
⚫ Medium  NP
⚫ Easy P
⚫ Order of N inputs
⚫ O(1) – constant-time
⚫ O(log2(n)) – logarithmic-time
⚫ O(n) – linear-time
⚫ O(n2) – quadratic-time
⚫ O(nk) – polynomial-time
⚫ O(kn) – exponential-time
⚫ O(n!) – factorial-time

https://www.baeldung.com/cs/p-np-np-complete-np-hard
 NP - Naming convention
⚫ NP-hard: Class of problems are at least as hard as the
hardest problems in NP.
⚫ NP-hard problems do not have to be in NP; means NP
hard problem may not even be decidable.
⚫ NP-complete: Class of decision problems which
contains the hardest problems in NP. Each NP-
complete problem has to be in NP.
⚫ NP: Class of computational decision problems for
which any given yes-solution can be verified as a
solution in polynomial time
⚫ NP-easy:At most as hard as NP, but not necessarily in
NP.

https://en.wikipedia.org/wiki/NP-hardness
https://www.baeldung.com/cs/p-np-np-complete-np-hard
 P and NP Problems
⚫ Nondeterministic Polynomial-time
⚫ “Nondeterministic” refers to
⚫ “luckiest possible guesser”
⚫ "Complete" refers to
⚫ “in the same complexity class”
⚫ Pversus NP determine
⚫ whether a problem can be verified in polynomial time
⚫ whether the problem can also be solved in polynomial time.
⚫ If it turned out that P ≠ NP, (widely accepted/believed),
⚫ There are problems in NPthat are harder to compute than to verify:
⚫ NP problems could not be solved in polynomial time, but the answer could be verified in
polynomial time.

https://en.wikipedia.org/wiki/P_versus_NP_problem
 NP Complete
⚫Nondeterministic Polynomial-time
Complete

⚫ Aproblem is NP-complete when:

⚫ a brute-force search algorithm can solve it, and the correctness of each solution can be
verified quickly, and
⚫ the problem can be used to simulate any other problem with similar solvability.
⚫ NP-complete problem can be verified "quickly",
⚫ There is no known way to find a solution quickly.

https://en.wikipedia.org/wiki/NP-completeness
 NP - Hard Problems
⚫ Non-Deterministic Polynomial-time hardness
⚫ At least as hard as the hardest problems in NP
⚫ There might be some polynomial-time algorithms for NP-hard problems but
might not been discovered yet
⚫ NP-hard but not NP-complete
⚫halting problem: "given a program
and its input, will it run forever?"
⚫ traveling salesman problem

https://en.wikipedia.org/wiki/NP-hardness
Reductionism in Algorithms
 Reductionism
⚫ Reductionism is old domain since 16th century
⚫ explains system in terms of parts and their interactions
⚫ Define a domain of possible parts
⚫ Generate inputs over the interaction between parts
⚫ Perform a deterministic computation on the input data
⚫ Aggregate the results
⚫ interprets a complex system as the sum of its parts
General Problems, Input Size and Time Complexity
⚫ Time complexity of algorithms :
⚫ polynomial time algorithm ("efficient algorithm") v.s.
⚫ exponential time algorithm ("inefficient algorithm")
⚫ Find the shortest path in a graph from X toY.(easy) polynomial time.
⚫ Find the longest path in a graph from X toY. (with no cycles) (hard) exponential time
⚫ Is there a simple path from X toY with weight < = M?(easy) polynomial time.
⚫ Is there a simple path from X toY with weight > = M?(hard) exponential time

f(n) 10 30 50

n 0.00001 sec 0.00003 sec 0.00005 sec

n5 0.1 sec 24.3 sec 5.2 mins

2n 0.001 sec 17.9 mins 35.7 yrs

Decision problems
⚫ The solution to the problem is "yes" or "no". Most optimization problems can be
phrased as decision problems (still have the same time complexity).
⚫ Given a decision problem X.
If there is apolynomial time Non-deterministic Turing machine (or computer)
program that solves X, then X belongs to NP
Given a decision problem X.
For every instance I of X,
(a) guess solution S for I, and
(b) check“is S a solution to I?”
If (a) and (b) can be done in polynomial time,then X belongs to NP.
 Polynomial-time Reduction Algorithm
⚫ Input to a particular problem an instance of that problem
⚫ Suppose that we have a procedure that transforms any instance α ofAinto some instance
β of B
⚫ Given an instance α of problemA, use a polynomial-time reduction algorithm
to transform it to an instance β of problem B.
⚫ Run the polynomial-time decision algorithm for B on the instance β
⚫ Use the answer for β as the answer for α.

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (Vol. 3, pp. 624-
642). Cambridge: MIT press.
 Algorithm Reduction
⚫ Def. Problem X reduces to problem Y if you can use an algorithm that solves Y to
help solve X.

ROBERT SEDGEWICK | KEVIN WAYNE. Algorithms 4th Edition, https://algs4.cs.princeton.edu/home/

 Algorithm Reduction

ROBERT SEDGEWICK | KEVIN WAYNE. Algorithms 4th Edition, https://algs4.cs.princeton.edu/home/

Revisiting the concepts
P and NP Problems

MIT Lecture Notes.

NP-Complete
NP-Complete

MIT Lecture Notes.

Algorithm Reduction – Language Transformation
⚫ The class P and DeterministicTuring Machine
• Given a decision problem X, if there is a polynomial time DeterministicTuring Machine
(or computer) program that solves X, then X belong to P
• Informally,there is a polynomial time algorithm to solve the problem
• PolynomialTransformation (" ∝ ")
• L1 ∝ L2 : There is a polynomial time transformation that transforms arbitrary instance
of L1 to some instance of L2.
• If L1 ∝ L2 then L2 is in P implies L1 is in P
(or L1 is not in P implies L2 is not in P)
• If L1 ∝ L2 and L2 ∝ L3 then L1 ∝ L3
NP-Completeness and Cooks Theorem (1971)
P and NP
⚫ Obvious : P ⊆ NP, i.e.A(decision) problem in P does not need “guess solution”.
The correct solution can be computed in polynomial time.
⚫ One of the most important open problem in theoretical compute science :
Is P=NP ?
⚫ Most likely “No”.
⚫ Currently, there are many known (decision) problems in NP,and there is no
solution to show anyone of them in P. NP

P
P, NP, and NP-Complete
⚫ P: (Decision) problems solvable by deterministic algorithms in polynomial time
⚫ NP: (Decision) problems solved by non-deterministic algorithms in polynomial time
⚫ Agroup of (decision) problems, including all of the ones we have discussed (0/1
Knapsack, Partition) have an additional important property:
If any of them can be solved in polynomial time, then they all can!
⚫ These problems are called NP-complete problems.
 Cooks Theorem
⚫ Stephen Cook introduced the notion of NP-Complete Problems.
⚫ This makes the problem “P= NP ?”much more interesting to study.
⚫ Lis NP-Complete if L ∈ NP then for all other L' ∈ NP, L' ∝ L
⚫ Lis NP-Hard if for all other L' ∈ NP, L' ∝ L
⚫ If an NP-complete problem can be solved in polynomial time then all problems in NP can
be solved in polynomial time.
⚫ If a problem in NP cannot be solved in polynomial time then all problems in NP-complete
cannot be solved in polynomial time.
⚫ Note that an NP-complete problem is one of those hardest problems in NP.
⚫ Lemma :
If L1 and L2 belong to NP,
L1 is NP-complete, and L1 ∝ L2
then L2 is NP-complete.
i.e.L1,L2 ∈ NPand for all other L' ∈ NP,L' ∝ L1 and L1 ∝ L2  L' ∝ L2
An Interesting Problem
A Boolean circuit is a circuit of AND, OR, and NOT gates; the CIRCUIT-SAT
problem is to determine if there is an assignment of 0’s and 1’s to a circuit’s
inputs so that the circuit outputs 1.

Inputs:
Logic Gates: 0 1 0
1
NOT 1
1
0 1 Output:

OR 1
0
1 0 1

AND

NP-Completeness
CIRCUIT-SAT is in NP
Non-deterministically choose a set of inputs and the outcome of every gate,
then test each gate’s I/O.

Inputs:
Logic Gates: 0 1 0
1
NOT 1
1
0 1 Output:

OR 1
0
1 0 1

AND

NP-Completeness
NP-Completeness
• A problem (language) L is NP-hard if every
problem in NP can be reduced to L in
polynomial time.
• That is, for each language M in NP, we can take
an input x for M, transform it in polynomial
time to an input x’ for L such that x is in M if
and only if x’ is in L.
• L is NP-complete if it’s in NP and is NP-hard.

NP L
poly-time

NP-Completeness
Cook-Levin Theorem
• CIRCUIT-SAT is NP-complete.
• We already showed it is in NP.
• To prove it is NP-hard, we have to show that every
language in NP can be reduced to it.
• Let M be in NP, and let x be an input for M.
• Let y be a certificate that allows us to verify membership in M in
polynomial time, p(n), by some algorithm D.
• Let S be a circuit of size at most O(p(n)2) that simulates a
computer (details omitted…)

NP M poly-time CIRCUIT-SAT

NP-Completeness
Cook-Levin Proof
We can build a circuit that simulates the verification of x’s membership in M using y.

 Let W be the working storage for D D D

D (including registers, such as
program counter); let D be given
in RAM “machine code.”
< p(n) W W W
 Simulate p(n) steps of D by cells
Output
replicating circuit S for each step S S
0/1
of D. Only input: y. from D

Inputs
 Circuit is satisfiable if and only if y y y

x is accepted by D with some

certificate y n x x x
 Total size is still polynomial:
O(p(n)3).
p(n)
steps

NP-Completeness
3SAT Problem
3SAT Problem…
3SAT Problem…
Thanks
Acknowledgment
• Some of the contents are taken from Dr. Animesh Chaturvedi’s PPT
• Some Contents are taken from Lecture slides by Kevin Wayne
Copyright © 2005 Pearson-Addison Wesley
http://www.cs.princeton.edu/~wayne/kleinberg-tardos
• Some contents are taken from MIT Lecture notes.