*Bounty: 50*

*Bounty: 50*

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 NP-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 buckets etc …), and that might be too long.

Of course, 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.