1

How can we reduce Boolean SAT problem to HALTING problem? I tried it, but have no idea how to begin.
Eventually, I wanted to prove HALT is NP-HARD, so is there a better method than this to prove HALT is NP-HARD?

Priyanshu
  • 21
  • 1
  • 6

1 Answers1

1

Basically, we can assume a Turing machine that considers all possible assignments:

  • If a satisfying assignment is found, the machine halts
  • Otherwise, it loops forever

if a satisfying assignment is not found then it runs forever. This machine halts if and only if the 3SAT instance is satisfiable. Given an input F (3Sat formula) to 3SAT, we pass the input into HALT(M, F) and see what the answer is.

Hadi GhahremanNezhad
  • 2,377
  • 5
  • 29
  • 58
  • how is this polynomial time reduction? for checking all the assignments the TM will take exponential time – Priyanshu Sep 12 '19 at 04:35
  • 1
    This is answered in [the link](https://stackoverflow.com/a/6990715/6129428) I put below your question. Only the reduction itself - that is, the construction of the TM that iterates over all the assignments - has to run in polynomial time. Solving the problem you reduced to (i.e., letting the TM run) does not need to be polynomial. Since the Turing machine has only constant size, mapping the input to a description of the mentioned Turing machine can be done in polynomial time. – Hadi GhahremanNezhad Sep 12 '19 at 12:45