Hacker News Reader

Comment by DevelopingElk | Hacker News Reader

His claim is that we exp-minus-log cannot compute the root of an arbitrary quintic. If you consider the root of an arbitrary quintic "elementary" the exp-minus-log can't represent all elementary functions.

I think it really comes down to what set of functions you are calling "elementary".

View on HN

The author discusses this in his third paragraph, and states explicitly in his fourth that he considers the result faulty for its unrealistically narrow definition of elementarity.

(I'm not a mathematician, so don't expect me to have an opinion as far as that goes. But the author also writes well in English, and that language we do share.)

Well the author saysin that paragraph:

> In layman’s terms, I do not consider the “Exp-Minus-Log” function to be the continuous analog of the Boolean NAND gate or the universal quantum CCNOT/CSWAP gates.

But is there actually a combination of NANDs that find the roots of an arbitrary quintic? I always thought the answer was no but admittedly this is above my math level.

Combinations of the NAND gate can express any Boolean function. The Toffoli (CCNOT) or Fredkin (CSWAP) can express any reversible Boolean function, which is important in quantum computing where all gates must be unitary (and therefore reversible). The posited analog is that EML would be the "universal operator" for continuous functions.

Solving polynomials over finite fields is trivial. Just try all combinations.

You probably want a fast algorithm.

Compare https://arxiv.org/abs/1108.1791 and why computational complexity is often more interesting that computability.

Sure, i guess i should have said something like with a polynomial circuit size or something.

However by the same token couldn't you use the same brute force approach with exp minus log?

What im really asking, are NAND gates really different here?

How can you brute force real numbers?

I meant for finite fields like the person i was responding to said.

Yes, NAND gates can implement root finding algorithms for arbitrary polynomials. For example a variant of Newton’s method can be used (there are also better algorithms for circuits specifically).

This can be done in polynomial time as well.

This is fairly obvious if you think about that your computer can do the same thing and it’s just a fancy circuit.

Surely you can use EML to do root finding approximations also.

Reply on news.ycombinator.com