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?