量杯問題之演算法與複雜度

Abstract

We study the water jug problem and obtain new lower and upper bounds on the minimum number of measuring steps. These bounds are tight and significantly improve previous results. We prove that to compute the crucial number µc(x) (i.e., min x=x·c ||x||1, where c 2 Nn, x 2 N, ||x||1 = Pni=1 |xi|) for estimating the minimum measuring steps is indeed a problem in PNP . Moreover, we prove that testing whether µc(x) is bounded by a fixed number is indeed NP-complete and thus the optimal jug measuring problem is NP-hard, which was also proved independently by [6]. Finally, we give a pseudo-polynomial time algorithm for computing µc(x) and a polynomial time algorithm, which is based on LLL basis reduction algorithm, for approximating the minimum number of jug measuring steps efficiently

We study the water jug problem and obtain new lower and upper bounds on the minimum number of measuring steps. These bounds are tight and significantly improve previous results. We prove that to compute the crucial number $\mu_{\mathbf{c}}(x)$ (i.e., $\min\limits_{x=\mathbf{x\cdot c}}||\mathbf{x}||_1$, where $\mathbf{c} \in \mathbf{N}^n, x \in \mathbf{N}, ||\mathbf{x}||_1 =\sum_{i=1}^n |x_i|$) for estimating the minimum measuring steps is indeed a problem in $P^{NP}$. Moreover, we prove that testing whether $\mu_{\mathbf{c}}(x)$ is bounded by a fixed number is indeed NP-complete and thus the optimal jug measuring problem is NP-hard, which was also proved independently by~\cite{Havas}. Finally, we give a pseudo-polynomial time algorithm for computing $\mu_{\mathbf{c}}(x)$ and a polynomial time algorithm, which is based on {\it LLL} basis reduction algorithm, for approximating the minimum number of jug measuring steps efficiently.