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 ($ P^{PP^{PP^{PP}}} $).

Reply

Comments are limited to a maximum of 1000 characters.
More information about formatting options