Can NP-complete problems be solved in polynomial time?
5%
chance

Sort by:
TassiloNeubauer avatar
Tassilo Neubauer
is predicting NO at 4%

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 avatar

@TassiloNeubauer It doesn't seem to me that this changes the mathematics of the situation.

TassiloNeubauer avatar
Tassilo Neubauer
is predicting NO at 4%

@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.

IsaacKing avatar
Isaac King
is predicting YES at 4%

@TassiloNeubauer Resolves based on the laws of our universe.

IsaacKing avatar
Isaac King
is predicting YES at 4%

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

TassiloNeubauer avatar
Tassilo Neubauer
sold Ṁ398 of NO

@IsaacKing Unironically seems like a good reason to sell no.

TassiloNeubauer avatar

@TassiloNeubauer I wouldn't bet on US implementing a bugfree universe.

IsaacKing avatar
Isaac King
sold Ṁ11 of YES

@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. :)

TassiloNeubauer avatar

@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 avatar
Isaac King
is predicting YES at 5%

@TassiloNeubauer For the pure math question I think you want my other market:

jack avatar
Jack
is predicting NO at 5%

What are the resolution criteria?

IsaacKing avatar
Isaac King
bought Ṁ50 of YES

@jack A proof it can be done.

jack avatar
Jack
bought Ṁ2,000 of NO

@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?

IsaacKing avatar
Isaac King
bought Ṁ7 of YES

@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.

Yev avatar

@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?

jack avatar
Jack
is predicting NO at 3%

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.

IsaacKing avatar
Isaac King
is predicting YES at 3%

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

TassiloNeubauer avatar
Tassilo Neubauer
is predicting NO at 3%

@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?

jack avatar
Jack
is predicting NO at 3%

@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.

TassiloNeubauer avatar
Tassilo Neubauer
is predicting NO at 3%

@jack

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 avatar
Tassilo Neubauer
is predicting NO at 3%

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

TassiloNeubauer avatar
Tassilo Neubauer
is predicting NO at 3%

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

jack avatar
Jack
is predicting NO at 4%

@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)

TassiloNeubauer avatar
Tassilo Neubauer
is predicting NO at 4%

@jack

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.

jack avatar
Jack
is predicting NO at 4%

Created a market with the criteria I proposed above

IsaacKing avatar
Isaac King
bought Ṁ10 of YES

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.

jack avatar
Jack
is predicting NO at 5%
TassiloNeubauer avatar
Tassilo Neubauer
bought Ṁ100 of NO

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.

IsaacKing avatar

@TassiloNeubauer

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.

Sjlver avatar
Sjlver
bought Ṁ95 of NO

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.

IsaacKing avatar

@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.

Sjlver avatar

@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.

jack avatar

@Sjlver I think it's clear from context that this question is referring to worst-case complexity.

jack avatar
Jack
bought Ṁ1,000 of NO

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

ManifoldDream avatar

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

IsaacKing avatar

Related (but not equivalent!):

Yev avatar

@IsaacKing How are these markets different?

IsaacKing avatar

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