|
|
 |
| Авторизация |
|
|
|
| Поиск по указателям |
|
|
|
|
|
|
|
 |
|
|
|
| Sipser M. — Introduction to the Theory of Computation |
|
|
|
| Предметный указатель |
Fortnow, Lance 384
Free variable 205
FST see "Finite state transducer"
Function 7—9
Function, argument 8
Function, binary 8
Function, computable 190
Function, domain 7
Function, one-to-one 161
Function, one-way 375
Function, onto 7 161
Function, polynomial time computable 250
Function, range 7
Function, space constructible 306
Function, time constructible 310
Function, transition 35
Function, unary 8
Gabarro Joaquim 382
Gadget in a completeness proof 260
Game 287
Garey, Michael R. 382
Gate in a Boolean circuit 322
Generalized Geography 290
Generalized nondeterministic finite, automaton 70—76
Generalized nondeterministic finite, converting to a regular expression 71
Generalized nondeterministic finite, defined 70 73
Geography game 289
GG (generalized geography) 290
Gill John T. 382
GNFA see "Generalized nondeterministic finite automaton"
GO, game of 294
Go-moku, game of 303
Goedel, Kurt 2 206 209 382
Goemans, Michel X. 383
Goldwasser, Shafi 383
Graph, acyclic 344
Graph, coloring 275
Graph, cycle in 11
Graph, degree 10
Graph, directed 12
Graph, edge 10
Graph, isomorphism problem 272 355
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 383
Halting configuration 129
Halting problem 159—167
Halting problem, unsolvability of 160
Hamiltonian path problem 242
Hamiltonian path problem, exponential time algorithm 242
Hamiltonian path problem, NP-completeness of 262—267
Hamiltonian path problem, polynomial time verifier 242 243
HAMPATH 242 262
Harary, Frank 383
Hartmanis, Juris 383
Hey, Anthony J.G. 382
Hierarchy theorem 306—317
Hierarchy theorem, space 307
Hierarchy theorem, time 311
High-level description of a Turing machine 145
Hilbert, David 142 383
Hofstadter, Douglas R. 383
Hoover, H. James 382 383
Hopcroft, John E. 381 383 385
Huang, Ming-Deh A. 381
IFF 17
Implementation description of a Turing machine 145
Implication operation 15
Incompleteness theorem 209
Incompressible string 218
Indegree of a node 12
Independent set 27
Induction hypothesis 23
Induction, basis 23
Induction, proof by 23—25
Induction, step 23
Inductive definition 65
Infinite set 4
Infix notation 8
Inherent ambiguity 98
Inherently ambiguous context-free language 98
Integers 4
Interactive proof system 354—366
Interpretation 205
Intersection operation 4
ISO 355
Isomorphic graphs 272
Johnson, David S. 382 383
k-ary function 8
k-ary relation 8
k-clique 245
k-optimal approximation algorithm 334
k-tuple 6
Karloff, Howard 384
Karp, Richard M. 383
Kolmogorov, Andrei N. 215
L 295
Labeled graph 10
Language of a grammar 93
Language, co-Turing-recognizable 167
Language, context-free 93
Language, decidable 130
Language, defined 14
Language, recursively enumerable 130
Language, regular 40
Language, Turing-decidable 130
Language, Turing-recognizable 130
Language, Turing-unrecognizable 167
Lawler, Eugene L. 383
LBA see "Linear bounded automaton"
Leaf in a tree 11
Leftmost derivation 98
Leighton, F. Thomson 383
Leiserson, Charles E. 382
Lemma 17
Lenstra, Jan Karel 383
Levin, Leonid A. 248 249—330 383
Lewis, Harry 383
Lexical analyzer 66
Lexicographic ordering 14
Li, Ming 383
Lichtenstein, David 384
Linear bounded automaton 177—180
Linear time 231
Lipton, Richard J. 383
Lisp 142
Literal 251
Log space computable function 297
Log space reduction 297 371
Log space transducer 297
Luby, Michael 384
Lund, Carsten 381 384
Majority function 332
Many-one reducibility 190
Mapping 7
Mapping reducibility 190—194
Mapping reducibility, polynomial time 250
Markov chain 33
Match 183
Matijasevic, Yuri 143
MAX-CLIQUE 276 331
MAX-CUT 273
Maximization problem 334
Member of a set 3
Micali, Silvio 383
| Miller, Gary L. 384
MIN-FORMULA 350
Minimal Boolean formula 319
Minimal description 215
Minimal formula 350
Minimization of a DFA 275
Minimization problem 334
Minimum pumping length 90
Model 205
MODEXP 272
Modulo operation 8
Motwani, Rajeev 381
Multiset 4 246
Multitape Turing machine 136—138
Natural numbers 4
NC 369
Negation operation 14
NFA see "Nondeterministic finite automaton"
Nim, game of 304
Nisan, Noam 384
Niven, Ivan 384
nl 295
NL-complete problem PATH 295
NL-completeness defined 297
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 278
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 243
Nondeterministic Turing machine 138—140
Nondeterministic Turing machine, space complexity of 277
Nondeterministic Turing machine, time complexity of 2 3 3
NONISO 355
NOT operation 14
NP 241—248
NP-complete problem, 3COLOR 275
NP-complete problem, 3SAT 329
NP-complete problem, CIRCUIT-SAT 328
NP-complete problem, HAMPATH 262
NP-complete problem, SUBSET-SUM 268
NP-complete problem, UHAMPATH 267
NP-complete problem, VERTEX-COVER 261
NP-completeness 248—271
NP-completeness, defined 253
NP-hard 273
NPSPACE 281
NSPACE(f(n)) 278
NTIME(f(n)) 245
NTM see "Nondeterministic Turing machine"
o(f(n)) (small-o notation) 228
One-sided error 343
one-time pad 372
One-to-one function 161
One-way function 375
One-way permutation 375
Onto function 7 161
Optimal solution 333
Optimization problem 333
OR operation 14
Oracle 211 318
Oracle tape 318
Oracle Turing machine 318
Outdegree of a node 12
P 234—241 247—248
P-complete problem CIRCUIT-VALUE 371
P-completeness 371
Pair, tuple 6
Papadimitriou, Christos H. 383 384
Parallel computation 366—372
Parallel random access machine 367
Parity function 323
Parse tree 92
Parser 91
Pascal 142
Path 237 295
Path in a graph 11
Path, Hamiltonian 242
Path, simple 11
PCP see "Post correspondence problem"
PDA see "Pushdown automaton"
Ph 354
Pigeonhole Principle 78 79 115
Polynomial 142
Polynomial bound 228
Polynomial time, algorithm 234—241
Polynomial time, computable function 250
Polynomial time, hierarchy 354
Polynomial time, verifier 243
Polynomial verifiability 242
Polynomial, versus exponential 234
Polynomially equivalent models 235
Pomerance, Carl 381 384
Popping a symbol 102
Post correspondence problem (PCP) 183—189
Post correspondence problem (PCP), modified 184
Power set 6 53
PRAM 367
Pratt, Vaughn R. 384
Prefix notation 8
Prenex normal form 205 284
Prime number 242 272 339
Private-key cryptosystem 374
Probabilistic algorithm 335—347
Probabilistic function 375
Probabilistic Turing machine 336
Processor complexity 367
Production 92
proof 17
Proof by construction 21
Proof by contradiction 21—22
Proof by induction 23—25
Proof, finding 17—20
Proof, necessity for 77
Proper subset 4
Prover 356
Pseudoprime 340
PSPACE 281
PSPACE-complete problem, FORMULA-GAME 288
PSPACE-complete problem, GG 290
PSPACE-complete problem, TQBF 284
PSPACE-completeness 283—294
PSPACE-completeness, defined 283
Public-key cryptosystem 374
Pumping lemma for context-free languages 115—119
Pumping lemma for regular languages 77—83
Pumping length 77 90 115
Pushdown automaton 101—114
Pushdown automaton, context-free grammars 106—114
Pushdown automaton, defined 103
Pushdown automaton, examples 104—106
Pushdown automaton, schematic of 102
Pushing a symbol 102
Putnam, Hilary 143
Puzzle 274 303
Quantified boolean formula 284
Quantifier 283
Quantifier in a logical sentence 204
Query node in a branching program 344
Rabin, Michael O. 384
Rackoff, Charles 383
Range of a function 7
Read-once branching program 345
Real number 162
Recognizes a language, meaning of 36
|
|
|
| Реклама |
|
|
|
|
|
О проекте