de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Report

On the intellectual terrain around NP

MPS-Authors

Chari,  S.
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Hartmanis,  Juris
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Locator
There are no locators available
Fulltext (public)

MPI-I-94-103.pdf
(Any fulltext), 9MB

Supplementary Material (public)
There is no public supplementary material available
Citation

Chari, S., & Hartmanis, J.(1994). On the intellectual terrain around NP (MPI-I-94-103). Saarbrücken: Max-Planck-Institut für Informatik.


Cite as: http://hdl.handle.net/11858/00-001M-0000-0014-B782-8
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.