Although Knowledge Representation is full of reasoning problems that have been formally proved to be both NP-hard and coNP-hard, the experimental analysis has largely focused on problems belonging to either NP or coNP. We still do not know, for example, whether well studied phenomena such as “phase transition”, which show up for many NP-complete problems (e.g., sat) happen for Σ p 2 -complete problems, and whether they are related to an “easy-hard-easy” pattern or not. The goal of this paper is to show some results of an ongoing experimental analysis that aims to provide reasonable answers to such questions. We analyze the problem of evaluating Quantified Boolean Formulae, which is the prototypical complete problem for all levels of the Polynomial Hierarchy, the computationally simplest hierarchy of complexity classes above NP of great interest to KR.
Experimental analysis of the computational cost of evaluating Quantified Boolean Formulae / Cadoli, M.; Giovanardi, A.; Schaerf, M.. - 1321:(1997), pp. 207-218. (Intervento presentato al convegno 5th Congress of the Italian Association for Artificial Intelligence, AI*IA 1997 tenutosi a Rome; Italy).
Experimental analysis of the computational cost of evaluating Quantified Boolean Formulae
Cadoli M.;Schaerf M.
1997
Abstract
Although Knowledge Representation is full of reasoning problems that have been formally proved to be both NP-hard and coNP-hard, the experimental analysis has largely focused on problems belonging to either NP or coNP. We still do not know, for example, whether well studied phenomena such as “phase transition”, which show up for many NP-complete problems (e.g., sat) happen for Σ p 2 -complete problems, and whether they are related to an “easy-hard-easy” pattern or not. The goal of this paper is to show some results of an ongoing experimental analysis that aims to provide reasonable answers to such questions. We analyze the problem of evaluating Quantified Boolean Formulae, which is the prototypical complete problem for all levels of the Polynomial Hierarchy, the computationally simplest hierarchy of complexity classes above NP of great interest to KR.File | Dimensione | Formato | |
---|---|---|---|
Cadoli_Experimental_1997.pdf
solo gestori archivio
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
862.52 kB
Formato
Adobe PDF
|
862.52 kB | Adobe PDF | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.