\item [Sqrt-sum problem] is known to be solvable in PSPACE but it has been a major open problem ([GareyGrahamJohnson’76]) whether it is solvable even in NP. \item [Allender et. al.,’06] Showed that Sqrt-Sum reduces to a more general problem, which they showed lies in the 4th level of the Counting Hierarchy ().
login/create account
Drupal
CSI of Charles University
Some update
Quotation from Etessami and Yannakakis, 2007:
\item [Sqrt-sum problem] is known to be solvable in PSPACE but it has been a major open problem ([GareyGrahamJohnson’76]) whether it is solvable even in NP. \item [Allender et. al.,’06] Showed that Sqrt-Sum reduces to a more general problem, which they showed lies in the 4th level of the Counting Hierarchy (
).