Abstract

BackgroundResults on Non-Existence

Results on ExistenceJump and a Problem

Summary

References

Forcing Complexity
Toshio Suzuki1
Tokyo Metropolitan University
toshio-suzuki•tmu.ac.jp (•=atmark)A joint work with Masahiro Kumabe
ELC Workshop on Randomness and Probability Through Computability
Hongo Campus, The Univerisity of Tokyo, Japan

14 May 2013
1

This work was partially supported by Japan Society for the Promotion ofScience (JSPS) KAKENHI (C) 22540146 and (B) 19340019.
1 / 22

Abstract

BackgroundResults on Non-Existence

Results on ExistenceJump and a Problem

Summary

References

Abstract
We overview our research on forcing complexity:• Forcing complexity (of a given formula)= Min. size of forcing conditions (its domain) which force it.
• A Dowd-generic set⇔ A set of strings s.t. associated query formulas havesmall forcing complexity (We will show precise def. later.)"⇔ A resource-bounded generic set of Ambos-Spies et al.
• Connections with:resource-bounded randomness
computational complexity
2 / 22

Abstract

BackgroundResults on Non-Existence

Results on ExistenceJump and a Problem

Summary

References

OutlineAbstract
BackgroundResults on Non-Existence
Results on ExistenceJump and a Problem
Summary
References

3 / 22

Abstract

BackgroundResults on Non-Existence

Results on ExistenceJump and a Problem

Summary

References§1 BackgroundDef. Resource-bounded randomness (Ambos-Spies et al.)t(n)-random# random for O(t(n))-time computable martingales.

Two Types of Resource-bounded Genericity• [Ambos-Spies and Mayordomo 1997],[Ambos-Spies, Terwijn, and Zheng 1997]:
Time-bound of finite-extension strategy.
t(n)-random ⇒ t(n)-stochastic ⇒ t(n)-generic.
• [Dowd 1992]: Based on analogy of forcing theorem.
[Kumabe and S.]: There exists an elementary recursive t(n) s.t.
t(n)-random ⇒ Dowd-generic.
4 / 22

Abstract

BackgroundResults on Non-Existence

Results on ExistenceJump and a Problem

SummaryReferences§1 Background
Dowd introduced the following in his study of NP=?coNP question.

Def. of Dowd-generic sets (sketch)“A certain property∗ of an exponential-sized portion of an oracle X
is forced by a polynomial-sized portion of X . ”“A certain property” is described withthe relativized propositional calculus (RPC).
RPC =( propositional caluculus )+ {ξ 1 (−), ξ 2 (−, −), ξ 3 (−, −, −), · · · }For each n, the n-ary connective
ξ n (a query symbol ) is interpreted tothe initial segment of a given oracle up to 2n th string.
5 / 22

Abstract

BackgroundResults on Non-Existence

Results on ExistenceJump and a Problem

SummaryReferences§1 Background
Example of a formula of RPC(q0 ⇔ ξ 3 (q1 , q2 , q3 )) ⇒ [q0 ∨ (q1 ∧ q4 )]Given a formula F of RPC and an oracle X , truth of F isdetermined by “a truth assignment + a finite portion of X ”.
Interpretation:ξ n (i th of {0, 1}n ) is interpreted as to be X (i th of {0, 1}∗ ),where “i th” is that of length-lexicographic order.

6 / 22

Abstract

BackgroundResults on Non-Existence

Results on ExistenceJump and a Problem

Summary

References§1 Backgroundξ n (i th of {0, 1}n ) is interepreted as to be X (i th of {0, 1}∗ ).
Examples (n = 2 and n = 3)
ξ 2 (0, 0)
X (empty string)ξ 2 (0, 1)
X (0)ξ 2 (1, 0)
X (1)ξ 2 (1, 1)
X (00)

ξ 3 (0, 0, 0)
X (empty string)ξ 3 (0, 0, 1)
X (0)ξ 3 (0, 1, 0)
X (1)ξ 3 (0, 1, 1)
X (00)

ξ 3 (1, 0, 0)
X (01)

ξ 3 (1, 0, 1)
X (10)

ξ 3 (1, 1, 0)
X (11)

ξ 3 (1, 1, 1)
X (000)Thus, ξ 2 (q2 , q1 ) and ξ 3 (0, q2 , q1 ) are interpreted as to be the same.
7 / 22

Abstract

BackgroundResults on Non-Existence

Results on ExistenceJump and a Problem

SummaryReferences§1 BackgroundDef. ForceA finite portion σ (a finite sub-function) of an oracle X is called aforcing condition.
σ forces F if for any Y extending σ, F is a tautology w. r. t. Y .

Example of force
Let F be: (q0 ⇔ ξ 3 (q1 , q2 , q3 )) ⇒ ¬q0
F is a tautology w. r. t. the characteristic func. of the empty set.
If σ forces F then the size of σ (its domain) ≥ 23 .
(And, the first 23 bits of σ should be 0.)

