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.
Feb 5·edited Feb 5Liked by Alejandro Piad Morffis
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
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.
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.
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.
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.
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!
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
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.
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 :)
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.
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.