Data Structures and Algorithms

   

A Heuristic Algorithm for the Solution of SAT in Polynomial Time

Authors: Valdir Monteiro dos Santos Godoi

Usando um novo conceito de linguagem variável, já provei anteriormente que P≠NP, mas tal prova não utilizou nenhum dos problemas clássicos conhecidos como NP-completos, a exemplo de SAT (satisfatibilidade, satisfiability), caixeiro-viajante (travelling-salesman), soma de subconjuntos (subset-sum), da mochila (knapsack), programação linear inteira (integer linear programming), etc. Tal prova não implica que sendo P≠NP então devemos ter NP-completo ∉P, ou seja, os mencionados famosos problemas difíceis podem ainda ser resolvidos em tempo polinomial, sem precisar encerrar a pesquisa nesta direção. Tal como ocorre com o método simplex, que pode resolver em tempo polinomial a grande maioria dos problemas de programação linear, também é possível resolver SAT em tempo polinomial na maioria das vezes, que é o que eu mostro neste trabalho.

Comments: 40 Pages. A primeira versão deste artigo foi meu trabalho de Métodos em Pesquisa Operacional (PM015), IMECC-UNICAMP.

Download: PDF

Submission history

[v1] 2018-07-02 02:25:42
[v2] 2018-07-12 18:01:28
[v3] 2018-07-20 12:41:10
[v4] 2018-08-09 13:48:59

Unique-IP document downloads: 11 times

Vixra.org is a pre-print repository rather than a journal. Articles hosted may not yet have been verified by peer-review and should be treated as preliminary. In particular, anything that appears to include financial or legal advice or proposed medical treatments should be treated with due caution. Vixra.org will not be responsible for any consequences of actions that result from any form of use of any documents on this website.

Add your own feedback and questions here:
You are equally welcome to be positive or negative about any paper but please be polite. If you are being critical you must mention at least one specific error, otherwise your comment will be deleted as unhelpful.

comments powered by Disqus