
doi: 10.3390/a5010148
handle: 1721.1/86068
Suppose there is a collection of n simple polygons in the plane, none of which overlap each other. The polygons are interlocked if no subset can be separated arbitrarily far from the rest. It is natural to ask the characterization of the subsets that makes the set of interlocked polygons free (not interlocked). This abstracts the essence of a kind of sliding block puzzle. We show that any monotone Boolean function ƒ on n variables can be described by m = O(n) interlocked polygons. We also show that the decision problem that asks if given polygons are interlocked is PSPACE-complete.
computational complexity, Industrial engineering. Management engineering, Electronic computers. Computer science, monotone boolean function, computational complexity; interlocked polygons; monotone boolean function; sliding block puzzle, QA75.5-76.95, T55.4-60.8, interlocked polygons, sliding block puzzle
computational complexity, Industrial engineering. Management engineering, Electronic computers. Computer science, monotone boolean function, computational complexity; interlocked polygons; monotone boolean function; sliding block puzzle, QA75.5-76.95, T55.4-60.8, interlocked polygons, sliding block puzzle
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 2 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
