Question

Show that the following problem is NP-complete. You are given a set of states $\mathit{Q}\mathbf{=}\left\{q0,q1,...,ql\right\}$and a collection of pairs $\left\{\left(s1,r1\right),.......,\left(sk,rk\right)\right\}$ where the $\mathit{s}\mathit{i}$are distinct strings over role="math" localid="1663239026093" $\mathbf{\sum }\mathbf{=}\left\{0,1\right\}$, and the $\mathit{r}\mathit{i}$are (not necessarily distinct) members of $\mathit{Q}$. Determine whether a role="math" localid="1663238989670" $\mathit{D}\mathit{F}\mathit{A}\mathit{M}\mathbf{=}\left(Q,\sum ,?,q0,F\right)$exists whererole="math" localid="1663239087484" $\mathbf{?}\left(q0,si\right)\mathbf{=}\mathit{r}\mathit{i}\mathbf{}\mathit{f}\mathit{o}\mathit{r}\mathbf{}\mathit{e}\mathit{a}\mathit{c}\mathit{h}\mathbf{}\mathit{i}$ . Here, role="math" localid="1663239126896" $\mathbf{?}\left(q,s\right)$is the state that $\mathit{M}$ enters after reading s, starting at state q.

Short answer

$F$is satisfiable $iff$there is some $DFA$that satisfy$CandR$ . Reduction is taking some polynomial time. Therefore, given problem is $NP$-complete.

Step-by-step solution

Introduction

Correct $DFA$ which satisfy$C$constraints and in polynomial time $\$\backslash pi\$$ can be guessed by Non Deterministic Turing Machine $iff$ such $DFA$ available or exist.

For showing that problem is $NP$ complete reduce it to polynomial time.

Consider the formula$\$F=\backslash wedge\_\{j=1\}^\left\{m\right\}R\_\left\{j\right\}\$where\$R\_\left\{j\right\}=\backslash left(s\_\{j\}\backslash vee$$u\_\left\{j\right\}\backslash right)\$$and construction some constraints $Cand\$\backslash Pi\$\$C=\backslash left\backslash \{c\_\{T\},c\_\{1\},c\_\{2\}\backslash right\backslash \}\$$ are states.

Creating pair $\$\backslash left(\backslash \backslash varepsilon,c\_\{F\}\backslash right)\{text\{in\left\}\right\}\backslash Pi\backslash \mathrm{user}1\{\backslash text\{forenforcing\left\}\right\}c\_\left\{F\right\}\$$as starting state.

Explanation

Every variable belongs to $\$F\backslash text\{willcreatethepairs\}\backslash left(s\backslash bars\{s\},c\_\{T\}\backslash right)\$$and $\$\backslash left(\backslash bar\{s\},c\_\{T\}\backslash right)\$$.

Every clause $\$R\_\left\{j\right\}^\{\backslash prime\}\$$' in formula will have pair in localid="1663237422355" $\$\backslash Pi\{t\backslash text\{thatis\left\}\right\}\backslash \mathrm{user}1\backslash left(s\backslash \#\_\{s\},$$c\_\left\{1\right\}\backslash right\$c\_\{$and $\$\backslash left(\backslash bar\{s\}\backslash \#\_\{s\},c\_\{2\}\backslash right)\$$that enforces that when reading and $\$\backslash bar\left\{s\right\},DFA\$$must be in different state.

Choose any $s$ in $F$. Now for $\$\backslash forall\$$variable $t$ create other three points in $\$\backslash Pi$.$\backslash left(s\backslash bar\{s\}t,$$c\_\left\{T\right\}\backslash right),\backslash left\backslash \#\_\{s\}t,c\_\{1\}\backslash right)\backslash left(\backslash bar\{s\}\backslash \#\_\{s\}t,c\_\{2\}\backslash right)\$$

$F$ is satisfiable $iff$ there is some $DFA$ that satisfy $CandR$. Reduction is taking some polynomial time. Therefore given problem is $NP$-complete.