New answers tagged

3 votes
Accepted

reference request: deciding validity of higher-order quantified boolean formulas is not Kalmar-elementary

One can be more precise than "non-elementary" and say that HOQBF is TOWER-complete — morally, TOWER is the complexity class just beyond elementary. This fact is explicitly stated and proved ...

Top 50 recent answers are included