¿Las sumas de Minkowski de conjuntos "convexos" cerrados hacia arriba en$\mathbb{N}^k$ siguen siendo "convexos"? (ERA: Comparación de los costos de maná en Magic: The Gathering)

Question

Este fue originalmente una pregunta sobre la comparación de los costes de maná en Magic: The Gathering, pero se ha convertido en una pregunta acerca de Minkowski sumas de arriba-cerrado conjuntos convexos en $\mathbb{N}^k$. La pregunta original se conserva a continuación, si desea ver la motivación original (o una respuesta a la pregunta original que no oso en esta nueva).

La pregunta es esta, decir que tenemos dos poliedros convexos $A$ e $B$ en $\mathbb{R}_{\ge0}^k$ cuyos vértices se encuentran en el entramado $\mathbb{Z}^k$ ("están celosía poliedros"); y dicen, además, que tanto $A$ e $B$ son hacia arriba cerrado en el obvio de orden parcial (es decir, para cada uno de ellos, la recesión de cono es igual a $\mathbb{R}_{\ge0}^k$). A continuación, se $(A+B)\cap \mathbb{Z}^k=(A\cap\mathbb{Z}^k)+(B\cap\mathbb{Z}^k)$?

Esta pregunta parece ser más frecuentes en el caso de que $A$ e $B$ son polytopes, que es acotado, que es a la vez tienen la recesión de cono igual a $\{0\}$ en lugar de a $\mathbb{R}_{\ge0}^k$. En este caso la respuesta es no, y sólo para probar las condiciones bajo las que se tiene es lo mejor que me puede decir un problema abierto en dimensiones mayores que 2. Pero me pregunto si en este contexto alternativo el problema es más fácil.

Esa es la pregunta; pero si quieres saber qué tiene esto que ver con los costes de maná en Magic: The Gathering, o si sería más fácil responder a la pregunta original en lugar de esto, sigue leyendo...

---

Sí, esta es una combinatoria pregunta, tratando con algo parecido a elecciones, donde a veces un vértice es permitido para que coincida con otros dos vértices en lugar de uno solo, como de costumbre! Pero surge de la Magia y, entonces, se necesita algún tipo de configuración para el estado. (Yo sin duda estaría interesado en generalizaciones, también.)

Antecedentes: En Magic: The Gathering, hay 6 tipos de "maná", que se denota {W}, {U}, {B}, {R}, {G} (los 5 colores de maná), y {C} (maná incoloro). (También podemos imaginar un 7 tipo, {P}, lo que representa 2 la vida; esto no es propiamente un tipo de maná.) Maná viene en número entero cantidades; por una "cantidad de maná" me refiero a un determinado número entero cantidad de cada tipo (y cierta cantidad de vida, supongo). Un coste de maná se describe un conjunto de cantidades de maná suficiente para pagar el costo. Un coste de maná se compone de un cierto número de los siguientes símbolos:

• {W}, {U}, {B}, {R}, {G} -- pagar sólo por 1 maná de ese color
• {C} -- pagar sólo por 1 maná incoloro
• {W/U}, {U/B}, {B/R}, {R/G} {G/W}, {W/B}, {U/R}, {B/G}, {R/W}, {G/U} -- a pagar por 1 maná de cualquier color apropiado (todos los 10 pares de colores se muestran aquí)
• {1} -- a pagar por 1 maná de cualquier tipo, color o incoloro
• {W/P}, {U/P}, {B/P}, {R/P}, {G/P} -- a pagar por el color adecuado o 2 de vida (lo que podemos pensar como un ficticio tipo de maná, {P})
• {2/W}, {2/U}, {2/B}, {2/R}, {2/G} -- a pagar por el color de maná o por cualquiera de los 2 de maná (en color o incoloro)

(Sí, para aquellos familiarizados con la Magia, estoy ignorando {X} y estoy ignorando la pregunta de la nieve, ya que no afectan seriamente el problema. De hecho, nosotros en realidad no se necesitan todas las anteriores, pero pensé que había que ser cuidadoso...)

Podemos poner un orden parcial en el conjunto de los costes de maná de la siguiente manera: a≤B si cualquier cantidad de maná suficiente para pagar B, es suficiente para pagar por A.

Entonces, la pregunta es, dados dos costes de maná, ¿cómo podemos determinar si uno es menor que igual a otro o no?

Si ignoramos la existencia de los símbolos de la forma {2/M}, entonces este problema no es difícil; el uso de la Sala de matrimonio teorema, podemos ver que uno sólo tiene que comprobar una serie de desigualdades, en concreto, que para cada conjunto S de los tipos de maná (incluyendo la ficticia {P}), el número de símbolos de maná en Una correspondiente a un subconjunto de S debe ser no más que el número de símbolos de maná en B, correspondiente a un subconjunto de S. Esto nos da más que 2^7 las desigualdades de verificación (de hecho, dado que los símbolos que existen en la realidad uno sólo necesita comprobar 65 de ellos).

Pero el {2/M} los símbolos son más de un problema. Debido a que puede corresponder a la 1 o 2 de maná, el matrimonio teorema no se aplica. Una manera de manejar esto es desambiguación -- cada {2/M} símbolo puede ser ambiguas a {2} o {M}. Entonces a≤B iff para cada desambiguación B' de B hay algunos desambiguación Un' de Un tal que A' = B'.

