For finite polyomino regions, tileability by a pair of rectangles is NP-complete for all but trivial cases yet can be solved in quadratic time for simply connected regions. Through a series of reductions and improvements, we construct a set of 117 rectangles for which the tileability of simply connected regions is NP-complete.

Tiling by dominoes in the plane is a matching problem, and thus can be solved in polynomial time. While the decision problem remains polynomial in higher dimensions, we prove that the counting problem becomes #P-complete. We also establish NP- and #P-completeness results for another generalization of domino tilings to higher dimensions.

We show that tileability of cofinite regions is undecidable, even for some fixed set of tiles, but present an algorithm for solving the case where all tiles are rectangular. We also show that whether a finite region can be enlarged by tiles such that the resulting region becomes tileable is also undecidable. Moreover, the existence of a tileable rectangle by a set of polyominoes is also shown to be undecidable.

It is not surprising that tiles can emulate other computational systems such as Turing machines and cellular automata. Some of these connections and consequences are explored and outlined. In particular, there are conjectures in the theory of cellular automata that, if proved, could lead to improvements of results in the theory of tilings.

Background: Although some evidence suggests a link between high dietary sugar, glycemic index (GI), and glycemic load (GL) with increased cancer risk, the relationship with the risk of lung and UADT cancers and their interactions with glucose metabolism-related genetic variants remains largely unexplored. In addition, the contributions of GI and GL from different food sources have not yet been studied. Objective and Methods: We aimed to evaluate the associations of GI, GL and glucose metabolism-related genetic variants with lung cancer and UADT cancer susceptibility in a Los Angeles (LA) population-based case-control study. In this study population, we also evaluated novel interactions between glucose metabolism-related genetic variants, GI, GL, tobacco smoking and alcohol drinking for the susceptibility of lung cancer and UADT cancers. At the global level, we conducted a pooled analysis using the dataset from the International Head and Neck Cancer Epidemiology (INHANCE) consortium to assess the associations by gender, tobacco smoking, alcohol drinking intensity and histological types of head and neck cancer (HNC), specifically for oral cavity and pharyngeal cancer (OPC) and laryngeal cancer (LC). Results: In the LA population-based case-control study, an increased odds of lung cancer with high GI diet and a reduced odds of UADT cancer with high sugar diet were observed. Furthermore, the effect of GI, GL and sugar might be source-dependent and modulated by smoking status. In addition, genetic variants in the pathway of glucose metabolism may modify the susceptibility of lung and UADT cancers. In the pooled analysis of eight case–control studies within the INHANCE consortium, we found elevated odds of HNC and laryngeal cancer with a high GI diet, and decreased odds of oral and pharyngeal cancer with a high GL diet. Conclusion: These results confirm the associations between a high GI diet and increased susceptibility of lung and laryngeal cancer. In addition, the associations could be varied by food sources, tobacco smoking and alcohol drinking. Furthermore, the associations between polymorphisms in the genes involved in the glucose metabolism and lung and UADT cancer susceptibility were observed, with the interaction of SNPs and tobacco smoking for lung cancer on both additive and multiplicative scale.