3 ms·

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

by bawolff 7mo ago

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.

reikonomusha 7mo ago
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.
meindnoch 7mo ago
Solving polynomials over finite fields is trivial. Just try all combinations.
- eru 7mo ago
  You probably want a fast algorithm. Compare https://arxiv.org/abs/1108.1791 https://arxiv.org/abs/1108.1791 and why computational complexity is often more interesting that computability.
- bawolff 7mo ago
  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?
  - zeroonetwothree 7mo ago
    How can you brute force real numbers?
    - bawolff 7mo ago
      I meant for finite fields like the person i was responding to said.
zeroonetwothree 7mo ago
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.
- floxy 7mo ago
  Surely you can use EML to do root finding approximations also.

by bawolff 7mo ago

reikonomusha 7mo ago

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.

meindnoch 7mo ago

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

eru 7mo ago
You probably want a fast algorithm. Compare https://arxiv.org/abs/1108.1791 https://arxiv.org/abs/1108.1791 and why computational complexity is often more interesting that computability.
bawolff 7mo ago
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?
- zeroonetwothree 7mo ago
  How can you brute force real numbers?
  - bawolff 7mo ago
    I meant for finite fields like the person i was responding to said.

zeroonetwothree 7mo ago

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.

floxy 7mo ago
Surely you can use EML to do root finding approximations also.