Tiling with bars and satisfaction of Boolean formulas (Q1922876): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claim: reviewed by (P1447): Item:Q331377 |
||
Property / reviewed by | |||
Property / reviewed by: Egon Schulte / rank | |||
Revision as of 13:28, 13 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Tiling with bars and satisfaction of Boolean formulas |
scientific article |
Statements
Tiling with bars and satisfaction of Boolean formulas (English)
0 references
23 March 1997
0 references
The paper considers plane figures made up from finitely many squares of the plane tessellation by unit squares. It is proved that the problem of tiling such a figure with horizontal or vertical bars of length 2 or 3 can be reduced in linear time (in the area of the figure) to the logic problem 3-SAT (3-satisfiability). In particular, this gives a linear algorithm which, given a figure \(F\), either exhibits a tiling of \(F\) or indicates that such a tiling cannot exist.
0 references
polyominoes
0 references
NP-hardness
0 references
3-satisfiability
0 references
plane figures
0 references
squares
0 references
plane tessellation
0 references
tiling
0 references
bars
0 references
linear algorithm
0 references