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.
1,000
3.00I believe that there are algorithm where we can spent S space and be able to solve any SAT problem with n variables in (1+1/S)^n time.
so it is still exponential time but we can increase S to reduce time into some reasonable value
if S is comparable with n then we can very quickly solve any SAT problem with n variables.
using simple hashmap which stores sat problems and its solutions will require exponential space, but i believe that there are some structure which can store solutions of all SAT problems with n variables by using polynomial space
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.
@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.
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.
@RealityQuotient That's not what people mean by "solved in polynomial time". See my earlier comments about worst-case complexity.
@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.
@RealityQuotient How would you recommend I change the title and/or description in order to clear up any potential ambiguity?
@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.
@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.
@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.