I've been convinced P!=NP ever since I started studying semigroup lower bounds. Even black box group membership is exponential in the largest prime less than or equal to N. https://oeis.org/A186202
There is a sense in which any complexity class which is self-low is "physical", or analogous to machines which we might build by hand with modular designs. A self-low class doesn't gain any additional power when relativized with itself as an oracle, and this directly corresponds to building a physical machine out of smaller machine modules.
We know that P is self-low. It seems that the universe insists that either we are able to build machines which tractably solve NP-complete problems, or not, but there is no in-between position.
You can add new axioms to an existing axiom set that can be semi-decidably proved inconsistent given the rest of the axiom set.
https://en.wikipedia.org/wiki/Large_cardinal https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_...
For a theory of how to choose an axiom set probabilistically, see: https://intelligence.org/2016/09/12/new-paper-logical-induct...
But, demonstrating an axiom is inconsistent with the standard model of peano arithmetic or ZFC is in the general case uncomputable.
For example, an axiom that claims some program halts when it does not actually halt cannot in general be proved to be inconsistent wrt the standard model, because otherwise one could decide the halting problem.
One reason I believe P!=NP is I can imagine what a proof of P=NP would look like -- just write a C program that solves SAT or Sudoku or something, in polynomial time, and prove it's correctness and execution time. There are tens of thousands of papers which do that, for various problems.
I can't really imagine what a proof of P!=NP would look like, proving something doesn't exist is extremely hard, particularly because for any particular instance of an NP problem, there is a problem which solves it "by luck".
Is it possible to prove that something is not provable?
It's possible to prove that something is not provable within some axiom set. See: https://en.wikipedia.org/wiki/List_of_statements_independent...
[1]: https://math.stackexchange.com/questions/2027182/how-do-we-p...
As far as I know the only way a theorem can be unprovable is if it makes statements involving infinity.
You can reduce P vs NP to a question involving only finite sets by choosing some finite n, which can be arbitrarily large. It should be large enough so that the asymptotic behavior of any algorithm would dominate at n.
Instead of asking about the scaling behavior of an algorithm as n approaches infinity you now ask about its scaling up to the finite value n.
This is now a question about a finite set which has a definite answer which could, in principle, be determined by enumerating all possible algorithms (represented, for example, by boolean circuits with some large size bound) for a particular NP complete problem for problem sizes up to n. Of course this would probably take many times the lifetime of the universe to actually do, but it could be done in principle. So the question of how the minimum circuit size which solves an NP complete problem scales with n has a definite answer.
It's quite plausible that it's unprovable, although you would have to be specific about the axiom system you're using.
> As far as I know the only way a theorem can be unprovable is if it makes statements involving infinity.
It does.
> You can reduce P vs NP to a question involving only finite sets by choosing some finite n, which can be arbitrarily large. It should be large enough so that the asymptotic behavior of any algorithm would dominate at n.
No, you can't. You don't know how large that n has to be, so you have to prove it for arbitrarily large n, and that's the "infinity" that you're dismissing.
> Instead of asking about the scaling behavior of an algorithm as n approaches infinity you now ask about its scaling up to the finite value n.
So you've changed the question to one that can be proven. The original question might still be unprovable.
So I don't see how your comment really makes any sense at all. Perhaps you could be a little more precise.
That would essentially be enough to convince me that P != NP.
It would be true for all practical purposes. In fact I would find the above information more interesting than the actual asymptotic behavior as n -> infinity.
But bottom line is that you're talking about something different.
But that's not how mathematical proofs work.
Please keep in mind that this includes an algorithm that has precomputed all possible solutions and retrieves their value from a list.
In fact I find it hard to say for certain that you can't for instance assume the existence of an algorithm that calculates the answers to some NP problem in constant time, but which takes an amount of time that can't be proven to be smaller than any other number. This would lead to a situation where P != NP may not be provable.
[1]: http://www.informit.com/articles/article.aspx?p=2213858
But if someone were to prove the opposite, the entire technology world would shift dramatically, so it will certainly help to have a proof for this.
Co-NP just seems so much harder than NP.
All these classes would turn out to be the same since P is closed under complement. Then NP would be as well and everything is equal.
That's why this result sometimes is called the collapse if the complexity hierarchy.