Exam 3

Question 1

What do we mean when we say a problem is intractable?

Answer 1

It’s unlikely to be solved efficiently

Question 2

Define a search problem.

Answer 2

A problem where we can efficiently verify solutions

Question 3

What is class P?

Answer 3

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

Question 4

What is class NP?

Answer 4

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

Question 5

What is an NP-complete problem?

Answer 5

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

Question 6

What is the input to the 3SAT problem?

Answer 6

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

Question 7

What is an independent set?

Answer 7

A subset, S of V (vertices) is an independent set if no edges are contained in S (none of the vertices are adjacent)

Question 8

What is a clique?

Answer 8

A fully connected subgraph; all pairs of vertices in a subset are connected by an edge

Question 9

What is a vertex cover?

Answer 9

S of V is a vertex cover if it covers every edge

Question 10

What class are linear programming (LP) problems in?

Answer 10

They are in the class of P because they can be solved and verified in polynomial time

Question 11

What class are integer linear programming (ILP) problems in?

Answer 11

They are in the class of NP-complete

Question 12

Where is an optimal point in a feasible region?

Answer 12

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

Question 13

What polynomial-time algorithms can be used on linear programming problems?

Answer 13

Ellipsoid algorithms and interior point methods; the ellipsoid method is theoretical based

Question 14

What algorithm is widely used on huge linear programming problems and works very fast?

Answer 14

Simplex algorithm; in the worst-case it runs in exponential time but is still widely used because it will always return an optimal point

Question 15

In duality, the dual LP is derived from what?

Answer 15

The primal LP

Question 16

What does the weak duality theorem state?

Answer 16

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

Question 17

What is the matching values corollary of the weak duality theorem?

Answer 17

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

Question 18

What is the unbounded LP corollary of the weak duality theorem?

Answer 18

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

Question 19

How do you check for unbounded LP?

Answer 19

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

Question 20

What does the strong duality theorem state?

Answer 20

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

Question 21

How does the Max-SAT problem differ from the regular SAT problem?

Answer 21

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

Question 22

What is the approximation that Ek-SAT is satisfied for a max-Ek-SAT problem?

Answer 22

(1 - 2^-k) is the approximation