MAX-2SAT
Contribuições Pedagógicas para o Aprendizado no Escopo da Teoria da Computação
DOI:
https://doi.org/10.20873/uft.2675-3588.2026.v7n2.p1-12Palavras-chave:
Max-2SAT, NP-Completude, Redução Polinomial, Teoria da Complexidade, Satisfatibilidade BooleanaResumo
Este artigo apresenta uma demonstração formal e didática da NP-completude do problema Maximum 2-Satisfiability (Max-2SAT) por meio de redução polinomial a partir do problema Clique. O Max-2SAT, variante de maximização do problema SAT em que cada cláusula contém no máximo dois literais, questiona se existe uma valoração booleana capaz de satisfazer pelo menos k cláusulas de uma fórmula em forma normal conjuntiva. Embora o problema 2-SAT seja resolvido em tempo polinomial, sua versão de maximização é NP-completa. A demonstração utiliza uma construção com variável auxiliar que mapeia estruturas de grafos em fórmulas booleanas, estabelecendo correspondência biunívoca entre cliques e valorações satisfatórias. Como contribuições pedagógicas, o trabalho apresenta: (i) prova formal detalhada de NP-pertinência e NP-dificuldade; (ii) construção explícita da redução Clique <=p Max-2SAT com figuras ilustrativas; (iii) exemplo completo comentado passo a passo; (iv) pseudocódigo do verificador polinomial; e (v) discussões sobre armadilhas comuns e estratégias de compreensão. O material produzido visa facilitar o aprendizado de reduções polinomiais e fortalecer a compreensão sobre a fronteira entre tratabilidade e intratabilidade computacional.
Downloads
Publicado
Como Citar
Licença
Copyright (c) 2026 Raphael Sales de Souza, Thiago Gonzaga dos Santos, Daniel Martins da Silva, Tanilson Dias dos Santos
Este trabalho está licenciado sob uma licença Creative Commons Attribution-NonCommercial 4.0 International License.
Autores que publicam neste periódico concordam com os seguintes termos:
- Autores mantém os direitos autorais e concedem ao periódico o direito de primeira publicação, com o trabalho simultaneamente licenciado sob a Creative Commons Attribution License (CC BY-NC 4.0), permitindo o compartilhamento do trabalho com reconhecimento da autoria do trabalho e publicação inicial neste periódico;
- Autores têm autorização para assumir contratos adicionais separadamente, para distribuição não-exclusiva da versão do trabalho publicada neste periódico (ex.: publicar em repositório institucional ou como capítulo de livro), com reconhecimento de autoria e publicação inicial neste periódico;
- Autores têm permissão e são estimulados a publicar e distribuir seu trabalho online (ex.: em repositórios institucionais ou na sua página pessoal) a qualquer ponto posterior ao processo editorial;
- Além disso, o AUTOR é informado e consente com o periódico que, portanto, seu artigo pode ser incorporado pela Academic Journal on Computing, Engineering and Applied Mathematics em bases e sistemas de informação científica existentes (indexadores e bancos de dados atuais) ou a existir no futuro (indexadores e bancos de dados futuros), nas condições definidas por este último em todos os momentos, que envolverá, pelo menos, a possibilidade de que os titulares desses bancos de dados possam executar as seguintes ações sobre o artigo:
- Reproduzir, transmitir e distribuir o artigo, no todo ou em parte sob qualquer forma ou meio de transmissão eletrônica existente ou desenvolvida no futuro, incluindo a transmissão eletrônica para fins de pesquisa, visualização e impressão;
- Reproduzir e distribuir, no todo ou em parte, o artigo na impressão;
- Traduzir certas partes do artigo;
- Extrair figuras, tabelas, ilustrações e outros objetos gráficos e capturar metadados, legendas e artigo relacionado para fins de pesquisa, visualização e impressão;
- Transmissão, distribuição e reprodução por agentes ou autorizada pelos proprietários de distribuidoras de bases de dados;
- A preparação de citações bibliográficas, sumários e índices e referências de captura relacionados de partes selecionadas do artigo;
- Digitalizar e / ou armazenar imagens e texto de artigo eletrônico.
