0

Taking the example of boolean satisfiability problem. We might have something like:

$$(a \lor b \lor c \lor d)\land (a \lor d \lor e) \land (f \lor b \lor g)$$

The statement is that there is no algorithm acting on a general input that would give the answer in polynomial time with respect to the length of the input.

Do we assume that the algorithm is some kind of Turing machine that looks at the input character by character and moves the head one step left or one step right after each move updating some internal state, or is there another way to formulate how the algorithm should be expressed?

zooby
  • 4,343

1 Answers1

2

Yes, the usual idea is that Turing machines can do anything we intuitively think of as an algorithm. This claim is called the Church-Turing thesis.

So if P=NP, then there exists a correct and efficient algorithm (say, a Turing machine) for deciding all SAT problems. We can call this Algorithm A.

SAT is NP-complete, meaning it is the hardest kind of problem where proposed answers are easy to check. If P=NP, you can use Algorithm A as a subroutine to solve any NP problem at all.

If you were to discover Algorithm A, its existence would be a proof that P=NP.

(*The words easy and efficient, above, specifically mean polynomial time.)

user326210
  • 17,287