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

Here, P means polynomial Time and NP means non-deterministic. P != NP says, that the NP problem doesn't take polynomial time to get solved. Therefore, it would take exponential time, to solve the problem.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

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