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?

  • 1
    $\begingroup$ What specifically is unclear (what "components")? You should at least get an understanding of reductions. $\endgroup$ – Juho Apr 26 '18 at 7:52
  • $\begingroup$ The paper seems to be self-contained, defining all terms used. $\endgroup$ – Yuval Filmus Apr 26 '18 at 10:45
  • $\begingroup$ 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. $\endgroup$ – David Richerby Apr 26 '18 at 10:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.