Dark Mode

Recent questions tagged reduction

2 votes

1 answer

1

#TOC NPTEL ASSIGNMENT Question about reducibility
Please help me understand this question. I have searched on internet, but not avail. Click this to see the question

iarnav asked in Theory of Computation Sep 6, 2021

by iarnav

252 views

0 votes

0 answers

2

Michael Sipser Edition 3 Exercise 5 Question 25 (Page No. 240)
Give an example of an undecidable language $B$, where $B \leq_{m} \overline{B}$.

Lakshman Patel RJIT asked in Theory of Computation Oct 19, 2019

by Lakshman Patel RJIT

212 views

0 votes

0 answers

3

Michael Sipser Edition 3 Exercise 5 Question 23 (Page No. 240)
Show that $A$ is decidable iff $A \leq_{m} 0 ^{\ast} 1^{\ast}$ .

Lakshman Patel RJIT asked in Theory of Computation Oct 19, 2019

by Lakshman Patel RJIT

145 views

0 votes

0 answers

4

Michael Sipser Edition 3 Exercise 5 Question 22 (Page No. 240)
Show that $A$ is Turing-recognizable iff $A \leq_{m} A_{TM}$.

Lakshman Patel RJIT asked in Theory of Computation Oct 19, 2019

by Lakshman Patel RJIT

112 views

0 votes

0 answers

5

Michael Sipser Edition 3 Exercise 5 Question 21 (Page No. 240)
Let $AMBIG_{CFG} = \{\langle G \rangle \mid \text{G is an ambiguous CFG}\}$. Show that $AMBIG_{CFG}$ is undecidable. (Hint: Use a reduction from $PCP$ ... $a_{1},\dots,a_{k}$ are new terminal symbols. Prove that this reduction works.)

Lakshman Patel RJIT asked in Theory of Computation Oct 19, 2019

by Lakshman Patel RJIT

216 views

0 votes

0 answers

6

Michael Sipser Edition 3 Exercise 5 Question 7 (Page No. 239)
Show that if $A$ is Turing-recognizable and $A\leq_{m} \overline{A},$ then $A$ is decidable.

Lakshman Patel RJIT asked in Theory of Computation Oct 19, 2019

by Lakshman Patel RJIT

164 views

0 votes

0 answers

7

Michael Sipser Edition 3 Exercise 5 Question 6 (Page No. 239)
Show that $\leq_{m}$ is a transitive relation.

Lakshman Patel RJIT asked in Theory of Computation Oct 19, 2019

by Lakshman Patel RJIT

114 views

0 votes

0 answers

8

Michael Sipser Edition 3 Exercise 5 Question 5 (Page No. 239)
Show that $A_{TM}$ is not mapping reducible to $E_{TM}$. In other words, show that no computable function reduces $A_{TM}$ to $E_{TM}$. (Hint: Use a proof by contradiction, and facts you already know about $A_{TM}$ and $E_{TM}$.)

Lakshman Patel RJIT asked in Theory of Computation Oct 19, 2019

by Lakshman Patel RJIT

98 views

0 votes

0 answers

9

Michael Sipser Edition 3 Exercise 5 Question 4 (Page No. 239)
If $A \leq_{m} B$ and $B$ is a regular language, does that imply that $A$ is a regular language? Why or why not?

Lakshman Patel RJIT asked in Theory of Computation Oct 19, 2019

by Lakshman Patel RJIT

132 views

0 votes

2 answers

10

CMI2019-A-8
We have constructed a polynomial time reduction from problem A to problem B. Which of the following is not a possible scenario? We know of polynomial time algorithms for both A and B. We only know of exponential time algorithms for both A and B. We only ... polynomial time algorithm for B. We only know an exponential time algorithm for B, but we have a polynomial time algorithm for A.

gatecse asked in Theory of Computation Sep 13, 2019

369 views

1 vote

0 answers

11

Reduction (ACE)
If $L_{1}\preceq L_{2}$ and $L_{2}$ turing recognizable Then $L_{1}$ cannot be A)not REL B)Context Sensitive C)Context Free D)Recursive

srestha asked in Theory of Computation Feb 28, 2019

341 views

3 votes

1 answer

12

GATE Overflow | Mock GATE | Test 1 | Question: 24
Let a problem $P_1$ is reducible to another problem $P_2$. Identify the incorrect statement. (i) If $P_2$ is decidable then $P_1$ must be decidable (ii) If $P_2$ is un-decidable then $P_1$ may or mayn't be undecidable (iii) If $P_2$ is decidable then we ... of $P_1$ is independent of $P_2$ (i) and (ii) (ii) and (iv) (ii) and (iii) (iii) and (iv)

Ruturaj Mohanty asked in Theory of Computation Dec 27, 2018

by Ruturaj Mohanty

447 views

0 votes

0 answers

13

Doubt : Reducibility
$Question:$ https://gateoverflow.in/63261/%23made-easy $Approach:$ A is reduced to B . Here reduction is done at polynomial time. Here B is solved in polynomial time. So A should also be in polynomial time. Now A can not be harder than B, ... just an argument for complexity classes? Explain if possible how reduction actually works, and why I couldn't apply it to my problem.

HeadShot asked in Algorithms Dec 4, 2018

184 views

0 votes

0 answers

14

Reduction
A is Recursively Enumerable but not recursive and A reduces to B then which of the following can be true? A) B is Recursive B) B is Recursive Enumerable C) B is Not RE D) B is CFL

