satisfying boolean n variable DNF formula

Question

I have an n variable boolean DNF formula and an input set,z consisting of n-tuples. Each tuple consists of truth/false assignment to n variable. the number of tuples in Z is not fixed, obviously <= 2^n. Example: Lets assume, i have 2input DNF formula F(a,b) = a'b+ab'. Z={11,00,01}. I want to determine if any of these 3 input in Z satisfies F(a,b). Again size Z is not fixed and worst case is 2^n input combination.
I want to prove whether this problem is NPC or P.I tried with boolean formula satisfiability but Z content is not fixed. So, they are not exactly the same problem and I know general DNF formula satisfiability is in P. any suggestion, please.

Answer 1

Your problem is in P. Using the naive algorithm of just trying each input against each disjunction in Z, the runtime grows linearly with the size of Z and linearly with the size of F. There's no exponential growth in runtime with the size of the problem, therefore the problem remains in P.