Что является примером вычислительно невозможной бизнес-проблемы?

17

У меня есть коллега, который отказывается принять реальность того, что машины Тьюринга (и машины фон Неймана в целом) не могут решить свою собственную проблему остановки, заявляя:

Вы можете сделать что-нибудь с достаточным количеством времени и денег.

Он также не любит теоретические проблемы, утверждая, что:

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

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

Джезан Фафон
источник
11
Вы не можете продемонстрировать своим примером, что что-то невозможно. Ваш коллега просто скажет: «Это не работает, потому что мы не нашли правильный подход». Лучшее, что вы можете сделать, это показать ему доказательство. Если он его не купит, он либо действительно глуп, либо идиот, либо и тот, и другой. Вот список неразрешимых проблем: en.wikipedia.org/wiki/List_of_undecidable_problems
Томас Эдинг,
18
Теоретику и инженеру сказали, что они могут поцеловать девушку, многократно преодолев расстояние между ними и ней вдвое. Теоретик сразу же сдался, сказав: «Это невозможно, я никогда не доберусь туда». Инженер пошел на это, сказав: «Я подойду достаточно близко для практических целей». Вы, сэр, должны попытаться поцеловаться.
gbjbaanb
2
@gbjbaanb: Это хороший дескриптор многих неоптимальных решений NP-сложных задач, и зная, что эти проблемы (практически) невозможно решить классически, вот почему вы выбираете альтернативный метод. Если вы не согласны с тем, что некоторые проблемы практически или буквально невозможно решить, то вы не будете искать несовершенные решения, которые могут дать «достаточно хороший» ответ через неопределенный период времени.
Фоши
3
@Phoshi Нет, дело в том, что реальные инженерные решения требуют только решения, достаточно хорошего, чтобы решить проблему в достаточной степени для принятия. Решая его совершенно не стоит времени и затрат. например. Задача коммивояжера невозможна с учетом нескольких узлов, но многие компании все еще требуют (и предоставляют) неоптимальное решение. Если бы мы только достигли совершенства, никто бы их не получил.
gbjbaanb
10
@gbjbaanb: Да, но единственная причина, по которой они решили эти проблемы, - это сначала признать, что вы не можете «делать что-либо с достаточным количеством времени и денег», и перестать искать оптимальное решение. Знание того, что вы не можете сделать, часто так же важно для поиска решения, как и знание того, что вы можете сделать.
Фоши

Ответы:

11

Не технически невозможно, но ...

Планирование ресурсов с целью нахождения идеального расписания, которое максимизирует использование временных интервалов. Однажды, в мои более ранние компьютерные дни, я работал над проектом, в котором было это требование. Я работал над этим некоторое время, прежде чем понял, что это NP-хард.

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

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

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

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

Роберт Харви
источник
14
Проблема остановки возникает в статическом анализе кода. Отсюда вы можете получить такие обыденные проблемы, как «вот какой-то код, чтобы он выглядел красиво», «вот какой-то код, это вредоносное ПО» - первое имеет большое значение для компаний, создающих IDE (подсветка синтаксиса, рефакторинг), второе антивирусные компании и специалисты по безопасности.
12
«Точно так же проблема остановки важна для теоретиков, но она не имеет большого значения для большинства предприятий». Хорошо, если бы проблема остановки была вычислимой, мы могли бы автоматически проверить, будет ли часть программного обеспечения завершаться / зависать определенный вклад или нет. У нас, вероятно, больше не будет BSOD. Поскольку это невозможно, мы должны использовать другие методы для обеспечения качества программного обеспечения (например, тестирование), и никто не вкладывает время и деньги в разработку общей программы «проверки завершения». Поэтому я думаю, что этот теоретический результат имеет огромное практическое значение.
Джорджио
4

Другие прокомментировали это, но я постараюсь написать ответ с изложением моей точки зрения.

Мне нравится ответ Роберта Харви и комментарии к его ответу, и я хотел бы остановиться на них.

Я думаю, что вы должны представить эти неразрешимые проблемы (такие как завершение) обычным способом: например, инструмент IDE, который «проверяет, всегда ли эта функция возвращает значение».

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