Sin embargo, esto es lento en el peor de los casos, debido a que se requiere la comprobación de un montón de disambiguations. Mi pregunta es: ¿Podemos hacerlo mejor?

Que la hipótesis de las dos siguientes instrucciones que le ayudará a reducir el número de disambiguations necesaria cuando los símbolos de la forma {2/M} están involucrados:

1. La cancelación se aplica. Que es: Si definimos la suma de los costes de maná de una manera obvia, es claro que $a\le b$ implica $a+c\le b+c$. Si no permitimos que los símbolos de la forma {2/M}, lo contrario también es, por el razonamiento anterior. Pregunta: ¿también se mantienen cuando tales símbolos son permitidos? Edit: parece una respuesta positiva a la #3 implica una respuesta positiva a esta (ver comentarios). Estoy retitling la pregunta para centrarse en el #3.

2. Supongamos que tenemos costes de maná de a y B y supongamos que M es un color que el símbolo {2/M} no ocurre en A. Es true, entonces a≤B si y sólo si a≤B, donde B' se compone de B, pero con todas las instancias de {2/M} reemplazado por {1}? (EDIT: Refutada en los comentarios por el Ritmo de Nielsen. No obstante, si se requiere Una no tiene símbolos de la forma {2/M} para todos los colores M (de nuevo, boceto en los comentarios), pero por desgracia, que forma más débil no forma una parte útil de la informática, el fin de la relación.)

3. (Añadido después de que Se Sawin frecuentes en los comentarios) - es el conjunto de cantidades de maná suficiente para pagar por un determinado coste de maná (incluyendo la ficticia {P}) igual a la de un poliedro convexo se cruzaba con el entero de celosía? (O entero cantidades de maná y hasta los importes de la vida, si usted prefiere pensar de esa manera.) Si es así esto podría darnos una manera más rápida de comparar de desambiguación, mediante la comparación de los conjuntos convexos (asumiendo que puede determinarse rápidamente; no estoy seguro de que se puede). (Esto es sin duda cierto, si hacemos caso de los símbolos de la forma {2/M}, por las razones arriba mencionadas.) Tenga en cuenta que es importante aquí, que nos permiten pagar en exceso; no es cierto si no (ver comentarios).

(No creo que haya ninguna manera de deshacerse de la necesidad de realizar al menos algunas disambiguations; si tiene más de algunos {2/M} el símbolo que la B, creo que sólo se va a tener que manejar manualmente. Pero tanto las declaraciones anteriores, al menos, iba a bajar a sólo haciendo eso.)

Hasta ahora no he sido capaz de probar estos trabajos, ni encontrar ningún contraejemplo. ¿Alguien puede probar o refutar estas?

Además, como yo dije que iba a estar interesado en ver las generalizaciones. Mientras cada símbolo corresponde a 1 de maná toda la cosa se reduce a que el matrimonio teorema como he dicho anteriormente. Pero cuando los símbolos pueden corresponder a diferentes cantidades yo no esperaría a funcionar tan bien en general. Parece que todavía funcionan muy bien para el conjunto de símbolos que existen en la realidad, como se indica anteriormente (aunque puedo estar equivocado!). Hay algunos abstractos de la propiedad de este conjunto de símbolos que la causa de esta, por lo que podemos decir cuando este tipo de cosas sucede? Sería interesante para ver.

Muchas gracias a todos!

Answer 1

A mí me parece que todos los de la norma contra-ejemplos para la polytope cuestión de adaptarse fácilmente a ser contador ejemplos a esta pregunta: Tomar cualquier polytopes en $\mathbb{Z}^{k-1}$ con $(A_0+B_0) \cap \mathbb{Z}^{k-1} \neq (A_0 \cap \mathbb{Z}^{k-1}) + (B_0 \cap \mathbb{Z}^{k-1})$. Incrustar $\mathbb{Z}^{k-1}$ a $\mathbb{Z}^k$ as $\{ (x_1, \ldots, x_k) : \sum x_i=0 \}$. Deje $A$ e $B$ ser la sumas de Minkowski $A_0+\mathbb{Z}_{\geq 0}^k$ e $B_0 + \mathbb{Z}_{\geq 0}^k$. Entonces $(A+B) \cap \mathbb{Z}^{k-1} = (A_0+B_0) \cap \mathbb{Z}^{k-1}$, $A \cap \mathbb{Z}^{k-1}=A_0\cap \mathbb{Z}^{k-1}$ y $B \cap \mathbb{Z}^{k-1}=B_0\cap \mathbb{Z}^{k-1}$, lo $A$ e $B$ tienen el mismo problema.

Como un ejemplo concreto, tome $A_0 = \mathrm{Hull}( (0,0,0),\ (1,1,-2))$ e $B_0 = \mathrm{Hull}( (1,0,-1),\ (0,1,-1))$. A continuación,$(1,1,-2) \in A_0 + B_0$, pero no se en $(A_0 \cap \mathbb{Z}^3) + (B_0 \cap \mathbb{Z}^3)$. Tome $A = A_0 + \mathbb{Z}_{\geq 0}^3$ e $B = B_0 + \mathbb{Z}_{\geq 0}^3$ y vemos exactamente el mismo problema con la recesión de los conos de su pedido.