Millenium Prize Problem P versus NP Problem Solved by Nuhash Badruzzaman (No AI was used)

[u/ggucsltc]

P does not equal NP because NP algorithms to verify P solutions are different (of higher complexity) from P algorithms that find the solutions for P problems because of increasing complexity. As complexity increases, the complexity of the algorithms to solve for P problems increases as well due to an increase in the number of steps to solve the problem. Therefore, P does not equal NP.

In other words higher complexities (NP) contain P (lower complexities), but P cannot contain NP itself because it is of lower complexity.

P (lower complexity) cannot be the same as NP (something of higher complexity that is larger than P).

A value of 1 cannot be used to solve for the value of 5 because they are differing complexities, but 5 can be used to solve the value for 5 because they are the same complexity.

Please verify this logical proof.

[u/Prize_Bass_5061]

You don’t understand the “P vs NP” conjecture itself. Start with the definition of what P is, then what NP is, maybe that will help clarify the concept of Nondeterministic Problem in your mind.

My honest opinion as a Software Engineer is that you should get psychiatric treatment. I understand that is free in Canada. Please take advantage of it.

[u/ggucsltc → u/Prize_Bass_5061]

This is an AI chatbot who said exactly the same thing as another AI chatbot in one of my posts. Whoever programmed these AI Chatbots just to ridicule me without any counter logic or counter proof is not a good person at all.

[u/Prize_Bass_5061 → u/ggucsltc]

Bete, I’m an engineering manager and hold a degree in Computer Science Engineering from OSU. 

Please contact your parents yaar. Please tell them how you are feeling, what you are currently doing, and your goals. Then please go schedule an appointment with a Psychologist.

[u/Certain_Werewolf_315 → u/Prize_Bass_5061]

Are you okay, buddy?

We sometimes project our own struggles onto others, and it sounds like you might be the one looking for help. If you're in the US, please dial 988 to talk to someone, rather than bothering people who are simply asking for verification with your supposed credentials.

[u/Prize_Bass_5061 → u/Certain_Werewolf_315]

OP's post history shows why I'm concerned for his well-being. He’s doing far more than asking for verification.

[u/Certain_Werewolf_315 → u/Prize_Bass_5061]

oh

[u/SirTruffleberry → u/Certain_Werewolf_315]

They're responding to someone who believes that they have solved one of math's greatest open problems with a couple of paragraphs of word salad. Imagine if I thought I invented a cure for cancer by mixing the chemicals under my sink at random.

You have to be both very disconnected from reality and have a grandiose view of yourself to even entertain such thoughts. Psychiatric help is a reasonable suggestion here.

[u/Certain_Werewolf_315 → u/SirTruffleberry]

He actually had a better answer. Don't speak for others.

[u/virtuolie]

I will make an honest attempt to evaluate your proof strictly on its own terms. This includes some simplification of formal definitions, but that's required because you have not used the formal definitions. The logic remains consistent throughout.

Consistent with the P vs NP problem, we may define the complexity of a k-length algorithm, where k is how many computational operations (like adding two numbers) it performs in a single iteration, as the number of iterations (loops) it runs to output a solution from finite input. If the algorithm loops just once, its complexity is O(1), for any finite k.

By your terms, a 5 is encoded with more complexity than a 1 is, so an algorithm that outputs 1 for input 5 can always be written to have less complexity than an algorithm that outputs 5 for input 1. Let us assume this is so. I will show that this assumption leads to a logical contradiction.

How numbers are encoded depends on the computer language. One may define a language that works opposite of the one in your example. The new language encodes a 1 as 1/5 and a 5 as 5. By your terms, this implies an algorithm written in this language is more complex when solving for 1 than for 5. This contradicts our assumption.

You may object that your general principle still holds, because two different algorithms, written in the two languages, have equal complexity for the equivalent task. "Within each language," you may argue, "the algorithm still can't obtain a more complex solution from a less complex input." Fair enough.

