Solving any coding challenge is NP-hard problem. You need to understand not only what you need to do but also how language in which you need to do it works. For example in game of Go you have huge amount of possible states but you have only couple of moves to transition to this states. In programming language every line of code has large space of states and it grows exponentially with every new line of code. Sure you can brute force "hello world" program but good luck with writing 1000 lines of code that work together to solve complex problem. Pattern matching will not help you, training based on github will not help you.
I think you meant to say "NP-hard" . And indeed, there are many program synthesis problems which are NP-hard, 2EXP-complete, or undecidable. But there are also many program synthesis algorithms which are polynomial time. If you use Windows, there might even be one running on your computer.
We've been studying this problem for close to 50 years. I think you see the basic problems, but we know a lot about what to do about them.
Which algorithm / program is this?
"PSPACE-complete is great news. It's the new poly-time." -- Moshe Vardi
SAT solvers are very fast. It's worst-case exponential, sure, but it's hard to find that worst-case. I just heard at lunch yesterday that MaxSAT is now also easily handling problems with millions of variables. I think I'd be scared if I found out what the record was for normal SAT.
So, how do you actually do synthesis? I could talk for quite a while about it.....but here's a pretty good intro-article: https://homes.cs.washington.edu/~bornholt/post/synthesis-for...
It's not that hard. Just generate a boolean circuit for the multiplication of 2 64 bit prime numbers and convert the circuit to a 3-SAT formula. I doubt any current SAT solver can solve that problem. If you could do it for 1024 bit primes a lot of cryptography would be toast.
EDIT: To be a bit more clear I mean that the circuit takes two n-bit numbers, multiplies them then compares the result to some known product of 2 primes. So by solving this circuit you factor the known integer.
EDIT2: Doesn't solving MaxSAT exactly imply that you can also solve SAT ? If there's a SAT solver that can handle million variable instances "easily" that's something I'd be really interested in hearing more about.
The circuit I described checks that the product of two arbitrary input integers is a specific known integer.
By solving the decision problem for each bit independently you can determine all bits of the 2 input integers and hence factor the known target.
To prove that statement you'd have to carefully define your terms.
If "Develop a polynomial time algorithm to determine whether any given 3SAT problem is satisfiable" is a valid coding challenge then the statement is obviously true.
On the other hand I doubt that solving the types of coding challenges that actually appear in competitions can be proven to be NP-hard because that would prove that humans are much better at solving NP-hard problems than any currently known algorithm. I don't think there is any such proof (though there may be some weak evidence for the proposition).
And by "known", I don't mean "in the AI's knowledge-base"; the AI would properly at least be able to hunt down textbooks and journal papers, read them, and learn problem-solving approaches from them. In other words, the AI would at least be as able to "do science" in the way that a grad student is expected to "do science."
What relation an AGI has to NP hardness is unclear. I think that if P=NP in the sense that a practical algorithm exists for solving large (ie. 10^9 variables) NP complete problems then AGI (even super-AGI) would probably follow. However I don't necessarily think that's a necessary condition for AGI to exist.