Какие практически неразрешимые проблемы в мире программирования?

Question

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

Какие еще проблемы программирования считаются неразрешимыми?

Answer 1

Если вы ищете проблемы, которые похожи на проблему коммивояжера, я предлагаю вам поискать проблемы с NP-полными. Это класс задач, который не имеет какого-либо известного эффективного решения, то есть алгоритм, который вычисляет результат за полиномиальное время. Интригующая вещь в классе задач NP состоит в том, что никто не смог показать, что любой алгоритм их решения должен занимать экспоненциальное время. Это, пожалуй, самый большой нерешенный вопрос в информатике.

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

Вот список других NP-полных задач:

• Упаковка бункера, как заполнить контейнер так, чтобы в него поместилось оптимальное количество вещей. Я знаю парня, который руководит компанией, которая помогает судоходным компаниям упаковывать свои суда наилучшим образом. Его программа не находит лучшего решения, но обычно может помочь упаковывать корабли более умным способом, чем то, что можно сделать вручную.
• SAT решение, показывающее, что пропозициональная формула выполнима. Это довольно теоретическая проблема, но она используется корпорацией Intel для автоматического подтверждения правильности схемотехники. SAT решатели становятся довольно хорошими в наши дни и могут довольно быстро решать довольно большие проблемы.
• Планирование, учитывая количество заданий, которые необходимо выполнить, и количество ресурсов, необходимых для выполнения этих заданий, рассчитывают наиболее эффективный способ выполнения заданий. Авиалайнерам приходится много решать эту проблему, поскольку у них есть свои ресурсы, персонал и самолеты, которые они хотят использовать как можно более эффективно, при этом обслуживая все рейсы. Такие компании, как Jeppesen, имеют программы для оптимизации этого.
• Раскраска графа. Возьмите неориентированный граф и попытайтесь раскрасить каждый узел так, чтобы никакие два смежных узла, соединенных ребром, не имели одинаковый цвет. Цель состоит в том, чтобы использовать как можно меньше цветов. Это используется компиляторами для назначения регистров локальным переменным. Чем лучше алгоритм раскраски графа, тем больше переменных помещается в регистры, а не в память.

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

Answer 2

Во-первых, существует большая разница между неразрешимыми проблемами и проблемами, которые трудно решить. Я знаю, это звучит очевидным, но многие люди отмечают, что сложные проблемы (например, коммивояжер) являются неразрешимыми, когда лучше сказать, что они не решаемы эффективно, т. Е. В полиномиальное время.

Самая известная неразрешимая проблема - проблема остановки. Смотрите эту страницу для получения дополнительной информации. Один из распространенных способов показать, что проблема неразрешима, - это показать, что она эквивалентна проблеме остановки.

Answer 3

Internet Explorer 6

Answer 4

Проблема остановки. Доказано неразрешимым.

Answer 5

Создание небьющегося DRM для неинтерактивного контента, где предполагаемые пользователи все еще могут использовать контент...

Answer 6

Проблемы, которые неразрешимы, не могут быть решены ни одним алгоритмом.

http://en.wikipedia.org/wiki/Undecidable_problem

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

Примеры неразрешимых проблем включают в себя проблему Остановки, которая гласит: учитывая алгоритм, решите, будет ли алгоритм в конечном итоге закончен или будет продолжаться вечно (например, в бесконечном цикле). Алан Тьюринг доказал, что проблема Остановки неразрешима.

Answer 7

Попытка найти разработчика, который доволен написанным кодом!

Answer 8

Как многие люди уже ответили, проблема ур, которую невозможно решить, является проблемой остановки: написать программу H который берет программу P в качестве ввода и отвечает ли программа ввода P будет цикл навсегда или нет. Обратите внимание, что наша программа H может ответить правильно для многих входных программ, задача состоит в том, чтобы написать программу, которая может ответить на этот вопрос для всех программ.

Почему проблема остановки неразрешима? Доказательство довольно простое и довольно забавное: предположим, что мы можем написать программу H которая решает проблему остановки. (Цель состоит в том, чтобы показать, что, предполагая это, мы получим результаты, которые являются просто бессмысленными, следовательно, наше предположение неверно.) Теперь создайте программу EVIL который использует H как подпрограмма. Мы можем написать EVIL как это:

EVIL p = if H p then loop
                else false

Краткое объяснение в порядке. EVIL берет программу, и если эта программа останавливается, то EVIL петли. Затем программа ввода зацикливается EVIL возвращает ложь

