4 ms·
It's not impossible to prove P==NP if that is the case as the program is the proof. Also if we assume "if P==NP then there exists program less than a trillion l
by YetAnotherNick 3y ago
It's not impossible to prove P==NP if that is the case as the program is the proof. Also if we assume "if P==NP then there exists program less than a trillion lines" then P!=NP is provable if that is the case.
- joe_the_user 3y agoExhibiting program that terminates in polynomial time for NP problem isn't sufficient to prove P==NP. You also need to actually prove the function terminates in polynomial time. And I could easily imagine that the general problem "does program P(X) terminate in time less than f(X)" is equivalent to the halting problem but in any case it's not at all guaranteed you could create such a proof.
- sterlind 3y agothe program isn't the proof. you have to prove that the program always gives the correct answer, and works inside some time bound. what if, say, it generates the Collatz sequence as a subroutine? good luck proving that the program is polynomial when we can't even prove that sequence always converges.