News for hackers. Stuff that matters.

A comment on Markets are efficient if and only if P=NP (2010). Parent comment

Re:Markets are efficient if and only if P=NP (2010) by hansvm on Wednesday October 21, 2020 @02:30AM (#24845265)
There'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.

[ Parent | on HN ]
Re:Markets are efficient if and only if P=NP (2010) by adamnemecek on Wednesday October 21, 2020 @10:28AM (#24848199)
How can you calculate Fourier in O(1) if the input is bound?
[ Parent | on HN ]
Re:Markets are efficient if and only if P=NP (2010) by beervirus on Wednesday October 21, 2020 @03:26PM (#24851138)
If the input maxes out at 64 bits, then calculating the Fourier transform is O(64), which is O(1).
[ Parent | on HN ]
Re:Markets are efficient if and only if P=NP (2010) by adamnemecek on Wednesday October 21, 2020 @06:57PM (#24853192)
I don't follow.
[ Parent | on HN ]
Re:Markets are efficient if and only if P=NP (2010) by beervirus on Wednesday October 21, 2020 @10:58PM (#24854481)
O(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).
[ Parent | on HN ]
Re:Markets are efficient if and only if P=NP (2010) by adamnemecek on Wednesday October 21, 2020 @11:46PM (#24854682)
I understand big O however Fourier bio O runtime is bound by the length of the signal, not by maximum value of the signal.
[ Parent | on HN ]
Re:Markets are efficient if and only if P=NP (2010) by hansvm on Thursday October 22, 2020 @11:59AM (#24859428)
The photonic processor in question can only process some maximum M number of bits worth of signal in a given time T though. To have a throughput of better than M/T you need more time or more/better processors (i.e., for large enough inputs the runtime isn't actually O(1) ).

What I was pointing out is that digital implementations have this exact same property -- if the input is bounded in the sense that there are a maximum number of bits being fed into your digital computer then the maximum runtime is a constant equal to the maximum runtime for any of those finite inputs -- i.e., the runtime is O(1) for the inputs you're actually able to provide (the exact same inputs you could provide to the photonic processor to achieve a constant-time Fourier transform). To scale up beyond that threshold you still need more time or more/better processors.

[ Parent | on HN ]
Re:Markets are efficient if and only if P=NP (2010) by adamnemecek on Thursday October 22, 2020 @12:38PM (#24859943)
Are we talking about analog computers?
[ Parent | on HN ]
Re:Markets are efficient if and only if P=NP (2010) by FeepingCreature on Sunday October 25, 2020 @02:08PM (#24888450)
Yes.
[ Parent | on HN ]