New tractable classes from old
The constraint satisfaction problem is known to be NP-hard in general, but a number of restrictions of the problem have been identified over the years which ensure tractability. This paper introduces two simple methods of combining two or more tractable classes over disjoint domains, in order to syn...
| Hlavní autoři: | , , |
|---|---|
| Médium: | Journal article |
| Jazyk: | English |
| Vydáno: |
2003
|
| _version_ | 1826286428601974784 |
|---|---|
| author | Cohen, D Jeavons, P Gault, R |
| author_facet | Cohen, D Jeavons, P Gault, R |
| author_sort | Cohen, D |
| collection | OXFORD |
| description | The constraint satisfaction problem is known to be NP-hard in general, but a number of restrictions of the problem have been identified over the years which ensure tractability. This paper introduces two simple methods of combining two or more tractable classes over disjoint domains, in order to synthesise larger, more expressive tractable classes. We demonstrate that the classes so obtained are genuinely novel, and have not been previously identified. In addition, we use algebraic techniques to extend the tractable classes which we identify, and to show that the algorithms for solving these extended classes can be less than obvious. |
| first_indexed | 2024-03-07T01:43:38Z |
| format | Journal article |
| id | oxford-uuid:97aada12-36bf-450b-9181-b7d0dfd05101 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T01:43:38Z |
| publishDate | 2003 |
| record_format | dspace |
| spelling | oxford-uuid:97aada12-36bf-450b-9181-b7d0dfd051012022-03-27T00:01:36ZNew tractable classes from oldJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:97aada12-36bf-450b-9181-b7d0dfd05101EnglishSymplectic Elements at Oxford2003Cohen, DJeavons, PGault, RThe constraint satisfaction problem is known to be NP-hard in general, but a number of restrictions of the problem have been identified over the years which ensure tractability. This paper introduces two simple methods of combining two or more tractable classes over disjoint domains, in order to synthesise larger, more expressive tractable classes. We demonstrate that the classes so obtained are genuinely novel, and have not been previously identified. In addition, we use algebraic techniques to extend the tractable classes which we identify, and to show that the algorithms for solving these extended classes can be less than obvious. |
| spellingShingle | Cohen, D Jeavons, P Gault, R New tractable classes from old |
| title | New tractable classes from old |
| title_full | New tractable classes from old |
| title_fullStr | New tractable classes from old |
| title_full_unstemmed | New tractable classes from old |
| title_short | New tractable classes from old |
| title_sort | new tractable classes from old |
| work_keys_str_mv | AT cohend newtractableclassesfromold AT jeavonsp newtractableclassesfromold AT gaultr newtractableclassesfromold |