Scribd
Upload
816 views15 pages

NP Hard and NP Complete

This document discusses NP-hard and NP-complete problems and complexity classes such as P, NP, NP-complete, and NP-hard. It defines NP as problems that can be verified in polynomial time and NP-hard as problems that are as hard as any problem in NP. NP-complete problems are defined as problems that are in NP and are NP-hard - meaning they can be verified in polynomial time and every other NP problem can be reduced to them in polynomial time. Common NP-complete problems like the traveling salesman problem are provided as examples.

Uploaded by

veningston
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
816 views15 pages

NP Hard and NP Complete

This document discusses NP-hard and NP-complete problems and complexity classes such as P, NP, NP-complete, and NP-hard. It defines NP as problems that can be verified in polynomial time and NP-hard as problems that are as hard as any problem in NP. NP-complete problems are defined as problems that are in NP and are NP-hard - meaning they can be verified in polynomial time and every other NP problem can be reduced to them in polynomial time. Common NP-complete problems like the traveling salesman problem are provided as examples.

Uploaded by

veningston
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 15

Design and Analysis of Algorithms (18CSE107)

NP Hard & NP Complete


NP Completeness

Veningston. K
Computer Science and Engineering
Unit V - Outline

• Network flow problem


– Ford Fulkerson Algorithm for Maximum Flow Problem

• NP–Hard and NP–Complete Problems


– Terminologies
– Examples

– Complexity Class - P, NP, NP-Complete, NP-Hard


– Is P=NP?
– Reducibility
•Design and Analysis of Algorithms
•2
(18CSE107)
P vs. NP

• NP
– Set of all problems which could be verified in polynomial
time.
– This set even contains P algorithms
• We will try to find out one problem to which every
problem in NP could be reduced to that problem in
polynomial time.
Reducibility

• Let us say, we have some problem A,

• We found out this problem is such a way that, every


problem in NP could be converted to this problem A
in polynomial time.

A
Why do we find such a problem?

• Why it is important to find such a problem A?


• This make the following things easy,
– To prove that every problem in NP can be solved in
polynomial time, provided if we could find a polynomial
time algorithm to A.
– If every problem in NP can be solved in polynomial time,
we can prove P == NP
• If we have found out many such problems, the name
given to such a problem is NP-Hard.
What is NP-Hard problem?

• If every problem in NP can be polynomial time


reducible to a problem A, then A is called NP-Hard.

• What does it mean?


– The problem A is as hard as any problem in NP. Why?

– If we can solve A, it means that we are able to solve every


problem in NP.
Scenario

• Arm Wrestling
What are the implications?

• What is the significance of such a problem?


– If A is such a problem, then we could make the following
simple statements.
• If A (which is NP-Hard problem) could be solved in
polynomial time, then what does it mean? Every
problem in NP is P (i.e. polynomial time solvable)

• If a problem in NP-Hard is solved in Polynomial


time, then we can say that P == NP

NOTE: Till now, no one is ever able to find out a polynomial time
solution to any NP-Hard problems
NP-Complete

• If the problem A is also NP, which means solution to


A can also be verified in polynomial time, then A is
NP as well as NP-Hard.

• The problem A happens to be present in this set


itself.
Scenario

• Arm Wrestling

Same class?
NP-Complete

• If we can find a problem A in the same NP set, in


such a way that every other problem could be
converted to this problem A,
– It is NP-Hard, because it is as hard as any problem in NP.

– As well as, it is NP

– Therefore, it is NP-Complete
NP-Complete - Formal definition

• A problem is said to be NP-Complete, if it is NP and


NP-Hard.
– If a problem is in NP, as well as every problem in NP can
be converted to it, then we call such a problem as NP-
Complete.
P vs. NP vs. NP-Hard vs. NP-Complete

• What is the relationship between P, NP, NP-Hard &


NP-Complete?
– We do not have any concrete proof of saying that P == NP
or P != NP
P vs. NP vs. NP-Hard vs. NP-Complete

• Well known NP-


Complete problems:
– Clique
– Vertex cover
– Hamiltonian Cycle
– TSP
– Subset sum
– 0/1 Knapsack
– Boolean
Satisfiability problem
(SAT)
– Longest path
P vs. NP vs. NP-Hard vs. NP-Complete

• Summary:
– NP-Hard or NP-Complete is solved in polynomial
time, then P == NP

– NP problem or NP-Complete is proven to be not


solvable in polynomial time, then P != NP.

You might also like