New answers tagged np-hardness
1
Your problem is NP-hard, since it contains the Hamiltonian cycle problem on grid graphs as special case: Given a set of lattice points in the plane, is there a cycle in which all edges have lengths $1$ (and hence connect two horizontally or vertically adjacent lattice points.
The grid graph has a Hamiltonian cycle, if and only if the corresponding $n$ ...
8
The powering step fails. After the powering, each vertex is labeled with a neighborhood of the original graph. each edge checks that its endpoints agree on the intersection of their neighborhoods, and that this labeling satisfies the edges in this intersection. However, the edge cannot check anything about part of the labeling that lies outside the ...
8
[Now that the question's been clarified I'll post my previous comment as an answer.]
It's in $\mathsf{P}$. Start with unit propagation. Afterwards, what's left on the right-hand sides will be monotone, so will be satisfied by setting all remaining variables to True.
(If you want to count the number of solutions, on the other hand, that might be harder.)
Top 50 recent answers are included
