Sobre algunas clases polinomiales de satisfacibilidad : Aplicaciones a la resolución de problemas geométricos

Abstract

La Geometría Computacional posee un vasto campo de aplicaciones en las áreas de las Ciencias de Información Geográfica, Electrónica y Computación, entre muchas otras. En estos campos, los problemas de etiquetado de mapas, trazados de circuitos integrados o creación de diagramas de flujos y organigramas son ejemplos particulares de problemas cuyas instancias son en muchos casos reducibles al problema de satisfacibilidad proposicional (SAT). Es decir, su resolución puede ser conseguida a partir de la resolución de determinadas instancias de SAT.|