Use este identificador para citar ou linkar para este item: http://repositorio.roca.utfpr.edu.br/jspui/handle/1/11596
Título: Limitante inferior para SAT e consequências
Título(s) alternativo(s): Lower-bound for SAT and consequences
Autor(es): Bichibichi, Yuri Socher
Orientador(es): Giménez-Lugo, Gustavo Alberto
Palavras-chave: Complexidade computacional
Árvores (Teoria dos grafos)
Álgebra booleana
Computational complexity
Trees (Graph theory)
Algebra, Boolean
Data do documento: 29-Nov-2018
Editor: Universidade Tecnológica Federal do Paraná
Câmpus: Curitiba
Referência: BICHIBICHI, Yuri Socher. Limitante inferior para SAT e consequências. 2018. 39 f. Trabalho de Conclusão de Curso (Bacharelado em Sistemas de Informação) - Universidade Tecnológica Federal do Paraná, Curitiba, 2018.
Resumo: Neste trabalho é realizado um levantamento sobre os recentes limitantes inferiores em tempo e espaço para o problema SAT. Também é demonstrada uma prova alternativa para EXP ≠ EXPSPACE ⇒ P ≠ PSPACE sem utilizar argumento de preenchimento. Em seguida é feita uma demonstração original de que PSPACE ≠ NEXP ⇒ NP ⊄ PolyL. Este resultado pode ser usado para provar melhores limitantes inferiores para SAT utilizando memória logarítmica e pode auxiliar na busca da solução do problema P vs L.
Abstract: In this work is realized a survey about recents time and space lower-bounds for SAT problem. Also, is demonstrated an alternative proof for EXP ≠ EXPSPACE ⇒ P ≠ PSPACE without using padding argument. After that is shown an original demonstration that PSPACE ≠ NEXP ⇒ NP ⊄ PolyL. This result can be used to prove betters lower-bounds for SAT with memory logarithmic and can help the search for the solution of the problem P vs L.
URI: http://repositorio.roca.utfpr.edu.br/jspui/handle/1/11596
Aparece nas coleções:CT - Sistemas de Informação

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
CT_COSIS_2018_2_03.pdf568,17 kBAdobe PDFVisualizar/Abrir


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.