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.