Наихудшее количество вопросов, необходимых для изучения монотонного предиката за сеансом

Рассмотрим $(X, \leq)$ конечное множество по элементам, а - неизвестный монотонный предикат над (т. Е. Для любого , , если и то ). Я могу оценить , предоставив один узел и выяснив, выполняется ли или нет. Моя цель - точно определить множество узлов x ∈ X, таких что P ( x ) , используя как можно меньше оценок P$n$$P$$X$$x$$y \in X$$P(x)$$x \leq y$$P(y)$$P$$x \in X$$P(x)$$x \in X$$P(x)$$P$насколько это возможно. (Я могу выбирать свои запросы в зависимости от ответа на все предыдущие запросы, я не обязан планировать все запросы заранее.)

Стратегия $S$ over $(X, \leq)$ - это функция, которая сообщает мне, как функцию запросов, которые я выполнил до сих пор, и их ответы, какой узел запрашивать и который обеспечивает это для любого предиката $P$ , следуя стратегии, Я достигну состояния, в котором я знаю значение $P$ на всех узлах. Время работы $r(S, P)$ из на предикат является число запросов необходимо знать значение на все узлы. Худшее время работы : . Оптимальная стратегия$S$$P$$P$$S$$wr(S) = \max_P r(S, P)$$S'$ таков, что $wr(S') = \min_S wr(S)$ .

Мой вопрос заключается в следующем: учитывая в качестве входных данных poset $(X, \leq)$ , как я могу определить наихудшее время выполнения оптимальных стратегий?

[Понятно, что для пустого poset потребуется $n$ запросов (нам нужно спросить о каждом отдельном узле), и что для общего порядка около $\lceil \log_2 n \rceil$ будут необходимы запросы (выполнение бинарного поиска для поиска граница). Более общий результат следующей информация теоретико-нижняя граница: число возможных вариантов для предиката $P$ является число $N_X$ антицепей из $(X, \leq)$ (потому что существует отображение один к одному между монотонными предикатами и антицепи интерпретируются как максимальные элементы $P$ ), поэтому, поскольку каждый запрос дает нам один бит информации, нам потребуется по крайней мере $\lceil \log_2 N_X \rceil$запросы, включающие два предыдущих случая. Является ли это жесткой связью, или это какие-то поэты, структура которых такова, что для обучения может потребоваться асимптотически больше запросов, чем число антицепей?]

Это не полный ответ, но это слишком долго, чтобы быть комментарием.

Я думаю, что нашел пример, для которого оценка $\lceil \log_2 N_X \rceil$ не является жесткой.

Рассмотрим следующий подход. Основное множество , и a i меньше, чем b j для всех i , j ∈ { 1 , 2 } . Другие пары несопоставимы. (Диаграмма Хассе является 4- тактной).$X=\{a_1, a_2, b_1, b_2\}$$a_i$$b_j$$i,j\in\{1,2\}$$4$

