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).
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.
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.
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?
Re:Markets are efficient if and only if P=NP (2010)
by FeepingCreature on Sunday October 25, 2020 @02:08PM
(#24888450)
Yes.