In this paper, we show how to systematically
improve on parameterized algorithms and their
analysis, focusing on search-tree based algorithms
for d-Hitting Set, especially for d=3.
We concentrate on algorithms which are easy to implement,
in contrast with the highly sophisticated algorithms
which have been elsewhere designed to ... more >>>

Bennett and Gill (1981) proved that P^A != NP^A relative to a
random oracle A, or in other words, that the set
O_[P=NP] = { A | P^A = NP^A }
has Lebesgue measure 0. In contrast, we show that O_[P=NP] has
Hausdorff dimension 1.

... more >>>

A set is called NP-simple if it lies in NP, and its complement is infinite, and does not contain any infinite subsets in NP. Hartmanis, Li and Yesha proved that no set which is hard for NP under many-one (Karp) reductions is NP-simple unless the intersection of NP and coNP ... more >>>