All the NP-hard problems are in NP.
FALSE
Not every decision problem in P has a polynomial time certifier.
If a problem can be reduced to linear programming in polynomial time then that problem is in P.
TRUE
If we can prove that P ≠ NP, then a problem A ∈ P does not belong to NP.
If P = NP, then all NP-Hard problems can be solved in Polynomial time.
If a problem X can be reduced to a known NP-hard problem, then X must be NP-hard.
If SAT ≤P A, then A is NP-hard.
If an undirected graph G=(V,E) has a Hamiltonian Cycle, then any DFS tree in G has a depth |V| - 1.
Linear programming is at least as hard as the Max Flow problem.
If P equals NP, then NP equals NP-complete.
Let X be a decision problem. If we prove that X is in the class NP and give a poly-time reduction from X to Hamiltonian Cycle, we can conclude that X is NP-complete.
To prove that a problem X is NP-complete, it is sufficient to prove that 3SAT is polynomial time reducible to X.
Every problem in NP can be solved in exponential time by a deterministic Turing machine
If Vertex-Cover ∈ P then SAT ∈ P.
If a problem X can be solved using dynamic programming, then X belongs to P
Assuming P!=NP and X is a problem belonging to class NP. There is no polynomial time algorithm for X
If NP = P, then all problems in NP are NP hard
L1 can be reduced to L2 in Polynomial time and L2 is in NP, then L1 is in NP
The simplex method solves Linear Programming in polynomial time.
Integer Programming is in P.
If a linear time algorithm is found for the traveling salesman problem, then every problem in NP can be solved in linear time.
If there exists a polynomial time 5-approximation algorithm for the general traveling salesman problem then 3-SAT can be solved in polynomial time.
Unless P = NP, 3-SAT has no polynomial-time algorithm.
If a decision problem A is polynomial-time reducible to a decision problem B (i.e., A≤p B ), and B is NP-complete, then A must be NP-complete.
If a decision problem B is polynomial-time reducible to a decision problem A (i.e., B≤ pA ), and B is NP-complete, then A must be NP-complete.
TRUE (we think it’s FALSE)
Integer max flow ( where flows and capacities are integers) is polynomial time reducible to linear programming .
It has been proved that NP-complete problems cannot be solved in polynomial time.
NP is a class of problems for which we do not have polynomial time solutions.
(we think its false because P is in NP)
If a problem is in P, it must also be in NP.
If a problem is in NP, it must also be in P.
UNKNOWN
If a problem is NP-complete, it must also be in NP.
If a problem is NP-complete, it must not be in P.
If a problem is not in P, it must be NP-complete.
If a problem is NP-complete, it must also be NP-hard.
If a problem is in NP, it must also be NP-hard.
If we find an efficient algorithm to solve the Vertex Cover problem we have proven that P=NP
If we find an efficient algorithm to solve the Vertex Cover problem with an approximation factor p ≥ 1 (a single constant), then we have proven that P=NP
If we find an efficient algorithm that takes as input an approximation factor p ≥ 1 and solves the Vertex Cover problem with that approximation factor, then we have proven that P=NP
If we find a quadratic time solution to an NP-Complete problem, then all NP-Complete problems can be solved in quadratic time.
Let ODD denote the problem of deciding if a given integer is odd. Then ODD is polynomial time reducible to Vertex Cover.
Independent Set problem has a polynomial run time on certain types of graphs.
Consider two decision problems Q1, Q2 such that Q1 reduces in polynomial time to Hamiltonian Cycle and Hamiltonian Cycle reduces in polynomial time to Q2. Then it is possible for both Q1 and Q2 to be in NP.
The problem of determining whether there exists a cycle in an undirected graph is in NP.
If Integer Linear Programming ≤p A, then A cannot be solved in
polynomial time.
If a problem Y is polynomial time reducible to X, then a problem X is polynomial time reducible to Y.
A linear program with all integer coefficients and constants must have an integer optimum solution.
A linear program can have an infinite number of optimal solutions.
Suppose that a Las Vegas algorithm has expected running time Θ(n) on inputs of size n. Then there may still be an input on which it runs in time Ω(n^2).
Halting Problem is an NP-Hard problem.
Every decision problem in P has a polynomial time certifier.
The linear programming solution to the shortest path problem discussed in class can fail in the presence of negative cost edges.
If P = NP, then all problems in P are NP-complete.
Assuming that we have found a correct optimal solution to an LP problem, if someone claims to have found a different optimal solution, we know that that solution must be incorrect.
Let X and Y be decision problems for which there exist efficient certifiers, and assume P ≠ NP. If X ≤P Y and Y ≤P X, then both X and Y are NP-complete.
Minimum Spanning Tree (MST) ≤P Hamiltonian Path.
The optimization version of the Linear Programming is not in NP.
If P=NP, then some NP-hard problems can be solved in polynomial time.
Even if P≠NP, there is a polynomial-time algorithm for the 0/1 Knapsack problem when all items have the same weight-to-value ratio
If P = NP, then every decision problem whose solution can be verified in polynomial time can itself be solved in polynomial time.
Integer Max Flow (where flows and capacities are integer-valued) is polynomial-time reducible to Linear Programming.
Which of the following problems have been proved to be not solvable in polynomial time? Circle all correct answers
A. Traveling Salesman
B. Integer Linear Programming
C. Subset sum
D. All of the above
E. None of the above
Let X, Y, Z, and W be problems. Suppose Z is polynomial-time reducible to X, and X is NP-complete. Which of the following statements are true? Circle all correct answers.
A. If Vertex Cover is polynomial-time reducible to problem Z, then Z is
NP-Complete.
B. If there exists an efficient certifier for problem Z, then Z is NP-Complete.
C. X is polynomial-time reducible to Independent Set.
D. If X is polynomial-time reducible to Y, then Z is polynomial-time reducible to Y.
E. If Z is polynomial-time reducible to W, then X is polynomial-time reducible to W.
C, D
If a problem X is in NP, then it must be NP-complete if... (Circle all correct answers)
a. It is polynomial-time reducible to 3-SAT.
b. 3-SAT can be reduced to it in polynomial time.
c. It can be reduced to every other problem in NP in polynomial time.
d. Some problem in NP can be reduced to it in polynomial time.
b
Let X be a decision problem. If we prove that X is in the class NP and give a poly-time reduction from X to 3-SAT, we can conclude that X is NP-complete.
If there is a polynomial time algorithm to solve problem A then A is in NP.
There is a polynomial-time solution for the 0/1 Knapsack problem if all items have the same weight but different values.
Any NP-hard problem can be solved in time O(2^poly(n)), where n is the input size and poly(n) is a polynomial.
Any NP problem can be solved in time O(2^poly(n)), where n is the input size and poly(n) is a polynomial.
If 3-SAT ≤p 2-SAT, then P = NP.
Assuming P ≠ NP, there can exist a polynomial-time approximation algorithm for the general Traveling Salesman Problem.
If problem X can be solved using dynamic programming, then X belongs to P.
All instances of linear programming have exactly one optimal solution.
Let Y ≤p X and there exists a 2-approximation for X, then there must exist a 2-approximation for Y.
There is no known polynomial-time algorithm to solve an integer linear programming.
To prove that a problem X is NP-hard, it is sufficient to prove that SAT is polynomial time reducible to X.
Every problem in P can be reduced to 3-SAT in polynomial time.
If there is a polynomial-time algorithm for 2-SAT, then every problem in NP has a polynomial-time algorithm.
If A is in NP, and B is NP-complete, and A ≤p B then A is NP-complete.
Given a problem B, if there exists an NP-complete problem that can be reduced to B in polynomial time, then B is NP-complete.
Every decision problem is in NP-complete.
An NP problem is NP-complete if 3-SAT reduces to it in polynomial time.
All Integer linear programming problems can be solved in polynomial time.
If the linear program is feasible and bounded, then there exists an optimal solution.
If X≤p Y, and X is NP-complete, then Y is NP-hard.
If X≤p Y, and X is NP-complete, then Y is NP-complete.
If X≤p Integer Programming, then X is NP-hard.
FALSE/UNKNOWN
If X≤p Linear Programming, then X is in P.
3-SAT cannot be solved in polynomial time.
If graph G has no cycles, then the independent set problem in G can be solved in polynomial time.
Although the general Travelling Salesman Problem is NP-complete, in class, we presented a 2-approximation algorithm for it that runs in polynomial time.
Let A and B be decision problems. If A is polynomial time reducible to B and B is in NP-Complete, then A is in NP.
The set of all vertices in a graph is a vertex cover.
Suppose there is a 7-approxmiation algorithm for the general Traveling Salesman Problem. Then there exists a polynomial time solution for the 3-SAT problem.
Assume P !=NP. Let A and B be decision problems. If A is in NP-Complete and A ≤ P B, then B is not in P.
There exists a decision problem X such that for all Y in NP, Y is polynomial time reducible to X.
If a problem is not in P, then it must be in NP.
If an NP-complete problem can be solved in linear time, then all NP-complete problems can be solved in linear time.
Consider problem A: given a flow network, find the maximum flow from a node s to a node t. problem A is in NP.
L1 can be reduced to L2 in Polynomial time and L1 is in NP, then L2 is in NP
NP is the class of problems that are not solvable in polynomial time.
If problem A is NP complete, and problem B can be reduced to problem A in quadratic time. Then problem B is also NP complete
If X can be reduced in polynomial time to Y and Z can be reduced in polynomial time to Y, then X can be reduced in polynomial time to Z.
The problem of deciding whether a given flow f of a given flow network G is a maximum flow can be solved in linear time.
If a problem is not solvable in polynomial time, it is in the NP-Complete class.
If any integer programming optimization problem can be converted in polynomial time to an equivalent linear programming problem, then P = NP.
It has been determined that NP Complete problems cannot be solved in polynomial time.
If P = NP, then there are still some NP complete problems that cannot be solved in polynomial time.
When we say that a problem X is NP Complete, then it means that every NP complete problem can be reduced to X.
NP-complete is a class of problems for which we do not have polynomial time solutions.
Last changed2 years ago
