Bihar STET – TOC Practice Test | Set 3 ⋆ CSE Study247

Bihar STET – TOC Practice Test | Set 3

Questions 71-75 of 100

0% completed (0/100 answered)

Question 71

MCQ · Single Correct 1 mark

What is the known inclusion chain for logarithmic space classes?

A L ⊆ NL ⊆ P B P ⊆ NL ⊆ L C NL ⊆ L ⊆ P D P ⊆ L ⊆ NL

MCQ · Single Correct 1 mark

In polynomial time reductions, what property must the reduction function f satisfy?

A f(x) must be linear only B f(x) must be computable in POLYNOMIAL TIME on the length of input x C f(x) must run in O(1) D f(x) must be exponential

MCQ · Single Correct 1 mark

If problem A is NP-Complete and A $\le _p B$ where B ∈ NP, what is the complexity status of B?

A B is EXPTIME-complete B B is in Class P C B is NP-Complete D B is Undecidable

MCQ · Single Correct 1 mark

If problem A is NP-Complete and A $\le _p B (where B$ is NOT known to be in NP), what is the complexity status of B?

A B is Decidable B B is NP-Complete C B is in Class P D B is NP-Hard

MCQ · Single Correct 1 mark

What was the first problem proved to be NP-Complete without relying on reduction from another NP-Complete problem?

A 3-SAT B Clique C Vertex Cover D Boolean Satisfiability (SAT)