Search results for reduction / GATE Overflow for GATE CSE

0 votes

0 answers

1

Hopcroft, Ullman Theorem 9.7 Reductions
There exists a language Ld = {M | M doesn't belong to L(M)}. Ld is the collection of Turing machines (programs) M such that M does not halt and accept when given itself as input. It is known and proved that Ld is a non- ... and Ld is non-RE, ATM must be non-RE. But we know that ATM is Recursively Enumerable and undecidable. How is this possible?

There exists a language Ld = {M | M doesn't belong to L(M)}. Ld is the collection of Turing machines (programs) M such that M does not halt and accept when given itself a...

dopq12

93 views

dopq12 asked Mar 5

47 votes

5 answers

2

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.

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

Sandeep Singh

12.4k views

Sandeep Singh asked Feb 12, 2016

2 votes

1 answer

3

#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

Please help me understand this question. I have searched on internet, but not avail. Click this to see the question

iarnav

468 views

iarnav asked Sep 6, 2021

52 votes

3 answers

4

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

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

Kathleen

12.1k views

Kathleen asked Sep 22, 2014

3 votes

2 answers

5

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

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

Tesla!

2.3k views

Tesla! asked Feb 4, 2018

0 votes

2 answers

6

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.

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

gatecse

662 views

gatecse asked Sep 13, 2019

1 votes

1 answer

7

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

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

go_editor

675 views

go_editor asked May 27, 2016

0 votes

0 answers

8

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

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$. Given an instance...

admin

395 views

admin asked Oct 19, 2019

0 votes

0 answers

9

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

Give an example of an undecidable language $B$, where $B \leq_{m} \overline{B}$.

admin

301 views

admin asked Oct 19, 2019

0 votes

0 answers

10

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.

Show that if $A$ is Turing-recognizable and $A\leq_{m} \overline{A},$ then $A$ is decidable.

admin

237 views

admin asked Oct 19, 2019

0 votes

0 answers

11

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

Show that $A$ is decidable iff $A \leq_{m} 0 ^{\ast} 1^{\ast}$ .

admin

201 views

admin asked Oct 19, 2019

0 votes

0 answers

12

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?

If $A \leq_{m} B$ and $B$ is a regular language, does that imply that $A$ is a regular language? Why or why not?

admin

188 views

admin asked Oct 19, 2019

0 votes

0 answers

13

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

Show that $A$ is Turing-recognizable iff $A \leq_{m} A_{TM}$.

admin

168 views

admin asked Oct 19, 2019

0 votes

0 answers

14

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

Show that $\leq_{m}$ is a transitive relation.

admin

169 views

admin asked Oct 19, 2019

0 votes

0 answers

15

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

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

admin

192 views

admin asked Oct 19, 2019

1 votes

0 answers

16

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

If $L_{1}\preceq L_{2}$ and $L_{2}$ turing recognizableThen $L_{1}$ cannot beA)not RELB)Context SensitiveC)Context FreeD)Recursi...

srestha

498 views

srestha asked Feb 28, 2019

3 votes

1 answer

17

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 ... of $P_1$ is independent of $P_2$ (i) and (ii) (ii) and (iv) (ii) and (iii) (iii) and (iv)

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

Ruturaj Mohanty

595 views

Ruturaj Mohanty asked Dec 27, 2018

0 votes

0 answers

18

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 ... just an argument for complexity classes? Explain if possible how reduction actually works, and why I couldn't apply it to my problem.

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

HeadShot

279 views

HeadShot asked Dec 4, 2018

0 votes

0 answers

19

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

A is Recursively Enumerable but not recursive and A reduces to B then which of the following can be true?A) B is RecursiveB) B is Recursive EnumerableC) B is Not RED) B i...

Mk Utkarsh

531 views

Mk Utkarsh asked Sep 19, 2018

0 votes

0 answers

20

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

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

srestha

551 views

srestha asked Sep 12, 2018

tags	tag:apple
author	user:martin
title	title:apple
content	content:apple
exclude	-tag:apple
force match	+apple
views	views:100
score	score:10
answers	answers:2
is accepted	isaccepted:true
is closed	isclosed:true