Pushing blocks is hard. (Q1395573): Difference between revisions
From MaRDI portal
ReferenceBot (talk | contribs) Changed an Item |
Set OpenAlex properties. |
||
| Property / full work available at URL | |||
| Property / full work available at URL: https://doi.org/10.1016/s0925-7721(02)00170-0 / rank | |||
Normal rank | |||
| Property / OpenAlex ID | |||
| Property / OpenAlex ID: W1999708036 / rank | |||
Normal rank | |||
Latest revision as of 08:50, 30 July 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Pushing blocks is hard. |
scientific article |
Statements
Pushing blocks is hard. (English)
0 references
1 July 2003
0 references
The authors study several variations of simpler puzzles and show that the models are NP-hard. The results subsume a number of previous NP-hardness proofs of pushing-block variations, and solve the Push-X open problem. The main idea in the is to force the robot to follow constrained Eulerian tours of planar graphs and carry a constant amount of information along each edge of the graph. Moreover it is build a kind of logic engine. This approach is innovative and contrast with other previous approaches of building circuits based on graphs.
0 references
computational complexity
0 references
computational geometry
0 references
motion planning
0 references
combinatorial games
0 references
NP-hard
0 references
push-X open problem
0 references
robot
0 references
Eulerian tours of planar graphs
0 references
