Главная    Ex Libris    Книги    Журналы    Статьи    Серии    Каталог    Wanted    Загрузка    ХудЛит    Справка    Поиск по индексам    Поиск    Форум   
blank
Авторизация

       
blank
Поиск по указателям

blank
blank
blank
Красота
blank
Watanabe O. (ed.) — Kolmogorov Complexity and Computational Complexity
Watanabe O. (ed.) — Kolmogorov Complexity and Computational Complexity



Обсудите книгу на научном форуме



Нашли опечатку?
Выделите ее мышкой и нажмите Ctrl+Enter

Название: Kolmogorov Complexity and Computational Complexity

Автор: Watanabe O. (ed.)

Аннотация:

There are many ways to measure the complexity of a given object, but there are two measures of particular importance in the theory of computing: One is Kolmogorov complexity, which measures the amount of information necessary to describe an object. Another is computational complexity, which measures the computational resources necessary to recognize (or produce) an object. The relation between these two complexity measures has been studied since the 1960s. More recently, the generalized notion of resource-bounded Kolmogorov complexity and its relation to computational complexity has received much attention. Now many interesting and deep observations on this topic have been established. This book consists of four survey papers concerning these recent studies on resource-bounded Kolmogorov complexity and computational complexity. It also contains one paper surveying several types of Kolmogorov complexity measures. The papers are based on invited talks given at the AAAI Spring Symposium on Minimal-Length Encoding in 1990. The book is the only collection of survey papers on this subject and provides fundamental information for researchers in the field.


Язык: en

Рубрика: Математика/

Серия: Посвящена 110-летию со дня рождения Колмогорова Андрея Николаевича

Статус предметного указателя: Готов указатель с номерами страниц

ed2k: ed2k stats

Год издания: 1992

Количество страниц: 105

Добавлена в каталог: 31.05.2006

Операции: Положить на полку | Скопировать ссылку для форума | Скопировать ID
blank
Предметный указатель
$\leq^{P}_{m}$-complete for C      27
Admissible place selection      68
Advice function      48
Algorithmically random      see Random
Almost every language      50
Almost everywhere (a.e.)      47
Approximation space      89
Baire category      13
Borel - Cantelli Lemma      50
BP-operator      38
Bunch      89
Characteristic sequence      48
Characteristic string      47
Circuit      29; see $AC^{0}$ P/Poly
Ciruit, circuit complexity      10 17
Ciruit, circuit-size complexity      52
Ciruit, P-uniform circuit      18
Ciruit, polynomial-size circuit      29
Ciruit, self-producible circuit      30
Ciruit, uniform circuit      17 18
Collectives      67
Collision set      60
complete      48
Complete, NP-complete      27
Complexity core      57
Computation of an n - DS      49
Concordance relation      88
Consistent      56
Context-free language      10
Cryptographic protocols      79
Cylinder      48 67
Data compression      10
Dense      47
Dense, dense set      12 14 17
Dense, nowhere-dense set      13
density      12
Density, density function      49
Density, density system ($n$ - DS)      49
description      87
Description mode, acceptable mode of description      90 92
Description mode, complexity with respect to a description mode      87
Description mode, mode of description      87
Descriptional complexity      85
Dyadic rationale      48
Encoding      87
entropy      86
Entropy, $XY$ entropy      90
Entropy, decision entropy      96
Entropy, monotonic entropy      96
Entropy, prefix entropy      96
Entropy, priori entropy      96
Entropy, simple entropy      96
Equivalent, many-one equivalent      27
Equivalent, Turing equivalent      27
Extension function      13
Fast set      57
Frequentist's approach      67
Full range test      see Statistical test
Global value      49
hard      48
High      36
High, extended high      37
High, high hierarchy      36
Honest function      11
Immune, immune predicate      7 16
Immune, immune set      18
Incompressible by $\leq^{P}_{m}$-reductions      60
Infinitely often (i.o.)      47
Invariance Theorem      71
Invertible function      10 12
Kolmogorov      27
Kolmogorov complexity, $K^{L}$ complexity measure      6
Kolmogorov complexity, conditional Kolmogorov complexity      71
Kolmogorov complexity, generalized Kolmogorov class      27
Kolmogorov complexity, Kolmogorov complexity      85
Kolmogorov complexity, Kt-complexity      5
Kolmogorov complexity, small generalized Kolmogorov complexity      28
Kolmogorov complexity, space-bounded Kolmogorov complexity      45 51
Low      36
Low, exponentially low      37
Low, extended low      37
Low, low hierarchy      36
Martin - L$\ddot{o}$f      68 69 72 74
Measure 0 in ESPACE      50
Measure 1 in ESPACE      50
Modulus      50
NAME      87
NE predicate      7 10 12 16 18
Nonreduced image      60
Null cover      49
One-way function      10 12
Optimal      86
Optimal machine      51
Oracle      9 12 13 18 26
Oracle, generic oracle      13
Oracle, oracle set      26
Oracle, random oracle      12
P-convergent      50
P-printable set      9 18
Polynomial-time hierarchy, polynomial-time hierarchy      27
Polynomial-time hierarchy, polynomial-time hierarchy, relative to $A$      27
Predictors      80
PSPACE      49
Pspace, pspace computation of an $n$ - DS      49
Pspace, pspace-measure 0      50
Pspace, pspace-measure 1      50
Pspace, pspace-null cover      50
Pspace, quantitative probability      66
Random      87
Random, algorithmically random      34
Random, levels of randomness      69
Random, perfect pseudo-random number generator      81
Random, pseudo-random number generator      79
Random, random place selection      68
Random, random sequence      68
Random, random source      80
Random, SBK-random      69 76
Ranking functions      9
Reduction, reducibility, $k$-truth-table reducible      33
Reduction, reducibility, bounded truth-table reducible      33
Reduction, reducibility, many-one reducible      27
Reduction, reducibility, reduction      48
Reduction, reducibility, truth-table reducible      33
Reduction, reducibility, Turing reducible      26
Relativized computation      9 12 13 18
Resource-bounded measure      45 49
Search problem      7
Self-p-printable      28
Set covered by a density function      49
Shannon effect      52
Solomonoff - Kolmogorov Theorem      87
Space constructible      76
sparse      25 47
Sparse, co-sparse      47
Sparse, sparse set      9 12
Statistical test      11 69 72 80
Statistical test, full range test      73
Statistical test, Martin - L$\ddot{o}$f statistical test      81
Statistical test, universal test      69 74 75 76
Statistical test, Yao statistical test      81
tally      25
Tally, tally set      9 17 19
Tangible set      9
TREE      89
Typical sequences      87
Unambiguous context-free language      10
Universal test      see Statistical test
Upward measure separation theorem      53
Ville      68
Von Mises      67 68
Wald      68
Weakly invertible function      11
Yao      80 (see also Statistical test)
blank
Реклама
blank
blank
HR
@Mail.ru
       © Электронная библиотека попечительского совета мехмата МГУ, 2004-2024
Электронная библиотека мехмата МГУ | Valid HTML 4.01! | Valid CSS! О проекте