If P NP then all problems in NP require exponential time.

True

False

If problem A reduces in polynomial time to B and B is in P then A is in P.

True

False

If problem A reduces in polynomial time to B and B is NP-complete then A is NP-complete.

True

False

If the Maximum Clique problem can be solved in polynomial time, then Circuit Satisfiability can be solved in polynomial time.

True

False

If there is a polynomial-time algorithm that determines whether a given set of linear equations and inequalities has a solution in which all the variables have integer values then P=NP.

True

False

Two Boolean circuits are called equivalent if they produce the same output for every assignment of values to the inputs. The Circuit-Equivalence problem is the problem of determining whether two given circuits are equivalent. Claim: If the Circuit-Equivalence problem can be solved in polynomial time then P=NP.

True

False