Note: previously asked on Math.SE, with no response there.

I suspect you might be able to modify the proof of the special case (of the theorem that all countable linear orders are embeddable in the c.e. degrees) that $\omega+\omega^*$ is embeddable to at least show that effective gaps exist.

By 'combinatorial' are you thinking expanding out $X$ and $Y$ into formal power series in $u$ and $q$ and finding a way of equating terms? Do you have a combinatorial interpretation for either of them? (Very much looking forward to seeing if anyone has an answer to your question, incidentally; it's an excellent one!)

@PeterTaylor That makes perfect sense; thank you for the explanation!

@PeterTaylor How do you use Cayley-Hamilton for 2)? Polynomial division by the characteristic takes time $O(n)$ AFAIK; the squaring method is $O(\log n)$ which is AFAIK asymptotically optimal because it literally takes you that long to read the input $n$...

AFAIK 1) comes down to a special case of 2), and the best known for 2) are essentially the square-and-multiply algorithms based on the binary expansion of $n$ (which work just as well for finding matrix powers as for finding scalar powers).

Idle question: is there an expression for the (univariate) generating function for the diagonal? OEIS doesn't recognize the sequence...

@ZuhairAl-Johar My point is that you have to be very explicit about how you're building such an $f$ without parameter-free definability, because my first reading of the axioms would suggest that they do rule it out; if union and separation only exist in parameter-free versions then where does such an $f$ come from? If you mean that such an $f$ exists 'externally' then that seems no more problematic than the countable models of ZFC, where 'uncountable' sets exist because the bijections from them to $\aleph_0$ aren't part of the model.

@ZuhairAl-Johar If $f$ is not explicit, does it even exist in your system?

Just to mark a dead end, I'll note that neither the leading coefficients or the values of $p_n(1)$ seem to appear in OEIS.

This might be better suited for math.SE; I haven't gone all the way through it but it seems as though it should be fairly straightforward using the usual Fibonacci identities to simplify the fractional-part term and turn it into a Riemann integral limit.

Doesn't Rice's theorem here mean that there is no way, given an algorithm as input, of doing what you want?

First issue I can think of: how do you restrict your loopy games to those that are 'number-comparable'? And as to why the Dedekind construction is preferred, a large part of it is that the construction is well-known; it's a canonical method of constructing a complete linear order from any suitable linear order, and since $No$ is a linear order it makes sense to look at the 'standard' completion of it.

Perhaps 'It is practically determined' here is meant as 'empirical evidence suggests'?

You might want to have a look at Linear SAT: sciencedirect.com/science/article/pii/S0166218X18302695 — I think (though I have not done the math) that these constraints should lead to an exponential number of clauses.

Since directing each edge introduces a poset structure and a grading on the hypercube, you might have better luck checking in the world of boolean lattices and algebras.

Unfortunately, the main non-relativizing complexity result I know is a positive one (IP = PSPACE) so it's not really an example for OP.