3
$\begingroup$

I have a list like this:

1*0*0
1**0*
0*0**
001**

Where the number of elements in each row is $n$ and * is a wildcard for 0 or 1. I need a polynomial-time algorithm that can determine if there exists an $n$-bit number that does not equal any of the rows. Does anyone know of an algorithm that could do this? I've been thinking about evaluating the total number of possible solutions for each row and subtracting from $2^n$ but I can't figure out how to delete duplicates in polynomial time.

$\endgroup$
  • $\begingroup$ Maybe use regular expressions? $\endgroup$ – saadtaame Jun 19 '14 at 0:32
  • $\begingroup$ I thought about that but you would have to regex over a list of all numbers from 0 to $2^n$ which would obviously require polynomial time to generate and work with. $\endgroup$ – Elliot Gorokhovsky Jun 19 '14 at 0:33
  • $\begingroup$ Unless there's some other way to use regex that I didn't think of :) $\endgroup$ – Elliot Gorokhovsky Jun 19 '14 at 0:33
  • 1
    $\begingroup$ Satisfiability. $\endgroup$ – Hendrik Jan Jun 19 '14 at 1:11
  • $\begingroup$ Yes, there's a way to use a regex that you didn't think of. hint: look up how to take the complement of a finite automata. $\endgroup$ – Wandering Logic Jun 19 '14 at 2:25
7
$\begingroup$

Reduce from SAT. Consider a CNF formula $\phi = C_1 \land C_2 \land \ldots \land C_m$ over a set of variables $\{x_i\}_{i=1}^n$. Construct an instance of your problem as follows:

For each clause $C_i$, create a row (i.e. binary string) $B_i = b_1 b_2 \ldots b_n$, where

$$ b_k = \begin{cases} 1 & \text{if }\overline x_k \in C_i \\ 0 & \text{if } x_k \in C_i \\ * & \text{if } x_k, \overline x_k \notin C_i \end{cases}$$

We can preprocess $\phi$ to remove any clauses that contain both a literal and its negation, as these will of course always be satisfied and do not affect the result.

Any binary string $S$ that solves your problem also yields a satisfying assignment to $\phi$, using the reduction that sets $x_i$ to the value of $S_i$.

Thus your problem is $NP$-hard. Since it is also clearly in $NP$, it is also $NP$-complete.

$\endgroup$

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.