Помогите понять ч.1

[z0ic]

1. Проблема Кука (сформулирована в 1971 г.)
Допустим, находясь в большой компании, вы хотите убедиться, что там же находится ваш знакомый. Если вам скажут, что он сидит в углу, то вам достаточно доли секунды, чтобы, бросив взгляд, убедиться в истинности информации. В отсутствие этой информации вы будете вынуждены обойти всю комнату, рассматривая гостей. Это говорит о том, что решение какой-либо задачи часто занимает больше времени, чем проверка правильности решения.
проблема: может ли проверка правильности решения задачи быть более длительной, чем само получение решения, независимо от алгоритма проверки.
===================================================
А что если решение написано на непонятном мне языке ?

[svv]

z0ic в сообщении #531306 писал(а):

А что если решение написано на непонятном мне языке ?

А если я такой дебил, что для меня проверка готового решения -- непосильный труд, так как я даже не понимаю, чего от меня хотят, -- то, выходит, я своим существованием опровергаю гипотезу P=NP?

[Circiter]

2z0ic

Цитата:

может ли проверка правильности решения задачи быть более длительной, чем само получение решения, независимо от алгоритма проверки.

Не совсем понял оговорку "независимо от алгоритма проверки". Просто если это черный ящик, то он же может быть и оракулом, который все знает... :)

Вообще, над вашим вопросом стоит подумать. Скажем, на бытовом уровне ответ конечно же положителен. Например в программисткой практике поддержка унаследованного кода может оказаться непосильной задачей -- проще переписать все с нуля. :) То есть, зачастую, проверка может автоматически подразумевать, фактически, полную реконструкцию всего пути получения такого решения плюс поправки на копание в чужих мыслях (похоже на ваше "А что если решение написано на непонятном мне языке").

Думаю, можно и более формальные примеры попробовать привести... Что если у нас есть алгоритм получения одного решения, а для проверки никакого специализированного алгоритма нет; очевидно, что в этом случае для проверки придется последовательно запускать алгоритм генерации очередного решения и сравнивать результат его работы с проверяемыми данными вплоть до совпадения (а что если возможых решений бесконечно много?)...

-- Чт янв 26, 2012 08:56:29 --

Кажется, вам надо как-то уточнить вопрос, ибо вы пытаетесь сравнить несравнимое, а именно распознавание (например, образа) с генерацией (этого образа). Иногда одно бывает сложнее другого, иногда наоборот.

[z0ic]

2Circiter: Большое спасибо. Эта формулировка задачи просто ужасна. Как только её могли поместить в учебник по теории алгоритмов.

[svv]

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

[Circiter]

2z0ic

Цитата:

Эта формулировка задачи просто ужасна. Как только её могли поместить в учебник по теории алгоритмов.

Но если вы её разгрызете, то сможете недурно заработать.

Также посмотрите как о сабже пишет сам Кук.

[bin]

ИМХО при такой формулировке задачи (см. первый пост) неверное решение - это тоже решение. Т.е. множество всех возможных решений состоит из двух непересекающихся подмножеств: верные решения и неверные решения. Если так, то ответ "да". Например, можно очень быстро сгенерировать решение генератором случайных чисел, а проверка, что это решение верное, будет гораздо труднее (по теоретической оценке). Так, для канонической нумерации вершин графа достаточно максимизировать (или минимизировать) его матрицу смежности. Т.е. берем любую перестановку (можем взять и исходную матрицу, предположив, что она минимальна) и получаем решение, а проверка потребует полного перебора.