What P vs NP is actually about

Support us on Patreon: / polylog
What if we could run algorithms backwards? We discuss how we could do this by turning algorithms into circuits and encoding those into satisfiability problems. We then explain how it all connects to P vs NP.
#somepi
0:48 Satisfiability
2:15 Breaking RSA
8:46 General reductions to SAT
12:03 P vs NP
Blog post: vasekrozhon.wo...
Code for the animations: github.com/pol...
Blender clip: • Will It Blend? - iPhone
Richard Hladík: Script editor, animator
Gabor Hollbeck: Video recording, video editor
Václav Rozhoň: Writer, animator
Václav Volhejn: Narrator, animator, script editor
Thank you to our beta testers: Matěj, Honza, Filip
Animations: manim, a Python library docs.manim.com...
Color palette: Solarized ethanschoonove...
Music: Thannoid by Blue Dot Sessions
Pictures: Wikipedia, Internet

[@PolylogCS]

Blog post: vasekrozhon.wordpress.com/2024/08/18/what-p-vs-np-is-actually-about/

[@AbeDillon]

I tried to comment on your blog post, but Wordpress was being super cagey: I don’t think your take on Neural Networks is “a stretch”. I’ve been noodling about similar topics for a while and I think there’s a framework inwhich one can demonstrate some equivalence between neural networks and logic networks. Imagine a neural network where the outputs of neurons are constrained to either +1 or -1 (equivalent to True & False, respectively) and the weights are constrained to the values +1, 0, and -1 (equivalent to a normal connection, no connection, and an inverted or NOT connection; respectively). Neurons have a summation stage: z = wx + b, and an activation stage y = f(z). For simplicity, we can also define a value, k, equal to the number of non-zero weights into a neuron. We can create a neural-equivalent AND gate by setting b = 0.5 - k, and y = f(z) = tanh(z) while rounding or clamping y to the nearest non-zero integer. We can create a neural-equivalent OR gate by setting b = k - 0.5 and using the same activation function. It’s been shown[1] that a feed-forward neural network with a single hidden layer qualifies as a universal approximator. That’s a layer of “hidden” AND gates feeding into output OR gates, which is equivalent to CNF-SAT. Note: there are many other ways to conceptualize neural-equivalent AND and OR gates, but I believe one has to factor in some version of the value k somehow, though; I haven’t explored how constrain something like the bias value in such a way might complicate back propogation. I know a lot of neural net theory was developed in the context of continuous functions and it’s may not be clear if something like the universal approximation theorem holds true if one discretizes the input, output, and weight values. However, I think there’s an argument to be made that one can “emulate” more continuous-valued neurons with discrete neurons since the set of {AND, OR, NOT} logical opperators are functionally complete. If one can implement the tanh(x) function in digital logic, it shouldn't be too much of a stretch... Please let me know what you think. I have no background in CS or math or anything, so if any of these ramblings offer any valuable insight, I’d love to know. I also have no idea how one goes about publishing papers on such topics, so if you’d like to colaborate on something like that, I’d be thrilled! (this isn't easy to do on KZbin AFAIK, but hopefully we can connect some way if need be) [1] www.sciencedirect.com/science/article/abs/pii/0893608089900208

[@SpektralJo]

Remember, even if P=NP, that doesnt mean that the SAT solver algorithm is fast on a practical level. Multiplication is in O(n log n), but that algorithm hast constants that don't fit into the observable universe. Cryptography is only doomed if we find a practically "fast" algorithm

[@PolylogCS]

This is a great point, it's not obvious a polynomial-time SAT solver would be practical. One of the ideas we did not have time to go into is that although "existence of polynomial-time algorithm" does not imply "the existence of practical algorithm", it correlates with it heavily. Like, sure, the theoretically optimal multiplication in O(n log n) has horrible constants, but doing it by FFT in slightly worse theoretical time is extremely fast in practice. Here's a challenge: What is the best example of a problem where we know a polynomial-time algorithm for it, but we don't have anything practical? EDIT: see the clarification below

[@Dent42]

@@PolylogCSAre you asking, like, “When is the average case equal to the worst case?”? ‘Practical’ isn’t well-defined

[@denki2558]

​@@PolylogCS It also depends on how P=NP is proven. If it's proof by contradiction, it might take decades before algorithms reversing cryptography can be discovered. If it's a constructive proof, were doomed immediately.

[@timtjtim]

@@Dent42no: average == worst is a different question. Consider practical = computable with current hardware.

[@AbelShields]

​@@PolylogCSthat's easy, its universal search-- hey wait a minute didn't you do a video about that?!

[@SpriteGuard]

The wildest part of P vs NP to me is just how many dead ends there have been. There's an entire genre of theorems ruling out particular ways that it might be solved, because it's far easier to prove that a line of reasoning will never resolve the issue than it is to actually solve it.

[@tristanridley1601]

Considering most people believe it's impossible, this is actually direct progress toward proof of that. We may have no idea how to prove that NO solution exists, but every constraint on it is progress.

