[nayuki]

> 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]

except factorisation is stupid easy

[andrewflnr]

Go ahead and start cracking RSA keys, then.

[DoctorOetker]

careful what you wish for

[andrewflnr]

Oh 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]

this 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]

Big talk for someone who isn't casually factoring 2048-bit RSA keys as easily as multiplying them.