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