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.

Improve this question
$\endgroup$
11
  • $\begingroup$ Maybe use regular expressions? $\endgroup$
    – mrk
    Jun 19, 2014 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, 2014 at 0:33
  • $\begingroup$ Unless there's some other way to use regex that I didn't think of :) $\endgroup$
    – Elliot Gorokhovsky
    Jun 19, 2014 at 0:33
  • 1
    $\begingroup$ Satisfiability. $\endgroup$
    – Hendrik Jan
    Jun 19, 2014 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, 2014 at 2:25

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.