[@darrennew8211]

Very cool. I have a PhD in computer science and I never heard PvNP explained so elegantly.

[@PolylogCS]

thanks!

[@99jdave99]

This is a really good explanation! P = NP never made a satisfyingly amount of sense to me, but this helped bridge that gap a bit! Thinking of it as “can we run solvers backwards?” is a cool approach! Quite sensible!

[@PolylogCS]

Thanks :)

[@NovemberIGSnow]

I had a fun conversation with a coworker once who suggested that it may be possible to prove that it's impossible to prove or disprove P=NP. I noticed a fun contradiction there. If you can prove it's impossible to show P=NP or not, then there is no Turing machine that can solve an NP-complete problem in polynomial time, because the existence of such a machine would prove the algorithm. My coworker countered with the notion that there could be a TM that seems to solve NP-complete problems in polynomial time for all inputs we've given it so far, but that we might not be able to t prove its complexity does not eventually get dominated by a non-polynomial term for sufficiently large input. I countered with the idea that you could analyze the runtime of the TM with a TM to find if there's a sufficiently large input where the algorithm becomes dominated by a non-polynomial term. He said that's the halting problem. Oops, lol. He was right.

[@PolylogCS]

That's a cool argument! I would say that proving that "p=np is in unprovable" (in the sense of being independent of zfc) is almost equivalent to proving p!=NP due to your argument: any polynomial time algorithm for SAT in that world would be incomprehensible mess and most probably it would be horribly inefficient in practice. Can't imagine an efficient algorithm that would be unanalyzable...

[@clearnightsky]

@@PolylogCS It's possible that iterative algorithms outputing data in the realm of chaos may fall into that cayegory if we use it to output a desired value.

[@Zane3G]

​@@PolylogCSA TM's behavior being independent of zfc doesn't necessarily mean it is incomprehensible. Consider the TM 'T' that iterates over proofs in zfc and halts when one proves False (or any statement independent of zfc) ZFC can't prove T never halts because doing so would prove its own consistency

[@PolylogCS]

@@Zane3G Ok ok :) Maybe instead of saying "it would be incomprehensible AND inefficient", let me claim it would be inefficient and if it is comprehensible, not in the way that let's you understand what makes the problem "easy".

[@MadocComadrin]

Your coworker is a bit off. The Halting Problem takes a TM as part of its input, i.e. there's no general algorithm that works for any TM. If you fix the TM, this changes the problem significantly. If this wasn't the case, it would also imply that Rice's Theorem makes testing and formal verification useless, which it is not. Also, we're working with NP Complete Algoritms, which by definition terminate. The Halting Problem is less of an issue here.

[@DemonixTB]

important to note that P is still a very large space O(n^9999999) is still in P, while O(2^0.01*n) isn't from that far away, many problems look the same, it is much more useful to prove a specific algorithm is O(n log n) and that the constants aren't too big, than it is to prove P=NP if the reductions require an incredibly unwieldy degree polynomial (even better to find easily parallelizable algorithms that are just a bit higher on the complexity side, since the takeover point for the given assymptotic functions can land outside of general human interests or dataset sizes)

[@tectrixer7036]

True, although even though the constants are heavily favoring the NP algorithm here, it only takes about n = 3,155,522,878 such that the polynomial algorithm is faster. But you are fully correct, the total number of instructions (assuming that the O-notation has the exact amount of instructions) would be about 6.8e+94990703 so wayy to many to be computable. => n is still small when P overtakes NP but it is still unpractical to use the NP algorithm

[@gitgudnga]

i dont think anyone would be willing to make 10^8-1 loops to prove something is polynomial time

[@Ganerrr]

Hands down best explanation on why NP problems are equivalent

[@zokalyx]

mah boi ganer getting that knowledge

[@jakub.118]

Cool video! My curiosity: Satisfied

[@PolylogCS]

Thanks :)

[@MishaBehersky]

bro used subway surfers trick while explaining 10:35

[@traywor1615]

Oh god and I thought that I was really interested in this problem. Turns out I am just a TikTok addict.

[@PolylogCS]

Gotta keep the engagement up somehow

[@voltflake]

noticed that too😆

[@realedna]

@@PolylogCS Engagement doesn't necessarily mean people pay more attention, if the alternative content you present is merely a distraction with different addictive powers. Attention != Distraction. And engagement also shouldn't mean watching the video for whatever reasons, otherwise fake views would also count as engagement.

[@rileyn2983]

This is the best explanation I've seen on why NP contains all the problems with easily verifiable solutions. I've always known that but didn't quite get why until now. Great video. You definitely deserve more subscribers

[@PolylogCS]

Thanks :)

[@chamidumadumal7130]

Congrats on winnig the Summer of Math Exposition this year. Great Job!

[@PolylogCS]

Thanks!

[@RobinDSaunders]

My understanding is that one-way functions are required to have no P-inverse even in the average case, while P != NP only requires functions with no P-inverse in the worst case. So in principle, we could have that all P-functions are average-case P-invertible, even without P = NP.

