Deterministic and randomized bounded truth-table reductions of P, NL, and L to sparse sets

DOI10.1006/JCSS.1998.1589zbMath0921.68030OpenAlexW2003299480MaRDI QIDQ1276171

Dieter van Melkebeek

Publication date: 17 January 1999

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

Full work available at URL: https://semanticscholar.org/paper/8cdc3d2342e6b56553b96aaeb58386652dd791a5

zbMATH Keywords

truth-table reductionsparse hard set

Mathematics Subject Classification ID

Related Items (1)

On the reducibility of sets inside NP to sets with low information content

Cites Work

• On log-tape isomorphisms of complete sets
• On reductions of NP sets to sparse sets
• Very Fast Parallel Polynomial Arithmetic
• A taxonomy of problems with fast parallel algorithms
• Problems complete for deterministic logarithmic space
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• On the existence of hard sparse sets under weak reductions
• Fast parallel matrix and GCD computations
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Deterministic and randomized bounded truth-table reductions of P, NL, and L to sparse sets