Alan L. Selman

TCS Journal 2009 Journal Article

Non-mitotic sets

• Christian Glaßer
• Alan L. Selman
• Stephen Travers
• Liyu Zhang

We study the question of the existence of non-mitotic sets in NP. We show under various hypotheses that • 1-tt-mitoticity and m-mitoticity differ on NP. • T-autoreducibility and T-mitoticity differ on NP (this contrasts the situation in the recursion theoretic setting, where Ladner showed that autoreducibility and mitoticity coincide). • 2-tt-autoreducibility does not imply weak 2-tt-mitoticity (from this it follows that autoreducibility and mitoticity are not equivalent for all reducibilities between 2-tt and T, although the notions coincide for m- and 1-tt-reducibility).

TCS Journal 2007 Journal Article

Canonical disjoint NP-pairs of propositional proof systems

• Christian Glaßer
• Alan L. Selman
• Liyu Zhang

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. We show that this degree structure is not superficial: Assuming there exist P-inseparable disjoint NP-pairs, every countable distributive lattice can be embedded into every interval of polynomial NP-degrees of disjoint pairs by maps that preserve the least and greatest element, respectively. As one consequence of this embedding, under the same assumption, there exist intermediate disjoint NP-pairs. That is, if ( A, B ) is a P-separable disjoint NP-pair and ( C, D ) is a P-inseparable disjoint NP-pair, then there exist P-inseparable, incomparable NP-pairs ( E, F ) and ( G, H ) whose degrees lie strictly between ( A, B ) and ( C, D ). Furthermore, between any two disjoint NP-pairs that are comparable and inequivalent, such a diamond exists.

TCS Journal 2007 Journal Article

Polylogarithmic-round interactive proofs for coNP collapse the exponential hierarchy

• A. Pavan
• Alan L. Selman
• Samik Sengupta
• N.V. Vinodchandran

If every language in coNP has a constant-round interactive proof system, then the polynomial-time hierarchy collapses [R. B. Boppana, J. Håstad, S. Zachos, Does co-NP have short interactive proofs? Information Processing Letters 25 (2) (1987) 127–132]. On the other hand, the well-known LFKN protocol gives O ( n ) -round interactive proof systems for all languages in coNP [C. Lund, L. Fortnow, H. Karloff, N. Nisan, Algebraic methods for interactive proof systems, Journal of the Association for Computing Machinery 39 (4) (1992) 859–868]. We consider the question of whether it is possible for coNP to have interactive proof systems with polylogarithmic-round complexity. We show that this is unlikely by proving that if a coNP-complete set has a polylogarithmic-round interactive proof system, then the exponential-time hierarchy collapses. We also consider exponential versions of the Karp–Lipton theorem and Yap’s theorem.

MFCS Conference 2005 Conference Paper

Autoreducibility, Mitoticity, and Immunity

• Christian Glaßer
• Mitsunori Ogihara
• Aduri Pavan
• Alan L. Selman
• Liyu Zhang 0001

Abstract We show the following results regarding complete sets. NP-complete sets and PSPACE-complete sets are many-one autoreducible. 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. If one-way permutations and quick pseudo-random generators exist, then NP-complete languages are m -mitotic. If there is a tally language in NP ∩ coNP - P, then, for every ε > 0, NP-complete sets are not 2 n (1 + ε ) -immune. These results solve several of the open questions raised by Buhrman and Torenvliet in their 1994 survey paper on the structure of complete sets.

MFCS Conference 2005 Conference Paper

Canonical Disjoint NP-Pairs of Propositional Proof Systems

• Christian Glaßer
• Alan L. Selman
• Liyu Zhang 0001

Abstract 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 P-inseparable disjoint pairs, there exist intermediate disjoint NP-pairs. That is, if ( A, B ) is a P-separable disjoint NP-pair and ( C, D ) is a P-inseparable disjoint NP-pair, then there exist P-inseparable, incomparable NP-pairs ( E, F ) and ( G, H ) whose degrees lie strictly between ( A, B ) and ( C, D ). Furthermore, between any two disjoint NP-pairs that are comparable and inequivalent, such a diamond exists.

I&C Journal 2005 Journal Article

Reductions between disjoint NP-Pairs

• Christian Glaßer
• Alan L. Selman
• Samik Sengupta

Disjoint NP-pairs are pairs (A, B) of nonempty, disjoint sets in NP. 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 reductions; the class of all disjoint NP-pairs is uniformly enumerable. Let A, B, C, and D be nonempty sets belonging to NP. A smart reduction between the disjoint NP-pairs (A, B) and (C, D) is a Turing reduction with the additional property that if the input belongs to A ∪ B, then all queries belong to C ∪ D. We prove under the reasonable assumption that UP∩co-UP has a P-bi-immune set that there exist disjoint NP-pairs (A, B) and (C, D) such that (A, B) is truth-table reducible to (C, D), but there is no smart reduction between them. This paper contains several additional separations of reductions between disjoint NP-pairs. We exhibit an oracle relative to which DistNP has a truth-table-complete disjoint NP-pair, but has no many-one-complete disjoint NP-pair.

