Следующий вопрос использует идеи из криптографии, примененные к теории сложности. Тем не менее, это чисто теоретический вопрос сложности, и для его ответа не требуется никаких криптовалют. Я намеренно пишу этот вопрос очень неформально. В отсутствие подробностей, это, возможно, указано немного...
Зафиксируем NP-полную задачу поиска, например форму поиска SAT. Поиск Левина предоставляет алгоритм L для решения X, который в некотором смысле является оптимальным. В частности, алгоритм таков: «Выполните все возможные программы P в соответствии друг с другом на входе x , как только некоторые P...
Мне недавно напомнили о проблеме против N P, как объяснил Стивен А. Кук в Математическом институте Клея.пP\mathsf{P}Н ПNP\mathsf{NP} Это вызвало у меня интерес, и я хотел бы узнать об этом больше. Первым шагом будет более глубокое понимание проблемы и понимание области в целом. Можете ли вы...
Прежде всего, мое понимание теоремы Гёделя о неполноте (и формальной логики в целом) очень наивно, а также мои знания в области теоретической информатики (имеется в виду только один выпускной курс, когда я еще студент), поэтому этот вопрос может быть очень наивно Насколько я мог найти, доказуемость...
Меня интересует вопрос, является ли NP равным coNP или нет. Я был бы очень признателен за советы о хороших публикациях по этой теме. Для справки, я знаю, что этот вопрос тесно связан с вопросом о том, равен ли P NP или нет (например, если NP! = CoNP, то P! = NP). Ура,...
В статье Стивена Кука о проблеме P против NP [1] он утверждает следующее [2]: Тезис осуществимости: естественная задача имеет выполнимый алгоритм, если он имеет алгоритм полиномиального времени. У меня вопрос, что именно он (или вообще, на самом деле, что один) подразумевает под « естественной...
Предположим, P! = NP. Мы знаем, что можем в любое время легко создавать 3-SAT. Мы также можем генерировать то, что мы считаем трудными примерами (потому что наши алгоритмы не могут их быстро решить). Что-нибудь мешает множеству жестких экземпляров быть сколь угодно малыми, при условии, что для...