Appologies if this question is utterly naive. I know very little about complexity classes, but like to learn more.
Consider the following problem. Given input $n$ (a natural number) we want to find the term $p_1$ in the sequence given by
$$p_n = 1/2(p_{n-1} + p_{n+1})$$ $$p_0 = 0; p_n = 1$$ (This problem has a nice interpretation that is irrelevant here, but see https://en.wikipedia.org/wiki/Gambler%27s_ruin#Fair_coin_flipping)
Now if we try to find $p_1$ deterministically we need to solve a system of $n$ linear equations which takes $O(n^2)$ time. However, if we guess the correct answer ($p_k = k/n$) we can easily verify that it is true purely symbolically, hence in constant time.
So my intuition is that this problem is not solvable in constant time, but it is solvable in 'non-deterministic constant time', so it is in NC but not C.
Perhaps I'm overlooking some smarter algorithm for solving systems of linear equations with lots of zeroes but that would only prove the C vs NC problem more interesting.
So my question is: is this a thing? Are these classes defined and known to be (un)equal?
(Perhaps my idea of non-deterministic constant time is wrong and we would need, given a candidate solution for $p_1$ presented as a fraction invest a logarithmic amount of time to check that it equals the theoretical solution $1/n$. But then still it would be faster to check the solution than to find it.)