Skip to main content
6 votes

How to show that a problem is in $\Pi_1^1$?

The standard example of a $\Pi^1_1$ complete decision problem is the following: Is $e$ an index for a Turing machine which (halts on all inputs and) computes a well-ordering of $\mathbb{N}$? Let's ...
Noah Schweber's user avatar
6 votes

How to show that a problem is in $\Pi_1^1$?

I think that a good well-studied problem may be the "recurrent tiling problem". For more references (with many use cases) consult the paper "Recurring Dominoes: Making the Highly ...
Bartosz Bednarczyk's user avatar
5 votes

Is any function between $n$ and $n\log n$ time-constructible on a 1-tape TM?

[EDIT: This result was already observed in Corollary 4.6 of the following paper: Gajser, David, Verifying time complexity of Turing machines, Theor. Comput. Sci. 600, 86-97 (2015). ZBL1329.68111.] ...

Only top scored, non community-wiki answers of a minimum length are eligible