Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR04-025 | 24th January 2004 00:00

#### Partial Bi-Immunity and NP-Completeness

TR04-025
Authors: John Hitchcock, A. Pavan, N. V. Vinodchandran
Publication: 9th April 2004 21:17
Keywords:

Abstract:

The Turing and many-one completeness notions for $\NP$ have been
previously separated under {\em measure}, {\em genericity}, and {\em
bi-immunity} hypotheses on NP. The proofs of all these results rely
on the existence of a language in NP with almost everywhere hardness.

In this paper we separate the same NP-completeness notions under a
{\em partial bi-immunity hypothesis} that is weaker and only yields a
language in NP that is hard to solve on most strings. This improves
the results of Lutz and Mayordomo~\cite{LutzMayordomo96}, Ambos-Spies
and Bentzien~\cite{AmbosSpiesBentzien00}, and Pavan and
Selman~\cite{PavanSelman02b}. The proof of this result is a
significant departure from previous work.

ISSN 1433-8092 | Imprint