Are there polynomial-time algorithms whose input is global but output is local in nature? What I have in mind is a problem instead of an algorithm. It’s the satisfiability (SAT) problem. Each clause is global information, because it’s surrounded by a host of satisfiable assignments, or rather their inverses, in the search space. But the goal, a satisfying assignment, is very local, i.e., one point in the search space. I want example problems and solutions that might shed light on SAT.

  • 1
    $\begingroup$ What does it mean for an input or an output to be local or global? Can you give a definition of those terms? Have you looked at 2SAT? Perfect matching? HornSAT? $\endgroup$ – D.W. Jul 22 '20 at 20:06
  • $\begingroup$ @D.W. Basically I have in mind NP-complete problems. For an instance, the search space is global. Given information or input is global in nature; each represents not one individual point of the search space, but a big part of it, therefore it’s global. Each solution is one point in the search space and it’s local. 2SAT is too restrictive in that each clause is too simple to encode global structure. The entire search space or a big part of it is global, and on the other end of the spectrum each candidate solution point is local. $\endgroup$ – Zirui Wang Jul 23 '20 at 10:01
  • $\begingroup$ @D.W. So you are talking about the 2SAT/3SAT difference—why 2 literals can’t represent global information but 3 literals can? That’s a good question. $\endgroup$ – Zirui Wang Jul 23 '20 at 10:09

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.