Hardness and Hierarchy Theorems for Probabilistic Quasi-Polynomial Time.
Jin-yi CaiAjay NerurkarD. SivakumarPublished in: STOC (1999)
Keyphrases
- computational complexity
- np hardness
- deterministic finite state automata
- information theoretic
- np hard
- worst case
- special case
- probabilistic model
- bayesian networks
- uncertain data
- generative model
- np complete
- approximation algorithms
- data driven
- probabilistic approaches
- hierarchical structure
- agnostic learning
- neural network
- belief networks
- learning theory
- finite automata
- bounded treewidth
- fixed parameter tractable