Why cryptography is not based on NP-complete problems
(blintzbase.com)
Cryptography is not based on NP-complete problems - let me explain why.
Cryptography is not based on NP-complete problems - let me explain why.
P vs. NP Explained (2014)
(danielmiessler.com)
If you spend time in or around the programming community you probably hear the term "P versus NP" rather frequently. Unfortunately, even many with formal computer science training have a weak understanding of the concept.
If you spend time in or around the programming community you probably hear the term "P versus NP" rather frequently. Unfortunately, even many with formal computer science training have a weak understanding of the concept.
Tokenisation Is NP-Complete
(arxiv.org)
In this work, we prove the NP-completeness of two variants of tokenisation, defined as the problem of compressing a dataset to at most $\delta$ symbols by either finding a vocabulary directly (direct tokenisation), or selecting a sequence of merge operations (bottom-up tokenisation).
In this work, we prove the NP-completeness of two variants of tokenisation, defined as the problem of compressing a dataset to at most $\delta$ symbols by either finding a vocabulary directly (direct tokenisation), or selecting a sequence of merge operations (bottom-up tokenisation).
Ask HN: New Resources for Learning Complexity Theory
(ycombinator.com)
A few years ago in 2021, I put together a guide to resources for learning computational complexity theory at the graduate level [0].
A few years ago in 2021, I put together a guide to resources for learning computational complexity theory at the graduate level [0].
Steven Rudich (1961-2024)
(computationalcomplexity.org)
Complexity theorist Steven Rudich passed away on October 29 at the age of 63.
Complexity theorist Steven Rudich passed away on October 29 at the age of 63.
What P vs. NP is about
(wordpress.com)
We recently made a Polylog video about the P vs NP problem. As usual, our goal was to present an underrated topic in a broadly understandable way, while being slightly imprecise and leaving out the messy technical details. This post is where I explain those details so that I can sleep well at night.
We recently made a Polylog video about the P vs NP problem. As usual, our goal was to present an underrated topic in a broadly understandable way, while being slightly imprecise and leaving out the messy technical details. This post is where I explain those details so that I can sleep well at night.