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.

  • $\begingroup$ It isn't clear what are the allowed patterns it can solve. Now SAT aims at finding a $\{0,1\}^n$ value for $x_1,\ldots,x_n$ which satisfies a given formula involving $\land,\lor,\lnot$, so your problem is harder than SAT ie. NP-hard (in $n$). $\endgroup$ – reuns Aug 12 '17 at 11:40
  • $\begingroup$ @reuns I don't understand. What do you mean ? I did show some reduction from 3SAT to problem from exercise. $\endgroup$ – Haskell Fun Aug 12 '17 at 12:58
  • $\begingroup$ What are the allowed patterns exactly ? Given a CNF formula $f : \{0,1\}^n \to \{0,1\}$ (call this a SAT patterns) SAT returns a solution $x \in \{0,1\}^n, f(x) = 1$ if it exists. Trivially your problem solves SAT. So the question is for what patterns SAT solves your problem (and if the reduction is polynomial). $\endgroup$ – reuns Aug 12 '17 at 13:04
  • $\begingroup$ From what I understand: I show that it is possible to transform problem from 3SAT to patterns (problem from task). And you agree with it. The problem is that transform problem from task to 3SAT ? In other words the problem is to show it on both direction, no only one direction ? $\endgroup$ – Haskell Fun Aug 12 '17 at 13:18
  • $\begingroup$ Your problem is NP-complete iff it solves SAT and SAT solves it, where solves means up to polynomial reduction and change of size (equivalently your problem is NP and solves every NP problem, like an universal non-deterministic Turing machine) $\endgroup$ – reuns Aug 12 '17 at 13:19

Your Answer

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

Browse other questions tagged or ask your own question.