Skip to main content
Share Your Experience: Take the 2024 Developer Survey

All Questions

Filter by
Sorted by
Tagged with
0 votes
0 answers
20 views

Issues in the proof of $A_{TM}$ reducidability to $𝐸_{𝑇𝑀}$

I'm studying reducidability in Sipser Book and watching his videos, but I couldn't fully understand his proof of $A_{TM}$ reducidability to $𝐸_{𝑇𝑀}$ (p. 218, 3rd ed). Consider this extract: M1 = “...
user169972's user avatar
5 votes
1 answer
328 views

Is every non-recursively-enumerable language RE-hard?

Is every language $L \notin RE$ is $RE$-hard? Similarly, is every language $L \notin RE \cup coRE$ is $RE$-hard and $coRE$-hard? It seems like a simple question but I can't find an answer. I tried to ...
Amit Keinan's user avatar
0 votes
1 answer
102 views

Mapping Reduction from HALT?

I've been given a task to determine whether L={〈M〉|M is a TM that loops on the input c (a constant)} is decidable. I can prove co-L is recognizable so I figured a reduction from HALT to co-L would ...
Diode's user avatar
  • 1
-4 votes
2 answers
87 views

PSPACE and Polynomial reduction

thanks for your help. This is my first question, so I am very sorry for the bad presentation of the question. I am studying computer science and this is the question I have been asked for the course ...
Lior klunover's user avatar
1 vote
1 answer
42 views

Is the Language of all encodings of Turing Machine that at least halts on one input and outputs 0 semi-decidable?

