Zobrazeno 1 - 10
of 95
pro vyhledávání: '"Hearn, Robert A."'
Symmetry is at the heart of much of mathematics, physics, and art. Traditional geometric symmetry groups are defined in terms of isometries of the ambient space of a shape or pattern. If we slightly generalize this notion to allow the isometries to o
Externí odkaz:
http://arxiv.org/abs/2302.12950
We prove PSPACE-completeness of several reversible, fully deterministic systems. At the core, we develop a framework for such proofs (building on a result of Tsukiji and Hagiwara and a framework for motion planning through gadgets), showing that any
Externí odkaz:
http://arxiv.org/abs/2207.07229
Publikováno v:
In Cities January 2024 144
Autor:
Chiu, Man-Kwun, Demaine, Erik D., Diomidova, Jenny, Eppstein, David, Hearn, Robert A., Hesterberg, Adam, Korman, Matias, Parada, Irene, Rudoy, Mikhail
Given a set of point sites, a sona drawing is a single closed curve, disjoint from the sites and intersecting itself only in simple crossings, so that each bounded region of its complement contains exactly one of the sites. We prove that it is NP-har
Externí odkaz:
http://arxiv.org/abs/2007.15784
Publikováno v:
Theor. Comput. Sci. 806: 332-343, 2020
We consider the computational complexity of reconfiguration problems, in which one is given two combinatorial configurations satisfying some constraints, and is asked to transform one into the other using elementary transformations, while satisfying
Externí odkaz:
http://arxiv.org/abs/1805.04055
Autor:
Burke, Kyle, Demaine, Erik D., Gregg, Harrison, Hearn, Robert A., Hesterberg, Adam, Hoffmann, Michael, Ito, Hiro, Kostitsyna, Irina, Leonard, Jody, Löffler, Maarten, Santiago, Aaron, Schmidt, Christiane, Uehara, Ryuhei, Uno, Yushi, Williams, Aaron
We study the computational complexity of the Buttons \& Scissors game and obtain sharp thresholds with respect to several parameters. Specifically we show that the game is NP-complete for $C = 2$ colors but polytime solvable for $C = 1$. Similarly th
Externí odkaz:
http://arxiv.org/abs/1607.01826
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2006.
Includes bibliographical references (p. 147-153).
There is a fundamental connection between the notions of game and of compu
Includes bibliographical references (p. 147-153).
There is a fundamental connection between the notions of game and of compu
Externí odkaz:
http://hdl.handle.net/1721.1/37913
Autor:
Hearn, Robert A.
Most Artificial Intelligence (AI) work can be characterized as either ``high-level'' (e.g., logical, symbolic) or ``low-level'' (e.g., connectionist networks, behavior-based robotics). Each approach suffers from particular drawbacks. High-level AI us
Externí odkaz:
http://hdl.handle.net/1721.1/7116
Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2001.
Includes bibliographical references (p. 57-58).
Most Artificial Intelligence (AI) work can be characterized as either "high-le
Includes bibliographical references (p. 57-58).
Most Artificial Intelligence (AI) work can be characterized as either "high-le
Externí odkaz:
http://hdl.handle.net/1721.1/17510