В классе сложности есть некоторые проблемы, предположительно не входящие в класс N C , то есть проблемы с детерминированными параллельными алгоритмами. Проблема максимального потока является одним из примеров. И есть проблемы, СЧИТАЕМЫЕ быть в N C , но доказательство еще не найдено.
Идеальный Matching проблема является одной из наиболее фундаментальной проблемы , затронутой в теории графов: для графа , мы должны найти идеальное соответствие для G . Как я мог найти в интернете, несмотря на прекрасный алгоритм Блоссома с полиномиальным временем Эдмондса и RANDOMIZED параллельный алгоритм Карпа, Апфала и Вигдерсона в 1986 году, известно, что только несколько подклассов графов имеют N C алгоритмов.
В январе 2005 года есть запись в блоге вычислительной сложности , что претензии он остается открытым ли паросочетания в . Мой вопрос:
Есть ли какой-либо прогресс с тех пор, кроме рандомизированного алгоритма ?
Чтобы прояснить мой интерес, любой алгоритм, который имеет дело с общими графами, хорош. Хотя алгоритмы для подклассов графов тоже в порядке, это может быть не мое внимание. Спасибо вам всем!
РЕДАКТИРОВАТЬ в 12/27:
Спасибо за вашу помощь, я стараюсь обобщить все результаты в одну цифру:
Наименее известные классы содержат следующие проблемы:
- Сопоставление в общих графах: [ KUW86 ], R N C 2 [ CRS93 ]
- Соответствие в двудольных планарных / константных графах: / S P L [ DKT10 ] / [ DKTV10 ]
- Соответствует, когда общее число является полиномиальным: [ H09 ]
- Максимальное совпадение с первым Lex: [ MS89 ]
Кроме того, при предположении вероятной сложности: для требуются экспоненциальные схемы, в общих графах сопоставление выполняется в S P L [ ARZ98 ].
источник
Ответы:
Надеюсь это поможет.
источник
Несколько лет спустя :) и Perfect Matching теперь известны в Quasi-NC (то есть, вам нужно квазиполиномиально много процессоров). См. Статью Феннера, Гурджара и Тирауфа (для двудольных графов) https://arxiv.org/pdf/1601.06319.pdf и нашу работу с Олой Свенссон (для общих графиков): https://arxiv.org/pdf/1704.01929
источник
Дерандомизация леммы об изоляции по Тевари-Винодчандрану, к сожалению, не дает верхней границы UL для плоского сопоставления. На самом деле я даже не думаю, что алгоритм NC не известен для плоского сопоставления. Но в недавней работе с Datta, Kulkarni и Nimbhorkar мы показываем верхнюю границу UL для двустороннего плоского сопоставления (запись этого результата все еще продолжается). Это интересно, потому что до этого даже NL-граница не была известна для этой проблемы.
источник
Когда известно, что проблема оптимизации трудна, обычно рассматривают их максимальные версии. Например, в то время как независимый набор является NP-Complete, лекс первый максимальный независимый набор, который является P-Complete.
Все это говорит о том, что не может быть легко распараллеливаемой версии NC для этого. Но тогда кто знает? Кто-то может дерандомизировать версию RNC на следующей неделе!
Редактировать: Спасибо, Рампрасад. Но вот еще одна ссылка на статью.
источник
Т. Фишер, А. В. Гольдберг, DJ Хаглин и С. Плоткин. Аппроксимирующие совпадения параллельно. Информация. Proc. Lett., 46 (3): 115, 1993
источник