A. Pavan, Alan L. Selman

We use hypotheses of structural complexity theory to separate various

NP-completeness notions. In particular, we introduce an hypothesis from which we describe a set in NP that is Turing complete but not truth-table complete. We provide fairly thorough analyses of the hypotheses that we introduce. Unlike previous approaches, we ...
more >>>

A. Pavan, Alan L. Selman

We prove that if for some epsilon > 0 NP contains a set that is

DTIME(2^{n^{epsilon}})-bi-immune, then NP contains a set that 2-Turing

complete for NP but not 1-truth-table complete for NP. Lutz and Mayordomo

(LM96) and Ambos-Spies and Bentzien (AB00) previously obtained the

same consequence using strong ...
more >>>

John Hitchcock, A. Pavan, N. V. Vinodchandran

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 ... more >>>

Debasis Mandal, A. Pavan, Rajeswari Venugopalan

We show that there is a language that is Turing complete for NP but not many-one complete for NP, under a {\em worst-case} hardness hypothesis. Our hypothesis asserts the existence of a non-deterministic, double-exponential time machine that runs in time $O(2^{2^{n^c}})$ (for some $c > 1$) accepting $\Sigma^*$ whose accepting ... more >>>