Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Shin Aida:

TR00-081 | 5th September 2000
Shin Aida, Rainer Schuler, Tatsuie Tsukiji, Osamu Watanabe

On the difference between polynomial-time many-one and truth-table reducibilities on distributional problems

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

ISSN 1433-8092 | Imprint