# Exam 3 Part 1 Flashcards

What is the difference between P and NP? What is a search problem?

NP = class of all search problems

P = class of search problems that are solvable in polynomial time

Search problem: problem that we can efficiently verify solutions

Given an instance I, find a solution S that matches input I

- if a solution exists return S, if not return NO

- we can verify the solution S paired with I in polynomial time

- polynomial of the input size

What does it mean when P = NP or P != NP?

- every search problem lies in NP and P is a subset of NP

P = NP:

- implies if I can check the solution in polynomial time, then I can generate the solution in polynomial time

- all problems in the class of NP are also in P

- hard to prove the problem is P

P != NP:

- means the separation area between P and NP is not NP

- there are some problems that can not be solvable in polynomial time

- the problems that lie in between are NP-complete problems

What are the NP-complete problems? What is the difference between NP-complete and NP-hard?

The problems that lie in between P and NP classes; they are the hardest problems in the class NP

NP-Complete Problems

Definition: A problem is NP-complete if it satisfies two conditions:

It is in NP: This means that given a solution, we can verify its correctness in polynomial time.

It is NP-hard: This means that every problem in NP can be reduced to this problem in polynomial time.

Significance: NP-complete problems are the “hardest” problems in NP in the sense that if we can find a polynomial-time algorithm to solve any NP-complete problem, then we can solve all problems in NP in polynomial time (i.e.,

𝑃

=

𝑁

𝑃

P=NP).

Examples:

The Boolean satisfiability problem (SAT)

The Traveling Salesman Problem (decision version)

The Clique Problem

NP-Hard Problems

Definition: A problem is NP-hard if every problem in NP can be reduced to it in polynomial time.

Significance: NP-hard problems are at least as hard as NP-complete problems, but they do not have to be in NP. This means an NP-hard problem might not have solutions that can be verified in polynomial time.

Examples:

The Halting Problem (which is undecidable)

The Optimization version of the Traveling Salesman Problem (TSP)

Certain scheduling problems

What is the SAT problem? Is is it in the class P and NP?

SAT is in the class NP but unknown if it’s in P

- can verified in O(nm) time

- no algorithm can solve in polynomial time yet

SAT:

input: CNF formula m clauses and n liters

output: satisfying if one exists; NO if none exist

What is the k-colorings problem? Is is it in the class P and NP?

input: undirected graph G(V,E) and integer k > 0

output: graph where each vertex is assigned a color in {1, 2 …k} where each adjacent vertex has different colors assigned; if no such assignment exists return NO

problem is in class NP because it can be verified in O(m) time where m is the edge length (we check all edges)

For k = 2, the problem is in P because there’s a polynomial algorithm to solve it

But not for k >= 3 (unless P = NP)

What is the MST problem? Is is it in the class P and NP?

MST = minimum spanning tree problem

input: undirected weighted graph G(V,E)

output: MST where all vertices are covered where the minimum total amount of edges are used (min weight tree)

In both classes P and NP

NP because we can run BFS/DFS to check if the output is a tree O(m + n) time

P because we can use Kruskal’s or Prim’s algorithm to find the MST O(m log n)

What is the Knapsack problem? Is is it in the class P and NP?

input: n objects with integer weights wi to wn and integer values vi to vn and a given capacity B

output: subset S of objects with total weight <= B and max total value (with or without repetition)

Knapsack is not in both NP or P because we can’t verify in polynomial time of the input size

What is the Knapsack search? Is is it in the class P and NP?

input: n objects with integer weights wi to wn and integer values vi to vn and a given capacity B AND goal g

output: subset S of objects with total weight <= B and total value (with or without repetition) at or greater than goal g ; otherwise NO

Knapsack search is in NP because we verify a solution in overall linear time O(n); not sure about P

The statement “SAT is NP-complete” means…

a) we can verify the solution for SAT in polynomial time

b) if we can solve SAT in polynomial time then we can solve every problem in NP in polynomial time

What are reductions and what is their purpose? How do we do it?

Based on the premise that if we can solve problem B in polynomial time then we can solve problem A in polynomial time using that algorithm

This is reducing from A to B

ex) k-colorings = A to B = SAT

How:

- we use the algorithm solving problem B (SAT in this case) as a black box algorithm

- input to A is transformed as an input to B (this is F(I) )

- output to B S is transformed to the output of A h(S)

- the transformations must be done in polynomial time to prove the reduction works

We need to prove:

S is a solution of F(G, k) <=> (if and only if) h(S) is a solution to (G, k)

T or F; we can reduce SAT to IS

True

What is the 3SAT problem? is is in the class NP and P?

input: CNF formula with n vars and m clauses where each clause has <= 3 variables

output: satisfying assignment if one exists and NO if one does not

3SAT is in the class NP

because we can reduce SAT to 3SAT and verify the solution in polynomial time O(m)

Unlikely to be in P

How is the reduction from 3SAT to SAT completed?

3SAT: A specific case of SAT where each clause has exactly three literals.

Take a CNF input called f

keep C1 and C3 clauses the same

Modify C2 with a new variable y to create new C2’

where you have claim C2 is satisfiable <=> C2’ is satisfiable

The same process can be done for reducing 5SAT to 3SAT where

in general

create k-3 variables y1, y2, …yk-3 and replace C by k-2 clauses

What is the independent set problem? Is it in NP?

input: undirected graph (V,E)

output: independent set S of maximum size

It is not known to be in NP

How can we show that the IS problem is NP-complete?

Given the solution S to the IS problem, we can verify the solution in O(n^2) time by checking all pairs x,y E in S and verify that the pairs do not have an edge in E and check in O(n) time that |S| >= g

Also reduce 3SAT to IS

How to:

- 3SAT CNF formula with xn vars and cn clauses (each clause as 3 or less vars)

- we define a graph G and set g = m
- for each clause ci, create |ci| vertices

In other words, we create a vertex for each literal in each clause

The clauses make up a subgraph where the literals are vertices and the edges connect to other literals in the clause

We then add edges between the complementary literals and their respective literals ex) x and x_bar

We then set the IS size as size m or the number of clauses

Example:

To satisfy the 3SAT formula, select one vertex from each clause without selecting any adjacent vertices

The selected vertices form an independent set of size 2, corresponding to a satisfying assignment for the 3SAT formula