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.