Как проверить, выполняет ли функция / программа то же самое после приятного рефакторинга? Конечно, у нас есть модульные тесты для этого, но они не охватывают все случаи. И им скучно писать ... Но мы программисты! Мы должны написать программу, которая проверяет, дают ли эти две функции всегда один и тот же результат! Почему бы тебе не попробовать это написать?

или, как вариант, может быть ближе к вашему случаю:

У нас есть этот унаследованный код, написанный на древнем непонятном диалекте COBOL, для которого не существует спецификации и / или компилятора. У нас есть только программа. Весь наш бизнес опирается на это, поэтому мы должны быть на 100% уверены, что новый код Java делает то же самое в любой ситуации. Руководство хочет программу, которая делает это, проверяя все возможные случаи, и оценивает, что это может быть сделано через 6 - 8 недель. Почему бы тебе не попробовать это написать?

Дело не в том, чтобы написать такую ​​программу. Или достаточно хорошее приближение требований. Суть в том, чтобы понять, что это НЕ может быть сделано прямым способом, НЕ тратить бесчисленное количество наших попыток выяснить, как это сделать (только чтобы понять, что это невозможно), но признать это. «Ах! Это неразрешимо! Невозможно сделать это напрямую. Мне нужно найти другой, более умный способ сделать это с достаточно хорошим приближением».

Вы должны найти способ представить проблему понятным и, по-видимому, простым способом. Вы не поверите, сколько учеников CS сразу попытаются написать такую ​​программу ... перед тем, как пойти на урок вычислимости :)

Лоренцо Дематте
источник
Ваша вторая цитата пытается некорректно вызвать проблему остановки; однако, если мы знаем, что программа COBOL работает и может выполнить ее в тестовой среде (vm-clone all PROD, если необходимо), проблема остановки будет исключена, и мы можем попытаться. Вероятно, вручную, а не программой, но мы все равно можем это сделать. Мы могли бы разделить пополам все возможные формы ввода, если это будет необходимо. Поскольку целевая программа останавливается, то и дерево-пополам.
Джошуа
2

Предполагая, что мы можем на время отложить в сторону моральные вопросы:

Бизнес А заключил с вами договор на способ связи между спутниковыми офисами А1 и А2, при котором никто, кроме уполномоченных сотрудников А1 и А2, не сможет понять связь.

Бизнес B заключил с вами контракт на интеллектуальное прослушивание всех коммуникаций между А1 и А2.

Очевидно, вы не можете сделать оба.

Из-за того, как работает математика (точная математика была предметом постоянных исследований в течение 100 лет), одно из следующих требований не может быть выполнено:

(1): Предоставить алгоритм шифрования, который не может быть взломан злоумышленником при наличии произвольной суммы денег.

(2): Предоставить алгоритм взлома шифрования для произвольного алгоритма шифрования, который выполняется за разумное время.

Джошуа
источник
1
(3): Не удается найти другую работу после того, как рынок узнает, что вы даже пытались оба
TruthOf42
1

Недавно я посещал занятия по модели и нотации бизнес-процессов ( BPMN ). Там легко увидеть, что рабочие процессы со слишком большим количеством разбиений, объединений и циклов быстро становятся непрактичными (хотя не обязательно невозможными , AFAIK) для понимания и управления (когда вы используете слишком много OR-разбиений вместо XOR-разбиений).

Для индустрии программного обеспечения, я думаю, то же самое относится к аналогичным проблемам «покрытия нескольких условий» в анализе покрытия кода .

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

Кроме того, я думаю, что есть много проблем в анализе сетей / графиков , которые невозможно решить (пытаясь определить топологию сети, итеративно обходя все пути и т.д.).

KNB
источник
0

Классический пример - попытка разобрать HTML с помощью регулярных выражений . Это может работать с ограниченными наборами HTML, но общее решение невозможно из-за того, что они имеют разные грамматики Хомского (как ясно показывает ссылка (ish)).

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

Алистер Маккензи
источник
-6