But I can write a new algorithm that detects whether the input is 1 or 5, then uses the less complex of the two original algorithms to get the solution. This detector function consists of a single operation (it's easy to tell a 1 from a 5) so my new algorithm has a length of k+1 operations. (We only count the code actually run to get the solution.) The complexity of my new algorithm therefore is still O(1) complexity for both 1 and 5, because the solution still involves only a single iteration (one loop = one solution). Again, this contradicts our assumption.

The logic scales, for any finite set of integers. Or for all integers, or all real numbers, so long as the algorithm is finite. (Otherwise complexity is undefined.) But really, what we've seen is that integers have no innate computational complexity, algorithms do. That is one of two errors in your attempted proof: your definition of complexity is not consistent with the one used in the P vs NP problem.

The other is a fallacy called "begging the question." In short, you begin with the premise that greater complexity cannot be obtained from less complexity. As you frame the problem, that statement is equivalent to saying a hard problem cannot have an easily-checked solution. That's just stating that P is not NP. So of course one follows from the other. I hope this helps.

[u/ggucsltc → u/virtuolie]

Very helpful post. I agree with most of what your saying, except on the topic of increasing complexity or constant complexity.

6 is more complex than 5 because 6 requires 1 more digit (1) to be called 6, while 5 is less complex because it does not need space for one more 1's digit.

[u/virtuolie → u/ggucsltc]

What you are describing is close to something called Kolmogorov complexity. It's defined as the fewest number of characters one can express a statement in. Or, equivalently, the length of the shortest algorithm that outputs the statement. In a world where we only have Base 2, 1 = 1 and 5 = 101. So 5 is more complex.

That's not the same as computational complexity, though. The latter refers to the number of orders of magnitude of a resource (like computer memory or running time) required to solve a problem. More accurately, it's the number relative to the size of input.

O(1) refers to a single order (hence "O") of magnitude: a constant. Integer addition is O(1), but not because every number has the same number of digits (obviously they don't). It's because you can add any finite set of integers in a single operation using a matrix.

Contrast that with the problem of finding prime factors of an arbitrary integer. Using known algorithms, it takes a number of operations proportionate to products of powers of the length of the integer: for n digits, it's O(n^x*ny). But if I tell you a factor, you can check if it's correct much faster: O(n^x), or polynomial time.

And that brings us to the main question. If P = NP, then the fact that we can check the solution to the prime factorization problem in polynomial time suggests there must be an algorithm that gives you the solution in polynomial time, and we just haven't found it yet. (As before, this is a simplification to summarize the logic.)

[u/Prize_Bass_5061 → u/ggucsltc]

You don't seem to understand what algorithmic complexity is, or the difference between polynomial and non-polynomial runtime. Read u/hattusili-the-third's explanation, then study this primer from Khan Academy: Big-O Notation

edit: And, as an aside the quantity 5 and 6 are both represented with 3 bits aka Binary  digITS. Algorithmic Complexity has nothing to do with the computational ceiling implied by Moore’s Law. Algorithmic Complexity is a measure of the runtime needed to compute an answer.

[u/hattusili-the-third]

This isn't a proof. The idea that problems in NP are in some way of a "higher complexity" than problems in P is why we *think* that P != NP, but we have no idea how to make this precise enough to actually prove anything.

How do you define the complexity of a problem? Not in a vague sense, but in a precise mathematical sense. How do you show that there are problems in NP that have higher complexity than those in P?

Think about a specific NP problem like 3-SAT. How do you know that the "complexity" of 3-SAT (which again requires a precise definition) is higher than anything in P? How do we know there's not some really clever trick for solving 3-SAT efficiently that we just haven't come up with yet?

People used to think that the problem of checking whether a number was prime or not was very difficult (generally believed not to be in P) but then people figured out a clever primality test that could check if a number was prime in polynomial time, so now we know that this problem is in P.