[@PolylogCS]

Indeed! P=NP means you can efficiently invert any function, always. But even being able to efficiently invert functions on average is still a serious security problem. So, we were correct that "P=NP breaks cryptography" but one can imagine a world in which P!=NP and yet cryptography still does not work very well. You might enjoy googling for "Impagliazzo's Five Worlds".

[@RobinDSaunders]

Thanks, I was trying to refind that paper and couldn't remember the author!

[@jmarvins]

interestingly enough, eminent computer scientist donald knuth was a contrarian on the P vs NP issue, and thought that P probably does equal NP his reasoning was heuristic: only the tiniest portion of the infinitely many possible recursive functions will ever be knowable to us - let alone practical to use - due to the nature of infinity, and thus the fact that it doesn't seem impossible should make us suspect there might be some inconceivably large P-class SAT-solving algorithm out there beyond Graham's Number or whatever other huge finite number of your choice i am not sure myself that this is a convincing argument, but nobody has proof and Knuth certainly had a better intuition about things than most, including me...

[@idonnow2]

Sadly infinity is not a material reality. A function like that would be something like an algorithmic implementation of a reverse laplace's demon to figure out a previous state from a specified current state; and any such implementation would necessarily have to be materially larger than the material reality it is attempting to model

[@vaclavrozhon7776]

It's also good to know that Knuth likes to be a contrarian. :) I can also imagine that p=np, but i think that if that is the case, it's most likely for some weird logical reason and the fast SAT solver would be something akin to universal search.

[@myxail0]

Knuth isn't dead yet so don't use past tense

[@skorp5677]

I really appreciate the Stuff Made Here attitude to background screens xD Amazing as always. I've heard lectures on satisfiability (esp. classes of SAT-solvers and reduction) and mathematical logic and this was a great overview as well as an interesting perspective on the content. Thank you for your work! :)

[@PolylogCS]

Great to hear!

[@orionspur]

When I worked on complexity theory back in the 90s, it occured to me that it is possible the following is true: For all n there exists a compressed lookup table that (in time polynomial in n) lets you solve all satisfiability problems in n variables. This is not one tidy algorithm, but a sequence of horribly complex ones (one for each n) that happen to suffice for the task. If such a sequence exists, that may make it impossibly difficult to prove that P ≠ NP.

[@PolylogCS]

I think this is why proving lower bound in general is so incredibly hard, there is so few techniques that have the power to rule out such algorithms...

[@michaelrenper796]

@@PolylogCS Very short an imprecise argument. If the proposal above is true, it would mean that there is no finite SAT solver for all n. The is somewhat similar to the Turing stop problem, where one can possibly find a solution for a given N with enough effort, but not one algorithm for all N. In short I think you are suggesting that P ≠ NP is undecidable. And it may well be.

[@MagicGonads]

@@michaelrenper796I have a feeling that it'd have to be undecidably undecidably... (etc) undecidable, cus if at any level we know the undecidability is decidable then we know P =/= NP as if P = NP there'd be an algorithm that decides it (the algorithm that takes this algorithm and proves that it is a solution to P = NP) (although maybe this is abuse of decidability, hence 'have a feeling')

[@LB-qr7nv]

@@MagicGonads the problem with this argument is that if P=NP we will not necessarily find the algorithm and we will not be able to prove that it is an algorithm that solves SAT

[@cambrown5777]

To the point of the great analogy you made regarding entropy and the 2nd law of thermo: in the case of computers, it quite literally is a matter of entropy. In a simple two-input digital gate (i.e. AND, OR, NOT, XOR, etc.) we take two bits of information and reduce it to a less organized state, being a single bit of output and heat! I have a feeling that current digital computing is limited by its paradigm to find a solution this problem. Loved the video, had never made these broader connections between the hardware world and theoretical CS. Signed, a junior CPU designer.

[@PolylogCS]

Thanks! You might like the section about reversible computing in the blog post.

[@be1tube]

The P=NP problem is itself an instance of reversing. We want to find an input to a computer that meets the constraints of "being a SAT solver" and being polynomial-time.

[@Ceelvain]

Yeah. Except that these are pretty hard to check. There might be some systematic ways to determin the worst-case complexity of a program. But how would we begin to check if a given program is a SAT solver?

[@be1tube]

@@Ceelvain You're right. Reversing is more general than NP. NP (and co-NP) are classes of problems that are "easy" to check. Checking that something is a SAT solver is more complex. For that checking, I would probably start with a theorem prover. But there are probably lots of complexities to implementing such a checker. So I'm not confident that that approach would be sufficient. Of course reversing such a checker would be even harder.

[@logician1234]

Aahh, a famoust computer science researcher, Mick Jagger

[@harriehausenman8623]

Great fresh take on the topic. Fantastic video with amazing production value! Thanks a bunch 🤗

[@PolylogCS]

Glad you enjoyed it!

[@mattbatwings]

Huge congrats on winning somepi :) - number 2

[@PolylogCS]

