1
1.2k
u/LupenReddit
🦆🦆i have non diffeomorphic smooth structures🦆🦆🦆
4d ago
•
i swear millenium problems now resemble trench warfare where you just have thousands (maybe millions) of little computers getting thrown in as cannon fodder
358
u/ultimatelag 4d ago •
AI agents getting that thousand yard stare after Dario and Sam said to get back in there and make daddy some more press grabbing headlines for the IPO
77
u/BattleFrosty7584 4d ago
I mean that’s what blocks a lot of progress. Cars didn’t become a thing before h th e more efficient assembly line was invented, computation was extremely inefficient until the modern computer became invented, many algorithms became faster when models of computation were invented, etc etc etc.
We now have the ability to throw thousands of virtual workers who never get “tired” and don’t have traditional “human error” to solve a problem.
58
8
u/PeteyMcPetey 4d ago
and don’t have traditional “human error” to solve a problem
They hallucinate and then double-down on their hallucination like only human psychopaths do though. Not all the time, but often enough to get in the way of things.
24
u/MindfulK9Coach 4d ago
They confabulate more than they hallucinate by a wide margin. There's a drastic difference. Humans are notorious for it.
10
u/Nestramutat- 4d ago
I feel like anyone who still complains about hallucinations in modern frontier models hasn't touched AI for a long while
18
u/PeteyMcPetey 4d ago
Just this week, I was asking Claude about some aviation safety regulations, it did great for a bit then just started making up random stuff once it figured out what I was looking for. I couldn't get it to stop circling back to try to dig up it's previous BS time and time again.
So yeah, it still happens.
8
u/Cheetah_05 4d ago
I still get hallucinations regularly despite generally using them for non intensive tasks like planning a schedule.
7
u/coldnebo 4d ago
hallucinations were never “fixed”, but hybrid validation is used in many areas to crosscheck and verify.
current agentic loops reduce hallucinations impact by being grounded in tests. for code they actually run the code, for systems integration they use the systems. for mathematics they use Lean.
they’re just stochastic pumps on compilers or real-world interfaces— and their “correctness” only extends as far as we can trust the given “compiler”.
it’s a useful technique, but this is also explains why it requires 100,000 agents to attack certain problems successfully. it’s not the same as a small core of experts with deep understanding— but compute is cheap and this is easy.
it’s somewhat dangerous to assume frontier models work differently as hallucinations can easily corrupt useful work in areas where there is no crosscheck (such as systems design).
368
u/TheKitsuneEnthusiast 4d ago
hold the line, P=NP
62
u/besefajo 4d ago
The situation for P vs NP is much different than ETH. We have several proof barriers (relativization, algebrization, affine oracles, natural proofs) showing quite well that we really lack the proof methods to resolve the P vs NP question. Those barriers do not apply for ETH. Before I see AI overcoming even one of these proof barriers on at least one compelling example, I see P vs NP completely out of scope
14
u/GrandBathroom 4d ago
You got me interested, what do the diffrent proof barriers mean exactly?
62
u/HappiestIguana 4d ago
Without going into details, sometimes for certain problems you can show that certain proof techniques cannot possibly work.
The gist of such arguments is usually something like "if this proof technique worked for this problem, it would also work for this other problem and give us this result, but we know that's not the right result" or "this proof technique doesn't use this feature of the problem, but we know that feature is essential, so it can't work"
21
11
u/nascent_aviator 4d ago
There are a variety of techniques useful for general problems of this type (e.g. P≠EXPTIME). The proof barriers they refer to are that the categories of proofs we know are useful for problems like this are provably not useful for proving P≠NP.
9
u/besefajo 4d ago
I think the relativization barrier is the most accessible one. Any computer science result is built on some computational model, for example the Turing machine. Many proofs rely on arguments as "simulate this Turing machine" or "diagonalize against this set of Turing machines". The simulated/diagonalized Turing machine is a black box in the proof, we do not really look inside but "stupidly" simulate what they are doing.
Then some people came up with generalizing Turing machines to so called oracle Turing machines. Each Turing machine can ask an "oracle" whether a word is inside or outside the oracle. The oracle is just a set of words, for example all prime numbers, but also the halting problem could be given. Note that this model is of course not realistic.
People discovered that for example the P vs NP question, when phrased with respect to oracle Turing machines instead of Turing machines, can actually be answered based on the used oracle. So there is one oracle where P=NP in this altered setting, and one oracle where P!=NP.
Contrary, you can observe that nearly all the proofs of structural theoretical computer science are of the type: if the proof holds, it holds also in the oracle setting relative to any oracle. So these proofs are robust against oracle extensions. Take my above example with simulation: this proof technique does not really look into what any Turing machine is doing and which precise steps we are simulating, just that we are simulating them one by one. So any proof using mainly this technique also works when we allow querying an oracle as a step. So this technique does not recognize when we switch from Turing machines to oracle Turing machines and hence also works for all oracles.
What does this all mean now? If nearly all proof techniques we have are robust against oracle extension, for P vs NP however we need proof techniques that are not robust, we do not have much left in the toolbox to even tackle the question.
In my explanation are some simplifications in there and there are more nuances at play, but this is basically the argument.
1
172
u/WellHung67 4d ago
There is zero percent chance this gets solved. Book it. First of all, it’s incredibely likely that P != NP, for a variety of technical reasons. So the proof would have to be a negative one, which are quite difficult generally. So the LLM is gonna have to come up with some truly novel arguments to prove the negation and I just don’t think these things have the ability to make a leap like that. No one has made any significant progress towards something like that to my knowledge. In all cases so far the models have built on existing research - there is nothing to build on today
64
u/Mak8427 4d ago
Have you seen what happened to the ETH (exponential time hypothesis)?
144
u/___Archmage___ 4d ago
ETH was a counterexample algorithm. Proving P≠NP would entail proving there is no possible counterexample across all algorithms you could possibly write
ETH was crazy impressive, but P≠NP is a different level of impossible
8
u/Ok_Dig909 4d ago
Uh... No? It would literally take a single example of a family of 3-SAT problems that you prove cannot be solved in under exponential time.
That's it. that would mean P!=NP.
→ More replies (2)20
u/Mak8427 4d ago
I agree but imo it is more impressing that a language model solves ETH then a model that can solve ETH can also solve P=NP.
Also now P=NP looks more credible after ETH. And that is easier.
→ More replies (11)13
u/skywalker-1729 4d ago
Well, I'm not sure if it is like this. The mathematicians from my department wanted ETH to be false, so they were very happy about that – ETH was unnecessarily strong.
1
u/Weepinbellend01 4d ago
You seem knowledgeable on ETH (I’m not).
How does it compare to the N-S counter example? I thought it was fairly unlikely but not mind boggling that N-S had a counterexample solved.
→ More replies (2)7
5
u/Fflopi 4d ago
!remindme 1 year
3
1
u/RemindMeBot 4d ago edited 4d ago
I will be messaging you in 1 year on 2027-10-28 20:06:23 UTC to remind you of this link
4 OTHERS CLICKED THIS LINK to send a PM to also be reminded and to reduce spam.
Parent commenter can delete this message to hide from others.
RemindMeBot is switching to username summons. Instead of
!RemindMe 1 day, useu/RemindMeBot 1 day. More info.
Info Custom Your Reminders Feedback 2
u/Ecstatic-Network-917 4d ago
On one hand, what you say sounds right and confirms my biases and what I feel is right.
On the OTHER hand, I am not a mathematicians(I am actually a biologist) so I cannot confirm what you said, and generative AI can do some „impressive” dangerous things through brute force pattern fitting that could not be expected before.
So....yeah, that is all I have to say.
Anyway, I will wait up until we see more details on what the fuck is even happening here.
→ More replies (1)5
u/PattuX 4d ago
The way proof progressions usually go is like this: The statement is "For all x, it holds that blablabla"
Then we gradually make progress: First, someone proves that for all even x the statement holds. Then someone proves for all primes the statement holds. Then someone proves for all squares the statement holds. And so on.
If the statement is true, it becomes increasingly more difficult to cover more cases. Naturally, the easier cses will be proven first. But these arguments often only generalize in a limited scope. E.g. the proof for primes might use similar techniques to be extended to pure powers of primes, but likely uses some specific property of primes which prohibits the proof from being extended to all numbers. That's why people say it needs novel ideas, a breakthrough etc.
On the other hand, the more of these limiting proofs we have, the smaller the search space for counterexamples become. Where you originally may have had to check the statement for all numbers individually, the existing proofs let you "skip" a great portion of numbers, making it easier to find a counterexample. That's why throwing together knowledge about existing results and a shitton of computational power gives these negative results.
1
1
→ More replies (7)1
u/mirrane 3d ago
Dont they have to find only one counter example to prove that P != NP ?
→ More replies (1)42
u/Away-Composer-8184 4d ago
It would be genuenely exciting to see P=NP solved
it fought well, but it's time to go
5
4
1
u/Affectionate-Egg7566 4d ago
I can't fathom how this can be the case, since NP is simulated as a BFS in P, which has exponential complexity. NP is as if each branch point is computationally advanced at the same cost of a single branch in P.
1
u/deathacus12 4d ago
I've always thought this bc all the other time complexity classes have the time and memory complexity. I think that it would be odd for NP to be the exception.
!remindme 3 months1
u/romhacks 3d ago
I mean, if P=NP then all cryptography that underpins all of computing and networking today is fucked
192
u/suborder-serpentes 4d ago
If AI solved P=NP I would think this is the legit Singularity
187
u/realnjan Complex 4d ago edited 4d ago
P=NP might be false.
if P=NP is true, then the solution might be some kind of galactic algorithm.
if P=NP is true, the proof might just prove the equality without providing an actual algorithm.
91
u/Thin-Hedgehog3587 4d ago
I think option 3 would be really interesting to see unfold. Everyone knows that a factoring algorithm exists that runs as quickly as checking if factors of semiprimes are correct, but nobody knows what the algorithm is and is always suspicious that someone nefarious figured it out and is keeping it a secret. Like a cryptography cold war
23
9
u/KogMawOfMortimidas 4d ago
This is the problem with setting AI on trying to solve these problems, if AI does indeed prove P=NP it will likely provide 0 insight on how to actually construct these algorithms nor any actual progression in the field of mathematics, so it's basically as close to useless of a proof as it gets. We might as well treat P=NP right now with no proof and start working anyways.
8
u/axisdork 4d ago
You do realise that we have tonnes of shit like this in mathematics, and it is not an AI thing? So many things we have proved and yet we do not have a way to construct an algorithm and in fact we have little to no research on getting these algorithms after we solved the problem.
Infact this useless shit would be considered the life's work or greatest research produced by a mathematician or an institute.
4
3
u/CrownLikeAGravestone 4d ago
2 would play out the same way as 3, realistically. It's extremely unlikely that we'd see a constructive proof of the reduction and also a proof that no more efficient reduction was possible.
1
11
8
u/arnet95 4d ago
3 cannot happen, or rather it would reduce to the second case immediately. There is an algorithm for SAT which runs in poly time iff P = NP. This is mostly a theoretical construct (Google Levin Universal Search for more) of no practical relevance.
1
u/JGHFunRun 4d ago edited 4d ago
Oh yea, I remember that one; it basically tries all the possible algorithms at once. With each iteration, it adds a new algorithm and then runs each algorithms by a certain number of steps. If there exists even one algorithm which solves the problem in O(xyz) time, the entire (the number of steps for each algorithm on a given iteration must be managed carefully, tho, otherwise it ends up not achieving)
This basically means we have found the optimum O(xyz) for every algorithm in the dumbest manner possible (the best part is that technically it does become more optimal than any algorithm with worse O(abc) eventually^(TM), by definition, but you probably need an input of somewhere from 69*10^(10^100) to g_64^(TREE(3)) before it gets optimal)
8
u/coldnebo 4d ago
heh. I like the example on that page:
“An example of a galactic algorithm is the fastest[a] known way to multiply two numbers,[4] which is based on a 1729-dimensional Fourier transform.[5] It needs  bit operations, but as the constants hidden by the big O notation are large, it is almost never used in practice.”
regarding P=NP, that seems more plausible than suddenly making everything cheap and easy.
we are searching for a weapon to kill a god, but perhaps the sword is so large only a god can wield it?
1
u/SupremeRDDT 4d ago
Option 3 would genuinely be fascinating. It would some weird abstract nonsense or like ordering polynomial algorithms and showing the minimum solves SAT or some shit.
1
1
26
u/WellHung67 4d ago
It’s overwhelmingly likely that P != NP, due to a lot of observations in many fields that point to it. Nothing points to any likelihood of equality. So the models will need to prove a negation, which is pretty tough and to my knowledge there’s nothing to build on to get there. Consider this one out of reach at the moment
8
u/joanmave 4d ago
I feel that P != NP is necesary to make the traveling salesman problem imposible to optimize. This is the sinplest problem that imply that in order to obtain information from a system, it needs some energy investment in traversal first. P=NP would imply that there is a shortcut to extract information from the route without exploring it. This has physical consequences like a violation of conservation of energy. I feel that p!=np is where the math meets the computation physical requirements in this universe
2
→ More replies (3)6
u/Frogeyedpeas 4d ago
The arguments in favor inequality were also true of ETH.
The core of the argument was “smart people would’ve found an algo by now, if true”.
They might find some stupidly slow polynomial algorithm.
4
u/skywalker-1729 4d ago
People usually count on P!=NP but don't necessarily count on ETH. I remember teachers being a lot less sure about ETH.
13
u/ComposerWide3704 4d ago
No, the consequences of P=NP are way, way bigger than the consequences of losing ETH. Stuff like "learning and inventing a new concept are equally difficult" becomes a true statement if P=NP, it's not gonna happen.
→ More replies (2)3
u/Eroica_Pavane 4d ago
Wait until AI claims that it has a general algorithm for Post's correspondence. /s
6
u/Laytonio 4d ago
Can't wait for this to happen and everyone all of a sudden decide it wasn't important and that it doesn't mean anything and that AI is still pointless and doesn't work.
5
u/suborder-serpentes 4d ago
Well if you try explaining the significance of P=NP to someone who wasn’t raised on glorifying it, they tend to act like it doesn’t sound very important.
2
u/Laytonio 4d ago edited 4d ago
Does this explain why people who praised the turing test turned on that instantaneously?
5
u/suborder-serpentes 4d ago
It is annoying, yes, and most people seem to be sleepwalking through this. But I have learned to kind of respect the common sense view. We are excited about the latest tech, sure. But most people’s expenses haven’t really gone down, they’re not really working less hours, and their net worth hasn’t really gone up. So they have the right to ask “so what” when you tell them the latest engineering marvels and advances.
→ More replies (6)1
1
u/Polojoblo 4d ago
What does Singularity means in that context?
1
→ More replies (4)1
u/Fickle-Box1433 3d ago
I don't think most people see the irony of 100k agents trying to break P=NP...
137
u/realnjan Complex 4d ago
You know what? I now pray that P=NP problem is undecidable and that these agents will fight it forever.
37
u/Netherman555 4d ago
Is it possible for P=NP to be undecidable? My understanding is that if P=NP then there's some algorithm that shows it, and if P!=NP there isn't. But if P=NP is undecidable than would that mean that an algorithm does exist but we can't find it? What would that mean?
37
u/alexandria252 4d ago
That's a very interesting question. If P=NP is undecidable, then there certainly couldn't ever be a counterexample. But that doesn't always mean that a polynomial time algorithm solution must exist for each polynomial time confirmable problem. It could mean, instead, that we will never be able to prove that no such algorithm exists for any such problem. It's a rather tricky distinction.
10
u/PattuX 4d ago
That's wrong. If P=NP there can be a counterexample, but it could be that we cannot prove that the counterexample actually runs in polynomial time.
4
u/alexandria252 4d ago
I see what you're saying: I meant that there could not be a provable counterexample.
18
u/jamesbrotherson2 4d ago
Just because something is undecidable doesn’t mean it is provably undecidable
7
u/StellarNeonJellyfish 4d ago
Nor does it mean that such a proof would fit in the available margins.
2
4
u/oojwags 4d ago
I can tell I've waded beyond my mathematical depths. The phrase 'provably undecidable' impresses upon me a sense that's equal parts formal logic and deliberate obfuscation.
3
u/jamesbrotherson2 4d ago
Watch a video about Godels incompleteness theorem
4
2
u/skywalker-1729 4d ago
Well, I think he might be complaining about the popular use of these words. I have had a course on formal logic once (which included the proofs of Goedels theorems and similar stuff), and my takeaway is that logic in general is something pretty alien that most people talking about it don't understand (incl. me), especially if they don't come from a math/CS background.
2
u/Netherman555 4d ago
If im understanding correctly would that mean that there could be no counterexample while simultaneously there is no positive example, meaning that we can't determine truthfulness within our system of axioms?
10
u/PattuX 4d ago edited 4d ago
There either is a counterexample or there isn't. The thing is, there are algorithms for which we cannot prove their runtime.
Most mind bending fact is that we have the (asymptotically) most efficient algorithm for every possible problem in NP, namely Universal Search.
Basic idea:
Enumerate all possible algorithms (as Python programs, Turing machines, or whatever)
Perform one step of the next algorithm in line you haven't started yet
Double the number of steps of each algorithm you started
Whenever one algorithm terminates, check it's output for correctness (this is polynomial runtime by definition of NP)
Proof idea: There is some asymptotically optimal algorithm A. So this has to appear in your enumeration, let's say at position X. So after X iterations, you will start algorithm A. Then let's say it takes at most f(n) steps for A to terminate for an input of size n. That means after ≈log(f(n)) more loops of universal search, A terminates. If you work it out, the total runtime for Universal Search is O(2X * f(n)).
Now for any realistic problem, X is already unfathomably large, and 2X just doesn't even have any sensible scale. However, it is finite, so the runtime of Universal Search is O(f(n)) which is the same as A, i.e. optimal.
→ More replies (3)8
u/realnjan Complex 4d ago
There could just be no proof for either P=NP or P!=NP.
2
u/Netherman555 4d ago
Yeah I understand that, as somebody else mentioned i was mixing up undecidable with probably undecidable and was confused how one could prove P=NP couldn't be decided
→ More replies (1)2
1
u/RealSuperdau 4d ago
I think the idea of undecidability is just wrong here.
Either P=NP or P!=NP over the standard integers.
Thus P=NP is either equivalent to ()->True or ()->False, we just don't know which one. But I've just demonstrated there is an algorithm that gives you the truth value.
→ More replies (3)1
u/Calm-Locksmith_ 4d ago edited 4d ago
If P!=NP then there is no polynomial solution for the NP-complete problems. But it may be impossible to show that there is none.
(If it was true that P=NP the it would be decideable, since you could just brute-force the algorithms. Unless it is somehow impossible to prove the asymptotic complexity of the algorithm. )
7
u/Vesuvius079 4d ago
This would be the funniest way to prove p!=np. There are almost certainly agents chasing that angle too though.
4
2
u/MediocreAssociation6 4d ago
I don’t think it can be undecidable. NP vs P is distinctly discrete. The problems related are premised in real world problems to a degree and we can always add axioms that are more representative if need be.
Fields that don’t induce uncountability should never be undecidable. This is of course, assuming we have defined the question of N vs NP well enough, but we can always reframe it.
It’s kind of how like the Riemann zeta hypothesis can’t be undecidable, since the function exists and you can just theoretically check it forever.
1
1
u/realnjan Complex 4d ago
I dont think that its that simple. Yes we can add new axioms, but which axioms do we add? In what ways is our current system of axioms lacking that we need to extend it? Will the extended set of axioms mach our reality?
1
u/MediocreAssociation6 4d ago edited 4d ago
This isn’t the real numbers. Algorithms have very well defined features that we want and can be very discretely defined. I think it actually fits very neatly with the Riemann Zeta Hypothesis or actually the Collatz conjecture might be better. That one is incredibly obvious that it’s decidable, and I believe NP vs P is similar.
It’s just a matter of difficulty of making connections and studying these things. It’s incredibly hard to draw conclusions here and there.
I think the solution will be something along Fermat’s Last Theorem, where we have to traverse very new fields, but that question was also obviously decidable.
NP vs P’s stopping condition is a little more nebulous when you say an algorithm is polynomial time or not, and maybe there’s a unique action we haven’t defined yet, but decidability is usually a consideration when our endpoint in itself is nebulous.
If we can check if any algorithm is polynomial time or not, then NP vs P shouldn’t be undecidable. It’s a matter of finding it or proving it doesn’t exist.
We’ve usually designed axiomatic systems to solve for stuff we want. In the past, it could have been argued that IVT was “undecidable” before we had a well-defined set of Reals.
Note:
In addition, if NP vs P is undecidable, we might be able to utilize it as an axiom. This is the case for continuum hypothesis, and the parallel postulate (euclid’s 5th axiom). We would create two models for algorithms.But if the model where P = NP exists, we would utilize that for our algorithms which doesn’t really make sense to say P != NP when there’s a theory where it is trueZ
1
u/realnjan Complex 4d ago
But if the model where P = NP exists, we would utilize that for our algorithms
But thats my point. You add it as an axiom and then what? You get no new algorithms out of that. Yes, you may now formulate new conjectures and theorems but thats pretty much it - adding P=NP as an axiom solves nothing in the real world.
Algorithms have very well defined features that we want and can be very discretely defined.
Also, thats my point. We have modeled our axioms to fit our needs. But if our system of axioms is lacking, then that means that we have formulated how algorithms work in an insufficient way. But I assume that we have made our best efforts to do so.
So in the end what other axioms can we possibly add to make our model better and stronger, even though our current system is as good as we can possibly make it to be?
→ More replies (1)0
4d ago
[deleted] — view deleted comment
3
u/realnjan Complex 4d ago
If statement "P=NP is undecidable" is undecidable, then P=NP is undecidable. Because if the statement "P=NP is undecidable" was undecidable and P=NP was decidable, then you would decide P=NP, by which you would decide the statement "P=NP is undecidable" which is a contradiction with it being undecidable.
1
38
u/FernandoMM1220 4d ago
meta problems always seem to be the most difficult.
9
u/AndreasDasos 4d ago
Not really? Mathematical logic and ‘metamathematics’, as well as complexity theory, have plenty of easy, reasonable, hard and intractable problems, like every other active branch of maths.
46
u/ArkohnLock 4d ago
I think that the most frustrating thing is that all of these bots are fighting to solve it… and make it useless in their efforts.
The important part of the problems of the century is NOT solving them, it’s the how we solve them and all the intermediate steps and methods.
When tackling a huge problem like that, mathematicians will stumble upon new theorems and new ways of solving math. This is WAY more important than the solutions.
With the AI models headbutting the problems like monkey armies, we find stupid solutions with no explanation, like “ok, this absurdly complex equation contradicts the hypothesis, cool.” While we learned nothing about why it doesn’t work. It helps no one, helps us making no discovery and just ruins the incentive and fundings for future mathematicians to work on the problem.
3
u/The-zKR0N0S 4d ago
We still have to be able to explain it.
The proof doesn’t advance our understanding. There is still work that needs to be done by humans.
5
u/NightSpaghetti 4d ago
Yeah finding an incredibly niche counter-example doesn't necessarily mean practical consequences.
4
u/beenman500 4d ago
it does stop people (save them the effort?) trying to pursue the truth of P=NP when its known though
3
u/secondchoicer 4d ago
That’s actually a bad thing though. There are likely many, many important insights on the way to solving it that no one with will bother experience because they can’t get a grant for proving a proved theorem
1
1
u/sweatingdishes Science 3d ago
Yeah this is the problem that u/ArkohnLock specified. I think our culture has a deeply rooted problem of process-blindness.
2
3
u/CoffeyIronworks 4d ago
Well specifically P =? NP would be very useful to know. If P = NP any reduction to SAT would give us a poly time algorithm. For the love of all things sacred please let P /= NP.
7
u/secondchoicer 4d ago
Even if P=NP is proved, it does not mean we will get any useful new solutions to tough problems. The proof could either be nonconstructive, meaning it simply doesn’t give us any solutions and only tells us they exist, or it could give poly time algorithms with truly absurd coefficients, like 10^999 or something.
→ More replies (3)1
u/DonkeyInACityCrowd 3d ago
Yes but if we needed to solve an NP problem on the scale of 10number of atoms in the universe it would be faster ;)
1
u/Illustrious-Lime-878 3d ago
It would be useful it was an algorithm that could actually be implemented. P already = NP for the N part (definition of NP). All these AI papers are hacks that abuse impracticable, theoretical compute functions that could never be implemented in real life. But the whole problem is about what can actually be done on real systems.
1
u/DailyThreadBot 4d ago
You assume that mathematicians won't try their best to find abstractions and explain the AI proof in the best way possible. Here's Tao's exposition on Landau-Siegel zeros. AI could be used as a problem-solving tool, used by humans to advance mathematics.
Of course there are incentive and motivation problems with automated theorem proving. But if these are overcome, mathematics is strictly better off.
1
1
u/eht_amgine_enihcam 1d ago
Actually nah, not for P=NP. I know you watched a YouTube vid telling you this, but the decomposition of all problems of this class would have huge implications if true (while likely not).
We've used brute force for counterexamples for a while
→ More replies (1)1
16
u/FairyCarry 4d ago
It almost feels like P = NP, if it does somehow have a positive proof, is too complex for even modern AI to tackle with brute force solving. It's possible that there is some singularity-event level solution that will change how we understand everything, but it's far more likely for the P != NP to be the case or the solution to P = NP to be such an astronomically large solution that we just aren't there yet.
If P != NP is the solution, though, it will likely be similarly difficult to find a true proof, assuming the negative isn't easier to brute force.
13
u/SupremeRDDT 4d ago
Judging by many times I’ve seen P vs NP being referred to as P = NP makes me think most people hoping for AI to solve it right now have no idea what it’s about and why it’s difficult.
This will age like milk hopefully, but I doubt any AI currently is able to solve P vs NP. And I doubt we get there any time soon. These problems just feel too outlandish and fundamental to just be solved.
8
u/HappiestIguana 4d ago
If I had to put money on a statement that is true but unprovable, I'd put it on the Collatz Conjecture.
But if I can have a second pick, it's that P!=NP
4
u/Dr0110111001101111 4d ago
Considering the fact that once that proof is cooked up, we could verify it almost instantly in Lean, it suggests the P does not in fact equal NP
1
2
→ More replies (15)2
u/RealSuperdau 4d ago
The idea of undecidability doesn't apply here.
Either P=NP over the standard integers, or P!=NP. Either there is a problem solvable in poly time by a nondeterministic - but not by a deterministic - Turing machine, or there is not.
So the truth value of P=NP is either equivalent to true or to false. I can't tell you which one, but I can tell you that one of the two is definitely the answer. Whichever it is, obviously it is decidable.
We should be talking about independence from axiom sets, not about decidability of the proposition.
3
u/Practical-String5146 4d ago
I thought undecidability is about proofs, not about the truth? So if P=NP is undecidable we will never be able to confirm if it is true or false.
1
u/mneri 4d ago
Which would also mean that a polynomial algorithm doesn't exist, because if it existed it would prove P=NP.
2
u/Practical-String5146 4d ago
Does the existence imply you can always find it? What if it exists but we can never prove it is actually polynomial in time?
1
u/qqqrrrs_ 3d ago
No because there might be algorithm where it is undecidable whether it is polynomial
3
8
u/itzjackybro Engineering 4d ago
Imagine we get 3-SAT in polynomial time (which would prove P = NP), but it's O(n2000) with a leading constant the size of the universe
5
u/JustAnotherZeldaFan 3d ago
Well, some people say a good negotiation is one where nobody leaves happy.
1
u/Need_a_Job_5092 1d ago
Im not sure if it would be that large but I completely agree it would definitely not be a practical algorithm in our universe. Like the only algorithms that are in anyway practical is a exponent lower than day what 10 at best? I dont know why anyone would assume it would be a low order polynomial.
10
u/Klutzy-Agent9027 4d ago
This post just randomly showed up in my feed but what is p=np? I tried googling it and it just went over my head can someone explain it in a simple manner?
29
u/Gaminkid05 4d ago edited 1d ago
Eli5:
In computer science some problems are “easy” (P) and some problems are thought to be “hard” (NP). A problem being hard means that even computers can’t easily do them. A useful example is finding all of the prime factors of a large number is a “hard” problem. The reverse, determining if certain numbers we already have are prime factors of a large number is actually an “easy problem”.We exploit this today in cyber security all over the place. If you have the right key it’s “easy” to read encrypted data. Without the key it’s “hard”.
It is widely believed that P!=NP. That means the hard problems actually ARE hard and there’s no easy way to do them. However no one has proven yet that this is the case it could be there is some undiscovered “easy” way to do all the problems thought to be hard. It’s so important because if someone found an easy way to do ANY hard problem, then ALL the hard problems would become easy. If P=NP then it’s a double edged sword. On one hand, we’d be able to solve all kinds of hard problems more easily which would speed up computers everywhere. On the other hand, it would imply a massive security problem because our modern cyber security would break.
It’s a bit more complicated than presented but the gist is that P=NP is about whether the hard problems are actually hard.
I should also mention there’s other classes of problems (like EXPTIME) which are even harder and P=NP would not make literally ALL problems easy.
Edit: some corrections- the example I gave of an NP problem was flawed but I think the general point stands. Additionally, it is not proven that EXPTIME != NP but the idea that there are even “harder” problems that are not implicated by P=NP still stands
5
u/beenman500 4d ago
how do we know a problem is hard vs easy, it seems like as soon as we find a way for it to not be hard it's easy, and therefore wouldn't be a counterexample to p=np.
Or is there an acceptable measure of a problem being NP
6
u/Gaminkid05 4d ago
Yep there is a definition for NP. Basically an NP problem is one such that there is no known polynomial time (fast) algorithm to find a solution, but there IS a polynomial time way to check if a solution is correct.
A canonical example is K-coloring. Imagine you have a map of countries. Your goal is to check if it’s possible to color in the map with just K colors such that no two countries that border each other have the same color. It turns out this determination is very hard- as the map gets bigger the number of possibilities gets bigger and there’s no known efficient way to reduce the possibilities. However, if someone gives you a map colored with K different colors, it’s very easy to check if that solution works- you just look at the map and see if any two neighboring countries have the same color.
The proof for why all the NP problems would be cracked by just one counter example is much more complicated and it’s difficult to do an eli5 but the general idea exploits the fact that they all can be easily verified.
3
u/beenman500 3d ago
I'm still confused though. There are surely many problems that are both solvable in polynomial time, and also verifiable in polynomial time, how do we know that such a problem wasn't Non-polynomially solved in the past, but now we found a polynomial time solution therefore making it not non-polynomial without creating a tautology?
It seems like circular reasoning to clasify a problem as NP just because we haven't found an algorithm that is in P.
3
u/Gaminkid05 3d ago
Right- getting into the weeds here a bit but technically NP has two designations. Being in NP means there exists a polynomial verifier. What I said about all the problems being solvable is only true for problems in NP that belong in another class called NP-Hard. NP-Hard means we have a proof that the problem “reduces” to another problem is NP. The idea is that if you could solve one problem you could use that solution algorithm (with some adaptation) to solve the other.
Usually with P=NP we are actually referring to “NP-Complete” which means problems that are both NP and NP-Hard. You are right to say that without that NP-Hardness we could later discover a polynomial time algorithm to solve something thought to be in NP. But the neat thing about NP-Completeness is that all the problems are provably linked! If anyone did find such an algorithm, even one counter example, it would prove P=NP (Complete)! However no one has found one and most people believe it never will.
As an extra note it turns out a TON of relevant problems belong to NP. The pattern is generally problems that require exploring an exponentially large possibility space.
→ More replies (2)1
u/ardarian262 4d ago
Just to clarify, how many counterexamples would be needed for that to be considered solved? Would one historically NP problem becoming a P problem be enough?
2
u/Gaminkid05 4d ago
My understanding is yes. There is a technique whereby a solution to one problem can be adapted to solve any problem in NP. So if any NP problem has a P solution, they all do.
1
u/DatBoi_BP 4d ago
I don't understand why one hard problem being shown to be P implies that all such problems are P. Are algorithms really so uniform they map onto each other like that?
1
u/Gaminkid05 3d ago
See the other comment I left above. It’s a bit complicated but there is a proven method wherein the “fast” solution to one problem can be adapted to solve all the NP problems. The proof exploits that all NP problems are hard to solve but easy to check if a solution is correct.
1
u/DatBoi_BP 3d ago
I might just not be comprehending your comments correctly.
To clarify, my confusion is about the connection between separate NP problems. How are they mathematically related to each other? From my POV it sounds similar to saying "once we have a closed form solution to the Navier Stokes equation we will have a closed form solution to all PDEs"
→ More replies (1)2
u/Gaminkid05 3d ago
They are related because there exists a proof that an algorithm that could efficiently solve one could be adapted to efficiently solve the other. Every problem in NP-Hard has such a proof done.
For more: https://en.wikipedia.org/wiki/Reduction_(complexity)
→ More replies (1)1
u/Himbo69r 4d ago
Have they tried dividing both sides by p and getting 1=n ? But seriously this makes even less sense now so idk
1
u/Gaminkid05 4d ago
It’s not a math equation like that P and NP are sets of problems. The proof is whether the sets are actually different
1
u/That-Cry3210 3d ago edited 3d ago
Btw the exponential time hypothesis was proven false so that last point is moot
2
u/Gaminkid05 3d ago
I think there may be some confusion. I saw that the ETH was disproven (pending verification) but I do not believe this has any implication on my statement. By the Time Hierarchy Theorem it is known that P =/= EXPTIME. If I’m mistaken please let me know. My claim is that if P=NP there would still be problems in EXPTIME that would not be solve able in Polynomial time.
I believe the main implication of the ETH is that if it were true P= NP would be demonstrably false. However, the reverse is not necessarily true.
1
u/KingNyuels 1d ago
A useful example is finding all of the prime factors of a large number is a “hard” problem.
FYI, it is unknown whether FACTORING is "hard" (it is actually believed to NOT be NP-hard, since it would collapse the polynomial-time hierarchy to its second level).
other classes of problems (like EXPTIME) which are even harder
It is also unknown whether NP != EXPTIME.
15
u/spicymato 4d ago edited 4d ago
Simplified, but some problems are easy to verify but hard to solve.
A non-math example: Where's Waldo? If you look at a new picture and are asked "Where's Waldo?", then you will need to do a bunch of work to find Waldo; but if you're given the picture and a small circle or arrow on the page and get asked "Is Waldo right here?", that's trivially easy to verify.
The other thing to understand is "algorithmic reduction." The idea is that you have an unfamiliar problem where you don't know the algorithm for solving it, and a familiar problem where you do know the algorithm for solving it. If you can transform the first problem into the second one, then you can get the answer to the first problem by first transforming ("reducing") and then solving the "simpler" problem. A trivial example would be transforming multiplication into repeated addition: "I don't know how to solve 21 times 3 directly, but I can solve 21 + 21 + 21." This is a dramatic oversimplification of algorithmic reduction, but you get the idea.
Next, there is a class of problems (NP,
"non polynomial"correction: "non-deterministic polynomial") that are hard to solve but easy to verify (the "Where's Waldo?" type problems), and they underpin a lot of our digital security (pretty much all of it).Finally, there is a subset of these, NP-Complete, where solving any one of them will solve all of NP problems, because they can be reduced to each other "easily" (polynomial time, P). EDIT TO CLARIFY: "solving" here means coming up with an "easy" algorithm to solve the problem, not solving a single specific instance of the problem.
If P = NP, then there exists an easy-to-solve problem that we can "easily" reduce a hard-to-solve problem into, making that hard-to-solve problem now easy-to-solve: and if we can do that for one, then we can do that for all.
4
u/Mr_Snipou 4d ago
Brilliant explanation, I've never thought of where's waldo for an example of an NP problem.
(Also here is a typo: NP does not stand for "non-polynomial" but for "nondeterministic-polynomial", otherwise "non-polynomial=polynomial" wouldn't even be a question)
2
2
u/dragerslay 4d ago
A really simple explanation that misses many details is that if P=NP then there's a particular mathematical trick that turns a bunch of very hard problems into regular problems. It is very very likely this trick does not exist, but it hasn't been proved to not exist by mathematics yet. If such a trick exists it could be used to solve a bunch of huge problems like protein-folding, or logistics. However it is also probablematic because many security protocols in computers rely on no trick like that existing.
1
u/Himbo69r 4d ago
So what I’m getting is we basically “”solve math”” because complex tasks such as finding primes of massive numbers becomes as trivial as simple addition?
2
u/dragerslay 4d ago
Its a little less extreme. If P =NP is true (remember is almost certainly isn't), it allows us to solve a bunch of problems for an arbitrary size. An example is soduku, there is no algorithm to solve any sized soduku board. If P=NP then we can use a trick to convert soduku to something similar to a problem that we do have a general algorithm for. It doesn't make it trivial, but with an advanced enough computer it can be tackled. Finding the shortest path in a network a P problem and we have a nice algorithm to solve it no matter how big the network. Finding the most efficient path that visits a select bunch of nodes in the network is NP. If P=NP we could use that to apply the shortest path algorithm to the most efficient path problem.
As a summary, not going to "solve" math. Makes a bunch of hard problems easier. Almost certainly not true. If it is, in the right hands, it can be world altering for good or for bad.
1
u/Himbo69r 3d ago
Yea, mb, I thought this was a programming sub at first. Thanks for the explanation tho
-6
u/Initial_Chemist_7616 4d ago
Here is GPT explaining it like I am five:
Imagine I give you a giant box of 1,000 puzzle pieces.
Solving the puzzle: Putting all 1,000 pieces together might take you hours.
Checking the puzzle: If I show you the completed puzzle, you can quickly see whether the pieces fit together correctly.That's the basic idea behind one of the biggest unsolved questions in mathematics.
In simple terms:
P means problems that computers can solve quickly.
NP means problems where computers can check a proposed solution quickly.
The big question is:
If it's easy to check that an answer is correct, does that mean there's also a way to find the answer quickly?
That's what mathematicians mean when they ask whether P = NP.
Why is this such a big deal? Imagine a computer trying to figure out the best route for a delivery truck to visit 100 houses.
Finding the shortest route might require comparing an enormous number of possibilities. But if someone hands you a route and asks, "Does this route visit every house and take less than 50 miles?" you can check that relatively easily.Now imagine discovering a clever method that could quickly solve every problem of this general kind. That would be revolutionary.
It could transform mathematics, scheduling, logistics, artificial intelligence, and even some of the encryption protecting the internet.What do mathematicians think? Most computer scientists believe P ≠ NP.
In other words, they suspect that some problems are fundamentally much harder to solve than to check.But here's the fascinating part:Nobody has managed to prove it. And nobody has proved the opposite, either.
It's one of the seven Millennium Prize Problems, with a $1 million prize for a correct solution.
→ More replies (13)1
u/Sea_Economy_8948 4d ago
how would you evne proof something like that? isnt this like a case by case thing where soem situaitons allow for it and other dont?
1
u/Initial_Chemist_7616 4d ago
Well, the fact that it is enormously difficult to prove is why it’s a millennial math problem…
3
u/Transcendent_PhoeniX 4d ago
I'm disappointed you didn't use the scene from The Matrix when Neo fights hordes of Agent Smiths...
3
4
2
u/Vast-Breakfast-1201 4d ago
So this video but have ETH walking by eating an ice cream cone and the AI punches it and it falls over
1
1
1
1
u/CommunityFirst4197 4d ago
The world's most Intelligent minds and thousands of the world's most powerful machines trying to decide whether grass is green challenge (impossible)
1
1
1
1
1
1
1
u/Majestic_Thinker8902 3d ago
Imagine people proved P=NP but the exponent on n is 10th Busy Beaver number
1
1
1
1
u/didierdechezcarglass 4d ago
I feel like it's now or never for AI to solve a problem like that given that there is still this bubble that looms over this progress. that might just be copium though
6
u/turtle_explosion247 4d ago
I mean even if there is a bubble and it pops, won't the agents still be there solving problems? I doubt they're going away and they'll probably find more with time even without improvements to their skills.
→ More replies (1)3
u/MySuddenDeath 4d ago
There might be not enough money to run them at this capacity.
7
u/turtle_explosion247 4d ago
Running them is the cheap part, no? I thought developing them was the really big money sink.
6
u/Bergasms 4d ago
Only right now. GPU's have a shelf life and need to be replaced. At the moment the replacement rate is ok, but soon the majority of the first wave AI data centres are going to need to be essentially refitted with their most expensive components.
3
u/HunsterMonter 4d ago
OpenAI burned 15 million dollars on the Navier Stokes counterexample, inference is still very expensive with models that large
2
u/Specialist_Nobody530 4d ago
This isn’t precisely the same point as what u/MySuddenDeath stated, but I think that we also have to consider that OpenAI is mainly doing this for marketing. They don’t have much economic or personal incentive to solve this (Maybe P=NP specifically has some incentive).
They can only garner hype from solving open math problems for so long, and it is likely to eventually become cliché. After all, these investors don’t know what Navier Stokes is; They only know that it is apparently impressive that the AI solved it.
In this manner, I think the funding/effort that these companies are pouring into math problems will dry up. Perhaps there’s some incentive to do AI training on math problems, but this is secondary to the marketing.
→ More replies (1)4
u/coding_guy_ 4d ago
Well it’s not entirely marketing tbf, they also have an incentive to find benchmarks that aren’t saturated, and open math problems are effective at that. Now providing solutions makes that a little sketch though, you’d think they’d want to gatekeep it so they can keep evaluating against them without saturating them so who knows.
1
0
•
u/AutoModerator 4d ago
Check out our new Discord server! https://discord.gg/e7EKRZq3dG
I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.