Impagliazzo and Levin demonstrated [IL90] that the average-case hardness of any NP-search problem under any P-samplable distribution implies that of another NP-search problem under the uniform distribution. For this they developed a way to define a reduction from an NP-search problem F with ``mild hardness'' under any P-samplable distribution H; ... more >>>

We study the Isomorphism Conjecture proposed by Berman and Hartmanis. It states that all sets complete for NP under polynomial-time many-one reductions are P-isomorphic to each other. From previous research it has been widely believed that all NP-complete sets are reducible each other by one-to-one and length-increasing polynomial-time reductions, but ... more >>>

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