
Researchers Identify 'Master Problem' Underlying All Cryptography
The Quanta Podcast
00:00
Computable Komogorov Complexity
There's no programme that can calculate the complexity of every possible string. We know this because if there were such a programme, we'd end up with a contradiction. If we forbid such slow programmes, we end up with time bounded komogoro complexity. This version of komogorov complexity is computable at least in principle. In some ways, it's as natural a concept as the original comogor of complexity.
Transcript
Play full episode