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

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

blank
blank
blank
Красота
blank
Zimand M. — Computational Complexity: A Quantitative Perspective
Zimand M. — Computational Complexity: A Quantitative Perspective

Читать книгу
бесплатно

Скачать книгу с нашего сайта нельзя

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



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


Название: Computational Complexity: A Quantitative Perspective

Автор: Zimand M.

Аннотация:

There has been a common perception that computational complexity is a theory of "bad news" because its most typical results assert that various real-world and innocent-looking tasks are infeasible. In fact, "bad news" is a relative term, and, indeed, in some situations (e.g., in cryptography), we want an adversary to not be able to perform a certain task. However, a "bad news" result does not automatically become useful in such a scenario. For this to happen, its hardness features have to be quantitatively evaluated and shown to manifest extensively.

The book undertakes a quantitative analysis of some of the major results in complexity that regard either classes of problems or individual concrete problems. The size of some important classes are studied using resource-bounded topological and measure-theoretical tools. In the case of individual problems, the book studies relevant quantitative attributes such as approximation properties or the number of hard inputs at each length.

One chapter is dedicated to abstract complexity theory, an older field which, however, deserves attention because it lays out the foundations of complexity. The other chapters, on the other hand, focus on recent and important developments in complexity. The book presents in a fairly detailed manner concepts that have been at the centre of the main research lines in complexity in the last decade or so, such as: average-complexity, quantum computation, hardness amplification, resource-bounded measure, the relation between one-way functions and pseudo-random generators, the relation between hard predicates and pseudo-random generators, extractors, derandomization of bounded-error probabilisticalgorithms, probabilistically checkable proofs, non-approximability of optimization problems, and others.

The book should appeal to graduate computer science students, and to researchers who have an interest in computer science theory and need a good understanding of computational complexity, e.g., researchers in algorithms, AI, logic, and other disciplines.

· Emphasis is on relevant quantitative attributes of important results in complexity.
· Coverage is self-contained and accessible to a wide audience.
· Large range of important topics including: derandomization techniques, non-approximability of optimization problems, average-case complexity, quantum computation, one-way functions and pseudo-random generators, resource-bounded measure and topology.


Язык: en

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

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

ed2k: ed2k stats

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

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

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

