Acerca de este libro electrónico
The theoretically polynomial algorithm (of quartic order) that we show helped us to reinforce our theory, and to consider that even if in the future it will be shown that there are physical limits (P != NP) that condition and will condition algorithm design forever. These limits could be transcended thanks to use the abstraction as another computational resource. This resource, which is independent of space and time, could tend to grow exponentially even though the temporal and spatial resources that our computing machine would use remain bounded in polynomial terms.
In this book, you will be able to see how thanks to the use of abstraction, we can compute the entire set of satisfiable configurations of a 3-SAT instance. Later, if the set is not empty, we will read one certificate (satisfacible assigments); just like we did, in our research work, to abstractly build and compute the set of all Hamiltonian cycles or TSP tours.
We are aware of the widespread skepticism that exists around any attempt to design a polynomial algorithm for an NP-Complete problem such as 3-SAT. However, you are welcome to give this algorithm (for 3-SAT) and our other algorithms (for HC, TSP, n-Queens) the benefit of the doubt. In fact, we can say that the logic of this algorithm is much simpler (and therefore easier to understand) than the one we required to implement in our main work for HC and TSP.
