Why is this not a proof of P # NP

Question

Suppose that there is a set of strings such that for each n there is at most one string |w| = n. For any given n there is a 50:50 chance that such a string exists. These string can be arranged in a lookup table such that the binary value of the string is interpreted as an index, the table entry indicates yes/no i.e. the existence or non-existence of the string.

Example:

string      existence

---

0000        no
0001        no
0010        yes
0011        no  
1000        no
1001        no
1010        no
1011        no  

In this example there is one string of length n = 4, namely '0010'. For some values of n the entries will be all 'no'.

Suppose further that some random process running in the background is filling these tables. A program P(n) is supposed to indicate if a string of length n exists. It is apparent that no polynomial algorithm can always correctly answer the question as the existence/non-existence of a given string is completely random. It can query only n^c entries, for some c, of all the 2^n entries. However an NP program can query all the entries in the table in parallel.

Why is this not a proof that P # NP?

Answer 1

Polynomial time means a runtime that is a polynomial in the length of the input. The input is an encoding of the problem instance as a sequence of symbols from some finite alphabet. A problem that is solvable in polynomial time with respect to one encoding may not be with respect to another. (Technically the encoding is part of the problem statement, so those are two different problems, but they tend to be conflated in informal descriptions.)

You need to encode your table as a sequence of symbols. For example, it could be encoded as NNYNNNNN.... But then the problem is solvable in polynomial time—linear time, in fact—by scanning the input looking for the symbol Y. You could also encode it as a list of strings that exist in the table, but then the problem is again solvable in polynomial time, though the method is different.

If you could come up with an encoding for which you could show that a polynomial-time solution is impossible, but a parallel (angelically nondeterministic) solution is possible, then you really would have shown that P≠NP, but it is not so easy to do that. It's not good enough to make the relationship between the input and the table so complicated that you can't think of any efficient way to solve the problem. You have to prove that there is no way to do it that you haven't thought of.