Exam 3 Flashcards
SAT(C)
Input: C is a CNF with any number of variables (n variables) and clauses (m clauses)
Output: Assignment of each varable such that the CNF is true
Sat -> IS, using graph with triangles for the clauses. Each clause vertex connects to it’s negation. IS runs, it will pick a IS which is also the soution to SAT 3.
3SAT(C)
Input C is a cnf whose clauses have at most 3 literals
output: Assignment of each variable such that the expression is true
(a V b V c V d V e) => (a V b V y1) ^ (~y1 V c V y2) ^ (~y2 V d V y3) ^ (!y3 V e)
Also, this can be restricted futher to say limit a variable only appearing twice:
replace subsequence instances and add statements linking them.
x => x1, x2, x3 => (~x1 V x2) ^(~x2 V x3) ^ (~xk V x1)
Clique(G, k)
Input: G is an undirected graph, unweighte graph. K is the size of the clique.
Output: Clique with K verticies. A Clique is a fully connected graph, so each vertex is connected to every other vertex.
IndependentSet(G, k)
Input: G is an undireted, unweighted graph. K is the size of the independent set.
Output: An independent set with K vertices. An independent set is a set of verticies such that there are no edges between the verticies.
(A set, of size b or less, in which no two elements are adjacent. )
As Max it is np hard, because you can’t verify that it is the max.
As a search problem, where you give it a threshold of at least b verticies then it is np complete.
Vertex Cover(G, b)
Input: G is an undirected, unweighted graph. B is the budget of the vertex cover.
Find the endpoint such that every vertex include one endpoint for every edge. vertex count b or less
Output: b vertices which are a vertex cover of F
SubsetSum(A, t)
Input: A is an array of integers. T is an integer
Ouptut: An array of integers, which is a subset from A, that sums up to t.
KnapsackSearch(W, V, B, g)
Input: W is an array of weights. V is the array of values. B is the capacity of the knapsack. G is the goal.
Output: Array of items of value at least g with weight less than or equal to B.
What are the 5 steps to prove problem B is NP-Complete
1) Demonstrage that problem B is in the class of NP problems by showing a solution check that takes polynomial time.
2) Show that an exisitng np complete problem A can be converted to B in polynomial time.
3) Show how a solution for B can be converted to a solution for A (in polynomial time)
4) Show that if you have a solution to B, you also have a solution to A.
5) Show that if there is no solution for B, then no solution exists for A.
What is NP Hard?
All problems B such that: for every problem A in NP, there is a reduction A to B
Within NP Hard, there is a subset that if you can verify those problems in polynomial time, then they are part of NP Complete.
What qualifies as NP
A set of problems that we can verify the solution to the problem in polynomial time.
What qualifies as P
The subset of NP problems that we can both verify and solve in polynomial time
If the primal is infeasible, what does this imply about the dual.
The dual is infeasible and unbounded.
If the primal is feasible and bounded, what does this imply about the dual.
The dual is feasible and bounded
If the primal is unbounded, what does this imply about the dual.
The dual is infeasible.
If the dual is infeasible, what does this imply about the primal.
The primal is infeasible and unbounded.
Properties of Duality
