Language L1 is polynomial time reducible to language L2. Language L3 is polynomial time reducible to L2, which in turn is polynomial time reducible to language L4. Which of the following is/are true I. if L4 ∈ P, then L2 ∈ P II. if L1 ∈ P or L3 ∈ P, then L2 ∈ P III. L1 ∈ P, if and only if L3 ∈ P IV. if L4 ∈ P, then L1 ∈ P and L3 ∈ P?

Question

Language L1 is polynomial time reducible to language L2. Language L3 is polynomial time reducible to L2, which in turn is polynomial time reducible to language L4. Which of the following is/are true I. if L4 ∈ P, then L2 ∈ P II. if L1 ∈ P or L3 ∈ P, then L2 ∈ P III. L1 ∈ P, if and only if L3 ∈ P IV. if L4 ∈ P, then L1 ∈ P and L3 ∈ P?

II only
III only
I and IV only
I only

LohaHridoy

5 views

2025-01-04 04:42

1 Answers

Related Questions

Which of the following powerhouses is /are associated with the Damodar Valley Project I. Durgapur. II. Chandrapura. III. Maithon. IV. Hampi. Choose the right option. A. Only I and II. B. Only II and III. C. I, II, and III. D. I, II, III, and IV.?

1 Answers 7 Views

Consider two decision problems Q1, Q2 such that Q1 reduces in polynomial time to 3-SAT and 3-SAT reduces in polynomial time to Q2. Then which one of the following is consistent with the above statement?

1 Answers 4 Views

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 recursive II. L̅2 (complement of L2) is recursive III. L̅1 is context-free IV. L̅1 ∪ L2 is recursively enumerable?

1 Answers 5 Views

Consider the following two-process synchronization solution. Process 0 - - - - - - - - Entry: loop while (turn == 1); (critical section) Exit: turn = 1; Process 1 - - - - - - - - Entry: loop while (turn == 0); (critical section) Exit: turn = 0; The shared variable turn is initialized to zero. Which one of the following is TRUE?

1 Answers 5 Views

In the question below are given three statements followed by three conclusions numbered I, II and III. You have to take the given statements to be true even if they seem to be at variance with commonly known facts. Read all the conclusions and then decide which of the given conclusions logically follows from the given statements disregarding commonly known facts. Statements: I. Only B is A II. Only a few C are D III. Few D are B Conclusions: I. Some A are D II. Some C are not B III. Some D are not B?

1 Answers 4 Views

In the question below are given three statements followed by three conclusions numbered I, II and III. You have to take the given statements to be true even if they seem to be at variance with commonly known facts. Read all the conclusions and then decide which of the given conclusions logically follows from the given statements disregarding commonly known facts. Statements: I. Some sabha are houses II. Only bill are money III. Only a few cash are bill Conclusions: I. All bill cannot be cash II. No sabha is money III. Some money are bill?

1 Answers 5 Views

In the question below are given three statements followed by three conclusions numbered I, II and III. You have to take the given statements to be true even if they seem to be at variance with commonly known facts. Read all the conclusions and then decide which of the given conclusions logically follows from the given statements disregarding commonly known facts. Statements: I. Some sabha are houses II. Only bill are money III. Only a few cash are bill Conclusions: I. Some money being house is a possibility II. Some cash is not the bill is a possibility III. All money is a bill?

1 Answers 5 Views

Let L1, L2 be any two context-free languages and R be any regular language. Then which of the following is/are CORRECT I. L1 ∪ L2 is context-free II. L̅1 is context-free III. L1 – R is context-free IV. L1 ∩ L2 is context-free?

1 Answers 5 Views

A boatman wants to cross a river which distance is 80 km. In the starting boatman goes to 20 km and then turn 90 degree anti-clock wise and goes 60 km in upstream after that he turn 90 degree clock wise and goes 40 km. After that he turn 90 degree clock wise and goes 60 km. In the end he turn 90 degree anti-clock wise and goes 20 km and reach his destination. The speed of boatman is 22 km/hr and speed of stream is 4 km/hr. Find the time to cover total distance?

1 Answers 4 Views

The value of the function f(x) is given at n distinct values of x and its value is to be interpolated at the point x* using all the n points. The estimate is obtained first by the Lagrange polynomial, denoted by IL, and then by the Newton polynomial, denoted by IN. Which one of the following statements is correct?

1 Answers 6 Views

AhmedNazir · Accepted Answer · 2022-09-04T04:29:57+06:00

Option 3 : I and IV only

Concept:

If a problem A is polynomial time reducible to problem B. So, B is at least as hard as A.

Explanation:

Here, L₁ is polynomial time reducible to L₂, L₂ is at least as hard as L₁.

L₃ is polynomial time reducible to L₂

L₂ is polynomial time reducible to L_4.

Option 1:

if L₄ ∈ P, then L₂ ∈ P

L₂ is polynomial time reducible to L₄. L₄ belongs to P type problem then L₂is also P type problem. So, it is true.

Option 2:

if L₁ ∈ P or L₃ ∈ P, then L₂ ∈ P

If L₁ belongs to P or L₃belongs to P, then L₂ belongs to P. This is not true because L₁, L₃ is a polynomial time reducible to L₂ not L₂ is polynomial time reducible to L₁.

Option 3:

L₁ ∈ P, if and only if L₃ ∈ P

L₁ belongs to P, if and only if L₃ belongs P. This is false because L₃ is polynomial time reducible to L₂ not L₁.

Option 4:

if L₄ ∈ P, then L₁ ∈ P and L₃ ∈ P

This statement is true because we know that L₁ is polynomial time reducible to L₂ and L₃ is polynomial time reducible to L₂ and L₂ is polynomial reducible to L₄ so L₁ and L₂ is polynomial time reducible to L₄.