The most important theoretical question in Computer Science asks about the existence of truly hard problems, that can't be solved efficiently regardless of how powerful is your tech.
This explanation is amazing! It will be my go-to recommendation for anyone looking to start learning about this. Personally, I gave it a try and initially switched to P vs PSPACE because it intrigued me. Although I haven't given up, my focus has shifted to more important things. I don't want to burn myself out on a problem that might remain unsolved for over 50 years.
Based on my experience, here's a list of topics I'm personally interested in reading from you over the next years. I also believe some could be included in this discussion or a future one, or even in a book.
1-) A fantastic future article could delve into Memory. While P and NP focus on time, memory is equally crucial. Exploring the contrast in memory since PSPACE = NPSPACE, even if the proof is challenging, could be insightful. It might be interesting to understand why this proof can't be applied to P and NP.
2-) Discuss the balance between memory and time. The difficulty in proving P vs NP and P vs PSPACE lies in limiting algorithm capabilities when more memory can be added. Classic algorithms often show that higher memory bounds lead to lower time bounds. However, the question remains: can problems like PSPACE-Complete problems be solved in polynomial time, regardless of how much polynomial memory is given to them?
It's interesting to draw parallels with the current challenge we face with LLMs. Despite providing them more memory and time for training, we don't know if, no matter how much we give them, they'll reach the pinnacle of AGI or acquire emergent abilities we're not aware of yet. It feels like we're encountering the same problem repeatedly :)
3-) And in the future when those exist then it could be good definitely to see discussions about the Hierarchy Theorems and their implications and once more why that proof is not applicable to P and NP because of the relativization.
4-) Finally, show a problem that we are actually certain is intractable no matter what we do because it belongs to EXPSPACE the EQ_REX problem: Two regular expressions are equivalent with exponentiation. In theory no matter how much we advance with AI an AGI cannot solve fast and efficiently this problem if is using classic computation to solve it of course.
I have many topics in mind but we can discuss it in the future this message is too long already hehehehe.
Alejandro this was just excellent! Quick question - what is the implication of p=np for cryptography, where answers are easy to verify, but computation is hard? thinking of the current prime-based cryptographic codes, but also quantum cryptography I suppose
Great question! If p = np then of course cryptography at least in it's current classical form is solvable, there are no one way functions.
Now, if p != np, there must exist problems that are not polynomially solvable but are neither np-complete. We might never know what those problems are but prime factorization is a good candidate.
Also, you writing in public is very inspiring. A tad intimidating how "clean" your chapters are... I was hoping for a little more "work in progress" type of reading, so I can feel better about myself.
Thanks! And to be fair, these aren't exactly first drafts, they already have a couple of passes before I publish them, but they still need a lot of work to make them book-worthy. Is this kind of feedback exactly what I like to do this in public, it gives me a lot of validation. Thanks for that.
Nice maybe I would add : very simple looking, and mundane, problems are NP-complete. Typically optimisation ones (making timetables, backpack optimization etc.).
On the flip side if P=NP it is not possible to make secure hash functions...Hence the whole crypto idea (at least in the form of Bitcoin like) is impossible. It also shows that even crypto bros who claim that they trust the science are actual believers...if nothing else they believe that P!=NP :)
Would you say that P vs NP is sort of the crux of whether we can accomplish AGI? Is it the central question? Problems that are hard to solve (but solvable) abound in what we humans can do. If I'm way off on this, please feel free to scold and explain! I appreciate how accessible this conversation is.
Thanks, man, you always nail it with the questions. I think AGI is totally achievable whether P = NP or not. AGI is just AI that is as good as the best humans at almost everything that's worth doing.
What I wonder about is if P != NP, does that mean we can't have super intelligence? Of the sort that AI doomers worry could wipe us all out in a blink?
The reason why I think this may be the case --that P not equal NP might preclude superAI-- is because most important problems are NP-hard, so if those are fundamentally unsolvable, then no matter how smart an AI gets, it won't magically find a way to, e.g., solve protein folding or optimal circuit design or any number of other super hard problems. It can't be that much better than us.
Good point. We're not after something that can do everything; we're after something that does the things we do better than we do.
Bit of a tangent here, but not too far of one: do you think the "economically valuable" or "economically viable" concept does a good job of representing "almost everything that's worth doing" vis a vis AGI? I've heard this argument made, and I can't come up with a better definition myself.
I guess is as good an arbitrary milestone as anything. The thing is, "all things worth doing" is way too subjective because who can claim that something super useless isn't worth it for you? So I guess this is like a way to define "worth doing" is more objective terms, as in, something that people would pay you for doing.
I've been pretty obsessed with economics for a few years now. I'm making up for a childhood deficiency and a young adult revulsion! It's fascinating stuff, though.
Realizing that the "traveling salesman" is infinitely more complex than "shortest path" was definitely an "Aha" moment for me. I inadvertently pondered about this as I was watching a live tracker for a package delivery (and how many stops it had before our house). I always figured they had this down to a precise science and had it fully solved. Never did it occur to me that they're likely just doing their best to approximate a "good enough" path within the given constraints.
Yeah, good enough is often... good enough, and we currently have pretty good approximate algorithms, especially for euclidean graphs (where edge costs are distances, like in maps) because those graphs are planar and edge costs follow the triangle inequality so you have some constrains that make heuristic search faster. However, for the general case TSP, we can prove that even finding a good approximation is NP-Hard.
I'll go ahead and use a "helpful" inverse-mnemonic device to remind my self that "NP" may sound like "no problem!" but is actually the unsolved type of problem. Wait...am I making this even more confusing? Ah well.
Most students fall into the trap and call it non-polynomial because NP also means we *believe* there aren't polynomial algorithms for them. So I always have to correct them, it's actually non-deterministic polynomial, which means that there *are* polynomial algorithms but only if you have non-deterministic computers (which are an abstract magical computer model)
Wow this is a really well written article and a far better introduction to P vs NP and complexity than what my university course had.
Thanks 😁 those are really kind words
This explanation is amazing! It will be my go-to recommendation for anyone looking to start learning about this. Personally, I gave it a try and initially switched to P vs PSPACE because it intrigued me. Although I haven't given up, my focus has shifted to more important things. I don't want to burn myself out on a problem that might remain unsolved for over 50 years.
Based on my experience, here's a list of topics I'm personally interested in reading from you over the next years. I also believe some could be included in this discussion or a future one, or even in a book.
1-) A fantastic future article could delve into Memory. While P and NP focus on time, memory is equally crucial. Exploring the contrast in memory since PSPACE = NPSPACE, even if the proof is challenging, could be insightful. It might be interesting to understand why this proof can't be applied to P and NP.
2-) Discuss the balance between memory and time. The difficulty in proving P vs NP and P vs PSPACE lies in limiting algorithm capabilities when more memory can be added. Classic algorithms often show that higher memory bounds lead to lower time bounds. However, the question remains: can problems like PSPACE-Complete problems be solved in polynomial time, regardless of how much polynomial memory is given to them?
It's interesting to draw parallels with the current challenge we face with LLMs. Despite providing them more memory and time for training, we don't know if, no matter how much we give them, they'll reach the pinnacle of AGI or acquire emergent abilities we're not aware of yet. It feels like we're encountering the same problem repeatedly :)
3-) And in the future when those exist then it could be good definitely to see discussions about the Hierarchy Theorems and their implications and once more why that proof is not applicable to P and NP because of the relativization.
4-) Finally, show a problem that we are actually certain is intractable no matter what we do because it belongs to EXPSPACE the EQ_REX problem: Two regular expressions are equivalent with exponentiation. In theory no matter how much we advance with AI an AGI cannot solve fast and efficiently this problem if is using classic computation to solve it of course.
I have many topics in mind but we can discuss it in the future this message is too long already hehehehe.
Thanks again for the enlightening discussion!
Do you want to collaborate with me on that first article exploring pspace vs npspace?
Sure it will be me my pleasure. And, yes mid semester is great for me. Thank you!
🔥🔥🔥
Not immediately but for mid semester maybe...
Alejandro this was just excellent! Quick question - what is the implication of p=np for cryptography, where answers are easy to verify, but computation is hard? thinking of the current prime-based cryptographic codes, but also quantum cryptography I suppose
Great question! If p = np then of course cryptography at least in it's current classical form is solvable, there are no one way functions.
Now, if p != np, there must exist problems that are not polynomially solvable but are neither np-complete. We might never know what those problems are but prime factorization is a good candidate.
So, In a sensible universe, cryptography is safe.
Cool! Thanks for the insight :)
Also, you writing in public is very inspiring. A tad intimidating how "clean" your chapters are... I was hoping for a little more "work in progress" type of reading, so I can feel better about myself.
Thanks! And to be fair, these aren't exactly first drafts, they already have a couple of passes before I publish them, but they still need a lot of work to make them book-worthy. Is this kind of feedback exactly what I like to do this in public, it gives me a lot of validation. Thanks for that.
What a great conclusion.... man, you give us hope.
Nice maybe I would add : very simple looking, and mundane, problems are NP-complete. Typically optimisation ones (making timetables, backpack optimization etc.).
On the flip side if P=NP it is not possible to make secure hash functions...Hence the whole crypto idea (at least in the form of Bitcoin like) is impossible. It also shows that even crypto bros who claim that they trust the science are actual believers...if nothing else they believe that P!=NP :)
Oh yeah, the implications of P=NP would be wild! I definitely have to go over that in my book, thanks for the comment ;)
I'm just gonna go ahead and say it:
NP should be the easiest problems.
No Problem! Piece of cake! NP!
Would you say that P vs NP is sort of the crux of whether we can accomplish AGI? Is it the central question? Problems that are hard to solve (but solvable) abound in what we humans can do. If I'm way off on this, please feel free to scold and explain! I appreciate how accessible this conversation is.
Thanks, man, you always nail it with the questions. I think AGI is totally achievable whether P = NP or not. AGI is just AI that is as good as the best humans at almost everything that's worth doing.
What I wonder about is if P != NP, does that mean we can't have super intelligence? Of the sort that AI doomers worry could wipe us all out in a blink?
The reason why I think this may be the case --that P not equal NP might preclude superAI-- is because most important problems are NP-hard, so if those are fundamentally unsolvable, then no matter how smart an AI gets, it won't magically find a way to, e.g., solve protein folding or optimal circuit design or any number of other super hard problems. It can't be that much better than us.
Good point. We're not after something that can do everything; we're after something that does the things we do better than we do.
Bit of a tangent here, but not too far of one: do you think the "economically valuable" or "economically viable" concept does a good job of representing "almost everything that's worth doing" vis a vis AGI? I've heard this argument made, and I can't come up with a better definition myself.
I guess is as good an arbitrary milestone as anything. The thing is, "all things worth doing" is way too subjective because who can claim that something super useless isn't worth it for you? So I guess this is like a way to define "worth doing" is more objective terms, as in, something that people would pay you for doing.
Yeah... not entirely satisfactory, but probably the best we can do (kinda like the study of economics itself).
Haha hope there are no economists reading...
I've been pretty obsessed with economics for a few years now. I'm making up for a childhood deficiency and a young adult revulsion! It's fascinating stuff, though.
Realizing that the "traveling salesman" is infinitely more complex than "shortest path" was definitely an "Aha" moment for me. I inadvertently pondered about this as I was watching a live tracker for a package delivery (and how many stops it had before our house). I always figured they had this down to a precise science and had it fully solved. Never did it occur to me that they're likely just doing their best to approximate a "good enough" path within the given constraints.
Yeah, good enough is often... good enough, and we currently have pretty good approximate algorithms, especially for euclidean graphs (where edge costs are distances, like in maps) because those graphs are planar and edge costs follow the triangle inequality so you have some constrains that make heuristic search faster. However, for the general case TSP, we can prove that even finding a good approximation is NP-Hard.
I'll go ahead and use a "helpful" inverse-mnemonic device to remind my self that "NP" may sound like "no problem!" but is actually the unsolved type of problem. Wait...am I making this even more confusing? Ah well.
Most students fall into the trap and call it non-polynomial because NP also means we *believe* there aren't polynomial algorithms for them. So I always have to correct them, it's actually non-deterministic polynomial, which means that there *are* polynomial algorithms but only if you have non-deterministic computers (which are an abstract magical computer model)