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

DOI10.1016/0022-0000(82)90002-2zbMath0493.68043OpenAlexW2023336906WikidataQ56610691 ScholiaQ56610691MaRDI QIDQ1168733

Publication date: 1982

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://hdl.handle.net/1813/6257

zbMATH Keywords

polynomial-time hierarchy NP-complete sets

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Other degrees and reducibilities in computability and recursion theory (03D30)

Related Items (88)

Reductions among polynomial isomorphism types ⋮ On reductions of NP sets to sparse sets ⋮ Small polyomino packing ⋮ The random oracle hypothesis is false ⋮ A note on bi-immunity and $p$-closeness of $p$-cheatable sets in $P$/poly ⋮ Complexity and dimension ⋮ On bounded query machines ⋮ Space-efficient recognition of sparse self-reducible languages ⋮ NP-hard sets are superterse unless NP is small ⋮ Jigsaw puzzles, edge matching, and polyomino packing: Connections and complexity ⋮ Computational complexity of synchronization under sparse regular constraints ⋮ Structural complexity theory: Recent surprises ⋮ Nonuniform lowness and strong nonuniform lowness ⋮ A comparison of polynomial time completeness notions ⋮ On helping by robust oracle machines ⋮ Geometric sets of low information content ⋮ Quasi-linear truth-table reductions to $p$-selective sets ⋮ Self-reducibility ⋮ Can the catenation of two weakly sparse languages be dense? ⋮ On the complexity of the spaced seeds ⋮ Isomorphisms and 1-L reductions ⋮ An excursion to the Kolmogorov random strings ⋮ Counting quantifiers, successor relations, and logarithmic space ⋮ $\Sigma_ 2SPACE(n)$ is closed under complement ⋮ $\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}$ ⋮ Collapsing degrees ⋮ Separating classes in the exponential-time hierarchy from classes in PH ⋮ Relativized alternation and space-bounded computation ⋮ On the relative complexity of hard problems for complexity classes without complete problems ⋮ On intractability of the classUP ⋮ Separating NE from Some Nonuniform Nondeterministic Complexity Classes ⋮ Notes on polynomial levelability ⋮ Self-reducible sets of small density ⋮ On polynomial-time truth-table reducibility of intractable sets to P-selective sets ⋮ A refinement of the low and high hierarchies ⋮ On the power of parity polynomial time ⋮ On vanishing of Kronecker coefficients ⋮ Infeasibility of instance compression and succinct PCPs for NP ⋮ The complexity of grid coloring ⋮ On universally easy classes for NP-complete problems. ⋮ Unnamed Item ⋮ Upper bounds for the complexity of sparse and tally descriptions ⋮ Classifying the computational complexity of problems ⋮ $P^{NP[O(\log n)}$ and sparse turing-complete sets for NP] ⋮ New developments in structural complexity theory ⋮ Separating NE from some nonuniform nondeterministic complexity classes ⋮ On Upward Drawings of Trees on a Given Grid ⋮ The Power of Self-Reducibility: Selectivity, Information, and Approximation ⋮ The complexity of minimum difference cover ⋮ A note on P-selective sets and closeness ⋮ The complexity types of computable sets ⋮ Turing machines with few accepting computations and low sets for PP ⋮ On polynomial time one-truth-table reducibility to a sparse set ⋮ On polynomial-time Turing and many-one completeness in PSPACE ⋮ Weak cardinality theorems ⋮ On sparseness and Turing reducibility over the reals ⋮ On the power of parity polynomial time ⋮ On the asymmetric complexity of the group-intersection problem ⋮ Special issue: 17th ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, Seattle, WA, USA, June 1--3, 1998 ⋮ On sparse hard sets for counting classes ⋮ A note on minimum-area upward drawing of complete and Fibonacci trees ⋮ On sparseness, reducibilities, and complexity ⋮ Core instances for testing: a case study ⋮ The strong exponential hierarchy collapses ⋮ Seed optimization for i.i.d. similarities is no easier than optimal Golomb ruler design ⋮ Bounded-depth succinct encodings and the structure they imply on graphs ⋮ Reductions to sets of low information content ⋮ A note on sparse sets and the polynomial-time hierarchy ⋮ Complexity classes between $\Theta _k^P$ and $\Delta _k^P$ ⋮ On sets bounded truth-table reducible to $P$-selective sets ⋮ Monotonous and randomized reductions to sparse sets ⋮ The structure of logarithmic advice complexity classes ⋮ Taming the knight's tour: minimizing turns and crossings ⋮ Relativizing relativized computations ⋮ On inefficient special cases of NP-complete problems ⋮ Complete sets and closeness to complexity classes ⋮ On the computational complexity of the languages of general symbolic dynamical systems and beta-shifts ⋮ Sparse hard sets for P: Resolution of a conjecture of Hartmanis ⋮ Resolution of Hartmanis' conjecture for NL-hard sparse sets ⋮ On hard instances ⋮ Sparse parameterized problems ⋮ Tally NP sets and easy census functions. ⋮ On small generators ⋮ Kolmogorov characterizations of complexity classes ⋮ On symmetric differences of NP-hard sets with weakly P-selective sets ⋮ Padding, commitment and self-reducibility ⋮ On one-one polynomial time equivalence relations ⋮ On the computational structure of the connected components of a hard problem

Cites Work

This page was built for publication: Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis