4 ms·
> Synthesis is harder than analysis Taking this statement at face value, it means something in computer science: computing an answer (synthesis) is currently b
by nayuki 3mo ago
> Synthesis is harder than analysis
Taking this statement at face value, it means something in computer science: computing an answer (synthesis) is currently believed to be harder than checking an answer (analysis).
The simplest example to illustrate the claim is that factoring a number is harder than multiplying the two factors to check that it equals the original number, or even to decide whether the original is prime or composite (but without yielding the factors).
This also cuts to the heart of what NP means - it means that the answer to a yes/no problem about binary strings can be checked in polynomial time. It doesn't give a recipe for how to generate the answer, but it is implied that finding an answer can take up to exponential time and no more.
- DoctorOetker 3mo agoexcept factorisation is stupid easy
- andrewflnr 3mo agoGo ahead and start cracking RSA keys, then.
- DoctorOetker 3mo agocareful what you wish for
- andrewflnr 3mo agoOh please. Do it then. It's just as easy as multiplication, right? Because otherwise it wouldn't have made any sense to bring it up. So go for it. If you don't want to be evil and MitM online banking sessions, publish the algorithm and collect your Turing award at your earliest convenience. Unless, perhaps, it is a bit harder, as said in the post you first responded to.
- DoctorOetker 3mo agothis assumes a Turing award to be the highest possible reward, and ignores that a non-insignificant fraction of contributors are driven by a sense of justice and concomittant need to grab power, the reward you describe is inferior to the reward I ogle to grab.
- andrewflnr 3mo agoBig talk for someone who isn't casually factoring 2048-bit RSA keys as easily as multiplying them.