Tag Info

4

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 ...

3

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 ...

1

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