I am currently in the process of proving some complexity bounds about k-DNF. However I am confused what the $n$ in the time complexity would refer to in this case (that is that I don't know how the "size" of a k-DNF is defined, nor was it defined in the assignment). Is it the number of clauses, the number of literals (distinct or nondistinct?) or something else? I think they should all be equivalent for the purpose of complexity, but I would rather adopt the standard convention.

| cite | improve this question | | | | |
  • $\begingroup$ Number of literals. $\endgroup$ – Yuval Filmus Feb 10 '19 at 4:14

The two standard conventions are number of clauses and number of literals (counted with repetition!). The two measures are within a factor of $n$ of each other.

| cite | improve this answer | | | | |

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.