# 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.
• 7,072
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

• 33k
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 [1] we can see that Cook, given a Turing Machine $M$ that runs in $T(n)$ and some input $w$, builds a ...
• 307
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

• 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