-1
$\begingroup$

To understand this proof you must first understand

  1. NP vs P problem
  2. The quantum eraser experiment
  3. True randomness

Before we start I must first assert things that have been proven to be true, if you question any of my assertions feel free to research them yourself.

  • True randomness does exist (demonstrated in quantum physics)
  • True randomness by definition creates objective unpredictability
  • Algorithms by definition can’t predict True randomness because it is objectively unpredictable (do not confuse with pseudo and statistical randomness which are predictable)
  • If true randomness exists it is inherent that a 3SAT problem can be created using the true randomness (will create one just to avoid questioning)
  • computers cannot create true randomness
  • If True randomness is applied to a NP complete problem it will prove P does not equal NP (what this proof is going to explain)

P does not equal NP because Boolean satisfiability and 3SAT cannot be solved in polynomial time. To prove this we will create a 3SAT problem using True randomness, which cannot be predicted by a computer or a deterministic algorithm.

To create this problem we will use the quantum eraser experiment multiple times. For each potential variable we will have one slit, in this example we will have 12 slits for the 12 variables, 3 slits for the boolean operators, and an infinite amount of slits to determine the length of the problem (which will be defined as the number of clauses in the problem).

How the slits work in the context of this problem:

  • Variables: we have 12 slits, whichever slit the photon goes through number 1-12 is the variable in that position, we run the experiment separate times for each variable position, the number of variables is determined by the length of the problem.

  • Boolean operators: we have 3 slits, whichever slit the photon goes through number 1-3 is the operator in that position. We run the experiment separate times for each operator position, the number of operators is determined by the length of the problem.

  • Length: an infinite amount of slits will be used to determine the length of the problem (which will be defined as the number of clauses in the problem). For example if the photon goes through slit 104 we will have 104 clauses in the problem.

The 3SAT blueprint would look like this if # shows a variable position, and ! shows an operator position.

