upvote

points

by manquer23 hours ago |
comments
upvoteby m_mueller22 hours ago|
next
[-]
wait, maybe this is the same problem....

with non-polynomial side being represented as the frontend programmer's constant need for more performance to do the same task...

reply
upvoteby mswphd19 hours ago|
parent|
next
[-]
worth mentioning that "NP" is not "non-polynomial" but "non-deterministic polynomial (time)". If NP was non-polynomial time then NP != P would be trivial (and in fact, P != EXP is known by the time hierarchy theorem).

Non-deterministic can be explained in several ways. One is in terms of a hypothetical "nondeterministic Turing machine" with certain non-physically realizable properties. The easier way is that a NP problem gets as input not only the problem instance x, but a "witness" w, that may depend on the problem instance. This witness generally makes the problem of deciding the problem instance straightforward (e.g. for SAT, x is the SAT instance, and w is a description of how to set the variables so that it is true).

reply
upvoteby sebzim45008 hours ago|
parent|
[-]
I reckon I could tell you in polynomial time whether a div was vertically centered, not sure if I could write the CSS in polynomial time.
reply
upvoteby 21 hours ago|
parent|
prev|
[-]
deleted
reply
upvoteby echelon21 hours ago|
prev|
[-]
Please let P=NP, Please let P=NP

Whomever is running this simulation, please.

reply
upvoteby osti21 hours ago|
parent|
next
[-]
It's math, the result shouldn't be different just because it's a different sim.
reply
upvoteby qarl5 hours ago|
parent|
next
[-]
To be fair - there are statements in math that are independent of the axioms. For those statements, the universe you find yourself in can pick either version (true OR false) and still be consistent.

See also: noneuclidian geometry and axiom of choice.

reply
upvoteby mertyildiran19 hours ago|
parent|
prev|
next
[-]
Well if the fundamental constants or hidden variables of the universe are shifting because of his comment then it can change the outcome.
reply
upvoteby brookst19 hours ago|
parent|
prev|
next
[-]
Depends how fundamental the variables are. If we can code a sim for a topos[1], why can’t we be in such a sim?

1. https://arxiv.org/pdf/1012.5647

reply
upvoteby NooneAtAll38 hours ago|
parent|
prev|
[-]
unless mechanism behind our universe dynamically alters our logic on the fly to be artificially self-consistent
reply
upvoteby sm-silversight20 hours ago|
parent|
prev|
[-]
Why?
reply
upvoteby adrianN20 hours ago|
parent|
[-]
Being able to solve NP hard optimization problems would enable progress in many areas of science and technology. For example it would allow us to find poly-sized Lean proofs for theorems efficiently, since proof verification can be done in polynomial time.

It would also be amusing to annihilate nearly six decades of proofs that assume P!=NP.

reply
upvoteby black_knight18 hours ago|
parent|
next
[-]
Leans proof checker is not polynomial time, unfortunately. It is super exponential. Basically, because it can verify the result of any function it can prove to be total.
reply
upvoteby sebzim450010 hours ago|
parent|
next
[-]
That's fine, we just change the problem from "find a lean proof of length < f(n)" to "find a lean proof that can be validated in time < f(n)".
reply
upvoteby adrianN16 hours ago|
parent|
prev|
[-]
Oh that’s unfortunate.
reply
upvoteby manquer19 hours ago|
parent|
prev|
next
[-]
Could also break the basic principles underlying most encryption approaches. I would rather have my bank account not stolen and internet working
reply
upvoteby mswphd18 hours ago|
parent|
next
[-]
to depress you even more, it is consistent with everything that we know that P != NP and that cryptography does not exist. So there is a worst of both worlds, and we cannot rule it out.
reply
upvoteby echelon19 hours ago|
parent|
prev|
[-]
I've had enough Internet for one lifetime.

As long as we also get low order polynomial solutions to important problems, it'll be worth it.

Besides, unencrypted wifi was funny.

reply
upvoteby charcircuit19 hours ago|
parent|
prev|
[-]
Even if P=NP it doesn't mean that the P approach will be better than the heuristic approach we already do today.
reply
upvoteby adrianN19 hours ago|
parent|
[-]
Of course, if we get ridiculous polynomials it doesn't mean much in practice. People who hope for P=NP generally hope for nice polynomials O(n^3) or something like that at worst.
reply