This HTML5 document contains 71 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dctermshttp://purl.org/dc/terms/
yago-reshttp://yago-knowledge.org/resource/
dbohttp://dbpedia.org/ontology/
n16http://dbpedia.org/resource/File:
foafhttp://xmlns.com/foaf/0.1/
n7https://global.dbpedia.org/id/
dbthttp://dbpedia.org/resource/Template:
rdfshttp://www.w3.org/2000/01/rdf-schema#
n17http://commons.wikimedia.org/wiki/Special:FilePath/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
dbpedia-frhttp://fr.dbpedia.org/resource/
wikipedia-enhttp://en.wikipedia.org/wiki/
dbchttp://dbpedia.org/resource/Category:
provhttp://www.w3.org/ns/prov#
dbphttp://dbpedia.org/property/
xsdhhttp://www.w3.org/2001/XMLSchema#
wikidatahttp://www.wikidata.org/entity/
dbrhttp://dbpedia.org/resource/

Statements

Subject Item
dbr:PSPACE-complete
dbo:wikiPageWikiLink
dbr:Nondeterministic_constraint_logic
Subject Item
dbr:Constraint_Logic_Problem
dbo:wikiPageWikiLink
dbr:Nondeterministic_constraint_logic
dbo:wikiPageRedirects
dbr:Nondeterministic_constraint_logic
Subject Item
dbr:Rush_Hour_(puzzle)
dbo:wikiPageWikiLink
dbr:Nondeterministic_constraint_logic
Subject Item
dbr:Constraint_logic_problem
dbo:wikiPageWikiLink
dbr:Nondeterministic_constraint_logic
dbo:wikiPageRedirects
dbr:Nondeterministic_constraint_logic
Subject Item
dbr:Games,_Puzzles,_and_Computation
dbo:wikiPageWikiLink
dbr:Nondeterministic_constraint_logic
Subject Item
dbr:Reconfiguration
dbo:wikiPageWikiLink
dbr:Nondeterministic_constraint_logic
Subject Item
dbr:Constraint_Logic_Problem_(Complexity_Theory)
dbo:wikiPageWikiLink
dbr:Nondeterministic_constraint_logic
dbo:wikiPageRedirects
dbr:Nondeterministic_constraint_logic
Subject Item
dbr:Nondeterministic_constraint_logic
rdfs:label
Nondeterministic constraint logic Logique contrainte
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. 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.
foaf:depiction
n17:Constraint_logic_and_gate.gif n17:Constraintgraph.png
dcterms:subject
dbc:PSPACE-complete_problems dbc:Reversible_computing dbc:Computational_problems_in_graph_theory dbc:Reconfiguration dbc:Logical_calculi
dbo:wikiPageID
53059902
dbo:wikiPageRevisionID
1099121984
dbo:wikiPageWikiLink
dbr:Sokoban dbr:Planar_graph dbr:Dominating_set dbr:Undirected_graph dbr:Rush_Hour_(puzzle) dbr:Reversible_computing dbr:Sliding_block_puzzle dbr:Sliding_puzzle dbr:Graph_bandwidth dbc:PSPACE-complete_problems dbc:Reversible_computing dbc:Computational_problems_in_graph_theory dbr:AND_gate dbr:3-CNF dbr:Game_complexity dbc:Reconfiguration dbr:OR_gate dbr:Rush_Hour_(board_game) dbr:PSPACE-complete dbr:Orientation_(graph_theory) dbr:Gadget_(computer_science) dbr:Erik_Demaine dbr:QSAT dbr:True_quantified_Boolean_formula dbc:Logical_calculi dbr:Vertex_cover dbr:Reduction_(complexity) dbr:Boolean_logic dbr:Theoretical_computer_science dbr:Quantifier_(logic) dbr:Reconfiguration n16:Constraint_logic_and_gate.gif n16:Constraintgraph.png dbr:Independent_set_(graph_theory) dbr:Cubic_graph
owl:sameAs
n7:2qKF2 wikidata:Q30590566 dbpedia-fr:Logique_contrainte yago-res:Nondeterministic_constraint_logic
dbp:wikiPageUsesTemplate
dbt:Reflist dbt:Mvar
dbo:thumbnail
n17:Constraint_logic_and_gate.gif?width=300
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. 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.
prov:wasDerivedFrom
wikipedia-en:Nondeterministic_constraint_logic?oldid=1099121984&ns=0
dbo:wikiPageLength
13045
foaf:isPrimaryTopicOf
wikipedia-en:Nondeterministic_constraint_logic
Subject Item
wikipedia-en:Nondeterministic_constraint_logic
foaf:primaryTopic
dbr:Nondeterministic_constraint_logic