If P NP then all problems in NP require exponential time. True False If problem

Question

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

Explanation / Answer

True

False

This is true though not yet proven that there is any problem in NP which can be solved in P time.

True

False

Polynomial time algo for A will be

True

False

This is false a polynomial time reduction of A to B might not mean P time reduction of B to A

True

False

True, as Max clieque problem is P reducible to Circuit Satisfiability

(Answering first 4 as per policy)

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.