Use este identificador para citar ou linkar para este item:
http://repositorio.utfpr.edu.br/jspui/handle/1/9249| 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 |
| Citação: | 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.utfpr.edu.br/jspui/handle/1/9249 |
| Aparece nas coleções: | CT - Sistemas de Informação |
Arquivos associados a este item:
| Arquivo | Descrição | Tamanho | Formato | |
|---|---|---|---|---|
| CT_COSIS_2018_2_03.pdf | 568,17 kB | Adobe PDF |  Visualizar/Abrir |
Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.