My question is related to Computational complexity of the word problem for semi-Thue systems with certain restrictions.

Is there a finite length-preserving string rewriting system $R$ (over say $\{0,1\}^\ast$) for which the following problem is NP-complete:

Given words u,v decide if $u \to_R v$

As I understand it is easy to construct $R$ where the problem is NP-hard. Take a TM solving 3SAT and apply Markov-Post.


It seems to me that the solution I posted at the other question (to which you link) provides an answer also to this question. Simply let $e$ be a program solving a fixed NP-complete problem, and let $R$ be the semi-Thue system that is described there. Basically, the rules of that system have basic transformation rules that transform $u$ to $u'$ in one step when $u$ codes a TM configuration and $u'$ codes the configuration after one computational step. The configuration description includes wildcard place-holders for the oracle, which are gradually filled in, and this is what allows for non-determinacy.

Now, the point is that to determine whether $u\to_Rv$ is at least as hard as solving the NP-complete problem that $e$ solves, and so this is NP-hard. But the problem for this particular rule set $R$ determined by program $e$ is also itself in NP, since once you know how to fill in the wildcards, the computation is deterministic (and has polynomial time length). That is, given $u$ and $v$, if it is possible to transform $u$ to $v$ via $R$, then this transformation proceeds by interpreting some of the wildcards of $u$ in a particular manner, and once having done so, the transformation rules are completely deterministic. So we can determine whether $u\to_R v$ in an NP manner.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.