8 / 22

Abstract

BackgroundResults on Non-Existence

Results on ExistenceJump and a Problem

SummaryReferences§2 Results on Non-Existence
The case of unbounded occurrences of query symbols

Definition. t-generic sets [Dowd 1992]
X is t-generic if every tautology F with respect to X is forced by aforcing condition of polynomial-size in |F |.

Thm. Non-existence of t-generic sets [Dowd, 1992], [S. 2001]
There are no t-generic sets.
Dowd, M.: Generic oracles, uniform machines, and codes.
Inf. Comput., 96, pp. 65–76 (1992).
S.: Forcing complexity: minimum sizes of forcing conditions.
Notre Dame J. Formal Logic, 42, pp. 117–120 (2001).
9 / 22

Abstract

BackgroundResults on Non-Existence

Results on ExistenceJump and a Problem

SummaryReferences§3 Results on Existence
The case of bounded occurrences of query symbols:
Here, r -query denotes “the # of occurrences of query symbols is r .”Def. Dowd-generic sets [Dowd, 1992]• Let r be a positive integer.
X is r -Dowd
if every r -query tautology F w. r. t. X
is forced by a forcing condition of polynomial-size in |F |.
• X is Dowd-genericif X is r -Dowd for every positive integer r .
(Polynomial bound depends on each r , unlike t-genericity)

10 / 22

Abstract

BackgroundResults on Non-Existence

Results on ExistenceJump and a Problem

SummaryReferences§3 Results on Existence
Thm. Existence of Dowd-generic sets
• [Dowd, 1992], [S.2001], [S.2002]
The class of all Dowd-generic sets has Lebesgue measure 1.
• [S. and Kumabe, 2009] Schnorr random ⇒ Dowd-generic.
S.: Degrees of Dowd-type generic oracles.
Inf. Comput., 176, pp.66–87 (2002).
S. and Kumabe, M.: Weak randomness, genericity and Boolean
decision trees.
Proc. 10th Asian Logic Conference, pp.322–344, 2009.

11 / 22

Abstract

BackgroundResults on Non-Existence

Results on ExistenceJump and a Problem

SummaryReferences§3 Results on Existence[Dowd 1992] asserts “any 1-Dowd set is not c.e.” (false)

Thm. Degrees of Dowd-generic sets
• [S. 2002] There exists a primitive recursive 1-Dowd set.
And, every Turing degree contains a 1-Dowd set.
• [Kumabe and S. 2012]
The same holds for “Dowd-generic” in place of “1-Dowd”.
Kumabe, M. and S.:
Computable Dowd-generic oracles.
Proc. 11th Asian Logic Conference, pp.128–146, 2012.

12 / 22

Abstract

BackgroundResults on Non-Existence

Results on ExistenceJump and a Problem

SummaryReferences§3 Results on Existence
Thm. Resouce-bounded ramdomness implies Dowd-genericity[Kumabe and S. ∞]There exists an elementary recursive function t(n) s.t.
t(n)-random ⇒ Dowd-generic.
Gives an alt. proof: ∃ a primitive recursive Dowd-generic set.
Kumabe, M. and S. :Resource-bounded martingales and computable Dowd-type genericsets. submitted to a journal (2010).

13 / 22

Abstract

BackgroundResults on Non-Existence

Results on ExistenceJump and a Problem

SummaryReferences§3 Jump and a Problem
Let 1TAUTX denote the set of all 1-query tautologies w. r. t. X .
Question: Does 1TAUTX has a degree strictly higher than X ?
Given a reduction concept ≤r (e.g., poly.-time Turing ≤PT ),we introduce the following statement, and we call it“One-query jump hypothesis w. r. t. ≤r ” (1QJH(r ), for short).

Def. One-query Jump Hypothesis w. r. t. ≤r“The class {X : X <r 1TAUTX }in the Cantor space”.

[S. 2002]

has Lebesgue measure 114 / 22

Abstract

BackgroundResults on Non-Existence

Results on ExistenceJump and a Problem

SummaryReferences§3 Jump and a Problem
Thm. [S. 1998]
1QJH(poly.-time Turing)⇔RP "= NP.

Here, RP is the one-sided version of BPP.

Thm. [S. 2002]
1QJH(poly.-time truth table) ⇒ P "= NP.
S.: Recognizing tautology by a deterministic algorithm whose
while-loop’s execution time is bounded by forcing.
Kobe Journal of Mathematics, 15, pp. 91–102 (1998).

15 / 22

Abstract

BackgroundResults on Non-Existence

Results on ExistenceJump and a ProblemSummaryReferences§3 Jump and a Problem
Examples of 1QJH

