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.
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 ...
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 $\...
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) $...
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-...
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 ...
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 ...
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} =...
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 ...
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 ...
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\...
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, ...
Top 50 recent answers are included
Related Tags
reductions × 1180complexity-theory × 558
np-complete × 334
turing-machines × 219
computability × 216
np-hard × 137
undecidability × 123
graphs × 92
np × 89
satisfiability × 72
algorithms × 70
decision-problem × 61
halting-problem × 50
polynomial-time-reductions × 46
polynomial-time × 43
formal-languages × 41
proof-techniques × 37
3-sat × 29
space-complexity × 28
optimization × 27
complexity-classes × 27
time-complexity × 23
semi-decidability × 18
partitions × 18
approximation × 16