Till Tantau

A language is \emph{selective} if there exists a

selection algorithm for it. Such an algorithm selects

from any two words one, which is an element of the

language whenever at least one of them is.

Restricting the complexity of selection algorithms

yields different \emph{selectivity classes} ...
more >>>

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

Till Tantau

A language is called k-membership comparable if there exists a

polynomial-time algorithm that excludes for any k words one of

the 2^k possibilities for their characteristic string.

It is known that all membership comparable languages can be

reduced to some P-selective language with polynomially many

adaptive queries. We show however ...
more >>>

Christian Glaßer, A. Pavan, Alan L. Selman, Samik Sengupta

We study several properties of sets that are complete for NP.

We prove that if $L$ is an NP-complete set and $S \not\supseteq L$ is a p-selective sparse set, then $L - S$ is many-one-hard for NP. We demonstrate existence of a sparse set $S \in \mathrm{DTIME}(2^{2^{n}})$

such ...
more >>>

Till Tantau

The Hartmanis--Immerman--Sewelson theorem is the classical link between the exponential and the polynomial time realm. It states that NE = E if, and only if, every sparse set in NP lies in P. We establish similar links for classes other than sparse sets:

1. E = UE if, and only ... more >>>