hide
Free keywords:
-
Abstract:
In this paper we view $P\stackrel{?}{=}NP$ as the problem which symbolizes
the attempt to understand what is and is not feasibly computable.
The paper shortly reviews the history of the developments
from G"odel's 1956 letter asking for the computational
complexity of finding proofs of theorems, through
computational complexity, the exploration of complete problems for NP
and PSPACE, through the results of structural complexity to the
recent insights about interactive proofs.