Возможно ли решить проблему сложности O (n!) За разумное время, учитывая бесконечное количество блоков обработки и бесконечное пространство?Пределы параллелизма (вопрос о собеседовании)
Типичным примером проблемы O (n!) Является поиск по грубой силе: попытка всех перестановок (упорядоченных комбинаций).
Это точно. Рассмотрите проблему коммивояжера в строгой форме NP: учитывая этот список расходов на путешествие из каждой точки в точку друг друга, можете ли вы объединить тур со стоимостью меньше K? С новым процессором с бесконечным ядром от Intel вы просто назначаете одно ядро каждой возможной перестановке и добавляете затраты (это быстро) и видите, успешно ли какие-либо основные флаги.
В общем случае проблема NP - проблема решения, так что потенциальное решение может быть проверено в полиномиальное время (т. Е. Эффективно), и поэтому (поскольку потенциальные решения перечислимы) любая такая проблема может быть эффективно решена с помощью достаточно много процессоров.
Конечно, вы можете перечислить все возможные решения, но как предоставить каждому процессу обработки требуемые данные? Вы должны распространять данные, и это означает, что вам нужно сравнивать каждую перестановку друг с другом. – psihodelia
Нет, вам не нужно сравнивать все со всем. Предположим, вы хотели получить самое дешевое решение для TSP. Рассчитайте все затраты параллельно. Затем четные процессоры сравнивают свои значения с соответствующими нечетными и сохраняют более экономичный результат. Сделайте такое сравнение, и вы можете получить ответ за время, необходимое для регистрации n! сравнения. O (n^n)> = O (n!), А log (n^n) - n log n, поэтому пост-обработка будет в худшем случае O (n log n), что является многочленом. Это можно было бы сделать, по крайней мере, при настройке. –
Давайте посмотрим на TSP, который: если полный взвешенный график найдет гамильтоновский цикл с наименьшим весом. Вы должны иметь детерминированную процедуру для создания уникального цикла Гамильтона на каждом CPU. Каждый процессор должен назначать каждый цикл. Даже если вычисление длины цикла может быть выполнено в полностью независимом потоке обработки, есть n! циклы. Возникает вопрос: могут ли все циклы быть назначены на процессоры независимо? Нет почему? Из-за детерминированного характера расплаты. – psihodelia
Несоблюдение стоимости установки (что бы это ни было ... присваивание диапазона значений, например, процессору), то да. В таком случае любое значение, меньшее бесконечности, может быть разрешено в одной параллельной итерации на равном числе блоков обработки.
Настройка, однако, является чем-то значительным, чтобы игнорировать.
Почему любая ценность меньше бесконечности? Учитывая бесконечное количество процессоров, не должны ли они обрабатывать равные (бесконечные) процессы? Бесконечность болит мой мозг иногда – Bob
@Bob: Потому что каждое значение меньше бесконечности;) –
Нет, потому что для распространения задания на бесконечные машины требуется бесконечное время - также требуется очень много времени, чтобы открыть ящики и установить их. –
Похоже, что вы действительно задаетесь вопросом, может ли проблема сложности O (n!) Свести к O (n^a) на недетерминированной машине; другими словами, является ли Не-P = NP. Ответ на этот вопрос - нет, есть некоторые проблемы не-P, которые не являются NP. Например, проблема с ограниченным остановом (которая запрашивает, если программа останавливается не более, чем n! Шагов).
Я принял ответ, если есть некоторые проблемы, которые можно легко решить. Вы отвечаете за все проблемы, которые в равной степени законны и что большинство респондентов не обращаются. –
Это правда. Я думаю, что наши ответы дополняют друг друга: есть некоторые проблемы, которые уменьшают, а другие - нет. Оба факта важны. – tloflin
Проблема будет заключаться в распределении работы и сборе результатов.
Если все процессоры могут считывать одну и ту же часть памяти одновременно, и если у каждого из них есть уникальный идентификатор CPU, который ему известен, тогда идентификатор может использоваться для выбора перестановки, а проблема распространения решаемые в постоянное время.
Сбор результатов был бы сложным. Каждый ЦП мог сравниться с его (числовым) соседом, а затем этот результат по сравнению с результатом двух ближайших соседей и т. Д. Это будет процесс O (log (n!)). Я не знаю точно, но я подозреваю, что O (log (n!)) Является гиперполиномиальным, поэтому я не думаю, что это решение.
O (log (n!)) = O (n log n). Это полиномиально. – Daniel
Если проблема заключается в проверке перестановок/ответов на проблему сложности O (n!), То, конечно, вы можете сделать это эффективно с помощью бесконечного числа процессоров.
Причина в том, что вы можете легко распределить атомные куски проблемы (атомная часть проблемы может, скажем, быть одной из перестановок для проверки) с логарифмической эффективностью.
Как простой пример, вы можете настроить процессоры как «двоичное дерево», так сказать. Вы можете быть в корне, и процессоры могут обеспечить перестановку проблемы (или, что бы это ни было наименьшей частью проблемы), чтобы листовые процессоры могли решить, и вы в конечном итоге решаете проблему в log (n!) время.
Помните, что доставка перестановок на процессоры занимает много времени. Каждая часть самой проблемы будет фактически решена мгновенно.
Редактировать: Исправлено сообщение в соответствии с комментариями ниже.
Поскольку число процессоров, используемых в этой проблеме, равно n! а не n, установка «двоичного дерева» находится в порядке log (n!). –
Ты прав. Виноват! – Cam
log n! достаточно. Это многочлен (хотя определенно не сублинейный). –
Каждая проблема может быть решена одним процессором, но кто поставит эти задания на все бесконечные процессоры? В общем, эта задача централизована, поэтому, если у нас есть бесконечные задания для доставки на все бесконечные процессоры, мы можем потратить бесконечное время на это.
На самом деле для большинства реальных задач распределение заданий является параллельным процессом, поэтому для распределения задач O (n!) Является O (n log n). –
Нет, N! даже выше NP. Размышление о неограниченном параллелизме могло решить проблему NP в полиномиальное время, которое обычно считается «разумной» временной сложностью, N! проблема по-прежнему выше, чем полином на такой установке.
* N! даже выше NP * - [править]. И это даже актуально? Пока результат проверяется полиномиальным временем, он находится в NP. – kennytm
Разумно сказать, что O (n!) Выше O (2^n), так как это сравнивается с подобным. Однако проблема NP определяется как та, которая разрешима в полиномиальное время на недетерминированной машине Тьюринга или, что то же самое, с результатами, которые проверяются в полиномиальное время. Он ничего не говорит о временной сложности для нахождения решения. Поэтому я просто не понимаю, что вы можете сказать по вашему заявлению. –
@KennyTM: Извините за злоупотребление нотной записью NP.Я как-то понял, что проблемы NP имеют форму k^N, возможно, из-за всемогущества его академического определения. Вы правы, я не должен был использовать NP в своем первоначальном ответе, и я не хочу ссылаться на мое заявление. Тем не менее, если проблема проверяется в полиномиальном временном порядке от проблемы к проблеме. Мое первоначальное намерение состояло в том, чтобы сказать, что есть некоторые проблемы с N! сложность не может быть проверена в полиномиальное время даже с неограниченным параллелизмом. – Codism
Вы упомянули поиск как «типичную» проблему, но были ли вы конкретно спрошены о проблеме поиска? Если да, то да, поиск обычно параллелизуется, но насколько я могу сказать, O (n!) В принципе не означает, что степень параллелизма доступна, не так ли? У вас может быть полностью последовательная проблема O (n!), Что означает, что бесконечные компьютеры не помогут. У меня когда-то была необычная проблема O (n^4), которая на самом деле была полностью серийной.
Итак, доступный параллелизм - это первое, и ИМХО вам нужно получить баллы за то, что вы приняли закон Амдаля в интервью. Следующая потенциальная ошибка - это межпроцессорная связь и, в общем, характер алгоритма. Рассмотрим, например, этот список классов приложений: http://view.eecs.berkeley.edu/wiki/Dwarf_Mine. FWIW код O (n^4), о котором я упоминал ранее, относится к категории FSM.
Еще один эпизод, связанный с анекдотом. Я слышал, как инженер из суперкомпьютерного производителя утверждает, что если 10% их процессорного времени тратится в библиотеках MPI, они считают параллелизм прочным успехом (хотя, возможно, это было ограничено кодов в области вычислительной химии).
Это похоже на вопрос о том, может ли бесконечное количество обезьян, печатающих на компьютере с доказательством уничтожения обезьян, с текстовым процессором, придумать все произведения Шекспира; учитывая бесконечное количество времени. Реалист сказал бы не потому, что условия физически невозможны. Идеалист скажет «да»; в теории это может случиться. Поскольку Software Engineering (Software Engineering, а не Computer Science) фокусируется на реальной системе, которую мы можем видеть и касаться, тогда ответ отрицательный. Если вы сомневаетесь во мне, тогда пошли строить его и доказывать, что я ошибаюсь! ИМХО.
Иногда правильный ответ: «Сколько раз это происходит с вашей базой кода?» но в этом случае есть реальный ответ.
Правильный ответ - нет, потому что не все проблемы могут быть решены с использованием совершенной параллельной обработки. Например, проблема, связанная с коммивояжером, должна совершить один путь для рассмотрения второго этапа поездки.
Предполагая полностью связанную матрицу городов, если вы хотите отобразить все возможные нециклические маршруты для нашего усталого продавца, вы застреваете с проблемой O (n!), Которая может быть разложена на O (n) * O ((n-1)!). Проблема в том, что вам нужно зафиксировать один путь (на стороне O (n) уравнения), прежде чем вы сможете рассмотреть оставшиеся пути (на стороне O ((n-1)!) Уравнения).
Поскольку некоторые вычисления должны выполняться до других вычислений, то нет возможности точно разбить результаты в одном проходе рассеяния/сбора. Это означает, что решение будет ждать результатов расчетов, которые должны быть выполнены до того, как можно будет запустить «следующий» шаг. Это ключ, поскольку потребность в предшествующих частичных решениях обеспечивает «горло бутылки» в возможности продолжить вычисление.
Поскольку мы доказали, что можем сделать несколько из этих бесконечно быстрых, бесконечно многочисленных, процессоры ждут (даже если они ждут сами по себе), мы знаем, что время выполнения не может быть O (1), и нам нужно только выбрать очень большой N, чтобы гарантировать «неприемлемое» время работы.
Нет. Распределите перестановки между процессорами, которые представляют собой операцию полиномиального времени. Каждый CPU затем вычисляет свою стоимость перестановки, которая также является полиномиальным временем, фактически O (n). Затем идет иерархическое сравнение, которое также является полиномиальным временем. –
Вы не можете распространять все перестановки между процессорами, не изучив пространство перестановок. Если вы возьмете подход с дробовиком, вы можете пропустить перестановки (и там определенно будет много перекрытий), а «фаза рекомбинации» будет платить цену за то, чтобы сортировать тонны дубликатов, которые все равно будут брать ее выше O (1), заставляя его по-прежнему подвергаться «необоснованному времени», сделав решение достаточно большим. –
Да, если n! <бесконечность. – mob
Я хочу знать, где вы проводили собеседование. Удивительно, что у них есть компьютер с бесконечными процессорами и памятью! –
@Jeff: Tee hee. – Pierreten