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
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?
dopq12
asked
in
Theory of Computation
Mar 5
by
dopq12
75
views
decidability
theory-of-computation
turing-machine
reduction
recursive-and-recursively-enumerable-languages
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
iarnav
asked
in
Theory of Computation
Sep 6, 2021
by
iarnav
449
views
theory-of-computation
reduction
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}$.
admin
asked
in
Theory of Computation
Oct 19, 2019
by
admin
294
views
michael-sipser
theory-of-computation
turing-machine
decidability
reduction
proof
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}$ .
admin
asked
in
Theory of Computation
Oct 19, 2019
by
admin
201
views
michael-sipser
theory-of-computation
decidability
reduction
proof
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}$.
admin
asked
in
Theory of Computation
Oct 19, 2019
by
admin
166
views
michael-sipser
theory-of-computation
recursive-and-recursively-enumerable-languages
reduction
proof
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.)
admin
asked
in
Theory of Computation
Oct 19, 2019
by
admin
387
views
michael-sipser
theory-of-computation
context-free-grammar
reduction
post-correspondence-problem
decidability
proof
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.
admin
asked
in
Theory of Computation
Oct 19, 2019
by
admin
239
views
michael-sipser
theory-of-computation
recursive-and-recursively-enumerable-languages
decidability
reduction
proof
0
votes
0
answers
8
Michael Sipser Edition 3 Exercise 5 Question 6 (Page No. 239)
Show that $\leq_{m}$ is a transitive relation.
admin
asked
in
Theory of Computation
Oct 19, 2019
by
admin
166
views
michael-sipser
theory-of-computation
turing-machine
reduction
proof
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}$.)
admin
asked
in
Theory of Computation
Oct 19, 2019
by
admin
180
views
michael-sipser
theory-of-computation
turing-machine
reduction
proof
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?
admin
asked
in
Theory of Computation
Oct 19, 2019
by
admin
185
views
michael-sipser
theory-of-computation
regular-language
reduction
proof
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.
gatecse
asked
in
Theory of Computation
Sep 13, 2019
by
gatecse
635
views
cmi2019
reduction
p-np-npc-nph
1
vote
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
srestha
asked
in
Theory of Computation
Feb 28, 2019
by
srestha
500
views
theory-of-computation
reduction
decidability
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)
Ruturaj Mohanty
asked
in
Theory of Computation
Dec 27, 2018
by
Ruturaj Mohanty
590
views
go-mockgate-1
decidability
theory-of-computation
reduction
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.
HeadShot
asked
in
Algorithms
Dec 4, 2018
by
HeadShot
277
views
reduction
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
Mk Utkarsh
asked
in
Theory of Computation
Sep 19, 2018
by
Mk Utkarsh
503
views
theory-of-computation
reduction
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
srestha
asked
in
Algorithms
Sep 12, 2018
by
srestha
541
views
theory-of-computation
reduction
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$.
Tesla!
asked
in
Algorithms
Feb 4, 2018
by
Tesla!
2.3k
views
cmi2017
algorithms
reduction
p-np-npc-nph
3
votes
0
answers
18
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
851
views
decidability
context-free-language
turing-machine
reduction
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}$).
Arjun
asked
in
Theory of Computation
Dec 10, 2017
by
Arjun
967
views
tifr2018
theory-of-computation
reduction
p-np-npc-nph
non-gate
1
vote
1
answer
20
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
998
views
theory-of-computation
reduction
5
votes
1
answer
21
UTM REDUCTION
please give proper reasoning.
junaid ahmad
asked
in
Theory of Computation
Sep 26, 2017
by
junaid ahmad
615
views
theory-of-computation
reduction
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
Bikram
asked
in
Theory of Computation
Aug 12, 2017
by
Bikram
662
views
tbb-toc-2
p-np-npc-nph
theory-of-computation
reduction
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
go_editor
asked
in
Theory of Computation
Dec 28, 2016
by
go_editor
626
views
tifr2016
theory-of-computation
reduction
p-np-npc-nph
1
vote
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$.
go_editor
asked
in
Algorithms
May 27, 2016
by
go_editor
653
views
cmi2014
algorithms
reduction
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.
Sandeep Singh
asked
in
Theory of Computation
Feb 12, 2016
by
Sandeep Singh
12.4k
views
gatecse-2016-set1
theory-of-computation
easy
recursive-and-recursively-enumerable-languages
reduction
2
votes
1
answer
26
Question on reducibility
Please check if the given answer is correct or not.
shikharV
asked
in
Theory of Computation
Jan 4, 2016
by
shikharV
818
views
theory-of-computation
reduction
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
Kathleen
asked
in
Theory of Computation
Sep 22, 2014
by
Kathleen
12.1k
views
gatecse-2005
theory-of-computation
decidability
normal
reduction
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
Arjun
asked
in
Theory of Computation
Aug 25, 2014
by
Arjun
2.1k
views
reduction
theory-of-computation
normal
To see more, click for the
full list of questions
or
popular tags
.
Subscribe to GATE CSE 2024 Test Series
Subscribe to GO Classes for GATE CSE 2024
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
Post GATE 2024 Guidance [Counseling tips and resources]
GATE CSE 2024 Result Responses
[Project Contest] Pytorch backend support for MLCommons Cpp Inference implementation
Participating in MLCommons Inference v4.0 submission (deadline is February 23 12pm IST)
IIITH PGEE 2024 Test Series by GO Classes
Subjects
All categories
General Aptitude
(3.5k)
Engineering Mathematics
(10.4k)
Digital Logic
(3.6k)
Programming and DS
(6.2k)
Algorithms
(4.8k)
Theory of Computation
(6.9k)
Compiler Design
(2.5k)
Operating System
(5.2k)
Databases
(4.8k)
CO and Architecture
(4.0k)
Computer Networks
(4.9k)
Artificial Intelligence
(79)
Machine Learning
(48)
Data Mining and Warehousing
(25)
Non GATE
(1.4k)
Others
(2.7k)
Admissions
(684)
Exam Queries
(1.6k)
Tier 1 Placement Questions
(17)
Job Queries
(80)
Projects
(11)
Unknown Category
(870)
64.3k
questions
77.9k
answers
244k
comments
80.0k
users
Recent questions tagged reduction
Recent Blog Comments
category ?
Hi @Arjun sir, I have obtained a score of 591 in ...
download here
Can you please tell about IIT-H mtech CSE self...
Please add your admission queries here:...