Computability and polynomial time computability

递归和多项式时间计算复杂性理论领域与广泛的主题密切相关，包括集合论、复杂性理论、学习理论、算法的概率方法和量子计算理论。在这里，我们报告我们在这些主题上的工作。广义Tsume-Shogi问题的计算复杂性：广义Tsume-Shogi问题使用大小为n×n的扩展板来表示自然数n，而不是通常的8×8大小。我们证明求解GTS是exptime完备的。作为推论，也证明了广义Shogi是exptime完备的。算法的概率方法：大小为n的随机生成电路的输出个数服从均值n/3，方差√<3n/45>的正态分布。学习1：我们考虑学习长度为O （logn）的单调布尔合的一致假设的问题，给出长度为n的负例子。这个问题被证明在计算上等同于具有O （(logn)^2）输入的与或与布尔电路关于对数空间多一可约性的可满足性问题。学习2：应用包含-不排除原理，我们证明了在2^<0(√<n>)>时间内可以学习聚n大小的DNF公式类。此外，在不可知论学习模型中，这个学习时间几乎是最好的。学习3：学习依赖于O（logn）变量的一般布尔函数。提出了三种求O（logn）个相关变量的快速算法。y . matsubara和S.Shelah证明了如果λ是强极限奇异基数，则P_κλ上的非平稳理想是不陡峭的。他们还证明了Means猜想在相同的假设下成立。T. ~ Ishiu和Yoshinobu证明了对于任意无限基数κ，当且仅当平方κ成立时，每个κ^+-策略闭序集都是κ^+-策略闭序集。

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.