On Optimal Algorithms and Optimal Proof Systems
On Optimal Algorithms and Optimal Proof Systems
复制标题
DOI：
10.1007/3-540-49116-3_51
复制
发表时间：
1999-03
期刊：
影响因子：
--
通讯作者：
J. Messner
中科院分区：
文献类型：
--
作者：
J. Messner
一个接受语言L的确定性算法O被称为（多项式）最优的，如果对于任何接受L的算法A，存在一个多项式p使得timeo（x）≤p（|X| + timeA（x））。证明了语言L存在最优接受者，如果存在L的p-最优证明系统.如果L是一个p-柱面，则逆蕴涵也成立。这一结果广泛地推广了Krají的工作|>cek和Pudlák给出了L = TAUT的结果。它进一步表明如何构建一个最佳的受体的p-cylinderL，给定一个受体的L上运行快的每一个容易的子集L。然后，我们调查的关系，这一概念的“最佳受体”的最优性的一个更一般的概念。这里，我们考虑的不是每个字符串的时间复杂度，而是最坏情况下的时间界限。据观察，每一套完整的指数时间下的线性长度有界的多项式时间多-一reductions有一个接受者的最佳时间范围，而另一方面，没有一套困难的指数时间下的多项式时间多-一reductions有一个p-最优的证明系统。最后，我们将展示如何将这些结果转化为不确定性算法和最优证明系统。
A deterministic algorithmOaccepting a languageLis called (polynomially) optimal if for any algorithmAacceptingLthere is a polynomialpsuch that timeo(x)≤p(|x| + timeA(x)) for everyx ∈ L. It is shown that an optimal acceptor for a languageLexists if there is a p-optimal proof system forL. IfLis a p-cylinder also the inverse implication holds. This result widely generalizes work from Krají|>cek and Pudlák who showed the result forL = TAUT. It is further shown how to construct an optimal acceptor for a p-cylinderL, given an acceptor forLwhich runs fast on every easy subset ofL. Then we investigate the relationship of this notion of an ‘optimal acceptor’ to a more general notion of optimality. Here, instead of considering time-complexity on each individual stringx, worst-case time-bounds are considered. It is observed that every set complete for exponential time under linearly length-bounded polynomial-time many-one reducibility has an acceptor with an optimal time-bound whereas on the other hand no set hard for exponential time under polynomial-time many-one reducibility has a p-optimal proof system. Finally we show how these results can be translated to nondeterministic algorithms and optimal proof systems.