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.
$\begingroup$
$\endgroup$
3
-
1$\begingroup$ 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? $\endgroup$– David RicherbyCommented Dec 9, 2018 at 17:23
-
$\begingroup$ 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. $\endgroup$– Shuvra ChakrabortyCommented Dec 9, 2018 at 17:46
-
$\begingroup$ 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! $\endgroup$– D.W. ♦Commented Dec 11, 2018 at 7:25
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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.
answered Dec 10, 2018 at 23:38
-
$\begingroup$ Thank you. I am wondering which problem to choose for reduction. DNF tautologies or boolean satisfiability in this case . Could you suggest. $\endgroup$ Commented Dec 11, 2018 at 12:03