Следующий шаг действительно крутой: применить EVIL к себе! Вопрос в том, каков будет ответ EVIL EVIL быть? Это явно зависит от того, EVIL зацикливается навсегда или нет. Давайте рассмотрим две альтернативы:

• предполагать EVIL петли навсегда. Но тогда, когда мы передаем это как входную программу для себя, она должна вернуть false поскольку H обнаружил, что это будет цикл навсегда. Но возвращаясь false противоречит тому, что мы впервые сказали, что EVIL петли навсегда, так что явно не может быть так.

• Хорошо, так что EVIL не зацикливается Хорошо, когда мы кормим EVIL сам по себе это будет просто петля, потому что H возвращенный true, Таким образом, у нас есть противоречие и здесь.

Вот досада! Обе альтернативы (EVIL петли или нет) приводит к противоречиям. Таким образом, наши предположения должны быть ошибочными. Нет такой программы как H который может решить, останавливается ли функция или нет.

---

Есть много интересных неисчислимых проблем, связанных с проблемой остановки. Некоторые из моих любимых - это технологии компиляции. Например: найти наименьшую эквивалентную программу.

Еще одно: учитывая, что вы аннотировали вашу программу утверждениями, напишите программу, которая проверяет, будет ли какое-либо из утверждений нарушено во время выполнения. Такая программа иногда называется средством проверки моделей, и они могут быть действительно полезными, но они никогда не могут быть завершены, то есть им иногда приходится отвечать "я не знаю", когда проблема становится слишком сложной.

Answer 9

Получение всех трех из: объем (функции), сроки (график), бюджет (ресурсы - разработчики); вместо "выбрать два".

Answer 10

Я считаю проблему рюкзака особенно интересной, поскольку она применима ко многим различным областям.

Answer 11

Н.П. Полные вопросы такие.

Answer 12

Проблема почтовой корреспонденции:

По двум спискам слов (a1, a2, .., an) и (b1, b2, .., bn) найдите последовательность индексов, чтобы объединенные слова были равны.

Например, учитывая списки (1: a, 2: ab, 3: bba) и (1: baa, 2: aa, 3: bb), последовательность (3, 2, 3, 1) является решением, поскольку bba+ab+bba+a = bb+aa+bb+baa.

Эта проблема выглядит так, как будто должен быть алгоритм, решающий ее (мы просто говорим о поиске последовательности, чтобы строки совпадали, и ничего сложного, как машины Тьюринга, не задействовано); но это неразрешимо, как и проблема остановки.

Answer 13

Заставить программистов документировать свой код.

Answer 14

На самом деле, NP-полные проблемы, такие как коммивояжёр, в общем, трудно решить, но конкретный экземпляр (или даже большинство его экземпляров в некоторой области (например, компиляция кода на Haskell]) может быть легко решен!

Есть много проблем, которые, в теории, невероятно сложны - но поскольку сложные случаи очень редки и довольно надуманы, их на самом деле очень легко решить. Два примера этого, которые я нахожу особенно интересными, оба являются законченными. Проверка типов в Haskell является одним из них: на самом деле, общий вывод типов в Haskell хуже, чем NP, завершенный: проверка типов является NP-полной; вывод типа NP-сложный. Но в реальном коде он практически линейный. Другая - логическая проблема, называемая 3-SAT. Однажды я посетил замечательную беседу парня по имени Дэниел Джексон, рассказывающего о формальном языке спецификации, который он разработал под названием Alloy. Сплав сокращает проверку спецификации до 3-SAT. Дэн объяснил это высказыванием так: "Плохая новость заключается в том, что анализ спецификаций Alloy является 3-SAT, так что он экспоненциальный и NP-полный. Но хорошая новость заключается в том, что анализ спецификаций Alloy является 3-SAT, поэтому мы можем решить его очень быстро

- MarkCC

Answer 15

Во многих ответах упоминается проблема остановки. Другие примеры неразрешимых проблем включают языки, не принимаемые машинами Тьюринга. Примером такого языка является язык машин Тьюринга, которые не принимают свою собственную кодировку.

Answer 16

Не все языки программирования могут иметь решаемые проблемы. Например, я бы предпочел сделать regrep с помощью perl, а не applecript. Большинство языков программирования, таких как PHP, имеют "ошибки", которые невозможно устранить, пока кто-то из команды php не исправит механизм php.

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