New answers tagged

4

As proved in this paper: http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-get.cgi/1991/CS/CS0699.revised.pdf If P != NP can be shown to be independent of Peano Arithmetic, then NP has extremely-close-to-polynomial deterministic time upper bounds. In particular, in such a case, there is a DTIME(n^1og*(n)) algorithm that computes SAT correctly on ...


Top 50 recent answers are included