Linear, Polynomial or Exponential? Complexity Inference in Polynomial Time.
Amir M. Ben-AmramNeil D. JonesLars KristiansenPublished in: CiE (2008)
Keyphrases
- polynomial hierarchy
- exponential size
- polynomial size
- average case complexity
- linear space
- linear complexity
- worst case
- computational complexity
- average case
- np hardness
- low order
- low degree
- dnf formulas
- special case
- lower bound
- vapnik chervonenkis dimension
- learning algorithm
- decision problems
- linear constraints
- upper bound
- search algorithm
- bayesian networks