Thanks! I also really liked your video and how you managed to make algorithms approachable! Not sure if you know: the main algorithm you described in that video is known by the theoretical computer science community as it has some really beautiful properties; I left a comment next to your video with a link, I will happily try to find some better resource if you are interested!

[@EHuelsz]

Excellent video, I have been following closely videos released here on KZbin related to P vs NP for the last 13 years and, in my opinion, this is the one that best explains the core of NP-completeness definition, thank you very much.

[@PolylogCS]

Thanks!

[@divy1211]

This is hands down THE BEST explanation of P vs NP I've ever seen, much better than what I was taught at university. Awesome video!!

[@PolylogCS]

Thanks :)

[@lunarthicclipse8219]

So I have an algorithm that I am currently working on. it's a very fast approximation algorithm for subset sum problem where it tries to find a subset that sums up to be close to the target sum specified. And I am quite stumped currently as I am still a uni student and I have no experience writing a research paper. I would love to reach out to you and share my work! I am sure u'll find it interesting :) I dont think anyone tried my approach to solve the problem. My approach is instead of working with complex data sets, ill just work with their indices. (This turns our problem from a random dataset, into a neat linear function distribution.) This allows us to instead find a subset whose sum of indices is equal to our target expected sum of indices if subset does exist. It's a very straightforward approach, but has alot of aspects that I wont be able to cover all in the comment. If anyone is interested I would be more than happy to share my work :) edit: Time complexity and space complexity of algorithm is O(N) for both. It's an iterative method but takes really few iterations to reach a good enough solution. The error of the algorithm is proportional to the minimum number of the data set / target sum.

[@PejmanMan]

What’s your pivot selection based on?

[@lunarthicclipse8219]

@PejmanMan it's based on solving subsst sum problem for my indices. Like if i have this dataset: [2,6,10,12] And my target is 16. Ill convert my dataset to an indices array, and convert my target to the expected sum of indices that i need. To do so, ill simply divide the target by the total sum, then multiply the ratio by the sum of indices, then round the number. (16 / 30)*10=5.333, by rounding it we get 5. Now i just need to find a subset from my indices set [1,2,3,4] that sums up to 5 which is very easy to do so. I have an algorithm for that. And I can call this algorithm recursively to refine my solution by calculating the difference between my soltuion and the target, then using the algorithm again to minimize the difference.

[@errorite6653]

(Max - min) of the dataset is still gonna be O(2^p(n)), i.e. exponential, so unfortunately it wouldn’t be very efficient for instances with polynomially many bits.

[@lunarthicclipse8219]

@errorite6653 nope, it's O(N) assuming data is sorted. I used it on instances with millions of items and it worked well. I even tried it with over 1000 bits and it worked well. I min max the algorithm using the same algorithm to minimize/max the difference. I let it run for like 100 iterations and usually it will find a good enough solution in less than 10.

[@lunarthicclipse8219]

It doesnt find an exact solution, but it finds good enough solutions with pretty good accuracy and efficiency. Finding an exact one is a huge challenge, doing so will basically solve the np problem. But I dont think it can be solved at the moment.

[@bryanredd4654]

This is by far the best explanation of P=NP I have ever heard. Great work!

[@metachirality]

I think computational complexity theory is one of the most fundamental fields of math!

[@NemisCassander]

Would you say it's at the same fundamental level as category theory? Just curious.

[@tjaron]

I probably would have needed such a video back in my computational complexity class. You did a good job at explaining the P-NP-Problem!

[@PolylogCS]

thanks!

[@JefCollier]

Instant sub. Great explanation and I'm going to steal some of your analogies the next time I'm teaching it.

[@Ozzah]

I didn't catch if you mentioned this in the video or not, but a key feature of the reduction is that the reduction must be achievable in polynomial time. If you can solve NP-complete problems in polynomial time, but your particular problem takes superpolynomial time to reduce, then at the end of the day you are still not able to solve your problem in polynomial time. There are some NP-hard problems that we call "NP-hard in the strong sense", or "strongly NP-hard", where you show that the reduction of the equivalent yes/no problem to a known NP-complete problem can only be done in pseudopolynomial time (polynomial in the magnitude of the inputs, not just the number of the inputs).

[@PolylogCS]

Thanks for mentioning this! This is one of those things that I believe we just mentioned in passing for reducing NP to SAT. we did not have time to develop the general language of reductions at all.

[@cefcephatus]

One thing about breaking cryptography: Because most encryption objects are product of a compressor function, any algorithm that tries to break it must output at least 2 objects. Factoring also output 2 objects at a time: smallest prime number, and multiplier, this is true even with factoring 3 numbers multiplication because recursion is a thing.

[@JoãoPedroFavoretti]

That is a very nice camera angle. Awesome editing

[@alexandersanchez9138]

16:13 >laughs in Church-Turing thesis

[@u2b83]

9:38 "Any algorithm can be represented as a circuit" ...yep, and that's what resnets are - you are effective doing a search of of all possible circuit algorithms for those that recreate the input data most concisely (effectively compressing it).

[@michal3141]

