Quanta Magazine (США): программисты расширяют рубежи поддающихся проверке знаний

Представьте себе: к вам приходит человек и говорит, что у него есть прорицатель, и что этот прорицатель может раскрыть непостижимые тайны вселенной. Вы заинтригованы, но вряд ли ему поверите. Вы обязательно захотите убедиться в том, что прорицатель говорит правду, и для этого вам нужен будет какой-то способ или метод.

В этом суть одной из главных проблем компьютерных наук. Некоторые задачи слишком трудно решить в разумные сроки. Но их решение легко проверить. По этой причине ученые, работающие в области теории вычислительных систем, хотят знать: насколько сложной может быть задача, имеющая решение, которое поддается проверке?

Оказывается, ответ таков: она может быть невероятно сложной.

В апреле два ученых-программист...