3 ms·
No, it's possible that there is a P-time SAT-solving algorithm A, but that it's not provable that A runs in P-time, and/or it's not provable that A actually sol
by throwaway81523 5y ago
No, it's possible that there is a P-time SAT-solving algorithm A, but that it's not provable that A runs in P-time, and/or it's not provable that A actually solves SAT (even though it does).
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.