Prueba de que el problema de colinealidad es NP completo

Problema : dados 3 puntos a , b , c , la tarea es verificar si estos tres puntos son colineales.

Explicación : una instancia del problema es una entrada especificada para el problema. Una instancia del problema de colinealidad son tres puntos ((ax _, a _y ), (b _x , b _y ), (c _x , c _y )) . Dado que un NP-Completo es un problema que está tanto en NP como en NP-difícil , la prueba de la afirmación de que un problema es NP-Completo consta de dos partes:

El problema en sí está en la clase NP.

Todos los demás problemas en la clase NP pueden ser reducibles en tiempo polinomial a eso.
(B es reducible en tiempo polinomial a C se denota como B ≤ P ^C )

Si solo se cumple la segunda condición, el problema se llama NP-Hard .
Pero no es posible reducir cada problema NP a otro problema NP para mostrar su NP-Completitud todo el tiempo. Por eso, para mostrar que un problema es NP-completo, demuestre que el problema está en NP y cualquier problema NP-Completo es reducible a eso. Así, se puede verificar que el problema de colinealidad es NP-Completo usando las siguientes proposiciones:

El problema de colinealidad está en NP :
si algún problema está en NP, entonces dado un ‘certificado’, que es una solución al problema y una instancia del problema (una colección de tres puntos a , b , c ) podremos identificar (si la solución es correcta o no) certificado en tiempo polinomial. Esto se puede hacer comprobando:

$\frac{b_{y}-a_{y}}{b_{x}-a_{x}}=\frac{c_{y}-b_{y}}{c_{x}-b_{x}}=0$

El problema de colinealidad es NP-Hard :
Para probar que el problema de colinealidad es NP-Hard, deduzca una reducción de un problema NP-Hard conocido , es decir, 3-Suma al problema de colinealidad. Para cada x en la instancia de 3-Suma, asigne de x a (x, x ³ ) . Ahora, de 3 instancias de Suma (x, y, z) tenemos ((x, x ³ ), (y, y ³ ), (z, z ³ )) .
Se cumplen las siguientes proposiciones:

Sea el conjunto S tiene puntos colineales (x, x ³ ), (y, y ³ ), (z, z ³ )
Ahora,

=> $\frac{z^{3}-y^{3}}{zy}=\frac{y^{3}-x^{3}}{yx}=0$

=> $y^{2}+xy+x^{2}=z^{2}+xz+x^{2}$

=> $-xz+xy=z^{2}-y^{2}$

=> $-x=z+y$

=> $x+y+z=0$

Por lo tanto, (x, y, z) son puntos colineales. Estas ecuaciones son intercambiables.
Por lo tanto, el Problema de Colinealidad es NP-Completo .

Publicación traducida automáticamente

Artículo escrito por yashchuahan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta Cancelar la respuesta