Poznámky k epizodě
Some computer problems become brutally harder as they grow. The Exponential Time Hypothesis proposed that this explosion was unavoidable for a central logic problem called 3-SAT. OpenAI’s new result overturns that assumption with an algorithm that counts the solutions to fixed-width Boolean formulas in subexponential time, using polynomial space. We unpack what those words mean, why counting solutions also lets a computer decide whether one exists, and how the result reaches problems involvi...
