6 ms·
I think that P==NP, just not on Turing machines. A prism calculates Fourier in “O(1)” which can be used to factorize in “O(1)” and thereby solve NP in P.
by adamnemecek 6y ago
I think that P==NP, just not on Turing machines. A prism calculates Fourier in “O(1)” which can be used to factorize in “O(1)” and thereby solve NP in P.
- WJW 6y agoIf you want to think of prisms as calculating devices, isn't a prism technically a massively parallel device where all the molecules are a "core" of sorts? It still does at least O(N log N) work I think, it just all happens in parallel. You can also find the minimum element of a list in logarithmic time instead of linear time if you have enough parallelism available, even though finding the minimum element is O(N).
- bidirectional 6y agoWhat model of computation then? If you abandon Turing machines with their infinite memory, aren't you just in the land of lookup tables? I can model a prism and all possible ways light can hit it as a (intractably huge) dictionary, everything is O(1).
- adamnemecek 6y agoYou really aren’t in the land of lookup tables no.
- bidirectional 6y agoWhy not? I realise there are non-Turing complete models of computation that cannot be described by a lookup table (e.g. coinduction), but are they physically realisable?
- adamnemecek 6y agoAnyone who says anything besides “I don’t know” is lying.
- enkid 6y agoDoes a prism truly solve a Fourier in "O(1)" or is it so fast it seems to be "O(1)"?
- Sebb767 6y agoO(1) does not necessarily mean "fast". It could take 400 years and still be O(1), as long as it would take 400 years independent of the amount of light put in. O(1) just states that the computation time does not change depending on the input.
- heavenlyblue 6y agoPrism is not a Turing machine however. i.e. it's not a generalised computer. By that definition computers have AI because humans can communicate through them (i.e. connect a prism to do O(1) Furrier transform vs connect a human for computer to behave like human).
- adamnemecek 6y agoNo prism is not a Turing machine however it can be used as a building block of a computer to perform an expensive operation.
- teraflop 6y agoInteger factorization is not known to be NP-complete, so as far as we know, finding an efficient way to factor integers would not tell us anything about P vs. NP. Also, analog computation schemes tend to rapidly encounter fundamental physical limits. If calculating an N-bit result requires a measurement with N bits of precision, then adding one additional bit tends to require twice as much energy, or twice as big an apparatus, or something of the sort. So even if the "computation" itself looks as if it's O(1), your resource consumption is still exponential.
- jvanderbot 6y agoComputational complexity is intrinsically linked to the computational model. It's actually meaningless to say P or NP on anything other than a Turing machine.
- adamnemecek 6y agoHence the quotation marks.
- jvanderbot 6y agoThere aren't enough quotations in the universe to make that statement true. But the sentiment is not wrong. There are potentially new computing paradigms that are really good for things that our machines are really bad at. I've always been fascinated by analog computers (machines, really). The old firing solution computers for torpedoes are just precisely machined wheels and gears (TDC, it's called). But ultimately, for information exchange and transmission, it does seem nature selected for something that strangely appears to be Turing-like: DNA. Perhaps there's something to this Turing machine model after all? I find it interesting too, is all I'm saying.
- ravi-delia 6y agoThe problem with analog computers beating out 'Turing machines' is that they are equivalent to a Turing machine themselves. There's nothing special about binary beyond its usefulness in tiny circuits.
- adamnemecek 6y agoThey aren’t.
- ravi-delia 6y agoCould you perhaps elaborate?
- lisper 6y ago> A prism calculates Fourier in “O(1)” Only because the prism puts an upper bound on the size of the input. If you do that, every problem is O(1).
- tlb 6y agoSo does any physical computer. Modern computers push that limit into the billions or trillions, while optical interferometry machines are currently stuck in the hundreds or thousands. But you can't guarantee that won't change.
- lisper 6y ago> So does any physical computer. That's technically true, but it misses the point rather badly. The size of the problem that a prism can accept as input is constrained by the physical size of the prism. The size of the problem that a computer can accept as input is constrained only by time. So yes, technically, the universe will eventually undergo heat death and so the amount of time available is finite, but that's just not very interesting.
- adamnemecek 6y agoWhether or not it can be spread really depends on the representation you use.
- lisper 6y agoNo. Turing machines are universal. All Turing-complete models of computation are equivalent. The representation is irrelevant. That is the whole point of TMs. A TM can do the same computation as a prism, or any other physical system. The converse is not true. That is the reason TMs are a thing.
- adamnemecek 6y agoI wasn’t talking about Turing machines, I was talking about a hypothetical analog photonic computer.
- Strilanc 6y agoIt really doesn't. Sure the mathematical model you have of a prism might contain terms that the solution is encoded into, but these terms either a) require rapidly increasing effort to extract from the experiment as the computational problem grows or b) are precisely where the model is diverging from reality (e.g. assuming infinite precision despite physical fuzziness due to effects like finite temperatures and Heisenberg uncertainty).
- adamnemecek 6y agoInfinite or arbitrary precision?
- Strilanc 6y agoThe amount of precision actually required would depend on the size of the problem being solved. But I meant that the mathematical model you had in mind probably just used perfect real numbers without a notion of precision.
- adamnemecek 6y agoIt would not use those no.
- deleted 6y ago[deleted]
- ravi-delia 6y agoFactorization is very likely not NP-complete, so that particular example doesn't generalize to the rest of NP. In fact, any computer can solve an NP problem in P: Just pick a problem in P of your choice! Every problem in P is also in NP.
- sebastialonso 6y agoI think Aaronson himself addressed most of this criticism in the survey. Look under "The Kitchen-Sink Objection" and "The Mathematical Snobbery Objection".
- adamnemecek 6y agoUsage of Fourier in complexity theory still assumes that Fourier is O(n*log(n)).