The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
Facebook Login
or
Email or Username
Password
Remember
Login
Register

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
Recent questions tagged reduction
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
michaelsipser
theoryofcomputation
turingmachine
decidability
reduction
proof
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
michaelsipser
theoryofcomputation
decidability
reduction
proof
0
votes
0
answers
3
Michael Sipser Edition 3 Exercise 5 Question 22 (Page No. 240)
Show that $A$ is Turingrecognizable iff $A \leq_{m} A_{TM}$.
asked
Oct 19, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
60.8k
points)

6
views
michaelsipser
theoryofcomputation
turingrecognizablelanguages
reduction
proof
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
michaelsipser
theoryofcomputation
contextfreegrammars
reduction
postcorrespondenceproblem
decidability
proof
0
votes
0
answers
5
Michael Sipser Edition 3 Exercise 5 Question 7 (Page No. 239)
Show that if $A$ is Turingrecognizable 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
michaelsipser
theoryofcomputation
turingrecognizablelanguages
decidability
reduction
proof
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
michaelsipser
theoryofcomputation
turingmachine
reduction
proof
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
michaelsipser
theoryofcomputation
turingmachine
reduction
proof
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
michaelsipser
theoryofcomputation
regularlanguages
reduction
proof
0
votes
1
answer
9
CMI2019A8
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
cmi2019
reduction
pnpnpcnph
+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
theoryofcomputation
reduction
decidability
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
theoryofcomputation
reduction
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
theoryofcomputation
reduction
+3
votes
1
answer
13
CMI2017A10
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
cmi2017
algorithms
reduction
pnpnpcnph
+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
decidability
contextfreelanguages
turingmachine
reduction
+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
theoryofcomputation
reduction
+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
theoryofcomputation
reduction
+1
vote
1
answer
17
CMI2014A04
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
cmi2014
algorithms
reduction
+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
theoryofcomputation
reduction
+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 NPcomplete problem to a P problem C. Reduction of a P problem to an NP problem D. Reduction of a P problem to an NPcomplete problem
asked
Aug 25, 2014
in
Theory of Computation
by
Arjun
Veteran
(
434k
points)

775
views
reduction
theoryofcomputation
normal
To see more, click for the
full list of questions
or
popular tags
.
Quick search syntax
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
Recent Posts
PSUs Recruitment
ISRO Recruitment
BARC Recruitment
GATE CSE: All NITs Admissions
GATE CSE: IIT Hyderabad Admissions
Follow @csegate
Recent questions tagged reduction
Recent Blog Comments
Here is a poll on ISRO marks, you can say your...
They removed it,please create some poll or...
Did not find... post the link here
Please update your marks in gate overflow fb...
For CIL
50,834
questions
57,853
answers
199,514
comments
108,390
users