CS6515_Exam3 Flashcards
1
Q
LP (Linear Programming) is in P? (T/F)
A
True
2
Q
ILP (Integer Linear Programming) is in P? (T/F)
A
False. It is known to be NP-Complete
3
Q
NP-Complete problems are the hardest problems in what class? What assumption are we making?
A
NP, ie the outer layer of the donut. The assumption we’re making is that P != NP, because in that case all NP-Complete problems are not in P.
In some sense, you can think of NP-Complete problems as the “essence” of the class NP.
4
Q
If a NP-complete problem can be solved in polytime then what does this mean?
A
Then ALL problems in NP can be solved in polytime.
5
Q
Describe the P vs. NP question? What is the historical background of it?
Note: not necessarily important for exam, but useful information to help contextualize P vs. NP.
A
In the 1960-70s scientists began realizing that certain problems had efficient algorithms for solving them, but many other problems did not seem to have such an algorithm. Many of these thorny latter problems had important practical applications, from vehicle routing, network design, etc. Scientists began sorting the problems based on their “hardness”. One thing scientists noticed is that while some of these hard problems did not appear to have polytime algorithms for SOLVING, a given solution could still be checked quickly (ie in polytime). This came to be the class NP.
While most modern researchers think that P != NP, a decisive answer to the question has been incredibly elusive. Doubts arise because sometimes a problem that was thought to be in NP turns out to be in P after someone devises a clever polytime algorithm (eg, finding primes, etc.). THIS IS REALLY YHE CORE QUESTION OF P vs NP: Will we eventually find polytime algorithms for all NP problems, in which case P = NP, or is it just the case that some really hard problems simply don’t have efficient algorithms for solving?
Previous ponderings and correspondence by people like Nash, Godel, and Von Neumann in the 1950s hinted that a problem was afoot. More formal descriptions following. In 1965, Cobham and Edmunds appear to be the first to identify the class of P problems [1][2], ie ones that can be solved in polynomial time. Edmunds published a paper (also in 1965) that provided a template for what would later become the class NP.
The formal theory of NP-Completeness is generally traced back to a few individuals (some working independently) in the early 1970s, namely Stephen Cook, Richard Karp, and Leonid Levin.
Sources:
[1] A. Cobham. The intrinsic computational difficulty of functions. In Y. BarHillel, editor, Proc. 1964 International Congress for Logic Methodology and
Philosophy of Science, pages 24–30, Amsterdam, 1964. North Holland.
[2] J. Edmonds. Paths, trees, and flowers. Canad. J. Math, 17:449–467, 1965.
[3] J. Edmonds. Minimum partition of a matroid into independent subsets.
J. Res. Nat. Bur. Standards Sect. B, 69:67–72, 1965
[4] S. Cook. The complexity of theorem proving procedures. In Proc. 3rd
Ann. ACM Symp. on Theory of Computing, pages 151–158, New York,
1971. Association for Computing Machinery
6
Q
Describe the different between the following problems in terms of computational complexity:
- Multiplication and sorting
- Sudoku
- The game of Chess or Go
A
- These are examples of problems that are in the class P because we have very good fast algorithms for solving them, eg Karatsuba algorithm for multiplication, merge-sort for sorting, etc.
- Sudoku is a classic example of an NP problem (it is also NP-Complete). If I give you a solved Sudoku grid, it’s trivial for you to check if it is correct (or at least trivial for a computer). However, solving a Sudoku grid is hard, and it gets exponentially harder as the grid gets bigger. There is no known algorithm for solving Sudoku puzzles in polytime.
- Chess or Go have massive possible state spaces. Solving a game like this is an example that goes outside NP, to the realm of EXPTIME algorithms. No modern superfast computer (or even one we could reasonable expect to develop in the near future) could solve problems like these, even if we let them run for thousands of years. Even just checking whether a move in chess is the best takes exponential time. We’re basically helpless (from a computational perspective) when it comes to problems like these.
7
Q
What is “Co-NP”
A
Similar to NP, but instead of it being easy to check a correct solution, Co-NP problems are easy to EXCLUDE WRONG ANSWERS
8
Q
Define a “search problem”.
Hint: Specify the form of the problem, and then the requirement that has to be met
A
Form:
Given instance T
- find a solution S for T if one exists
- output ‘NO’ if T has no solutions
Requirement (to be a search problem):
- if given an instance T and solution S, then we can verify that S is a solution to T in polytime (ie polynomial in the size |T|)
9
Q
How do we show that a problem is in NP?
A
We show that there is a polytime algorithm for checking solutions to the problem
10
Q
SAT is in NP? (T/F) Why or why not?
A
True. Because we can check solutions to SAT in polynomial time. There are worst case n variables to check in for each clause, and there are m clauses, so it takes O(nm) time to verify a solution, which is polynomial.
11
Q
The k-Colorings problem is not in NP? (T/F) Why or why not?
A
False, it is in NP because we can verify solutions in polytime. All we have to do is iterate over all the edges in the graph and verify that color(u) != color(v), which takes O(m) time, ie polynomial.
12
Q
MST is in NP? (T/F) Why or why not?
A
True, because we can verify solutions in polytime. The steps we take to prove this are as follows:
- Verify the output is of proper form (ie MST is a search problem): there will always be some tree output by MST; a ‘NO’ instance isn’t possible (although it would still be of the correct form if it was possible). So yes, the output is of the proper form.
- Verify that the output is a tree: simply run DFS/BFS and make sure that no cycles are present
- Run Kruskal’s/Prim’s algorithm to check that tree T has minimum weight, which takes polytime.
13
Q
MST is not in P? (T/F) Why or why not?
A
False, it is in NP because we can verify solutions in polytime. The steps for this proof are:
- Verify the output is of proper form (ie MST is a search problem): there will always be some tree output by MST; a ‘NO’ instance isn’t possible (although it would still be of the correct form if it was possible). So yes, the output is of the proper form.
- We can find a tree of minimum weight in polytime using Kruskal’s or Prim’s algorithm
14
Q
Knapsack is in NP? (T/F) Why or why not?
A
False, because we can’t verify that a solution is a maximum in polynomial time. This is because of the pseudo-polynomial nature of knapsack that we discussed in previous lectures. The budget B is a MAGNITUDE; it isn’t bounded to the input size, it can be an arbitrarily large number.
15
Q
Knapsack is definitely NOT in NP? (T/F) Why or why not?
A
False. This may seem to contradict a previous question about whether knapsack is in NP (which is also False). We aren’t actually violating the “Law of the Excluded Middle” though; the reason the answer here is False is an epistemic problem: we simply don’t know whether knapsack is in NP or not, so we can’t conclusively say one way or the other currently.
16
Q
As best as we know right now, Knapsack is not known to be in NP? (T/F)
A
This is True. This admits the current epistemic gap that exists, namely, that we don’t know for sure if Knapsack is outside NP.
17
Q
How do we modify knapsack so that it falls under NP? What is the consequence of this modification?
A
We get rid of the ‘max’ operation and instead set a goal value that we want to be greater than. The consequence is that this turns the original Knapsack problem into a Search Problem, for which we DO have a polytime algorithm for checking solutions to, which makes this Knapsack Variant fall into the class NP.
18
Q
If any NP-complete problem is solvable in P, then every problem in NP is solvable in P? (T/F)
A
True.
19
Q
“Can we say anything general about when a computational complexity perspective is helpful in philosophy, and when it isn’t?”
Source:
https://arxiv.org/abs/1108.1791
Note: not necessarily important for exam, but useful information to help contextualize P vs. NP.
A
“Extrapolating from the examples in this essay, I would say that computational complexity tends to be helpful when we want to know whether a particular fact does any explanatory work : Sections 3.2, 3.3, 4, 6, and 7 all provided examples of this.”
Source:
“Why Philosophers Should Care About Computational Complexity”. Scott Aaronson. 2011. https://arxiv.org/abs/1108.1791
20
Q
NP stands for “Non-Polynomial”? (T/F)
A
False. It stands for “Non-Deterministic Polynomial Time”.
The explanation in the lectures is that “non-deterministic” as used in this context means something like “allowed to guess at each step”. I like to think of it more as a “branching” of possibilities, and not committing to any single one; all that is required is that there exists >= 1 branch that is an accepting/terminating state.
21
Q
P is a subset of NP? (True/False)
A
True. Note that this is True (although in a sort of degenerate sense) even if it turns out P = NP, because that would just mean that NP consists of the empty set.
22
Q
Assuming P != NP, NP-Complete problems are the hardest problems in the class NP? (T/F)
A
True
23
Q
What does it mean for SAT to be NP-Complete?
A
(a) SAT is in NP
(b) If we can solve SAT in polytime, then we can solve EVERY problem in NP in polytime, ie it would be the case that P = NP.
24
Q
Let A=Colorings problem and B=SAT problem. What does the notation “A –> B” mean?
A
It means that we’re REDUCING A to B; ie if we can solve problem B in polytime, then we can use that algorithm to solve A in polytime.
25
When writing a proof that some problem B is NP-Complete, what are we saying?
We are saying that:
1. B is in NP, ie a polytime algorithm exists for checking solutions
2. For all A (ie KNOWN NP problems) in NP, we can reduce A --\> B, ie if a polytime algorithm existed for us to solve B (the UNKNOWN problem), then we could use that as a subroutine to solve ALL any problem A in NP in polytime
26
3SAT is in NP? (T/F) Why or why not? If it is, how long does it take to verify solutions?
True, because we can verify solutions in polynomial time. Since each clause contains at most 3 literals, this means we can check each clause in O(1) time. There are m clauses, so total runtime is O(m), which is polynomial.
27
For 3SAT, If we have a clause of size k (where k \> 3), how many new auxiliary variables do we create? How many new clauses?
k - 3 new variables, k - 2 new clauses
See NP3\_9 end of video
28
For 3SAT, if we have a lengthy clause of size k (where k \> 3) and want to reduce it to size 3, what auxiliary variables would we have to create? How many clauses would C' contain? Are these variables distinct?
Create k -3 new variables y1, y2, ... y\_(k - 3). We would replace the original clause C with k - 2 clauses. Yes, these auxiliary variables would all be distinct.
29
What is the worst case number of variables we might add when taking a big clause C of length k (where k \> 3) and convert it to an input to 3SAT?
We might have to create n new variables for m clauses, so order O(nm)
30
What is the pattern for converting a big clause into one acceptable for 3SAT?
See slide
31
For the FORWARD proof from C --\> C' for 3SAT, how should we set the variables? (Let a\_i be min i where a\_i is satisfied)
We take an assignment that satisfies C using a\_1, a\_2, ... a\_k
1. Let a\_i = True --\> This satisfies the (i - 1)st clause of C'
2. Set y\_1 = y\_2 = ... y\_(i - 2) = True --\> This satisfies the 1st through (i - 2)st clause
3. Set y\_(i - 1) = y\_i = ... y\_(k - 2) = False --\> This satisfies the remaining clauses
32
For the REVERSE proof from C' --\> C for 3SAT, how should we set the variables? (Let a\_i be min i where a\_i is satisfied)
Take assignment to a\_1, ..., a\_k, and y\_1, ..., y\_(k - 3) satisfying C'
33
When proving the reverse claim for 3SAT, we can set a\_1, a\_2, ..., a\_k = F and still get a valid assignment? (T/F)
False. At least one of the literals has to be satisfied.
See NP2\_12 for details. I still don't quite get this one.
34
The red colored vertices below are an example of what? Why? How do we check for this feature?
They form an _independent set._ Definition: Subset S ⊂ V is an independent set if NO EDGES are contained in S.
To find an independent set, for all edges (x,y) in S, check to see if (x,y) in E, ie:
∀ (x,y) ∈ S, (x, y) ∉ E
35
In a graph G=(V,E), the empty set ∅ forms an independent set? (T/F) Why or why not?
True. Because the definition of an independent set is that for subset S ⊂ V, _no edges_ (x, y) in S are in E.
36
In a graph G=(V, E), a singleton vertex does NOT form an independent set? (T/F) Why or why not?
False, it does form an independent set. This is because the definition of an independent set is that for subset S ⊂ V, no edges (x, y) in S are in E, and obviously a singleton vertex (trivially) satisfies this condition.
37
The max independent set problem is in NP? (T/F)
Trick question. We can't really state whether or not something is definitely in NP or not, because until we have a proof for P=NP (or P != NP), we can't make a definitive assignment. So the correct way to phrase this question would be: "The max independent set problem *_is known to be_* in NP?"
This is a subtle distinction, but Dr. Brito notes in the lectures that HW/Exam problems will be presented in the proper form "known to be", so it's probably a useful thing to remember in case they try to trip us up with a trick question like the one here.
38
The max independent set problem is known to be in NP? (T/F) Why or why not?
False, because we have no way of checking in polytime that a given solution is of *maximum* size. This is similar to the knapsack problem we encountered earlier.
39
How can we convert the max independent set problem into a problem that is in NP?
Similar to what we did for the knapsack problem, we get rid of the *max* operation and replace it with a goal *g*. This turns the optimization problem into a search problem.
40
Say you have a 3SAT clause C = (x\_1 v !x\_3 v x\_2). How would you represent this as a graph G = (V, E). What is the max size of an independent set you could have for this graph?
We simply draw edges between x\_1, !x\_3, and x\_2 to form a triangle. These are the *_clause edges_*. The max size IS would be a single vertex; if you added a second vertex, then one of the edges is guaranteed to be in E, violating the definition of IS.
This question is pretty pivotal for understanding reductions from 3SAT --\> Independent Sets. See NP3\_7 for more details on this.
41
In the context of 3SAT and graph algorithms, what is the difference between "clause edges" and "variable edges"?
Clause Edges: edges between variables inside a clause. For example, if you had the clause C = (x\_1, !x\_3, x\_2), we simply draw edges between x\_1, !x\_3, and x\_2 to form a triangle.
Variable Edges: edges between all x\_i and !x\_i; this prevents logical inconsistencies where we try to set, eg x\_1 = T and x\_1 = F, which obviously can’t happen
42
What does it mean to be "NP-Hard"? What is one consequence of this? How can we show that an NP-Hard problem is in NP-Complete?
It means the problem is _at least_ as hard as everything in NP. One thing that means is we can reduce any problem in NP to a problem in NP-Hard, eg prove that Max-IS is in NP-Hard by applying the reduction from IS --\> Max-IS.
To show that an NP-Hard problem is also in NP-Complete, we have to prove that we can check solutions for the problem in polytime. Remember that NP + NP-Hard = NP-Complete; equivalently, all problems in NP are in NP-Hard, but not all NP-Hard problems are in NP.
43
NP-Complete problems are the hardest problems in the set, and NP-Hard problems are *_at least_* as hard as everything in the set? (T/F)
True
44
The clique problem is only defined for directed graphs? (T/F)
False, it is only defined for undirected graphs.
45
What is the definition of a "clique" in a graph?
A clique is a fully connected subgraph, ie a subset of vertices is a clique if given subset S ⊂ V, ∀ (x, y) ∈ S, (x, y) ∈ E
46
Say you have 5 vertices on a graph. How many different pairs of vertices are there?
5 choose 2, so using formula in image below we have 5! / (2! \* (5 - 2)!) = 10
47
What are the red vertices in the graph below an example of?
Definition: a clique is a fully connected subgraph, ie a subset of vertices is a clique if given subset S ⊂ V, ∀ (x, y) ∈ S, (x, y) ∈ E
48
Why couldn't the vertex circled in blue in the graph below belong to the clique of red vertices?
Because it it is missing the edge shown in the image below that would make it fully connected with all of the red vertices.
49
What is the definition of a "Vertex Cover"?
A subset of vertices S ⊂ V is a vertex cover if it “covers every edge”, ie ∀ (x,y) ∈ E, either x ∈ S, y ∈ S, or (x, y) ∈ S
50
What is the graph in the image below an example of? Why?
Definition of Vertex Cover: S ⊂ V is a vertex cover if it “covers every edge”, ie ∀ (x,y) ∈ E, either x ∈ S, y ∈ S, or (x, y) ∈ S
51
What is the key idea behind the proof (the one shown in the lectures) for the Clique problem being NP-Complete?
That a clique is the opposite of an Independent Set
52
What is the key idea behind the proof (the one shown in the lectures) for the Vertex Cover problem being NP-Complete?
Key Idea of Proof: S is a VC ⇔ complement S’ is an IS
53
What are the inputs to a Max-Flow problem using LP?
Inputs: directed graph G=(V, E) with capacities c\_e \> 0 for e in E
LP: m variables: f\_e for every e in E
Objective function: maximizing flow out of source vertex or maximizing flow in to sink vertex
Constraints:
Capacity constraints: ∀ e ∈ E, 0 \<= f\_e \<= c\_e
Conservation of flow: ∀ v ∈ V - {s,t}, sum\_in(f\_v) = sum\_out(f\_v) [slight abuse of notation here, but this is general idea]
54
Say you have the LP shown in the following image. From a geometric standpoint, what do the x\_i constraints represent?
They form a half-plane.
55
The graph below shows a geometric representation of the constraints in a linear program. What does the brown shaded region represent?
The feasible region, ie the area where solutions exist that satisfy the constraints.
56
When using LP, the optimum solution will always lie on integer values? (T/F) Why or why not? What is an important consequence of this?
False. The feasible region represents a continuous function, ie it may very well find that the optimum is a non-integer value. The important consequence is that while LP is in P, Integer Linear Programming (ILP) is known to be NP-Complete.
57
In LP, the optimum will always lie at a vertex (ie corner) of the feasible region? (T/F) Why or why not?
True
58
In LP, the only optimal solutions are guaranteed to lie on a vertex of the feasible region? (T/F) Why or why not?
False. While it is true that a vertex at the maximum of the feasible region is guaranteed to be at least as good as any other optimal solution, it may not be the only one. Think about the case of a horizontal line that goes across the feasible region and through that vertex Any point along that line is also a solution. See the image below.
59
In geometric terms, what is one important consequence of the linear constraints we impose on an LP?
These linear constraints form _half-planes_. When we stack up all these linear constraints, they intersect to form a _convex shape_. This means that the feasible region is convex, so the optimum solution is guaranteed to fall somewhere on the convex hull of the shape. This is what enables algorithms like Simplex to be able to solve LPs in linear time.
60
What is the size of the constraint matrix A for an LP? What is the size of b (ie the inequality values)?
Matrix A is of size (M x N), where N is the number of variables x1, x2, ..., x\_N, and M is the number of constraints.
The size of b is (M x 1)
61
What is the standard form for an LP?
See image below.
62
How is an LP represented from a linear algebra approach? (Give sizes of matrices, objective function, constraints, etc.)
Variables: X --\> (N x 1)
Objective function C --\> (N x 1)
Constraint Matrix A --\> (M x N)
Constraints B --\> (M x 1)
Objective function: max[C.T @ X], where @ denotes matrix multiplication
Such that: A @ X \<= B
Non-negativity constrains: X \>= 0
63
For the LP below, what should the values for the objective function matrix C be? Constraint matrix A? Constraints b?
C = [[1], [6], [10]]
A = [[1, 0, 0], [0, 1, 0], [1, 3, 2], [0, 1, 3]]
b = [[300], [200], [1000], [500]]
64
Say you have the following objective function for an LP:
min [C.T @ X]
How would you convert this objective function into standard form?
Note: .T represents the matrix transpose operation and @ denotes matrix multiplication.
We turn it into a maximization problem by multiplying by -1 and then maximizing, ie:
min [C.T @ X] \<==\> max [-1 \* C.T @ X]
65
Say you have an LP with a constraint like:
a1\*x1 + a2\*x2 \>= b
How would you write this in standard form?
In standard form, we should always have the constraints such that they are \<= b. We can do this by simply multiplying both sides of the inequality by -1, ie:
a1\*x1 + a2\*x2 \>= b ⇐⇒ -a1\*x1 + -a2\*x2 \<= -b
66
Say you have an LP that has an equality constraint like:
a1\*x1 + a2\*x2 = b
How would we represent this in standard form?
We simply use two inequalities, \<= b and \>= b, the latter of which we convert to standard form by multiplying both sides by -1:
a1\*x1 + a2\*x2 = b ⇐⇒ a1\*x1 + a2\*x2 \<= b AND -a1\*x1 + -a2\*x2 \<= -b
67
Say you have an LP with a strict inequality constraint like:
a1\*x1 + a2\*x2 \< b
How would you represent this in standard form?
Trick question. Strict inequalities aren't valid to use for an LP. This is because the feasible region must form a _closed set_. If we use a strict inequality, then it becomes an open set, and the problem is ill-defined.
68
Say you're creating an LP and you want x to be able to take on an unconstrained range of values, ie you want x to be able to take on positive or negative values. How would you write this in standard form?
We would need to drop the non-negativity constraint and then add in two new variables, x\_plus and x\_minus. We would then add in two new constraints:
x\_plus \>= 0 and x\_minus \>= 0, (or in standard form: -x\_plus \<= 0 and -x\_minus \<= 0)
Then we would replace x with the following equation:
x = x\_plus - x\_minus
69
For the LP below, what should the values for the objective function matrix C be? Constraint matrix A? Constraints b?
Note that the objective function is a **minimization**, so we need to multiply by -1 to convert to a **maximization** problem for standard form:
C = [[-3], [2.5], [-1]]
Constraint matrix (3x3 matrix):
A = [[0, -1, -1], # negate to reverse the inequality
[0.5, 7, -2], # convert = to \<=
[-0.5, -7, 2]] # convert = to \>=, then negate to reverse
Constraint values (3x1 column vector):
b = [[-300], # negate to reverse the inequality
[4], # convert = to \<=
[-4]] # convert = to \>=, then negate to reverse
70
In an LP, say you have n number of variables. From a geometric perspective, how many dimensions will there be? Say you have m number of constraints; how many total constraints will you have?
n variables --\> n dimensions
total # constraints = (n + m), because there are m constraints, plus we have n non-negativity constraints for each of the variables.
71
From a geometric perspective, what does the feasible region in an LP represent?
**feasible region = intersection of (n + m) halfspaces = convex polyhedron in n-dimensional space**
The (n + m) halfspaces represent the m constraints + the non-negativity constraints for the n variables
72
The feasible region of an LP is formed by the intersection of (n + m) halfspaces, which from a geometric view form a convex polyhedron in n-dimensional space. What do the vertices of this n-dimensional polyhedron represent? What is the upper bound on the number of vertices there will be?
The vertices represent points that satisfy:
* n constrains with =
* m constrains with \<=
The upper bound on the # of vertices will be \<= (n + m) choose n
73
Say you have an LP with 3 variables and 2 constraints. What is the upper bound on how many vertices there could be on the convex polydedron that forms the feasible region? What is the upper bound on the number of neighors that any given vertex might have?
Let n=3 and m=2. The **upper bound on the number of vertices will be \<= (n + m) choose n**, ie 5 choose 3 = 5! / (3! (5 - 3)!) = **10**
**The upper bound on the number of neighors will be \<= nm,** any given vertex will have at most n times m neighbors, so 3 \* 2 --\> **\<= 6 neighbors**
See LP1\_17 for more details on why these calcs are what they are.
74
What are two polynomial time LP algorithms? Which one is more commonly used in real-world applications currently?
1. Ellipsoid algorithms (typically more of theoretical interest)
2. Interior point methods (used quite extensively in real-world applications)
75
The output of the Simplex algorithm on an LP is guaranteed to be optimal, assuming an optimum exists? (T/F)
True. (See LP1\_18)
76
The Simplex algorithm for LPs runs in polynomial time? (T/F)
False, it is worst-case exponential time. In spite of that, it is very widely used on a routine basis to solve huge LPs.
77
The Simplex algorithm starts off with x=0. Why?
Because the 0 vector at least satisfies the n non-negativity constraints. If it also satisfies the m inequality constraints, then we're at least now on the feasible region, which gives us a foundation to try to build a better solution from.
78
Say you run the Simplex algorith on some large LP with n variables and m constraints. The algorithm as usual starts off by trying a solution with x1, x2, ... x\_n = 0; however, the algorithm immediately halts after trying this solution. What has happened? What can we conclude about the LP?
Starting with x=0 ensures that, at a minimum, all the n non-negativity constraints on x have been satisfied. If the algorithm immediately halted though, **that means that it must not have been able to satisfy any of the other m constraints, so the feasible region is empty. This means that the solution to this LP is infeasible.**
79
What is the key idea of the simplex algorithm?
It "walks" along the vertices (ie corners) of the convex n-dimensional polyhedron that is formed by the constraint half-planes (ie the outer edges of the feasible region).
80
The optimum of an LP is achieved at a vertex of the feasible region EXCEPT in what two cases?
1. Infeasible: feasible region is empty
2. Unbounded: optimal is arbitrarily large
81
The situation shown in the LP below is an example of what situation? Why is this the case?
An INFEASIBLE SOLUTION. This is because the **feasible region is empty.**
82
The LP shown below is an example of an *infeasible solution* because of constraints imposed by the objective function? (T/F) Why or why not?
False. This is indeed an LP with an infeasible solution. However, the reason it is infeasible has nothing to do with the objective function. **The feasible region is solely defined by the constraints.**
83
The **feasibility/infeasibility** of an LP is solely a function of the constraints and **is not** impacted by the objective function, while the **bounded/unboundednes**s **is** a function of the objective function as well as the constraints? (T/F)
True. See LP2\_3-4 for details.
Whether LP is feasible/infeasible depends solely on the constraints (ie does NOT depend on objective function)
Whether LP is bounded/unbounded depends on the constraints AND ALSO DEPENDS on objective function
84
The LP shown below is an example of what situation? Why?
It is an UNBOUNDED LP. Take a look at the colored heatmap in the graph which shows values for 'c' (ie c = x + y, the thing we are maximizing). Notice that the top of the graph is actually truncated; in fact the follows for c go off to infinity. This is the definition of an unbounded LP: when the thing we are maximizing grows arbitrarily large.
85
The LP shown below is unbounded? (T/F) Why or why not?
False, it is in fact bounded. While the level sets (colored gradient does indeed go off to infinity as x, y --\> +inf, notice that we're *maximizing*, so the constraints AND the objective function actually DO bound the problem in the direction we care about, leading to the optimum value shown by the circled point in the image below.)
86
Say we have the LP shown below. How can we check if there is a **feasible** solution to the LP?
Hint: Remember that feasibility/infeasibility is *solely* a function of the constraints
We introduce a new variable *z* that is unconstrained, ie -inf \<= z \<= +inf. Notice that if we manipulate the constraint equation slightly by adding in this new variable, we can ensure that the constraint equation is ALWAYS satisfied by simply setting z = -inf, or some arbitrarily large negative number. On the other hand, notice that if there is a solution where z \>= 0, then z isn't even necessary because we could just satisfy the inequality using Ax, hence we could drop z. This means a simple way to check for feasibility is to just setup a new LP and maximize z (which will always have a feasible point since we can just set z = -inf). If the solution to that LP yields a value for z that is non-negative (ie z \>= 0), then we know the LP is feasible; if z turns out to be negative, then we know the LP is infeasible.
The other nice thing about this approach is that if a solution turns out to be feasible, as a bonus we can then use that solution as a starting point and hand things off to the simplex algorithm (or some other LP solver).
87
Say you have an LP with 3 variables and 4 constraints; how many variables and constraints will be in the dual LP?
4 variables (which correspond to the constraints in the primal LP), 3 constraints (which correspond to the variables in the objective function of the primal LP).
88
The dual(dual) = primal LP? (T/F)
True
89
When writing the dual LP from the primal LP, we should include the non-negativity constraints as the variables in the dual LP? (T/F)
False, we don't include these non-negativity constraints as far as the variables in the objective function in the dual LP are concerned, we only consider the actual constraint equations.
See LP3\_8-9 if this is confusing.
90
Say you have an LP with 4 variables and 3 constraints, plus another 4 non-negativity constraints for each of the variables. How many variables and constraints will be in the dual LP?
There will be 3 variables (we don't include the non-negativity constraints in the variables) and 4 constraints in the dual.
91
To be in standard form, how should inequalities for an LP be written in terms of \_\_\_\_\_\_\_\_\_\_?
Minimization, ie \<=
92
To be in standard form, the objective function for an LP should be written in terms of \_\_\_\_\_\_\_\_\_\_\_?
Maximization. Note that if we're given an LP that is a minimization problem, all we have to do is multiply the objective function by -1 and then maximize that new objective function.
93
For an LP, any feasible y for the dual LP ⇒ b.T @ y is an upper bound on the primal objective function? (T/F)
Note: .T here represents the matrix transpose operation, and @ represents matrix multiplication.
True. (See LP3\_10)
94
For an LP, any feasible x for the primal LP ⇒ c.T @ x is a lower bound on the dual LP objective function? (T/F)
Note: .T here represents the matrix transpose operation, and @ represents matrix multiplication.
True.
95
If the primal LP is unbounded, then the dual LP is infeasible? (T/F) Why or why not?
True. This is one of the corellaries of the Weak Duality Theorem. See the slide below. If the primal LP objective function (ie the left side of the inequality) is unbounded (ie infinite), then you could never come up with a value that would be greater for the dual LP objective function, **hence if the primal LP is unbounded, the dual LP is infeasible. And also by extension, if the dual is unbounded, then the primal is infeasible.**
96
If the dual LP is unbounded, then the primal LP is infeasible? (T/F) Why or why not?
True. This is one of the corellaries of the Weak Duality Theorem. See the slide below. If the dual LP objective function (ie the right side of the inequality) is unbounded (ie negative infinity, remember that the dual LP is *minimizing* its objective function), then you could never come up with a value that would be smaller for the primal LP objective function, **hence if the dual LP is unbounded, the primal LP is infeasible. And also by extension, if the primal is unbounded, then the dual is infeasible.**
97
If the dual LP is infeasible, then the primal LP is guaranteed to be unbounded? (T/F) Why or why not?
False. It *might* be that the primal LP is unbounded, but just knowing that the dual LP is infeasible doesn't give us that information. It IS the case that if we knew that the primal LP is unbounded, then the dual is guaranteed to be infeasible, but this corollary of the weak duality theorem only holds in the forward direction.
Note: This is probably a very good thing to remember for the exam!
98
Say you're given some LP, and an oracle tells you that she knows that the dual of this LP is infeasible. What can you conclude about the primal LP?
The primal is guaranteed to be either **unbounded** **or** **infeasible**
99
Say you're given some LP, and an oracle tells you that she knows that the dual of this LP is infeasible, but she's not sure about the state of the primal LP? Describe how you could figure out the status of the primal LP.
If the dual LP is infeasible, then we know for certain that the primal LP is either: 1. Unbounded, or 2. Infeasible. So all we have to do is check to see if the primal LP is feasible\*\*. If it is feasible, then we know for certain that the primal LP is unbounded.
\*\*Note: Remember how we do this: creating new LP with z variable in objective function, maximizing that objective function and checking that z \>= 0
100
For an LP, if we find feasible x for the primal and feasible y for the dual where c.T @ x = b.T @ y, then x & y are optimal? (T/F)
True.
101
What makes the Weak Duality Theorem "weak"?
By weak, we simply mean we're not making any claims on the primal or dual LPs. Specifically, we're not claiming that they are definitely not infeasible or definitely not unbounded. (If we do make those claims, we end up with the Strong Duality Theorem, for which we get different guarantees.)
102
If the Primal LP is feasible and bounded ⇐⇒ dual LP is feasible and bounded? (T/F)
True. (This is the Strong Duality Theorem)
103
If the Primal LP has optimal x\* ⇐⇒ Dual has optimal y\*? (T/F)
True. (This is the Strong Duality Theorem)
104
You have a large LP you want to solve, and you hand it over to an oracle to give you a solution. Being a slightly impish oracle, she decides not to tell you the solution, or even if one exists, but only provides the mysterious clue that she found that: "The optimal value for the primal LP is equal to the optimal value for the dual LP? What can you conclude at the very least based on her statement?
The LP is feasible and bounded (both primal and dual, which is somewhat redundant to say since knowing that one is feasible and bounded implies the other does as well). We also know that whatever value she found, since the primal and dual are equal, it is guaranteed to be the optimum value for the LP.
105
The Strong Duality Theorem can also be used to prove the Max-Flow = Min ST-Cut Theorem? (T/F)
True. (See LP3\_15)
106
Say you have an input for a SAT problem where every clause is of length exactly three. What is the probability that any given clause is NOT satisfied.
2^-k = 2^-3 = 1/8
107
Say you have an input for a SAT problem where every clause is of length exactly three. What is the probability that any given clause is IS satisfied.
1 - 2^-k = 1 - 2^-3 = 1 - 1/8 = 7/8
108
Say you have an E3-SAT problem, and you discover a 9/10-Approximation algorithm to solve it. What has just happened? Why?
You have just proven that P=NP. This is because for E3-SAT the best correctness you can achieve without the problem becoming NP hard is 1 - 2^-k, ie 1 - 1/8=7/8. Since 9/10 \> 7.8, your algorithm is better than the expected approximation, so if you've found this algorithm then you've just proven P=NP.
109
For E3-SAT, we can achieve the best possible satisfying solution with 7/8 probably by just using a random assignment algorithm? (T/F)
True. (See LP4\_8)
110
Integer Linear Programming (ILP) is known to be NP-Hard? (T/F)
True.
111
Any feasible point for an ILP is also a feasible point for an LP approximation of the ILP? (T/F) Why or why not? What is one important consequence of this?
True. Think about it. The ILP is like superimposing a "grid" on the n-dimensional space. The LP however considers continuous values, but obviously the set of points on the grid in the ILP is also contained in that continuous space in the LP. Important consequence is that the LP approximation is guaranteed to be at least as good as the ILP solution.
TL;DR The LP contains more points to consider, of which the points in the ILP are guaranteed to be a subset of.
112
The LP approximation solution will always be equal to the ILP solution? (T/F)
False. The LP approximation is guaranteed to be _at least as good as the ILP solution._ (ie the LP solution is an upper bound on the ILP solution)
113
In the context of using ILP/LPs to solve sat problems, what do the variables y\_i and z\_j represent in the LP? Give a brief description of how we use them in the LP.
The y\_i variables represent the variables in the original SAT formula. The z\_j variables represent the clauses.The idea is that there is only one way of assigning variables so as to NOT satisfy a clause. Under that assignment, we set z\_j=0 to denote that the clause is not satisfy the constraint. Then we take the sum of the z\_j variables and the constraint that sum(Y) + sum(1 - !Y) \>= z\_j. Since z\_j is constrained to only take on 0 or 1 values, this inequality gives us the behavior that we want, namely, that z\_j is positive if any of the y variables are satisfied.
114
What is the basic idea about using an LP to approximate a solution to an ILP problem?
The LP is guaranteed to give us a feasible solution if a feasible solution exists in the original ILP, and it does this in polynomial time (because LP is in P, but ILP is not!). The LP approximation is also guaranteed to be at least as good as the optimal ILP solution. So then if we round the solution provided by the LP to integer values (we do this rounding probabilistically based on the values the LP found for y\_hat\_i\*), we can use that as a starting point for the ILP.
115
For an LP used to find an approximate solution for a SAT problem, let W = # of satisfied clauses. In expectation, what can we expect W to be?
E[W] \>= (1 - 1/e) \* m\*, where m\* is the optimal (ie max) # of clauses that could possibly be satisfied.
116
What is often one good way of approaching an NP-Hard problem?
Try to reduce it to ILP., then relax it to an LP and solve it (using some polytime solver or simplex). Then we apply randomized rounding to the LP solution, and use that as a feasible starting point solution for the ILP.
(See LP4\_22)
117
In the context of Max-SAT on Ek-SAT, for k\>=3 the simple algorithm performs better (in terms of being -- in expectation -- closer to the optimum) than the LP-based algorithm? (T/F)
True. This is the crossover point. For SAT problems with small clauses (ie k \< 3), the LP-based solution is better.
118
In the context of Max-SAT on Ek-SAT, in terms of k (ie the size of the clause) how close can we get to the optimum number of clauses m\* using the 'Simple' algorithm vs with the LP-based algorithm?
See the formulas in the image below.
119
In the context of Max-SAT on Ek-SAT problems, how do we guarantee a 3/4-approximation algorithm? Is this guaranteed to achieve this 3/4-approximation even on clauses of varying sizes?
We combine the simple random algorithm with the LP-based algorithm. First we run the simple algo, then we run the LP-based algo. Take the better of the two as the answer. In expectation then, we get E[max{m\_simple, m\_lp}] \>= 3/4 m\*, where m\* is the optimum number of clauses satisfied.
Yes, it will achieve the 3/4-approximation even with varying length clauses.
120
The subset sum problem is known to be in P? (T/F) Why or why not?
False. Because it is only pseudopolynomial in the input size because the target sum t isn't bound to the input size in any way. This is the same situation that we run into with the Knapsack problem. (See Quiz in NP4\_3)
121
We can check solutions to the SubsetSum problem in polynomial time? (T/F) Why or why not?
True. We can easily check a solution S by simply checking that for all i in S, sum(a\_i) = t. This takes time O(n log t). It is log t because we can represent t in binary, so that each doubling of the magnitude of t only increases it’s representation size by one.
122
What is the difference between NP-Complete problems and Undecidable problems?
NP-Complete problems are **_computationally difficult_**; they are the hardest problems that exist in the class NP. If P != NP, then there will **never** be a polytime algorithm that works on **every input**.
Undecidable problems are problems that are **computationally impossible;** no algorithm exists that will solve the problem on every input, even given unlimited time and space.
123
What are the inputs/outputs for the SAT algorithm?
124
What are the inputs/outputs for the 3SAT algorithm?
125
What are the inputs/outputs for the Clique algorithm?
126
What are the inputs/outputs for the IndependentSet problem?
127
What are the inputs/outputs for the VertexCover problem?
128
What are the inputs/outputs for the TSPSearch problem?
129
What are the inputs/outputs for the SubsetSum problem?
130
What are the inputs/outputs for the KnapsackSearch problem?
131
What is a good hierarchy to consider for performing NP reductions?
In general: for graph problems try to use a graph problem. For logic problems, use SAT or 3SAT, for Knapsack use SubsetSum, etc. The slide below shows the hierarchy.
Note: Don't necessarily need to memorize this slide, but having a general idea of how to breakdown the NP problems like will probably be helpful on the exam.
132
Proving that something is NP-Hard requires proof that it is in NP? (T/F)
False. Remember that NP + NP-Hard = NP-Complete. An NP-Hard problem can be in NP, but it can also be outside NP.
Source: Joves' Notes
133
Not all NP problems are in P? (T/F) Why or why not?
Correct answer is "maybe" (but probably not, based on current understanding). If all NP problems are in P, then P = NP, which has yet to be proven (or disproven)
134
All NP problems have the potential to be in P? (T/F) Why or why not?
Correct answer is "maybe". It depends on if P = NP. If it P != NP, then there will definitely be problems in NP for which polytime solutions cannot exist.
135
We can always prove whether an NP problem is definitely not in P? (T/F) Why or why not?
False. This hinges on whether we ever know if P = NP or not. Since we don't know, all we can say about an NP problem is that it is *not known to be in P.*
136
The hardest problems in NP are also NP-Hard? (T/F)
True. This is just the definition of an NP-hard problem: a problem that is at least as hard as a hardest problem in NP.
137
NP-Hard problems are always in NP? (T/F)
False. They can be in NP (in which case they would be NP-Complete since NP + NP-Hard = NP-Complete), but they can also be outside NP entirely.
138
You have some magic algorithm that solves every imaginable halting problem you through at it, and even in polynomial time! But there's this one halting problem that you keep throwing at it, but the algorithm always says "sorry, even given an infinite amount of time and space, I can't solve this problem". What class of problems would this be?
It would be in the "undecidable" class. The key to undecidability and an algorithm is that it must work on EVERY input. So if there's even one that's undecidable, then nothing has fundamentally changed. The class of problems you are dealing with is still undecidable.
139
Why do we consider approximation in the context of NP-Hard problems?
Because in the absence of proof that P=NP, we're unlikely to find efficient algorithms for NP-Hard problems. Approximating the problem can allow us to get a "good enough" answer quickly.
140
What approach do we use for tackling NP-Hard problems using LP/ILP?
Take NP-Hard Problem:
1. Reduce to ILP
2. Relax to LP
3. Solve the LP (use simplex or some polytime algorithm)
4. Round the solution to integer values (randomized or other techniques)
141
Max-SAT is NP-Hard? (T/F)
True
142
C is a vertex cover if and only if V - C is a(n) _________________ in G.
Independent Set
143
C is a(n) ______________ if and only if V - C is a(n) independent set in G.
vertex cover
144
What is the "Strong Duality Theorem"? What is an equivalent way of stating it?
Primal LP is feasible and bounded i.f.f. dual LP is feasible and bounded
An equivalent statement would be:
Primal has optimal x\* i.f.f. dual has optimal y\*
145
If you have a max-flow problem and you write the primal form of the LP for it, what will the solution give you?
The size of the max flow
146
If you have a max-flow problem and you write the dual form of the LP for it, what will the solution give you?
The capacity of the min st-cut
147
Say someone gives you an LP (written in primal form) that describes a max-flow problem. They tell you they want to know the size of the max-flow. What are two different ways you could solve this?
First way: just solve the primal LP as-is; the solution to the primary LP representing a max-flow problem is already = size of max flow.
Alternatively, write the dual form of the LP and solve that, which will give you the capacity of the min st-cut. By the max-flow == min st-cut theorem, we would then just claim that the solution to the dual LP that gives the min st-cut is equal to the size of the max-flow.
148
At a high-level, what does the dual of an LP represent?
It represents the upper bound on the primal objective function
149
Say someone tells you that they have a black-box algorithm for some problem, and the algorithm returned 'NO' for some instance of the problem. The person claims that the problem is "Undecidable". Are they correct? Why or why not?
No, they are incorrect. Undecidable problems are those that we truly can't determine a solution one way or another. An answer of 'NO' is a definitive answer.
See OH11 for a good discussion on this from Joves'.
150
One good strategy for NP-Complete reductions is to solve A to create an instance of B? (T/F)
FALSE FALSE FALSE!!!. NEVER DO THIS!.
151
What are the four ways we can show correctness for an NP-Complete problem?
Note: First one is most important to remember (and can derive all the others from it)
1. "If A has a solution then B has a solution" AND "If B has a solution then A has a solution" (This is the standard, "Both Positive" implications)
2. "If A has a solution then B has a solution" AND "If A has NO solution then B has NO solution" (This swaps the second positive implication for its contrapositive)
3. "If B has NO solution then A has NO solution" AND "If B has a solution then A has a solution" (This swaps the first positive implication for its contrapositive)
4. "If B has NO solution then A has NO solution" AND "If A has NO solution then B has NO solution" (This swaps both positive implications for their contrapositive). Note: OH11 Joves' mentions NOT to use this one! It's legal, but VERY DIFFICULT.
152
For NP-Completeness proofs, we don't need to state O(1) runtimes? (T/F)
False. We DO need to mention ALL runtimes. Joves' lists this as one of the most common mistakes people made this semester. And ALL runtimes need to be in O() notation
153
It is possible for both the primal and the dual LP to be infeasible? (T/F)
True. (See Aja's comments at 1hr 6min mark in OH11)
154
What is the runtime to count the number of variables (ie to find what n is) in a CNF?
O(nm).
155
In the primal and the dual are both feasible, then they are both bounded? (T/F)
True. (There is a good discussion of this at 00:04:42 in OH10)
156
If the primal and the dual are both feasible, then it is still possible that one of them is unbounded? (T/F)
False. They must both be bounded in that case. This is a tricky one to remember, because say for instance that the dual was infeasible. In that case the primal might be either: (1) infeasible or (2) unbounded. If it were to be shown that the primal was feasible, then in that case it would have to be that the primal is unbounded. But in the case where BOTH are feaasible, as in the question here, it must be the case that both are bounded.
157
If the primal LP is unbounded and feasible, then the dual LP is infeasible?
True. (See OH10 00:05:00)
158
If the dual LP is feasible, then the primal LP is either:
1. _______________ OR
2. \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_
1. Bounded and Feasible
2. Infeasible
(See OH10 00:05:00)
159
When using the Z method to check the feasibility of an LP, you should always add a non-negativity constraint for the Z variable? (T/F) Why or why not?
FALSE! The whole idea behind the Z method is that it turns any LP into one that is GUARANTEED to be feasible because we can just set Z to -inf (or some arbitrarily large negative number like that) to guarantee we satisfy the Ax + Z \<= b constraints.
(See OH11 00:35:55 for details.)
160
If you're using the Z method to check for the feasibility of an LP, there will ALWAYS be a feasible solution when using this strategy? (T/F) Why or why not?
True. Because we can always set Z to be arbitrarily small in order to guarantee we meet the Ax + Z \<= b constraints.
161
What is one good way of checking which side of the line should be shaded in when graphing an inequality?
Just plug in a point (ideally an easy one, like the zero vector) and plug it in to the inequality and see if it still yields a true statement. If so, then that's the side we shade in. (Aja has a really good discussion of this in the Week #9 OH)
162
It is possible to have an LP that is both infeasible AND unbounded? (T/F) Why or why not?
False. It only logically makes sense to talk about an LP being potentially unbounded if it is feasible. If there are no feasible solutions, then it's not possible for the solution set to become unbounded (because the solution set is just the empty set)
163
What process should we use to find vertices in an LP with 3+ variables?
**_1. Convert_** LP to standard form (if not already)
**_2. Pick_** n inequalities to make into “=” (where n is # of vars)
Say you have an LP with three vars. Could use the three non-negativity constraints to convert, so you’d have x1=0, x2=0, x3=0
Don’t have to use the zero vector though - think about what inequalities might be smartest to pick
**_3. Check_** the other constraints for if it’s feasible.
If it is feasible, then go to the next step.
Otherwise, pick a different point and repeat
**_4. Compute_** the objective function at that point
**_5. Swap two neighbors_** and compute objective function to check for a better solution
Swapping neighbors just means switching out two inequalities
Make sure to check that each new solution does in fact satisfy all the constraints!
**_6. Repeat Steps 4-5_** until you find a vertex with a larger max than all its neighbors; at that point, you have your solution.
164
If the primal LP is unbounded then the dual LP is \_\_\_\_\_\_\_\_\_?
Infeasible
165
If the Dual LP is Unbounded then the Primal LP is \_\_\_\_\_\_\_\_\_\_\_?
Infeasible
166
Any **_feasible_** value of the DUAL LP is an upper bound on the original PRIMAL LP? (T/F)
True.
167
The primal LPs objective function will ALWAYS evaluate \<= the dual LPs obective function? (T/F)
True
168
If the primal LP is unbounded (and feasible), then the dual LP is infeasible? (T/F)
True. Remember that the primal being unbounded only makes sense in the case that it is also feasible. You're never going to have a situation where the primal is both infeasible and unbounded.
169
If the dual LP is unbounded (and feasible), then the primal LP is also feasible? (T/F) Why or why not?
False. In this case the primal is infeasible because the dual is unbounded
170
What is the strong duality theorem?
"The primal LP is feasible and bounded if and only if the dual LP is feasible and bounded"
171
What should our process be for solving LPs?
Hint: From Aja's OH9 on LPs
Steps for Solving LPs
**1. Check if Primal LP is feasible** (eg plugin simple values, use Z method, etc)
**2. If Primal LP is feasible, then check whether the primal LP is bounded**
2.1 Do this by checking whether dual LP is feasible
An infeasible dual LP means that the primal LP is either feasible+unbounded OR infeasible
If the dual LP is feasible, at this point we know this means that the primal LP is bounded and feasible.
**3. Solve the primal LP**
