#StackBounty: #complexity-theory #np-complete #np-hard #np #open-problem Is the buckets of water problem in NP?

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.


Get this bounty!!!

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.