# Exam 3 Part 1 Flashcards

1
Q

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

A

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

2
Q

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

A
• 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

3
Q

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

A

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

4
Q

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

A

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

5
Q

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

A

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)

6
Q

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

A

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)

7
Q

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

A

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

8
Q

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

A

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

9
Q

The statement “SAT is NP-complete” means…

A

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

10
Q

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

A

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)

11
Q

T or F; we can reduce SAT to IS

A

True

12
Q

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

A

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

13
Q

How is the reduction from 3SAT to SAT completed?

A

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

14
Q

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

A

input: undirected graph (V,E)

output: independent set S of maximum size

It is not known to be in NP

15
Q

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

A

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

16
Q

What is the clique problem and is it part of the NP group?

A

Input: G(V,E) undirected and goal g size

Output: subset of V where S is the clique of size g or larger if one exists; else NO

The clique problem is not known to be in the NP class but we can show that it’s NP-complete via reduction

17
Q

How can we reduce IS to clique problem?

A

Key idea: Clique is the opposite of an IS and vice versa

Thus we can prove that:

S is a clique in G <=> S is a IS in Gbar

where Gbar is a graph where the edges in G are flipped (remove edges between vertices that have them and add edges between verties that don’t have them)

Proving clique problem is NP-complete:
We can verify that the subset has edges between all pairs in S in O(n^2) time and check in O(n) time the size of S

Input transformation:
construct Gbar from G and input to IS problem

output transformation:
Take soluton S and return for clique problem for graph G

18
Q

What is the Vertex Cover problem and is it in NP?

A

input: G(V,E) and budget b

output: subset S of vertices that cover all edges in the graph of size <= b ; else NO

In the class NP because it can be validate in polynomial time

19
Q

What problem has a direct relationship with the vertex cover problem where a reduction could happen? How?

A

Independent Set can be reduced with vertex cover

First) Vertex cover is NP-complete:
Output S can be verified and checked every x,y pairing is in E where x and y are in S (take O(n+m) runtime)
Also takes O(n) time to verify <= b

S is a vertex cover in G <=> Sbar is an independent set

No Sbar edges in S and thus Sbar is an IS

20
Q

What is the subset problem and is it in P and NP?

A

input: positive integers a1..an and t

output: subset S of {1..n} where sum ai = t if such as subset exists
No otherwise

Not in P

In NP -> verified O(n log t) time

21
Q

What problem can be reduced with the subset problem? What are the steps to do so?

(card incomplete)

A

3SAT

Steps:

Input to subset: 2n + 2m + 1 numbers

v1, v1bar, v2, v2bar, … vn, vnbar, s1, s1bar, …sm, smbar and t

all are <= n+m digits long & base 10

t ~ 10^n+m

vi corresponds to xi
vibar corresponds to xibar
Thus
vi is in S <=> xi is True
vibar is in S <=> xibar is False

digit n+j corresponds to clause Cj

if xi in Cj then put 1 in digit n+j for vi

if xibar in Cj then put 1 in digit n+j for vibar

put 3 in digit n+j of t

Put O in digit n+j of other numbers

subset-sum has a solution <=> 3SAT f is satsifiable

Take the solution S of the subset-sum and then:
- for digit n+j where 1<= j <= n

to get sum of 3 in digit n+j

need to include >= 1 literal of

22
Q

Is there an algorithm that takes polynomial time on every input for an NP problem?

A

NO

23
Q

What are undecidable problems?

A

Problems that are computationally impossible; there is no algorithm that solves a problem on every input regardless of the run time

24
Q

What is the halting problem?

A

This is an example of a undecidable problem

input: a program (any language) with input I

output: True if P(I) ever terminates; False otherwise (has an infinite loop)

ex) while x % 2 == 1 {
x += 6
}
let x = 5

it never stops so then
Halting (P,5) = False

25
Q

How do we prove that the halting problem is undecidable?

A

Derive algorithm Terminator(P,I)

We can construct a program Q and input J where when we run terminator(Q, J) is incorrect (terminator is a black box)

26
Q

What is the HP paradox?

A

If Harmful(Harmful) terminates, then Harmful(Harmful) never terminates

If Harmful(Harmful) never terminates, then Harmful(Harmful) terminates

Thus program terminator program exists is impossible