Questions tagged [cc.complexity-theory]

P versus NP and other resource-bounded computation.

7
votes
0answers
187 views
+50

Planar Exact Cover by even-size sets

Major edit on June 6, 2019: Replaced the target problem with a simpler (but equivalent) one. Is the following problem NP-complete? Planar Exact Cover by even-size sets Input: A set $U$, a ...