In this paper we separate many-one reducibility from truth-table reducibility for distributional problems in DistNP under the hypothesis that P neq NP. As a first example we consider the 3-Satisfiability problem (3SAT) with two different distributions on 3CNF formulas. We show that 3SAT using a version of the standard distribution ... more >>>

SBP is a probabilistic promise class located between MA and AM \cap BPPpath. The first part of the paper studies the question of whether SBP has many-one complete sets. We relate this question to the existence of uniform enumerations. We construct an oracle relative to which SBP and AM do ... more >>>

A clone is a set of functions that is closed under generalized substitution. The set FP of functions being computable deterministically in polynomial time is such a clone. It is well-known that the set of subclones of every clone forms a lattice. We study the lattice below FP, which contains ... more >>>