Limitante inferior para SAT e consequências

Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.contributorGiménez-Lugo, Gustavo Alberto-
Autor(es): dc.contributorSilva, Murilo Vicente Gonçalves da-
Autor(es): dc.contributorSilva, Murilo Vicente Gonçalves da-
Autor(es): dc.contributorSdroievski, Nicolas Mocelin-
Autor(es): dc.contributorTacla, Cesar Augusto-
Autor(es): dc.contributorDorini, Leyza Baldo-
Autor(es): dc.creatorBichibichi, Yuri Socher-
Data de aceite: dc.date.accessioned2022-02-21T22:19:03Z-
Data de disponibilização: dc.date.available2022-02-21T22:19:03Z-
Data de envio: dc.date.issued2020-11-11-
Data de envio: dc.date.issued2020-11-11-
Data de envio: dc.date.issued2018-11-29-
Fonte completa do material: dc.identifierhttp://repositorio.utfpr.edu.br/jspui/handle/1/9249-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/capes/672475-
Descrição: dc.descriptionIn 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.-
Descrição: dc.descriptionNeste 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.-
Formato: dc.formatapplication/pdf-
Idioma: dc.languagept_BR-
Publicador: dc.publisherUniversidade Tecnológica Federal do Paraná-
Publicador: dc.publisherCuritiba-
Publicador: dc.publisherBrasil-
Publicador: dc.publisherBacharelado em Sistemas de Informação-
Publicador: dc.publisherUTFPR-
Direitos: dc.rightsopenAccess-
Palavras-chave: dc.subjectComplexidade computacional-
Palavras-chave: dc.subjectÁrvores (Teoria dos grafos)-
Palavras-chave: dc.subjectÁlgebra booleana-
Palavras-chave: dc.subjectComputational complexity-
Palavras-chave: dc.subjectTrees (Graph theory)-
Palavras-chave: dc.subjectAlgebra, Boolean-
Palavras-chave: dc.subjectCNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO-
Título: dc.titleLimitante inferior para SAT e consequências-
Título: dc.titleLower-bound for SAT and consequences-
Tipo de arquivo: dc.typelivro digital-
Aparece nas coleções:Repositorio Institucional da UTFPR - RIUT

Não existem arquivos associados a este item.