17×17 is NP-complete

创业投资 2012-02-12

Update (2012.05.18):
Bill Gasarch
and I have written a paper
on the subject. You may find it easier to follow. Also, the $12 times 21$ problem has since been solved.

Intro

The 17x17 problem
has been the subject of recent attention. The question, which was solved in the affirmative
, asks whether it is possible to $4$-color the $17 times 17$ grid such that no rectangle exists within the grid having all four corners the same color. The remaining unanswered question for $4$-colorings is whether there exists a coloring of the $12 times 21$ grid also without monochromatic rectangles.

The $17 times 17$ problem and the $12 times 21$ problem are specific instances of the problem of $4$-coloring for grids. The general question for $n times m$ grids with rectangle-free $c$-colorings is the $(n,m,c)$ problem. A related question is whether a partial coloring of a grid can be extended to a full coloring. The difficulties involved in completing $(n,m,c)$ grids suggest the problem is NP-complete. This is proved here.

Definition

The $n times m$ grid is $c$-colorable if there is a way to color the vertices of the grid with $c$ colors so that no rectangle exists with all four corners the same color ( Gasarch
). The PARTIAL-$(n,m,c)$ decision problem asks whether a partial coloring of an $n times m$ grid can be continued to a complete $c$-coloring.

PARTIAL-$(n,m,c)$ is NP-complete

Proof
. By reduction from 3-SAT. Consider the following gadget.


F 210( z)                                 WB       
F 210(¬z)                              WB WB
F 210( z)                           WB WB
F 210(¬z)                        WB WB
F 210( z)                        WB                  B   
F   .  . 
F   .  .
F   .  .                                             
F 210( y)                      WB                     
F 210(¬y)                   WB WB
F 210( y)                WB WB
F 210(¬y)             WB WB                   
F 210( y)             WB                         ?   ?
F   .  .                                         W   W
F   .  .                       F
F   .  .
F 210( x)           WB 
F 210(¬x)        WB WB
F 210( x)     WB WB
F 210(¬x)  WB WB
F 210( x)  WB                                    B 
F   .  .
F   .  .
F   .  .
F 210  0...                                      0...0
F 210  1...                                      1...1
F 210  2...                                      2...2
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF FFFFFFFFFFFFFFFFFFFFFF

Imagine that $( x)$ or $(neg x)$ are of single-character width. Let $W$ indicate true and $B$ indicate false. All positions in the grid will begin colored except for the positions indicated by variables (e.g. $(x)$ or $(neg x)$) and $?$'s (question marks).

New variables may be added by extending the construction vertically. The number of clauses in which a given variable $x$ appears will increase the number of rows of $x$ and $neg x$ needed.

For simplicity's sake the 3-SAT clause $(x vee y vee z)$ is shown. The core of the gadget consists of the two question marks, the adjacent two $W$'s, and the two $B$'s in the columns corresponding to the $W$'s. The two question marks create a $W$ rectangle if and only if all $x,y,z$ are $B$. One entry in the clause must be true. By placing similar constructions strictly to the right of existing constructions you may add clauses arbitrarily.

For readability the pictured gadget leaves many positions unspecified. These positions need to be filled with inactive colors which cannot affect the core function of the gadget. The spots marked $F$ indicate one example filler color. Additional filler colors can be generated for each otherwise unfilled position in the grid. (Note the $F$ in the center of the construction.) To fill an unfilled position in the grid, add a column of $F~'$ to the far left, put $F~'$ in the desired spot, and add a row of $F~'$ to the bottom of the grid with a gap in the column of the newly filled position.

The free colors $0,1,2,ldots$ show how arbitrary colors can be added without materially affecting the construction. Free colors can be used to fill the gaps in the bottom rows of filler colors.

责编内容by:Kevin Lawler (源链)。感谢您的支持!

您可能感兴趣的

The Alpha AXP, part 7: Memory access, loading unal... Last time, we look ed at loading aligned memory. Now we're going to look at unal...
未命名 千兆网卡作为 PCI 设备要遵循 PCI 设备的编程规范。 通过 pci_dev 可以获取 resource 字段用于 ioremap,然后通过 write...
vn.py发布v1.7.1 – CTA策略模块升级版 前后忙活了两个月,终于算是完成发布了v1.7.1的版本。这次新版本主要针对的是CTA策略相关的功能,按照几个主要的方向来介绍下。 交易委...
What brings women into coding? One day, on my Facebook group for women in tech, I asked this question: “How did...
The Most Compact of Zip Bombs, and File Size as Pe... ZipIt, a project that appeared as part of The Wrong’s “Scripting the ...