Recent years have seen considerable growth in the application of complexity-theoretic ideas to problems in Artificial Intelligence. Many of the significant advances in both fields have a background in concerns that are recognised as central to Artificial Intelligence. Despite this, it is debatable to what extent A.I. practitioners are, in general aware of important theoretical contributions and, equally, to what extent specialists in Computational Complexity Theory recognise the importance of Artificial Intelligence as a source of core theoretical problems. The explosion of interest in Phase-transition phenomena stemming from pioneering experimental studies carried out by A.I. researchers provides just one example where the subsequent involvement of complexity specialists has resulted in valuable exchanges of ideas taking place. Similarly in fields such as planning and search, reasoning and theorem proving, contributions from both A.I. and complexity researchers have been of major importance. There are, however, many examples of A.I. specialisms which are only beginning to attract serious attention from theoreticians. This workshop should provide not only a platform through which participants can report on recent developments within fields where Complexity Theory and A.I. already interact, but also heighten awareness of A.I. disciplines in which a foundation for such interaction can be constructed. Its main focus will concern a select number of topics where interaction between complexity theory and artificial intelligence has been particularly fruitful. Among these are: search, planning & scheduling problems, knowledge representation and reasoning; theorem proving techniques, multi-agent interactions and agent systems, Argumentation and Dialogue Games; phase-transition phenomena.
The theory of computational complexity and computability is the very heart of computer science. Computability theory addresses itself to the question of what problems can be solved by computer, whereas the theory of computational complexity is concerned with precisely characterising the inherent difficulty of solving problems by computer. Just as these results have far-reaching implications for mainstream computer science, so they have in AI -- a field that is, after all, ultimately concerned with answering the question of whether intelligence in all its forms is computable, and if so, whether it is practically computable. While the hurdles of NP-completeness and other such negative results are the ultimate source of many of AI's failures and disappointments, these also present its greatest challenges. Recognising the critical relevance of computational complexity and computability to the ultimate success - or otherwise - of the AI project, the aim of this workshop is to bring together researchers interested in applying and extending the results of complexity theory to the problems of AI.
The organisers invite the submission of original papers addressing any aspect of computational complexity and computability in AI. Papers that are solely devoted to computational complexity theory, without making a contribution to AI, or papers that address AI issues without making their relevance to computational complexity/computability clear are probably best sent elsewhere.
Topics of interest include, but are by no means restricted to the following:
Complexity/computability results for:
Contributions should be submitted by 25th February 2002, in accordance with the instructions here.
Papers will be reviewed by the Workshop Organizing Committee and notifications of acceptance or otherwise given by 5th April 2002.
The number of participants is limited.
All participants in this workshop will be expected to register for the main ECAI 2002 Conference.
| Paul E. Dunne (Liverpool) (Main Contact) | |
| Bernhard Nebel (Freiburg) | |
| Marco Cadoli (Rome) | Yannis Dimopoulos (Cyprus) |
| Thomas Eiter (T.U. Vienna) | Moshe Vardi (Rice) |
| Toby Walsh (York) | Mike Wooldridge (Liverpool) |
Submissions should be prepared following the Camera-ready format specified for
articles in the main ECAI Proceedings.
Contributors are strongly encouraged to use the LaTex style or LaTeX2e class files in
preparing articles.
These may be downloaded from here.
Articles should be a maximum of 4 pages within the prescribed format and sent
electronically (as a Postscript file) to
with the phrase CoCoA Submission included in the Subject header.
Submission Procedures
| 25th February 2002: | Deadline for receipt of submissions. |
| 5th April 2002: | Notification of acceptance. |
| 26th April 2002: | Deadline for receipt of final Camera-Ready version |
| 22-23 July 2002: | Workshop Program at ECAI 2002 |
| 24-26 July 2002: | Main Technical Program of ECAI 2002 |