17 citations · 26 across the 27 of their papers we have counts for
Showing 2009Show all
2 papers · 1 filter
cs.CC2009
A Divergence Formula for Randomness and Dimension (Short Version)
Jack H. Lutz
If is an infinite sequence over a finite alphabet and is a probability measure on , then the {\it dimension} of with respect to , written , is a c…
cs.CC2009★ 1 cited
Inseparability and Strong Hypotheses for Disjoint NP Pairs
Lance Fortnow, Jack H. Lutz, Elvira Mayordomo
This paper investigates the existence of inseparable disjoint pairs of NP languages and related strong hypotheses in computational complexity. Our main theorem says that, if NP doe…