Why doesn't a simple equation like this solve P=NP

Question

Can’t we confirm P does not equal np based on simple equations

For example this problem will never be solved with an algorithm and can only be solved by guessing (nondeterministic)

Problem- You have to open a lock on a file you downloaded, you know there are six variables with specific randomly assigned numerical values(dice roll), if you get all the values correct the lock opens instantly and the file is accessible, if you get any of them wrong nothing happens. After you get the combination incorrect each number has a 50% chance of going down one and a 50% chance of going up one.

Here is the problem a,b,c,d,e,f=True or False

This is the information you have to work with- a<=1000 b<=1000 c<=1000 d<=1000 r<=1000 f<=1000

An example of an answer would be (104, 289, 31, 576, 942, 723) if it was false the you would see the word false on the screen, if it was correct the file would open

No function algorithm or equation can be created to solve this faster than a nondeterministic algorithm. Because functions, algorithms, and equations are all created based on patterns and correlations, and this lock is created to have no patterns. We know this because every variable is randomly assigned a number less than or equal to 1000, and all of those numbers have an equal chance of appearing. Each variable has no effect on the other variables' results. And each time it moves up or down 1 it is also completely random.

Since there's no pattern, no equation will be applicable to multiple versions of this problem, even if it is solved nondeterministically.

And since Mathematics is the science of patterns and relationships

Since there's no pattern, and there is no relationship between the values in one problem and the values in another, no formula or algorithm can be created to solve it in polynomial time, and therefore P does not equal NP.

I am only in highschool so I know this is probably stupid, but could someone explain if it’s wrong and why it’s wrong.

Answer 1

The problem isn't in NP because a computer can't (by itself) check whether or not a solution is correct. To check it, you have to try to open the lock, which requires the computer to interact with something else.

Answer 2

There seems to be some trouble with the definitions. First, one defines a finite alphabet $\Sigma$. You can choose $\{0, 1\}$ when encoding everything in binary, but you can also use all digits, letters of the English language, and some symbols. A problem or language is now a collection of allowed strings over the alphabet.

An example: You can form the language $L_1$ of all strings containing the substring "banana". Then "I like bananas." is an element of $L_1$, whereas "apple pie" is not.

Another example: The language $L_2$ of all prime numbers, written in decimal. Then "5" is an element of $L_2$, but "14" and "Italy" are not.

Now being in P or in NP is a property on languages. A language $L$ is in P if there is a deterministic Turing machine (think: deterministic computer program) that can tell you whether a given string lies in $L$ or not. It has to be finished after a number of computation steps that is at most a polynomial in the length of the given string. The definition for NP is similar, but the Turing machine may use non-determinism (i.e. it is allowed to guess).

Now in your concrete example it is unclear how it is to be formalized. You could interpret each lock as a separate language. This language $L$ then contains exactly one element, namely the combination opening the lock. $L$ is in P: If $w$ is the solution, there is a Turing machine comparing the input with $w$. If they are the same, the input is $L$. Otherwise, it is not. Note that you do not need to know what $w$ is. The existence of such a Turing machine is enough.

A more intricate approach could be to have the lock as a part of the strings of the language as well. The resulting language has the form $M = \{(l, s(l)) : l \in A\}$. Here $A$ is the set of possible locks and $s(l)$ denotes the solution opening a lock $l \in A$. Here the question of $M$ being depends heavily on how $s$ looks like (also on $A$, but let's not focus on that). You certainly cannot use a function that is easily calculated. In that case, a Turing machine given an input $(l, x)$ can just calculate the solution $s(l)$ and compare it to $x$.

In this case, the problem is that you have to include the lock in the formalization. If you can calculate the solution from the encoding of the lock easily, $M$ is in P. If not, one cannot expect $M$ to be in NP. Most experts believe that non-determinism does not help in calculating a function like this.

Answer 3

First of all, $\mathrm{NP}$ class contains only decision problems, i. e., problems that have an answer yes or no. And in your problem the answer is a sequence of numbers. So just by definition your problem has no chance to be a member of $\mathrm{NP}$.

You could pretend this problem to be a member of $\mathrm{FNP}$ class, which is defined as follows:

Given an input $x$ and a polynomial-time predicate $F(x,y)$, if there exists a $y$ satisfying $F(x,y)$ then output any such $y$, otherwise output 'no'.

In this case we need to understand that the result of every trial to open the lock is encoded in the function $f(y) = F(x, y)$ which is a part of the input. Depending on the way how you encode this function we could get a polynomially solvable problem (in terms of the input size), or an USAT (UNAMBIGUOUS-SAT) problem, or essentially any other problem from $\mathrm{FNP}$ class.

It is important to understand here that as soon as $F(x, \cdot)$ becomes a part of the input the brute force solution (i. e., simple testing each possible option one by one) becomes one of many possible solutions, but not the only one.