MPI-I-94-103
On the intellectual terrain around NP
Chari, S. and Hartmanis, Juris
January 1994, 11 pages.
.
Status: available - back from printing
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.
URL to this document: https://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1994-103
BibTeX
@TECHREPORT{ChariHartmanis94,
AUTHOR = {Chari, S. and Hartmanis, Juris},
TITLE = {On the intellectual terrain around NP},
TYPE = {Research Report},
INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
NUMBER = {MPI-I-94-103},
MONTH = {January},
YEAR = {1994},
ISSN = {0946-011X},
}