Register

NIELIT 2016 MAR Scientist B - Section C: 19

• retagged by
1,755 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.
User Avatar
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.

User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

2.7k
views
2 answers
2 votes
admin asked Mar 31, 2020
2,668 views
NIELIT 2016 MAR Scientist B - Section C: 24
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^*)$
User Avatar
1.3k
views
2 answers
1 votes
admin asked Mar 31, 2020
1,330 views
NIELIT 2016 MAR Scientist B - Section C: 25
Regarding power of recognition of language, which of the following statements is false?Non deterministic finite-state automata are equivalent to deterministic finite-stat...
User Avatar
988
views
4 answers
2 votes
admin asked Mar 31, 2020
988 views
NIELIT 2016 MAR Scientist B - Section C: 26
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$...
User Avatar
913
views
4 answers
4 votes
admin asked Mar 31, 2020
913 views
NIELIT 2016 MAR Scientist B - Section C: 27
If $L$ be a language recognizable by a finite automaton, then language from $\{L\} = \{w$ such that $w$ is a prefix of $v$ where $v\in L\}$, is aregular language.context-...
User Avatar
Link Copied!