| dbo:abstract
|
- En informatique théorique et en théorie des jeux, la logique contrainte (nom original en anglais : constraint logic) est un formalisme proposé par Robert A. Hearn et Erik D. Demaine pour démontrer plus simplement des résultats de complexité théorique pour des jeux de plateau, comme le jeu de pousse-pousse qui a été montré complet pour la classe PSPACE. La logique contrainte propose des gadgets et est utilisée pour prouver la dureté de généralisation de problèmes sur les graphes comme ensemble indépendant. (fr)
- In theoretical computer science, nondeterministic constraint logic is a combinatorial system in which an orientation is given to the edges of a weighted undirected graph, subject to certain constraints. One can change this orientation by steps in which a single edge is reversed, subject to the same constraints. The constraint logic problem and its variants have been proven to be PSPACE-complete to determine whether there exists a sequence of moves that reverses a specified edge and are very useful to show various games and puzzles are PSPACE-hard or PSPACE-complete. This is a form of reversible logic in that each sequence of edge orientation changes can be undone. The hardness of this problem has been used to prove that many games and puzzles have high game complexity. (en)
|
| dbo:thumbnail
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 13045 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdfs:comment
|
- En informatique théorique et en théorie des jeux, la logique contrainte (nom original en anglais : constraint logic) est un formalisme proposé par Robert A. Hearn et Erik D. Demaine pour démontrer plus simplement des résultats de complexité théorique pour des jeux de plateau, comme le jeu de pousse-pousse qui a été montré complet pour la classe PSPACE. La logique contrainte propose des gadgets et est utilisée pour prouver la dureté de généralisation de problèmes sur les graphes comme ensemble indépendant. (fr)
- In theoretical computer science, nondeterministic constraint logic is a combinatorial system in which an orientation is given to the edges of a weighted undirected graph, subject to certain constraints. One can change this orientation by steps in which a single edge is reversed, subject to the same constraints. The constraint logic problem and its variants have been proven to be PSPACE-complete to determine whether there exists a sequence of moves that reverses a specified edge and are very useful to show various games and puzzles are PSPACE-hard or PSPACE-complete. (en)
|
| rdfs:label
|
- Logique contrainte (fr)
- Nondeterministic constraint logic (en)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
