Exam 3 Flashcards
What do we mean when we say a problem is intractable?
It’s unlikely to be solved efficiently
Define a search problem.
A problem where we can efficiently verify solutions
What is class P?
Class of search problems that are SOLVABLE in polynomial time AND can be verified in polynomial time; P is a subset of NP and stands for polynomial time
What is class NP?
Class of ALL search problems, saying that is can verify solutions in polynomial time; it stands for nondeterministic polynomial time, meaning problems that can be solved in polynomial time on a machine that is allowed to guess at each step
What is an NP-complete problem?
If P != NP then ALL NP-complete problems are not in P; if an NP-complete problem CAN be solved in polynomial time, then ALL problems in NP can be solved in polynomial time
What is the input to the 3SAT problem?
Boolean formula, f, in CNF with n variables & m clauses where each clause has <= 3 literals; the output is a satisfying assignment if one exists & NO otherwise
What is an independent set?
A subset, S of V (vertices) is an independent set if no edges are contained in S (none of the vertices are adjacent)
What is a clique?
A fully connected subgraph; all pairs of vertices in a subset are connected by an edge
What is a vertex cover?
S of V is a vertex cover if it covers every edge
What class are linear programming (LP) problems in?
They are in the class of P because they can be solved and verified in polynomial time
What class are integer linear programming (ILP) problems in?
They are in the class of NP-complete
Where is an optimal point in a feasible region?
An optimal point is at a vertex (a corner); an optimal point may be non-integer (fractional); the feasible region is convex, meaning that an optimal point is at a vertex rather than a line extending out of the feasible region
What polynomial-time algorithms can be used on linear programming problems?
Ellipsoid algorithms and interior point methods; the ellipsoid method is theoretical based
What algorithm is widely used on huge linear programming problems and works very fast?
Simplex algorithm; in the worst-case it runs in exponential time but is still widely used because it will always return an optimal point
In duality, the dual LP is derived from what?
The primal LP
What does the weak duality theorem state?
The primal LP objective function is c^Tx and the dual LP objective function is b^Ty; the feasible x for primal LP and feasible y for dual LP
What is the matching values corollary of the weak duality theorem?
It states that if we find a feasible x AND feasible y where c^Tx = b^Ty then we can conclude that x AND y are both optimal; x maximizes the primal LP and y minimizes the dual LP
What is the unbounded LP corollary of the weak duality theorem?
It states that if the primal LP is unbounded then the dual LP must be infeasible, and vice-versa, if the dual is unbounded, then the primal must be infeasible; this does not mean an equivalence, one or the other is either unbounded OR infeasible
How do you check for unbounded LP?
Check if there is a feasible point for the primal LP, if so then check to see if the dual LP is infeasible; if it is, then we know that the primal LP is unbounded
What does the strong duality theorem state?
If the primal LP is feasible AND bounded, then the dual LP is also feasible AND bounded; if the primal LP has an optimal point, then the dual LP also has an optimal point
How does the Max-SAT problem differ from the regular SAT problem?
The input is the same; a Boolean formula f in CNF with n variables & m clauses; BUT the output is now an assignment maximizing the # of satisfied clauses; it is now NP-hard instead of in the class NP since we can’t verify that the number of clauses is now maximum, but it’s NP-hard because we know it’s at least as hard as the SAT problem is
What is the approximation that Ek-SAT is satisfied for a max-Ek-SAT problem?
(1 - 2^-k) is the approximation
