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.


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?

  • 5
    $\begingroup$ 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. $\endgroup$ Commented Apr 8, 2023 at 18:03
  • $\begingroup$ 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. $\endgroup$
    – Newberry
    Commented Apr 8, 2023 at 22:59
  • 1
    $\begingroup$ $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$. $\endgroup$
    – Steven
    Commented Apr 9, 2023 at 10:21
  • $\begingroup$ What on earth makes you think this is a proof that P ≠ NP? For a start, it needs to make sense. $\endgroup$
    – gnasher729
    Commented Apr 9, 2023 at 17:01

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.