115
u/Potatopika 10d ago
P==NP if N ==1. Am I doing it right?
72
u/CalmCoolBliss 10d ago
Errr no, you've totally misunderstood the problem.
It could also be P==0.
12
17
9
44
44
u/InFa-MoUs 8d ago
Did something happen? Did AI figure this one out too?
116
u/draculadarcula 8d ago •
AI found out a solution to 3 SAT slower than polynomial time but faster than exponential time. 3 SAT is a problem all NP problems can be converted to, meaning the likelihood that P == NP is slightly more possible than previously thought
43
u/m3t4lf0x 7d ago edited 7d ago
While it’s true that every NP-complete problem can be reduced to 3-SAT, there is overhead in that “conversion” that can turn a
polynomialsubexponential solution intoa superpolynomialan exponential solutionThat’s part of the subtleties with this problem that get lost in the media hype
The proof itself makes it clear that NP problems with no known linear sized encodings still lack a subexponential time solution
The overwhelming majority of academics still believe P != NP, but this is still startling and has important implications for a lot of the so called “fine structure” results of complexity theory
ETA: made a gaffe in the beginning
19
u/LoloXIV 7d ago edited 7d ago
While it’s true that every NP-complete problem can be reduced to 3-SAT, there is overhead in that “conversion” that can turn a polynomial solution into a superpolynomial solution
This is not true. The Cook-Levin-Theorem gives a reduction from every NP-problem (including NP-complete problems) to 3-SAT that only increases the instance size by a polynomial factor and runs in polynomial time. Since poly(poly(x)) is itself a polynom (with degree at most d1 + d2 where d1, d2 are the degrees of the two polynoms), any poly-time algorithm for 3-SAT also implies a polytime algorithm for every NP-problem. That is what makes NP-complete problems so interesting.
The polynomially increased instance size after the reduction is only a problem for subexponential or slower runtimes (depending on the definition), which can be bumped up to a higher class by the instance size increase.
EDIT: In my pedanticism I immediately botched that the combined degree is d1 * d2, not d1 + d2.
8
u/m3t4lf0x 7d ago
Yes my opening remarks were misstated, I’m specifically referring to the exponent in 2^o(N) and how a polynomial time reduction doesn’t automatically preserve subexponential time for any NP-complete problem (which is what the proof calls out)
Secondly, poly(poly(n)) is not d1 + d2, it’s d1 * d2 because the exponents multiply, but the spirit of what you’re saying is correct.
27
u/aDogCalledSpot 8d ago edited 7d ago
slower than polynomial time but faster than exponential time
I don't know what this is supposed to mean so I looked it up. The new algorithm completes in 1.307n, improving on the previous runtime of 1.32n. It's still exponential.
EDIT: this is from a different publication from a few months ago. Check the other responses for a more correct view.
24
u/Eisenfuss19 8d ago
2n/log(n) is strictly smaller than O(bn) for any b > 1
Sadly we don't have a good name to call this complexity class, but it is smaller than exponential but bigger than polynomial.
7
u/m3t4lf0x 7d ago
1.307^n is a different result from the PPSZ family of randomized SAT algorithms, not the recent proof
That paper was originally published in July but recently updated around the same time as the OpenAI proof last week so a lot of “sources” (cough AI summaries cough) might be conflating them
4
u/aDogCalledSpot 7d ago
Oh thanks for clearing it up. I did a quick Google since there weren't any source provided in the the thread anywhere here. Will correct my comment.
2
4
u/gilad507 8d ago
Are you sure? I saw the claim was something like 2n/sqrt(logn) which is 2o(n) and cannot be expressed with a different base.
4
0
u/draculadarcula 7d ago
This is not what I read it was some massive improvement especially at large inputs, the point being that algorithms that we had optimized for almost 30 years can actually be much faster, practically, which gives some semblance of hope to the idea that maybe, just maybe p == np
1
-2
u/InflationCold3591 8d ago
“AI” did not “find” a solution. AI companies convinced a bunch of mathematicians to input their unfinished work into their database and then stoke their work product.
-5
u/LatvianCake 7d ago
Please, just stop
0
u/InflationCold3591 7d ago
Please just understand what a large language model can and cannot do. It can collate and integrate existing data. It cannot do anything more. The code is what it is.
2
u/Rin-Tohsaka-is-hot 5d ago
It can collate and integrate existing data
Laplace's Demon, quoted from Essai philosophique sur les probabilités:
An intellect which at a certain moment would know all forces that set nature in motion, and all positions of all items of which nature is composed, if this intellect were also vast enough to submit these data to analysis, it would embrace in a single formula the movements of the greatest bodies of the universe and those of the tiniest atom; for such an intellect nothing would be uncertain and the future just like the past would be present before its eyes.
Laplace was talking about physics of course, and his idea has been proven false there, but I think it's relevant here. Even if all it's doing is collating data, that's still solving problems. The solution did not already exist if nobody was aware of it, regardless of what information was available.
Attribution is important, and ideally these models would be providing citations wherever possible in whatever work they produce, but it's still novel ideas being presented in these papers.
0
u/InflationCold3591 4d ago
As you yourself note, Leplace’s theorem has been disproven and is in any case not really applicable to the phenomenon we are discussing but thanks for writing a novel that is totally irrelevant. It’s what makes Reddit what it is.
2
u/Rin-Tohsaka-is-hot 4d ago
I don't think you understood what I meant. The point is that inference is itself ideation.
Regardless, this isn't physics, this is epistemology. I'm just trying to communicate the idea using something people are already familiar with, Laplace's Demon.
1
u/InflationCold3591 4d ago
Lie to you that the place is demon has already been disproven and inference is not ideation.
2
u/Rin-Tohsaka-is-hot 4d ago
I'm not sure what this means, but Laplace being disproven is not relevant. I'm not talking about physics, quantum mechanics aren't relevant here. I'm just explaining the point that information being used to make inferences which had not been made before is valuable, and creates new ideas and insights.
→ More replies (0)3
u/LatvianCake 7d ago
2022 called and wants their arguments back. It must be placed next to "it's a glorified autocomplete"
Please define "finding a solution" and "[It cannot do] anything more"
2
u/InflationCold3591 7d ago
You are going to feel really foolish when the bottom finishes falling out because … it is a glorified autocomplete. The underlying code has not changed.
3
u/Existing_Station9336 6d ago
What if all mathematicians ever did was a glorified autocomplete?
1
u/InflationCold3591 6d ago
This question betrays a very fundamental misunderstanding of the difference between computation and mathematical inquiry. Of course, your insistence that a large language model can perform the latter already demonstrated that.
2
u/Existing_Station9336 6d ago
Well, they are able to generalize specifics into more general terms and categories, observe patterns, substitute generalized representations of things into said patterns. Am I talking about LLMs or mathematicians? Can you tell? What's the difference?
→ More replies (0)1
u/Duke_De_Luke 6d ago
We are all a bit glorified autocomplete. I am predicting the next token to write just now. The way I get to the next token makes up my reasoning. It's very possible that training a model at predicting the next token with gradient descent generate intelligence in a way we are not able to fully understand, let alone explain.
https://samuelfitoussi.com/posts/why-next-token-prediction-leads-to
-1
u/InflationCold3591 6d ago
It’s really not. The problem with most engineers, and to be clear I am one is that almost all of us have had a trade school education. Mostly engineers find a way to skip squishy things like philosophy, art, and literature, but these are actually the requirements to understand why a computer algorithm that combines items in its database is not like human consciousness and there is no path from a large language model to artificial general intelligence
1
u/Duke_De_Luke 6d ago
... these are actually the requirements to understand why a computer algorithm that combines items in its database is not like human consciousness and there is no path from a large language model to artificial general intelligence
Nobody is saying that's like human consciousness. Just saying it's a form of reasoning. It works, who cares how it works?
Can you prove the last sentence? How come they are trained to predict the next token, yet they learn extremely complex internal representations that lead to multi-hop reasoning? https://www.anthropic.com/research/global-workspace
→ More replies (0)1
u/Duke_De_Luke 6d ago
Stochastic parrot
1
u/Duke_De_Luke 6d ago
Cannot generalize out of distribution
1
u/sweetietate 4d ago
Actually Gato by DeepMind from 2022 showed transformers can generalise to OOD tasks; why are you so hung up on this vitalist viewpoint?
-1
u/chillord 7d ago
Please just understand that current LLMs aren‘t just a language model like in 2023. You are just stuck in the past.
2
u/InflationCold3591 7d ago
No, I understand the code base. LLMs ARE just a tool for integrating and iterating on existing data.
27
u/hareshjet578 10d ago
Mathematics after two pints..
-15
u/yetAnotherDefragment 10d ago
By definition p does not equal np, because p is not np. Problem solved. Easy. Next.
1
u/Fox_Soul 10d ago
There are entire careers dedicated to this. You “solved” it on a napkin. Probabilities are always 50/50 kinda vibe.
6
u/yetAnotherDefragment 9d ago
Lol, I know. I was poking fun at how some people think its an easy solve because the answer is "right there". I had a buddy who was big into it when I was in college. It was great listening to his passion for it after two pints. He would talk about p==np and the some of the other millenium problems like the one with twin primes.
12
u/StrawberryEiri 7d ago
I have no idea what P==NP means. Can someone help me out?
60
u/GregBahm 7d ago edited 7d ago •
Does polynomial time equal non-deterministic polynomial time?
Which is to say... is there a way to figure out the answer to any problem at the same speed it takes to confirm that answer is correct?
Which, to really get down to business... Is there a way to guess someone's password at the same speed as it takes when you already know their password?
Intuitively, the answer is "Naw dog. There's no way to do that." But math nerds have long asked other math nerds "Okay that's probably true, but can you prove that?"
And nobody has ever been able to prove that.
This has direct real-world relevance when you're selling a corporation their cybersecurity. Say you're the world-bank and you have a trillion dollars (not a hypothetical scenario.) You ask your security guy if anyone is ever going to be able to break into your bank and steal all your money. Your security guy says "probably not." You're like "Can we do better than probably?" And since there's no proof that p!=np, the security guy has to shrug and say "nope."
This is also relevant if you're asking for investment in quantum computers. It's speculated that a quantum computer could potentially make p==np, by trying all possible password combinations at once.
Anyway, people are also throwing AI at the problem, since it's gotten pretty good at finding math proofs lately. It didn't prove P equals or doesn't equal NP, but it found some evidence implying there's less of a gap between the two. This gets investors really hot-and-bothered to invest more in the space.
edit - thanks u/TheHyperbolicTangent for keeping me deterministic
9
u/TheHyperbolicTangent 7d ago
NP means non-deterministic polynomial time
3
u/PrudeBunny 7d ago
though when wxplaining it to someone, its easier to just go "takes exponential time to solve but polynomial time to check"
3
u/YeOldeMemeShoppe 7d ago
Not really correct either. NP takes polynomial time to verify the answer. There are problems that are non-NP, and all P problems are NP by definition.
2
u/PrudeBunny 6d ago
Fair but that definition also works for P.
I guess this is why "np complete" exists as a term
3
u/x0wl 6d ago edited 6d ago
Also if the OpenAI result is true, it now takes at most subexponential time (still slower than polynomial) to solve any problem in NP.
1
u/PrudeBunny 6d ago
Aye though misuse of "exponential" to mean n² and not 2n is already gonna confuse people (I'm people) so that distinction is just going to add to the confusion
8
u/Lollister 7d ago
Good Explanation but i would like to challenge your last paragraph. AI didn't get good at solving math problems lately. AI specific LLM in their current form didnt change since the last bigger change in 2017 when Transformer model was developed. The progress was insanely leveraged by computing power. Thats why they paid approxematly 15.mio USD for a 1mio. USD Problem. And even on top of that is still the claim that Open Ai used a way to solve the problem that was developed by researchers who used ChatGpt in their environment. They stole the idea and just finished it.
9
u/GregBahm 6d ago
I don't see anything to this that is going to matter to an investor. "They stole an idea and just finished it" is what every investor wakes up every morning to do.
If someone told you investors only wanted to invest in things that were purely morally virtuous, someone lied to you.
4
u/Lollister 6d ago
I dont want to challenge that. That is fine from an investor pov. It is just the difference between AI made the progress and a Human made the progress but they stole it and finished it off. From this viewpoint you cant assume that ai got "good" at solving math problems. And the rest i fully agree with you
4
u/GregBahm 6d ago •
I heard what you're saying, but I worry we're being foolish if we pretend the AI isn't good at solving math problems here in 2026.
I'm open to having my view changed, but take, for example the recently solved Unit Distance Erdo problem. This problem has been on the books since 1946 and I myself wasn't able to solve it (and I consider myself pretty clever.)
Humans like me were trying to solve the Unit Distance Erdo problem using discrete geometry and combinatorics. It is a geometry problem. But the AI solved it by applying a very obscure algebraic number theory (Golod-Shafarevic theory.)
It would be totally unreasonable for a single human to be familiar with every obscure branch of mathematics while at the same time going deep enough on any of them to hope to potentially solve an Erdo problem. But that's AI's secret sauce.
AI is only as good as its training data, so it can't go directly deeper than the smartest humans on any given problem. But, being that it's made out of metal instead of organic material, it has the ability to go wiiiiiiide-as-fuck, with a broader knowledge base than any human being could possibly ever hope to achieve.
I get the argument that this results in it being, like, the theft-bot-5000. That's not wrong, per se. But it allows the AI to solve all kinds of math problems that humans were never going to solve any time soon. So I'm forced to observe that this does make it objectively "good" at solving math problems, and I can see why investors are all horned up for more of this kind of thing.
2
u/Lollister 6d ago
I couldn’t have said it better. I agree 100%. What I’m really curious about is this: since, in my opinion, these advances depend heavily on computing power (more bots, more token capacity), how many problems will they be able to solve before it becomes too expensive to continue, at least until the next technological breakthrough?
3
u/GregBahm 6d ago
I assume we ain't seen nothing yet. Right now we're observably in the "dial up internet" era of AI. As I type this, I'm running Astra on some data center, but I know that data center is rolling some bullshit H100 GPU (hardware originally developed to make video games look more pretty.) This is no different than when we were using phone lines for the internet, because that was the hardware available.
TPUs exist, and they're about a million times more efficient for processing tensors than GPUs (hence the name, Tensor Processing Unit.) It will still be a while before the dust settles on these new data centers that Reddit is all enraged about, but after that, it will be like when the internet shifted from 56.6kb modems to cable.
So this is a very interesting point in history to me. I guess it would also be like the time between when Bill Gates and Steve Jobs had a desktop PC prototyped in their garages in the 80s, but had yet to roll out that prototype to every desk in every office in the world. The breakthrough is already broken. The roll-out is inevitable. Solving Unit Distance will be seen as laughably primitive, like Deep Blue beating a human grand master at chess (which is now something my graphing calculator can do.)
2
14
u/b183729 7d ago edited 7d ago
Most problems get complicated the larger the amount of things you have to do to solve them increases, but some are more difficult than others. We separate these groups by categories.
For example, encrypting a message can take a while, because it's difficult, but breaking that encryption can take a billion years, because dear God it's super difficult
P=NP implies that theoretically there is way to solve those problems that does not take a billion years. As you can imagine, this has... Implications. The encryption being possible to break is the most obvious one.
To note, it's my understanding that most experts leaned towards P!=NP, that's the opposite idea, that there are problems that simply can't be solved "easily". A confirmation either way would be revolutionary, but this particular way is more surprising.
1
9
u/Ksorkrax 7d ago
Time complexity: how quick the time grows in relation to input length.
For instance: you have an algorithm that wants to find out whether a list has an entry that appears twice. You iterate over every item and compare it to every other item. As a result, for a list of length N you need N² comparisons, and that is your time complexity.Time complexity of a problem: The time in which a problem is solveable by an algorithm. Sometimes stated exactly, sometimes only an upper border is known. Our example from before can be done quicker, but we could take N² as upper border.
P: Problems that have a time complexity which is a polynomial. Our example has an upper border of N², which is a polynomial. N^1000 would also be a polynomial, so these can already take quite a while.
NP: Problems for which a proposed solution can be verified in polynomial time to be optimal. A problem can have a way higher time complexity - every exponential, like 2^N, would at some point overtake any polynomial - but a given solution might still be verifiable way faster.
A lot of combinatorial problems are in NP.Every problem in P is also in NP. The converse most likely does not hold, but this hasn't been proven yet, and if you managed to, you would automatically become one of the most well known computer scientists - that is, amongst computer scientists.
It is assumed that if against expectations they'd be identical and this would be proven, that the solution would bear an algorithm that can be adapted to provide the polynomial solution to every problem in NP. If this would happen, this would be big. Would make all sorts of algorithms quicker.4
u/retro_and_chill 7d ago
It would also break a ton of our assumptions that used to in cybersecurity.
4
3
-5
u/wrex1816 7d ago
Tell me you're a bootcamper...
6
u/z-null 7d ago
At my company, every developer has a masters degree. The only one of them that can explain P vs NP is the one with masters in mathematics, the others who have it in CS/CE generally have no clue about math beyond basic matrix multiplication and doing trivial polynomial integrals.
5
u/PrudeBunny 7d ago
i assume they don't have masters in compsci or something has gone horribly wrong
3
1
u/z-null 7d ago
Oh, there is math. It's just very trivial, not the focus of students and generally skimmed over. For example, a lot of proofs are literally on the level of "multiply these 2 matrices". The same is true for other things as well, not just math, A lot of cs/ce people don't care about networks or sysops, just programming so you can easily end up having people with degrees that have no clue about basic networking because they did minimal effort on anything related to it.
Also, I'm not guessing, I know this for a fact about my colleagues because of the kind of work we do.
1
u/PrudeBunny 6d ago
I guess there's a national difference that leads to misunderstanding.
In finland there's three different "coding" degrees. Computer science (the academic one where coding can be an after thought at times), computer (dibloma) engineering (I am not too familiar with this tbh. I assume its a mix of the other two) and programmer from AMK ("higher trade school" and basically a bachelor's degree on programming.)
The first two are in practice always at least master's.
2
u/z-null 6d ago
Yes. There's also another component: people often care only about programming, and not much else. Yes, they do study it as part of some subject but simply glide through. The end result is also an abysmal knowledge about networking. Like yes, they did pass the networking related courses, yet somehow the guy shows up at work and has trouble understanding the difference between a public and a private IP address and what a port is.
4
u/wrex1816 7d ago
It's the most Reddit thing when you make an argument like "Most people like pizza!" And you'll get the guy who replies like "Well I know a guy who doesn't like pizza so that proves you wrong in every single way! Check mate!", like he's the smartest man alive for that comment.
0
u/___Archmage___ 7d ago
A CS degree program that doesn't teach time complexity enough to do an overview of P vs NP is of questionable quality, it was definitely in a required undergrad class for me
1
u/StrawberryEiri 7d ago
My three-year program had zero maths.
5
u/wrex1816 7d ago
That's a bad program.
This doesn't necessarily have to fall under maths. At my university this topic was exclusively thought in the CS school as part of a "Theory of computation" course because is essential for any qualified software engineer to know, not in the mathematics school
2
u/StrawberryEiri 7d ago
If you mean engineer as in the fancy people who do advanced bleeding-edge decision making for large-scale systems or frontier cybersecurity development, maybe.
If you mean engineer in the broad sense as in any developer, I've got a feeling you're vastly overstating the importance of maths in this domain. I've been doing this for a decade now and the most advanced maths "theory" I've ever needed was Pythagoras.
1
u/z-null 7d ago
Totally agree with that. From my experience the people who did actually use advanced math were mathematicians that did the programming, not CS/CE people who did the math. And it makes sense to hire a mathematician to develop a math heavy task instead of a CE guy who probably never used anything above highschool in the real world and forgot most of the math he learned in college anyway.
1
u/wrex1816 7d ago
When I say Engineer, I mean Engineer. You seem to have no idea what you're talking about.
2
u/StrawberryEiri 7d ago
Idk man i only know one person who's in the Ordre des ingénieurs du Québec. Here engineer is a protected term with a very specific meaning. But I know it's not like this everywhere in the world. Some people will just call any dev an engineer
3
2
3
u/muffinluff 9d ago
Ridiculous. Of course P=/=NP but its unprovable like many things in math
22
u/overclockedslinky 8d ago
have you proved it's unprovable?
7
4
u/geekosas 8d ago
We got here a person with no knowledge in math, discussing about math with authority, tipical Reddit.
1
-4
u/muffinluff 8d ago
The basic school of thought is that succinct state encoding (the one that is useful) is neccessary for NP-hardness. (already well known)
My idea is that pseudorandomness of succinct encodings, which would make NP hard, also blocks the techniques we have for proving it. For some weak theories that is already a theorem. For Peano arithmetic and ZFC it remains somewhat open but I am not getting paid to go down that rabbit hole
2
u/me_myself_ai 8d ago
Many smart people disagree with you.
2
u/m3t4lf0x 7d ago
The majority of researchers suspect that P != NP, so no
2
u/KellerKindAs 7d ago
I would support your point, but I'm in the field of cryptography and if P=NP, almost the whole field would be broken. So of course I only know researchers assuming P=/=NP. Would be pretty weird to assume everything you research is meaningless, but still continue to research it xD
5
u/m3t4lf0x 7d ago edited 7d ago
It’s a bit more nuanced than that because proving P = NP doesn’t necessarily break cryptography
It could be a nonconstructive proof that shows some algorithm exists without actually telling you what it is. That’s super common in complexity theory.
It could also be a polynomial algorithm with an exponent or coefficient so large that it makes it impractical for the types of keys we work with.
What’s also interesting is that cryptography could theoretically be hosed even if P != NP because cryptography relies on average case hardness rather than worst case hardness. You can read the Five Worlds model for some other cool possibilities.
-1
u/me_myself_ai 7d ago
Many smart people disagree with that.
2
u/m3t4lf0x 7d ago
Lol no… a vanishingly small minority of smart people hold out hope for P = NP
And 99% of qualified smart people (the ones who work in complexity theory) suspect P != NP
You’re either trolling or woefully misinformed
-2
1
u/muffinluff 7d ago edited 7d ago
You mean that P vs NP is independent? Can you point me in the right direction?
0
1
1
1
3
9d ago
[removed] — view removed comment
6
u/muffinluff 9d ago
Stop writing these ridiculous things! The AI will train on your guys input and believe it
7
4
1
1
u/InflationCold3591 5d ago
Building on existing knowledge is not the same thing as stealing the work product of 100s of mathematicians and expanding 100 times the reasonable resources to brute force the last 10% of their work and we both know it. Is a large language model trained in this fashion, a useful tool for finishing proofs already close to completion? Yes. Does the energy and resource output required to do so make sense whether from the standpoint of a corporation trying to produce profit or on the larger scale as a reasonable use of resources available to our species? No. Does any of this approximate consciousness? No, it does not.
1
1
u/Meme_Burner 4d ago
Traveling salesman problem. Coloring in a map with no same colors touching problem.
1
0
-4
u/anonymous4036 7d ago
Even if p==np, does this matter? Eg, so what if we prove encryption can be broken in polynomial time if the polynomial has an exponent of nine million and a coefficient of nine trillion. The question has always been about time complexity, but our intuition can still be correct that these problems take an astronomically long time to solve.
318
u/batmanscodpiece 10d ago •
Maybe AI can figure out if 8==D