Estoy tratando de resolver una tarea (tomada del libro Algorithms - de S. Dasgupta, CH Papadimitriou y UV Vazirani , Capítulo 8, problema 8.6a), y estoy parafraseando lo que dice:
Dado que 3SAT permanece NP-completo incluso cuando se restringe a fórmulas en las que cada literal aparece como máximo dos veces, demuestre que si cada literal aparece como máximo una vez, entonces el problema se puede resolver en tiempo polinómico.
Intenté resolver esto separando las cláusulas en múltiples grupos:
- Cláusulas que no tenían ninguna variable en común con el resto de las cláusulas.
- Cláusulas que solo tenían 1 variable en común
- Cláusulas que tenían 2 variables en común.
- Cláusulas que tenían las 3 variables en común
Mi razonamiento se intentó en el sentido de que el número de tales grupos es finito (debido a la restricción impuesta de que no haya literal presente más de una vez), y podríamos tratar de satisfacer primero al grupo más restringido (grupo 4) y luego sustituir el resultó en los grupos menos restringidos (3, 2 y luego 1), pero me di cuenta de que esto no me estaba llevando a ninguna parte, ya que esto no difiere mucho del caso de la versión restringida de 3SAT en la que puede aparecer cada literal a lo sumo dos veces, que ha demostrado ser NP-completo.
Intenté buscar en línea cualquier pista / solución, pero todo lo que pude obtener fue este enlace , en el que la pista indicada no tenía suficiente sentido para mí, que estoy reproduciendo textualmente aquí:
Cualquier ayuda para descifrar la pista o proporcionar un camino que pueda explorar sería realmente apreciada.
fuente