The Quanta Podcast cover image

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

The AI-powered Podcast Player

Save insights by tapping your headphones, chat with episodes, discover the best highlights - and more!
App store bannerPlay store banner
Get the app