Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > P-SELECTIVE:
Reports tagged with P-selective:
TR00-077 | 24th August 2000
Till Tantau

On the Power of Extra Queries to Selective Languages

Revisions: 1

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


TR01-032 | 3rd April 2001
A. Pavan, Alan L. Selman

Separation of NP-completeness Notions

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


TR02-004 | 2nd November 2001
Till Tantau

A Note on the Power of Extra Queries to Membership Comparable Sets

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


TR04-019 | 15th January 2004
Christian Gla├čer, A. Pavan, Alan L. Selman, Samik Sengupta

Properties of NP-Complete Sets

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


TR08-027 | 4th December 2007
Till Tantau

Generalizations of the Hartmanis-Immerman-Sewelson Theorem and Applications to Infinite Subsets of P-Selective Sets

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




ISSN 1433-8092 | Imprint