39 citations · 78 across the 10 of their papers we have counts for
Showing 2021Show all
2 papers · 1 filter
cs.CC2021
ZHED is NP-complete
Sagnik Saha, Erik D. Demaine
We prove that the 2017 puzzle game ZHED is NP-complete, even with just 1 tiles. Such a puzzle is defined by a set of unit-square 1 tiles in a square grid, and a target square of th…
cs.CC2021
NP-completeness of the Active Time Scheduling Problem
Sagnik Saha, Manish Purohit
In this paper, we study the active time scheduling problem. We are given n jobs with integral processing times each of which has an integral release time and deadline. The goal is…