As one of the comments under the article mentions, there is some discussion of what is now called P versus NP in the correspondence between Gödel and Von Neuman

As one of the comments under the article mentions, there is some discussion of what is now called P versus NP in the correspondence between Gödel and Von Neumann from 1956. Which is earlier than Cobham but later than Pocklington and was itself only discovered in the late 80s. [1][2] [1] http://www.cs.cmu.edu/~odonnell/15455-s17/hartmanis-on-godel-von-neumann.pdf http://www.cs.cmu.edu/~odonnell/15455-s17/hartmanis-on-godel... [2] https://www.cambridge.org/core/journals/bulletin-of-symbolic-logic/article/abs/von-neumann-godel-and-complexity-theory/8F133F1B5742612B7E118BDE7A59AF65 https://www.cambridge.org/core/journals/bulletin-of-symbolic...