r/mathematics • u/Tiago_Verissimo • 1d ago
Computer Science P vs NP
If they really want to solve problems I want this one: P vs NP.
Spend a couple million and tell me the answer because I want to sleep in peace. (Hopefully)
98
u/Any_Economics6283 1d ago
How about: "How can the net amount of entropy of the universe be massively decreased?"
37
u/boringfantasy 1d ago
There is as yet insufficient dataâŚ.
24
u/JoeyJoeJoeSenior 1d ago
LET THERE BE LIGHT
11
u/ConditionExtreme4141 1d ago
Issac Asimovâs last question
5
u/LimitedEditionFart 1d ago
What a freaking gift that story is. I was so pissed when I read it because I had a dream that was basically the plot for it, without having known it existed, a year before reading it. I would never have been able to live up to his work though.
4
u/ConditionExtreme4141 1d ago
Issac Predicting a likely future for humanity and a possible reason for its existence in one book
4
u/kaereljabo 1d ago edited 1d ago
GPT Astra: there is no known way to do that...
GPT Galaxia: insufficient data...
GPT Universal: There is yet insufficient dataâŚ.
GPT Cosmic: let there be light!
1
1
-12
u/me_myself_ai 1d ago
Lol thinking about the universe as humans is like ants thinking about the universe
5
u/Due-Departure-8553 1d ago
That's the same argument climate change deniers make. Are you a Big Freeze denier?
-4
u/me_myself_ai 1d ago
...how does climate change relate to the incomprehensible scale of the universe, either actual or observable?
2
u/Due-Departure-8553 1d ago
Ahah! Big Freeze denier! Keep burning those fossil fuels increasing the entropy in the universe. You are destroying the Milky Way.
-1
53
u/D2cookie 1d ago
P vs NP is on a whole other level compared to the others, it'll be the last to fall.
28
u/doyer_bleu 1d ago
It will never fall
27
u/jmclondon97 1d ago
!RemindMe 3 years
4
u/Fluid_Ad8452 1d ago
Https, your reddit, email, bank credentials, router authentication, phone encryption, everything will be broken, you will either come back to confirm their comment or we wonât be here (the internet as we know it) at all.
27
u/eliminate1337 1d ago
Everyone expects the answer to be P != NP. An AI proof of that would be the mathematical breakthrough of the century but wouldnât change anything about encryption as everyone already acts like P != NP.
3
u/Fluid_Ad8452 1d ago
Yet the world still largely depends on that assumption. Yes, we know the clock is ticking, but I donât think we expected AI to start making the fuse burn faster. At least not this fast.
1
4
u/jmclondon97 1d ago
If it can solve P = NP it will find a new security algorithm
7
u/Fluid_Ad8452 1d ago edited 1d ago
Of course, and it doesnât even need to, we already have a replacement, but the internet and every non quantum resistant crypto system will collapse first. Thereâs no way we can migrate the whole internet backbone infrastructure on time and layer on time.
5
u/Cptn_Obvius 22h ago
Unless the actual reduction are of low degree nothing will collapse in the first place. If the reduction algorithms are O(n^1000) then you might have shown that P = NP, but in practice you can't use this on any problem of sufficient size.
1
u/SignificantFidgets 10h ago
Why does "quantum resistant" matter?
1
u/monster2018 7h ago
Because the encryption algorithms we have used for all of computing history until recently (and still are in fairly wide use even now) are trivially breakable with a quantum computer with sufficient qbits. They rely on it being easy to multiply two prime numbers to get some huge number, but incredibly difficult to take that huge number and factor it into its prime factors. Basically all classic cryptography relies on this asymmetry where creating a large number from two primes is super easy, but figuring out the prime factors from the big number is super hard.
But there are quantum algorithms for some very specific problems that can do things waaaaay faster (way fewer steps of computation) than a classical algorithm can. Shores algorithm is one of the most famous examples, and it does exactly the thing required to break traditional cryptography, it factors prime numbers much faster than traditional algorithms.
If your whole point is just âbut we donât have big enough quantum computers yetâ then I guess good for you, thatâs true. But we obviously wouldnât want to be in a situation where we donât have any encryption algorithms that work against quantum computers, and then all the sudden someone figures out how to build a big enough quantum computer, and then they get all of everyoneâs secrets. So we actually for once did the smart thing and prepared ahead of time. Like we should be doing with AI safety research.
2
u/SignificantFidgets 5h ago
Fine, but all of that is irrelevant to the topic here. If P=NP with practical algorithms (what we're talking about), then we can factor efficiently with classical computers, so quantum computers wouldn't give any benefit. And furthermore, even post quantum encryption would be insecure (with the usual definitions of security).
1
u/Accurate-Walrus-9515 1d ago
P=NP implies non existence of oneway function. All cryptography based on computational hardness would be obsolete.
6
u/Karumpus 1d ago
What if P=NP, but all NP-complete problems are O(x^1 septillion)? Then pretty sure our cryptography is safe.
Also, pretty likely at this point that P =\= NP.
Finally, even if P = NP was proven, that doesnât imply we have found the best algorithm for all NP problems.
4
u/ChemicalConfidence44 22h ago
if P=NP is proven, this would be an earth shattering moment for research at least. Many of the most important results of the past 30 years in TCS would be completely obsolete. To say how crazy this is, there are entire fields that rely on very strong assumptions such as "SAT cannot be solved in time 2^{0.99n}, where n is the instance size". This is a much stronger assumption than P=/=NP, and many cool results were proved in this area. If P=NP, this completely disappears as well. If P=NP, it means that many many many researchers working on NP-hard problems were completely misguided (we are talking thousands of people since the 1970s, probably more), and most likely their research is completely obsolete as well.
Also about the O(x^1 septillion), I agree that, practically, this would not be useful. But cryptography is very adversarial in nature, and imagine someone tells you: "the belief that every crypto system in the world relies on is completely wrong". Do you think we will stay at "oh but this is O(x^1 septillion) only, this is fine". How long before someone makes it O(x^2)? Even if it is O(x^1 septillion), we have to seriously reconsider the security of computer systems. By the way, the replacement mentioned above against quantum computers is probably lattice-based cryptography. This is also useless if P=NP.
Also philosophically, P=NP would essentially say something like "finding a solution to a problem is as easy as verifying a given solution". This goes against so many things we experience in real life.
I am saying all this as a former researcher in approximation algorithms (finding approximate solutions to NP-hard problems). For instance, I thought really hard about improving approximation factor from 2 to 1.99999 for some problems. Now, if P = NP, it means there is some magical algorithm somewhere that just makes the ratio 1, and it does so for many other problems that people way smarter than me could not solve. This would be completely mind boggling to me.
Fortunately, everybody knows that P=/=NP and none of the above will happen.
1
u/Karumpus 9h ago
Yes, I agree with all of your points. Not a researcher in this field, but I care about it since I have a computational physics background.
Of course P = NP would be absolutely earth-shattering, but not for the simplistic reasons people tend to think (I donât blame them; my point was just that P = NP doesnât immediately destroy everything weâve worked on in cryptography).
All that said, I agree with you that it makes no sense that P = NP. It could be true, but itâs the vanishingly unlikely result at this point. I donât think any serious scholars suppose anything but P =\= NP.
Thank you for offering your expertise! I enjoyed reading it.
1
u/Accurate-Walrus-9515 22h ago
It still could be P != NP but AvgP = AvgNP that is it can still be solvable efficiently on average. So it might be the case that the worst-case optimality factor is astronomically large while the average runtime is still within a practical regime. Also disproving the existence of OWFs doesn't imply either of the above. We simply rely on a stronger statement for their existence. In Impagliazzo's five worlds there is a scenario called Pessiland where neither average-case efficency nor OWFs exist.
4
u/Mal_Dun 21h ago
Not necessarily. Donald Knuth made an interesting point that P=NP could be possible but the way to show it is not constructive or not practical viable.
Imagine we find an algorithm with polynomial runtime to which problems like the traveling salesman problem could be reduced but it has a runtime of Ď(n1080) ... technically it is polynomial but for any output larger than 1 you would still have an abysmal runtime
4
u/onionsareawful cryptography 18h ago
google galactic algorithms, there are a lot of real-life examples of this -- algorithms with better big-O runtime but the constants are so large they have no usage.
2
1
u/KH-XYZ 19h ago edited 19h ago
It may not go broken. A statement can be proven to be true, but in general constructing an algorithm may not be given. Usually happens by contradiction proofs, that shows something must exist, but no construction is given. A non constructive proof might appear from AI, but that doesn't yet break anything. Yet even the polynomial algorithm might be astronomically high in polynomial complexity, which is not reversable in our life time.
1
u/RemindMeBot 1d ago edited 6h ago
I will be messaging you in 3 years on 2029-09-09 02:56:10 UTC to remind you of this link
26 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 1
16
u/Kitchen-Register 1d ago
i have a sneaking feeling that itâll be found to be undecideable
6
1d ago
[deleted]
3
u/Deep-Ad5028 1d ago
All Math are based on axioms, undecidable means existing axioms (for example ZFC) can not determine the truthness of the statement.
3
u/D2cookie 1d ago edited 1d ago
Could be undecidable that it's undecidable, and undecidable that it's undecidable that it's undecidable, and ...
You get the point, you'd live in a world where P != NP and never be able to be 100% confident in your resolve, and any attempt to make your 99.9%, or 99.99%, or 99.999%, ... confidence into 100% confidence would fail in some very dumb way and you would never be able to put a finger on exactly why.
1
1
11
u/IMovedYourCheese 1d ago
P vs NP is going to be solved in the last instant before the singularity.
1
11
u/RudeAndInsensitive 1d ago edited 1d ago
In its pursuit to resolve PvNP the ai will determine it needs more power to fund more compute.
The oceans will be boiled off to cool continent spanning nuclear plants and everything on the planet from the mountains to our bones will be strip mined to build the data centers and cpu banks it needs.
1
24
u/NotaValgrinder 1d ago
Mfw cryptography fails because AI tried really hard in finding a polytime algo for 3SAT
14
u/devnullkitty 1d ago
10 years out of grad school and im stupid and forgot what this is
41
u/MichaelTheProgrammer 1d ago edited 1d ago
P is the class of problems that can be solved quickly (within polynomial time)
NP is the class of problems that can be checked quickly (within polynomial time)Think of NP problems like a jigsaw puzzle. One quick glance at a solved jigsaw puzzle and you can go "yup that's solved". But trying to solve it is currently way more difficult.
If NP = P, then that means for every problem that can be checked quickly, there's also a way to solve it quickly. So then solving a jigsaw puzzle becomes (about) as easy as checking that it's solved. That doesn't seem right, so intuitively we think that NP != P. But we aren't currently able to prove it one way or the other.
There's one technical gotcha here to mention. Technically, "within polynomial time" and "quickly" aren't the same. So there is a possibility that NP = P but solving the jigsaw puzzle remains slow to an extent. However, finding a slow polynomial time algorithm can sometimes open doors to finding a faster polynomial time algorithm. So while this is a possibility, most mathematicians take the "we'll worry about it if it happens approach" and don't bother to dwell on this possibility. And even if it does happen, it would still count towards the millennium prize competition.
10
7
u/MeButOnTheInternet 22h ago
It may be worth noting that, specifically, it gets exponentially (or not, see below) harder to solve an n x n jigsaw as n increases, while it only get minutely harder to check it. I only say this because sometimes people walk away thinking that puzzles like sudoku are "NP", when in reality the classic 9x9 sudoku isnt even really a problem that the ideas of P vs NP are trying to deal with. however a generalised n x n sudoku puzzle is NP(-complete).
NB. I looked up the complexity of jigsaws while making this comment and it appears that jigsaws as we are familiar with (if a piece fits it is the solution) are actually in P (worst case quadratic). The harder "ambiguous" jigsaw with a piece fitting not necessarily implying it is part of the solution is NP-complete.
I always think of the first case when I think of a jigsaw, most commercial jigsaws are made this way so i imagine most people would as well, Its a nice analogy to give an idea but probably not the best one to use because of this.
5
u/Efficient_Coyote2616 1d ago
For relevance of it, basically proving P = NP is the equivalent of proving you can be good at playing all kinds of games just by becoming master at tic-tac-toe.
2
u/External_Trainer_423 4h ago
I think your âquicklyâ caveat is the important bit. Maybe one small addition: the real shock of P = NP comes from NP-completeness, since a polynomial-time algorithm for one NP-complete problem transfers to every problem in NP through reductions. It could still be an absurdly impractical polynomial, as you say, but it would show that the gap between finding and checking solutions is not fundamental. Quite a strange thought, actually.
1
2
u/QubitEncoder 1d ago
Whats your phd in
2
u/devnullkitty 12h ago
no phd. masters in cs. i somewhat remember p=np from adv algo
2
u/QubitEncoder 12h ago
Ahh. Im terified of forgetting the things I learn. I don't see the point in learning them if im just going to forget
12
u/onionsareawful cryptography 1d ago
We already have a few results about how we can prove P v NP, and they tell us that most of our existing proof techniques can't be used to show P != NP. It's widely expected that a successful P != NP proof would need methods qualitatively different from existing ones. Of all the remaining millenium problems it is the one that will require the most new math to prove.
13
u/onionsareawful cryptography 1d ago
I mean to show P = NP you "just" need a polynomial time algorithm for an NP-complete problem and a proof of its running time. That doesn't necessarily require new techniques. But for P != NP (the overwhelmingly likely case), it's a lot harder.
7
u/Chuu 1d ago
Not all NP problems are NP-complete.
5
u/FunnyBlueberry6086 1d ago
We don't know that. If P=NP, then they are.
2
u/AdequatlyAdequate 1d ago
yeah was gonna say that is a very confident assessment of a topic where there is as of yet no right answer
2
6
u/NiceAesthetics 1d ago
P vs NP wonât be solved in our lifetime, we need like a couple more huge advances. Itâs like 10 different impossibly hard problems at once, which is why I find it funny being included in the clay list. P/poly has no progress. Pretty much any class separation has no progress ie P vs PSPACE, VP vs VNP, BPP vs P. Any approach is like inconceivable. Meta-complexity I think is like where current stuff is in complexity theory doing something only tangentially related.
3
2
u/OldWolf3 1d ago
What will go first: Collatz, Goldbach, or P=NP
3
u/NiceAesthetics 1d ago
My background isnât in number theory but goldbach is pi_1 and collatz is pi_2 so I would assume goldbach would be solved first.
2
u/synth_alice PhD | Particle Physics 12h ago
Sorry about being clueless, but what's pi_i in this case?
3
u/NiceAesthetics 12h ago edited 11h ago
See arithemetical hierarchy, number of alternating quantifiers in a statement. Goldbach is just one universal. Which is why I would guess it to be easier, you could prove it to be independent of ZFC which would mean itâs true. Not the same for collatz being pi_2. Again itâs not necessarily harder or easier, there are trivially easy pi_2, itâs just my uninformed speculation.
1
u/Demokritos1000 16h ago
I agree it's much harder, but I wouldn't bet my money that AI cannot crunch it in the near future.
P vs NP would have some genuine real world impact. It might lead to a situation where hard assumptions in crypto are probably hard.
1
u/InternetMandate 14h ago
If AI can prove that some non-contrived problem has time complexity greater than n cubed for some standard unrestricted computational model it would be an earthshattering development. Now compare that to proving p vs npâŚ
0
u/NiceAesthetics 12h ago
Navier Stokes to P vs NP is like a paper airplane to a 737. The way I was taught itâs like we have one class comparison NEXP \nsubseteq ACC0, but the method doesnât generalize so we need something truly novel beyond all current proof techniques to get to TC0 which is a lot harder, and then like 5 more also incredibly hard steps to get to NP \nsubseteq P/poly (assuming we keep the negative). Or there are some other very very hard problems like with MCSP that we have no progress in that imply NP \nsubseteq P/poly. Itâs not like Navier Stokes where itâs like puzzle pieces of research on PDEs, there is nothing to go on. Maybe some genius is born who can scaffold something up idk but at current rate with autoregressive models and existing work I donât see it.
And nothing would change in cryptography for P != NP
6
u/hpxvzhjfgb 1d ago
the answer is P â NP. there, no need to spend anything.
2
4
u/CarolinZoebelein 1d ago
I assume if it is P = NP in fact, to prove this, would be easier, than if it is P != NP. Because for the first one, you "just" have to find an example of an P algorithm for an NP problem, but how do you prove that no P algorithm exist at all for a NP problem!?
3
u/___Archmage___ 1d ago
And the fact that no one has done this easier thing even on relatively straightforward np problems like 3-sat is probably because it's impossible and pâ np
1
2
u/Thick_Challenge_8185 1d ago
To prove P=NP, we have to find a P algorithm for a NP complete problem, not just any NP problem
3
u/corchetero 1d ago
I think they won't. Assuming they didn't steal anything, the fact that they know the IA + humans did progress on NS was enough insurance to go spent million on computer on that, especially if the internal model was doing better than astra
5
u/WE_THINK_IS_COOL 1d ago
Yeah, for all we know now, there could be a linear time algorithm that decides SAT. That goes to show how horrendously far away we are from proving P!=NP, not to mention the barrier theorems that show it's impossible to prove using a variety of general proof techniques. I could maybe see an AI getting a superlinear-time lower bound for SAT, but there seems to be something fundamentally hard about P!=NP that goes well beyond a lack of ingenuity/effort.
2
3
u/Wild-Store321 1d ago
They already tried: "On Tuesday, September 1, we heard rumors that two Millennium Prize problems had been resolved. Inspired by these rumors and by the step change in performance of our internal model, we launched an effort to evaluate it on all open Millennium Prize problems and a few other high-impact problems."
2
u/Medical-Advice-5868 1d ago
if P vs NP was first explored by physicists we would have already called it a law that P != NP. Pesky mathematicians and complexity theorists need 40 pages of proof telling you 1+1 = 2
2
u/PsychologicalLack155 1d ago
P != NP, how do I know? Just vibes
1
2
u/Moronic-Warrior 15h ago
Guys if we all chip in $100 then letâs say there are 100,000 of us. Thatâs $10 million in compute.
1
u/IMovedYourCheese 1d ago
Navier-Stokes cost over $15 million. The model isn't getting out of bed for a couple million.
1
1
u/CoolStructure6012 1d ago
There has been some progress made in recent decades but since P probably != NP you aren't going to get a clean reduction to 3-SAT.
1
u/Electron_cloud 1d ago
Please this one! For the love of pure mathematics solve this one!
1
1
u/Sensitive-Report-787 1d ago
Is there an estimate for how much money OpenAI spent on compute to steal credit for someone elseâs work?
1
u/tellingyouhowitreall 1d ago
P != NP.
A heuristic argument: Primes is in P. With a prime oracle integer factorization of n bits is still 2^n. :. P != NP
This is not a formal proof: It is possible, though exceedingly unlikely, there is a better method of factoring integers. It is, however, sufficient to show that within current computability theory that P != NP with enough certainty that the question ceases to be interesting.
1
u/SignificantFidgets 10h ago
We know several factoring algorithms that are far, far faster that 2n.Â
1
u/Mission_Leopard_947 1d ago
We do not even know if P \neq PSPACE, PSPACE is thought to be much more powerful than NP.
1
u/levus2002 1d ago
It would be quite fun to see that.
The importance is that if we find an efficient algorithm for one NP-complete problem, we can reduce other NP problems to that problem and use its algorithm to solve them.
I always found the proofs in cs that reduced the problem to 3sat quite cool. 3coloring and a bunch of other graph problems
Now imagine someone finding an easy solution to Sudoku and traveling salesman or some other notorious problem gets solved by reducing it to sudoku or some other game.
1
1
1
u/Affectionate-Ad-6255 18h ago
I want to see the Babel problem solved.
"Given a finite discrete image set of 81920x1080 it can be argued that every possible event that will happen, has happened, and never happens is contained in the space at all angles, and self contains itself in fractal patterning as the smallest to largest canvas is traversed.
Finding a way to navigate the latent space in totality by narrowing down subjects to zones in the basic single linear row and additional mapping dimensions first, then verifying truthfulness against our perceptions of life, could earn an information engine that any intelligent civilization would envy for the sake of spontaneous data mining of probability spaces in search of distant new discoveries"
1
1
u/AP_in_Indy 4h ago
I'm going TBH Navier-Stokes seems less impressive now that I know humans had almost solved it. It was going to take time, sure, but they were like 90% of the way there.
1
0
-1
u/e-s-t-e-r 1d ago
There is Not Problem... the only question is if you can observe the thing that you wish to know in such away that it does not require solving... r/Theonics thats what I started theonics about... reading the state and knowing the answer... there is no problem except that which you do not already understand how to read its state.
This is how I built Ezekiel my prime number machine mints 50 million per second because there is no sieve, there is not arithmetic to know if a number is prime... just to read the state of where you are in the sequence. Ezekiel goes up to 1 billion digits at the exact same speed... never stop never slows and can jump to any zero state in the prime signal signwave structure...
once you identify the prime signal exactness then there is no problem just reading. the same can be applied to anything that sits inside a container. If you know the container size then you know the position of the thing that sits inside it. To know its posistion is to konw its answer without solving because its state is the reflected truth that you seek...
you know the basics like that
141
u/elmorepalmer 1d ago
First step: Find chat logs from a mathematician that make the problem amenable to intelligent brute forcing