Considere un vector de variables , y un conjunto de restricciones lineales especificadas por .
Además, considere dos politopos
donde 's y g ' s son asignaciones afines . A saber, son de la forma → c ⋅ → x + d . (Observamos que P 1 y P 2 son politopos porque son "mapeos afines" del politopo A → x ≤ b .)
La pregunta es, ¿cómo decidir si y P 2 son iguales como conjuntos? ¿Cuál es la complejidad?
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?
Respuestas:
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 ⋅ → x ≤ bP1 P2
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
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.
fuente
fuente