PlumX Metrics
Embed PlumX Metrics

Colors make theories hard

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), ISSN: 1611-3349, Vol: 9706, Page: 152-170
2016
  • 0
    Citations
  • 0
    Usage
  • 0
    Captures
  • 0
    Mentions
  • 0
    Social Media
Metric Options:   Counts1 Year3 Year

Conference Paper Description

The satisfiability problem for conjunctions of quantifier-free literals in first-order theories T of interest–“T -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 T of interest, a key theoretical problem is to establish the computational (in)tractability of T -solving, or to identify intractable fragments of T. In this paper we investigate this problem from a general perspective, and we present a simple and general criterion for establishing the NPhardness of T -solving, which is based on the novel concept of “colorer” for a theory T. 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.

Provide Feedback

Have ideas for a new metric? Would you like to see something else here?Let us know