Проверка эквивалентности двух многогранников

14

Рассмотрим вектор переменных и набор линейных ограничений, заданных как . $\vec{x}$ $A\vec{x}\leq b$

Кроме того, рассмотрим два многогранника

\begin{aligned} P_{1} & = {(f_{1} (\vec{x}), \dots, f_{m} (\vec{x})) ∣ A \vec{x} \leq b} \\ P_{2} & = {(g_{1} (\vec{x}), \dots, g_{m} (\vec{x})) ∣ A \vec{x} \leq b} \end{aligned}

$\begin{align*} P_1&=\{(f_1(\vec{x}), \cdots, f_m(\vec{x}))\mid A\vec{x}\leq b\}\\ P_2&=\{(g_1(\vec{x}), \cdots, g_m(\vec{x}))\mid A\vec{x}\leq b\} \end{align*}$

где «ы и » ы являются аффинные отображения. А именно, они имеют вид . (Отметим, что и являются многогранниками, потому что они являются «аффинными отображениями» многогранника .) $f$ $g$ $\vec{c}\cdot \vec{x} +d$ $P_1$ $P_2$ $A\vec{x}\leq b$

Вопрос в том, как решить, равны ли и как множества? В чем сложность? $P_1$ $P_2$

Мотивация проблемы связана с сенсорными сетями, но она кажется прекрасной (возможно, базовой?) Геометрической проблемой. Это можно решить в exptime, возможно, перечислив все вершины и , но есть ли лучший подход? $P_1$ $P_2$

cc.complexity-theory linear-algebra linear-programming polytope Maomao
источник

2

Что вы подразумеваете под эквивалентностью двух многогранников? Мне сразу приходят в голову три интерпретации: равные как множества, аффинно эквивалентные и комбинаторно эквивалентные. Два существующих ответа предполагают разные интерпретации.

Цуёси Ито

Я имею в виду равные как наборы.

Maomao

Пожалуйста, отредактируйте вопрос, чтобы включить это разъяснение. Не оставляйте это в комментариях. Вопросы должны быть автономными: людям не нужно читать комментарии, чтобы понять, что вы спрашиваете. Спасибо.

DW

12

Я не могу с уверенностью сказать, считаете ли вы следующий подход лучшим, но с точки зрения теории сложности существует более эффективное решение. Идея состоит в том, чтобы перефразировать ваш вопрос в теории рациональных порядков первого порядка с добавлением и порядком. У вас есть то, что входит в тогда и только тогда, когда $P_1$ $P_2$ . Понятно, как вывести эквивалентностьитаким же образом. Теперьимеет префикс фиксированного квантификатора-чередование, и, следовательнов разрешимом, второй уровень иерархии полиномиального времени (Сонтаг, 1985

\begin{aligned} Φ := \forall \vec{x} . \exists \vec{y} . (A \cdot \vec{x} \leq b ⟹ (A \cdot \vec{y} \leq b \land \underset{1 \leq i \leq m}{⋀} f_{i} (\vec{x}) = g_{i} (\vec{y}))) \end{aligned}

$\begin{align*} \Phi := \forall \vec{x}.\exists \vec{y}.\left( A \cdot \vec{x} \le b \implies \left( A \cdot \vec{y} \le b \wedge \bigwedge_{1\le i\le m} f_i(\vec{x}) = g_i(\vec{y}) \right)\right) \end{align*}$

P_{1}

$P_1$

P_{2}

$P_2$

Φ

$\Phi$

Π_{2}^{P}

$\Pi_2^\text{P}$ ). Я довольно уверен, что можно также доказать соответствие нижней границы, я вспоминаю, что где-то читал, что включение между двумя многогранниками является

-твердым.

Π_{2}^{P}

$\Pi_2^\text{P}$

Если вы ищете инструментальную поддержку для решения таких проблем на практике, современные SMT-решатели, такие как z3, полностью поддерживают эту теорию.

Кристоф Хааз
источник

5

$Ax \le b$ $P_1$ $P_2$ $A$ $b$ $A$ $b$

Денис Панкратов
источник

2

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

Колин Маккуиллан

Хорошая точка зрения! Похоже, что мое утверждение еще должно пройти, но мы должны углубиться в доказательство в статье, которую я привел. Начиная с графа, они строят многогранник, такой, что два графа изоморфны тогда и только тогда, когда соответствующие многогранники изоморфны. Их многогранники имеют полиномиальное количество вершин, а описания их вершин могут быть вычислены за полиномиальное время. Таким образом, мы можем считать (A, b) симплексом в измерении, представляющем собой число вершин, а f - аффинной проекцией, дающей многогранник, который можно получить из описания вершины.

Денис Панкратов

Проверка эквивалентности двух многогранников

Ответы: