Предполагается, что из доказательства можно будет извлечь конкретный алгоритм (то есть, что оно будет "конструктивным"), или хотя бы что оно даст намек на то, как этот алгоритм искать.
Хотя, конечно, в математике бывают существенно неконструктивные доказательства. Обычно они так или иначе полагаются на аксиому выбора.
Вообще говоря это может означать то, что есть какой-то алгоритм, который на практике решает SAT за полиномиальное время, но про который нельзя доказать, что он работает во всех случаях.
Существует точный алгоритм, который на любом графе находит оптимальное решение за O(2^n * n^2), что гораздо быстрее, чем обычный перебор, работающий за O(n! * n). В каком-то смысле он динамический, а не переборный.
Если кратко, суть в том, чтобы для создать таблицу, в которой для произвольной пары из некоторого подмножества вершин (маски) и отдельной вершины v хранилась бы длина кратчайшего пути, проходящего через эти вершины и заканчивающегося в вершине v. Эту таблицу можно заполнять итеративно, постепенно переходя к более большим подмножествам вершин. В конечном итоге, так как оптимальный путь в какой-то вершине заканчивается, мы можем перебрать эту вершину и посмотреть на минимум из чисел, записанных в таблице для этой вершины и всего множества вершин в качестве посещенных.
Если нужно узнать не только длину кратчайшего пути, но и восстановить сам путь, то это тоже можно сделать по таблице стандартным для динамического программирования методом.
Предполагается, что из доказательства можно будет извлечь конкретный алгоритм (то есть, что оно будет "конструктивным"), или хотя бы что оно даст намек на то, как этот алгоритм искать.
Хотя, конечно, в математике бывают существенно неконструктивные доказательства. Обычно они так или иначе полагаются на аксиому выбора.
Вообще говоря это может означать то, что есть какой-то алгоритм, который на практике решает SAT за полиномиальное время, но про который нельзя доказать, что он работает во всех случаях.
Если кратко, суть в том, чтобы для создать таблицу, в которой для произвольной пары из некоторого подмножества вершин (маски) и отдельной вершины v хранилась бы длина кратчайшего пути, проходящего через эти вершины и заканчивающегося в вершине v. Эту таблицу можно заполнять итеративно, постепенно переходя к более большим подмножествам вершин. В конечном итоге, так как оптимальный путь в какой-то вершине заканчивается, мы можем перебрать эту вершину и посмотреть на минимум из чисел, записанных в таблице для этой вершины и всего множества вершин в качестве посещенных.
Если нужно узнать не только длину кратчайшего пути, но и восстановить сам путь, то это тоже можно сделать по таблице стандартным для динамического программирования методом.