5 ms·
P==PN on analog photonic machines. A light prism calculates Fourier in O(1) (given a prism is not aware of Big O). Using Fourier, one can factorize a number in
by adamnemecek 6y ago
P==PN on analog photonic machines. A light prism calculates Fourier in O(1) (given a prism is not aware of Big O). Using Fourier, one can factorize a number in O(1), and then solve NP in P.
- FeepingCreature 6y agoPhotons are discrete.
- adamnemecek 6y agoWhat's your point?
- FeepingCreature 6y agoYou cannot do continuous computation with discrete components.
- beervirus 6y agoWhatever you're encoding into the light that gets shined on the prism... that process is probably not gonna be O(1).
- adamnemecek 6y agoIt's not, no. Whats your point? The factorization step is still O(1).
- beervirus 6y agoYou can't factorize a number in O(1) if it takes O(n) or whatever to set up the problem. Everything is O(1) if you can ignore steps.
- adamnemecek 6y agoI don't think you understand my point.
- beervirus 6y agoAnd I’m quite sure you don’t understand mine.
- hansvm 6y agoThere's a limited amount of information in the signal to a photonic machine of a given size though. If the inputs are bounded in some sense then a digital computer can calculate Fourier in O(1) too. That doesn't make the problem any easier asymptotically -- you still need more machine or more time to calculate arbitrary Fourier. That said, recent work on photonic Fourier transforms does look interesting from the perspective of a co-processor. They offer meaningful gains over alternatives.
- adamnemecek 6y agoHow can you calculate Fourier in O(1) if the input is bound?
- beervirus 6y agoIf the input maxes out at 64 bits, then calculating the Fourier transform is O(64), which is O(1).
- adamnemecek 6y agoI don't follow.
- beervirus 6y agoO(whatever) refers to the asymptotic behavior as n gets arbitrarily large. If n is bounded, big O notation doesn’t really mean anything because everything is O(1).
- adamnemecek 6y agoI understand big O however Fourier bio O runtime is bound by the length of the signal, not by maximum value of the signal.
- hansvm 6y ago