Många naturliga kombinatoriska problem kan uttryckas som problem med begränsad tillfredsställelse. Denna typ av problem är känd för att vara NP-komplett i allmänhet, men vissa restriktioner i form av begränsningar kan garantera dragbarhet. Här visar vi att varje uppsättning relationer som används för att specificera tillåtna former av begränsningar kan associeras med en ändlig universell algebra och vi utforskar hur den beräkningsmässiga komplexiteten i motsvarande restriktionstillfredsställelse problem är kopplad till egenskaperna hos denna algebra. Därför översätter vi helt och hållet problemet med att klassificera komplexiteten i problem med begränsad begränsningstillfredsställelse till språket för universell algebra. Vi introducerar ett begrepp av "dragbar algebra", och undersöka hur dragbarheten av en algebra relaterar till dragbarheten av de mindre algebras som kan härledas från den, inklusive dess subalgebras och homomorfa bilder. Detta gör det möjligt för oss att avsevärt minska de typer av algebror som behöver klassificeras. Med hjälp av våra resultat visar vi också att om det beslutsproblem som är förknippat med en given samling av begränsningar typer kan lösas effektivt, så kan motsvarande sökproblem. Vi klassificerar sedan alla finita strikt enkla surjektiv algebras med avseende på dragbarhet, erhålla en dikotomi teorem som generaliserar Schaefers dikotomi för den generaliserade satisfiability problem. Slutligen föreslår vi ett möjligt allmänt algebraiskt kriterium för att särskilja de dragbara och svåråtkomliga fall av problemet med tvångstillfredsställelse.
Begreppet "kombinerande algoritm" är relaterat till begreppet polymorfisms REF i studien av problem med begränsad tillfredsställelse.
CLASSIFYING THE COMPLEXITY OF CONSTRAINTS USING FINITE ALGEBRAS∗
{'venue': 'ICALP', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}