There are given:
- finite alphabet $Σ$ with some symbols $a,b$.
- finite list of
- forbidden patterns natural number $n$ written unary (eg. $1^n$)
Result: Is there exists word of form $a\Sigma^*b$ with length at most $n$ such that it doesn't contains (as subword) any of word from list (list contains many words, expressed by patterns). Show that this problem is NP-complete.
Example to better understand patterns: $bbaaacb$ contains a word $a??c$, but $aacba$ doesn't contain $a??c$, where $?$ is some special symbol in $\Sigma$
I am not sure if I correctly understand reduction, can you help me verify it ? Also other approaches are welcome here,
My approach is following:
We reduce 3-SAT problem, let $n=6$
$(x_1 \vee \neg x_4\vee x_6)$. For this clauses we create one pattern and put on the forbidden list:
$0??1?0$ what means that there are forbidden assigments such that it assign: $x_1=0, x_4=1, x_6=0$. Such assigment is forbidden because in this case it is not possible to satisfy this clause.
Analogously, we do with rest of clauses, so list of forbidden pattern has size $k$ where $k$ is number of clauses. Of course generating this list takes polynomial time.
Now, we can set $\Sigma=\{a,b,0,1\}, n=\text{number of variables}$ and use problem from statement of exercise to check if there exists assigment which satisfies this formula.