Buckets of Water Problem – Part 2


Continuing from this question: The buckets of water problem

(All the definitions can be found there, so I will not repeat them).

As seen there by Yuval’s answer, the problem is NP-Hard. I was attempting to prove its Completeness, and while doing so – I was suddenly not sure whether or not it belongs to NP.

Because the witness is most likely to be a series of actions (filling buickets etc..), and that might be too long.

Ofcourse, we can change the definition of the language, in such a way we will limit the number of actions to be polynomial or make it part of the input (with a slight adjustment to represent the number of actions in unary, so it won’t be log of the number’s value).

But, I find it interesting to ask if this is a must?

And if we do not change anything – Can we tell for sure it is not NP? That there is no better (polynomial) witness.