Sparse Hard Sets for P

Dieter van Melkebeek and Mitsunori Ogihara
Additional contact information
Dieter van Melkebeek: University of Chicago, Department of Computer Science
Mitsunori Ogihara: University of Rochester, Department of Computer Science

A chapter in Advances in Algorithms, Languages, and Complexity, 1997, pp 191-208 from Springer

Abstract: Abstract Sparse hard sets for complexity classes has been a central topic for two decades. The area is motivated by the desire to clarify relationships between completeness/hardness and density of languages and studies the existence of sparse complete/hard sets for various complexity classes under various reducibilities. Very recently, we have seen remarkable progress in this area for low-level complexity classes. In particular, the Hartmanis’ sparseness conjectures for P and NL have been resolved. This article overviews the history of sparse hard set problems and exposes some of the recent results.

Keywords: Complexity Class; Satisfying Assignment; Boolean Circuit; Collision Pair; SIGACT News (search for similar items in EconPapers)
Date: 1997
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-1-4613-3394-4_10

Ordering information: This item can be ordered from
http://www.springer.com/9781461333944

DOI: 10.1007/978-1-4613-3394-4_10

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().