Cornell University
Library
Cornell UniversityLibrary

eCommons

Help
Log In(current)
  1. Home
  2. Cornell Computing and Information Science
  3. Computer Science
  4. Computer Science Technical Reports
  5. On the Intellectual Terrain Around NP

On the Intellectual Terrain Around NP

File(s)
93-1402.pdf (1.21 MB)
93-1402.ps (322.28 KB)
Permanent Link(s)
https://hdl.handle.net/1813/6180
Collections
Computer Science Technical Reports
Hartmanis, Juris
Author
Hartmanis, Juris
Chari, Suresh
Abstract

In this paper, we view $P \stackrel{?}{=} NP$ as the problem which symbolizes the attempt to understand what is and what is not feasibly computable. The paper shortly reviews the history of the developments from Godel'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.

Date Issued
1993-12
Publisher
Cornell University
Keywords
computer science
•
technical report
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR93-1402
Type
technical report

Site Statistics | Help

About eCommons | Policies | Terms of use | Contact Us

copyright © 2002-2026 Cornell University Library | Privacy | Web Accessibility Assistance