Skip to main content
Computer Science

Return to Answer

replaced http://cstheory.stackexchange.com/ with https://cstheory.stackexchange.com/
Source Link
Community Bot
Community Bot
  • 1

Yes. ​ By the real-number analogue of the Tseytin transformation, that
reduces to the existential theory of the reals, which is in PSPACE by

page 291 and the bottom of page 290 from this paper
and
the answers to this questionthis question

.


For all real numbers $x$, $\sqrt{x^2}$ and $x$ are both well-formed and ​ ​ ​ $\sqrt{x^2} = x$ ​ if and only if ​ $0\leq x$ ​ , ​ ​ ​ so testing inequality reduces to your problem. ​ ​ ​ ​ ​ ​ ​ I'm not aware of any better upper bound for testing inequalities of sums-of-square-rootsinequalities of sums-of-square-roots than this paper, which puts it in the counting hierarchy.

Yes. ​ By the real-number analogue of the Tseytin transformation, that
reduces to the existential theory of the reals, which is in PSPACE by

page 291 and the bottom of page 290 from this paper
and
the answers to this question

.


For all real numbers $x$, $\sqrt{x^2}$ and $x$ are both well-formed and ​ ​ ​ $\sqrt{x^2} = x$ ​ if and only if ​ $0\leq x$ ​ , ​ ​ ​ so testing inequality reduces to your problem. ​ ​ ​ ​ ​ ​ ​ I'm not aware of any better upper bound for testing inequalities of sums-of-square-roots than this paper, which puts it in the counting hierarchy.

Yes. ​ By the real-number analogue of the Tseytin transformation, that
reduces to the existential theory of the reals, which is in PSPACE by

page 291 and the bottom of page 290 from this paper
and
the answers to this question

.


For all real numbers $x$, $\sqrt{x^2}$ and $x$ are both well-formed and ​ ​ ​ $\sqrt{x^2} = x$ ​ if and only if ​ $0\leq x$ ​ , ​ ​ ​ so testing inequality reduces to your problem. ​ ​ ​ ​ ​ ​ ​ I'm not aware of any better upper bound for testing inequalities of sums-of-square-roots than this paper, which puts it in the counting hierarchy.

Bounty Ended with 50 reputation awarded by Mees de Vries
Source Link
user12859
user12859

Yes. ​ By the real-number analogue of the Tseytin transformation, that
reduces to the existential theory of the reals, which is in PSPACE by

page 291 and the bottom of page 290 from this paper
and
the answers to this question

.


For all real numbers $x$, $\sqrt{x^2}$ and $x$ are both well-formed and ​ ​ ​ $\sqrt{x^2} = x$ ​ if and only if ​ $0\leq x$ ​ , ​ ​ ​ so testing inequality reduces to your problem. ​ ​ ​ ​ ​ ​ ​ I'm not aware of any better upper bound for testing inequalities of sums-of-square-roots than this paper, which puts it in the counting hierarchy.