New answers tagged reductions
1
vote
reducing the word problem for dtm to sat / cnf-sat / 2-sat
The answer is no because the problem seems undecidable.
You can reduce the halting problem to it.
- 7,072
6
votes
Accepted
Why can't $QBF$ be reduced to $SAT$
The problem is that the resulting formula does not have a length that is polynomial in the original formula since you are doubling the size of the formula every time you remove a quantifier.
Even ...
- 22.7k
2
votes
Is the problem of "DFA-TM-INCLUSION" recursively enumerable?
TOTAL is the problem of deciding whether a given Turing machine halts on all inputs. This problem is $\Sigma_2$-complete, and in particular, it is neither r.e. nor co-r.e.
Your problem is also $\...
- 268k
2
votes
Accepted
Is the problem of "DFA-TM-INCLUSION" recursively enumerable?
No, $\{\langle D,M\rangle\mid D\text{ is a DFA }\land M\text{ is a Turing Machine }\land L(D)\subseteq L(M)\}$ is not recursively enumerable.
Let $Z=\{0^{n}\mid n\ge0\}$. Call a Turing Machine (TM) $...
- 33k
2
votes
Accepted
Reducing to an NP-complete problem
Yep - your reasoning regarding your NP is correct. But not regarding NP-complete. The crux of the matter is that NP is inclusive, P is in NP and your problem R could be in P (and thus in NP).
NP-...
- 136
0
votes
Are Path-systems P-complete under logspace many-one reductions?
Admissible path-systems are, indeed, P-complete under many-one logspace reductions.
On the paper [1] we can see that Cook, given a Turing Machine $M$ that runs in $T(n)$ and some input $w$, builds a ...
- 307
3
votes
Accepted
$\mathrm{MON} = \{\langle M\rangle : \text{$M$ is monotone}\}$ is undecidable
Your answer is correct
What might seem missing is that $M'$ erases any input, writes $w$ and simulates $M$ on $w$, so it might seem that for any input (say $x$ which we erase), $M'$ takes the same ...
- 609
0
votes
Prove that DIFFERENTDFA, PDA {<M1, M2> | Where M1 is a DFA and M2 is a PDA where L(M1)≠L(M2)} is undecidable
Let $Different_{DFA,PDA} = \{<M_1,M_2> \vert \ M_1 \text{ is a DFA and } M_2 \text{ is a PDA where } L(M_1) \neq L(M_2)\}$, we want to show that this language is undecidable
Let $ALL_\text{CFG} =...
- 609
1
vote
Accepted
Prove $REJECT\leq_mACCEPT$ and vice versa
There might have been confusion on the meaning of "return the opposite of what it returns" when you run $M$ on $w$.
When $M$ runs forever, nothing can be returned by $M$. Then that rule does ...
- 33k
0
votes
Condensed Nearest Neighbor Explanation
The idea is to form a subset ($Z$) of the training set such that it classifies the same way as the whole set, using the nearest-neighbor rule.
If a classification error occurs, adding to $Z$ the ...
- 3,241
0
votes
If you can reduce A to B, does that mean B reduces to A?
basically just have to do the opposite
Not all functions are surjective!
It souds like you're thinking about some variant of many-one reducibility, where $A\subseteq\mathbb{N}$ is reducible to $B\...
- 2,425
1
vote
Accepted
On the language of Turing machines that accepts 1 but does not accept 0
Yes, we can reduce $\hat L$ to $\mathcal L$ as you suspected. Imagine we replace $1$ by $w_1$ and $0$ by $w_2$.
Let $s=\langle M_1,w_1,M_2,w_2\rangle$, where $M_1, M_2$ are Turing machines and $w_1, ...
- 33k
Top 50 recent answers are included