0
$\begingroup$

It is known that the $\mathbf{P}\overset{?}{=}\mathbf{NP}$ problem is equivalent to asking whether there exists a polynomial-time Turing machine that decides an $\mathbf{NP}$-complete problem. Let's say this problem is subset-sum. Now I'm considering enumerating all the Turing machines with fewer than $s$ states. Since the number of states are limited, the number of Turing machines we need to enumerate are limited. I want to select the Turing machine that decides the subset-sum problem in the fewest steps. By Rice's theorem, it is impossible to decide whether a Turing machine correctly solves the subset-sum problem, but we can design some test cases, feed them to the Turing machines and simulate their execution on these inputs. Those who pass all the tests are likely to successfully decide the problem. We can then manually check the correctness of the machines which consume the least steps. Another issue here is that a Turing machine may not halt, but we can set a step limit for each test case and terminate the execution of a machine if it has consumed all the available steps. If $\mathbf{P}=\mathbf{NP}$, the best machine we found may decide the subset-sum problem in polynomial time. If $\mathbf{P}\ne\mathbf{NP}$, it is still possible for us to find a machine that solves the subset-sum problem faster than any methods we've already known.

My questions are:

  1. Are there any loopholes in my idea?
  2. Is it practical to implement my idea (or an improved version of my idea)?

Note:

  1. We may not necessarily choose Turing machines as the computing model. We can also use $\lambda$-calculus and enumerate functions which consist of fewer than $s$ elementary functions, using $\beta$-reduction to assess time complexity.
  2. We assume that we can "understand" a Turing machine and if it provides a correct solution to the subset-sum problem, we can prove its correctness.
$\endgroup$

1 Answer 1

1
$\begingroup$

There are a lot of Turing machines, so no, this idea is completely unpractical (I don't think there is really a loophole, since you are considering many restrictions). For example, there are roughly $10^{140}$ machines with an alphabet of $5$ letters and $10$ states. Try to write a Turing machine that implement quicksort, and you will see that $10$ states is a very small number.

You could consider that this is the same reason we are not trying to prove the Riemann conjecture by enumerating all possible proofs and checking which are true.

$\endgroup$
1
  • $\begingroup$ I have found an algorithm similar to my idea on Wikipedia. And it is said to be "enormously impractical" :-) $\endgroup$
    – Soha
    Commented Jan 1, 2023 at 2:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.