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

Question

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

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

Answer 1

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

Учитывая два списка слов (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 2

Получение от программистов документирования их кода.

Answer 3

NP Complete вопросы такие.

Answer 4

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

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

- MarkCC

Answer 5

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

Answer 6

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

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