# n-DNF boolean formula k satisfiability

Given an n variable boolean DNF formula and a number k, does this formula has satisfying input combination greater than k?. (0<=k<=2^n). Where input is infinite number of n tuples where repeating tuple is possible. For exampl. F(a,b) =ab + a'b. Input set is (11,00,11,01) and k=2. Answer is 3 here so decision says yes as 3>k. Can i define this problem in more formal way and prove that it is np/npc/ anything else. I am looking for suggestions specially for infinite number of tuples. I am aware of npc and reduction stuffs but need help to classify this problem properly.

• I don't undersand your question. What do you mean by an "input combination greater than $k$"? How are you passing an infinite amount of data as input? Since P and NP characterize computation length in terms of input length, they don't make sense with infinite inputs. And why do you need an infinite input if you only have $n$ variables, so there are only finitely many possible formulas? – David Richerby Dec 9 '18 at 17:23
• Input combination greater than k means does more than k number of given n tuples satisfies the dnf formula. My problem is like that, where same tuple repeatedly occur in input set. I am actually wondering how to conclude about this problem. Suppose i have total z number of n tuples to be checked. Can i classify it then. – Shuvra Chakraborty Dec 9 '18 at 17:46
• Rather than clarifying by adding a comment, please edit the question so that the question is self-contained and people can understand what you are asking without having to read the comments. Thank you! – D.W. Dec 11 '18 at 7:25

## 1 Answer

Your problem can't be any easier than DNF-TAUTOLOGIES since that problem is produced by setting $$k$$ equal to $$2^n$$. Therefore your problem is NP-hard, just as DNF-TAUTOLOGIES is.

• Thank you. I am wondering which problem to choose for reduction. DNF tautologies or boolean satisfiability in this case . Could you suggest. – Shuvra Chakraborty Dec 11 '18 at 12:03