Warning: The hard deadline has passed. You can attempt it, but you will not get credit for it. You are welcome to try it as a learning exercise.
To specify an array or sequence of values in an answer, separate the values inthe sequence by whitespace. For example, if the question asks for the firstten powers of two (starting at 1), then the following answer is acceptable: 1 2 4 8 16 32 64 128 256 512If you wish to discuss a particular question and answer in the forums, pleasepost the entire question and answer, including the seed (which can be used bythe course staff to uniquely identify the question) and the explanation (whichcontains the correct answer).
(seed = 468996)Which of the following problems are known to be in P? Check all that apply.
SHORTEST-ST-PATH: given a graph and two vertices s and t, find the shortest simple path between s to t.
FACTOR: given an N-bit integer x, find a factor other than 1 and x.
BOUNDED-HALTING: given a constant-size program, does it halt in at most K steps?
BIPARTITE: given a graph, partition the vertices into two pieces A and B such that every edge connects a vertex in A with a vertex in B?
MAXIMUM-SPANNING-TREE: given a graph with positive edge weights, find a maximum spanning tree.
(seed = 563993)Suppose that problem X is in NP, Y is NP-complete, and P != NP. Which of the following can you infer? Check all that apply.
Y polynomial-time reduces to X.
X is not in P.
X is not NP-complete.
X polynomial-time reduces to Y.
If Y polynomial-time reduces to X, then X is NP-complete.
(seed = 835383)What is the definition of the complexity class NP?
All problems solvable in polynomial space.
All search problems that are not solvable in polynomial time.
All problems for which there exists a polynomial-time algorithm to check whether a proposed solution is a solution.
All problems solvable in exponential time.
All problems not solvable in exponential time.