Atenção: Todas as denúncias são sigilosas e sua identidade será preservada.
Os campos nome e e-mail são de preenchimento opcional
Metadados | Descrição | Idioma |
---|---|---|
Autor(es): dc.contributor | Giménez-Lugo, Gustavo Alberto | - |
Autor(es): dc.contributor | Silva, Murilo Vicente Gonçalves da | - |
Autor(es): dc.contributor | Silva, Murilo Vicente Gonçalves da | - |
Autor(es): dc.contributor | Sdroievski, Nicolas Mocelin | - |
Autor(es): dc.contributor | Tacla, Cesar Augusto | - |
Autor(es): dc.contributor | Dorini, Leyza Baldo | - |
Autor(es): dc.creator | Bichibichi, Yuri Socher | - |
Data de aceite: dc.date.accessioned | 2022-02-21T22:19:03Z | - |
Data de disponibilização: dc.date.available | 2022-02-21T22:19:03Z | - |
Data de envio: dc.date.issued | 2020-11-11 | - |
Data de envio: dc.date.issued | 2020-11-11 | - |
Data de envio: dc.date.issued | 2018-11-29 | - |
Fonte completa do material: dc.identifier | http://repositorio.utfpr.edu.br/jspui/handle/1/9249 | - |
Fonte: dc.identifier.uri | http://educapes.capes.gov.br/handle/capes/672475 | - |
Descrição: dc.description | 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. | - |
Descrição: dc.description | 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. | - |
Formato: dc.format | application/pdf | - |
Idioma: dc.language | pt_BR | - |
Publicador: dc.publisher | Universidade Tecnológica Federal do Paraná | - |
Publicador: dc.publisher | Curitiba | - |
Publicador: dc.publisher | Brasil | - |
Publicador: dc.publisher | Bacharelado em Sistemas de Informação | - |
Publicador: dc.publisher | UTFPR | - |
Direitos: dc.rights | openAccess | - |
Palavras-chave: dc.subject | Complexidade computacional | - |
Palavras-chave: dc.subject | Árvores (Teoria dos grafos) | - |
Palavras-chave: dc.subject | Álgebra booleana | - |
Palavras-chave: dc.subject | Computational complexity | - |
Palavras-chave: dc.subject | Trees (Graph theory) | - |
Palavras-chave: dc.subject | Algebra, Boolean | - |
Palavras-chave: dc.subject | CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO | - |
Título: dc.title | Limitante inferior para SAT e consequências | - |
Título: dc.title | Lower-bound for SAT and consequences | - |
Tipo de arquivo: dc.type | livro digital | - |
Aparece nas coleções: | Repositorio Institucional da UTFPR - RIUT |
O Portal eduCAPES é oferecido ao usuário, condicionado à aceitação dos termos, condições e avisos contidos aqui e sem modificações. A CAPES poderá modificar o conteúdo ou formato deste site ou acabar com a sua operação ou suas ferramentas a seu critério único e sem aviso prévio. Ao acessar este portal, você, usuário pessoa física ou jurídica, se declara compreender e aceitar as condições aqui estabelecidas, da seguinte forma: