On the complexity of learning minimum time-bounded Turing machines
On the complexity of learning minimum time-bounded Turing machines
复制标题
关于学习最小时间有限图灵机的复杂性
DOI：
--
复制
发表时间：
1990
期刊：
影响因子：
--
通讯作者：
K. Ko
中科院分区：
文献类型：
--
作者：
K. Ko
研究了时间有界程序规模复杂性的下列问题：（1）对于给定的字符串x，大小界s，时间界t，是否存在大小小于或等于s的图灵机使x在t中移动;（2）对于两个给定的有限字符串集合Y和Z、大小界限s和时间界限t，是否存在一个大小小于或等于s的图灵机，它在时间t内运行，并接受Y$中的所有y，拒绝Z$中的所有z。这些问题是复杂性理论和可行学习理论的基础。这些问题的复杂性显然介于P和$NP$之间，但似乎很难精确分类。这些问题是攻击的相对化的方法。结果表明，对于某些变化的问题，它们可以是多项式时间可计算的或不是多项式时间可计算的，这取决于不同的预言。此外，有预言相对于他们是不完整的$NP$下的多项式时间图灵红…
The following problems about time-bounded program-size complexity are studied: (1) for a given string x, a size bound s, and a time bound t, whether there exists a Turing machine of size less than or equal to s that prints x in t moves; (2) for two given finite sets Y and Z of strings, a size bound s, and a time bound t, whether there exists a Turing machine of size less than or equal to s that operates in time t and accepts all $y in Y$ and rejects all $z in Z$. These problems are fundamental in complexity theory and feasible learning theory. The complexity of these problems is apparently between P and $NP$, but appears very difficult to classify precisely. These problems are attacked by the approach of relativization. It is shown that for certain variations of the problems, they could be either polynomial-time computable or not polynomial-time computable, depending on different oracles. Furthermore, there are oracles relative to which they are not complete for $NP$ under the polynomial-time Turing red...