-
@ Juraj
2025-05-22 12:22:09
In the 1980s, behind the Iron Curtain, the countries of the Eastern Bloc organized their economies through Council for Mutual Economic Assistance, dividing production tasks among member states. Computers and their parts were no exception. Bulgaria received the assignment to produce computer hard drives—leading to the construction of a brand-new factory right beside a cow farm. The factory quickly earned a reputation across Eastern Europe: its hard drives were notoriously unpredictable, sensitive even to the temperature shifts inside the room.
Around this time, at Comenius University in Bratislava, a young Slovak student named Róbert Szelepcsényi found himself tasked with writing software drivers for these very Bulgarian drives. Each time he tried reading the first sector of data, the faulty hardware might land the magnetic head unpredictably—on the correct sector, or perhaps one or two sectors off. Instead of giving up, Szelepcsényi devised an elegant workaround: every time his software started, it first read a special marker from wherever the drive’s head landed, determining its actual position. It then corrected the offset accordingly, allowing the rest of the system to behave as if the drive had been reliable all along.
Years later, this practical experience provided Szelepcsényi with an insight he brought into theoretical computer science, inspiring a groundbreaking proof known today as the Immerman–Szelepcsényi theorem. This proof solved a longstanding puzzle: whether problems solvable nondeterministically (by guessing solutions and verifying them using limited memory) could also solve their complementary problems—the problems where "yes" and "no" answers are swapped—in the same constrained memory space. Szelepcsényi’s insight echoed his driver technique: even if a computation didn't immediately know its exact situation, it could nondeterministically "guess" a state and then methodically verify correctness by systematic checking and counting. Just as he had once turned faulty hardware into something reliable, he demonstrated how seemingly limited computational models could systematically verify their complements
https://en.wikipedia.org/wiki/Immerman%E2%80%93Szelepcs%C3%A9nyi_theorem