Computability and polynomial time computability

点击翻译按钮获取中文摘要

The field of recursion and polynomial-time computational complexity theories are closely related to a wide range of topics including set theory, complexity theory, learning theory, and probability methods for algorithms and quantum computing theory. Here we report our work ranging over these topics.The Computational complexity of Generalized Tsume-Shogi : The Generalized Tsume-Shogi problem uses the extended board of size n×n for a natural number n, rather than the usual 8×8 size. We show that solving GTS is EXPTIME-complete. As a corollary, Generalized Shogi is also proved to be EXPTIME-complete.Probability methods for algorithms : The number of outputs of randomly generated circuits of size n is shown to obey a normal distribution of mean n/3 and variance √<3n/45>.Learning 1 : We consider the problem of learning a consistent hypothesis of monotone Boolean conjunction of length O (logn), given negative examples of length n. This problem is shown to be computationally equivalent to the satisfiability problem of AND-OR-AND Boolean circuits having O ((logn)^2) inputs with respect to log-space many-one reducibility. Learning 2 : Applying the inclusion-exclusion principle, we show that the class of poly n-size DNF formula can be learnable within time 2^<0(√<n>)>. Moreover, this learning time is shown to be almost the best possible in the agnostic learning model.Learning 3 : Learning general Boolean functions depending on O(logn) variables is discussed. Three fast algorithms finding O(logn) relevant variables are presented.Y.Matsubara and S.Shelah proved that if λ is a strong limit singular cardinal then the non-stationary ideal over P_κλ is nowhere precipitous. They also proved that Means' Conjecture holds under the same hypothesis. T.〜Ishiu and Yoshinobu showed that for any infinite cardinal κ, every κ^+-strategically closed poset is κ^+-strategically closed if and only if square-κholds.