# Length preserving rewriting system with NP-complete $u\to v$ problem

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.