Операции: Положить на полку | Скопировать ссылку для форума | Скопировать ID
blank
Предметный указатель
#P      128
$(\dot, \dot)$      111
$(\epsilon, S)$-hard function      154
$ACC(V^w(x))$      269
$ACC_{V(P_1,P_2,...,P_p)}(x)$      271
$ACG_v(x)$      271
$C_{not}$      116
$f_l$      144
$G_{\sigma}$      134
$K_4$      97
$MIP_1$      271
$NP^A$      85
$PCP_{c(n),s(n)}[r(n), q(n)]$      269
$P^A$      85
$U_n$      147
$x \dot y$      144
$x \odot y$      144
$x\circ y$      301
$\alpha$-cover      17 20
$\delta$-biased random variable      293
$\delta$-close functions      299
$\Gamma$-measure, one      21
$\Gamma$-measure, zero      21
$\Gamma$-uniform union      22
$\models$      232
$\mu *\leq\nu *$      98
$\omega(G)$      282
$\oplus$      81
$\Prod_n$ formula      243
$\Sigma *$      13 60
$\sigma$-field      15
$\Sigma^{\infty}$      13 60 86
$\Sigma_n$ formula      243
$\sqsubseteq$      26
$\|A\|$      13
$|0\rangle$      111
$|1\rangle$      111
1-wise $\epsilon$-independent random variable      293
3-SAT      55 296
a.e.      4
Abstract complexity      25 49
Abstract complexity measure      25
ACC(V(x))      269
Acceptable godelization      5 43
Accepting state      2
Adversary      145 153
Ajtai, M.      315
Alexi, W.      222
Alon, N.      316
Ambainis, A.      141
Ambos-Spies, K.      107
Amplitude      110
Approximation algorithm      226
Approximation ratio      226
APX      227 252 265 313
Arithmetic hierarchy      61
Arithmetic hierarchy, $\Prod_2$      4 61
Arithmetic hierarchy, $\Sigma_2$      4 61
Arithmetization      296
Arity of a relation      231
Arora, S.      315
Average-case complexity      92
Average-case reduction      98
Axiom      37
Babai, L.      223 315
Baire category theorem      12 13
Baire category, first      12 28 37 38 43 70
Baire category, second      12 28 36 38 39 62 64 66 69
Baire classification      12
Baire classification, superset topology      61
Baker, T.      107
Ball      164
Ballot Theorem      57
Barenco, A.      116 127 140
Base, topological      12
Beaver, D.      223
Ben-Or, M.      315
Benioff, P.      140
Bennett, C      107 140
Berlekamp, E.      223
Bernstein, E.      140
BH      101
Bit      110
Black Box      128
Blum axioms      25 42 43 49
Blum space      26 28 36 37 45 47 48
Blum, L.      222
Blum, M.      30 37 49 222 224
Borel set      15
Borel — Cantelli lemma      88 137
Borodin, A.      49
Bounded halting problem      101
bpp      9 209 221 223
BQP      127 140
Bra/ket notation      111
Brainerd, W.      50
Brassard, G.      141
Cai, J.-Y.      222
Calude, C      5 50
Cantor topology      13—15 26 28 60
Central limit theorem      317
Cheatable set      74
Chebyshev’s inequality      167 186 318
Chernoff bounds      125 318
Chernoff bounds, additive      150 194 320
Chernoff bounds, multiplicative      183 187 193 202 319
Chor, B.      222 224
Chung, F.      315
Church — Turing thesis      1
Chvatal, V.      313
Circuit      9
Circuit, boolean      9
Circuit, family of circuits      10
Circuit, size      10
Clause      55
Cleve, R.      140
Clique number      282
Closed formula      232
Closure under finite variations      22
Co-FIN      61
Co-meagre set      12
Co-nowhere dense set      12
Codeword      164
Collision      135
COLORABILITY problem      96
COMP      4
Complexity class      6 28 43 47
Complexity measure      25
Compression theorem      42 43 49
Computable function      4
Computation tree      3
Computational distance      147 148 172 211 222
Computationally close distributions      149
Condon, A.      313
Configuration of a classical computer      110
Configuration of a Turing machine      2 105
Configuration symbol      234
Conjunctive normal form      55
CONSISTENCY TEST      302
Constable, R.      49
Controlled-NOT transformation      116
Cook reducibility      53
Cormen, T.      313
Countably additive      16
Countably subadditive      134
Crypto-hard function      154
Cylinder      134
Cylinder set      16
D-BH      101 102
D-PC      103
d-regular graph      284
de Moivre — Laplace theorem      317
Decision problem      231
Deduction rule      37
Deductive system      37
Deductive system, sound      37 38 70
Delayed diagonalization      107
Density function      93
Descriptive complexity      313
Design      200 201 214
Design, (weight l, intersection $\alpha$)      201
Deterministic Turing machine      2
Deutsch, D.      140 141
Dime, W.      222
Direct product      191 197
Discrete log problem      146 222
DistNP      98 102 103
distribution      93
Distribution function      92
Distributional bounded halting problem      101
Distributional Post correspondence problem      103
Distributional problem      93
DiVicenzo, D.      140
Domain of a structure      231
Domination      98
DSPACE[f(n)]      6
DTIME[f(n)|      6
Duality theorem      259
Dyadic rational number      22
D—3COL      96
e      8 71 72
Easily approximable set      74
Easily countable set      74
Effective Baire classification      27
Effectively enumrable set      37
Effectively first Baire category set      27
Effectively first Baire category set, superset topology      61
Effectively nowhere dense set      27
Effectively nowhere dense set, superset topology      61
Effectively second Baire category set      27
Effectively second Baire category set, superset topology      61
Eigenvalue      284
Eigenvector      284
Engebretsen, L.      315
Ensemble of functions      145
Entangled states      115
Entropy function      59
Error-correcting code      164 182 199 215
Error-correcting code, decoding property      164
Error-correcting code, list decoding      165
Error-correcting code, list-decoding      199 223
EXP      8
Expander graph      284 284 315
Exponentially hard function      155
Extender      161 163 170—172 200
Extender, ensemble      161
Extension of a pseudo-random generator      149
extractor      156 211
Fagin, R.      313
Feasible solution      225
Feige, U.      272 313
Feigenbaum, J.      223
Fenner, S.      107
Feynman, R.      109 140
Finite structure      231
Finitely additive      16 134
First Baire category      27
First-order logic      231
First-order logic, $\Prod_2$ logical formula      232
Fischer, P.      49
Fortnow, L.      223 315
Fourier transform      294
FPC      5
FPRED      28
Free variable      232
Freivalds, R.      141
Fully space-constructible function      7 42
Fully time-constructible function      7
Function effectively computed from another function      152
Function oracles      128
FUNCTION SAT      273
Function, length-preserving      144
Function, length-regular      144
Gabber, O.      284 315
Galil, Z.      284 315
Gap theorem      39 42 49
GAP($\Phi$, F)      39
Gate      9
Gemmel, P.      223
GF(2)      144
Gill, J.      107
Goldreich, O.      108 222—224 316
Goldwasser, S.      222 223 313 315
Grigoriev, D.      223
Grover, L.      128 141
Gurevich, Y.      108
Had(x)      165
Hadamard error-correcting code      165 199 218 220
Hadamard error-correcting code, list decoding      165
Hadamard transformation      113 130
Halting problem      10
Hamming distance      57 164 183
Hard function      153 154 179
Hard function, constant-rate      154
Hard function, cryptographically      154
Hard function, exponentially      155
Hard function, hardness amplification      179 191 196
Hard function, worst-case      154 180
Hard function, worst-case hard      208
Hard predicate      153 155 197 198 200 206
Hard predicate, crypto-hard      198
Hard predicate, exponentially hard      198 200
HARD($\Phi$, g)      29 36 47
Hard-core predicate      162 162 163—165 169
Hartmanis, J.      49 50
Hastad, J.      152 223 287 315 316
Hellman, M.      222
Hemaspaandra, E.      141
Hemaspaandra, L.      107 141
Hidden bit      162
Hierarchy theorems      7
Hochbaum, D.      313
Holmerin, J.      315
Hopcroft, J.      50
Hoyer, P.      141
Hybrid distributions      172 176 203
Hybrid method      172
I.o.      4
Impagliazzo, R.      152 223 315
Imrnerman, N.      313
INDEPENDENT SET-B      256
Inner product      111 144 165 293
Input alphabet      2
Integer factoring      146 222
Interactive protocol, completeness      269 269
Interactive protocol, soundness      269 269
Interpretation      231
IP      315
Istrate, G.      50
Johnson, D.      313
Jozsa, R..      141
Kaltofen, E.      223
Karloff, H.      315
Karp reducibility      53
Kautz, S.      107
Kilian, J.      315
Knuth, D.      222
Kolaitis, P.      313
Kolmogorov 0-1 law      16
Komlos, J.      315
1 2 3
blank
Реклама
blank
blank
HR
@Mail.ru
       © Электронная библиотека попечительского совета мехмата МГУ, 2004-2017
Электронная библиотека мехмата МГУ | Valid HTML 4.01! | Valid CSS! О проекте