Love this :)
The only time such an argument had been yielded and has some value is in my (not so, I guess) humble opinion when I think Fermi used the argument that if there was a lower energy level of water there surely would have been an animal by now that used this extra energy by converting water to this state (although I cannot find a link to this quite so quickly, so perhaps the argument was slightly different).
But more notably, like Fermat's theorem, we can probably conclude that there's no easy quadratic or cubic algorithm for SAT that we've somehow missed. If P = NP, then, the most likely algorithm we'd see would be some hideous combinatorial algorithm that has a constant factor of 3^2^2^4 lurking in it that is completely impractical.
I think it's fair to assume that there are potentially asymptotic limits to what can be achieved, but it's not that we default to one conclusion or the other, but that we conclude that whatever might be the real solution, the complexity of the proof is insurmountable or doesn't exist.
P doesn't mean fast, it means polynomial.
A runtime of O(n + a) is polynomial (and just O(n)!), but with a big enough "a" (e.g. 2^999999999999999999999999999999999) it's likely large enough to be practically non-commutable.
I.e. there are "practically non-commutable" polynomial algorithm.
So the idea "there is not proof because we should have found it else wise" is deeply flawed.
I get that problems can have constant/linear/polynomial/exponential complexity to solve so I (think) I understand ‘P’.
Over at NP I get confused around what constitutes a test/validating that a solution is true in polynomial time.
For example, a problem, “what’s the shortest path between two points” I get that a brute force breadth-depth first algorithm is going to rapidly take longer as more branches are added, but what constitutes verifying the solution?
In that example does verifying a solution mean having access to some prior list of all possible permutations and sorting them to find the shortest path, and because sorting is easy then this is an example of easily verifying?
The general process to convert a function problem of "find the best X for this input" to a decision problem is to recast it as "is there an X better than k for this input?" So the validation in these cases means finding that a) the claimed X is actually an X on the input (e.g., a sequence of nodes to visit is actually a valid path in the first place), and b) you can measure the property of X you're trying to optimize (e.g., what is the total cost of the path).
Another way to think of it--one which actually illuminates the underlying proofs a bit better--is that NP is a nondeterministic class. Basically, this means that any problem in NP [in the fuzzy sense] can be thought of as a polynomial-time algorithm, but every time we have to make a "choice" of some kind (which node to pick next, which color to assign it, etc.), we can ask a magic oracle which tells us the correct answer in O(1) time.
Just to add to this: This can obviously also be brought back to "find the shortest path", by just asking the question again and again for smaller and smaller k, by halving.
P are the problems that we can create an answer to 'quickly'.
The question is, if we are able to verify an answer quickly, does that imply we can also always create an answer quickly? It feels like obvious not the case, but we can't prove it either way.
It's in NP because given a sudoku problem instance (a n by n grid with only some clues filled in) and a proposed solution (a n by n grid with all the squares filled in) you can check if the solution is correct in polynomial time. That is, you check that each square in the problem is equal to the square in the solution, and you check the rows/columns/larger-squares to see if they each contain the values (1..n).
So a problem X is in NP if given a polynomial-sized certificate C, you can run a polynomial-time algorithm C_Check() to see if it is actually a valid solution. In the sudoku problem:
X is Sudoku with instance x
C is the proposed solved sudoku
C_Check(x, C) is the algorithm where you check the rows/columns/larger-squares and you check that for every square in X[i][j] that is filled, C[i][j] == X[i][j]
In a normal breadth first search, where there are a polynomial # of vertices, you actually don't even need to use C until the very end. You're allowed to say
X is ShortestPathProblem with instance x
C is the proposed shortest path
C_Check(x, C) is just (BFS(x) == C)
So therefore any problem in P is automatically in NP.
An email address that works for me is in my profile.
Of course, if I had a polynomial-time solver for the "cost <= X?" query, I could easily create a polynomial time solver for the cost of the shortest path, using binary search.
See Decision Problem: https://en.wikipedia.org/wiki/Decision_problem
Switching to the decision version: "Is there a path of length at most L between the two points?"
To verify a "yes" answer, you get a path; and you just verify that it's short enough and goes from the first point to the second; that's it.
Obviously this verification doesn't work for a "no" answer.
Both are enjoyable reads.
> (P!=NP) In my opinion this shouldn’t really be a hard problem; it’s just that we came late to this theory, and haven’t yet developed any techniques for proving computations to be hard. Eventually, it will just be a footnote in the books.
... Anyway, awesome pun!
[Not equal]: 50
In fact there is a known and fairly simple algorithm that provably solves SAT, but its running time is unknown. It runs in P-time if and only if P=NP. It is called Levin's Universal Search and you can read about it.
Assuming it's a proof, there's two cases:
1) it's really P=NP, but we can't prove it
2) it's really P!=NP, but we can't prove it
If it's case 1, that's impossible. If P=NP, then there exist polytime algorithms for NP-Complete problems, and any of those algorithms are a proof that P=NP. So that's a contradiction.
So the _only_ possibility given a proof that it's unprovable would be case 2, thus proving P!=NP and contradicting itself.
Am I missing something? Even assuming I'm right, this isn't a proof that one of P=NP or P!=NP are provable, just that it's impossible to prove that neither can be proven.
 Assuming ZFC is itself consistent
That would mean that in ZFC+A there exist algorithms that can't exist in ZFC+B? Hard for me to imagine what those would even be, since they'd have to be representable in ZFC itself anyway, right, since that's all that an algorithm would be this model, a particular Turing machine?
But (I think) all of them have to do with infinity in some weird way.
Why not SAT? There's a $200,000 bounty paid out every ten minutes for solutions to a well-known SAT problem.
Or crypto. Math. Chess.
I don't think I would describe SHA256 prefix matching as "a well-known SAT problem".
I'm not sure I follow -- do you mean there is a challenge open somewhere which pays 200k$?
Short the hell out of bitcoin.