English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
  Local TagsRelease HistoryDetailsSummary

Released
Report

On the intellectual terrain around NP

MPS-Authors
/persons/resource/persons296226

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

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
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: https://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.