|
|
 |
| Авторизация |
|
|
|
| Поиск по указателям |
|
|
|
|
|
|
|
 |
|
|
|
| Sipser M. — Introduction to the theory of computation |
|
|
|
| Предметный указатель |
Edge of a graph 10
Edmonds, Jack 416
Element distinctness problem 147
Element of a set 3
Emptiness testing for CFG. 171
Emptiness testing for DFA 168
Emptiness testing for LBA 195
Emptiness testing for TM 189
Empty set 4
Empty string 13
Encoding 157 259
Enderton, Herbert B. 416
Enumerator 152—153
Equality operation 15
Equivalence relation 9
Equivalent machines 54
Erdos, Paul 415
Error probability 369
Euclidean algorithm 261
Even, Shimon 416
Exclusive or operation 15
Existential state 381
Exponential bound 250
Exponential, versus polynomial 257
EXPSPACE 340
EXPSPACE-completeness 343—349
EXPTIME 308
Factor of a number 371
Feller, William 416
Fermat test 372
Fermat’s Little Theorem 371
Feynman, Richard P. 416
Final state 3 5
Finite automaton, automatic door example 32
Finite automaton, computation of 40
Finite automaton, decidability 166—170
Finite automaton, defined 35
Finite automaton, designing 41—44
Finite automaton, transition function 3 5
Finite automaton, two-dimensional 213
Finite automaton, two-headed 212
Finite state machine see “Finite automaton”
Finite state transducer 87
Fixed point theorem 223
Formal proof 230
Formula 225 271
FORMULA-GAME 314
Fortnow, Lance 418
Free variable 225
FST see “Finite state transducer”
Function 7—9
Function, argument 8
Function, binary 8
Function, computable 206
Function, domain 7
Function, one-to-one 175
Function, one-way 408
Function, onto 7 175
Function, polynomial time computable 272
Function, range 7
Function, space constructible 336
Function, time constructible 340
Function, transition 35
Function, unary 8
Gabarro, Joaquim 416
Gadget in a completeness proof 283
Game 313
Garey, Michael R. 416
Gate in a Boolean circuit 352
Generalized Geography 316
Generalized nondeterministic finite automaton 70—76
Generalized nondeterministic finite automaton, converting to a regular expression 71
Generalized nondeterministic finite automaton, defined 70 73
Geography game 315
GG (generalized geography) 317
Gill, John T. 416
GNFA see “Generalized nondeterministic finite automaton”
GO, game of 320
Go-moku, game of 330
Godel, Kurt 2 227 230 416
Goemans, Michel X. 416
Goldwasser, Shafi 416 417
Graph, acyclic 376
Graph, coloring 297
Graph, cycle in 11
Graph, degree 10
Graph, directed 12
Graph, edge 10
Graph, isomorphism problem 295 387
Graph, k-regular 21
Graph, labeled 10
Graph, node 10
Graph, strongly connected 12
Graph, sub- 11
Graph, undirected 10
Graph, vertex 10
Greenlaw, Raymond 417
Halting configuration 141
Halting problem 173—181
Halting problem, unsolvability of 174
Hamiltonian path problem 264
Hamiltonian path problem, exponential time algorithm 264
Hamiltonian path problem, NP-completeness of 286—291
Hamiltonian path problem, polynomial time verifier 265
HAMPATH 264 286
Harary, Frank 417
Hartmanis, Juris 417
Hey, Anthony J.G. 416
Hierarchy theorem 336—347
Hierarchy theorem, space 337
Hierarchy theorem, time 341
High-level description of a Turing machine 157
Hilbert, David 154 417
Hofstadter, Douglas R. 417
Hoover, H.James 416 417
Hopcroft, John E 415 417 419
Huang, Ming-Deh A. 415
IFF 18
Implementation description of a Turing machine 157
Implication operation 15
Incompleteness theorem 230
Incompressible string 239
Indegree of a node 12
Independent set 27
Induction hypothesis 23
Induction, basis 23
Induction, proof by 22—25
Induction, step 23
Inductive definition 65
Infinite set 4
Infix notation 8
Inherent ambiguity 106
Inherently ambiguous context-free language 106
Integers 4
Interactive proof system 387—399
Interpretation 226
Intersection operation 4
ISO 387
Isomorphic graphs 295
Johnson, David S. 416 417
K(x) (descriptive complexity) 236
k-ary function 8
k-ary relation 8
k-clique 267
k-optimal approximation algorithm 367
k-tuple 6
Karloff, Howard 418
Karp, Richard M. 417
Kayal, Neeraj 415
Kolmogorov, Andrei N. 236
| L 321
Labeled graph 10
LADDER 330
Language, co-Turing-recognizable 181
Language, context-free 101
Language, decidable 142
Language, defined 14
Language, of a grammar 101
Language, recursively enumerable 142
Language, regular 40
Language, Turing-decidable 142
Language, Turing-recognizable 142
Language, Turing-unrecognizable 181
Lawler, Eugene L. 417
LBA see “Linear bounded automaton”
Leaf in a tree 11
Leeuwen, Jan van 419
Leftmost derivation 106
Leighton, F.Thomson 417
Leiserson, Charles E. 416
Lemma 17
Lenstra, Jan Karel 417
Leveled graph 333
Levin, Leonid A. 271 359 417
Lewis, Harry 417
Lexical analyzer 66
Lexicographic ordering 14
Li, Ming 417
Lichtenstein, David 418
Linear bounded automaton 193—197
Linear time 253
Lipton, Richard J. 417
Lisp 154
Literal 274
Log space computable function 324
Log space reduction 324 404
Log space transducer 324
Luby, Michael 418
Lund, Carsten 415 418
Majority function 363
Many-one reducibility 206
Mapping 7
Mapping reducibility 206—211
Mapping reducibility, polynomial time 272
Markov chain 33
Match 199
Matijasevic, Yuri 155
MAX-CLIQUE 300 361
MAX-CUT 296
Maximization problem 367
Member of a set 3
Micali, Silvio 416 417
Miller, Gary L. 418
MIN-FORMULA 383
Minesweeper 298
Minimal Boolean formula 349
Minimal description 236
Minimal formula 383
Minimization of a DFA 299
Minimization problem 366
Minimum pumping length 91
Model 226
MODEXP 295
Modulo operation 8
Motwani, Rajeev 415
Multiset 4 269
Multitape Turing machine 148—150
Myhill — Nerode theorem 91
Natural numbers 4
NC. 402
Negation operation 14
NFA see “Nondeterministic finite automaton”
Nim, game of 331
Nisan, Noam 418
Niven, Ivan 418
nl 321
NL-complete problem PATH 322
NL-completeness defined 324
Node of a graph 10
Node of a graph, degree 10
Node of a graph, indegree 12
Node of a graph, outdegree 12
Nondeterministic computation 47
Nondeterministic finite automaton 47—58
Nondeterministic finite automaton, computation by 48
Nondeterministic finite automaton, defined 53
Nondeterministic finite automaton, equivalence with deterministic finite automaton 55
Nondeterministic finite automaton, equivalence with regular expression 66
Nondeterministic polynomial time 266
Nondeterministic Turing machine 150—152
Nondeterministic Turing machine, space complexity of 304
Nondeterministic Turing machine, time complexity of 255
NONISO 387
NOT operation 14
NP 264—270
NP-complete problem, 3COLOR 297
NP-complete problem, 3SAT 274 359
NP-complete problem, CIRCUIT-SAT 358
NP-complete problem, HAMPATH 286
NP-complete problem, SUBSET-SUM 292
NP-complete problem, UHAMPATH 291
NP-complete problem, VERTEX-COVEF. 284
NP-completeness 271—294
NP-completeness, defined 276
NP-hard 298
NP-problem 266
NPSPACE 308
NSPACE(f(n)) 304
NTIME(f(n)) 267
NTM see “Nondeterministic Turing machine”
O(f(n)) (big-O notation) 249—250
o(f(n)) (small-o notation) 250
One-sided error 375
one-time pad 406
One-to-one function 175
One-way function 408
One-way permutation 408
Onto function 7 175
Optimal solution 366
Optimization problem 365
OR operation 14
Oracle 232 348
Oracle tape 348
Outdegree of a node 12
P 256—263 269—270
P-complete problem, CIRCUIT-VALUE 404
P-completeness 404
Pair, tuple 6
Palindrome 90 128
Papadimitriou, Christos H. 417 418
Parallel computation 399—404
Parallel random access machine 400
Parity function 353
Parse tree 100
Parser 99
Pascal 154
Path 259 322
Path, Hamiltonian 264
Path, in a graph 11
Path, simple 11
PCP see “Post correspondence problem”
PDA see “Pushdown automaton”
Perfect shuffle operation 89 131
Ph 386
Pigeonhole Principle 78 79 124
Pippenger, Nick 402
Polynomial 154
Polynomial bound 250
Polynomial time, algorithm 256—263
Polynomial time, computable function 272
|
|
|
| Реклама |
|
|
|
|
|
О проекте