Recent questions tagged reduction - GATE Overflow

0 votes

0 answers

1

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}$.

asked Oct 19, 2019 in Theory of Computation by Lakshman Patel RJIT Veteran (60.8k points) | 19 views

0 votes

0 answers

2

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

asked Oct 19, 2019 in Theory of Computation by Lakshman Patel RJIT Veteran (60.8k points) | 12 views

0 votes

0 answers

3

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

asked Oct 19, 2019 in Theory of Computation by Lakshman Patel RJIT Veteran (60.8k points) | 6 views

0 votes

0 answers

4

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.)

asked Oct 19, 2019 in Theory of Computation by Lakshman Patel RJIT Veteran (60.8k points) | 6 views

0 votes

0 answers

5

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.

asked Oct 19, 2019 in Theory of Computation by Lakshman Patel RJIT Veteran (60.8k points) | 13 views

0 votes

0 answers

6

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

asked Oct 19, 2019 in Theory of Computation by Lakshman Patel RJIT Veteran (60.8k points) | 3 views

0 votes

0 answers

7

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}$.)

asked Oct 19, 2019 in Theory of Computation by Lakshman Patel RJIT Veteran (60.8k points) | 4 views

0 votes

0 answers

8

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?

asked Oct 19, 2019 in Theory of Computation by Lakshman Patel RJIT Veteran (60.8k points) | 6 views

0 votes

1 answer

9

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.

asked Sep 13, 2019 in Theory of Computation by gatecse Boss (17.6k points) | 43 views

+1 vote

0 answers

10

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

asked Feb 28, 2019 in Theory of Computation by srestha Veteran (119k points) | 107 views

0 votes

0 answers

11

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

asked Sep 19, 2018 in Theory of Computation by Mk Utkarsh Boss (36.8k points) | 82 views

0 votes

0 answers

12

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

asked Sep 12, 2018 in Algorithms by srestha Veteran (119k points) | 74 views

+3 votes

1 answer

13

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$.

asked Feb 5, 2018 in Algorithms by Tesla! Boss (18.5k points) | 343 views

+3 votes

0 answers

14

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

asked Jan 10, 2018 in Theory of Computation by Nymeria (359 points) | 212 views

+1 vote

1 answer

15

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

asked Oct 2, 2017 in Theory of Computation by sunaina rawat (171 points) | 275 views

+5 votes

1 answer

16

UTM REDUCTION
please give proper reasoning.

asked Sep 26, 2017 in Theory of Computation by junaid ahmad Loyal (8.6k points) | 120 views

+1 vote

1 answer

17

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 Halting ... $A$ says nothing about whether there is an algorithm for $P$. The Halting Problem can be solved using $A$.

asked May 27, 2016 in Algorithms by jothee Veteran (106k points) | 80 views

+2 votes

1 answer

18

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

asked Jan 5, 2016 in Theory of Computation by shikharV Active (3.5k points) | 252 views

+3 votes

4 answers

19

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

asked Aug 25, 2014 in Theory of Computation by Arjun Veteran (434k points) | 775 views

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

Recent questions tagged reduction

50,834 questions

57,853 answers

199,514 comments

108,390 users