Abstract
We empirically study the computational complexity of diagnosing systems with real-world structure. We adopt the structure specified by a small-world network, which is a graphical structure that is common to a wide variety of naturally-occurring systems, ranging from biological systems, the WWW, to human-designed mechanical systems. We randomly generate a suite of digital circuit models with small-world network structure, and show that diagnosing these models is computationally hard.
| Original language | English |
|---|---|
| Title of host publication | ECAI 2006 |
| Subtitle of host publication | 17th European Conference on Artificial Intelligence August 29 - September 1, 2006, Riva del Garda, Italy |
| Editors | Gerhard Brewka, Silvia Coradeschi, Anna Perini, Paolo Traverso |
| Publisher | IOS Press BV |
| Pages | 783-784 |
| Number of pages | 2 |
| ISBN (Print) | 9781586036423 |
| Publication status | Published - 2006 |
Publication series
| Name | Frontiers in Artificial Intelligence and Applications |
|---|---|
| Volume | 141 |
| ISSN (Print) | 0922-6389 |
| ISSN (Electronic) | 1879-8314 |