I have to say the two proposed forms at the start of the post seem uncharacteristically poor–sort of meaningless when you try to implement them. I would have thought your first try would have been Jesus’s “Do unto others as you would have them do unto you.” (Doesn’t work for sado-masochists though.)

Personally, I vote for Bill & Ted’s “Be excellent to each other.”

]]>Can you tell me if quantum state separability is in NP? I’d think it is since it’s like proving that a number is composite by showing the factors, but maybe I miss something. Wikipedia only says it’s NP-hard rather than NP-complete.

]]>https://www.scottaaronson.com/democritus/lec9.html

you mention “modeling the stock market” as an example of an NP-complete problem. But I thought the stock market is modelled very well by Brownian motion, aka the Wiener process. That’s completely stochastic, so if you meant -predicting- the stock market, that’s not computable much less in NP. Did you have something else in mind?

]]>Yes, you could argue that QC does slightly decrease the motivation for the specific question P vs. NP—since even if P≠NP, the question we *now* need to ask, if we want to know whether we get the world-changing consequences that flow from all NP problems being efficiently solvable, is whether NP is contained in BQP.

On the other hand, even before QC, I personally feel like the right way to think about P vs. NP was simply as the *flagship* for dozens of questions about the limits of efficient computation, none of which we currently know how to answer, and all of which seem to be hard for similar reasons. For starters, there’s P vs. PSPACE, NP vs. coNP, NP vs. P/poly, P vs. P^{#P}, the existence of one-way functions…

And I’d claim that, not only has QC not decreased the importance of this general class of questions, it’s significantly *increased* its importance, since now we know that these same questions are also bound up with the question of whether Nature can be efficiently simulated using digital computers.

Does the QC model weaken that sense of robustness and perhaps make P seem less important? Thanks.

]]>