This reminds me of good old days when I wrote my MSc on SAT. My intention was to solve this fascinating problem but it turned out really damn hard so I ended up rediscovering some wheels and playing with satisfiability solvers and SAT encodings of various computational problems.

[@alexengineering3754]

I never thought of logicgates as a list of constrains. This gives me an interesting new perspective. Thank you!

[@xxlvulkann6743]

The way the satisfiability solver is explained at 1:27 in terms of states (or variables) and constraints reminds me of how quantum computers are programmed. I wonder if quantum algorithms allow for solving a significant subset of NP problems, if not NP-complete problems.

[@PolylogCS]

Quantum algorithms can solve only a few very specific problems that are not known to be in P, like factoring or simulating a Quantum system.

[@atrus3823]

I think an often glossed over detail is that NP does not just mean not polynomial, it means nondeterministic polynomial. So, it's not just any hard problem, but a specific way of being hard, namely, that they are solvable in nondeterministic polynomial time.

[@knkootbaoat6759]

17:43 i agree. i never like when youtubers do that

[@rnoro]

Amazing video! Clear and inspiring!

[@mrbutish]

A really important story - the original Genie did not have a limit on the number of wishes - he failed to straighten the dog's tail Thinking that solving the satisfiability problem would make cryptography impossible is a minor consequence not the purpose. The real purpose is no problem would ever be unsolvable in real life. We could just give our desired solution and get the problem solving approach step by step with the immediate inputs (or immediate tasks we have to do to get started). So solving cancer for example would be to encode the output of no cancer or immortality through genetic modification and we would get the path to do exactly that.

[@mrbutish]

From this perspective you can see how p=?np Will the SAT solver really give us a simple polynomial step by step solution. Or would it inherently be an exponential number of steps? Or if you're only interested to find the input(immediate next steps) instead of step by step:- will it require an exponentially large circuit to do so, or will our finite resources like supercomputers suffice?

[@mrbutish]

A rather simple way to view cryptography, we have n bits of seed (n>1000,000). Can you really get the solution despite 1 million random bits of thorough interference? Cause we will hit singularity if it is possible easily. 🙂

[@mrbutish]

Added implicit constraints to the cryptography are the Challenger will have access to two out of three of the input bits(any length), output bits(any length), and the algorithm of thorough interference (with 1 million bits although this can be any length as well - sha256 uses 256 bits for example). Of course having the input and output is a trivial exclusion but only partially. As you can see, it's safe to say cryptography is secure.

[@idonnow2]

This is spot on. This is exactly why metaheuristic algorithms for solving NP hard problems are based on many natural phenomena that arise for solving real world NP hard problems. for instance Evolution is an NP hard problem, as it is not known what genetic permutation will give rise to the most fit biological machine given an ecological system. Science is also an NP hard problem, as it is not known what model can best approximate the real world empirical function. Even memes are an NP hard problem, it is not known what is the "best meme" among all possible conceivable memes. If N=NP then evolution would have developed a perfect specimen generator function, science would be solvable by asking chatgpt, and there would be only a single perfect meme that satisfies everyone.

[@mrbutish]

@@idonnow2 yes i did a course of genetic algorithms 10 years ago. Travelling salesman problem also has many solutions like nearest neighbour, minimum span tree, k-opt, simulated annealing, ant-colony optimization. We need solutions to NP hard. Don't worry about crypto. Default RSA for example uses 2048 or 4k bits - and that is for boring internet traffic. Secrets and confidential information will have a few MB or GiB of seed. Quantum means if they start programming atoms to collect them(1 million quantum atoms for 1 million seed decoding(1 MB seed)) then also we have post quantum crypto algorithms and increased seed size. The focus is not crypto, it is solving the NP hard problem.

[@Aweorih]

Nice video, will definitely check out some others of the channel :) It should be noted though, that modern cpus don't do multiplication this way anymore. They use lookup tables on 4x4 (bit) multiplications and some additional adding logic for bigger numbers. This way it requires only 131kb of storage for fast multiplications. Bigger lookup tables (e.g. 8x8) would require too much storage though

[@binathiessen4920]

Multiplying is Polynomial though. Most simple multiplication algorithms are O(n^2), but the latest versions of the Schönhage-Strassen algorithm have achieved O(n ln(n)) time complexity.

[@MagicGonads]

that's verification of multiplication (the forward direction), and P is in NP, the question is whether NP is in P

[@programmer1379]

Excellent use of visuals to simplify the explanations !!

[@PolylogCS]

Glad you enjoyed it!

[@RobertBlair]

The SAT problem as circuits helps me envision how quantum computing could work. Set up the 50 million qbit circuit and out pops the result where all the qbits allow the solution

[@bastiankraft3108]

This video is an amazing summary of what N = NP is about. I think I will just send a Link to this video next time somebody asks me about it. I simply cant sum it up nearly as well.

[@vampire_catgirl]

It's a good day when polylog uploads

[@Elliott_101]

thanks man, this was very informative!

[@PolylogCS]

Thanks :)

