Logarithmic truth-table reductions and minimum sizes of forcing conditions : preliminary draft (Proof Theory and Computation Theory)
Masahiro Kumabe, Toshio Suzuki, Takeshi Yamazaki · Kyoto University Research Information Repository (Kyoto University) · 2005
In our former works, for a given concept of reduction, we study the following hypothesis: "For a random oracle $A$ , with probability one, the degree of the one-query tautologies with respect to $A$ is strictly higher than the degree of A." In our former works, the following three results are shown: (1) the hy- pothesis for polynomial-time Turing reduction is equivalent to the assertion that the probabilistic complexity class $\mathrm{R}$ is not equal to $\mathrm{N}\mathrm{P}$ , (2) the hypoth- esis for polynomial-time truth-table reduction implies that $\mathrm{P}$ is not $\mathrm{N}\mathrm{P}_{;}$ $(3)$ (to appear in Arch.Math.Logic) the hypothesis holds for polynom ial-time 'The author was partially supported by Grant-in-Aid for Scientific Research (No. 14740082), Japan Society for the Promotion of Science