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
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.9k
points)

11
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
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.9k
points)

4
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
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.9k
points)

1
view
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
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.9k
points)

2
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
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.9k
points)

7
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
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.9k
points)

1
view
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
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.9k
points)

2
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
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.9k
points)

2
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
in
Theory of Computation
by
gatecse
Boss
(
16.8k
points)

23
views
cmi2019
reduction
polynomialtime
exponentialtime
+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
in
Theory of Computation
by
srestha
Veteran
(
117k
points)

97
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
(
35.7k
points)

76
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
(
117k
points)

64
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.3k
points)

317
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
(
353
points)

203
views
decidability
contextfreelanguage
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)

249
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.5k
points)

113
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
(
105k
points)

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

241
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
(
425k
points)

761
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
Linear Algebra Important Points
GATE 2020
OFFICIAL GATE MOCK TEST RELEASED
IIITH: Winter Research Admissions 2019 (For Spring 2020)
TIFR and JEST exam
Follow @csegate
Recent questions tagged reduction
Recent Blog Comments
Lakshman Patel RJIT Do you have such notes...
Great work sir
Yes Sir, It will be very helpful if we get...
@arjun sir is there a pdf...
Really helpful sir Thanks a ton👍👍
50,645
questions
56,556
answers
195,715
comments
101,581
users