Extending techniques of Dowd and those of Poizat, we study computational complexity of in the case when is a generic oracle, where is a positive integer, and denotes the collection of all -query tautologies with respect to an oracle . We introduce the notion of ceiling-generic oracles, as a generalization of Dowd's notion of -generic oracles to arbitrary finitely testable arithmetical predicates. We study how existence of ceiling-generic oracles affects behavior of a generic oracle, by which we show that is (...) not a subset of is comeager in the Cantor space. Moreover, using ceiling-generic oracles, we present an alternative proof of the fact (Dowd) that the class of all -generic oracles has Lebesgue measure zero. (shrink)

We consider minimal ranks of extenders associated with Shelah cardinals by introducing witnessing numbers. Using these numbers we shall investigate effects of Shelah cardinals above themselves. MSC: 03E55.

This note is a continuation of our former paper ''Complexity of the r-query tautologies in the presence of a generic oracle.'' We give a very short direct proof of the nonexistence of t-generic oracles, a result obtained first by Dowd. We also reconstitute a proof of Dowd's result that the class of all r-generic oracles in his sense has Lebesgue measure one.

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. (shrink)

The relativized propositional calculus is a system of Boolean formulas with query symbols. A formula in this system is called a one-query formula if the number of occurrences of query symbols is just one. If a one-query formula is a tautology with respect to a given oracle A then it is called a one-query tautology with respect to A. By extending works of Ambos-Spies (1986) and us (2002), we investigate the measure of the class of all oracles A such that (...) the set of all one-query tautologies with respect to A does not p-btt-reduce to A, where p-btt denotes polynomial-time bounded-truth-table. We show that certain Dowd-type generic oracles all belong to the class, and hence measure of the class is one. (shrink)