0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\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.