Kolmogorov complexity and non-determinism

被引：0
|
作者：
Grigorieff, S
Marion, JY
机构：
[1] Univ Paris 07, UFR Informat, F-75251 Paris 05, France
[2] Univ Clermont Ferrand, Lab LLAIC, Clermont Ferrand, France
[3] Univ Nancy 2, LORIA, Calligramme Project, F-54506 Vandoeuvre Les Nancy, France
来源：
THEORETICAL COMPUTER SCIENCE | 2002年 / 271卷 / 1-2期
关键词：
Kolmogorov complexity;
D O I：
10.1016/S0304-3975(01)00038-X
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We are concerned with Kolmogorov complexity of strings produced by non-deterministic algorithms. For this, we consider five classes of non-deterministic description modes: (i) non-bounded description modes in which the number of outputs depends on programs, (ii) distributed description modes in which the number of outputs depends on the size of the outputs, (iii) spread description modes in which the number of outputs depends on both programs and the size of the outputs., (iv) description modes for which each string has a unique minimal description, and lastly (v) description modes for which the set of minimal length descriptions is a prefix set. (C) 2002 Elsevier Science B.V. All rights reserved.
引用
收藏
页码：151 / 180
页数：30
相关论文
共 50 条
  • [1] Kolmogorov complexity and nondeterminism versus determinism for polynomial time computations
    Hromkovic, Juraj
    THEORETICAL COMPUTER SCIENCE, 2024, 1013
  • [2] Kolmogorov-Loveland Stochasticity and Kolmogorov Complexity
    Bienvenu, Laurent
    THEORY OF COMPUTING SYSTEMS, 2010, 46 (03) : 598 - 617
  • [3] Kolmogorov-Loveland Stochasticity and Kolmogorov Complexity
    Laurent Bienvenu
    Theory of Computing Systems, 2010, 46 : 598 - 617
  • [4] Kolmogorov complexity and noncomputability
    Davie, G
    MATHEMATICAL LOGIC QUARTERLY, 2002, 48 (04) : 574 - 580
  • [5] Kolmogorov complexity of categories
    Department of Computer and Information Science, Brooklyn College, CUNY, Brooklyn, NY 11210, United States
    不详
    Lect. Notes Comput. Sci., 2013, (350-362): : 350 - 362
  • [6] Approximating Kolmogorov complexity
    Ishkuvatov, Ruslan
    Musatov, Daniil
    Shen, Alexander
    COMPUTABILITY-THE JOURNAL OF THE ASSOCIATION CIE, 2023, 12 (03): : 283 - 297
  • [7] Kolmogorov complexity and cryptography
    Muchnik, Andrej A.
    PROCEEDINGS OF THE STEKLOV INSTITUTE OF MATHEMATICS, 2011, 274 (01) : 193 - 203
  • [8] Axiomatizing Kolmogorov Complexity
    Antoine Taveneaux
    Theory of Computing Systems, 2013, 52 : 148 - 161
  • [9] Kolmogorov complexity and cryptography
    Andrej A. Muchnik
    Proceedings of the Steklov Institute of Mathematics, 2011, 274 : 193 - 203
  • [10] Axiomatizing Kolmogorov Complexity
    Taveneaux, Antoine
    THEORY OF COMPUTING SYSTEMS, 2013, 52 (01) : 148 - 161
12345