Рассмотрим следующую версию задачи Клика, где вход имеет размер и нас просят найти клику размера k . Ограничение состоит в том, что процедура принятия решения не может изменить входной граф в любое другое представление и не может использовать любое другое представление для вычисления его ответа, кроме log ( n k ) дополнительных битов помимо входного графа. Дополнительные биты могут использоваться, например, в алгоритме грубой силы, чтобы отслеживать состояние исчерпывающего поиска клики, но процедура принятия решения может использовать их любым другим способом, который все еще решает проблему.
Что-нибудь известно на данный момент о сложности этого? Была ли проделана какая-либо работа над другими ограничениями Клики, и если да, могли бы вы направить меня к такой работе?
источник
Ответы:
Это звучит так, как будто вы спрашиваете, можно ли решить задачу клики с полной NP в логарифмическом пространстве. Используя машины Тьюринга, одна лента доступна только для чтения и хранит входной график. Другая лента ограничена , так что есть пространство для некоторой константы с . Класс задач, решаемых в этой модели, известен как L , детерминированное логарифмическое пространство. (См. Википедию или в зоопарке сложности )clgn c L
Неизвестно, будет ли , но положительный ответ будет означать, что P = N P , поэтому вы (почти наверняка?) Не найдете ответа. L ⊆ P ⊆ N Р и С Л Я В U Е ∈ L означает C L I Q U E ∈ P , что влечет P = N P .CLIQUE∈L P=NP L⊆P⊆NP C L I Q U E ∈L C L I Q U E ∈P п= Nп
Изменить, если я неправильно истолковал проблему:
Если вы намереваетесь, что в lg n k = k lg n совпадает с размером клика k (т. Е. Объем памяти масштабируется с помощью ввода k ), то существует простой алгоритм перебора: вы можете перебрать все возможные наборы k узлов и проверьте, образуют ли они k -клик. Отправной точкой для поиска лучших решений могут быть ссылки из [1].К Л.Г.NК= к лгN К К К К
[1] Вирджиния Василевская, «Эффективные алгоритмы для задач клики» pdf link
источник
searchпроблема, в данном случае.