Login
Register
@
Dark Mode
Profile
Edit my Profile
Messages
My favorites
Register
Activity
Q&A
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous Years
Blogs
New Blog
Exams
Dark Mode
Recent questions tagged reduction
2
votes
1
answer
1
#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
iarnav
asked
in
Theory of Computation
Sep 6, 2021
by
iarnav
252
views
theory-of-computation
reduction
0
votes
0
answers
2
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}$.
Lakshman Patel RJIT
asked
in
Theory of Computation
Oct 19, 2019
by
Lakshman Patel RJIT
212
views
michael-sipser
theory-of-computation
turing-machine
decidability
reduction
proof
0
votes
0
answers
3
Michael Sipser Edition 3 Exercise 5 Question 23 (Page No. 240)
Show that $A$ is decidable iff $A \leq_{m} 0 ^{\ast} 1^{\ast}$ .
Lakshman Patel RJIT
asked
in
Theory of Computation
Oct 19, 2019
by
Lakshman Patel RJIT
145
views
michael-sipser
theory-of-computation
decidability
reduction
proof
0
votes
0
answers
4
Michael Sipser Edition 3 Exercise 5 Question 22 (Page No. 240)
Show that $A$ is Turing-recognizable iff $A \leq_{m} A_{TM}$.
Lakshman Patel RJIT
asked
in
Theory of Computation
Oct 19, 2019
by
Lakshman Patel RJIT
112
views
michael-sipser
theory-of-computation
recursive-and-recursively-enumerable-languages
reduction
proof
0
votes
0
answers
5
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.)
Lakshman Patel RJIT
asked
in
Theory of Computation
Oct 19, 2019
by
Lakshman Patel RJIT
216
views
michael-sipser
theory-of-computation
context-free-grammar
reduction
post-correspondence-problem
decidability
proof
0
votes
0
answers
6
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.
Lakshman Patel RJIT
asked
in
Theory of Computation
Oct 19, 2019
by
Lakshman Patel RJIT
164
views
michael-sipser
theory-of-computation
recursive-and-recursively-enumerable-languages
decidability
reduction
proof
0
votes
0
answers
7
Michael Sipser Edition 3 Exercise 5 Question 6 (Page No. 239)
Show that $\leq_{m}$ is a transitive relation.
Lakshman Patel RJIT
asked
in
Theory of Computation
Oct 19, 2019
by
Lakshman Patel RJIT
114
views
michael-sipser
theory-of-computation
turing-machine
reduction
proof
0
votes
0
answers
8
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}$.)
Lakshman Patel RJIT
asked
in
Theory of Computation
Oct 19, 2019
by
Lakshman Patel RJIT
98
views
michael-sipser
theory-of-computation
turing-machine
reduction
proof
0
votes
0
answers
9
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?
Lakshman Patel RJIT
asked
in
Theory of Computation
Oct 19, 2019
by
Lakshman Patel RJIT
132
views
michael-sipser
theory-of-computation
regular-language
reduction
proof
0
votes
2
answers
10
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.
gatecse
asked
in
Theory of Computation
Sep 13, 2019
by
gatecse
369
views
cmi2019
reduction
p-np-npc-nph
1
vote
0
answers
11
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
srestha
asked
in
Theory of Computation
Feb 28, 2019
by
srestha
341
views
theory-of-computation
reduction
decidability
3
votes
1
answer
12
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 we ... of $P_1$ is independent of $P_2$ (i) and (ii) (ii) and (iv) (ii) and (iii) (iii) and (iv)
Ruturaj Mohanty
asked
in
Theory of Computation
Dec 27, 2018
by
Ruturaj Mohanty
447
views
go-mockgate-1
decidability
theory-of-computation
reduction
0
votes
0
answers
13
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 B, ... just an argument for complexity classes? Explain if possible how reduction actually works, and why I couldn't apply it to my problem.
HeadShot
asked
in
Algorithms
Dec 4, 2018
by
HeadShot
184
views
reduction
0
votes
0
answers
14
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
Mk Utkarsh
asked
in
Theory of Computation
Sep 19, 2018
by
Mk Utkarsh
295
views
theory-of-computation
reduction
0
votes
0
answers
15
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
srestha
asked
in
Algorithms
Sep 12, 2018
by
srestha
359
views
theory-of-computation
reduction
3
votes
2
answers
16
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$.
Tesla!
asked
in
Algorithms
Feb 5, 2018
by
Tesla!
1.9k
views
cmi2017
algorithms
reduction
p-np-npc-nph
3
votes
0
answers
17
Decidability
a) L is decidable b) L is undecidable c) L is regular d) None of these
Nymeria
asked
in
Theory of Computation
Jan 10, 2018
by
Nymeria
573
views
decidability
context-free-language
turing-machine
reduction
4
votes
1
answer
18
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}$).
Arjun
asked
in
Theory of Computation
Dec 10, 2017
by
Arjun
759
views
tifr2018
theory-of-computation
reduction
p-np-npc-nph
non-gate
1
vote
1
answer
19
Reducibility
Why this is incorrect? For any two languages A and B, if A ⊆ B, then A is reducible to B.
sunaina rawat
asked
in
Theory of Computation
Oct 2, 2017
by
sunaina rawat
696
views
theory-of-computation
reduction
5
votes
1
answer
20
UTM REDUCTION
please give proper reasoning.
junaid ahmad
asked
in
Theory of Computation
Sep 26, 2017
by
junaid ahmad
367
views
theory-of-computation
reduction
0
votes
1
answer
21
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
Bikram
asked
in
Theory of Computation
Aug 12, 2017
by
Bikram
276
views
tbb-toc-2
p-np-npc-nph
theory-of-computation
reduction
3
votes
1
answer
22
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
go_editor
asked
in
Theory of Computation
Dec 28, 2016
by
go_editor
421
views
tifr2016
theory-of-computation
reduction
p-np-npc-nph
1
vote
1
answer
23
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$.
go_editor
asked
in
Algorithms
May 27, 2016
by
go_editor
390
views
cmi2014
algorithms
reduction
45
votes
5
answers
24
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.
Sandeep Singh
asked
in
Theory of Computation
Feb 12, 2016
by
Sandeep Singh
9.8k
views
gatecse-2016-set1
theory-of-computation
easy
recursive-and-recursively-enumerable-languages
reduction
2
votes
1
answer
25
Question on reducibility
Please check if the given answer is correct or not.
shikharV
asked
in
Theory of Computation
Jan 5, 2016
by
shikharV
646
views
theory-of-computation
reduction
47
votes
3
answers
26
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 to $P_2$ $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
Kathleen
asked
in
Theory of Computation
Sep 22, 2014
by
Kathleen
10.4k
views
gatecse-2005
theory-of-computation
decidability
normal
reduction
3
votes
4
answers
27
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
Arjun
asked
in
Theory of Computation
Aug 25, 2014
by
Arjun
1.5k
views
reduction
theory-of-computation
normal
To see more, click for the
full list of questions
or
popular tags
.
Subscribe to GATE CSE 2023 Test Series
Subscribe to GO Classes for GATE CSE 2023
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
From GATE to Australia
DRDO Previous Year Papers
From Rank 4200 to 64: My Journey to Success in GATE CSE Exam
What are the key things to focus on during the final 10-15 days before the GATE exam to improve performance?
All India GO Classes Mock test
Subjects
All categories
General Aptitude
(2.5k)
Engineering Mathematics
(9.3k)
Digital Logic
(3.3k)
Programming and DS
(5.9k)
Algorithms
(4.6k)
Theory of Computation
(6.7k)
Compiler Design
(2.3k)
Operating System
(5.0k)
Databases
(4.6k)
CO and Architecture
(3.8k)
Computer Networks
(4.6k)
Non GATE
(1.3k)
Others
(2.4k)
Admissions
(649)
Exam Queries
(842)
Tier 1 Placement Questions
(17)
Job Queries
(74)
Projects
(9)
Unknown Category
(853)
Recent questions tagged reduction
Recent Blog Comments
Man, I feel you! I left my job to do gate this...
Yes, CDU provides assistance for internships...
Are you fully aware of the job opportunities in...
When this exam will happen ?
Can Someone guide me how to prepare for interview...