Max 2SAT-3, Net, Euclidea: Techniques and Results in Computational Inapproximability

This Master’s thesis investigates three diverse problem domains through the lens of computational inapproximability: Max 2SAT-3, the Net tile-rotating puzzle family, and the mobile game Euclidea. Max 2SAT-3 is a problem long known to be APX-complete, but finding a clear proof is harder than one might expect. We examine the history of Max 2SAT-3, addressing past misconceptions and clarifying where the reduction chain has been opaque, and present a novel proof of its APX-completeness. Net variants form a wide class of puzzles with lots of potential for future research. We introduce a natural optimization variant of Net and demonstrate its inapproximability, as well as consolidate existing findings and present other new results. Euclidea is a mobile game based on Euclidean straightedge-and-compass constructions. We define the game as an optimization problem and establish its APX-hardness, as well as discuss challenges in upper-bounding its complexity, relating to current knowledge gaps regarding the constructible and algebraic numbers.

Name thesis:degree_name

Master

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2024

Author dc:creator

• Luo, Victor

Advisor dc:contributor.advisor

• Demaine, Erik D.

Statement dc:rights

• Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0)
• Copyright retained by author(s)

Licence dc:rights.uri

• https://creativecommons.org/licenses/by-nc-nd/4.0/

Handle dc:identifier.uri

https://hdl.handle.net/1721.1/156791

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/156791