Можно ли эффективно равномерно выбрать соседа вершины в графе многогранника?

У меня есть многогранник определенный как .$P$$\{ x : Ax \leq b, x \geq 0\}$

Вопрос: Учитывая вершину из P , есть ли алгоритм полиномиального времени для равномерной выборки из соседей v в графе P ? (Многочлен в измерении, число уравнений и представление б . Я могу предположить, что число уравнений является полиномиальным в измерении.)$v$$P$$v$$P$$b$

Обновление: я думаю, что я смог показать, что это сложный NP, см. Мой ответ, который объясняет аргумент. (И под $NP$ жестким я подразумеваю, что алгоритм за полиномиальное время докажет $RP = NP$ ... не уверен, какая здесь правильная терминология.)

Обновление 2: есть 2-строчное доказательство $NP$ -твердости (учитывая правильный комбинаторный многогранник), и мне удалось найти его в статье Хачияна. Смотрите ответ для описания и ссылку. :-D

Эквивалентная проблема :

В комментариях Петр Шор указал, что этот вопрос эквивалентен вопросу о том, можем ли мы равномерно выбирать из вершин данного многогранника. (Я думаю, что эквивалентность выглядит следующим образом: в одном направлении мы можем перейти от многогранника $P$ с вершиной $v$ к фигуре вершины в $v$ , $P/v$ , и выборка вершин $P/v$ эквивалентна выборке соседей $v$ на $P$ В другом направлении мы можем перейти от многогранника $P$ к многограннику $Q$ одного более высокого измерения, добавив конус с вершиной $v$ и основанием $P$, Тогда выборка соседей $v$ в $Q$ эквивалентна выборке вершин $P$ )

Эта формулировка вопроса уже задавалась ранее: /mathpro/319930/sampling-uniformly-from-the-vertices-of-a-polytope

Изменить 2: смущающе, есть две строки доказательства $NP$ -твердости, если начать с правильного многогранника.

Во-первых, вспомнить циркулярный многогранник графа внизу страницы 4 Трудно сгенерировать все вершины многогранника .

Его вершины находятся в биективном соответствии с направленными простыми циклами. Поэтому их трудно отобрать или подсчитать по предложению СП 5.1 . :-D

С помощью этих ключевых слов я смог найти сложность результата выборки в виде теоремы 1 о поперечных гиперграфах и семействах многогранных конусов Хачияна.

Изменить: я записал аргумент ниже, и он выглядит правильно. Тем не менее, есть гораздо более простой аргумент, который я изложу здесь:

а) Анализ алгоритмов возврата для перечисления всех вершин и всех граней выпуклого многогранника (Фукуда и др.) сильно затрудняет решение следующей задачи на многогранниках:

Вход: многогранник $Ax = b , x \geq 0$ в $\mathbb{R}^n$ подмножестве $S \subseteq n$

Вывод: существует ли вершина $v$ из $P$ , которая отлична от нуля на каждой из координат в $S$ .

б) Учитывая это, можно сделать следующую конструкцию: ввести новые переменные $y_{ik}$ для $i \in S$ и $k = 1, \ldots, d$ и ввести неравенство $0 \leq y_{ik} \leq x_i$ . Назовите получившийся многогранник $P_{S,d}$ . Смысл этой конструкции состоит в том, чтобы ввести гиперкуб над каждой вершиной размерности $d |supp(x) \cap S|$,

в) Можно проверить, что все вершины этого многогранника лежат над вершинами старого многогранника и что число вершин над вершиной равно $2^{d | supp(x) \cap S|}$где $supp$ - функция, которая отправляет вершину в координаты, где она отлична от нуля.

d) Из обычной цепочки аргументов типа бигонов следует, что, беря $d$ достаточно большого размера, равномерная выборка из вершин $P_{S,d}$ (с высокой вероятностью) даст выборку из вершин, максимизирующую размер их пересечения с $S$ ,

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

(Раньше здесь был старый аргумент - он есть в истории редактирования. Я удалил его, потому что он очень длинный и помешает найти правильный ответ на вопрос.)