Timeline for A simplified Art Gallery Problem in a matrix
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2016 at 21:18 | answer | added | Paul Burchett | timeline score: 1 | |
| Apr 1, 2016 at 16:53 | comment | added | Gerhard Paseman | nikoli.com has a puzzle series called Akari. Doubtless there are discussion boards and some analysis on this puzzle type that may shed light (pun intended) on your problem. Gerhard "Be Glad For So Few" Paseman, 2016.04.01. | |
| Apr 1, 2016 at 16:18 | comment | added | Steven Stadnicki | I would be amazed if this problem (specifically, the threshold version 'is there a lamplighting of this grid with $k$ or fewer lamps?') isn't NP-complete. It seems like it would be pretty straightforward to craft 'gadgets' for doing signal propagation and boolean operations analagous to the ones that are used in many NP-completeness proofs (e.g. Minesweeper's), and contrariwise the question is clearly in NP. | |
| Apr 1, 2016 at 15:48 | history | edited | Stefan Kohl♦ | CC BY-SA 3.0 |
Added top-level tag.
|
| Apr 1, 2016 at 13:21 | answer | added | Per Alexandersson | timeline score: 1 | |
| Apr 1, 2016 at 12:42 | answer | added | Tony Huynh | timeline score: 3 | |
| Apr 1, 2016 at 11:32 | history | asked | Yijun Yuan | CC BY-SA 3.0 |