文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > The Non-Recursive Power of Erroneous Computation
侵权投诉

The Non-Recursive Power of Erroneous Computation

Abstract. We present two new complexity classes which are based on a complexity class C and an error probability function F. The first, F-Err C, reflects the (weak) feasibility of problems that can be computed within the error bound F. As a more adequate m

The Non-Recursive Power of Erroneous Computation Christian Schindelhauer; and Andreas Jakoby; 13 23

1 2

ICSI Berkeley, 1947 Center Street, Berkeley, U.S.A. schindel@icsi.berkeley.eduy Depart. of Computer Science, Univ. of Toronto, Canada jakoby@cs.toronto.edu 3 Med. Univ. zu Lubeck, Inst. fur Theoretische Informatik, Lubeck, Germany

complexity class C and an error probability function F . The rst, F -Err C, re ects the (weak) feasibility of problems that can be computed within the error bound F . As a more adequate measure to investigate lower bounds we introduce F -Errio C where the error is in nitely often bounded by the function F . These de nitions generalize existing models of feasible erroneous computations and cryptographic intractability. We identify meaningful bounds for the error function and derive new diagonalizing techniques. These techniques are applied to known time hierarchies to investigate the in uence of error bound. It turns out that in the limit a machine with slower running time cannot predict the diagonal 1 language within a signi cantly smaller error prob. than 2 . Further, we investigate two classical non-recursive problems: the halting problem and the Kolmogorov complexity problem. We present strict lower bounds proving that any heuristic algorithm claiming to solve one of these problems makes unrecoverable errors with constant probability. Up to now it was only known that in nitely many errors will occur.

Abstract. We present two new complexity classes which are based on a

1 Introduction The answer of the question whether NP equals P is a main goal of computational complexity theory. If they di er, which is the widely proposed case, a polynomial time bounded deterministic algorithm cannot correctly decide an NP -complete problem. Hence, the correctness of such an algorithm is the most reasonable requirement. Nevertheless, in the desperate situation where one wants to solve an infeasible problem one may accept errors, provided their in uence can be controlled somehow. The quality of such an error can be exploited in more detail. Probabilistic error: It is common sense that BPP can be seen as a class of e ciently solvable problems. Unlike an P -algorithm a BPP -algorithm can make errors, but on every input this error probability has to be bounded by 1 . So, BPP -algorithms can be modi ed to decrease this error probability to 3 an arbitrarily small non-zero polynomial. Furthermore, BPP -algorithms solve problems for which no P -algorithm is known yet, i.e. test of primalty. y

parts of this work are supported by a stipend of the\Gemeinsames Hochschulsonderprogramm III von Bund und Lander" through the DAAD.

第1页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email