Skip navigation
Use este identificador para citar ou linkar para este item: https://repositorio.ufpe.br/handle/123456789/7639
Título: Uma redução do problema de fatorização de inteiros para o problema de programação 0-1
Autor(es): Happ Botler, Fábio
Palavras-chave: Algoritmos; Análise combinatória
Data do documento: 31-Jan-2011
Editor: Universidade Federal de Pernambuco
Citação: Happ Botler, Fábio; Luiz Soares Lins, Sóstenes. Uma redução do problema de fatorização de inteiros para o problema de programação 0-1. 2011. Dissertação (Mestrado). Programa de Pós-Graduação em Matemática, Universidade Federal de Pernambuco, Recife, 2011.
Resumo: O problema de Fatorização de Inteiros, assim como os outros em NP, pode ser reduzido em tempo polinomial para o problema de Satisfabilidade, devido ao Teorema de Cook. O problema de Satisfabilidade, por sua vez, pode ser reduzido facilmente ao problema de Programação Inteira. Este trabalho apresenta uma dessas reduções, isto é, Fatorização 􀀀! Programação Inteira e algumas particularidades encontradas. Obtemos uma redução de ordem O(n2) no número de dígitos binários de um inteiro N a ser fatorado e, além disso, encontramos algumas propriedades locais da matriz final que podem auxiliar um possível estágio de pré-processamento
URI: https://repositorio.ufpe.br/handle/123456789/7639
Aparece na(s) coleção(ções):Dissertações de Mestrado - Matemática

Arquivos deste item:
Arquivo Descrição TamanhoFormato 
arquivo994_1.pdf580,91 kBAdobe PDFVer/Abrir


Este arquivo é protegido por direitos autorais



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