[@ronaldpikksaar2202]

"Like and subscribe" is ok as long as it's at the end of the video. It's like a reminder that if your vid has been interesting throughout then they might be interested in similar content. It's only discusting if people are begging for likes before they have even shown if they have anything to offer or not.

[@bartolhrg7609]

9:37 just wanted to point out: those circuits might be extremely complex, which would mean that SAT might not be enough to solve all problems Also, computer circuits sometimes rely on time (like flip-flops) and/or have loops (input connected to the output) Which is not describeable by CNF logic

[@vaclavrozhon7776]

You might enjoy the blog post where we clarify how to deal with general circuits

[@yash1152]

reallllllly good video. the background color is also pleasant to look at. awesome.

[@JA-zp4qu]

Great video A bit of an oversight, but NP-complete problems are only known to be equivalent under polynomial computible reductions There is some evidence (particularly in fixed parameter tractibility and higher levels of the polynomial heirarchy) that some of these problems are different and easier in some aspects. For example, linear time reductions could exist in only one direction between problems

[@PolylogCS]

Also, very different if you just want to approximate the solution... It's one of many simplifications we had to do for the sake of conciseness.

[@FoggyStillness]

Very nice discussion. Thank you.

[@torquesjr]

Incredible video guys. Keep it up! Also the blogpost is missing from the description 😉

[@PolylogCS]

Thanks! It is now a pinned post, we will add it to description too

[@tanchienhao]

awesome video! but wait im confused, this video seems to suggest factorisation is reducible to circuit SAT and is hence NP-complete, but it's suspected to be NP-intermediate, where did i go wrong?

[@PolylogCS]

Multiplication is also reducible to sat and yet is not np complete. The reduction in the video just shows that sat and not multiplication/factoring is powerful.

[@jenbanim]

"We don't really have good ways of proving a problem can't be solved with a fast equation". This makes sense but immediately makes me curious what tools we do have, where we have found solutions, and what has been tried but failed

[@PolylogCS]

One trick we have is so called diagonalization. And to understand why some tricks cannot work, try googling for relativization, natural proofs, and algebraization.

[@andrewdunbar828]

I'll get back to unscrambling eggs after I watch this video.

[@patrickwienhoft7987]

Well but SAT is just a decision problem and not necessarily constructive. In fact, deciding primality IS in P, so SAT restricted to multiplication circuits with a given output is in P, just actually FINDING the satisfying assignment is complicated.

[@AlfW]

The fact that primality testing is in P without actually getting factors in the No cass is such a weird result of the AKS paper that I never really understood. And after I read your comment I've read up on the AKS result and finally understood! The basis of AKS is Pascal's triangle and not factors. That's so wild.

[@AlfW]

Regarding your comment, it is wrong. You can take any decision problem and call its solution algorithm polynomially often to make a constructive algorithm. Hence, if you have a non-constructive polynomial-time SAT solver, you can build a constructive polynomial-time SAT solver from it. The real issue is that PRIMES is in P, but FACTORIZATION is NP-complete.

[@patrickwienhoft7987]

@@AlfW Ah you're right , good point. SAT being discrete makes this quite easy then to go from decision problem to constructing a solution.

@@AlfW Factorisation ain't known to be NP-complete. In fact, factorisation is both in NP and in co-NP, and it's widely believed that NP != co-NP, and thus no problem in co-NP can be NP-complete.

[@PolylogCS]

We are discussing some aspects of factorization and how to convert deciding SAT to solving SAT in the blog post, it did not fit in the video.

[@finnaerix9837]

The task to evaluate if P=NP could be easily solved if P=NP.

[@Ronnypetson]

That's the coolest thing I've watched in a while

[@PolylogCS]

Thanks!

[@nlysts]

One of the best videos on p VS np I've seen yet

[@PolylogCS]

Thanks :)

[@MrHaggyy]

It always amazes me how relevant and active P = NP remains for decades now. There are a lot of similar dead ends in math, physics and engineering. Hilbert's problem, 3-body problem, turbulance ... But somehow P = NP stuck with people like Schrödinger's cat.

[@NemisCassander]

Putting on my engineer's hat for a moment, I'd say P = NP has stuck because the practical applications of proving it are so large. I'm an Industrial Engineer on the hard side of the field, with primary focus in OR. That discipline would effectively disappear if P = NP, as it's simply a lot of techniques to optimize systems under constraints. Schrodinger's Cat has stayed around because we can't verify whether the radium vial has broken yet. ;) Okay, that was a joke. In all seriousness, though, it's such an arresting image that strikes at the heart of the mortal condition.

[@tomholroyd7519]

I do like the super-resolution tricks using neural operators where they skip the PDE solver and use a DNN. It sort of doesn't matter that it's a hard problem, it's not really solving those equations, just estimating what the solution probably is. And it's right because fluids all look the same after a while ...

[@santiagowu5365]

I think is impossible to reverse every algorithm. Algorithms also has a its equivalent as math functions. Then, if that function is bijective, it has an inverse function.

