Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Alan L. Selman:

TR07-018 | 1st March 2007
Christian Glaßer, Alan L. Selman, Liyu Zhang

The Informational Content of Canonical Disjoint NP-Pairs

We investigate the connection between propositional proof systems and their canonical pairs. It is known that simulations between proof systems translate to reductions between their canonical pairs. We focus on the opposite direction and study the following questions.

Q1: Where does the implication [can(f) \le_m can(g) => f \le_s ... more >>>

TR06-090 | 22nd June 2006
Christian Glaßer, Alan L. Selman, Stephen Travers, Liyu Zhang

Non-Mitotic Sets

<p> We study the question of the existence of non-mitotic sets in NP. We show under various hypotheses that:</p>
<li>1-tt-mitoticity and m-mitoticity differ on NP.</li>
<li>1-tt-reducibility and m-reducibility differ on NP.</li>
<li>There exist non-T-autoreducible sets in NP (by a result from Ambos-Spies, these sets are neither ... more >>>

TR06-069 | 11th May 2006
Christian Glaßer, Alan L. Selman, Stephen Travers, Klaus W. Wagner

The Complexity of Unions of Disjoint Sets

This paper is motivated by the open question
whether the union of two disjoint NP-complete sets always is
NP-complete. We discover that such unions retain
much of the complexity of their single components. More precisely,
they are complete with respect to more general reducibilities.

more >>>

TR05-072 | 11th July 2005
Christian Glaßer, Alan L. Selman, Liyu Zhang

Survey of Disjoint NP-Pairs and Relations to Propositional Proof Systems

We survey recent results on disjoint NP-pairs. In particular, we survey the relationship of disjoint NP-pairs to the theory of proof systems for propositional calculus.

more >>>

TR05-068 | 7th July 2005
Christian Glaßer, A. Pavan, Alan L. Selman, Liyu Zhang

Redundancy in Complete Sets

We show that a set is m-autoreducible if and only if it is m-mitotic. This solves a long standing open question in a surprising way. As a consequence of this unconditional result and recent work by Glasser et al., complete sets for all of the following complexity classes are m-mitotic: ... more >>>

TR05-011 | 21st December 2004
Christian Glaßer, Mitsunori Ogihara, A. Pavan, Alan L. Selman, Liyu Zhang

Autoreducibility, Mitoticity, and Immunity

We show the following results regarding complete sets:

NP-complete sets and PSPACE-complete sets are many-one

Complete sets of any level of PH, MODPH, or
the Boolean hierarchy over NP are many-one autoreducible.

EXP-complete sets are many-one mitotic.

NEXP-complete sets are weakly many-one mitotic.

PSPACE-complete sets are weakly Turing-mitotic.

... more >>>

TR04-106 | 19th November 2004
Christian Glaßer, Alan L. Selman, Liyu Zhang

Canonical Disjoint NP-Pairs of Propositional Proof Systems

We prove that every disjoint NP-pair is polynomial-time, many-one equivalent to
the canonical disjoint NP-pair of some propositional proof system. Therefore, the degree structure of the class of disjoint NP-pairs and of all canonical pairs is
identical. Secondly, we show that this degree structure is not superficial: Assuming there exist ... 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 >>>

TR04-007 | 13th January 2004
Alan L. Selman, Samik Sengupta

Polylogarithmic-round Interactive Proofs for coNP Collapses the Exponential Hierarchy

Revisions: 1 , Comments: 1

It is known \cite{BHZ87} that if every language in coNP has a
constant-round interactive proof system, then the polynomial hierarchy
collapses. On the other hand, Lund {\em et al}.\ \cite{LFKN92} have shown that
#SAT, the #P-complete function that outputs the number of satisfying
assignments of a Boolean ... more >>>

TR03-027 | 21st April 2003
Christian Glaßer, Alan L. Selman, Samik Sengupta

Reductions between Disjoint NP-Pairs

We prove that all of the following assertions are equivalent:
There is a many-one complete disjoint NP-pair;
there is a strongly many-one complete disjoint NP-pair;
there is a Turing complete disjoint NP-pair such that all reductions
are smart reductions;
there is a complete disjoint NP-pair for one-to-one, invertible ... more >>>

TR03-011 | 17th February 2003
Christian Glaßer, Alan L. Selman, Samik Sengupta, Liyu Zhang

Disjoint NP-Pairs

We study the question of whether the class DisNP of
disjoint pairs (A, B) of NP-sets contains a complete pair.
The question relates to the question of whether optimal
proof systems exist, and we relate it to the previously
studied question of whether there exists ... more >>>

TR02-005 | 3rd January 2002
A. Pavan, Alan L. Selman

Bi-Immunity Separates Strong NP-Completeness Notions

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

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

TR96-027 | 20th February 1996
Lane A. Hemaspaandra, Ashish Naik, Mitsunori Ogihara, Alan L. Selman

Computing Solutions Uniquely Collapses the Polynomial Hierarchy

Is there an NP function that, when given a satisfiable formula
as input, outputs one satisfying assignment uniquely? That is, can a
nondeterministic function cull just one satisfying assignment from a
possibly exponentially large collection of assignments? We show that if
there is such a nondeterministic function, then the polynomial ... more >>>

TR95-019 | 14th April 1995
Jin-Yi Cai, Alan L. Selman

Average time complexity classes

ISSN 1433-8092 | Imprint