3 ms·
That explanation is by definition. The perspective given in the video is about encoding NP problems as satisfiability problem and then solving these efficiently
by RGamma 2y ago
That explanation is by definition. The perspective given in the video is about encoding NP problems as satisfiability problem and then solving these efficiently if P=NP. A corollary is that by suitably constraining the output of such instances a (practical) PTIME SAT solver would efficiently invert hash functions or any other circuit, breaking cryptography.