# 3-SAT reduction to image matching problem

I have a research paper, Elastic image matching is NP-complete by Daniel Keysers and Walter Unger, that illustrates the reduction from 3-SAT to an image matching problem in order to prove that this problem is NP-Complete. It says that from 3-SAT formula we construct an equivalent image matching problem using a cost function $f$ such that $c(A(o),B(o),f) \leq 0$ iff the formula $o$ is satisfiable. And reduction from 3-SAT is performed using 3 steps:

• constructing the dependency graph $D(o)$
• $D(o)$ is drawn in the plane
• The drawing of $D(o)$ is refined to depict the logical behaviour of $o$.

We need to use components that act as building blocks for drawing the graph, which are the representation of connectors, crossing, variables and clauses.

This is the basic idea. Before I try to understand the reduction I couldn't understand the basic components they are talking about. Any hints to help understanding the problem?

• What specifically is unclear (what "components")? You should at least get an understanding of reductions. – Juho Apr 26 '18 at 7:52
• The paper seems to be self-contained, defining all terms used. – Yuval Filmus Apr 26 '18 at 10:45
• Could you give a bit more detail about what it is that you don't understand? Usually, reductions from 3-SAT work by representing the formula is a circuit with gadgets that act like wires and logic gates. – David Richerby Apr 26 '18 at 10:54