Hierarquia uniforme de problemas que abrangem complexidade e hierarquias computacionais

Alguém conhece um conjunto de problemas que variam uniformemente e abrangem uma das hierarquias "interessantes" de complexidade e computabilidade? Por interessante, quero dizer, por exemplo, a Hierarquia Polinomial, a Hierarquia Aritmética ou a Hierarquia Analítica. Ou talvez (N) P, (N) EXP, 2 (N) EXP,$\ldots$

Mais concretamente: você pode fornecer um conjunto uniforme de problemas que caracterizam a Hierarquia Aritmética: . Mas estes nem sempre são os mais úteis para reduzir a problemas reais.$0, 0', \overline{0'}, 0'', \overline{0''},\ldots$

Por outro lado, o livro de Harel, Kozen e Tiuryn ​​tem um conjunto de problemas variados de ladrilhos que são NP, $\Pi^0_1$ , $\Sigma^0_2$ e $\Sigma^1_1$ completos. Os problemas são úteis para mostrar reduções, mas não está totalmente claro se eles se generalizam uniformemente para cobrir os outros níveis das hierarquias em que se inserem.

Alguém conhece esse conjunto de problemas concretos e uniformes que abrangem uma hierarquia?

EDIT: Apenas para esclarecimento, eu sei que as três hierarquias que dou acima têm definições padrão em termos de força do quantificador alternado. Não é isso que estou procurando. Estou procurando algo diferente, como um jogo em um gráfico ou um quebra-cabeça jogado com ladrilhos.

[Partindo da percepção de Kaveh nos comentários.] Parece improvável que alguém possa apresentar uma família de problemas significativamente diferentes da fórmula booleana quantificada, sem refutar o analógico PH da conjectura de isomorfismo Berman-Hartmanis. Sem isso, qualquer problema que surgir seria não apenas equivalente ao , mas de fato isomórfico. Uma maneira de definir o isomorfismo entre duas línguas aqui é usar uma única linguagem abstrata, mas codificar seus objetos (neste caso, fórmulas booleanas quantificadas) usando duas codificações booleanas diferentes.$QBF_k$

Por outro lado, o isomorfismo não é necessariamente um bom juiz do que é útil para as pessoas apresentarem provas. Afinal, na hierarquia aritmética, o Teorema do Isomorfismo de Myhill prova o análogo aritmético da conjectura do isomorfismo de BH (na verdade, isso é história ao contrário, pois BH foi motivado por Myhill). No entanto, como a pergunta aponta, existem várias caracterizações "de aparência diferente" de vários níveis, algumas das quais são mais úteis para provas do que outras.

Embora pareça improvável que alguém tenha uma família de idiomas tão uniforme para todos os níveis de PH, as duas pesquisas ( uma , duas ) de Schaefer e Umans discutem problemas naturais que pelo menos "parecem diferentes" do QBF para os primeiros níveis de PH.