| dbo:abstract
|
- The complexity of constraint satisfaction is the application of computational complexity theory on 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 the way constraints can be placed over the variables. Research has also established a relationship between the constraint satisfaction problem and problems in other areas such as finite model theory and databases. (en)
- A complexidade da satisfação de restrição é a aplicação da teoria da complexidade computacional na satisfação de restrição. Foi principalmente estudado para discriminar as classes tratáveis e intratáveis da complexidade dos problemas da satisfação de restrição em domínios finitos. Resolver um problema de satisfação de restrição num domínio finito é, normalmente, um problema NP-completo. A pesquisa mostrou um número de subcasos de tempo polinomial, a maioria obtido ao restringir tanto domínios permitidos ou restritos quanto a maneira como as restrições podem ser colocadas sobre as variáveis. A pesquisa também estabeleceu uma relação dos problemas da satisfação de restrição com problemas em outras áreas, como a teoria de modelo finitos ou banco de dados. (pt)
|
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 28457 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- The complexity of constraint satisfaction is the application of computational complexity theory on constraint satisfaction. It has mainly been studied for discriminating between tractable and intractable classes of constraint satisfaction problems on finite domains. (en)
- A complexidade da satisfação de restrição é a aplicação da teoria da complexidade computacional na satisfação de restrição. Foi principalmente estudado para discriminar as classes tratáveis e intratáveis da complexidade dos problemas da satisfação de restrição em domínios finitos. (pt)
|
| rdfs:label
|
- Complexity of constraint satisfaction (en)
- Complexidade da satisfação de restrição (pt)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
