<p>[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.</p>

<p>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.</p>

<p>Although it seems unlikely that anyone will come up with such a uniform family of languages for every level of PH, the two surveys (<a href="http://ovid.cs.depaul.edu/documents/phcom.pdf" rel="nofollow">one</a>, <a href="http://ovid.cs.depaul.edu/documents/phmeth.ps" rel="nofollow">two</a>) by Schaefer and Umans discuss natural problems that at least "look different" from QBF for the first few levels of PH.</p>

CC BY-SA 2.5
2010-11-12T13:58:13.490Z
Nice connection to BH. :)
Kaveh
CC BY-SA 2.5
2010-11-12T02:02:45.497Z
2010-11-12T02:02:45.497Z
Joshua Grochow
<p>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$</p>

<p>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. <br></p>

<p>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.</p>

<p>Does anyone know of such a set of concrete, uniform problems that span a hierarchy?</p>

<p>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.</p>

CC BY-SA 2.5
2010-11-10T05:53:49.767Z
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".
Kaveh
CC BY-SA 2.5
2010-11-10T13:21:46.900Z
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.
Mark Reitblatt
CC BY-SA 2.5
2010-11-10T13:50:24.273Z
So the following would be an acceptable answer: Truth of a of totally quantified boolean formula with $k$ number of alternations gives the $k$-th level of polynomial hierarchy. There are many similar hierarchies defined using logical formulas/graphs/games.
Kaveh
CC BY-SA 2.5
2010-11-10T15:12:45.433Z
I should have been more specific. You can give a complete problem for each level of the hierarchies above by alternating quantifiers in an appropriate fashion. In fact, that's often how the arithmetic and analytic hierarchies are defined. But I'm looking for something simpler.
Mark Reitblatt
CC BY-SA 2.5
2010-11-10T15:38:02.277Z
"Simpler" is misleading. I really just want a different uniform characterization of these hierarchies. Sometimes it's just not clear (especially for the computability hierarchies) how to encode a quantified formula into your problem. But sometimes a very different looking game is easier. I want a new set of tools to toss in my bag.
Mark Reitblatt
CC BY-SA 2.5
2010-11-10T16:34:44.887Z
$k$th level of PH ≈ a two-player came that is played for $k$ rounds. But is this close to what you are looking for?
Jukka Suomela
CC BY-SA 2.5
2010-11-10T16:55:49.863Z
That just looks like TQBF lurking in a very thin disguise. I'm looking for something that feels fairly different.
Mark Reitblatt
CC BY-SA 2.5
2010-11-11T06:44:35.910Z
I don't know any and would be interested if there is one. The reason I suspect that finding such a class of problems is difficult if not impossible (well, you have undefined non-mathematical terms in your question so I can't prove this) is the following: Assume that there is a class of problems $Q_k$ for say PH which satisfy your conditions. Problem $Q_k$ is going to be complete for the $k$-th level of the hierarchy, so it should be reducible to/from the $TQBF_k$, and you need to prove this fact (directly or indirectly), and these proofs will be uniform in $k$.
Kaveh
CC BY-SA 2.5
2010-11-11T06:44:58.627Z
[continued] And this looks like what you have called "TQBF lurking in a very thin disguise".
Kaveh
CC BY-SA 2.5
2010-11-11T22:11:58.607Z
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.
Joshua Grochow
CC BY-SA 2.5
2010-11-11T23:54:09.977Z
@Josh Interesting. I wasn't aware of that conjecture. But the first google hit is to the CC blog, where it's suggested that the current belief is that it will turn out to be false. I guess the Myhill Isomorphism theorem is the equivalent problem for the Arithmetic hierarchy. Hmm.
Mark Reitblatt
CC BY-SA 2.5
2010-11-12T01:48:45.897Z
@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: http://dx.doi.org.proxy.uchicago.edu/10.1006/jcss.1997.1486
Joshua Grochow
CC BY-SA 2.5
2010-11-12T01:49:43.840Z
(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.)
Joshua Grochow
<cc.complexity-theory><computability>
Uniform hierarchy of problems that span complexity and computational hierarchies
Mark Reitblatt
# Uniform hierarchy of problems that span complexity and computational hierarchies

(Asked by: username_0 on 2010-11-10)

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.

**Tags:** cc.complexity-theory, computability

> **Comments:**
> **username_1**: 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".  
> **username_0**: 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.  
> **username_1**: So the following would be an acceptable answer: Truth of a of totally quantified boolean formula with $k$ number of alternations gives the $k$-th level of polynomial hierarchy. There are many similar hierarchies defined using logical formulas/graphs/games.  
> **username_0**: I should have been more specific. You can give a complete problem for each level of the hierarchies above by alternating quantifiers in an appropriate fashion. In fact, that's often how the arithmetic and analytic hierarchies are defined. But I'm looking for something simpler.  
> **username_0**: "Simpler" is misleading. I really just want a different uniform characterization of these hierarchies. Sometimes it's just not clear (especially for the computability hierarchies) how to encode a quantified formula into your problem. But sometimes a very different looking game is easier. I want a new set of tools to toss in my bag.  
> **username_2**: $k$th level of PH ≈ a two-player came that is played for $k$ rounds. But is this close to what you are looking for?  
> **username_0**: That just looks like TQBF lurking in a very thin disguise. I'm looking for something that feels fairly different.  
> **username_1**: I don't know any and would be interested if there is one. The reason I suspect that finding such a class of problems is difficult if not impossible (well, you have undefined non-mathematical terms in your question so I can't prove this) is the following: Assume that there is a class of problems $Q_k$ for say PH which satisfy your conditions. Problem $Q_k$ is going to be complete for the $k$-th level of the hierarchy, so it should be reducible to/from the $TQBF_k$, and you need to prove this fact (directly or indirectly), and these proofs will be uniform in $k$.  
> **username_1**: [continued] And this looks like what you have called "TQBF lurking in a very thin disguise".  
> **username_3**: Continuing username_1'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.  
> **username_0**: @Josh Interesting. I wasn't aware of that conjecture. But the first google hit is to the CC blog, where it's suggested that the current belief is that it will turn out to be false. I guess the Myhill Isomorphism theorem is the equivalent problem for the Arithmetic hierarchy. Hmm.  
> **username_3**: @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: http://dx.doi.org.proxy.uchicago.edu/10.1006/jcss.1997.1486  
> **username_3**: (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.)  

---

## 1 answers

### Answer by username_3 on 2010-11-12. Score: 3

[Building off of username_1'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](http://ovid.cs.depaul.edu/documents/phcom.pdf), [two](http://ovid.cs.depaul.edu/documents/phmeth.ps)) by Schaefer and Umans discuss natural problems that at least "look different" from QBF for the first few levels of PH.

> **Comments:**
> **username_1**: Nice connection to BH. :)  

---

