Skip to main content
Computer Science

Return to Question

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

Consider terms built from elements of $\mathbb Q$ and the operations $+,\times,-,/$, and $\sqrt[n]{\,\cdot\,}$ for each natural number $n$. Given the promise that two terms are well-formed -- that is, there is no division by zero, and no even roots of negative numbers -- is there an algorithm which decides when the two terms are equal?

A related question was posted herehere, but it is more general (as it allows arbitrary exponentiation, rather than just by rational numbers).

Consider terms built from elements of $\mathbb Q$ and the operations $+,\times,-,/$, and $\sqrt[n]{\,\cdot\,}$ for each natural number $n$. Given the promise that two terms are well-formed -- that is, there is no division by zero, and no even roots of negative numbers -- is there an algorithm which decides when the two terms are equal?

A related question was posted here, but it is more general (as it allows arbitrary exponentiation, rather than just by rational numbers).

Consider terms built from elements of $\mathbb Q$ and the operations $+,\times,-,/$, and $\sqrt[n]{\,\cdot\,}$ for each natural number $n$. Given the promise that two terms are well-formed -- that is, there is no division by zero, and no even roots of negative numbers -- is there an algorithm which decides when the two terms are equal?

A related question was posted here, but it is more general (as it allows arbitrary exponentiation, rather than just by rational numbers).

Notice removed Draw attention by Mees de Vries
Bounty Ended with user12859's answer chosen by Mees de Vries
Notice added Draw attention by Mees de Vries
Bounty Started worth 50 reputation by Mees de Vries
Tweeted twitter.com/StackCompSci/status/785355453526052864
Source Link
Mees de Vries
Mees de Vries
  • 353
  • 2
  • 16

Decidability of Equality of Radical Expressions

Consider terms built from elements of $\mathbb Q$ and the operations $+,\times,-,/$, and $\sqrt[n]{\,\cdot\,}$ for each natural number $n$. Given the promise that two terms are well-formed -- that is, there is no division by zero, and no even roots of negative numbers -- is there an algorithm which decides when the two terms are equal?

A related question was posted here, but it is more general (as it allows arbitrary exponentiation, rather than just by rational numbers).