Возможно, ответ таков: ваш коллега прав. Возможно, вы неправильно поняли Тьюринга, или как он здесь применяется?

Все машины конечны, поэтому нет «настоящих» машин Тьюринга и программ, которые никогда не остановятся. Тривиальная программа, которая выполняет простой бесконечный цикл, может выполняться 5 минут или 50 лет, но на конечном компьютере она останавливается. Нетривиальная задача, не связанная с остановкой, такая как «точное вычисление числа пи», также будет остановлена, потому что в конечном итоге вычисление превысит способность хранить дополнительные цифры.

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

Вы можете подумать, что подобная программа { while true: print "running"; print "halted"; }является контрпримером, но это не так. Эта программа имеет побочные эффекты, которые могут или не могут привести к ее остановке. Игнорируя побочные эффекты, можно придумать формальное доказательство того, что эта программа не остановится. В этом вопросе мы имеем дело только с программами, которые уклоняются от формального доказательства отсутствия остановки, где вопрос об остановке неразрешим. Это не такая программа.

Это может помочь отличить «сильный» Тьюринг от «слабого» Тьюринга. Сильные машины Тьюринга на самом деле бесконечны и, если они не смогут остановиться, будут работать бесконечно долго. Мы не можем построить их.

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

Суть Тьюринга в том, что ярлыков нет. Единственный способ убедиться в том, что проблема вычислительно выполнима, - это написать программу, запустить ее и выяснить. Имея достаточно времени и денег, вы можете написать все программы, запускать их вечно и со временем и находить те, которые дают результаты (недоумения). Остальные все еще будут бежать. У вашего коллеги достаточно времени и денег, чтобы сделать это?

Если серьезно, то спор идет о пределах. Turing и NP complete говорят нам, что определенные классы проблем не могут быть решены компьютерами в рамках любого заданного бюджета или по любому заданному графику, независимо от того, насколько велик этот бюджет или насколько щедрым может быть этот график. Примеров такого рода проблем предостаточно: взлом криптографических ключей; оптимизация маршрутов для доставки на сотни адресов; упаковка коробок в грузовики; поиск ошибок в больших программах!

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

david.pfx
источник
2
Суть проблемы остановки заключается в том, что существуют классы задач, которые невозможно вычислить никогда - даже с бесконечным временем и деньгами. Это то, что мой коллега отказывается принять.
Джезан Фафон
Тогда мы не согласны. Я отредактировал свой ответ, но по сути сообщение то же самое. Ваш заданный вопрос не имеет ответа (или не тот, который вам понравится), но в основе его лежит реальная проблема и реальная точка зрения, которую нужно сделать. Если вы хотите выиграть этот спор, вам придется несколько изменить положение, и я попытался помочь вам в этом. [Напомните мне не пытаться отвечать на подобные вопросы снова - отрицательные голоса нежелательны.]
david.pfx
2
@simon: рискуя повториться, нет программ, выполнение которых занимает бесконечное количество времени, потому что нет компьютеров Тьюринга, а лишь конечные приближения к ним. Вы не можете доказать, что произвольная программа завершится в любой конкретный промежуток времени любым способом, который быстрее, чем фактический запуск программы. На практике любое предложение со словом «бесконечный» в нем рискует не иметь смысла.
david.pfx
3
while True: print "doing stuff"; print "Finished"; Это пример программы, которая занимает бесконечное количество времени, чтобы закончить. Существует бесконечное количество других программ, которые также требуют бесконечного количества времени для завершения. Мы регулярно создаем программы, которые целенаправленно занимают бесконечное количество времени. Они называются «длительными процессами». Большинство динамических сайтов являются примерами одного.
Синглтон
2
Дело, конечно, в том, что есть наборы компьютерных программ, которые фактически бесконечны, они никогда не остановятся сами по себе (в конечном итоге мы нажмем на разрыв, отключим питание и т. Д.), Если мы запрограммируем их в машину Тьюринга, это будет бегать без остановки. Суть проблемы остановки заключается в том, что практически или теоретически практически невозможно теоретически определить программы без остановки.
Алистер Маккензи