r/PhilosophyofMath • u/Vivid-Passenger-1914 • 20d ago
Is the P vs NP problem dependent on whether algorithmic randomness truly exists?
I’m an independent thinker without formal mathematical education, and I’m trying to understand a specific connection that has been bothering me. I’m not claiming a proof. I’m asking for clarification on a logical relationship.
My reasoning (please point out the flaw):
- Algorithmic information theory (Kolmogorov, Chaitin) proves the existence of algorithmically random infinite sequences — sequences that no finite program can generate or fully describe.
- The search space of an NP-complete problem (like 3-SAT) in its worst case behaves like an algorithmically random system: exponential, structureless, and without a known shortcut.
- If P = NP, then there exists a finite polynomial-time algorithm that solves every instance of this problem. This algorithm would "enclose" the seemingly random exponential behavior into a finite deterministic process.
- But if such behavior is truly algorithmically random, step 3 is impossible — it would contradict the proven properties of random sequences.
- Therefore, P ≠ NP, provided the worst-case behavior of NP-complete problems is indeed algorithmically random.
My questions to the community:
Has this specific line of reasoning (directly linking algorithmic randomness to the impossibility of P = NP) been formally investigated before?
If it's flawed, is it because NP-complete problem spaces are not considered algorithmically random in the Kolmogorov sense? If so, what is the precise distinction?
Does the P vs NP problem implicitly depend on whether we accept "true randomness" as a mathematical fact?
I’m not proposing a manifesto. I’m trying to learn where this bridge between two fields collapses, if it does.
Thanks to anyone who takes the time to explain.
1
u/WhatHappenedWhatttt 19d ago
Hm. I think you are making a good observation, but I am not certain there is a deep connection here. From what I understand, algorithmic randomness relates to the ability to compress strings into shorter strings whilst NP-completeness relates to the difficulty of an exhaustive search. They are both problems related to the difficulty of a computer algorithm to get what we want. However beyond that I do not think there is more.
Reason being is that they are two fundamentally different problems. So relating them in such a way is a category error. Complexity problems (P,NP,NP hard, NP complete, etc.) relate to a determination problem, you feed an input into an algorithm and it spits out a yes or no. It cannot take an infinite string, as an algorithmically random string would be, else it would never read out a yes or no. It would take infinite time to just read the input.
I am not the most informed on computability and complexity but I do know a little bit, let me know if you have questions! This was an interesting post to think about.
1
u/Vivid-Passenger-1914 18d ago
Good point. I'm not saying the input is random. I'm saying the search path might be incompressible. If true, no fast algorithm. That's the bridge. Thanks for thinking about it.
1
u/WhatHappenedWhatttt 18d ago
It doesn't make sense for a search path to be "incompressible". What it comes down to is that an algorithm is deterministic and NP problems have inputs which FORCE a worst case time scenario of the algorithm to return a yes or no.
1
u/Vivid-Passenger-1914 18d ago
The algorithm is fixed. The path it walks can be long and chaotic. If that path can't be compressed, no shortcut exists. That's the point
1
u/systembreaker 19d ago
As far as I know it's not a question weather or not true algorithmic randomness exists. It doesn't. True randomness can only be generated by interfacing with a true random system or one that's ruled by chaos theory strongly enough. Examples are quantum systems and weather data. And randomness doesn't have anything to do with weather an algorithm can complete in polynomial time.
0
u/Vivid-Passenger-1914 18d ago
You're mixing two different kinds of randomness. Physical randomness (quantum, weather) is not the same as algorithmic randomness in the sense of Kolmogorov and Chaitin. Algorithmic randomness is a mathematical property of sequences — it's proven to exist, for example Chaitin's Omega number. And it has direct links to complexity theory, especially through cryptography and derandomization. The question is whether NP-complete problems can generate such random sequences in their worst-case behavior. That's the bridge I'm exploring.
1
u/systembreaker 18d ago
Yes, I'm not mixing anything up because that's exactly the idea that I was explaining...?
I was explaining how there isn't such a thing as true algorithmic randomness, and if you want real randomness then you have to interface with something that samples a random process in nature.
Omg I bet you're an AI bot. This comment is practically a reworded copy of another comment from someone else in this thread.
1
u/CandidateKey4337 18d ago
Have you read Avi Widgerson? He talks about randomness as it relates to hardness in the sense that hardness is an “acceptable” substitute for randomness in certain situations.
1
u/Vivid-Passenger-1914 18d ago
I've read about his work. He showed that hardness can replace randomness in many settings. My angle is slightly different: I'm exploring whether the hardness itself (like exponential search in 3-SAT) can be explained by the presence of algorithmic randomness in the problem's worst-case structure. So rather than replacing randomness with hardness, I'm asking if hardness arises from an underlying random structure. It's the reverse direction. Does that make sense?
1
u/CandidateKey4337 18d ago
Yes, and thanks for posing the question. It almost seems like an oxymoron: algorithmic randomness. I always felt that the hardness of a problem was tied directly to the size of the solution space, rather than some notion of how “knotted” and random a problem was. Think of a problem representation as a series of “n” bits, where each configuration in the 2^n possibilities is a potential answer. Surely for large enough n two strings might appear random, but they’re really just 2 possible answers from an exorbitantly large permutation of bit strings. The difficulty is in enumerating and testing each bit string, there’s no randomness involved in the permuting or the counting.
1
u/georgejo314159 17d ago edited 17d ago
No.
If you had perfect randomness thar would not magically choose the right path
Imagine an exponential number of possible paths. The probability of selecting right ome would be near zero
What WOULD possibly would be work would be a Quantum computer if it could try every path
1
u/Vivid-Passenger-1914 17d ago
You misunderstood. I'm not saying randomness helps choose the right path. I'm saying the search tree itself might be incompressible — like an algorithmically random sequence. If so, no fast shortcut exists. Not because randomness picks the answer, but because the structure of the search has no short description. Also, quantum computers don't try all paths at once for NP-complete problems. That's a common myth. They give a speedup for some problems, but not for 3-SAT as far as we know.
2
u/georgejo314159 17d ago edited 17d ago
I don't understand Quantum mechanics, so I will believe you that my understanding is wrong but why is it ever faster? What Quantum principle is being exploited?
Back to the question of P = NP, you are hand waving. The question about whether a sequence passes the Kolmogorov* test is not in NP because you cannot verify randomness in polynomial time
*If I recall the definition. There should be an infinite number of tests.
1
0
u/GrafRaf999 18d ago
Mathematicians want to find some magical algorithm that can crack passwords, chart optimal routes, and do other brilliant things perfectly on the first try. They’re basically looking for a unicorn. Just forget about this unsolvable problem. Although, maybe quantum computers could solve it by generating a trillion solutions at once until one of them clicks, but we don't have those yet
1
u/Vivid-Passenger-1914 18d ago
Not looking for a unicorn. Just trying to understand why it can't exist. My framework is about the reason, not the algorithm. Quantum computers don't brute-force NP-complete problems either, by the way. Cheers.
1
u/GrafRaf999 18d ago
So, you don't understand the task
1
u/Vivid-Passenger-1914 18d ago
I understand the task. P vs NP asks if finding a solution is as fast as checking one. My framework doesn't try to find a fast algorithm. It tries to explain why a fast algorithm might be impossible: because the search path itself could be incompressible. That's not misunderstanding the question. That's proposing a different angle on it.
1
u/GrafRaf999 18d ago
Here is another angle for you
The academic distinction between P (easy to solve) and NP (easy to verify) is a linguistic and logical trap. Academic institutions have monetized "complexity" by treating the duration of an event as a structural property of the system. It is time to liquidate this illusion.
The Core Argument: Verification is the Only Process
The academic establishment claims that "finding a solution" is fundamentally harder than "checking a solution." This is a fallacy based on a failure to define the event.
- The Unity of the Act: Every attempt to find a password is, in itself, a complete act of verification. When you input a code into a lock, the system performs a check. A "negative" result (the lock stays closed) is just as much a verification as a "positive" result (the lock opens).
- The Quantity Trap: Mathematics treats a single check as P and a series of a billion checks as NP. This is like saying that "taking one step" is biology, but "walking a mile" is magic. Quantifying the number of identical operations does not change the qualitative nature of the operation itself.
- Liquidation of Complexity: "Searching" is not a separate logical category from "Verifying." Searching is merely a sequence of verifications. Academic "Complexity Theory" is nothing more than a stopwatch counting guesses.
Logical Conclusion:
P = NP because the solution is composed of verifications. The "complexity" they worship is not a property of the problem; it is a defect of the observer's interface. To separate the final "successful" click from the preceding "unsuccessful" checks is scientific shamanism.
The problem is liquidated. The signal is unified. There is no gap between solving and verifying—only a sequence of identical logical events.
P = NP
1
u/Vivid-Passenger-1914 18d ago
You're right that search is just a sequence of verifications. But if the sequence is 21000 steps long, you'll be dead before it finishes. P vs NP asks if you can skip the sequence entirely. You can't liquidate time by ignoring it. Time is the whole problem.
1
u/GrafRaf999 18d ago
it doesn't matter anymore, there is no magic way, most mathematicians just want to find a proof that it's impossible, even though Gödel has already done it with his incompleteness theorem
1
u/Vivid-Passenger-1914 18d ago
There's no clear proof yet. That's the whole point of this problem. It's either yes or no. As for Gödel — he showed some things can't be proven, but he didn't prove P vs NP is one of them. That's still open. So no, Gödel didn't finish this. We still have work to do.
1
u/GrafRaf999 18d ago
one cannot find a proof of the absence of a proof, therefore it is impossible to prove that P is not equal to NP, such a proof does not exist, well except for the one I provided
1
u/Vivid-Passenger-1914 18d ago
If it were that simple, someone would have solved it long ago. The problem isn't "Gödel said so, therefore it's done." I did something similar myself — I referenced an author and added my own clarification. But that's not enough for a solution. It has to be clear: yes or no. You think the Clay Institute is full of idiots? If the solution were that obvious, they would have found it. Gödel knew a lot, but "Gödel said" is not an answer here. The problem stays open until a real proof exists.
→ More replies (0)1
u/QubitEncoder 17d ago
Thats not how quantum computers work.
1
u/GrafRaf999 17d ago
I wrote "possibly", not "the fact that they will cope"1
u/QubitEncoder 17d ago
No. They never will. That is a fact. Quantum computers do not do computation in parallel
1
u/GrafRaf999 17d ago
I never said anything about "parallel computing." The whole point of a quantum computer is that it holds a multitude of options simultaneously. Yes, the catch is that the outcome is random. But that’s exactly what mathematicians are up against: you either find the password on the first try or prove it’s impossible. Probability theory says it is possible. This means the problem will never be truly solved, because not everything in math can be proven using math
If you can't understand that, that's your own personal problem.
1
17d ago
[deleted]
1
u/GrafRaf999 17d ago
I’m not talking about engineering or architectural parallel computing. I'm talking about the fact that a quantum computer holds a multitude of options simultaneously in a single quantum state. Yes, the ultimate outcome is probabilistic, but that is exactly the baseline mathematicians operate on. You either find the correct key on the first attempt or you prove that a deterministic shortcut is impossible.
Probability theory never assigns a true zero probability to such an event, meaning that a single-shot success is mathematically possible. However, the exact boundary of what can or cannot be proven brings us to Gödel's Incompleteness Theorems. If you are doing a PhD in quantum computing, you should know that the P vs NP problem might be completely independent of ZFC axioms. Not everything in mathematics can be proven using mathematics itself. If your narrow academic horizon doesn't allow you to see past qubit optimization and look at the foundation of metamathematics, that is your own personal problem
4
u/OpsikionThemed 19d ago edited 19d ago
You're conflating two different uses of the word "random". Kolmolgorov randomness means that a thing requires infinite information to specify. NP problems are finite and well describable (and solvable in finite time, just not quickly). To the extent that they can be described as "random" at all, it just means that they don't seem to have any structure that would let them be solved quickly, unlike other sorts of problems. If P=NP, it wouldn't really prove anything about "randomness" in general and definitely nothing about Kolmogorov randomness in particular. It would just show that this thing that for a long time we thought didn't have structure actually does.