Generic-case complexity, decision problems in group theory and random walks
Ilya KapovichAlexei G. MyasnikovPaul E. SchuppVladimir ShpilrainPublished in: CoRR (2002)
Keyphrases
- decision problems
- random walk
- influence diagrams
- computational complexity
- decision model
- utility function
- expected utility theory
- pspace complete
- directed graph
- optimal policy
- transition probabilities
- markov chain
- np hard
- stationary distribution
- decision processes
- markov random walk
- optimal strategy
- multiple criteria
- bandit problems
- bayesian decision problems
- decision analysis
- np complete
- spectral methods
- von neumann
- bounded treewidth
- flow graph
- transition probability matrix
- probability distribution
- lower bound