retagged by
585 views
0 votes
0 votes

retagged by

2 Answers

1 votes
1 votes
L is polynomial time verifiable and exponantial time solvable. So it must be NP but not P.Ifthere exist a problem which is in NP but not in P i.e. P!=NP.

what is option (3). NP ---> P i.e. all NP can be converted into P in polynomial amount of time whichmeans NP = P but it is already false.

Obviously L should not be NPC.
0 votes
0 votes
  • L is in NP (means polynomial time verification algorithm exists) and is proved that L is solved in $\Sigma(2^{n})$ hence $P < NP$
  • If it were said L is NP hard problem and we can prove that lower bound of time complexity of L is $\Omega(2^{n})$ then also we could not say anything about P and NP relation
  • If it were said L is NP complete problem and  we can prove that lower bound of time complexity of L is $\Omega(2^{n})$ then $P \neq NP$ and $P \cap NP = \phi $
edited by

Related questions

0 votes
0 votes
1 answer
1
0 votes
0 votes
0 answers
2
0 votes
0 votes
1 answer
3
2 votes
2 votes
1 answer
4