The order encoding: From tractable CSP to tractable SAT
Many mathematical and practical problems can be expressed as constraint satisfaction problems (CSPs). The general CSP is known to be NP-complete, but many different conditions have been identified which are sufficient to ensure that classes of instances satisfying those conditions are tractable, tha...
| Main Authors: | , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
2011
|
| _version_ | 1826266337481064448 |
|---|---|
| author | Petke, J Jeavons, P |
| author_facet | Petke, J Jeavons, P |
| author_sort | Petke, J |
| collection | OXFORD |
| description | Many mathematical and practical problems can be expressed as constraint satisfaction problems (CSPs). The general CSP is known to be NP-complete, but many different conditions have been identified which are sufficient to ensure that classes of instances satisfying those conditions are tractable, that is, solvable in polynomial time [1,2,3,4,7]. © 2011 Springer-Verlag. |
| first_indexed | 2024-03-06T20:37:22Z |
| format | Journal article |
| id | oxford-uuid:33139ffa-71ab-4d22-8968-c12f65a1cbc9 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-06T20:37:22Z |
| publishDate | 2011 |
| record_format | dspace |
| spelling | oxford-uuid:33139ffa-71ab-4d22-8968-c12f65a1cbc92022-03-26T13:18:09ZThe order encoding: From tractable CSP to tractable SATJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:33139ffa-71ab-4d22-8968-c12f65a1cbc9EnglishSymplectic Elements at Oxford2011Petke, JJeavons, PMany mathematical and practical problems can be expressed as constraint satisfaction problems (CSPs). The general CSP is known to be NP-complete, but many different conditions have been identified which are sufficient to ensure that classes of instances satisfying those conditions are tractable, that is, solvable in polynomial time [1,2,3,4,7]. © 2011 Springer-Verlag. |
| spellingShingle | Petke, J Jeavons, P The order encoding: From tractable CSP to tractable SAT |
| title | The order encoding: From tractable CSP to tractable SAT |
| title_full | The order encoding: From tractable CSP to tractable SAT |
| title_fullStr | The order encoding: From tractable CSP to tractable SAT |
| title_full_unstemmed | The order encoding: From tractable CSP to tractable SAT |
| title_short | The order encoding: From tractable CSP to tractable SAT |
| title_sort | order encoding from tractable csp to tractable sat |
| work_keys_str_mv | AT petkej theorderencodingfromtractablecsptotractablesat AT jeavonsp theorderencodingfromtractablecsptotractablesat AT petkej orderencodingfromtractablecsptotractablesat AT jeavonsp orderencodingfromtractablecsptotractablesat |