MPI-INF/SWS Research Reports 1991-2021

2. Number - All Departments


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:

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},