BPSC TRE – TOC | Full-Length Test

BPSC TRE – TOC | Full-Length Test – 1

Questions 66-70 of 80

0% completed (0/80 answered)

Question 66

MCQ · Single Correct 1 mark

What does it mean for a problem B to be NP-Hard?

A Every problem A in NP can be polynomial-time reduced to B (A \le _p B), but B itself need not be in NP B B is in P and NP C B is undecidable D More than one of the above E None of the above

Question 67

MCQ · Single Correct 1 mark

What does it mean for a problem B to be NP-Complete?

A B is in P AND B is in NP B B is non-deterministic and undecidable C B is in NP AND B is NP-Hard D More than one of the above E None of the above

Question 68

MCQ · Single Correct 1 mark

Which of the following problems is DECIDABLE?

A Halting problem for Turing Machines (HALT_TM) B Emptiness problem for Linear Bounded Automata (E_{LBA}) C Membership problem for Context-Sensitive Languages (A_{LBA}) D More than one of the above E None of the above

Question 69

MCQ · Single Correct 1 mark

Which language class is recognized by Type-0 grammars (Unrestricted Grammars)?

A Context-Sensitive Languages B Context-Free Languages C Incorrect distractor statement D More than one of the above E None of the above

Question 70

MCQ · Single Correct 1 mark

Is the Emptiness problem L(M) = ∅ DECIDABLE for Turing Machines?

A Decidable in $O(n^2)$ B Decidable in Polynomial Time C Undecidable (by Rice's Theorem) D More than one of the above E None of the above