вторник, 26 января 2021 г.

Проблема Кука

Проблема Кука (сформулирована в 1971 году) Область: математическая логика и кибернетика Ее еще называют "Равенство классов P и NP", и она является одной из наиболее важных задач теории алгоритмов, логики и информатики. Может ли процесс проверки правильности решения какой-либо задачи длиться дольше, чем время, затраченное на само решение этой задачи (независимо от алгоритма проверки)? На решение одной и той же задачи, порой, нужно разное количество времени, если изменить условия и алгоритмы. К примеру: в большой компании вы ищете знакомого. Если вы знаете, что он сидит в углу или за столиком - то вам понадобится доли секунд, чтобы его увидеть. Но если вы не будете знать точно, где находится объект, то затратите больше времени на его поиски, обходя всех гостей. Основным вопросом является: все или не все задачи, которые можно легко и быстро проверить, можно также легко и быстро решить? Что такое решение? Это одновременно вопрос и ответ. Что такое ответ? Это результат математических действий или озарение - по наитию отечающие на вопрос. Проверка правильности решения? Доказательство соотвествия ответа вопросу. Что такое легко и быстро проверить, легко и быстро решить? Это необъяснимо. Термин (легко) каждый понимает по своему. Значит основным вопросом является, все или не все задачи которые можно проверить, можно решить? Проверка правильности решения какой либо задачи, может ли длиться дольше, чем время затраченное на само решение этой задачи? Да может. Ответ на вопрос и ответ о правильности ответа на вопрос это две разные задачи. И они естественно для решения потребуют разные интервалы времени. Кроме ответа по озарению по наитию, потому что в этом случае ответа на вопрос полученного в результате математических действий вообще не существовало. Время для решения задач с ответами по озарению по наитию не определено. Такие задачи можно вообще не решить в реальное время для одного человека. Равенство классов P и NP в таком случае неверно.

Комментариев нет:

Отправить комментарий