0
$\begingroup$

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.

$\endgroup$
  • 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 Richerby Dec 9 '18 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 Chakraborty Dec 9 '18 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. Dec 11 '18 at 7:25
1
$\begingroup$

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.

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

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.