10
$\begingroup$

Does anyone know of a set of problems that vary uniformly and span one of the "interesting" hierarchies of complexity and computability? By interesting, I mean, for example, the Polynomial Hierarchy, the Arithmetic Hierarchy, or the Analytic Hierarchy. Or maybe (N)P, (N)EXP, 2(N)EXP, $\ldots$

More concretely: You can give a uniform set of problems that characterize the Arithmetic Hierarchy: $0, 0', \overline{0'}, 0'', \overline{0''},\ldots$. But these aren't always the most useful for reducing to actual problems.

On the other hand, the book by Harel, Kozen and Tiuryn has a set of varying tiling problems that are NP, $\Pi^0_1$, $\Sigma^0_2$ and $\Sigma^1_1$ complete. The problems are useful for showing reductions, but it isn't entirely clear if they generalize uniformly to cover the other levels of the hierarchies they sit in.

Does anyone know of such a set of concrete, uniform problems that span a hierarchy?

EDIT: Just for clarification, I know that the 3 hierarchies I give above all have standard definitions in terms of alternating quantifier strength. That's not what I'm looking for. I'm looking for something different, like a game on a graph or a puzzle played with tilings.

$\endgroup$
13
  • 1
    $\begingroup$ There are graph based problems (e.g. reachability) and logic based problems (evaluation of a circuit or a first-order formula). ps: have you tried making the tiling a game between two players with a specified number of rounds or limited computational power? btw, it might help if you clarify what you mean by the words "uniform" and "concrete". $\endgroup$
    – Kaveh
    Nov 10, 2010 at 5:53
  • $\begingroup$ Yes, there are graph or circuit problems which have variations complete for a couple of levels. But can you find analogues complete for all levels of a hierarchy? By uniform I mean that to go up in the hierarchy you just change some parameter in some uniform way. For example, you increase the number of X by one, where X is some parameter of the problem. By concrete I just informally mean accessible. I don't consider hierarchies of the halting problem to be particularly accessible. On the other hand, something like SAT or QBF is more concrete. $\endgroup$ Nov 10, 2010 at 13:21
  • 1
    $\begingroup$ Continuing Kaveh's comments: such a language is also likely to be p-isomorphic to TQBF, unless someone plans to prove that the Berman-Hartmanis isomorphism conjecture fails at some (or every) level of PH. In this case it would be a very thin disguise, since it would merely be a re-encoding of TQBF, that is to say, you wrote down the quantified propositional formulae using a different boolean encoding. $\endgroup$ Nov 11, 2010 at 22:11
  • 1
    $\begingroup$ @Mark: I don't have good intuition for the isomorphism conjecture. The original BH paper suggested it might be true; Joseph and Young then suggested that one-way functions might show it is false (basically: apply a one-way function to SAT to get an NP-complete set that is probably not isomorphic to SAT), but then Rogers showed relativized worlds realizing all four possibilities re: existence of one-way functions and the isomorphism conjecture. So I don't know if there's really consensus at the moment. Here's the Rogers paper: dx.doi.org.proxy.uchicago.edu/10.1006/jcss.1997.1486 $\endgroup$ Nov 12, 2010 at 1:48
  • 1
    $\begingroup$ (John Rogers' paper appears to be about 2 years later than the discussion on the CC blog, but I don't know the exact history of when he got the result, as opposed to when it was first published.) $\endgroup$ Nov 12, 2010 at 1:49

1 Answer 1

3
$\begingroup$

[Building off of Kaveh's insight in the comments.] It seems unlikely that someone could come up with a family of problems that is significantly different from quantified boolean formula, without disproving the PH-analog of the Berman-Hartmanis isomorphism conjecture. Without that, any problem you come up with would be not only equivalent to $QBF_k$, but in fact isomorphic to it. One way to define isomorphism between two languages here is to take a single abstract language, but encode its objects (in this case, quantified boolean formulae) using two different boolean encodings.

On the other hand, isomorphism isn't necessarily a good judge of what's useful for people to come up with proofs. After all, in the arithmetic hierarchy, Myhill's Isomorphism Theorem proves the arithmetic analog of the BH isomorphism conjecture (in fact, that's history backwards since BH was motivated by Myhill). Yet, as the question points out, there are several "different-looking" characterizations of various levels, some of which are more useful for proofs than others.

Although it seems unlikely that anyone will come up with such a uniform family of languages for every level of PH, the two surveys (one, two) by Schaefer and Umans discuss natural problems that at least "look different" from QBF for the first few levels of PH.

$\endgroup$
1
  • $\begingroup$ Nice connection to BH. :) $\endgroup$
    – Kaveh
    Nov 12, 2010 at 13:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.