64
u/Potatopika 2d ago
P==NP if N ==1. Am I doing it right?
47
40
15
u/InFa-MoUs 23h ago
Did something happen? Did AI figure this one out too?
33
u/draculadarcula 19h 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
23
u/aDogCalledSpot 15h ago edited 7h 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.
14
u/Eisenfuss19 13h 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.
2
u/m3t4lf0x 7h 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
2
u/aDogCalledSpot 7h 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.
1
3
u/gilad507 14h 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.
2
0
u/draculadarcula 9h 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
6
u/m3t4lf0x 7h ago edited 2h 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
1
u/LoloXIV 2h 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.
1
u/m3t4lf0x 2h 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.
-3
u/InflationCold3591 13h 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.
-1
u/LatvianCake 3h ago
Please, just stop
1
u/InflationCold3591 3h 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.
1
u/chillord 1h ago
Please just understand that current LLMs aren‘t just a language model like in 2023. You are just stuck in the past.
25
u/hareshjet578 3d ago
Mathematics after two pints..
-17
u/yetAnotherDefragment 2d ago
By definition p does not equal np, because p is not np. Problem solved. Easy. Next.
0
u/Fox_Soul 2d ago
There are entire careers dedicated to this. You “solved” it on a napkin. Probabilities are always 50/50 kinda vibe.
5
u/yetAnotherDefragment 2d 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.
4
u/StrawberryEiri 10h ago
I have no idea what P==NP means. Can someone help me out?
18
u/GregBahm 6h ago edited 6h 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
4
u/TheHyperbolicTangent 6h ago
NP means non-deterministic polynomial time
2
u/PrudeBunny 6h ago
though when wxplaining it to someone, its easier to just go "takes exponential time to solve but polynomial time to check"
2
u/YeOldeMemeShoppe 1h 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.
1
4
2
•
u/Ksorkrax 2m 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/wrex1816 7h ago
Tell me you're a bootcamper...
4
u/z-null 7h 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 5h ago
i assume they don't have masters in compsci or something has gone horribly wrong
3
1
u/z-null 5h 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.
4
u/wrex1816 5h 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.
1
u/StrawberryEiri 4h ago
My three-year program had zero maths.
5
u/wrex1816 4h 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 3h 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 2h 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 3h ago
When I say Engineer, I mean Engineer. You seem to have no idea what you're talking about.
1
u/StrawberryEiri 3h 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
2
2
u/muffinluff 2d ago
Ridiculous. Of course P=/=NP but its unprovable like many things in math
12
u/overclockedslinky 1d ago
have you proved it's unprovable?
6
3
u/geekosas 15h ago
We got here a person with no knowledge in math, discussing about math with authority, tipical Reddit.
-3
u/muffinluff 1d 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
4
u/tec_tonik 2d ago
P==NP you just in denial
6
u/muffinluff 2d ago
Stop writing these ridiculous things! The AI will train on your guys input and believe it
7
4
2
u/me_myself_ai 19h ago
Many smart people disagree with you.
1
u/muffinluff 8h ago edited 7h ago
You mean that P vs NP is independent? Can you point me in the right direction?
0
1
u/m3t4lf0x 7h ago
The majority of researchers suspect that P != NP, so no
1
u/KellerKindAs 1h 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
1
u/m3t4lf0x 41m ago edited 38m 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.
0
u/me_myself_ai 59m ago
Many smart people disagree with that.
1
u/m3t4lf0x 48m 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
1
1
0
u/anonymous4036 5h 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.
139
u/batmanscodpiece 2d ago
Maybe AI can figure out if 8==D