computational-complexity

Col is one of three basic placement games on graphs along with Snort and Node Kayles .  In all three, players take turns painting vertices their color, with a restriction based on what colors are neighboring.  In Col, you can't paint a vertex adjacent to another vertex that already has your color.  In Snort, you can't paint adjacent to a vertex in your opponent's color.  In Node Kayles, you can't…

P = NP? Not exactly, but here are some research questions from the Office of Technology. bjames@ftc.gov May 15, 2024 | 8:41AM P = NP? Not exactly, but here are some research questions from the Office of Technology. By Staff in the Office of Technology The scientific community has a history of creating and sharing lists of important or interesting questions. The mathematician Paul Erdős, for examp…

The hardest problem Solving it would net someone a $1 million prize, yet to the rest of us it would be priceless. Jacob Aron reports

(The CGT sessions were only held on the first day, so this is as far as my notes go.) In the afternoon sessions, I spoke first about placement games on graphs, some variants that could be applied to all of them, and the computational complexity of the resulting games (of which very little is known). Rebecca Milley went next, and this was the first time I'd ever heard an academic talk about Bowlin…

Last week, I mentioned we had some computational complexity results concerning the game NoGo , which was the "new game" played at the game workshop at BIRS this year. After getting more comfortable with the game play, it felt like the game might be another great example of PSPACE-completeness. I put some effort into solving this, knowing it would be great to resolve the complexity while at…