A Post on the Post Post

On Monday Richard Lipton wrote a nice piece on the work of Emil Post, a famous logician who had great results and even greater questions in the early days of recursion theory. I have a few comments and thought I would follow up with my own post.

As Lipton mentioned, Post showed that every language that is both c.e. and co-c.e. is computable. Lipton talks about the open complexity version, what he calls Post++: L is in P if and only if both L and its complement are in NP, or in my terms P = NP ∩ co-NP. Lipton seems to suggest that Post++ is true but consider the following language:

A = {(n,r) | There is a m that divides n with 1 < m ≤ r}

A is in both NP and co-NP (even UP and co-UP) by guessing the prime factors of n. If A is in P then you can factor n by binary search. So if you believe that Factoring is a hard problem you have to believe that Post++ is not true. Lipton alludes to this when he says Post++ would kill most crypto protocols.

Lipton then talks about Post’s problem: Show there are non-computable, incomplete computably enumerable sets. Post had a program for this problem: Find some property P of sets, show there are non-computable c.e. sets with property P and no complete sets have property P. Out of Post’s program came useful properties such as simplicity, mitoticity and autoreducbility  but it wasn’t the right approach to solve Post’s problem. A decade ago I co-authored a paper that talked about using polynomial-time version of autoreducibility to separate complexity classes but we were also unsuccessful so far in using it to prove any new separations.

Friedberg and Muchnik independently settled Post’s problem in the late 50’s (Ladner proved the complexity version, assuming, P ≠ NP in the 70’s). Lipton asks “why do open problems stay open for years and then get solved independently at about the same time?” The answer is they don’t, most open problems are not solved independently, Fermat’s Last Theorem, Primes in P, etc., but the few that do stand out.

In our field if you look at the most famous examples: Friedberg and Muchnik, Borodin and Trakhtenbrot, Cook and Levin, Immerman and Szelepcsényi, you have two people, one on each side of the Iron Curtain during the cold war in a time before we sent results electronically. It could take several years for results to travel giving a much larger window for “about the same time”.

To solve Post’s problem one needed “computational thinking,” in this case thinking of c.e. sets as being produced by a computational process. Post didn’t think of c.e. sets this way, they were called recursively enumerable back then. Friedberg and Muchnik were children of the new computer age and could make that intellectual leap needed to solve Post’s problem. That’s why Post’s program was solved in the US and Russia at about the same time.