Sparse complete sets for NP: Solution of a conjecture of Berman and Hartmanis

1982/10/01 by Stephen R. Mahaney · 1 voice · 6 citations
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #semigroups and automata theory

paper · pdf · doi:10.1016/0022-0000(82)90002-2

crossref issued 1982/10/01 · crossref published 1982/10/01 · crossref published-print 1982/10/01 · openalex publication_date 1982/10/01 · crossref created 2003/12/04 · crossref deposited 2019/02/16 · openalex created_date 2025/10/10 · crossref indexed 2026/03/05 · openalex updated_date 2026/08/01

Citations

• Computational Complexity of Probabilistic Turing Machines

Cited by

• Frameworks for Solving Turing Kernel Lower Bound Problem and Finding Natural Candidate Problems in NP-intermediate
• Non-NP-Hardness of Translationally-Invariant Spin-Model Problems
• An NP-Complete Problem in Grid Coloring
• A Moment of Perfect Clarity II: Consequences of Sparse Sets Hard for NP with Respect to Weak Reductions
• Tally NP Sets and Easy Census Functions
• NP-hard sets are not sparse unless P=NP: An exposition of a simple proof of Mahaney's Theorem, with applications

Discussions

• If your hashes had length $O(\log n)$ rather than just $(\log n)^{O(1)}$ , then this would imply $\let\C\mathsf\C{P = NP}$ by Mahaney’s theorem [1], as it would make $$L=\{(1^n,H_n(F)):F\text{ is a sa [stackexchange, 4 points]