I&C Journal 2004 Journal Article

Bi-immunity separates strong NP-completeness notions

• A. Pavan
• Alan L. Selman

We prove that if for some ϵ>0, NP contains a set that is DTIME(2 n ϵ )-bi-immune, then NP contains a set that is 2-Turing complete for NP (hence 3-truth-table complete) but not 1-truth-table complete for NP. Thus this hypothesis implies a strong separation of completeness notions for NP. Lutz and Mayordomo (Theor. Comput. Sci. 164 (1996) 141–163) and Ambos-Spies and Bentzien (J. Comput. Syst. Sci. 61(3) (2000) 335–361) previously obtained the same consequence using strong hypotheses involving resource-bounded measure and/or category theory. Our hypothesis is weaker and involves no assumptions about stochastic properties of NP.

TCS Journal 2000 Journal Article

Complete distributional problems, hard languages, and resource-bounded measure

• A. Pavan
• Alan L. Selman

We say that a distribution μ is reasonable if there exists a constant s⩾0 such that μ({x||x|⩾n})=Ω(1/ns). We prove the following result, which suggests that all DistNP-complete problems have reasonable distributions. If NP contains a DTIME(2n)-bi-immune set, then every DistNP-complete set has a reasonable distribution. It follows from work of Mayordomo [19] that the consequent holds if the p-measure of NP is not zero. Cai and Selman [6] defined a modification and extension of Levin's notion of average polynomial time to arbitrary time-bounds and proved that if L is P-bi-immune, then L is distributionally hard, meaning that, for every polynomial-time computable distribution μ, the distributional problem (L, μ) is not polynomial on the μ-average. We prove the following results, which suggest that distributional hardness is closely related to more traditional notions of hardness. 1. If NP contains a distributionally hard set, then NP contains a P-immune set. 2. There exists a language L that is distributionally hard but not P-bi-immune if and only if P contains a set that is immune to all P-printable sets. The following corollaries follow readily 1. If the p-measure of NP is not zero, then there exists a language L that is distributionally hard but not P-bi-immune. 2. If the p2 -measure of NP is not zero, then there exists a language L in NP that is distributionally hard but not P-bi-immune.

TCS Journal 1998 Journal Article

A hierarchy based on output multiplicity

• Ashish V. Naik
• John D. Rogers
• James S. Royer
• Alan L. Selman

The class NPkV consists of those partial, multivalued functions that can be computed by a nondeterministic, polynomial time-bounded transducer that has at most k distinct values on any input. We define the output-multiplicity hierarchy to consist of the collection of classes NPkV for all positive integers k ≥ 1. In this paper we investigate the strictness of the output-multiplicity hierarchy and establish three main results pertaining to this: 1. 1. If for any k > 1, the class NPkV collapses into the class NP(k − 1)V, then the polynomial hierarchy collapses to Σ 2 P. 2. 2. If the converse of the above result is true, then any proof of this converse cannot relativize. We exhibit an oracle relative to which the polynomial hierarchy collapses to PNP, but the output-multiplicity hierarchy is strict. 3. 3. Relative to a random oracle, the output-multiplicity hierarchy is strict. This result is in contrast to the still open problem of the strictness of the polynomial hierarchy relative to a random oracle. In introducing the technique for the third result we prove a related result of interest: relative to a random oracle UP ≠ NP.

TCS Journal 1993 Journal Article

Foreword

• Alan L. Selman

TCS Journal 1993 Journal Article

Hard promise problems and nonuniform complexity

• Luc Longpré
• Alan L. Selman

For every recursive set A, let PP-A denote the following promise problem: input x and y promise (xϵA) ⊕ (yϵA) property xϵA. We show that if L is a solution of PP-A, then AϵP L /Poly. From this result, it follows that if A is ⩽P T-hard for NP, then all solutions of PP-A are hard for NP under a reduction that generalizes both ⩽P T and ⩽SN T. Specifically, if A is NP-hard, then all solutions of PP-A are generalized high 2 (Balcázar et al. , 1986). The main theorem that leads to this result states that if A is a self-reducible set and AϵP L /Poly, then ΣP, A 2 ⊆ ΣP, L 2. Several interesting connections between uniform and nonuniform complexity follow directly from this theorem.

MFCS Conference 1990 Invited Paper

One-Way Functions in Complexity Theory

• Alan L. Selman

