摘要
There are a large number of papers that claim that there are problems that once solved lead to an efficient solution of a wide range of problems, classified as NP. In this paper we will not only question the existence of this class of NP-co problems, but we will also explain their limitations in engineering and give a polynomial-time solution to SAT, one of these emblematic problems. The resolution will be so trivial that it will even be possible to practice it on paper.
There are a large number of papers that claim that there are problems that once solved lead to an efficient solution of a wide range of problems, classified as NP. In this paper we will not only question the existence of this class of NP-co problems, but we will also explain their limitations in engineering and give a polynomial-time solution to SAT, one of these emblematic problems. The resolution will be so trivial that it will even be possible to practice it on paper.
作者
Dato Ruiz
Juan Manuel
Dato Ruiz;Juan Manuel(Instituto Estudios Superiores Carlos III, Cartagena, España)
