
YinYang Puzzles are NPcomplete
We prove NPcompleteness of YinYang / ShiromaruKuromaru pencilandpap...
read it

Hardness of Token Swapping on Trees
Given a graph where every vertex has exactly one labeled token, how can ...
read it

New Results in Sona Drawing: Hardness and TSP Separation
Given a set of point sites, a sona drawing is a single closed curve, dis...
read it

Circumscribing Polygons and Polygonizations for Disjoint Line Segments
Given a planar straightline graph G=(V,E) in R^2, a circumscribing poly...
read it

Cookie Clicker
Cookie Clicker is a popular online incremental game where the goal of th...
read it

Computational Complexity of Motion Planning of a Robot through Simple Gadgets
We initiate a general theory for analyzing the complexity of motion plan...
read it

Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible
We analyze the computational complexity of the many types of penciland...
read it

Computational Complexity of Generalized Push Fight
We analyze the computational complexity of optimally playing the twopla...
read it

A simple proof that the (n^21)puzzle is hard
The 15 puzzle is a classic reconfiguration puzzle with fifteen uniquely ...
read it

Hamiltonicity is Hard in Thin or Polygonal Grid Graphs, but Easy in Thin Polygonal Grid Graphs
In 2007, Arkin et al. initiated a systematic study of the complexity of ...
read it

TreeResidue VertexBreaking: a new tool for proving hardness
In this paper, we introduce a new problem called TreeResidue VertexBre...
read it

Solving the Rubik's Cube Optimally is NPcomplete
In this paper, we prove that optimally solving an n × n × n Rubik's Cube...
read it
Mikhail Rudoy
is this you? claim profile