Я читал в Stack Overflow вопрос о том, является ли NP- трудным перечисление всех простых циклов в графе, содержащем определенный узел, и мне пришло в голову, что я не могу придумать какой-либо существующий класс сложности, который хорошо подходит для разговор о проблемах в форме «перечислите все решения этой проблемы». Класс NP в некотором смысле состоит из задач, которые задают вопрос о том, существует ли хотя бы одно решение, класс FNP просит создать единственное решение, а класс #P просит подсчитать, сколько существует решений, но ни одно из них не касается сложности. исчерпывающего перечисления всех возможных решений.
Существует ли класс сложности для описания задач, которые имеют вид "заданный вычисляемый предикат полиномиального времени и строку , перечислим все для которых истинно, при условии [вставить некоторые соответствующие ограничения сложности]? " Я понимаю, что может быть сложно определить ограничения, учитывая, что число решений может быть экспоненциально больше, чем размер ввода , хотя это не кажется непреодолимым.
источник
Ответы:
Понятие, которое вы ищете, называется сложностью перечисления , то есть изучением вычислительной сложности перечисления (перечисления) всех решений проблемы (или членов языка / набора). Алгоритмы перечисления можно смоделировать как двухэтапный процесс: этап предварительного вычисления и этап перечисления с задержкой . Оба этих шага имеют свои временные и пространственные сложности (возможно, и энтропию). В общем духе сложности между ними часто приходится искать компромиссы.
Шаг предвычисления выполняет какую - то работу, которая необходима , прежде чем первый раствор перечислен. Это может включать в себя поиск самого решения или инициализацию некоторой большой структуры данных, которая уменьшит общую задержку между каждым решением.
Задержка является стоимостью ресурсов , связанной с вычислением необходимого между произвольными перечисленными решениями. Другими словами, задержка является мерой пространства и времени, необходимых для получения решения после решения . Задачи, решения которых требуют времени для каждого перечисления, имеют постоянную задержку. Говорят, что требование времени имеет полиномиальную задержку. i t h O ( 1 ) O ( p o l y ( n ) )я + 1т ч яTч О( 1 ) О ( р о л у( н ) )
Для проблемы перечисления, которую вы конкретно упомянули в своем вопросе, вам следует обратиться к классу и связанным с ним братьям и сестрам в разделе 2.1 «Перечисление: алгоритмы и сложность» Йоханнеса Шмидта (ссылка внизу).ЕNUMNп
Почему мы заботимся о времени предварительного расчета и задержке?
Задержка - это ключ к пониманию истинных сложностей перечислимых проблем. Перечисление элементов (до размера ) и где - булева формула (т.е. SAT) оба занимают экспоненциальное время. Однако перечисление через требует только постоянной задержки, поскольку вы можете просто проходить элементы в некотором порядке. Насколько нам известно, задержка для перечисления решений для экземпляра 3SAT может быть экспоненциальной. Наша работа как теоретиков сложности заключается в том, чтобы понять, почему последняя проблема существенно сложнее (более сложная), чем первая. Задержка делает довольно хорошую работу по демонстрации этой разницы. n { → x : ϕ ( → x ) } ϕ ( → x ) Σ ∗Σ* N { х⃗ : ϕ ( x⃗ ) } φ ( x⃗ ) Σ ∗
Кроме того, мы также должны знать, сколько выполнено предварительных вычислений. Мы можем уменьшить задержку для любой проблемы перечисления до постоянного времени и пространства, предварительно рассчитав все решения и сохранив их в списке для последующего перечисления. Задача состоит в том, чтобы найти наилучший баланс между двумя ресурсами.
Порядок, в котором вы перечисляете элементы, также может влиять на сложность. Требование возврата результатов в указанном отсортированном порядке может потребовать от нас выполнения дополнительных вычислений на обоих этапах. Хотя ситуации, в которых достаточно любого порядка (если каждый перечисляемый элемент уникален), конечно, тоже изучаются.
Насколько я знаю, эти классы обычно не имеют кратких меток (сродни и ). Мы не можем ожидать, что сможем сделать это, поскольку классы сложности перечисления манипулируют 3 или более ресурсами (предварительное вычисление / общее время, пространство, задержка и энтропия). Просто слишком много комбинаций границ ресурсов, чтобы выдавать специальные имена. Это не делает эти занятия менее интересными, а также не мешает исследователям в любом случае попробовать.Н Пп Nп
Ресурсы
Этот опрос (действительно попытка формализации) должен помочь вам начать. Это также доказывает некоторые основные теоремы иерархии.
Перечисление: алгоритмы и сложность (Йоханнес Шмидт, 2009)
https://www.thi.uni-hannover.de/fileadmin/forschung/arbeiten/schmidt-da.pdf
Для перечисления результатов в сложности перечисления, проверьте этот сборник, куратор Кунихиро Васа. Поскольку он классифицирован по типу задачи, вы можете легко найти ряд статей, посвященных перечислению циклов графа. Должно быть просто изменить используемые алгоритмы, чтобы рассматривать только циклы с данным узлом.
http://www-ikn.ist.hokudai.ac.jp/~wasa/enumeration_complexity.html
источник