[Kumabe, S. and Yamazaki 2008](1) 1QJH(monotone reductions) holds.
(tt-reductions s.t. truth tables are monotone Boolean formulas.)(2) c < 1 ⇒ 1QJH(tt-reductions s.t. norm ≤ c × |F |) holds.
(F is an input formula and |F | = # of occurrences of symbols.)

Problem
In (2), can we relax the assumption of “c < 1”?
Kumabe, M., S. and Yamazaki, T.: Does truth-table of linear norm
reduce the one-query tautologies to a random oracle? Arch. Math.
Logic, 47, pp.159–180 (2008).
16 / 22

Abstract

BackgroundResults on Non-Existence

Results on ExistenceJump and a Problem

Summary

References

Summary§1 Results on Non-Existence (Thm. [Dowd 1992], [S. 2001])
No t-generic sets (No poly.-bound on forcing complexity when
unbounded occurrences of query symbols).

§2 Results on Existence (Def.)(1) r -Dowd ↔ poly.bound on forcing comp. for r -query tautologies(2) Dowd-generic ↔ ∀r ≥ 1 r -Dowd§2 (Thm. [Kumabe and S., ∞])There exists an elementary recursive function t(n) s.t.
t(n)-random ⇒ Dowd-generic.
(Hence ∃ a primitive recursive Dowd-generic set.)
17 / 22

Abstract

BackgroundResults on Non-Existence

Results on ExistenceJump and a Problem

Summary

References

Summary§3 Jump and a Problem (Def.)

1QJH(r ): “ {X : X <r 1TAUTX } has Lebesgue measure 1”.

§3 (Thm. [Kumabe, S. and Yamazaki 2008])(1) 1QJH(monotone reductions) holds.
(2) c < 1 ⇒ 1QJH(tt-reductions s.t. norm ≤ c × |F |) holds.
(F is an input formula and |F | = # of occurrences of symbols.)§3 (Problem)
In (2), can we relax the assumption of “c < 1”?

18 / 22

Abstract

BackgroundResults on Non-Existence

Results on ExistenceJump and a Problem

Summary

References

Thank you.

19 / 22

Abstract

BackgroundResults on Non-Existence

Results on ExistenceJump and a Problem

Summary

References

References
Arora, S. and Barak, B.: Computational Complexity,Cambridge university press, New York, 2009.
Ambos-Spies,K. and Mayordomo, E.: Resource-boundedmeasure and randomness. In: Lecture Notes in Pure and Appl.
Math., 187, 1–47 Dekker, 1997.
Ambos-Spies,K., Terwijn, S.A. and Zheng,X. : Resourcebounded randomness and weakly complete problems.
Theoret. Comput. Sci., 172 (1997) 195–207.
Dowd, M.: Generic oracles, uniform machines, and codes.
Inf. Comput., 96, pp. 65–76 (1992).
Kumabe, M. and Suzuki, T. : Computable Dowd-genericoracles. Proc. 11th Asian Logic Conference, pp.128–146,
World Scientific, 2012.

20 / 22

Abstract

BackgroundResults on Non-Existence

Results on ExistenceJump and a Problem

Summary

References

Kumabe, M. and Suzuki, T. : Resource-bounded martingales
and computable Dowd-type generic sets, submitted to ajournal (2010).
Kumabe, M., Suzuki, T. and Yamazaki, T.: Does truth-tableof linear norm reduce the one-query tautologies to a random
oracle? Arch. Math. Logic, 47, pp.159–180 (2008).
Suzuki, T.: Recognizing tautology by a deterministic algorithm
whose while-loop’s execution time is bounded by forcing.
Kobe Journal of Mathematics, 15, pp. 91–102 (1998).
Suzuki, T.: Computational complexity of Boolean formulaswith query symbols. Doctoral dissertation, Institute ofMathematics, University of Tsukuba, Tsukuba-City, Japan(1999).
Suzuki, T.: Complexity of the r-query tantologies in thepresense of a generic oracle.
Notre Dame J. Formal Logic, 41, pp. 142–151 (2000).
21 / 22

Abstract

BackgroundResults on Non-Existence

Results on ExistenceJump and a Problem

Summary

References

Suzuki, T.: Forcing complexity: minimum sizes of forcing
conditions.
Notre Dame J. Formal Logic, 42, pp. 117–120 (2001).
Suzuki, T.: Degrees of Dowd-type generic oracles.
Inf. Comput., 176, pp.66–87 (2002).
Suzuki, T.: Bounded truth table does not reduce theone-query tautologies to a random oracle.
Arch. Math. Logic, 44, pp.751–762 (2005).
Suzuki, T. and Kumabe, M.: Weak randomness, genericity
and Boolean decision trees.
Proc. 10th Asian Logic Conference, pp.322–344, World
Scientific, 2009.
Toshio Suzuki URI:
http://researchmap.jp/read0021048/?lang=english
22 / 22