Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
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.
