Scribd
Upload
23 views30 pages

Lecture 2

The document discusses NP and NP-Complete problems, focusing on the 3SAT problem and its reductions to independent set and vertex cover. It outlines the relationships between decision, search, and optimization problems, emphasizing their polynomial-time reducibility. Additionally, it acknowledges sources of content used in the presentation.

Uploaded by

prasuk0129
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
23 views30 pages

Lecture 2

The document discusses NP and NP-Complete problems, focusing on the 3SAT problem and its reductions to independent set and vertex cover. It outlines the relationships between decision, search, and optimization problems, emphasizing their polynomial-time reducibility. Additionally, it acknowledges sources of content used in the presentation.

Uploaded by

prasuk0129
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/ 30

NP, and NP-Complete Problems…

Dr. Ajay Pratap


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

[email protected]
3SAT Problem
3SAT Problem…
3SAT Problem…
Problems according to computational requirements
Packing and covering problems
Independent set
Vertex cover
Question
Vertex cover and independent set reduce to one another
Vertex cover and independent set reduce to one another
Vertex cover and independent set reduce to one another
Set Cover
Set Cover
Question
Vertex cover reduces to set cover
Vertex cover reduces to set cover
Vertex cover reduces to set cover
Recap on SAT Problem
Satisfiability
Satisfiability is hard
3-satisfiability reduces to independent set
3-satisfiability reduces to independent set
3-satisfiability reduces to independent set
Recap…..
Review
Decision, search, and optimization problems

 Decision problem. Does there exist a vertex cover of size ≤k ?


 Search problem. Find a vertex cover of size ≤k.
 Optimization problem. Find a vertex cover of minimum size.

 All three problems poly-time reduce to one another.


Acknowledgment
Thank you!
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.

You might also like