INTRATABILIDADE e NP-COMPLETUDE - Sandro Andrade .INTRATABILIDADE e NP-COMPLETUDE Sandro Santos Andrade

  • View
    216

  • Download
    1

Embed Size (px)

Text of INTRATABILIDADE e NP-COMPLETUDE - Sandro Andrade .INTRATABILIDADE e NP-COMPLETUDE Sandro Santos...

  • INTRATABILIDADEe

    NP-COMPLETUDE

    SandroSantosAndrade

    DoutoradoMultiinstitucionalemCinciadaComputaoUFBA/UNIFACS/UEFS

    Junho/2008GrafoseAnlisedeAlgoritmos

  • Introduo

    Para alguns problemas no existem algoritmos substancialmente melhores que a execuo de uma busca exaustiva

    Estes problemas so inerentemente intratveis Provar essa intratabilidade inerente pode ser to difcil quanto

    encontrar um algoritmo eficiente para resolver o problema Pode-se, entretanto, provar que o problema em questo to

    difcil quanto um grande conjunto de outros problemas reconhecidamente difceis (problemas NP-Completo)

    Saber que um problema NP-Completo antecipa a preferncia por abordagens menos ambiciosas: Solues para casos especiais do problema geral, solues eficientes

    somente na maioria dos casos, solues aproximadas etc

  • Conceitos Iniciais

    Def: um PROBLEMA uma questo genrica a ser respondida e que possui parmetros, cujos valores no so especificados

    Um problema definido pela i) descrio geral dos seus parmetros e pelas ii) propriedades que a resposta (SOLUO) deve satisfazer

    Def: uma INSTNCIA de um problema obtida atravs da especificao de valores particulares para os parmetros

    Exemplo: Problema do Caixeiro Viajante (Travelling Salesman Problem) Parmetros: conjunto C={c1,c2,,cm} de cidades e, para cada par de cidades

    ci, c

    j em C, a distncia d(c

    i,c

    j) entre elas

    Soluo: sequncia de cidades que minimiza:

    i=1

    m1d c i , c i1 d cm , c 1

  • Conceitos Iniciais

    Instncia do Problema do Caixeiro Viajante: C={c

    1,c

    2,c

    3,c

    4} d(c

    1,c

    2)=10,d(c

    1,c

    3)=5,d(c

    1,c

    4)=9,d(c

    2,c

    3)=6,d(c

    3,c

    4)=3

    Soluo:

  • Conceitos Iniciais

    Um ALGORITMO um procedimento, passo a passo, para resolver um determinado problema

    Um algoritmo RESOLVE um problema se ele puder ser aplicado a qualquer instncia de e sempre produzir uma soluo para esta instncia

    Em geral, procura-se algoritmos eficientes (rpidos) Os requisitos de tempo so indicados em funo do tamanho da

    instncia (quantidade de dados de entrada) A descrio da instncia pode ser vista como uma string nica e

    finita de smbolos escolhidos em um alfabeto finito de entrada

  • Conceitos Iniciais

    Def: a forma particular e fixa escolhida para representar instncias de um problema denominada ESQUEMA DE CODIFICAO (encoding schema) Ex: um esquema de codificao para o Problema do Caixeiro Viajante:

    c[1]c[2]c[3]c[4]//10/5/9//6/9//3. Tamanho da entrada = 32 Def: a FUNO DE COMPLEXIDADE DE TEMPO de um algoritmo

    informa, para cada tamanho de entrada possvel, a maior quantidade de tempo necessrio para resolver uma instncia deste tamanho Depende do esquema de codificao e do modelo de computao

    utilizados, porm estes produzem pouco impacto nas distines feitas pela teoria da NP-completude

  • Conceitos Iniciais

    A distino entre algoritmos de tempo polinomial e algoritmos de tempo exponencial define um critrio para anlise de eficincia

    Def: um algoritmo de TEMPO POLINOMIAL se a sua funo de complexidade de tempo (p(n)) , para alguma funo polinomial p, onde n o tamanho da entrada. Os algoritmos cuja funo de complexidade de tempo no so limitadas dessa forma so ditos de TEMPO EXPONENCIAL (mesmo aqueles com funo de complexidade de tempo limitadas por funes no-polinomiais e no-exponenciais)

    A maioria dos algoritmos de tempo exponencial so meramente variaes de busca exaustiva, enquanto os de tempo polinomial so projetados a partir do entendimento mais aprofundado da estrutura do problema

  • Conceitos Iniciais

    Def: um problema dito INTRATVEL se no existir um algoritmo de tempo polinomial que o resolva

    Excees para as associaes polinomial eficiente, exponencial ineficiente: Entradas pequenas. Ex: 2n mais rpido que n5, para n20 Aplicabilidade prtica. 2n significa que existe pelo menos uma (e porque

    no somente uma ?) instncia de tamanho n que requer tal tempo (anlise do pior caso).

    A aplicabilidade prtica de alguns algoritmos de tempo exponencial indicam a existncia de alguma propriedade do problema que, se refinada, pode conduzir a melhores algoritmos

    Algoritmos com complexidade n100 ou 1099n2 no executaro de forma eficiente, mas na prtica os polinmios so de baixa ordem

  • Conceitos Iniciais

    Qualquer esquema de codificao razovel ir diferir de um outro de forma polinomial, portanto no interferem na intratabilidade

    Todos os modelos de computao j estudados (Mquinas de Turing de uma e mltiplas fitas, random-access-machines RAM, etc) so equivalentes em relao complexidade polinomial de tempo e no interferem na intratabilidade

    Duas causas distintas para a intratabilidade: A dificuldade do problema requer uma quantidade exponencial de tempo

    para se chegar na soluo A soluo to extensa que no pode ser descrita por uma expresso cujo

    comprimento limitado por uma funo polinomial do tamanho da entrada (causa menos comum). Ex: variao do Problema do Caixeiro Viajante: quais so todos os ciclos com comprimento menor ou igual a um valor B ?

  • Conceitos Iniciais

    Def: um problema dito INDECIDVEL se no existir um algoritmo (mesmo exponencial) que o resolva. um sentido mais forte para a intratabilidade. Ex: problema da parada

    Histrico: 1936 (Turing): problema da parada (indecidvel) 1965 (Hartmanis e Stearns): problemas decidveis e intratveis artificiais 1972 (Meyer e Stockmeyer): problemas decidveis e intratveis reais

    Os problemas apontados em 1972 no podem ser resolvidos em tempo polinomial nem mesmo por um modelo computacional no-determinstico

    Alguns problemas aparentemente intratveis encontrados na prtica so decidveis e podem ser resolvidos por um computador no-determinstico

  • Conceitos Iniciais

    Estudar como os problemas se relacionam em relao sua dificuldade pode trazer informaes valiosas para os projetistas de algoritmos

    A principal tcnica para demonstrar que dois problemas se relacionam a REDUO

    A reduo define uma transformao que mapeia qualquer instncia de um problema em uma instncia equivalente de um outro problema

    Contribuies de Cook (1971): Noo de redutibilidade em tempo polinomial Ressaltou a classe NP (problemas de deciso que podem ser resolvidos em

    tempo polinomial por um computador no-determinstico) Provou que todo problema em NP pode ser polinomialmente reduzido a um

    problema particular em NP (o Problema da Satisfatibilidade)

  • Conceitos Iniciais

    Consequncias: Se o Problema da Satisfatibilidade puder ser resolvido com um algoritmo de

    tempo polinomial, ento todo problema em NP tambm poder Se algum problema em NP for intratvel, ento o Problema da

    Satisfatibilidade tambm O Problema da Satisfatibilidade o problema mais difcil em NP Outros problemas compartilham com o Problema da Satisfatibilidade o

    ttulo de Problema mais difcil em NP Def: a classe de equivalncia que contm os problemas mais

    difceis em NP denominada classe dos problemas NP-COMPLETO

    A intratabilidade de todos os problemas em NP depende da intratabilidade dos problemas NP-Completo (o que desconhecido)

  • A Teoria da NP-Completude

    Por convencincia, a Teoria da NP-Completude aplicada somente a Problemas de Deciso

    Def: um PROBLEMA DE DECISO consiste de um conjunto D de instncias e um sub-conjunto Y D de instncias-sim

    Exemplo de Problema de Deciso:

    Instncia genrica: dois grafos G1=(V1,E1) e G2=(V2,E2) Questo: G1 contm um sub-grafo que isomorfo a G2 ?

    Problema de deciso relacionado ao Problema do Caixeiro Viajante: Instncia genrica: o conjunto C de cidades, a distncia entre cada par de

    cidades e um valor limite B Questo: Existe um ciclo que passa por todas as cidades de C com

    comprimento menor ou igual a B ?

  • A Teoria da NP-Completude

    Problemas de otimizao podem ser facilmente transformados em Problemas de Deciso: mnimo (mximo) custo existe X com custo menor (maior) ou igual a Y ?

    Porque trabalhar com Problemas de Deciso ? Pelo suporte formal dado pela Teoria da Computao (linguagens e

    modelos computacionais) Def: para qualquer conjunto finito de smbolos, * denota o

    conjunto de todas as strings finitas formadas por smbolos de . Ex: ={0,1} , *={ ,0,1,00,01,10,11,000,001, }

    Def: se um sub-conjunto de * ento uma LINGUAGEM sobre o conjunto . Exs: {01,001,111,1101010} uma linguagem sobre {0,1}, * uma linguagem sobre

  • A Teoria da NP-Completude

    Cada instncia de um problema descrita por uma string formada por smbolos de um alfabeto fixo

    Um problema e um esquema de codificao e particionam * em trs classes de strings: i) as que no codificam instncias de , ii) as que codificam instncias-no de e iii) as que codificam instncias-sim de

    Def: a LINGUAGEM ASSOCIADA A e e definida por:

    Se um resultado vlido para a linguagem [, e] ento ele vlido para o problema sobre o esquema de codificao e

    L [ ,e ] = x* : oalfabetousadopor e ; x acodificaoem e deumainstncia I em

  • A Classe P

    Para formalizar a noo de algoritmo necessrio padronizar um modelo particular de computao

    MQUINA DE TURING DETERMINSTICA DE UMA FITA (MTD):

    Um programa para uma MTDespecifica: Um conjunto finito de smbolos de fita, incluindo o sub-conjunto de

    smbolos de entrada e o smbolo branco b - Um conjunto finito Q de estados, incluindo um estado-inicial q0 e dois

    estados-final qY e q

    N

    Uma funo de transio :(Q{qY,qN})x Qx x{1,+1}

  • A Classe P