P=NP in Exponential Space?

87 views Asked by At

Suppose that we find that, for any NP-complete problem, there is an algorithm that can solve it in P time. However, the algorithm takes exponential space. For example, the algorithm to revert SHA256 would only take 256 steps. But you would need 2^256 bits to write the algorithm. Is the time complexity of this algorithm P? Would P equal NP?

The Clay Math Institute says that "Informally the class P is the class of decision problems solvable by some algorithm within a number of steps bounded by some fixed polynomial in the length of the input." It makes no limitations to the space taken by this algorithm.

We also commonly say that a binary decision tree with depth d can be executed in time-complexity O(d), even if the tree's length might be 2^d.

On the other hand, we know that P is contained within PSPACE.

0

There are 0 answers