Can NP-complete problems be solved in polynomial time?
30
129
670
2200
5%
chance

Resolves YES if it is theoretically possible to solve all NP problems in worst-case polynomial time, with error probability bounded by a constant. Resolves NO once that is known to be impossible.

If you know a bit about complexity theory: this means it is not necessary that P = NP. BPP = NP (randomized algorithms with constant error probability) would be sufficient, and BQP = NP (quantum algorithms) would also be sufficient if the relevant algorithms could actually be run practically on quantum computers. Other methods could also be sufficient if they meet the resolution criteria.

Any method of computation is allowed for this question, as long as it could in theory be physically implimented in the real universe.

Description mostly copied from Jack's question.

Get Ṁ1,000 play money
Sort by:

With error probability bounded by a constant.

I am probably wrong but, isn’t it easy if the constant is high ?

@dionisos The constant is implicitly less than 1/2.

bought Ṁ15 of YES

A little over half of the claimed proofs listed on https://www.win.tue.nl/~wscor/woeginger/P-versus-NP.htm are in favor of P = NP.

Also I think P vs. NP (or similar questions) will be very, very important to the future of computer science (c.f. AI vs. crypto), so I'm subsidizing this market with M$100.

FYI Don Knuth expects p=np

predicts YES

@LinaWolski Well, Don Knuth is welcome to come bet in this market. :)

bought Ṁ1 of NO

@LinaWolski It's an interesting thought, but I wonder if he would support this on reflection. There are tasks involving hash-functions (e.g. like SHA256 - but maybe with the length of the hash increasing with the size of the input, instead of being capped at 256 characters) that could be specially constructed to be in NP but not in P.

bought Ṁ10 of YES

Technically, they can, it's just not guaranteed. The very definition of NP-complete was, the "non-determinsitic" part, is that you can make a lucky guess and verify it. With the canonical Boolean Satisfiability for example, any SAT instance "can" be solved in polynomial time. It's just not guaranteed.

predicts NO

@RealityQuotient That's not what people mean by "solved in polynomial time". See my earlier comments about worst-case complexity.

predicts YES

@jack People usually say P =? NP (like in the brickwork of the Princeton Comp Sci department) or P = NP? specifically to avoid this ambiguity. The N literally means that the problem, if solvable, can be solved in Polynomial time.

My $10M bet isn't on whether or not P =? nP, but on whether or not Isaac will resolve the market based on the question.

predicts YES

@RealityQuotient You should sell that M$10. :)

predicts YES

@RealityQuotient How would you recommend I change the title and/or description in order to clear up any potential ambiguity?

sold Ṁ11 of YES

@IsaacKing Sold, at a small profit.

"Does P = NP?"

predicts NO

I don't think P = NP? is the same question.

For example, being able to solve with quantum computers and randomness would be a reasonable avenue to YES. (i.e. BQP = NP + building quantum computers)

See my own question:

predicts NO

The language I use in my resolution criteria to clear up this ambiguity about easy instances is "solve all NP problems in worst-case polynomial time, with error probability bounded by a constant."

@jack I'm good with that wording.

predicts YES

@RealityQuotient That is indeed not the same question. I have a market on that question here.

I've updated the description to use Jack's wording, thank you Jack.

predicts NO

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?

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

predicts NO

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

predicts YES

@TassiloNeubauer Resolves based on the laws of our universe.

predicts YES

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

sold Ṁ398 of NO

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

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

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

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

predicts YES

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

More related questions