recategorized by
9,332 views
16 votes
16 votes

Let $\pi_A$ be a problem that belongs to the class NP. Then which one of the following is TRUE?

  1. There is no polynomial time algorithm for $\pi_A$.

  2. If $\pi_A$ can be solved deterministically in polynomial time, then P = NP.

  3. If $\pi_A$ is NP-hard, then it is NP-complete.

  4. $\pi_A$ may be undecidable.

recategorized by

1 Answer

Best answer
22 votes
22 votes

A problem which is in P, is also in NP- so, A is false. If problem can be solved deterministically in Polynomial time, then also we can't comment anything about P=NP, we just put this problem in P. So, B also false. C is TRUE because that is the definition of NP-complete.

D is false because all NP problems are not only decidable but decidable in polynomial time using a non-deterministic Turing machine.

edited by
Answer:

Related questions

46 votes
46 votes
7 answers
1
Kathleen asked Sep 22, 2014
20,950 views
The above DFA accepts the set of all strings over $\{0,1\}$ that begin either with $0$ or $1$.end with $0$.end with $00$.contain the substring $00$.
42 votes
42 votes
6 answers
3
Kathleen asked Sep 22, 2014
12,633 views
Given the following state table of an FSM with two states $A$ and $B$,one input and one output.$$\small\begin{array}{|c|c|c|c|c|c|}\hline \textbf{PRESENT} & \textbf{PRESE...