Comprobación de equivalencia de dos politopos

14

Considere un vector de variables x , y un conjunto de restricciones lineales especificadas por Axb .

Además, considere dos politopos

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

donde 's y g ' s son asignaciones afines . A saber, son de la forma cx + d . (Observamos que P 1 y P 2 son politopos porque son "mapeos afines" del politopo A xb .)fsolcx+rePAG1PAG2UNXsi

La pregunta es, ¿cómo decidir si y P 2 son iguales como conjuntos? ¿Cuál es la complejidad?PAG1PAG2

La motivación del problema proviene de las redes de sensores, pero parece ser un problema de geometría encantador (¿probablemente básico?). Uno puede resolver esto en tiempo de ejecución, posiblemente enumerando todos los vértices de y P 2 , pero ¿hay un mejor enfoque?PAG1PAG2

maomao
fuente
2
¿Qué quieres decir con dos politopos equivalentes? Inmediatamente me vienen a la mente tres interpretaciones: igual que conjuntos, equivalente afín y equivalente combinatoriamente. Las dos respuestas existentes suponen interpretaciones diferentes.
Tsuyoshi Ito
Me refiero a igual que los conjuntos.
maomao
Edite la pregunta para incluir esa aclaración. No lo dejes solo en los comentarios. Las preguntas deben ser independientes: las personas no deberían tener que leer los comentarios para comprender lo que está preguntando. Gracias.
DW

Respuestas:

12

No puedo decir con certeza si considerará mejor el siguiente enfoque, pero desde un punto de vista teórico de la complejidad hay una solución más eficiente. La idea es reformular su pregunta en la teoría de primer orden de los racionales con suma y orden. Tienes que está incluido en P 2 si y solo si Φ : = x . y . ( A xbP1P2 es válido. Está claro cómo derivar la equivalencia deP1yP2de la misma manera. AhoraΦtiene un prefijo de alternancia de cuantificador fijo y, en consecuencia, es decidible enΠP2, el segundo nivel de la jerarquía de tiempo polinomial (Sontag, 1985

Φ:=x.y.(Axb(Ayb1imfi(x)=gi(y)))
P1P2ΦΠ2P) Estoy bastante seguro de que es posible probar también un límite inferior coincidente, recuerdo haber leído en alguna parte que la inclusión entre dos politopos es -duro.Π2P

Si está buscando soporte de herramientas para resolver tales problemas en la práctica, los solucionadores SMT modernos como z3 respaldan completamente esta teoría.

Christoph Haase
fuente
5

AxbP1P2AbAb

Denis Pankratov
fuente
2
No creo que este argumento funcione: ignora la dimensión del símplex dada por el teorema citado. (x es parte de la entrada, por lo que cualquier reducción debe asegurarse de que esté limitada polinomialmente)
Colin McQuillan
¡Buen punto! Parece que mi reclamo aún debe pasar, pero tenemos que entrar en la prueba en el documento que cité. Comenzando con un gráfico, construyen un politopo, de modo que dos gráficos son isomorfos si y solo si los politopes correspondientes son isomorfos. Sus politopos tienen un número polinómico de vértices, y sus descripciones de vértices se pueden calcular en tiempo polinómico. Por lo tanto, podemos tomar (A, b) para ser un símplex en la dimensión que es el número de vértices y f para ser la proyección afín que da el politopo que se puede obtener de la descripción del vértice.
Denis Pankratov