Weird edge case: What if the simulation hypothesis is true? Do we resolve this based on the physics we are simulated on, or based on the physics of the operators?

@Elspeth If you mean physics doesn’t change p!=np doesn’t change based on physics I agree. I think King might consider changing the title, but this question isn't about mathematically 'rigorous' polinomial time. It's more of a physics + complexity question. If you meant something else I did not understand.

But of course if those laws somehow allow us to access the universe one step above to perform computation, then that counts.

@TassiloNeubauer With any other answer I'd be worried about our ability to know for sure. Maybe quantum mechanics is so weird because it's a bug in the simulation? Can't prove it either way. I want this market to actually be resolvable. :)

@IsaacKing Yeah seems like the right approach. It's more like at first I was answering this question based on math and now that physics is involved I need to be more careful.

@IsaacKing That's for YES, what about for NO - also a proof that it can't be done?

And based on your comments about quantum computers, it's clear the question isn't whether P = NP. It would be helpful to better specify what complexity class you're thinking of - e.g. BQP? Or does it depend on whether practical quantum computers have been built?

@jack Yeah, a proof that it can't be done.

With regards to quantum computers, I think I'm asking about whether BQP ⊇ NP. But this question also includes other physical phenomena that could potentially allow for rapid computation of NP-complete problems.

@IsaacKing How can you ever prove that there are *no* physical phenomena like that? You can prove it under the known laws of physics, but what if there are laws we don't know about?

Hmm, this is a reasonable question to ask, but I don't think an impossibility proof that NP-complete problems cannot be solved with physical processes in polynomial time would be at all feasible.

@Yev Once we have a theory that explains all phenomena we've observed, I'll count that as good enough.

@jack Not sure about how other people think about this, but at least for me: p(this is possible with future engineering/this is possible given physics) p(we find a way to do this by 2200) are not that far apart, so maybe just resolve no by then?

@TassiloNeubauer I like the idea of creating a market with that criteria instead but I disagree that they have similar probabilities. I wouldn't be terribly surprised if the problem remains open for centuries, considering other similar mathematical problems.

I'm drafting a market, what do you think of something like this:

Resolves YES if by 2200 humanity has the demonstrated capability to solve all instances of all NP problems in polynomial time, with error probability bounded by a constant. Otherwise resolves NO. Because this criteria may be somewhat subjective, the resolution will be based on expert consensus.

Any method of computation is allowed for this question, as long as humans can actually do it practically and at reasonable scale. E.g. factorization is not considered solvable in polynomial time today because quantum computers can only do it on toy demonstrations today.

Any method of computation is allowed for this question, as long as humans can actually do it practically and at reasonable scale. E.g. factorization is not considered solvable in polynomial time today because quantum computers can only do it on toy demonstrations today.

Hm... yeah if you don't count factorization as solved then I agree the probabilities are different. I was more thinking about whether we would find any physics hack that would allow solving NP-complete problems even in principle.

I wouldn't be terribly surprised if the problem remains open for centuries, considering other similar mathematical problems.

Well, heuristics are provably strictly more powerful when trying to be right. Just because there is no proof, I don't believe we cannot be confident in the conjecture. I'd be terribly surprised if the outcome would be that P=NP after all. Even if there is no proof by 2200, I'd say there is a 99.9 percent chance that we have identified the correct outcome, with 99.99% confidence something along those lines.

@TassiloNeubauer Here's the link to the paper about [logical induction](https://arxiv.org/abs/1609.03543) hope the link works this time.

@TassiloNeubauer I shouldn't say strictly since if P=NP, everything I think I know is out the window anyway.

@TassiloNeubauer Ok, yeah, your question formulation is definitely different than mine and I like that one as well.

Well, heuristics are provably strictly more powerful when trying to be right. Just because there is no proof, I don't believe we cannot be confident in the conjecture. I'd be terribly surprised if the outcome would be that P=NP after all. Even if there is no proof by 2200, I'd say there is a 99.9 percent chance that we have identified the correct outcome, with 99.99% confidence something along those lines.

I'm not sure I understand what your claim is here. I agree that we can be pretty confident P != NP today (hence why I've bet a lot of NO here). But if the problem is unsolved in 2200, that by itself doesn't mean we should update up or down - it depends on what evidence the future research provides one way or another. One could imagine a scenario where our future knowledge of complexity theory leads us to believe P = NP is probably true but we haven't actually found an algorithm for it yet (similar to how we can conjecture that matrix multiplication is ~n^2)

I'm not sure I understand what your claim is here.

The argument is: I currently am 99.9% sure that NP!=P. IF that is true, I expect us to gather more and more evidence for this being true (so future me will be even more confident). In the worlds where this is false, my estimates of what future me thinks are all over the place. Like maybe most evidence of this would just be using AI to prove this, Mostly just very confused about that world.

For anyone wondering why this isn't higher due to Shor's algorithm: Integer factorization isn't NP-complete, we just don't know of a p-time algorithm for it.

Is it considered market manipulation on manifold if I tag markets like this as free money? Tagging them this way reflects my honest credence, but it also helps me out because I expect other people to vote on no faster, so I can cash out earlier.

A) Market manipulation is allowed.

B) I don't think "free money" is an appropriate tag for this market. "Free money" is for when nearly everyone agrees that a single result is near 100% to occur, not just for one user's subjective belief.

If you want to cash out faster, I'd recommend trying to convince other traders why NO is more likely, so that more people bet on it. You could also advertise the market to try and get more people betting on it.

There are NP-complete problems where most practical instances can be solved quickly. I guess that's not the spirit of the question, but consider making it a bit more specific.

@Sjlver Questions about computational complexity are always concerned about the asymptotic growth rate of the function, not early behavior for small inputs. If you limit yourself to a finite number of inputs, you can "solve" them in constant time with a lookup table.

@IsaacKing Not talking about small instances here, but "most practical instances". They often have a structure that can be exploited surprisingly well. For example, SAT solvers like z3 are very useful tools, even though the problem they attempt to solve is NP-complete in the general (often not relevant in practice) sense.

In this context, "solving" a problem in polynomial time means being able to solve *all* instances in polynomial time.

@Yev If quantum computing violates the complexity-theoretic Church–Turing thesis, this market could resolve to YES while that one resolves to NO.

Can NP-Complete problems be solved in polynomial time?, 8k, beautiful, illustration, trending on art station, picture of the day, epic composition