Recognizing tautology by a deterministic algorithm whose while-loop's execution time is bounded by forcing
Toshio Suzuki · Institutional Repositories DataBase (IRDB) · 1998
By Bennet and Gill [4], it is shown that if A is a random oracle then TAUTA / ∈ PA with probability 1, where TAUTA denotes the collection of all tautologies relative to A. Extending Dowd’s work [6], we present a forcing argument to bound execution time of a while-loop of a deterministic algorithm, by which we show that for each positive integer r, if A is an r-generic oracle in the sense of Dowd then rTAUTA≡PT TAUT ⊕ A, where rTAUTA denotes the collection of all r-query tautologies with respect to A. As a consequence, the following two assertions are equivalent: (i) if A is a random oracle then rTAUTA / ∈ PA with probability 1, (ii) R 6 = NP. 1