Carregant...
Carregant...

Vés al contingut (premeu Retorn)

On the sparse set conjecture for sets with low density

Autor
Buhrman, H.; Hermo, M.
Tipus d'activitat
Document cientificotècnic
Data
1994-01-01
Codi
LSI-94-23-R
Repositori
http://hdl.handle.net/2117/97218 Obrir en finestra nova
Resum
We study the sparse set conjecture for sets with low density. The sparse set conjecture states that P = NP if and only if there exists a sparse Turing hard set for NP. In this paper we study a weaker variant of the conjecture. We are interested in the consequences of NP having Turing hard sets of density f(n), for (unbounded) functions f(n), that are sub-polynomial, for example log(n). We establish a connection between Turing hard sets for NP with density f(n) and bounded nondeterminism: We prov...
Citació
Buhrman, H., Hermo, M. "On the sparse set conjecture for sets with low density". 1994.
Paraules clau
Low density sets, Sparse set conjecture

Participants

  • Buhrman, Harry  (autor)
  • Hermo Huguet, Montserrat  (autor)

Arxius