One-Way Computable Transformations - The Barmalias-Zhang Example

One-Way Computable Transformations - The Barmalias-Zhang Example

Explore a detailed Kolmogorov seminar lecture examining the Barmalias-Zhang example of "one-way" computable transformation, which provides an answer to Levin's question in computational complexity theory. Delivered by Alexander Kozachinskiy, this 91-minute talk delves into fundamental concepts of computational and descriptional complexity, continuing the academic tradition established by Kolmogorov in 1979.