(# ! # ! #) ! (# ! # ! #) ! (# ! # !#) etc

This is the pool of variables they can select from for the variable spots

(x1)
(x2)
(x3)
(x4)
(x5)
(x6)
(x7)
(x8)
(x9)
(x10)
(x11)
(x12) 

This is the pool of Boolean operators that can be selected for the operator spots.

  • The not operator (⇁)
  • The and operator (∧)
  • The or operator (∨)

I have now created a truly random problem, and by definition the result cannot be predicted. This assures that no math equation, function, or algorithm can be created to solve any of the problems we would generate as or more efficiently than a nondeterministic turing machine, meaning all of them would only be solvable in Nondeterministic Polynomial Time. They would only be solvable, because simply put we have assured that the only way to solve the problem is through brute force, in which a deterministic algorithm/turing machine cannot solve in polynomial time.

Finally P does not equal NP because true randomness by definition cannot be predicted by a deterministic algorithm, and therefore a deterministic turing machine would not be as efficient as a nondeterministic turing machine at solving a truly random 3SAT problem. Since we have created a 3SAT problem that is truly random in nature,(not pseudo random or statistically random). This means that we have finally proven that P cannot equal NP because the 3SAT problem we have created (an NP complete problem) cannot be solved in polynomial time, and a deterministic turing machine would be less efficient than a nondeterministic turing machine when solving it.

Summary

We have proven P does not equal NP by creating a NP complete problem (3SAT) with true randomness, completely eliminating the ability for deterministic algorithms to predict results, making it so that no deterministic machine could solve it faster than a nondeterministic one. This also proves that it couldn't be solved in polynomial time, this finally proves P does not equal NP.

Here are things that might have been confusing in my argument, because I absolutely suck at showing a clear train of thought.

The objective of this is to eliminate all predictability in the problem, making brute force or “systematic” guessing the only way to solve it. We know this because by definition true randomness is unpredictable (NOT pseudo or statistical randomness we encounter in the real world which is predictable). There is no correlation between 2 problems generated by this formula, meaning if you solve one in nondeterministic polynomial time then find some strange supposed relationship between variables, that doesn’t give you the ability to solve another in polynomial time, because there truly is no relation between variables. The only deterministic algorithm will be systematically guessing which would not be more efficient than a nondeterministic turing machine.

here is the link https://www.academia.edu/110544358/Using_True_Randomness_in_Quantum_Mechanics_to_Prove_P_Does_Not_Equal_NP

$\endgroup$
3
  • $\begingroup$ Comments have been moved to chat; please do not continue the discussion here. Before posting a comment below this one, please review the purposes of comments. Comments that do not request clarification or suggest improvements usually belong as an answer, on Computer Science Meta, or in Computer Science Chat. Comments continuing discussion may be removed. $\endgroup$
    – D.W.
    Dec 5, 2023 at 4:48
  • $\begingroup$ I don't see a question here. Please edit your post to explicitly state the question you want answered. A question normally ends with a "?". The question belongs in the body of the post. This is not a place to advertise or try to draw attention to results or arguments. The proper place for that is a personal blog, preprint server, etc. $\endgroup$
    – D.W.
    Dec 5, 2023 at 4:52
  • 2
    $\begingroup$ You are claiming to have a solution for a well-known, difficult open problem. This is an extraordinary claim requiring extraordinary evidence. It is not our goal here to make broad advances to science in a single post. See here for a related discussion. Also, our site's format is not designed for extended interaction or back-and-forth. If you'd like that, I suggest seeking a personal tutor. $\endgroup$
    – D.W.
    Dec 5, 2023 at 4:52

3 Answers 3

5
$\begingroup$

It's a bit unclear how you make a leap from "The problem is truly random" to "the result can't be predicted".

Let's imagine another example: you use True Randomness to shuffle N numbers. Does this stop sorting algorithms from working? Obviously no, they will still work in O(N log N) time. So why does True Randomness make any difference in 3SAT if it doesn't matter in sorting?

$\endgroup$
0
4
$\begingroup$

I think you don’t quite understand what non-deterministic means.

Take the travelling salesman problem. Say 50 cities, and we ask if you can visit all of them and return to the start within 1950 miles. A nondeterministic algorithm guesses correctly in which order to visit the 50 cities, you add the distances, it’s less than 1950 miles, you are done. Very efficient except we can’t build a machine that does this.

(It’s not just guessing, you also need to prove that the guess is the correct solution. So if I guess the number of beans in a big glass correctly, I still need to count it to verify the guess).

$\endgroup$
1
2
$\begingroup$

It seems like you misunderstand what NP stands for and what the 3SAT problem is. NP stands for Nondeterministic Polynomial, which means that a non-deterministic Turing machine can guess a solution to the problem and determine the solution is correct in polynomial time ("Nondeterministic Polynomial Time", 2019). A problem in 3SAT is in Conjunctive Normal Form (CNF) of clauses Ci such as the following:

P = C1 ^ C2 ^ ... ^ Cn

Each clause is disjunctive with 3 arbitrary terms chosen from a set X such as the following Ci = (Xi ∨ ~Xj ∨ Xk)

Therefore, a sample instance of the 3SAT is the following.

P = (X4 ∨ X2 ∨ ~X3) ^ (X1 ∨ ~X2 ∨ X3)

Specifically, we want to know whether there is an assignment of truth values to the terms such that P is true (Kleinberg & Tardos, 2005).

The point I'm trying to make is that you can't choose arbitrary operators to generate random instances of the 3SAT problem, which brings me to my other point. You are attempting to simply generate random instances of the 3SAT problem, but when we discuss these algorithms, we are typically, already discussing arbitrary instances of the problem.

References

Kleinberg, J., & Tardos, É. (2005). Algorithm Design. Pearson.

Nondeterministic Polynomial Time. (2019). DeepAI. https://deepai.org/machine-learning-glossary-and-terms/nondeterministic-polynomial-time

$\endgroup$

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.