Proving "QUESTION" is NP-Complete by reduction from n-variable 3SAT I'm struggling with a problem in my theory of computation course that asks us to prove "QUESTION" is NP-complete by reduction from n-variable 3SAT. I've done a number of other similar reductions but I keep getting stumped on this particular problem.

We define a question as a string over the alphabet $\{0,1, ?\}$ and say that a question covers all of the strings where substituting ?? with 0s and 1s yields a string such as $0??1$ covers the four strings $0001$, $0011$, $0101$, $0111$.

We have to reduce the 3SAT problem to QUESTION= {A : A is a set of questions, each of length $n$, such that there exists a string $w$ of length $n$ where no question in A covers $w$}. To show that it is NP-complete.

I recognize that some instance of QUESTION will "cover" less than $2^n$ strings but I'm pretty stumped on how to go forward as all of the things I've tried end up not working out.
The reduction is straightforward, but what's likely tripping you up is that while 3CNF clauses seem to describe what's needed for a satisfying assignment, what they do more directly is describe what assignments won't work, and that's the insight you need to do the reduction.

Each clause will be converted into a QUESTION string of length $n$, where $n$ is the number of variables in the 3CNF formula.  Number the variables in the formula from 1 to $n$.  For each clause output a QUESTION string with a 0, 1 or ? in the position of the string corresponding to that variable's number.  Use 1 if the variable is negated in the clause, 0 if it is not negated and ? if it does not appear in the clause at all.

Example: the 3CNF formula has seven variables ($x_1$ ... $x_7$) and there is a clause ($x_1 \lor \lnot x_4 \lor x_7$) you would output the QUESTION string 0??1??0 .

Once all the clauses are converted to QUESTION strings, any $w$ string not covered by the QUESTION strings can be directly converted to a satisfying assignment for the 3CNF formula.  As in the QUESTION strings each position in $w$ corresponds to previously numbered variable.  But in $w$ each 0 represents a variable that should be negated in the satisfying assignment, and each 1 represents a variable that should not be negated.