On the Intellectual Terrain Around NP
Author
Hartmanis, Juris
Chari, Suresh
Abstract
In this paper, we view $P \stackrel{?}{=} NP$ as the problem which symbolizes the attempt to understand what is and what is not feasibly computable. The paper shortly reviews the history of the developments from Godel'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.
Date Issued
1993-12
Publisher
Cornell University
Keywords
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR93-1402
Type
technical report