|
 |
Авторизация |
|
 |
Поиск по указателям |
|
 |
|
 |
|
 |
 |
|
 |
|
Jerrum M. — Counting, sampling and integrating: algorithms and complexity |
|
 |
Предметный указатель |
#P 13
#P-complete 14
#SAT 14
0,1-Perm 15
Almost uniform sampler 27
Almost uniform sampler, fully polynomial 27
Arborescence 4
Ball walk 66
bpp 93
Brooks's theorem 98
Brunn — Minkowsky theorem 84
Canonical paths technique 51
Complexity class, #P 13
Complexity class, BPP 93
Complexity class, FP 13
Complexity class, NP 12
Complexity class, P 11
Complexity class, RP 93
Conductance of the ball walk 89
Congestion 51
Continuised Markov chain 63
Coupling Lemma 37
Curvature condition 69
Decision problem 11
Detailed balance 32
Dimer model 9
Dirichlet form 52
Ergodic [Markov chain] 31
Eulerian circuit 4
FP 13
Fully polynomial almost uniform sampler 27
Fully polynomial randomised approximation scheme 26
Gapl 10
Hamilton cycle 11
Independent set 94
Ising model 9
Linear extensions of a partial order 42
| Local conductance 70
Markov chain 30
Markov chain with continuous state space 67
Markov chain, continuised 63
Markov chain, ergodic 31
Markov chain, time reversible 32
Markovian coupling 36
Matching 49
Mixing time 35
Monomer-dimer system 49
Multicommodity flow problem 51
NP 12
NP-complete 12
Oracle model 65
P 11
Path coupling 41
Perfect matchings 5
Permanent [of a matrix] 15
Pfaffian orientation 5
Poincare inequality 52
Poincare inequality for the ball walk 73
Polynomial-time Turing reducibility 14
Probabilistic Turing machine 25
Probabilistically checkable proof 98
Proper q-colouring 33
Randomised approximation scheme 26
Randomised approximation scheme, fully polynomial 26
RP 93
Sampling problem 26
Spanning tree 1
Stationary distribution 31
Time reversible [Markov chain] 32
Total variation distance 26
Transition matrix 31
Turing machine, model 12
Turing machine, probabilistic 25
Volume of a convex body 65
|
|
 |
Реклама |
 |
|
|