Autor Tema: NP-Completitud en cuestión: proc lineal resuelve satisfacibilidad booleana.

0 Usuarios y 1 Visitante están viendo este tema.

22 Agosto, 2018, 07:10 am
Leído 2703 veces

Elius

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 399
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
https://www.academia.edu/s/da61caba7e/linear-sat-decider-np-completeness-in-question?source=link

Usa una técnica ya usada en los algoritmos DPLL (Davis-Putnam-Logemann-Lovelandes), el backtracking.
La diferencia es que lo usa desde el comienzo, no cuando surge un conflicto. Y cuando surge un conflicto no hay disparadas exponenciales (exponencial throws), al parecer.
Puede ser que sea útil en la práctica, aún si no resuelve del todo el problema teórico. Pues si hay alguna incorrección detectable, tal que se pueda acotar su alcance de antemano, o alguna disparada exponencial, también acotable, sería útil para la industris.

Saludos.


23 Agosto, 2018, 10:51 pm
Respuesta #1

Elius

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 399
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino