321 citations · 2k across the 200 of their papers we have counts for
Showing cs.CCShow all
3 papers · 1 filter
cs.CC2021★ 1 cited
The Complexity of Iterated Reversible Computation
David Eppstein
We study a class of functional problems reducible to computing for inputs and , where is a polynomial-time bijection. As we prove, the definition is robust…
cs.CC2018★ 7 cited
Reconfiguration of Satisfying Assignments and Subset Sums: Easy to Find, Hard to Connect
Jean Cardinal, Erik D. Demaine, David Eppstein +2
We consider the computational complexity of reconfiguration problems, in which one is given two combinatorial configurations satisfying some constraints, and is asked to transform…
cs.CC2000★ 6 cited
Phutball Endgames are Hard
Erik D. Demaine, Martin L. Demaine, David Eppstein
We show that, in John Conway's board game Phutball (or Philosopher's Football), it is NP-complete to determine whether the current player has a move that immediately wins the game.…