Recent questions tagged 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

92 views

dopq12 asked Mar 5

2 votes

1 answer

2

#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

0 votes

0 answers

3

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

4

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

5

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

6

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

7

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

8

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

9

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

0 votes

0 answers

10

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

2 answers

11

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

0 answers

12

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

13

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

594 views

Ruturaj Mohanty asked Dec 27, 2018

0 votes

0 answers

14

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

15

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

16

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

3 votes

2 answers

17

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

3 votes

0 answers

18

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

a) L is decidableb) L is undecidablec) L is regulard) None of these

Nymeria

872 views

Nymeria asked Jan 10, 2018

4 votes

1 answer

19

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

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

Arjun

981 views

Arjun asked Dec 10, 2017

1 votes

1 answer

20

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

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

sunaina rawat

1.0k views

sunaina rawat asked Oct 2, 2017

5 votes

1 answer

21

UTM REDUCTION
please give proper reasoning.

please give proper reasoning.

junaid ahmad

632 views

junaid ahmad asked Sep 26, 2017

0 votes

1 answer

22

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

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

Bikram

672 views

Bikram asked Aug 12, 2017

3 votes

1 answer

23

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

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$-SAT4-SAT is polynmial-time reducible to $3$-...

go_editor

641 views

go_editor asked Dec 28, 2016

1 votes

1 answer

24

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

47 votes

5 answers

25

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

26

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

Please check if the given answer is correct or not.

shikharV

835 views

shikharV asked Jan 4, 2016

52 votes

3 answers

27

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

4 answers

28

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

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 problemB. Reduction of a NP-complete problem ...

Arjun

2.2k views

Arjun asked Aug 25, 2014

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