2024/04/17 by Reiner Czerwinski, Czerwinski, Reiner
Computer Science · #03D15 #03D55 #68Q17 #69Q15 #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #F.1.3 #F.2.3 #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Logic, programming, and type systems #Polynomial and algebraic computation
paper · pdf · doi:10.48550/arxiv.2405.18439
openalex publication_date 2024/04/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The arithmetical hierarchy (AH) is similar to the polynomial hierarchy (PH). Unlike the PH, the AH does not collapse relative to any oracle. A language in the (k + 1)-st level of the AH is computable enumerable (c.e.) relative to the kth level. So, given an oracle in the kth level of the AH, we could use a black-box search to decide whether the input word is in the language. With very large padding arguments, i.e. the paddings grow faster than any relative to the level k of the AH computable function, we would construct a language contained in the k + 1 level of PH, if we use only a finite set of input words. From the oracle in AH, we would construct an analogue oracle at the kth level of PH. For the input words of the finite set, a word is in the language of AH, if and only if it is in the language of PH. And the input word is in the oracle set of AH, if and only if it is in the oracle of PH. As in the language of AH, we must apply a black-box search in the language of PH. So, we would also have exponentially many oracle queries in the language of PH. The PH does not collapse.