𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Sparse Hard Sets for P: Resolution of a Conjecture of Hartmanis

✍ Scribed by Jin-Yi Cai; D. Sivakumar

Publisher
Elsevier Science
Year
1999
Tongue
English
Weight
170 KB
Volume
58
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

✦ Synopsis

Building on a recent breakthrough by Ogihara, we resolve a conjecture made by Hartmanis in 1978 regarding the (non)existence of sparse sets complete for P under logspace many one reductions. We show that if there exists a sparse hard set for P under logspace many one reductions, then P=LOGSPACE. We further prove that if P has a sparse hard set under many one reductions computable in NC 1 , then P collapses to NC 1 .

πŸ“œ SIMILAR VOLUMES

A new a priori ordering method for spars
A new a priori ordering method for sparse systems of equations based on an ordered output set
✍ Kabekode V. S. Bhat; Bharat Kinariwala πŸ“‚ Article πŸ“… 1980 πŸ› John Wiley and Sons 🌐 English βš– 585 KB

## Abstract In the context of solution to the sparse systems of equations arising in computer‐aided analysis and design of electrical networks using the Gaussian elimination (GE) process it is well‐known that an __a priori__ reordering for equations and unknowns is almost mandatory. In this paper w

A sparse marker extension tree algorithm
A sparse marker extension tree algorithm for selecting the best set of haplotype tagging single nucleotide polymorphisms
✍ Ke Hao; Simin Liu; Tianhua Niu πŸ“‚ Article πŸ“… 2005 πŸ› John Wiley and Sons 🌐 English βš– 533 KB

Single nucleotide polymorphisms (SNPs) play a central role in the identification of susceptibility genes for common diseases. Recent empirical studies on human genome have revealed block-like structures, and each block contains a set of haplotype tagging SNPs (htSNPs) that capture a large fraction o