2

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.)

Vincent
  • 10,614
  • It's not clear what you mean by 'purely symbolically' here, or for that matter by 'verify'. The latter, particularly, has a formal meaning that I don't think you're applying here. – Steven Stadnicki Jun 12 '15 at 23:10
  • There's nothing "non-deterministic" here. If you accept a "closed-form" formula containing $n$ as a solution, then the algorithm that writes down that formula is a constant-time algorithm for the problem. – Robert Israel Jun 12 '15 at 23:29
  • Ok, I see the problem. Still finding the closed formula seems to take up more time than verifying that the numbers it produces fit the recursion. So what if we we make the precise form of the recursion part of the input, and require the output to be an expression of $p_k$ as a function of $k$? The time to check that a candidate solution fits the recursion does not depend on which $a_k$ are given in the beginning as initial conditions while the time it takes to find such a solution seemingly does. – Vincent Jun 13 '15 at 12:03

0 Answers0