Mk Utkarsh asked in Theory of Computation Sep 19, 2018

295 views

0 votes

0 answers

15

Reducibility
State which are TRUE and which are FALSE (Question 1) and 2) both have same options) $1)$If there is an algorithm for polynomial time reduction from A to B? $2)$ if there is an algorithm for exponential time reduction from A to B? Consider the ... time algorithm then A can have polynomial time algo $d)$ A can have an polynomial time algorithm then B can have polynomial time algo

srestha asked in Algorithms Sep 12, 2018

359 views

3 votes

2 answers

16

CMI2017-A-10
We have constructed a polynomial time reduction from problem $A$ to problem $B$. Which of the following is a valid inference? If the best algorithm for $B$ takes exponential time, then there is no polynomial time algorithm for $A$ ... don't know whether there is a polynomial time algorithm for $B$, then there cannot be a polynomial time algorithm for $A$.

Tesla! asked in Algorithms Feb 5, 2018

by Tesla!

1.9k views

3 votes

0 answers

17

Decidability
a) L is decidable b) L is undecidable c) L is regular d) None of these

Nymeria asked in Theory of Computation Jan 10, 2018

573 views

4 votes

1 answer

18

TIFR CSE 2018 | Part B | Question: 15
$G$ respresents an undirected graph and a cycle refers to a simple cycle (no repeated edges or vertices). Define the following two languages. $\text{SCYCLE}=\{(G,k)\mid G \text{ contains a cycle of length at most k}\}$ ... $\text{SCYCLE}$ to $\text{LCYCLE}$).

Arjun asked in Theory of Computation Dec 10, 2017

by Arjun

759 views

1 vote

1 answer

19

Reducibility
Why this is incorrect? For any two languages A and B, if A ⊆ B, then A is reducible to B.

sunaina rawat asked in Theory of Computation Oct 2, 2017

by sunaina rawat

696 views

5 votes

1 answer

20

UTM REDUCTION
please give proper reasoning.

junaid ahmad asked in Theory of Computation Sep 26, 2017

by junaid ahmad

367 views

0 votes

1 answer

21

Test by Bikram | Theory of Computation | Test 2 | Question: 21
A problem $X$ is reducible to problem $Y$ in polynomial time. All the problems in NP can also be reduced to problem $X$. Then, which of the following statements are true? S1 : $X$ is NP complete and $Y$ is in NP. S2 : $X$ is NP complete and ... hard. S4 : $X$ and $Y$ are NP hard. S4 only S1, S2 & S3 S3 & S4 S1, S2, S3 & S4

Bikram asked in Theory of Computation Aug 12, 2017

by Bikram

276 views

3 votes

1 answer

22

TIFR CSE 2016 | Part B | Question: 3
Assume $P \neq NP$. Which of the following is not TRUE? $2$-SAT in NP $2$-SAT in coNP $3$-SAT is polynmial-time reducible to $2$-SAT 4-SAT is polynmial-time reducible to $3$-SAT $2$-SAT in P

go_editor asked in Theory of Computation Dec 28, 2016

421 views

1 vote

1 answer

23

CMI2014-A-04
Alan's task is to design an algorithm for a decision problem $P$. He knows that there is an algorithm $A$ that transforms instances of $P$ to instances of the Halting Problem such that $\text{yes}$ instances of $P$ map to $\text{yes}$ instances of the ... $A$ says nothing about whether there is an algorithm for $P$. The Halting Problem can be solved using $A$.

go_editor asked in Algorithms May 27, 2016

390 views

45 votes

5 answers

24

GATE CSE 2016 Set 1 | Question: 44
Let $X$ be a recursive language and $Y$ be a recursively enumerable but not recursive language. Let $W$ and $Z$ be two languages such that $\overline{Y}$ reduces to $W$, and $Z$ reduces to $\overline{X}$ (reduction means the standard ... enumerable. $W$ is not recursively enumerable and $Z$ is recursive. $W$ is not recursively enumerable and $Z$ is not recursive.

Sandeep Singh asked in Theory of Computation Feb 12, 2016

by Sandeep Singh

9.8k views

2 votes

1 answer

25

Question on reducibility
Please check if the given answer is correct or not.

shikharV asked in Theory of Computation Jan 5, 2016

646 views

47 votes

3 answers

26

GATE CSE 2005 | Question: 45
Consider three decision problems $P_1$, $P_2$ and $P_3$. It is known that $P_1$ is decidable and $P_2$ is undecidable. Which one of the following is TRUE? $P_3$ is decidable if $P_1$ is reducible to $P_3$ $P_3$ is undecidable if $P_3$ is reducible to $P_2$ $P_3$ is undecidable if $P_2$ is reducible to $P_3$ $P_3$ is decidable if $P_3$ is reducible to $P_2$'s complement

Kathleen asked in Theory of Computation Sep 22, 2014

10.4k views

3 votes

4 answers

27

To say P=NP
To say P=NP which one of the following is sufficient? (All reductions in polynomial time) A. Reduction of a NP problem to a P problem B. Reduction of a NP-complete problem to a P problem C. Reduction of a P problem to an NP problem D. Reduction of a P problem to an NP-complete problem

Arjun asked in Theory of Computation Aug 25, 2014

by Arjun

1.5k views

To see more, click for the full list of questions or popular tags.

Recent questions tagged reduction