0
$\begingroup$

Given the challenge of proving algorithmic bounds on the likes of 3-SAT to resolve P versus NP, I wondered whether it might be possible to use undecidability within an NP problem to ensure that we can never find any algorithm as an alternative to brute force. I couldn't find any references on this type of idea.

After playing with a number of problems I ended up back at a version of the halting problem as follows: for a given machine M, is there an n-bit input x such that M halts after n steps? Any particular solution can be checked in O(n) polynomial time by running the input on M and seeing if it halts after n steps.

However, to find a solution x out of a possible 2^n, the undecidability of the halting problem says in general we cannot know in advance if M will halt on any particular input, and the probability of halting cannot be known because it would contract this (Chaitin). Therefore we have to go through all possible O(2^n) programs until we find one that halts after n steps, while stopping all other candidate solutions after n+1 steps. This might therefore be an NP problem where undecidability ensures there is no polynomial time algorithm to solve it.

I'm new to complexity theory so would appreciate any feedback on potential flaws people see in this approach. Any related references also gratefully received. Thanks

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

I don't think the approach you outline is valid.

Therefore we have to go through all possible

Your "Therefore" does not follow. This is not an accurate deduction.

For one thing, the halting problem talks about decidability, i.e., existence of an algorithm that has unlimited time. Your problem asks about the case where the running time is limited to 2^n.

For another thing, there is no reason to believe one has to go through every possible input. It might be possible to quickly rule out some inputs, e.g., because they don't have the correct format and are rejected within the first few steps of the algorithm.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I tried the aproach o conclude from undicidable set to NP-complete sets to show, that we have to go through all possible solutions. see arxiv.org/abs/2108.09269 $\endgroup$
    – Reiner Czerwinski
    Feb 10 at 7:24
  • $\begingroup$ Thanks Reiner, exactly what I was thinking. Have you submitted your paper for publication? $\endgroup$
    – Brian
    Feb 10 at 10:47
  • $\begingroup$ @ReinerCzerwinski can you prove there is no polynomial-time way to compute the result of your NP function? you seem to assume there is no way to know whether 2^N different Turing machines halt in T steps in less than T*2^N time. You speak of worst-case time but that is worst-case for the class of machines you transform NP problems into, not necessarily worst-case for NP problems. Or sorry if I misunderstood the paper. $\endgroup$
    – user253751
    Mar 27 at 10:17
  • $\begingroup$ @ReinerCzerwinski for example, it takes O(2^N) (exponential) steps for a Turing machine to check if its input is 2^N 1's, but transforming the input into binary and transforming the machine to read binary allows it to be done in O(N) steps. Once again I didn't really have time to understand the paper so this is based on skimming it $\endgroup$
    – user253751
    Mar 27 at 10:19

Your Answer

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

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