Verificando a equivalência de dois politopos

14

Considere um vetor de variáveis e um conjunto de restrições lineares especificado por .xAxb

Além disso, considere dois politopos

P1={(f1(x),,fm(x))Axb}P2={(g1(x),,gm(x))Axb}

onde e são mapeamentos afins . Ou seja, eles têm a forma . (Observamos que e são politopos porque são "mapeamentos afins" do politopo .)gfgcx+dP1P2Axb

A questão é: como decidir se e são iguais em conjuntos? Qual é a complexidade?P1P2

A motivação do problema é das redes de sensores, mas parece ser um problema de geometria adorável (provavelmente básico?). Pode-se resolver isso exptime, possivelmente enumerando todos os vértices de e , mas existe uma abordagem melhor?P1P2

maomao
fonte
2
O que você quer dizer com dois politopos sendo equivalentes? Três interpretações imediatamente me vêm à mente: iguais em conjuntos, equivalentes afinamente e equivalentes combinatoriamente. As duas respostas existentes assumem interpretações diferentes.
Tsuyoshi Ito
Quero dizer igual a conjuntos.
maomao 22/09/2015
Edite a pergunta para incluir esse esclarecimento. Não deixe nos comentários. As perguntas devem ser independentes: as pessoas não precisam ler os comentários para entender o que você está perguntando. Obrigado.
DW

Respostas:

12

Não posso dizer com certeza se você considerará a melhor abordagem a seguir, mas, do ponto de vista teórico da complexidade, há uma solução mais eficiente. A idéia é reformular sua pergunta na teoria de primeira ordem dos racionais com adição e ordem. Você tem que está incluído em P 2 se e somente se Φ : = x . y . ( A xbP1P2 é válido. É claro como a equivalência derivam deP1eP2da mesma maneira. AgoraΦpossui um prefixo fixo de quantificação-alternância e, consequentemente, é decidível emΠP2, o segundo nível da hierarquia polinomial-temporal (Sontag, 1985

Φ: =x.y.(UMAxb(UMAyb1EumfEu(x)=gEu(y)))
P1P2ΦΠ2P) Estou bastante confiante de que é possível também provar uma correspondência limite inferior, eu lembro de ter lido em algum lugar que a inclusão entre dois polytopes é -Hard.Π2P

Se você estiver procurando por suporte de ferramentas para resolver esses problemas na prática, os solucionadores de SMT modernos, como o z3, apoiam totalmente essa teoria.

Christoph Haase
fonte
5

UMAxbP1P2UMAbUMAb

Denis Pankratov
fonte
2
Eu não acho que esse argumento funcione - ele ignora a dimensão do simplex dada pelo teorema citado. (x é parte da entrada, portanto, qualquer redução precisa ter certeza que é polinomialmente limitada)
Colin McQuillan
Bom ponto! Parece que minha reivindicação ainda deve ser aprovada, mas temos que entrar na prova do artigo que citei. Começando com um gráfico, eles constroem um polítopo, de modo que dois gráficos sejam isomórficos se e somente se os polítopos correspondentes forem isomórficos. Seus polítopos têm um número polinomial de vértices e suas descrições de vértices podem ser calculadas em tempo polinomial. Assim, podemos considerar que (A, b) é um simplex na dimensão que é o número de vértices ef é a projeção afim que fornece o politopo que pode ser obtido a partir da descrição do vértice.
Denis Pankratov