Минимальные элементы монотонного предиката над набором мощности

Рассмотрим монотонный предикат над множеством степеней (упорядоченный по включению). Под «монотонным» я подразумеваю: такой, что , если то . Я ищу алгоритм, чтобы найти все минимальные элементы , то есть такие, что но , . Поскольку ширина равна $P$ $2^{|n|}$ $\forall x, y \in 2^{|n|}$ $x \subset y$ $P(x)$ $P(y)$ $P$ $x \in 2^{|n|}$ $P(x)$ $\forall y \subset x$ $\neg P(y)$ $2^{|n|}$ $n \choose n/2$ , может быть экспоненциально много минимальных элементов, и поэтому время работы такого алгоритма может быть экспоненциальным в целом. Однако может ли существовать алгоритм для этой задачи, который является полиномиальным по размеру вывода?

[Контекст: был задан более общий вопрос, но в ответах не было попыток оценить сложность алгоритма в размере выходных данных. Например, если я предполагаю, что существует только один минимальный элемент, я могу выполнить бинарный поиск после этого ответа и найти его. Однако, если я хочу продолжить поиск большего количества минимальных элементов, мне нужно сохранить имеющуюся у меня информацию о $P$ таким образом, чтобы можно было продолжать поиск, не тратя время на то, что уже известно. Можно ли это сделать и найти все минимальные элементы за полиномиальное время в размере вывода?]

В идеале я хотел бы понять, можно ли это сделать с помощью общих групп доступности баз данных, но я уже не знаю, как ответить на вопрос для $2^{|n|}$ .

ds.algorithms ds.data-structures partial-order order-theory search-problem a3nm
источник

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

2^{| n |}

$2^{|n|}$

{1, . . ., n}

$\{1, ..., n\}$

a3nm

Ответы:

Ваша проблема известна в учебной литературе как «изучение монотонных функций с использованием запросов на членство». Класс монотонных функций, для которого можно идентифицировать все minterms, известен как «полиномиально обучаемый с использованием запросов членства».

Кажется, что существование алгоритма полиномиального времени все еще открыто. Шмулевич и соавт. докажите, что «почти все монотонные булевы функции являются полиномиально обучаемыми с помощью запросов членства». Если мы также потребуем, чтобы я минута была сгенерирована во временном полиноме от и , то проблема эквивалентна монотонной дуализации, как показали Биоч и Ибараки . Вот опрос, посвященный монотонной дуализации. $t$ $n$ $t$

Юваль Фильмус
источник

Спасибо за этот чрезвычайно полезный ответ. Известны ли вам обобщения на произвольные группы доступности баз данных (т. Е. Больше, чем в особых случаях в разделе 5.2 Eiter et al.)?

a3nm

Нет, к сожалению нет.

Юваль Фильмус

Хорошо, я все равно приму этот ответ. Дополнительные замечания: (1) этот ответ касается сложности вычислений, а не сложности числа оценок (см. Cstheory.stackexchange.com/a/14862/4795 для этого последнего случая), и (2) точного открытия вопрос «можете ли вы выучить монотонную булеву функцию за полиномиальное время по и ее количество минимумов и максимумов», нет никакой надежды сделать это за полиномиальное время по и количеству максимумов, потому что может быть линейное число максимумов но экспоненциальное число минимумов (см. пункт 6.1, пункт 2 в упомянутом выше обследовании).

P

$P$

n

$n$

n

$n$

a3nm

См. Мой другой вопрос cstheory.stackexchange.com/q/16258/4795 для получения информации о глобальной сложности запросов наихудшего случая для произвольных групп доступности баз данных.

a3nm

повторная монотонная дуализация (CNF ← → DNF) и DAG. звучит очень похоже на теорему из булевой функции juknas book сложность сек 9.4. "критерий нижних границ" thm 9.17

vzn