Limitante inferior para SAT e consequências

Bichibichi, Yuri Socher

Use este identificador para citar ou linkar para este item: http://repositorio.utfpr.edu.br/jspui/handle/1/9249

Registro completo de metadados

Campo DC	Valor	Idioma
dc.creator	Bichibichi, Yuri Socher
dc.date.accessioned	2020-11-12T12:02:36Z	-
dc.date.available	2020-11-12T12:02:36Z	-
dc.date.issued	2018-11-29
dc.identifier.citation	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.	pt_BR
dc.identifier.uri	http://repositorio.utfpr.edu.br/jspui/handle/1/9249	-
dc.description.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.	pt_BR
dc.language	por	pt_BR
dc.publisher	Universidade Tecnológica Federal do Paraná	pt_BR
dc.rights	openAccess	pt_BR
dc.subject	Complexidade computacional	pt_BR
dc.subject	Árvores (Teoria dos grafos)	pt_BR
dc.subject	Álgebra booleana	pt_BR
dc.subject	Computational complexity	pt_BR
dc.subject	Trees (Graph theory)	pt_BR
dc.subject	Algebra, Boolean	pt_BR
dc.title	Limitante inferior para SAT e consequências	pt_BR
dc.title.alternative	Lower-bound for SAT and consequences	pt_BR
dc.type	bachelorThesis	pt_BR
dc.description.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.	pt_BR
dc.degree.local	Curitiba	pt_BR
dc.publisher.local	Curitiba	pt_BR
dc.contributor.advisor1	Giménez-Lugo, Gustavo Alberto
dc.contributor.advisor-co1	Silva, Murilo Vicente Gonçalves da
dc.contributor.referee1	Silva, Murilo Vicente Gonçalves da
dc.contributor.referee2	Sdroievski, Nicolas Mocelin
dc.contributor.referee3	Tacla, Cesar Augusto
dc.contributor.referee4	Dorini, Leyza Baldo
dc.publisher.country	Brasil	pt_BR
dc.publisher.program	Bacharelado em Sistemas de Informação	pt_BR
dc.publisher.initials	UTFPR	pt_BR
dc.subject.cnpq	CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO	pt_BR
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

Mostrar registro simples do item Recomendar este item Visualizar estatísticas