Позвольте мне идентифицировать монотонные свойства с расстройствами poset. Этот набор имеет семь расстройств: , { b 1 } , { b 2 } , { b 1 , b 2 } , { a 1 , b 1 , b 2 } , { a 2 , b 1 , b 2 } , { a 1 , а 2 , б 1$\emptyset$$\{b_1\}$$\{b_2\}$$\{b_1,b_2\}$$\{a_1,b_1,b_2\}$$\{a_2,b_1,b_2\}$ , и у этого множества есть семь антицепей, так как антицепи находятся в взаимно однозначном соответствии с расстройствами. Итак, ⌈ log 2 N X ⌉ = ⌈ log 2 7 ⌉ = 3 для этого множества.$\{a_1,a_2,b_1,b_2\}$$\lceil \log_2 N_X \rceil=\lceil \log_2 7 \rceil = 3$

Теперь, используя аргумент противника, я покажу, что для любой стратегии требуется как минимум четыре запроса (поэтому необходимо запросить все элементы). Давайте исправим произвольную стратегию.

Если стратегия первых запросов , то Противнику ответы « P ( 1 ) не выполняется.» Затем у нас остается пять возможностей: ∅ , { b 1 } , { b 2 } , { b 1 , b 2 } , { a 2 , b 1 , b 2 } . Таким образом, чтобы определить, что именно так, нам нужно, по крайней мере, ⌈ log 2 5 ⌉ = $a_1$$P(a_1)$$\emptyset$$\{b_1\}$$\{b_2\}$$\{b_1,b_2\}$$\{a_2,b_1,b_2\}$$\lceil \log_2 5\rceil = 3$больше запросов. Всего нам нужно четыре запроса. Же аргумент применяется , если первый запрос 2 .$a_2$

Если стратегия сначала запрашивает , то противник отвечает « P ( b 1 ) имеет место». Затем у нас остается пять возможностей: { b 1 } , { b 1 , b 2 } , { a 1 , b 1 , b 2 } , { a 2 , b 1 , b 2 } , { a 1 , a 2 , $b_1$$P(b_1)$$\{b_1\}$$\{b_1,b_2\}$$\{a_1,b_1,b_2\}$$\{a_2,b_1,b_2\}$ . Поэтому нам нужно как минимум еще три запроса, как и раньше. Всего нам нужно четыре запроса. Тот же аргумент применяется, когда первый запрос равен b 2 .$\{a_1,a_2,b_1,b_2\}$$b_2$

Если мы возьмем параллельных копий этого множества, то у него будет 7 k антицепей, и, следовательно, предложенная граница равна ⌈ log 2 7 k ⌉ = 3 k . Но, так как каждая из копий необходимо четыре запроса, нам нужно по крайней мере 4 K запросов.$k$$7^k$$\lceil \log_2 7^k \rceil = 3k$$4k$

Вероятно, есть больший посет с большим разрывом. Но этот аргумент может только улучшить коэффициент.

Здесь проблема выглядит как ситуация, когда ни один запрос не разбивает пространство поиска равномерно. В таком случае противник может заставить большую половину остаться.

В своей работе каждый Посьет Имеет центральный элемент шоу, Linial и Сакса (теорема 1) , что число запросов , необходимых для решения проблемы идентификации идеал в ч.у.м. не превосходит K 0 лог 2 я ( X ) , где K 0 = 1 / ( 2 - войти 2 ( 1 + войти 2 5 ) ) и я ( Х ) является число идеалов X . То, что они называют «идеалом», на самом деле является более низким набором$X$$K_0 \log_2 i(X)$$K_0 = 1/(2 - \log_2(1 + \log_2 5))$$i(X)$$X$и существует очевидное соответствие один к одному между монотонными предикатами и нижним набором точек, в которых они не хранятся, кроме того, что их «проблема идентификации» состоит в том, чтобы идентифицировать, запрашивая узлы, как в моей настройке, так что я думаю, что они решения этой проблемы я заинтересован в том , что и .$i(X) = N_X$

Таким образом, согласно их результату, теоретико-информационная нижняя граница тесно связана с относительно небольшой мультипликативной константой. Так что это в основном решает вопрос о количестве вопросов , необходимых, в зависимости от и с точностью до мультипликативной константы: она находится между лог 2 N X и K 0 лог 2 N X .$N_X$$\log_2 N_X$$K_0 \log_2 N_X$

Линиал и Сакс цитируют личное сообщение Ширера о том, что существуют известные порядки, для которых мы можем доказать нижнюю границу для некоторого K 1, который лишь немного меньше K 0 (это в духе Ответ Йошио Окамото, который попробовал этот подход для меньшего значения K 1 ).$K_1 \log_2 N_X$$K_1$$K_0$$K_1$

Это не полностью отвечает на мой вопрос вычисления числа вопросов, требуемых от , однако, поскольку вычисление N X из X является # P-полным , у меня есть ощущение, что надежды мало. (Комментарии по этому вопросу приветствуются.) Тем не менее, этот результат Линиала и Сакса является поучительным.$X$$N_X$$X$

Для булева n-куба (или, что то же самое, для множества ( 2 S , ⊆ ) всех подмножеств множества n-элементов), ответ дается теоремами Коробкова и Гензеля (с 1963 и 1966 соответственно). Теорема Гензеля [1] гласит, что неизвестная монотонная булева функция (т. Е. Неизвестный монотонный предикат на этом множестве) может быть изучена детерминированным алгоритмом, делающим не более ϕ ( n ) = ($(\{0, 1\}^n, \leq)$$(2^S, \subseteq)$ запросов (т. Е. Задает ϕ(n)вопросов в худшем случае). Этот алгоритм соответствует нижней границе теоремы Коробкова [2], в которой говорится, чтозапросовϕ(n)-1недостаточно. (Таким образом, алгоритм Ханселя является оптимальным в худшем случае.) Алгоритм в обоих утверждениях понимается как детерминированное дерево решений.$\phi(n) = \binom{n}{\lfloor n/2 \rfloor} + \binom{n}{\lfloor n/2 \rfloor + 1}$$\phi(n)$$\phi(n) - 1$

Логарифм числа антицепей в асимптотически равен ($(\{0, 1\}^n, \le)$ , поэтому междуlogNXи оптимальной производительностью алгоритма существуетразрыв с постоянным множителемϕ(n)∼2 ($\binom{n}{\lfloor n/2 \rfloor} \sim 2^n / \sqrt{\pi n / 2}$$\log N_X$ для этого набора.$\phi(n) \sim 2 \binom{n}{\lfloor n/2 \rfloor}$

К сожалению, я не смог найти хорошее изложение алгоритма Гензеля на английском языке, доступное в Интернете. Он основан на лемме, которая разбивает n-куб на цепочки со специальными свойствами. Некоторое описание можно найти в [3]. Что касается нижней границы, я не знаю ссылки на описание на английском языке.$\phi(n)$

Поскольку я знаком с этими результатами, я могу опубликовать описание на arXiv, если обработки в статье Ковалерчука не достаточно.

Если я не сильно ошибаюсь, были попытки обобщить подход Гензеля, по крайней мере, на множество , где ( E k , ≤ ) - цепь 0 < 1 < … < k - 1 , хотя я не может дать ссылку сразу. Для логического случая люди также исследовали понятия сложности, отличные от наихудшего случая для этой проблемы.$(E_k^n, \le)$$(E_k, \le)$$0 < 1 < \ldots < k - 1$

[1] Г. Хансель, Sur nombre des fonctions booléennes monotones de n variable. ЧР акад. Sci. Paris, 262 (20), 1088-1090 (1966)

[2] В.К. Коробков. Оценка числа монотонных функций алгебры логики и сложности алгоритма нахождения резольвентного множества для произвольной монотонной функции алгебры логики. Советская математика Доклыды 4, 753-756 (1963)

[3] Б. Ковалерчук, Е. Триантафиллу, А.С. Дешпанде, Е. Витяев. Интерактивное изучение монотонных булевых функций. Информатика 94 (1), 87-118 (1996) ( ссылка )

[ ПРИМЕЧАНИЕ: следующий аргумент, похоже, не работает, но я оставляю его здесь, чтобы другие не делали ту же ошибку / на тот случай, если кто-то может это исправить. Проблема заключается в том, что экспоненциальная нижняя граница для изучения / идентификации монотонной функции, как показано ниже, не обязательно противоречит возрастающему полиномиальному алгоритму для задачи. И именно последнее эквивалентно проверке взаимной двойственности двух монотонных функций за многократное время.]

Я полагаю, что ваша гипотеза о в целом неверна. Если это действительно тот случай, когда требуются протоколы N X запросов, это подразумевает довольно сильную нижнюю границу для изучения монотонных функций с использованием запросов членства . В частности, пусть посетом X булева куба с обычным упорядочением (если вы хотите, X является Powerset из { 1 , . . . , П } с ⊆ в качестве частичного порядка). Число M максимальных антицепей в X удовлетворяет log M $\log N_X$$\log N_X$$X$$X$$\{1,...,n\}$$\subseteq$$M$$X$ [1]. Если ваша идея вжурналеNXверна, то существует некоторый монотонный предикат наX,который требует существенно ( n-$\log M = (1 + o(1))\binom{n-1}{\lfloor n/2 \rfloor}$$\log N_X$$X$запросов. В частности, это подразумевает нижнюю оценку, по существу,2nдля сложности любого алгоритма, решающего эту проблему.$\binom{n-1}{n/2} \approx 2^n$$2^n$

Однако, если я правильно понял ( чего я теперь знаю, что не знал ), ваша проблема эквивалентна проверке взаимной двойственности двух монотонных функций, что можно сделать за квазиполиномиальное время (см. Введение в этой статье Биоч и Ибараки , которые цитируют Фредмана и Хачияна), противоречат всему, что близко к нижней границе .$2^n$

[1] Ливиу Ильинка и Джефф Кан. Подсчет максимальных антицепей и независимых множеств . Arxiv: 1202.4427