New answers tagged


I'll start with your first question: If $P=NP$ was proven with an algorithm, would that have to mean that there is one algorithm that has to work for all inputs of length $n$? Yes, in order for $P$ to equal $NP$, there has to be one algorithm for all inputs. It can't be infinitely many algorithms that each solve some subset of the problem. For your more ...


You can think about this more informally: it takes time to access memory. For any algorithm, whether a Turing machine or using some other formalism, whenever it queries or modifies memory that takes a certain amount of time. Therefore, total space used by an algorithm (units of space accessed during execution) is always less than or equal to the time used by ...


Any turing machine with running time $O(T(n))$ for some function $T$, will have to use at most $O(T(n))$ cells on the tape, and hence will use at most $O(T(n))$ space. Therefore, the answer is that such an algorithm wouldn't even exist.

Top 50 recent answers are included