Skip to main content


eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >

Please use this identifier to cite or link to this item:
Title: Computation Times of NP Sets of Different Densities
Authors: Hartmanis, Juris
Yesha, Yaacov
Keywords: computer science
technical report
Issue Date: Mar-1983
Publisher: Cornell University
Abstract: In this paper, we study the computational complexity of sets of different densities in NP. We show that the deterministic computation time for sets in NP can depend on their density if and only if there is a collapse or partial collapse of the corresponding higher nondeterministic and deterministic time bonded complexity classes. We show also that for NP sets of different densities there exist complete sets of the corresponding density under polynomial time Turing reductions. Finally, we show that these results can be interpreted as results about the complexity of theorem proving and proof presentation in axiomatized mathematical systems. This interpretation relates fundamental questions about the complexity of our intellectual tools to basic structural problems about P, NP, CoNP, and PSPACE, discussed in this paper.
Appears in Collections:Computer Science Technical Reports
Hartmanis, Juris

Files in This Item:

File Description SizeFormat
83-548.pdf1.14 MBAdobe PDFView/Open
83-548.ps459.04 kBPostscriptView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.


© 2014 Cornell University Library Contact Us