Sum of Square Roots Problem
|
Supervisor |
|
|
Suitable for |
Abstract
The sum of square roots problem asks given integers a_1,...,a_m and b_1,...,b_n, whether
\sqrt{a_1} + ... + \sqrt{a_m} > \sqrt{b_1} + ... + \sqrt{b_n}
This problem occurs naturally in many settings, including the Euclidean Travelling Salesman Problem and various problems in probabilistic verification. It is known to be in PSPACE but is not known to be NP-hard, and could conceivable be decidable in polynomial time. The goal of this project is survey the literature surrounding this problem. There is also scope for original research concerning circuit bounds for a variant of the problem. Suitable background courses include Complexity Theory. Knowledge of basic number theory and algebra would also be helpful.
Reading:
Johannes Bl\"{o}mer. Computing Sums of Radicals in Polynomial Time. Proceedings of FoCS'91. IEEE Computer Society Press 1991.
Qi Cheng. On Comparing Sums of Square Roots of Small Integers. Proceedings of MFCS 2006, LNCS 4162, Springer 2006.