Из Википедии :
Тип вычислительной проблемы: Наиболее часто используемые проблемы - это проблемы с решением . Однако классы сложности могут быть определены на основе функциональных проблем, проблем с подсчетом, оптимизационных задач, проблем с обещаниями и т. Д.
Я также видел, что определения NP-complete, NP-hard, NP, ..., определены только для решения проблем. Интересно, почему это так?
Это потому, что любая другая проблема может быть эквивалентно преобразована в проблему решения?
Есть, вероятно, много разных способов ответить на этот вопрос, однако одним из ключевых элементов является исторический прецедент. опровержение Тьюрингом алгоритма решения проблемы остановки в 1936 году использует проблему остановки как решение проблемы. это , в свою очередь основано на (и решен отрицательно) Hilberts проблема разрешения (1928) , который просил для систематического метода определения истинности или ложности какого - либо хорошо сформированной математической постановки т.е. также проблемы принятия решений.
это, в свою очередь, имеет некоторое сходство с 10-й проблемой Гильбертса, датируемой 1900 годом, которая требует решения целочисленных диофантовых уравнений (многие из его 23 краевых / центральных исследовательских задач были сформулированы как проблемы решения). Тем не менее, обратите внимание, что проблема Entscheidungs уходит корнями в гораздо более раннюю концепцию Лейбница, как гласит Википедия:
Также обратите внимание, что диофантовы уравнения датируются греками, которые были одними из первых, кто рассмотрел, изучил и подчеркнул важность математического доказательства. Есть по крайней мере две важные проблемы из теории чисел, которые до сих пор не решены во многих современных исследованиях из-за греков: существование бесконечных простых чисел-близнецов и существование нечетных совершенных чисел .
Отметим, что некоторые «проблемы решения» (то есть в форме поиска доказательств, чтобы открыть математические гипотезы) буквально заняли сотни лет, чтобы решить, например, последнюю теорему Фермаса , более 3,5 века, также в теории чисел.
таким образом, проблемы решения очень стары, но даже если их просто сформулировать, они могут быть чрезвычайно трудными и, по сути, коренятся в вопросе «является ли это утверждение истинным или ложным» относительно существования доказательств (доказательств). в основе его основная математическая концепция. более того, он продолжает появляться в современных местах фундаментальным и напоминающим образом, таким как вопрос P vs NP (~ 1971), где класс NP может быть определен / сформулирован с точки зрения остановки машины NP и решения проблемы выполнимости за время P ,
источник