TY - JOUR

T1 - Does truth-table of linear norm reduce the one-query tautologies to a random oracle?

AU - Kumabe, Masahiro

AU - Suzuki, Toshio

AU - Yamazaki, Takeshi

N1 - Funding Information:
The authors are partially supported by Grant-in-Aid for Scientific Research (No. 14740082 and No. 17540131), Japan Society for the Promotion of Science.

PY - 2008/7

Y1 - 2008/7

N2 - 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 (Suzuki in Kobe J. Math. 15, 91-102, 1998; in Inf. Comput. 176, 66-87, 2002; in Arch. Math. Logic 44, 751-762), the following three results are shown: The hypothesis for p-T (polynomial-time Turing) reduction is equivalent to the assertion that the probabilistic complexity class R is not equal to NP; The hypothesis for p-tt (polynomial-time truth-table) reduction implies that P is not NP; The hypothesis holds for each of the following: disjunctive reduction, conjunctive reduction, and p-btt (polynomial-time bounded-truth-table) reduction. In this paper, we show the following three results: (1) Let c be a positive real number. We consider a concept of truth-table reduction whose norm is at most c times size of input, where for a relativized propositional formula F, the size of F denotes the total number of occurrences of propositional variables, constants and propositional connectives. Then, our main result is that the hypothesis holds for such tt-reduction, provided that c is small enough. How small c can we take so that the above holds? It depends on our syntactic convention on one-query tautologies. In our setting, the statement holds for all c < 1. (2) The hypothesis holds for monotone truth-table reduction (also called positive reduction). (3) Dowd (in Inf. Comput. 96, 65-76, 1992) shows a polynomial upper bound for the minimum sizes of forcing conditions associated with a random oracle. We apply the above result (1), and get a linear lower bound for the sizes.

AB - 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 (Suzuki in Kobe J. Math. 15, 91-102, 1998; in Inf. Comput. 176, 66-87, 2002; in Arch. Math. Logic 44, 751-762), the following three results are shown: The hypothesis for p-T (polynomial-time Turing) reduction is equivalent to the assertion that the probabilistic complexity class R is not equal to NP; The hypothesis for p-tt (polynomial-time truth-table) reduction implies that P is not NP; The hypothesis holds for each of the following: disjunctive reduction, conjunctive reduction, and p-btt (polynomial-time bounded-truth-table) reduction. In this paper, we show the following three results: (1) Let c be a positive real number. We consider a concept of truth-table reduction whose norm is at most c times size of input, where for a relativized propositional formula F, the size of F denotes the total number of occurrences of propositional variables, constants and propositional connectives. Then, our main result is that the hypothesis holds for such tt-reduction, provided that c is small enough. How small c can we take so that the above holds? It depends on our syntactic convention on one-query tautologies. In our setting, the statement holds for all c < 1. (2) The hypothesis holds for monotone truth-table reduction (also called positive reduction). (3) Dowd (in Inf. Comput. 96, 65-76, 1992) shows a polynomial upper bound for the minimum sizes of forcing conditions associated with a random oracle. We apply the above result (1), and get a linear lower bound for the sizes.

KW - Computational complexity

KW - Forcing complexity

KW - Monotone Boolean formula

KW - Random oracle

KW - Truth-table reduction

UR - http://www.scopus.com/inward/record.url?scp=45049084674&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=45049084674&partnerID=8YFLogxK

U2 - 10.1007/s00153-008-0076-4

DO - 10.1007/s00153-008-0076-4

M3 - Article

AN - SCOPUS:45049084674

SN - 0933-5846

VL - 47

SP - 159

EP - 180

JO - Archive for Mathematical Logic

JF - Archive for Mathematical Logic

IS - 2

ER -