3 ms·

I don't see how it could be unprovable. As far as I know the only way a theorem can be unprovable is if it makes statements involving infinity. You can reduce

I don't see how it could be unprovable. 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.

contravariant 9y ago
>enumerating all possible algorithms [...] for problem sizes up to n. 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.
ColinWright 9y ago
> I don't see how it could be unprovable. 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.
- tgflynn 9y ago
  Say you let n be a number equal to all of the memory bits that currently exist on Earth then showed that the size of the smallest boolean circuit solving 3SAT for variable counts near n scaled as 2^n. 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.
  - pavel_lishin 9y ago
    > It would be true for all practical purposes. But that's not how mathematical proofs work.
  - ColinWright 9y ago
    You're talking about something completely different. If you don't care about asymptotic behavior that's one thing, but you do need to recognise that you're talking about something different, and unless you are really clear and really precise you won't be able to communicate effectively with other people, even if what you say is relevant and important. But bottom line is that you're talking about something different.

contravariant 9y ago

>enumerating all possible algorithms [...] for problem sizes up to n. 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.

ColinWright 9y ago

> I don't see how it could be unprovable. 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.

tgflynn 9y ago
Say you let n be a number equal to all of the memory bits that currently exist on Earth then showed that the size of the smallest boolean circuit solving 3SAT for variable counts near n scaled as 2^n. 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.
- pavel_lishin 9y ago
  > It would be true for all practical purposes. But that's not how mathematical proofs work.
- ColinWright 9y ago
  You're talking about something completely different. If you don't care about asymptotic behavior that's one thing, but you do need to recognise that you're talking about something different, and unless you are really clear and really precise you won't be able to communicate effectively with other people, even if what you say is relevant and important. But bottom line is that you're talking about something different.