| 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 |
https://www.researchgate.net/publication/2595366 http://www.ics.uci.edu/~dechter/books/index.html |
| dbo:wikiPageID |
4489942 (xsd:integer) |
| dbo:wikiPageLength |
28457 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID |
1000142677 (xsd:integer) |
| dbo:wikiPageWikiLink |
dbr:Primal_constraint_graph dbr:Homomorphism dbr:Decomposition_method_(constraint_satisfaction) dbr:Intractability_(complexity) dbr:Connected_graph dbr:Schaefer's_dichotomy_theorem dbr:Graph_(discrete_mathematics) dbr:Graph_coloring dbr:NP-complete dbr:Constraint_satisfaction dbr:Constraint_satisfaction_problem dbr:Ordered_graph dbr:Computational_complexity_theory dbr:P_(complexity) dbr:Table_(database) dbr:Tree_(graph_theory) dbr:Truth_value dbr:Database_theory dbr:Gadget_(computer_science) dbr:Join_(SQL) dbr:Local_consistency dbr:Database dbr:Datalog dbr:Dichotomy dbc:Constraint_programming dbr:Binary_constraint dbr:Bipartite_graph dbr:3-SAT dbr:Forest_(graph_theory) dbr:Finite_model_theory dbr:Propositional_satisfiability dbr:Gaifman_graph dbr:2-SAT dbr:Ladner's_theorem dbr:Three-colorable_graph dbr:Strong_directional_i-consistency dbr:Conjunctive_query_containment dbr:Conjunctive_query_evaluation dbr:Hell-Nesetril_theorem |
| dbp:wikiPageUsesTemplate |
dbt:As_of dbt:Cite_book dbt:Cite_conference dbt:Cite_journal dbt:Expand_section dbt:ISBN dbt:No_footnotes |
| dct:subject |
dbc:Constraint_programming |
| gold:hypernym |
dbr:Application |
| rdf:type |
dbo:Software |
| 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 |
freebase:Complexity of constraint satisfaction wikidata:Complexity of constraint satisfaction dbpedia-pt:Complexity of constraint satisfaction https://global.dbpedia.org/id/4iJL8 |
| prov:wasDerivedFrom |
wikipedia-en:Complexity_of_constraint_satisfaction?oldid=1000142677&ns=0 |
| foaf:isPrimaryTopicOf |
wikipedia-en:Complexity_of_constraint_satisfaction |
| is dbo:wikiPageWikiLink of |
dbr:Decomposition_method_(constraint_satisfaction) dbr:Graph_homomorphism dbr:Moshe_Vardi dbr:Constraint_satisfaction_problem dbr:Structure_(mathematical_logic) dbr:Local_consistency dbr:Denormalization dbr:Growing_context-sensitive_grammar |
| is foaf:primaryTopic of |
wikipedia-en:Complexity_of_constraint_satisfaction |