Cops and Robbers is EXPTIME-complete.
William B. KinnersleyPublished in: J. Comb. Theory, Ser. B (2015)
Keyphrases
- exptime complete
- description logics
- data complexity
- expressive power
- pspace complete
- expressive description logics
- np complete
- transitive closure
- satisfiability problem
- query containment
- tree automata
- decision problems
- model checking
- knowledge base
- knowledge representation
- query evaluation
- query answering
- reasoning tasks
- first order logic
- conjunctive queries
- machine learning
- query language
- special case
- artificial intelligence