# Why is this not a proof of P # NP

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?

• You have to look up the definitions of P and NP before you can prove anything useful about them. "Random processes running in the background" is not a useful concept when talking about Turing machines. Apr 8 at 18:03
• The random process in the background establishes the problem. You can be asked to solve a traveling salesman problem such that the hypothetical cities' coordinates have been generated by a random process. Apr 8 at 22:59
• $P$ and $NP$ are sets of decision problems, i.e., languages. What is the language $L$that you're claiming to be in $NP \setminus P$? This is not apparent from your description, which involves queries and background processes. I suspect that as soon as you try to formalize your idea you'll see that to get rid of this oracle you'll have to encode the table in the instance of your problem, which would immediately show the existence of a polynomial-time algorithm to decide $L$. Apr 9 at 10:21
• What on earth makes you think this is a proof that P ≠ NP? For a start, it needs to make sense. Apr 9 at 17:01

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.