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).
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.
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.
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...
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).
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.
Please let P=NP, Please let P=NP
Whomever is running this simulation, please.
It's math, the result shouldn't be different just because it's a different sim.
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.
Well if the fundamental constants or hidden variables of the universe are shifting because of his comment then it can change the outcome.
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
unless mechanism behind our universe dynamically alters our logic on the fly to be artificially self-consistent
Why?
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.
9 replies →