CINECA IRIS Institutional Research Information System
IRIS è l'Anagrafe della ricerca dell'Università degli Studi di Trento, e ha lo scopo di raccogliere, documentare, conservare e diffondere, anche ad accesso aperto, la produzione scientifica degli autori afferenti all'Università degli Studi di Trento.
Englishhe satisfiability problem for conjunctions of quantifier-free literals in first-order theories of interest–“ -solving” for short–has been deeply investigated for more than three decades from both theoretical and practical perspectives, and it is currently a core issue of state-of-the-art SMT solving. Given some theory of interest, a key theoretical problem is to establish the computational (in)tractability of -solving, or to identify intractable fragments of . In this paper we investigate this problem from a general perspective, and we present a simple and general criterion for establishing the NP-hardness of -solving, which is based on the novel concept of “colorer” for a theory . As a proof of concept, we show the effectiveness and simplicity of this novel criterion by easily producing very simple proofs of the NP-hardness for many theories of interest for SMT, or of some of their fragments.
Scheda prodotto non validato
I dati visualizzati non sono stati ancora sottoposti a validazione formale da parte dello Staff di IRIS, ma sono stati ugualmente trasmessi al Sito Docente Cineca (Loginmiur).
| Titolo: | Colors make theories hard |
| Autori: | Sebastiani, Roberto |
| Autori Unitn: | |
| Titolo del volume contenente il saggio: | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
| Luogo di edizione: | London |
| Casa editrice: | Springer Verlag |
| Anno di pubblicazione: | 2016 |
| Codice identificativo Scopus: | 2-s2.0-84976610701 |
| ISBN: | 9783319402284 9783319402284 |
| Handle: | http://hdl.handle.net/11572/168325 |
| Appare nelle tipologie: | 04.1 Saggio in atti di convegno (Paper in proceedings) |
File in questo prodotto:
Copyright © 2020