Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9650025 | Artificial Intelligence | 2005 | 35 Pages |
Abstract
We then investigate the computational complexity of model checking for knowledge update. We first show that in general the model checking for knowledge update is Σ2P-complete. We then identify a subclass of knowledge update problems that has polynomial time complexity for model checking. We point out that some important knowledge update problems belong to this subclass. We further address another interesting subclass of knowledge update problems for which the complexity of model checking is NP-complete.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Artificial Intelligence
Authors
Chitta Baral, Yan Zhang,