Complexity of constraint satisfaction
id:
complexity-of-constraint-satisfaction-196-16754948
title:
Complexity of constraint satisfaction
text:
The complexity of constraint satisfaction is the application of computational complexity theory to constraint satisfaction. It has mainly been studied for discriminating between tractable and intractable classes of constraint satisfaction problems on finite domains. Solving a constraint satisfaction problem on a finite domain is an NP-complete problem in general. Research has shown a number of polynomial-time subcases, mostly obtained by restricting either the allowed domains or constraints or t
brand slug:
wiki
category slug:
encyclopedia
description:
original url:
https://en.wikipedia.org/wiki/Complexity_of_constraint_satisfaction
date created:
date modified:
2024-03-17T11:31:24Z
main entity:
{"identifier":"Q5156628","url":"https://www.wikidata.org/entity/Q5156628"}
image:
fields total:
13
integrity:
13