The relation between 2SAT and 3SAT
-
02-11-2019 - |
Pregunta
Show that proving 2SAT is not NP-Complete would prove that 3SAT is not in P.
Or eqivalently -
Show that proving 3SAT is in P would prove that 2SAT is NP-Complete.
I can see there is an easy reduction from 2SAT to 3SAT and it seems like it is the key here, but I can't quite prove the statement above. Can anyone help?
No hay solución correcta
Licenciado bajo: CC-BY-SA con atribución
No afiliado a cs.stackexchange