[@VincentCheng-tc9hr]

polylog is reaching 3b1b-level. the vids just don't miss! great stuff

[@PolylogCS]

Thanks :)

[@elliotn7578]

Correction: Some cryptography would still be possible if P=NP, particularly symmetric ciphers like one-time pads.

[@PolylogCS]

Yeah, it was a slight overstatement, but only slight. If one-time pad is the only survivor, there's not much left. Classical symmetric ciphers would not survive p=np.

[@u2b83]

I've [briefly] played around with applying gradient descent + predictive nets to solve SAT problems but haven't [yet] had success using 5-layer nets and 5 binary variables. I used minibatches of initial guesses to try to make things more continuous. In my version, the initial guess is applied to the net, which then attempts to nudge the solution every iteration, continuously. However, I'm doubtful of this approach since the MSE quickly bottomed out. Here's a few approaches suggestion by Chat - Applying Gradient Descent to SAT (Indirect Methods): While traditional gradient descent isn't directly applicable, there are approaches inspired by gradient descent that have been adapted for SAT and related combinatorial problems: Continuous Relaxation: Idea: Relax the discrete SAT problem into a continuous problem by allowing Boolean variables to take values in the continuous range [0, 1] instead of just {0, 1}. Then, apply gradient descent to optimize in this continuous space. Example: One might formulate a loss function that measures how close a given assignment is to satisfying the formula. However, this approach requires clever design to ensure that the continuous relaxation remains meaningful and can be mapped back to a valid discrete solution. Neural Networks and Differentiable SAT Solvers: Idea: Recent work has focused on using neural networks to approximate SAT solvers. By embedding the problem into a neural network, gradient descent can be used to train the network to predict satisfying assignments. For example, SATNet is a differentiable layer that can be integrated into neural networks, allowing gradient-based learning on SAT problems. Energy-Based Models: Idea: Another approach is to model the SAT problem as an energy minimization problem, where low-energy states correspond to satisfying assignments. Gradient descent (or variants like simulated annealing) can be used to find these low-energy states. Although this isn't traditional gradient descent, it's conceptually related in that it seeks to minimize an objective.

[@badabing3391]

would sat allow us to recover the training data from a neural network by reading the weights that are available and the algorithm used to set those weights

It might allow you to recover some possible training data. In general, there are more possible training data than there are different weights for your neural network. (Simply put: the training data takes more bits to store than the network.) Training a network is a 'lossy' compression.

[@PolylogCS]

@badabing3391 Fast SAT solver would enable you to find optimal neural-network weights for given training data. Keeping in mind issues like overfitting, it would essentially solve technical aspects of how to train neural networks. Of course, you can argue that in practice, the backpropagation algorithm is solving these technical aspects rather well, but probably not nearly as good as what is possible.

[@NemisCassander]

An interesting question, but something to keep in mind is that a lot of current applications for NNs is in the area of optimization or classification, which P = NP would obviate.

@@NemisCassander Only if you could solve those problems efficiently. Technically, you could have P=NP, but your best SAT solving algorithm could still be O(N^2000).

[@PolylogCS]

N^2000 could for sure happen but as we discuss in some other comment thread, most polynomial-time algorithms are in fact also efficient in practice.

[@obriketimothy5914]

What of using an abstract algebra approach? By converting algorithmic statements into mathematical substructures and playing with their Galois representations is it possible to show that an algorithm can or cannot exist?

[@PolylogCS]

There is an algebraic approach called geometric complexity theory, you might enjoy p vs np survey by aaronson

[@obriketimothy5914]

@@PolylogCS oh, that seems nice

[@PeterJnicol]

This was great. Really great.

[@PolylogCS]

Thanks :)

[@philipoakley5498]

Isn't this (directionality question) a 'variant' of the direction of time problem in physics with respect to the 'just declare a law' comment at ~17:00. In some way it maps (and hence highlights omissions) in the physics vs computing science laws (logic vs observation)

[@bartolhrg7609]

I believe that quantum computing is fast SAT solver, because they can compute function at the same time for both x=0 and x=1

[@yigitpolat]

how do we encode loops with unknown number of iterations as feed-forward circuits?

[@PolylogCS]

I discuss these loops a bit in the blog post. Let me know if it does not make sense

[@hamster-is2ij]

very interesting video. i find the idea that you told us very interesting

[@johnjones8330]

I still prefer the interpretation that P is the problems solvable in P and NP is the problems that can be verified in P.

[@PolylogCS]

That is fair point, there is a reason why most people go with that interpretation! I think both interpretations are valuable and the best is to understand why they are equivalent.

[@yanntal954]

Great video as always, thanks!

[@PolylogCS]

Thanks :)

[@thomasmeslin8399]

Really nice explanation !

[@exponentmantissa5598]

For an arbitrarily large general SAT solver would Godels theorem not come into play? If Np is infinite and the SAT solver is complete then it will generate inconsistencies and vice versa.

[@PolylogCS]

I don't think there is so close connection, except for the fact that the vibes of the two problems are very similar, p!=NP is kind of like efficiency version of incompleteness theorem

[@NemisCassander]

It's a good question. My personal take is that P = NP is something that Godel's theorem hides from us. Or, put another way, IF P = NP, then this is something that is true that we can't prove.

[@PolylogCS]

@@NemisCassander but if P!=NP? Do you think there would be a "normal" proof of that fact?

[@CheaterCodes]

Very good video, super insightful. However, hashing would not be broken. At least, not completely. Hashing is not just a one-way-function, there are also multiple possible inputs for a given hash. There's still practical problems arising from this: For example, authentication relies on it being difficult to generate a new input with the same hash, which becomes trivial.

[@PolylogCS]

This is good point! There are several interpretations of what it means to "break hashing". Even finding two arbitrary inputs that map to the same output can be considered a weak form of breaking hashing and that would be simple if p=np. As you say, if p=np it is still not trivial to break hashing in the strongest sense of finding the original input to the jak function, but there are ways that would probably work quite well. For example, if you code a program that tries to recognize whether a given input looks like a file, you could invert this algorithm and solve the problem "among all inputs hashing to this output, which one looks the most like a file according to this program"

[@CheaterCodes]

The good news is that there are still infinitely many perfectly valid files that map to a single hash. However if you have any information about the original file (length, first word) breaking it becomes quite reasonable. I suppose that's also how you could break any encryption, assuming you know the inner workings.

[@PolylogCS]

@@CheaterCodes Exactly!

[@JeremyHelm]

1:53 to know (what's true or false) in a particular (hypothesis?)… You've got to roll back a formal statement of all the rules you know … causality follows(?) 1:56 or maybe there's no solution

[@octo-lab-314]

I have a question, I know it quite dumb, but I would like to know any possibility to this. Instead of answering P vs NP, what if the question turns into "What is the possibility for a problem to be in P and NP?". My wonder falls into on what possible aspects for a problem to be both in P and NP, or not in either of them.

[@maysaraaljumaily]

Fantastic video! I kindly ask how did you manage to animate the amber-coloured lines at 6:08. I don't know how to make the colour transition from the beginning of the line to the end.

[@PolylogCS]

I think we just create new line on top of it. Check out our github for details!

[@maysaraaljumaily]

@@PolylogCS Thank you for the kind reply! Keep up the good work!!

[@ArtificialDjDAGX]

I mean, lossy compression algorithms can't be reversed so as to get back lossless data formats. Don't know if that's even something under the purview of P=NP, though.

[@wanfuse]

question if one could devise a sort algorithm, that is fully reversible that is reversible each step knowing only the final output, does that mean one has a solution to this set of problems?

[@charlesmartin1972]

So, running long multiplication on a set of logic gates equivalent to classical Boolean algebra loses information at every gate that is not an inverter, so finding a polynomial-time SAT function in that context seems quite difficult; however, suppose one implemented long multiplication on a set of Toffoli gates, which don't lose information because number of inputs = number of outputs?

[@PolylogCS]

That would not change much - i will try to add a section to the blog post

[@ryansheehy8444]

I feel that because logic gates are irreversible and lose information, and since it takes time to reconstruct that information, certain algorithms implemented with logic gates must also be irreversible (taking more time in one direction than the other).

[@vinniepeterss]

superb!

[@davecorry7723]

Excellent!

[@cinnamonroll5615]

in some sense, this looks quite similar to quantum mechanics, where the state of the gate is in some combinations of those two values or four with some gates

[@ch1n3du3]

Thank you for another amazing video

[@PolylogCS]

Thanks :)

[@caiocouto3450]

What's your monitor? It really caught my attention

[@xatario]

You are so god bro!

[@abstractalgo]

what a great video, thank you

[@PolylogCS]

Glad you enjoyed it!

[@userou-ig1ze]

So just to confirm, a giant fpga built specifically to solve for rsa or any hash algorithm would be impractical? Would it be for a nation too? That part/scope I haven't quite grasped, after the video my intuition says it would be impossible

[@PolylogCS]

Specialized hardware cannot make exponential time algorithm polynomial time. In other words, speeding up a problem that would require 10^100 years to be solved in 10^90 years is not enough to make a problem solvable.

[@immanuelkant202]

awesome vid, keep it up!

[@Pedritox0953]

Great video!

[@PolylogCS]

Thanks!

[@mttiii]

Technically, solving a SAT instance only gives you a single bit (satisfiable / not satisfiable). It doesn’t give you the variable values, right? For breaking, RSA, however, you would actually need to know the factors.

[@PolylogCS]

Good point! We are discussing these issues in the blog post.

[@j7gy8b]

Outstanding presentation and... is that LaTeX?

[@PolylogCS]

Thanks :) yes, we use Manim that supports latex

[@udaykiran2427]

I just finished my Algorithms end sem exam, and this is in my recommendations

[@GoldbergToastyBred]

Nice video and much better haircut :)

[@bobspianosbffl]

edit: The blog is up now

[@PolylogCS]

it's linked now