Abstract In complexity theory a one-way function is defined to be a one-one, honest, function that is computable in polynomial time whose inverse is not computable in polynomial time. We will examine relationships between the complexity of functional computational problems and ordinary set recognition problems. The complexity of inverting one-way functions will follow from these relationships. Then, we will survey various forms of one-way functions that have arisen in relationship to some cryptographic investigations and in relationship to the Isomorphism Problem.

I&C Journal 1988 Journal Article

Promise problems complete for complexity classes

• Alan L. Selman

A general framework is given to obtain hardness results for promise problems that derive from self-reducible decision problems. The principal theorem is that if a set A is ≤ d P -equivalent to a disjunctive-self-reducible set in NP, then the natural promise problem associated with A is as hard to solve as it is to recognize A. NP-hardness of the satisfiability promise problem follows, and graph isomorphism hardness of a promise problem that derives from the graph isomorphism problem is proved.

FOCS Conference 1984 Conference Paper

Complexity Measures for Public-Key Cryptosystems (Preliminary Report)

• Joachim Grollmann
• Alan L. Selman

The first part of this paper gives results about promise problems. A "promise problem" is a formulation of a partial decision problem that is useful for describing cracking problems for public-key cryptosystems (PKCS). We prove that every NP-hard promise problem is uniformly NP-hard, and we show that a number of results and a conjecture about promise problems are equivalent to separability assertions that are the natural analogues of well-known results in classical recursion theory. The conjecture, if it is true, implies nonexistence of PKCS having NP-hard cracking problems. The second part of the paper studies more appropriate measures for PKCS. Among the results obtained are the following: One-way functions exist if an only if P /spl ne/ U and one-way functions f such that range f /spl epsiv/ P exist if and only if U /spl cap/ co-U /spl ne/ P. It will allow that there exist PKCS that cannot be cracked in polynomial time (and that satisfy other reasonable assumptions) only if P /spl ne/ U.

FOCS Conference 1984 Conference Paper

Sparse Oracles and Uniform Complexity Classes

• José L. Balcázar
• Ronald V. Book
• Timothy J. Long
• Uwe Schöning
• Alan L. Selman

We show that several questions about the polynomial-time hierarchy can be answered by answering their counterparts for the polynomial-time hierarchy relativized to an arbitrary sparse oracle set. For each of these questions, the answer will be the same for the hierarchy relativized to S/sub 1/ as it will be for the hierarchy relativized to S/sub 2/ for any choice of S/sub 1/ and S/sub 2/ that are sparse sets, including the choice of S/sub 1/ being empty and S/sub 2/ being nonempty but sparse.

TCS Journal 1982 Journal Article

Reductions on NP and P-selective sets

• Alan L. Selman

P-selective sets are used to distinguish polynomial time-bounded reducibilities on NP. In particular, we consider different kinds of “positive” reductions; these preserve membership in NP and are not a priori closed under complements. We show that the class of all sets which are both P-selective and have positive reductions to their complements is P. This is used to show that if DEXT ≠ NEXT, then there exists a set in NP−P that is not positive reducible to its complement. Various similar results are obtained. We also show that P is the class of all sets which are both p-selective and positive truth-table self-reducible. From this result, it follows that various naturally defined apparently intractible problems are not p-selective unless P = NP.

TCS Journal 1979 Journal Article

A second step toward the polynomial hierarchy

• Theodore P. Baker
• Alan L. Selman

Some of the questions posed by Baker et al. [1] are here answered. The principal result is that there exists a recursive oracle for which the relativized polynomial hierarchy exists through the second level; that is, there is a recursive set B such that Σ 2 P, B ≠ Π 2 P, B. It follows that Σ 2 P, B ⊊ Σ 3 P, B.

FOCS Conference 1976 Conference Paper

A Second Step toward the Polynomial Hierarchy

• Theodore P. Baker
• Alan L. Selman

Some of the questions posed by Baker, Gill, and Solovay [1] are here answered. The principal result is that there exists a recursive oracle for which the relativized polynomial hierarchy exists through the second level; that is, there is a recursive set B such that Σ2P, B ≠ π2P, B. It follows that Σ2P, B ⊂≠ Σ3P, B.

STOC Conference 1974 Conference Paper

Comparisons of Polynomial-Time Reducibilities

• Richard E. Ladner
• Nancy A. Lynch
• Alan L. Selman

STOC Conference 1972 Conference Paper

Turing Machines and the Spectra of First-Order Formulas with Equality

• Neil D. Jones
• Alan L. Selman

In this paper we show that these similarities are not accidental - that spectra and context sensitive languages are closely related, and that their open questions are merely special cases of a family of open questions which relate to the difference (if any) between deterministic and non-deterministic time-or space-bounded Turing machines.