Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society


On the intellectual terrain around NP

Chari, S. and Hartmanis, Juris

MPI-I-94-103. January 1994, 11 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
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.
References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s):
MPI-I-94-103.pdfMPI-I-94-103.pdf8886 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView
URL to this document:
Hide details for BibTeXBibTeX
  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},