retagged by
1,673 views

2 Answers

2 votes
2 votes
Since language L is NP-Complete all NP and NP Complete problems can be reduced to L in polynomial time.

And it is given that complement of language L is in NP. Hence complement of all NP problems is in NP.
1 votes
1 votes

If there is an NP-complete language L whose complement is in NP, then the complement of any language in NP is in NP.

Answer:

Related questions

2 votes
2 votes
2 answers
1
admin asked Mar 31, 2020
1,873 views
Which of the following regular expressions denotes a language comprising all possible strings over the alphabet $\{a,b\}$?$a^*b^*$$(a\mid b)^*$$(ab)^+$$(a\mid b^*)$
2 votes
2 votes
4 answers
3
admin asked Mar 31, 2020
905 views
If $L_1$ and $L_2$ are context free language and $R$ a regular set, then which one of the languages below is not necessarily a context free language?$L_1L_2$$L_1\cap L_2$...
4 votes
4 votes
4 answers
4