I need to prove if the following Language is or is not semi-decidable. A := {w ∈ {0,1}^* | there exists an input x on which M_w produces the output 0} Where A is the language of all the encoding w ∈ {...
sergio ospina's user avatar
2 votes
1 answer
71 views

Reducing from the complement of the Halting Problem

Consider the halting problem $HALT_{TM} = \{\langle M, w\rangle: M \text{ is a TM that halts on input } w\}$, and some undecidable Language $L$ of the form $L = \{\langle M\rangle: M \text{ does a ...
cassnx's user avatar
  • 21
3 votes
1 answer
108 views

Can I reduce a non semi decidable and undecidable language to a semi decidable and undecidable langauge? many-one reduction

Let's say a Language L is NON-semi decidable and undecidable. Let's also take the Halting problem H, which is a semi decidable and undecidable language. Is it possible to reduce L to H in a many-one ...
sergio ospina's user avatar
2 votes
2 answers
262 views

Help understanding the proof that $L = \{ \langle M \rangle \mid M \text{ is a TM that accepts the input string } 101\}$ is undecidable

I understand of the existence of Rice's Theorem, however, I want to understand better how this reduction is formed. My professor gives the answer as follows: "By contradiction, assume that $L$ is ...
codeing_monkey's user avatar
0 votes
0 answers
21 views

Does valid value in L2 have to be gotten from L1 when we have a Many-One Reduction from L1 to L2

If I am doing a many-one reduction from L1 to L2, since it is described as a total function, does that mean that every possible encoding in L2 should have been achieved from L1 or is it possible that ...
River Uzoma's user avatar
0 votes
1 answer
36 views

Can an unreocognizable language be Turing-reducible to a recognizable language?

Suppose $L_1\preccurlyeq_T L_2$, and $L_1$ is unrecognizable, can $L_2$ be recognizable? With decidability, if $L_1$ is undecidable, then $L_2$ is undecidable, because $L_1$ is the “easier” question. ...
Arthur's user avatar
  • 3
-1 votes
1 answer
107 views

Understanding reductions and notation

I am currently working through Sipser's Introduction to the Theory of Computation. In chapter 5, he defines that a Language $A$ is mapping reducible to language $B$, written $A\leq_m B$ if there is a ...
talon23's user avatar
1 vote
1 answer
36 views

Concrete example of a set with a lower degree of unsolvability

Post's problem, posed in 1944 by Post, was to know if there is a recursively enumerable set, which, being undecidable, was not equivalent to the Halting problem under Turing reducibility. While I've ...
user6767509's user avatar
0 votes
1 answer
50 views

If $B \in RE$ then $A \in RE$ - Reduction

I know that if there is a Turing Reduction from $A$ to $B$, say $A \le_T B$, and $B \in R$ then $A \in R$. I also know that Turing Reduction is for Decision, and not Recognition. Is it possible to ...
Geo's user avatar
  • 47
1 vote
1 answer
65 views

$L=\{<M>|M~is~a~TM~and~L(M)=\{0^n1^n|n\ge0\}\}$

About the language $L=\{<M>|M~is~a~TM~and~L(M)=\{0^n1^n|n\ge0\}\}$ I want to determine if it is in RE / coRE or neither. I think that I found a mapping reduction from $\overline{A_{TM}}$ to $L$, ...
Geo's user avatar
  • 47
1 vote
1 answer
54 views

Mapping reduction - Bit Flip

Let $L=\{<M> | M$ is a TM, $L(M)\ne \emptyset$ and $\forall x\in L(M), \overline{x} \notin L(M) \}$ While $\overline{x}$ is the bit flip of $x$. I want to show a mapping reduction to prove that ...
Geo's user avatar
  • 47
2 votes
2 answers
112 views

Is the problem of "DFA-TM-INCLUSION" recursively enumerable?

Consider the following problem: Input: A Turing Machine M and a DFA D. Question: Is $L(D) \subseteq L(M)$? Of course, this problem is not decidable. Because it is known that judging whether a word ...
Audra Jacot's user avatar
1 vote
2 answers
141 views

Reduce instances of a-Turing-machine-does-not-accept-a-string to Turing machines that accept the empty string

I am struggling with a mapping reduction that I think cannot be correct, but I'm not able to say exactly what's the problem. Let $L_{u}= \{\langle M,w\rangle \mid M\text{ accept }w\}$, $\overline{L_{u}...
PedrV's user avatar
  • 55
1 vote
1 answer
501 views

Prove $H2 = \{\langle M\rangle : M$ accepts all inputs in $\{0, 1\}^∗$ whose length is at most $2\}$ is undecidable but recognizable

Yet another question from an exe. in the Computability class taught by Z. Luria - I'm not really sure how to prove the undecidability, moreover, didn't a finite language always decidable? I mean we ...
RedYoel's user avatar
  • 217
0 votes
1 answer
264 views

Prove that EXIST = {$<M>$:There exists a string $w ∈ Σ*$ such that $M$ halts on $w$} is undecidable

This is a question by my professor Z. Luria in my Computability course. My first approach was to try and prove it by contradiction, assuming that EXIST is decidable and using the algorithm that ...
RedYoel's user avatar
  • 217
0 votes
0 answers
51 views

In-place Acceptance Problem

In-place Acceptance Problem (InAP) Instance: A deterministic Turing Machine M and a w input for it. Question: Does M accept the input w without going through cell (|w|+1)? Show that InAP is PSPACE-...
user146767's user avatar
-1 votes
1 answer
34 views

If two languages are polytime reducable, does that imply they are also turing reducable

Is it possible for a pair of languages where A ≤T B but not A ≤p B? I am not sure if this could be the case since a turning reduction would imply we can use a decider for one language to decide ...
user145121's user avatar
0 votes
1 answer
364 views

Reduction: Does polytime reduction imply Turing reduction?

I am unsure if given $A \leqslant_p B$, does that imply that $A \leqslant_T B$. If we can polytime reduce $A$ to $B$, that would imply there is a decider for $A$ that runs in polynomial time which can ...
user145117's user avatar
-1 votes
1 answer
147 views

Reduction of RE and Rec languages

Suppose $L_1$ is reduces to $L_2$ in polynomial time, $L_1\leq_p^\mathsf{}L_2.$ we know that if $L_2$ is RE then $L_1$ is also RE and $L_2$ is REC then $L_1$ is also REC. And also I know that if $...
S. M.'s user avatar
  • 327
0 votes
1 answer
247 views

Reduction from recursive language to recursive enumerable

If any language $L_1$ reduces $L_2$ in polynomial time $L_1\leq_p^\mathsf{}L_2.$ If $L_1$ is recursive then $L_2$ is recursive and recursively enumerable, is it true? Because $L_2$ is at least as ...
S. M.'s user avatar
  • 327
1 vote
1 answer
44 views

Language classification

I am currently taking a computational course as part of my degree in Computer Science, and I would like to understand in depth the differences between these languages and if their belonging to R. The ...
Dolev Abuhatzira's user avatar
-1 votes
1 answer
169 views

Reduction from problem A to another problem B

I have a question from a test that I failed to pass, I failed to do the question. The question: Let A and B have two languages so that there is a reduction function f: $A\leq _pB$. Suppose that $A \in ...
masterHaham's user avatar
0 votes
2 answers
490 views

Reduction between CLIQUE to SUBSET SUM

I have a question from a test that I failed to pass, I failed to do the question. The question is about the reduction between Clique and Subset Sum. I tried to find an explanation for this on the ...
hch's user avatar
  • 83
0 votes
1 answer
76 views

Reduction from language in P to another language in NP

I have a question I was unable to do, from a last test I had. This is the question: Will be $A \in NP$ Let $c \in P$ be a language so that there exists $C \leq _pA$. Determine which of the following ...
hch's user avatar
  • 83
3 votes
1 answer
645 views

Reduction from the SAT problem to the NAE-SAT problem

I study complexity and computation independently. I have a problem that I can not solve. That's the problem: For the SAT problem, there is a version in which we receive as input phrase $\varphi$ in ...
masterHaham's user avatar
0 votes
2 answers
381 views

edge-coloring and vertex-coloring reduction problem

I study complexity and computation independently. I have a problem that I can not solve. That's the problem: Edge-Coloring problem, we get as input graph G = (V, E) and natural number k and ask "...
ish's user avatar
  • 15
0 votes
1 answer
244 views

Reduction from the Clique problem to the Odd Clique problem

I have a question that is not clear to me, and I have not been able to answer it from a test I had. This is the question: Let's look at the problem $Oclique$ , In it we get a graph $G = (V,E)$ , And ...
masterHaham's user avatar
0 votes
1 answer
37 views

Complications of a language that reaches a state of reject

I have a question that is not clear to me, and I have not been able to answer it from a test I had. This is the question Let's look at the language $L_\mathrm{reject} = ${ $\left \langle M,w \right \...
masterHaham's user avatar
1 vote
1 answer
358 views

edge-coloring reduction problem

I study complexity and computation independently. I have a problem that I can not solve. That's the problem: Edge-Coloring problem, we get as input graph G = (V, E) and natural number k and ask "...
ish's user avatar
  • 15
1 vote
1 answer
144 views

Language in NPC and CoNP

A few days ago I had a test that I failed to pass, and it had a question that I failed to do. the question: given: $A \in NPC$ $A \in CoNP$ Determine which of the following statements is correct: $P\...
masterHaham's user avatar
2 votes
2 answers
828 views

tautology vs satisfiability

I had a test that I failed to pass, and it had a question that I failed to do. This is the question: Let us look at the language TAUTOLOGY: Collect all the phrases $\varphi$ so that each placement on ...
hch's user avatar
  • 83
0 votes
1 answer
100 views

Reduction from TSP to even TSP

I have a question from a test that I failed to pass, I failed to do the question. The question: Let's look at the problem of the even-length traveling agent. Given graph $G = (V,E)$ and a weight ...
hch's user avatar
  • 83
1 vote
1 answer
145 views

Complexity of the language that enters an infinite loop

A few days ago I had a test that I failed to pass, and it had a question that I failed to do. This is the question Let's look at the language $L_\mathrm{loop} = ${ $\left \langle M,w \right \rangle$ | ...
masterHaham's user avatar
1 vote
3 answers
461 views

Relationship between NP and CoNP

I have a question from a test that I could not pass, I could not answer the question and I am looking for help with this question This is the question Will be $A\in \mathbf{NP}$ Suppose that $A\notin \...
hch's user avatar
  • 83
1 vote
2 answers
159 views

Reduction with CoNP and CoNPC

I have a question I was unable to do, from a last test I had. This is the question: Suppose that there is a language $A \neq \emptyset ,\sum{_{}}^{*}$ such that $A \in CoNP - CoNPC$. Determine ...
hch's user avatar
  • 83
1 vote
1 answer
73 views

Reduction with NPH

I have a question in complexities that I could not do. There will be D, E, F, three languages belonging to NPH. Suppose that the reductions exist $D \leq _P E$ and $E \leq _P F$. Determine which of ...
masterHaham's user avatar
-1 votes
1 answer
464 views

Reduction from SAT to 3SAT

a few days ago I had a test and could not pass it. This is a question I did not understand in the test. Recall the reduction we saw $SAT \leq _p 3SAT$. Given verse $\varphi$ in the form of $CNF$, we ...
hch's user avatar
  • 83
0 votes
1 answer
78 views

Deteremine if $L = \{\langle M\rangle : L(M) \text{ consits of all words of prime length}\}$ is in $R$ or in $RE\setminus R$ or not in $RE$

Deteremine if $L = \{\langle M\rangle : L(M) \text{ consits of all words of prime length}\}$ is in $R$ or in $RE\setminus R$ or not in $RE$ I am trying to prove that $L$ is not in $RE$ by reduction ...
John D's user avatar
  • 125
1 vote
2 answers
986 views

Reduction from vertex-coloring problem to edge-coloring problem

A few days ago I had a test and could not pass it. This is a question I did not understand in the test. We will look at the Edge-Coloring problem, in which, as is well known, we get as input graph G =...
hch's user avatar
  • 83
0 votes
1 answer
77 views

How to know if language is in comp or np?

I'm new to the site. I had a test a few days ago and failed it, I had a question I did not understand. This is the question: Let's look at the FALSE language: Collect all the verses P in the form of ...
hch's user avatar
  • 83
0 votes
1 answer
27 views

Reduction from 2 finite languages when one doesn't include epsilon and the other does

Just did a test about the subject that had the following question: I know it seems trivial and my first reaction was "well of course its true" but the epslilon kinda threw me off. $L_2$={ab,$...
David Pitts's user avatar
0 votes
1 answer
164 views

Issues in the proof of $E_{TM}$ is Turing reducible to $A_{TM}$

First definition: $A_{TM}$ = $\{ <M,w> | $M is a TM and M on w accepts$ \}$ Second definition: $E_{TM} = \{ <M> |$ M is a TM and L(M) = $\phi \}$ Let $T^{A_{TM}}$ be an oracle Turing ...
user777's user avatar
  • 729
0 votes
1 answer
107 views

How to prove that $L_{D}\leq L_{U}$?

I have the following two languages: $$ L_{U}\triangleq\left\{ \langle M,x\rangle\,:\,M\text{ accepts }x\right\} ,L_{D}\triangleq\left\{ \langle M\rangle\,:\,M\text{ accepts }\langle M\rangle\right\} $...
abuka123's user avatar
  • 115
0 votes
1 answer
60 views

If $L_1\in R$ and $L_2$ is non-trivial language then $L_1\leq L_2$

Language $L$ is trivial if $L=\varnothing$ or $L=\Sigma^*$. I'm trying to prove the following theorem: If $L_1\in R$ and $L_2$ is non-trivial language then $L_1\leq L_2$. If $L_2$ is non-trivial the ...
abuka123's user avatar
  • 115
0 votes
2 answers
367 views

Reduction of the diagonalization language to the universal language

I'm going through Jeffrey D. Ullman's Introduction to Automata Theory, Languages, and Computations. The author reduces an instance of the membership problem in $L_d$ (diagonalization language) to a ...
Yueor's user avatar
  • 83
1 vote
1 answer
247 views

Is there a mapping reduction for every two language $A$ and $B$ to some language $C$?

One of my friend told me that there is a language $C$ for every two languages $A$ and $B$ s.t $A \leq_{m} C$ and $B \leq_{m} C$ , he simply define two languages $A’=\{0w|w \in A\}$ and $B’=\{1w|w \in ...
Omid Yaghoubi's user avatar

1
2 3 4 5