# Tag Info

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.
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 ...

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-...

### 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  we can see that Cook, given a Turing Machine $M$ that runs in $T(n)$ and some input $w$, builds a ...
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 ...
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\...
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, ...