Let S be an NP-complete problem. Q and R are other two problems not known to be NP. Q is polynomial time reducible to S and S is polynomial time reducible to R. Which of the following statements is true?

Let S be an NP-complete problem. Q and R are other two problems not kn

1.	Let S be an NP-complete problem. Q and R are other two problems not known to be NP. Q is polynomial time reducible to S and S is polynomial time reducible to R. Which of the following statements is true?
A.	R is NP-complete
B.	R is NP-hard
C.	Q is NP-complete
D.	Q is NP-hard
Answer» C. Q is NP-complete

Discussion

No Comment Found

Related MCQs

For any two languages L1 and L2 such that L1 is context-free and L2 is recursively enumerable but not recursive, which of the following is/are necessarily true?I. L̅1 (complement of L1) is recursiveII. L̅2 (complement of L2) is recursiveIII. L̅1 is context-freeIV. L̅1 ∪ L2 is recursively enumerable
Consider the transition diagram of a PDA given below with input alphabet ∑ = {a, b} and stack alphabet Γ = {X, Z}. Z is the initial stack symbol. Let L denote the language accepted by the PDA.Which one of the following is TRUE?
Consider the NPDA 〈Q = {q0, q1, q2}, Σ = {0,1}, Γ = {0,1,⊥}, δ, q0, ⊥, F = {q2}〉, where (as per usual convention) Q is set of states, Σ is the input alphabet, Γ is the stack alphabet, δ is the state transition function, q0 is the initial state, ⊥ is the initial stack symbol, and F is the set of accepting states. The state transition is as follows:Which one of the following sequences must follow the string 101100 so that the overall string is accepted by the automaton?
If G is a grammar with productionsS → SaS | aSb | bSa | SS | ∈Where S is the start variable. Then which one of the following strings in not generated by G?
A student wrote two context-free grammars G1 and G2 for generating a single C-like array declaration. The dimension of the array is at least one. For example,int a[10] [3] ;The grammars use D as the start symbol, and use six terminal symbols int; id[ ] numGrammar G1Grammar G2D → int L;D → int L;L → id[EL → idEE → num]E → E[num]E → num][EE → [num] Which of the grammars correctly generate the declaration mentioned above?
Consider the following languages.L1 = {wxyx | w, x, y ϵ (0 + 1)+}L2 = {xy | x, y ϵ (a + b)*, |x| = |y|, x ≠ y}Which one of the following is TRUE?
Let L1 be a regular language and L2 be a context-free language. Which of the following languages is/are context-free?
A grammar that produces more than one left most derivation or right most derivation for the same sentence is known is _____.
Consider the following grammar.S → ABA → aA → BaBB → bbAWhich of the following statement is FALSE?
Consider the following languages :L1 = {am bn | m ≠ n}L2 = {am bn | m = 2n + 1}L3 = {am bn | m ≠ 2n}Which one of the following statement is correct ?

Let S be an NP-complete problem. Q and R are other two problems not known to be NP. Q is polynomial time reducible to S and S is polynomial time reducible to R. Which of the following statements is true?

Discussion

No Comment Found

Related MCQs

Reply to Comment