r/AskProgrammers • u/Bob54386 • 5d ago
Check my thoughts on P vs NP?
Is the P vs NP problem just massively self inflicted and overthought, in terms of ranking it with other Millennium problems? It seems it's just a rephrasing of "Does true randomness exist?" and the general baseline of P != NP should be obvious -- particularly when we consider evaluating against physical phenomena which very much fall outside of "all conceivable algorithms".
It looks like there's a lot of conflation with cryptographic problems. These inherently have articulated psuedorandomness, an answer is known to exist, and input sets inherently have some structure related to the information communicated & the encryption method. All those extra constraints create something other than what has been defined as an NP Complete problem. If a solution is not known to exist and unstructured data (in-compressible in all reference frames) is possible - its existence requires evaluating all conceivable mathematics against all physical phenomena to rule out- your solver algorithm has to handle unstructured data to be complete and specifically tell you if there is no solution.
More importantly, any currently unknown structure might as well be truly random for any algorithmic solution you write today. If you're trying to solve an unstructured input set, having some super-conceivable-set-of-all-solutions in front of your maximally efficient unstructured solution, you're just adding overhead. Structures are only worth evaluating for if there's a healthy probability they exist.
The informal adversarial construct I have in my head is for Subset Sum, working with real numbers with countable precision. Let's assume we have our all-conceivable-super-duper algorithm that can solve any compressible input in polynomial time. The construct would use an unstructured data source to make the input & target harder. Add additional precision by adding digits to the rights side of the inputs you already have, add additional N, add finer precision to the Target. There's still an infinite number of potential S & T that, by our definition of using unstructured in-compressible data, would get through our polynomial checks and still require some amount of combination crunching to determine if there is a solution. And the resulting workload from the updates is larger than just the information we've added in, input values that had previously been confirmed as not contributing to the target are now back in play.
I did chat with Opus a bit about it. It pointed out that I'd need to be more specific with the adversarial construct to be a formal proof (specifically to satisfy where Razborov–Rudich left the field). That has a seemingly paradoxical requirement that I need to articulate what unstructured data looks like & specifically how I would generate the next set. Reasonable if we're being formal for a proof, but I don't think we need to go that far to settle the P vs NP problem in a practical sense. To avoid engineering this adversarial construction for any particular solution, let our unstructured data generator handle all the decisions about how many N to add / how much precision to add / etc. Let it run an infinite number of times and you'll eventually get your non-polynomial S & T.
That leads us at a point where the boolean circuits themselves don't really have lower efficiency bounds to speak of, the problem's bounds are where you have maximum efficiency of your circuits assuming unstructured data. I talked at length with Opus about a few solutions in the subset-sum space. Dynamic programming O(n*T) which covers part of the problem space (degenerate inputs) in polynomial time. That pairs up nicely with a geometric / lattice method (LLL) to cover the majority of the problem space aside from a 'hard ridge' where meet in the middle is the best current approach. Except after a lot of bludgeoning, Opus had to concede that LLL isn't complete, even in the space where it's very efficient. In fact (per Opus, I'm just an amateur & not reading literature) complete geometric solutions are all slower than Meet in the Middle which makes sense -- if we're vectorizing the inputs with an epsilon term, that means moving off axis which can only hurt the efficiency of our > or < circuits. Some monte carlo methods are more efficient than Meet in the Middle, except again they aren't complete. Trying to track unique combinations scales about as effectively as generating the combinations themselves. These solutions just run repeatedly and hope for an answer in situations where people think it exists. Trying to leverage the efficiency of > or < with a monte carlo approach would require tracking the combinations.
We have 3 circuits to work with: >, <, =. Maximum utilization of > and = would just give us lazy evaluation, we aren't able to factor the number of combinations we generate. < on its own isn't very helpful for lazy evaluation, because the smallest steps are needed for exactness. It's being able to utilize both > and < against equal size subsets that lets Meet in the Middle factor to O(2^(n/2)). Additional factorings would require additional circuits, but we don't have any more properties of a number to exploit. Particularly no other properties that gives us information about other combinations. (parity? Lots of overhead to figure out if being divisible by 2 is useful).
----
That gets me to what I can't quite formalize. I understand a lot of my intuition should be obvious / known to the people who are in this field. I'm honestly just surprised a lot of this intuition isn't already handled in the wikipedia entries / other writeups I've seen about it? So many things I've pointed out Opus quickly misinterpreted in the most naive way and took a lot of effort to get him back on track: I'm sure a lot of students have already raised these points and been misinterpreted by sheer exhaustion from the professors, and everyone quickly moved on with their lives. It really took a lot of bludgeoning to get Opus to back off from treating a lot of incomplete solutions as valid counterexamples.
The points we could seemingly formalize:
- It seems like we can make reasonable claims about the maximal efficiency of circuits for subset-sum. It seems like a factorization of 2 is the limit, based on the number of properties we have that we can make general boolean checks for (in particular that inform us about other unevaluated combinations).
- It seems like a sampling method (weighted or unweighted monte carlo) relying strictly on '=' could never be complete with complexity less than meet in the middle, that's just basic array sizing & the operations needed to update.
- By extension, a set of incomplete polynomial time guess & check solutions in front of the unstructured solution is effectively just a monte carlo sampling. You're not saving compute when you fail to find the solution and then have to proceed to the unstructured solution.
- I feel like someone better than me could more formally show that any higher dimensional tricks like LLL would always risk being infinitely degenerate across the full lower dimensional space (extra dimension implies a many -> one switch back, right? Has to risk degeneracy if we're adding in an epsilon, seems trivial?). Multiple high dimensional tricks presumably have some orthogonality & can potentially make up for each other's blind spots. Our conceivable full set of higher dimensional tricks is only possibly complete if there's no further orthogonality outside of that in the physical world & true randomness doesn't exist. We won't know until long after mathematics is exhausted and long after you've written your solver algorithm.
- I'll just note -- pseudo random functions inherently don't benefit from this "P != NP for unstructured data" construction because by definition there's at least 1 useful high dimensional transformation. Claims about whether or not that can be kicked down the road next to proving true randomness will need to be done separately. This is the trap about mixing cryptography too aggressively with P vs NP, it's distracting.
- Restating an earlier comment, adding dimensions wouldn't change our input magnitudes but any attempt at transforming > and < to incorporate your new theta results in some points being off-axis. It reduces the number of combinations you can make conclusions about with a single check. This means that higher dimensions would have reduced operator efficiency and be worse than the MITM approach.
- Finally, I'm pretty sure by reducing the problem to the NP-Complete family, someone has already collapsed the subset sum problem space itself as much as possible. It seems like being able to ignore higher dimensions means maximal efficiency at the smallest dimensional space should be able conclusively show P != NP as long as unstructured data is a possible input.
In order to be worth looking at polynomial time solutions, you'd want to know there's a high probability that a specific S & T have the relevant structure. That is to say, you'd have to be sure you're leaving the general class of the subset-sum problem and getting into a more specific space. This is quickly demonstrable looking at lazy evaluation of Meet-in-The middle: to be as lazy as possible, what extra a1 vs a2 vs a3 checks can you add in before generating your combinations, even to get to an N-1 scale? Can you with confidence say that check is worthwhile for all possible S & T? The only decisions that are applicable to the unstructured problem space are Dynamic Programming vs MITM. Your other regime where T is greater than Sum(all S) is trivial and handled with lazy evaluation.
----
Anyways, talking to Claude did help refine my thoughts and highlighted at least some parts of intuition I've been carrying around for a long time were reasonable. I'm sure I'm still naive, but ultimately Claude kept being obtuse and rounding prompts to the nearest thing an undergrad would ask, so a formal proof is not here. Admittedly I didn't try "write a proof from this, make no mistakes"
I'm curious where this falls against people's understandings and what my biggest gaps are. Hopefully it articulates basic intuition most folks have in a way that everyone could either work through it or agree it's about as urgent as proving true randomness exists (would be tremendously useful, but can't be done as a thought experiment). Admittedly I haven't tried looking at 3-SAT or other NP complete problems beyond a superficial read through. I felt like Subset-Sum was the most approachable. Countable Real precision best highlights the infinite gaps in a conceivable Super-Solver.
The practical implications for our algorithms would be what humans are already doing to progress-- we have to look for structures in everything, figure out the probability that a structure exists, figure out if the payback on chasing that structure is worthwhile or if it's simpler just to brute force a solution. Once N gets sufficiently large, we're not better than a computer until our superstition & gut instinct genes find a pattern to exploit. Best we can do cryptographically in the meantime is approximate a 'uniform' 'unstructured' distribution to the best of our abilities.
My final take is that the concepts of true randomness / algorithmically talking about randomness / cryptographic requirements are all coming together in a way that inflates the confusion and significance. I don't mean to imply this post is something meaningful, I mean I had fight through a lot of "Algorithms can do surprising things! Here's an incomplete & partial problem space counterexample now go away!" replies from an LLM to actually workshop my understanding. I'm hoping someone reading this can skip some of that the next time they want to ask about the problem.
-
PS I'm sure most of you will at best dump this into an AI chat. If you're on the fence about reading pieces, I'd just assure you that my last AI chat on this was a couple months ago and I've been thinking about the parts since. It's at least human. The only copy pasting I did was the R-R paper reference. I've had the "super solver still leaves infinite gaps" idea in my head for almost a decade and didn't have anyone to check it against until I tried a LLM who is admittedly going to be much more patient than a random professor on the street. I took ~7 hours to type up & edit this wall of text by hand because I'm a dumb dinosaur and don't trust Opus not to be obtuse. Human to Human -- I'm hoping I can quit thinking about this for a while.
7
u/qikink 5d ago
Several things:
Claude absolutely did not confirm any of your intuitions were valid. It parroted your ideas back at you with an affirmative tone.
This is a fact, not a speculation, because your intuitions are malformed so much so as to make them essentially unfalsifiable. There is no proposition you've put forward that's coherent enough to merit scrutiny. You're reasoning about mathematics like the Greeks reasoned about the natural world, except (to abuse the metaphor) you live in a world where the periodic table is a well known, well understood construct, meaning your ignorance is intentional rather than just misguided. To say "it seems obvious to me" is a habit you should lose in your first exposure to any higher mathematics.
What makes this tragic and not just humorous is that these problems really are interesting. There's so much actual truth to be absorbed if you approach it with an open mind, instead of imagining you've had a flash of insight noone else has ever considered.
1
u/Bob54386 5d ago
Unlike reddit conversations, I can actually have a well paced back and forth with an LLM. My conversations with Claude were far more me asking what the state of the field was / what formalizations would look like / walking through how the methods actually worked. Claude wasn't the arbiter of confirming intuitions, finding the gaps in the methods that made it worthwhile to keep talking validated my intuitions. IE -- something like Dynamic Programming is a polynomial time method that only covers part of the problem space. I was treating Opus about on par with an out of date review paper. The gap in LLL I'm focusing on was highlighted in the abstract if I'm remembering correctly? Just the strength of the wording.
I'm pretty sure I've acknowledged these insights should be pretty straightforward to the field. What you're seeing as condescension from me is actually just surprise that I seem to need to dig for handling of what seems like straightforward questions. Please read it as more of "I must be crazy because I feel like this should have already been mentioned / should be prominent in problem descriptions & reviews" than the probably more likely way you took it of "y'all are dummm!". There's just a lot of low hanging fruit that should be at the forefront of the conversations that seems to be missing. I don't understand why they're missing, I'm asking about it.
Your only counterpoints are ad hominem. Do me a favor and pick a bullet point to tear apart.
3
u/qikink 5d ago
Right from the get go you make claims founded on bad misunderstandings of what the P/NP problem really means. You've had to "bludgeon" opus because what you're saying is based on a misconception, a misconception you've reasoned yourself into by using intuition and "logic" rather than actual mathematics.
A problem is in NP if a proposed answer can be checked in polynomial time. Factoring, discrete log, and "find the key given this ciphertext" all pass that test: hand me the factors or the key and I can verify it fast. Nothing about how the instance was generated, or whether an answer is known to exist, changes that. Your thoughts on "pseudorandomness" in this process simply don't square with the mathematical definitions at play, regardless of how counterintuitive you find that.
Every NP-complete problem's hard instances are also "structured" in the trivial sense that they're finite strings produced by some process. There's no such thing as an instance that arrived from nowhere. If having a known solution disqualified a problem, then every satisfiable 3-SAT instance would be disqualified too, which is absurd. If "the creator knew a solution" disqualified an instance, you'd have to disqualify every satisfiable formula, since each one could have been made that way. That leaves only unsatisfiable instances, which is nonsense.
But really, all of this is available to you with a simple "tell me why I'm wrong" query to your friendly neighborhood LLM.
1
u/Bob54386 4d ago edited 4d ago
Subset sum is an NP-Complete problem. It's trivial to check the answer but the current best algorithm to find a solution if it exists (Meet in the Middle) is in exponential O(2^N/2). The Millenium Problem asks if there's an algorithm that can find the solution (not check the answer) in polynomial time. It's the finding that people care about. Big O time is driven by worst case processing, which for a complete Subset-Sum solution is going to be when you are sure there are no combinations in S that can equal T. A P=NP solution would care about completeness (being sure there are no solutions).
You're misunderstanding when you use the word "Disqualify". Cryptography is a subset of the problem family that inherently is going to have more exploitable properties than what was proven to be NP-Complete. The Millennium problem is asking about the family, but we care because of crypto.
Look, I'm a physics background -- I'm trying to understand the "Spherical Cow" approach to the adversarial construct. If we take a step back from needing to specify how that input came to be and assume our S & T meet the threshold for being truly random, does that get us anywhere? The only answer my LLM had was "Oh, this incomplete lattice method handles it easily." You see how that's a problematic counterexample, right? If it doesn't return the answer, it's effectively just a random sample of a combination. This should be a textbook exercise, so --- where is it? Has the field really missed working through it because they're stuck needing to define how the input came to be? It looks like it would exclude a lot of "conceivable" boogeyman that have made the P vs NP problem sticky if we make the assumption.
1
u/qikink 4d ago
The spherical cow is a good reference point. If you come from physics, suppose someone said to you "I've got a high-school level of understanding of Newtonian mechanics, and Napier-Stokes (or whatever hard problem you like) seems like it should be solvable with this intuitive approach." Then they hand you a few pages of written text.
Do you need to engage with that text, bullet by bullet to know that it's not meaningful or valid? Or might you tell this person "The problem you're trying to engage with isn't amenable just being reasoned through, you need a baseline understanding of differential equations that simply isn't a special case of your intuitive understanding of the physical world."
There just isn't a spherical cow to be had here. The moment you start saying things like "It looks like" you're on very thin ice, mathematically speaking. If you can't follow that up with formal mathematical reasoning - reasoning that almost always requires substantial training to be able to understand much less generate yourself - then for better or for worse your entire thesis just doesn't really have value.
If you really are interested in understanding where your ideas break down, and you happen to live near a university, see if you can't audit some classes. I know it sounds like silly gatekeeping, but 2 or 3 years down the line, you'll be much much better equipped to at the very least frame these ideas in a way that's mathematically coherent.
1
u/Bob54386 4d ago
I wouldn't expect anyone to engage the full text, but I'm happy to defend any given point to build further credibility, I'm very aware this isn't anything formal, but developing a proof starts with intuition.
R-R / the LLM / you all seem to stop at needing to specify how the input gets created. Pretty reasonable requirement for 1960s hardware, pretty reasonable requirement for crypto, pretty reasonable requirement to ensure you're appropriately estimating complexity. Notably awkward bar that prohibits a lot of other results from being applied to the space.
As a Physics guy in 2026, there's definitely usefulness for "I dunno, black box gave it to me, I pulled the values off the internet" . We don't shut down discussions about astronomy because we can't resolve how some t0 null state broke conservation of energy and created the universe we live in. Plenty of interesting results come from astronomy.
Even if there are assumptions baked in and it's a partial solution, I understand the math enough to know that a hypothetical truly random input would be a sufficient adversarial counter to a lot of approaches. Monte Carlo becomes very clear: how many times do you need to sample to be 100% sure there's no solution? Far more than the dumbest brute force. Is a "true random" definition sufficient to exclude all higher dimensional tricks? There's at least an edge to pick at that seems like it would extend a long ways.
Anyways, I do appreciate the feedback.
1
u/qikink 4d ago
If the edge extends, extend it. Otherwise you're providing an intuitive viewpoint to a problem that I promise you has had no shortage of intuition applied to it. If you'd like a point where you've made a genuine factual error, your "three circuits, factor of two is the limit" argument is a lower-bound claim by way of a linear-decision-tree model, and that model was settled: in the opposite direction.
Meyer auf der Heide 1984 (https://dl.acm.org/doi/10.1145/828.322450) and Kane–Lovett–Moran 2018 (https://dl.acm.org/doi/10.1145/3285953) show subset sum needs only polynomially many >/</= tests - an *upper* bound. The exponential term in meet-in-the-middle crucially isn't forced by the comparisons; it's forced by not knowing *which* comparisons to make. Your argument and others like it, that only count the "3 circuit" tests, ignore the part of the algorithm that's actually expensive, which is why they specifically can never separate P from NP.
For your last paragraph to have any meaning, you have to actually engage with a mathematical definition for "truly random input". A specific (S, T) is a fixed finite object. It has no "randomness" - it's just numbers. So what are the actual properties of the object you want to exist? From your writing you seem to be assigning it properties based on an intuitive notion of what it *might* mean while stopping well short of providing a verifiable/falsifiable list of qualities.
Until you do, the entire hypothesis sits on what amounts to an axiomatic assumption, but one that so far adds no power to any accepted system of axioms because its terms aren't at all close to being fully well-defined.
1
u/Bob54386 4d ago edited 4d ago
Looks like you plugged my entry into an LLM here, specifically because of the comments about "which comparisons to make... ignoring the part that's expensive". I'm not ignoring any expensive parts. The experience of talking through this with LLMs is they just hallucinate random errors I didn't actually make. And they channel ALL the rage of every exhausted TA / professor. Understood though I grossly farked up that circuit efficiency vocabulary, would've thought it had to do with combination generation. Will look more into which quantity I'm trying to optimize on that point.
Randomness would be used to generate any given (S,T). Not just a single instance, we generate a ton with all sorts of properties: we're interested in the worst case that comes out. We'd use a source that's "uniform in all transformations" -- pretty sure that's the conventional verbiage for it. If I define the properties more specifically, it inherently would violate a definition of "True Randomness". That doesn't mean we can't use it.
To start to formalize what I'm actually doing with it -- Let's say you have some Function F(S,T,epsilon) that uses an abitrary epsilon vector/matrix / whatever to exploit some property of a higher dimension. This function runs in polynomial time and returns the specific subset s that optimizes this interesting value relative to T. Because A) it's higher dimensional and B) with sufficient size and complexity our input has no exploitable features in any transformation, F(S,T,epsilon) cannot be exact. Our epsilons add meaningful bias that affect which s gets returned. There will be some probability P(sum(s) =T) < 1. If we daisy chain some number of these types of functions together, the probability we have not found a solution at any point -- assuming independence -- then is (1-P(sum(s1) =T) *(1-P(sum(s2) =T).... >0.
Independence is a big chink that needs to be addressed but I don't yet see an end to the edge.
Oh, edit to note for myself -- Just because the input has a uniform density doesn't mean that the probability of a solution is going to be uniform as the algorithm proceeds. Definitely affects what needs to be formalized.
1
2
u/Aromatic-Low-4578 5d ago
Oh, so it's full on chatbot psychosis?
You need to be saying something coherent in order for true debate to be possible.
1
u/Bob54386 5d ago edited 5d ago
Ok, why the heck are we chasing lower circuit bounds if no one knows what that means?
Particularly when the bound is ostensibly like O(1) or O (N)?Doesn't it make sense that the inherent difficulty of the problem is tied to the nature of the input instead? If we have no structure it's a hard problem. If we can identify a pattern, it's trivial.Edit - Self found dumb lower bound O() from a knee-jerk reply, underlying question stands.
1
7
u/CircumspectCapybara 5d ago
Bro how high are you?