Register

NIELIT 2016 MAR Scientist B - Section C: 19

• retagged by
2,192 views

2 Answers

2 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 1 vote

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

Voting & Accepting an answer helps improve the community
Answer:
← Previous · NIELIT 2016 MAR Scie...Next → · NIELIT 2016 MAR Scie...
← Previous in category · NIELIT 2016 MAR Scie...Next in category → · NIELIT 2017 DEC Scie...
Position:
Show:

Related questions

2 2 votes
2 2 answers
3.5k
3.5k views
admin asked Mar 31, 2020
3,460 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^*)$
1 1 vote
2 2 answers
2.2k
2.2k views
admin asked Mar 31, 2020
2,184 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...
2 2 votes
4 4 answers
1.6k
1.6k views
admin asked Mar 31, 2020
1,645 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$...
4 4 votes
4 4 answers
1.6k
1.6k views
admin asked Mar 31, 2020
1,568 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-...