Post's Problem Revisited---A Complexity Dichotomy Perspective

Jin-Yi Cai

Emil Post initiated the investigation regarding the existence of r.e.
Turing degrees between 0 and 0'. The famous solution came independently
from Richard Friedberg and Albert Muchnik, who invented the finite
injury priority argument. The rest, as they say, is history---Recursion
Theory has blossomed into a formidable mathematical discipline.

Complexity Theory owes greatly to Recursion Theory in its early days.
Many basic concepts and proof techniques were borrowed directly from it.
However, recently the two subjects have diverged.

I would like to revisit Post's Problem. I will report on a
substantial new theory which has the philosophical underpinning that,
at least in Complexity Theory, maybe an anti-Friedberg-Muchnik theory
is the right answer.

We will present theorems which have the general flavor that, in a broad
class of relevant computational problems, there are really only two
levels of problem complexity: one is tractable, the other is complete.
I will survey a number of recent dichotomy theorems that achieve this
complete classification, in the setting of counting problems.
Specifically I will discuss
(1) Graph Homomorphisms,
(2) Counting Constraint Satisfaction Problems, and
(3) Holant Problems.

http://arxiv.org/abs/0903.4728
http://arxiv.org/abs/1008.0683
http://arxiv.org/abs/1204.6445

One speculation is that there might be a parallel theory one can
develop within Recursion Theory. Is it time that Complexity Theory
starts to pay back some debt it owes to Recursion Theory?

http://www.math.wisc.edu/~lempp/conf/swlc.html#cai