New answers tagged

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.
user avatar
  • 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 ...
user avatar
  • 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 $\...
user avatar
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) $...
user avatar
  • 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-...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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} =...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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\...
user avatar
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, ...
user avatar
  • 33k

Top 50 recent answers are included