Complexidade e Classes de Problemas em Otimização: P, NP, NP-completo, NP-difícil, Redução, Provas

e vamos falar da classe de programação falando de algoritmos e eu falei um pouco desses algoritmos aí naquela SP São só alguns exemplos o Dark esse daqui é para resolver lá caminho menino ontem não tenha ciclo negativo né não tem a valores negativos Nazaré essas né que ele vai precisar ele ó M ao quadrado então algoritmo eficiente por isso que todo mundo quando vai resolver um caminho me falou para caminho mais fácil eu resolvi aqui é rapidinho tá aí de fato você pode resolver problemas enormes aí em poucos segundos meses tem também quando você tem

alguns valores não negativos na rede que você não chega em ciclos negativos enviar uma forte caiu ai meu cu plano de transporte existe um algoritmo lá o que resolve em ordem meu cubo outro lado de terra até o maior valor lá né dos dados pode inclusive resolver modelar Ele comprando programação linear e resolver por um pelo menos Simplex pelo médico no interior Qual que é a grande questão até agora eu meio que enrolei um pouco vocês enganei com vocês e quando a gente tava falando da classe P Teoricamente assim na raiz mesmo se você querer

conter raiz assim né Essa classe pé para problemas de decisão Tem muita gente que mistura a gente falar classe tempo para resolver qualquer problema e aí começa a fazer uma salada tá a gente fala não Não importa se decisão utilização se é busca mas né na forma como foi concebido essas classes que a gente vai vir agora A ideia era um problema de decisão um problema de sim ou não você faz uma pergunta EA resposta é sim ou não podes Inclusive a um problema de otimização disfarçado existe uma rota com a distância Total menor que

cá igreja que eu não tô minimizando nem maximizando nada como são definir se lá no target né palavra meu objetivo é cá né a meta é cá e isso é consigo uma rota né com distância Total menor que ficar isso é um problema de decisão veja que a resposta para isso é sim ou não você fala assim você consegue tchau viu Ah não você não consegue então é diferente no plano time são todas essas classes que a gente vai vir agora tá então para problemas de D A grande questão é por que que o pessoal

né definir tudo para decisão é fácil você converter um fazendo um problema de otimização promo de decisão a gente acabou de converter o caixeiro-viajante para um problema de decisão aí você fala Poxa mas isso não souber é o Caio Não sei qual é o valor ótimo você pode ainda usar aquelas buscas binárias tá você fala Olha acho um valor alto mil ele responde assim você reduz para 500 o pai respondeu não aqui tá vai para 750 a respondeu sim metade você vai fazendo né essa busca aí sempre dividindo intervalo ao meio que uma hora você

converte o outro exemplo de problema de decisão aí ó é que é bem clássico é o clique te dar um gráfico seja uma representação aqui né que eu tenho nós e as usar estas ligando que esses nós e o Inter o carro e eu te pergunto né existe um clique que tem um clique é um Sub Grave completo peguei esses nós eles estão todos ligados aqui por Alerta Então também não existe um clique aqui de tamanho caça e caça dois já achei o achei outro Achei você dá uma resposta aqui assim a carga para existe

o cliente já você Oi gente tamanho 3 existentes tamanho quatro eu não tô vendo nenhum aqui que qualquer quatro que eu pegue eles têm que estar todos ligados entre si tão é essa daí é a minha pergunta essa é a minha decisão E aí é a resposta é sim ou não é um problema de decisão E aí agora tem um problema de decisão que é bastante conhecido tá E que deu na verdade origem a essa teoria que a gente vai ver agora de problemas NP NP completa no hiper difícil é problema de saco disso habilidade

tem algum pessoa que traduz como satisfatibilidade é um nome complicado ditado vem do inglês aí tá sai habilite aqui traduzir a massacrante fala sabe o que que é esse problema de satisfabilidade ó dá nessa fórmula booleana é uma fórmula bolena Por exemplo essa daqui tá uma fórmula em que eu tenho falou diz aqui ó é uma expressão na verdade em que eu tenho variáveis que só podem assumir valores booleanos ou ela tem que assumir verdadeiro ou falso o 01 eu as combinações delas em sempre em sem cláusulas tá sentenças eu vou sempre usar aqui a

forma normal conjuntiva então é uma fórmula o plano satisfabilidade ele é pô suave definido usando uma fórmula do Leana e a pergunta dele é tem alguma atribuição de verdadeiro ou falso né de valores booleanos para essas variáveis aqui de modo que essa expressão toda seja verdadeira é que essa forma normal conjuntiva são cláusulas tá desses valores desses combinações esses elementos usando ou pode ter vários tá x aqui Eu tenho 2 x 1 ou não x 2 e aqui no meio sempre a por isso que essa conjuntiva tá é uma conjunção de disjunções ou disjuntivo também

seria o contrário disso mais ó eu não posso repetir o elemento tá ele tem que estar né uma única vez aqui nessa cláusula eu posso ter várias causas aí nas costas não posso repetir alimento X1 tá nessa e tá nessa isso daí é um problema de satisfabilidade tá é sempre eu acho que daqui a uma distância dele X1 não x2.exe sushi Ah e não X1 eo X2 uma expressão EA pergunta Tem valores para x 1 x 2 de flores clientes que eu faço fimose que quando eu avaliar essa expressão ela seja sempre verdadeira a resposta

nesse caso é sim não resolveu o problema e eu tenho Certificado Agora dessa desse Sim esse certificado é a minha resposta é solução para garantir esse sim se eu vim aqui falar que eu fiz um é verdadeiro e esses dois é verdadeiro e que vai acontecer como é o basta que um deles Seja verdadeiro então a gente uma verdadeiro o PAC da verdadeira e aqui de verdadeiro já matei verdadeiro é verdadeiro e verdadeiro verdadeiro então portanto Existe uma forma de essa expressão ser verdadeira hoje esteja eu faço qualquer valor tá porque como eu basta que

o X1 eo X2 aqui sejam verdadeiros para garantir Então essa folha não tá de sua habilidade Óbvio que eu posso colocar ele né como se fosse uma uma situação em que você tem vários requisitos para você satisfazer e você que a garantia que esses requisitos sejam satisfeitos tá Ou seja que você consiga um verdadeiro aqui nessa combina e eu satisfabilidade de origem aí a uma classe de problemas só uma caixa a gente vai ver já já primeira só vou relembrar tem uma classe pq são problemas tá para os quais existem algoritmos de tempo polinomial tão

p é a classe de problemas agora de decisão estou considerando aqui de São somente problemas de decisão que podem ser resolvidos em tempo polinomial sentido exemplo só a hora ainda quadrado em nove n-232 não importa é uma constante mas ele é uma classe de problemas para os quais existem algoritmos apostila algoritmos eficientes por satisfabilidade não entrou nessa nessa classe e aí lá o pessoal criou essa classe é np para ele fica essa classe NP que a gente falar a Cassiane pera aquela se dá para usar o pronome Não não é isso é a classe de

problemas e tempo polinomial não-determinístico n aqui tá inferno não determinístico então isso tem uma classe p e problemas que a gente sabe que existem algoritmos eficientes a vida legal se você quiser trabalhar nela só vai ficar ali né achando do herpes no melhor ali mas uma hora você acha um algoritmo lá cada vez um pouco melhor né vai aprimorando mas existe uma classe de problemas em que ninguém consegue que nem um algoritmo eficiente é tudo com problemas que dá o povo meio sem esperança lá de resolver tá de uma forma eficiente como é que a

gente define esses problemas de decisão para os quais o resultado se então por exemplo probleminha lá de Santa habilidade satisfabilidade ou de cliente uma resposta assim e essa resposta assim ela tem o certificado para falei pra vocês certificado aquela solução uma atribuição de valores ou o próprio clique que eu peguei lá não sei pra vocês eu queria pedir três Um certificado de tamanho polinomial que pode ser checado um tempo então você falar resolver o problema de satisfabilidade tá bem difícil puxar Charlie uma tribo Imagine que eu tenho agora mil cláusulas cada cláusula tendente dela Como

saber se uma atribuição de verdadeiro ou falso vai dar um verdadeiro no todo é difícil mas se você me der a resposta eu consigo chegar em tempo polinomial é fácil Se você me der falava X1 = v x 2 = x 3 = FX quatro lados que você me dá essa resposta eu vou lá encher com rapidinho é uma coisa do clix não falar esses três são clientes mas eu vou lá contas arestas entre eles se tem um garfo Complexo da completa o problema que tá NP eu não sei um algoritmo não conheço uma leite

e eficiente para resolver mas se você me der uma resposta eu consigo chegar essa resposta de uma forma eficiente existe um metro e um objetivo de tempo polinomial para checar se a resposta está correta então eu vou chegar o certificado tão a sempre que a decisão é se é possível verificar verificar a resposta no tempo polinomial veja que isso é válido para os caras que estão e também então a gente tem esse primeiro o resultado ver tá contido no NP é isso aqui ela tem uma classe de problemas agora cresceu antes só tinha probleminhas peta

ordem meu cubo e olha ainda 230 em todos aqui e tá o problema em Pauta o qual existe um algoritmo e tempo polinomial aqui estão os problemas de decisão para os quais não se conhece talvez não exista Mas enfim Só posso dizer que não se conhece um algoritmo e tempo polinomial para resolver mas a gente consegue chegar uma solução dele em tempo polinomial da onde vem o n Então vem vem de não-determinístico porque não determinístico porque esses problemas eles podem ser solucionados em tempo polinomial se a gente usar uma máquina de turing não determinística daí

que vem onde ter me pagado de tudo para quem nunca viu é uma abstração de um computador é uma forma teórica de você representar né o processamento no computador tem uma fita e comandos nessa fita você vai volta para seguir instruções você tem um computador hoje na sua frente aí graças a máquina de turing altura e aí eu é o pai da Computação foi ele que começou com as ideias aí e fundamentais aí e implementou ideias fundamentais tá então a máquina de turing Na verdade eu abstração disso é o conceito teórico disso e a máquina

de turing tenha determinística que aquela que é o nosso processador ou você fala para ele olha tem as instrução Será que essa instrução e o que você mandar ele fazer ele faria essa máquina de turing determine a não ter Mística é uma cultura em louco Oh Ana não ela vai fazendo movimentos aí e são aleatórias que essa moda vai ter ministros E aí e isso pode fazer com que você chegue a uma solução do problema então pode mandar aquela vai fazer esse número para o nome é de Passos é mais ou menos fazendo assim não

é de uma forma bem bem grosseira a ideia de uma neurite uma meteorite nela vai fazendo ela sorteio número faz um passo né E aí ela vai de uma forma pode chegar no ótimo fala nossa né turístico aqui rodou em um segundo e achou ótimo do problema caramba ficar Fernanda termine que ela por sorte ela chutou e no chute ela achou ótima a questão é ninguém sabe o tamanho disso Pode ser que isso daqui seja tudo uma coisa só pode ser que p o PT existe na verdade até esse prêmio de um milhão de dólares

para quem conseguir provar se P = NP ou diferente dnp tá mas hoje em dia ninguém sabe a resposta Será que pega no teu pé diferente dele P ninguém sabe se você quiser ser um milionário BBB não tá com nada mais tá Pessoal agora é resolver um desses problemas aqui tá deixa esse pessoal aqui eles têm na verdade de vários problemas à saúde esse conjunto planos alguém conhecido né problemas aí em aberto há muito tempo que ninguém consegue uma resposta para ele mas você conseguir ganha 1 milhão e muita só classes de problemas Então temos

que existe a p e NP e quem está interessado na cnp vou mostrar uma coisa para vocês dentro do snp tem uma subclasse em primeira coisa que você usa um problema a gente fala que ele é redutível a um problema devo usar essa natação a é redutível a ver consigo reduzir ele abrir se para qualquer Instância dele já tá então pegar uma estão a infinitas peguei a gente pode construir uma Instância de bebê também agora do B em tempo polinomial então eu consigo ida de a fazer essa conversão para beber em tempo polinomial a levou

ele não quadrado parte se o de a resultar em si esse bebê também tem que resultar em sim e vice-versa Então seja eu consigo fazer essa conversão esse essa distância ficou uma Instância do tipo sim tem uma solução essa também tem que dar sim e vice-versa Então essa assim seis somente essa daqui assim é uma conversão transformar um problema em outro mas eu quero garantir essa propriedade que isso esse se a resposta desse assim uma resposta desse assim a resposta de senão a resposta desse não foi uma decisão aqui nesse caso eu fiz uma redução

tá E é uma redução polinomial aí fiz em tempo polinomial sua redução por quê que isso é importante reduzir um probleminha aqui ó um problema b e n b completo esse daí fosse muito já ouviram falar tá problema np-completo ele é np-completo se ele tá no Mp e da o que era nesse NP eu consigo reduzir a para ver eu tenho aqui esse cara agora tá no MPE tá peguei o bico aqui no Mp e tá qualquer outro problema que eu pegar aqui eu consigo reduzir não seja consigo transformar esse ano B de modo que

eles sejam certa forma a equivalência resolver um resolveu porque um filme tem um sim bairro não aqui eu não lá então resolveu resolveu isso é um problema np-completo essa definição que que significa ser um problema ele ter concreto são os mais difíceis da classe sempre porque os mais difíceis se você achar um algoritmo tempo polinomial é um problema np-completo você acha para todo mundo da classe em pó para todo mundo então a gente tem aí o nosso diagrama veja que Agora terei uma fatia aqui né Tem mais um pedacinho tenho a classe toda NP que

essa bola toda aí Alguns ali ó são problemas que eu conheço um algoritmo eficiente tem uma classe e né que o que sobrou na verdade que sobrou dessa classe eu ainda não conheço Pode ser que exista não sei mas tem uma div ó e aqui são os problemas que extremamente difícil eu resolver um aqui aí eu sei que pegam em de forma eficiente eu sei que p é ele então agora dado que né ah e bnp né e eu consigo fazer a minha redução tal a irredutível para ver eu tenho esses dois casos aqui importante

SB tá em pé ou seja se existe um algoritmo tempo polinomial para esse problema bebê Então existe por lá também tá porque olha se eu consigo reduzir o a para beber você já consigo transformar o ar não ver qualquer Instância de ar tá falando Qualquer distância de bebê resolvi o bem ao distância de b e todos sim ou não aqui assim não lá obviamente eu achei uma corrente para resolver Ah tá então se B tá em p a também tem que estar em e agora essa que é a mais legal de todas que é isso

que o pessoal usa na prova tá então se a é np-completo então B é np-completo eu vejo que na definição Eu precisaria provar né Qualquer a e tá em LP e conseguiria e eu conseguiria reduzir para ver esse daqui me permite fazer olha se a np-completo se eu já tem um problema que alguém provoca np-completo então basta eu reduzir ele para ver que com isso eu provo que o Benê quer comprar tá logo para provar que um problema dele ter completo A gente parte de um problema aqui a gente já sabe CNT completo e faz

a redução de a para B muita gente faz isso ao contrário cuidado tá até site na internet para o cara vai provar uma coisa ele prova o contrário ele pega o problema que ele quer provar que é completo e redução np-completo é rápido tá não é isso Ó a ordem aqui ao contrário eu pego que eu já sei que ainda te completo por exemplo satisfabilidade E aí sim e eu faço a redução em 71 por Steve Cook aqui ok e propôs aí nessa ideia não foi completa porque ele provou o programa está a sua habilidade

ainda foi comprar com isso e começou toda essa teoria aí dele pena que comprar tem que é difícil E aí logo depois também E aí isso procurando de decisão aí vai o pessoal e quando isso também para problemas de otimização vou chegar lá e aí como é que o pessoal começou a usar essa teoria editado que o provou que sabe que o site não é np-completo beleza e basta o reduzir o site do clipe Faz essa redução E aí pronto Clique agora ele foi completo Basta fazer a redução do clipe um outro foi uma vai

ter que esperar quem que é bastante comum em nossa teoria Então agora eu sei que vai ter que esperar que ele foi completa também então é só ficar reduzindo um para o outro e aí a gente consegue provar e essa redução é uma coisa muito malucas esse tá vendo né isso pela primeira vez falando Nossa Senhora do nada tá me falando isso não que eu vou fazer assim na vida é louca né ó Pode parecer loucura mas é uma coisa que é muito interessante e não é difícil quando você vê a palavra obviamente que tá

provar o cara talvez passou alguns meses aí na vida dele para ter aquele estalo para ter ideia Olha a prova do site para o clipe para vocês verem que a coisa não é tão absurda assim aí eu vou provar eu clique é np-completo tá lembro do clip aquele probleminha de achar clix eu te dou graças te dou o cá existe um clique aí do tamanho cá a existe sim a não existe não como é que a gente faz a redução lembra aqui ó a redução primeira coisa é eu pego uma Instância qualquer do problema a

e converto ela vou converter é uma Instância qualquer do problema b então tem primeiro passo de conversao e tem que ser polinomial tem que ser eficiente tá assim não foi tudo por água abaixo tem que ser uma redução polinomial aí ó como é que ele faz isso ele vai pegar a cada uma da das cláusulas lado minha expressão lembra que era cláusula Isso é uma cláusula isso aqui é outra cláusula Isso aqui é uma Instância do problema exemplo tá peguei uma qualquer para cada elemento dessa fórmula aí que eu tiver então lá em cada uma

das cláusulas da fórmula qual que é uma delas aí ó x e ir ou não x Itachi então estejam não importa qualquer elemento que eu tiver lá escrito eu vou criar um verniz Então vou pegar cláusula E aí ó para cada elemento aqui eu vou criar um verso então tio X1 queria um vértice para aí tá o outro x 2 outro perto então para cada entidade aqui para cada entrada aqui é uma bolinha lugar se aparecer mais uma vez cria uma cópia limpar tudo que aparecer lá se foi embaixo e agora para cada par de

elementos de cláusulas diferentes e que podem ser verdadeiros ao mesmo tempo eu crio uma aresta entre eles então vocês vão ligar dois caras aqui que estejam em cláusulas diferentes então eu vou olhar o x1 com esse com esse com esse depois do x1 com os três aq o não X1 aqui eu só vou olhar com o X1 e com os três tá vou olhar cada elemento com os caras de cláusulas diferentes e mais do que isso eles têm que ser verdadeiras ao mesmo tempo X1 como não X1 pode ser vender o mesmo tempo não sem

saber desse falso então esses dois pode ser verdadeiro ao mesmo tempo pode né basta o verdadeiro aqui verdadeiro aqui tá que eu vou fazer vou por Maressa entre os 2 x 1 e não X3 pode ser verdadeira mesmo tempo pote eu ligo aqui isso daqui ixi e três quatro verdadeiro mesmo tempo pode outra causa também que bonitinho ó fiz aqui o meu garrafo cada elemento da minha expressão é um nó e cada um né desses nós que podem ser que estão em causas diferentes e podem ser verdadeiras ao mesmo tempo eu vou colocar o mar

é no total ficou esse monte de alerta que aqui bonito agora que que ele fala se eu conseguir um clique veja que eu tinha uma Instância dos Santos do Programa de acessibilidade e agora eu cria uma Instância do clipe fiz minha conversão forma conversão difícil é fácil a conversão em tempo polinomial número de nós e aí ligar esses caras aqui tá com ar é nada demais não foi uma conversão e tem polinomial agora o que que eu vou precisar fazer ver se eu acho um clique aqui você disse toda a resposta sim aqui é uma

sim aqui e vice-versa e eu não aqui é não lá né para você vice-versa se for beleza mas vejo aqui ó o clique aqui nesse gráfico corresponde ao conjunto de elementos e na sua cláusula que podem ser definidos como verdadeiro ao mesmo tempo tá se eu tiver um clique aqui significa que a verdadeiro verdadeiro verdadeiro e veja que o carro é o número de Cláudio tão caro que é igual a três Então se achar um clique aqui de pegar três nós tá E aí eles foram todos ligados Eu tenho um clique de tamanho 3 se

eu tenho um clipe de tamanho 3 existe uma atribuição de verdadeiros e faz com que a resposta da situação toda Seja verdadeiro então eu converti um probleminha outro se eu tiver um sim aqui eu tenho sim aqui para isso que eu precisava e porque eu fiz isso porque eu sei que esse problema aqui ó ele é np-completo alguém já provou isso se ele é np-completo e eu consigo reduzir ele em tempo polinomial para esse clipe esse clique também é ele quer comprar isso Acabou Talvez o que não tem nada de expressão matemática maluca que eu

não tenho nada nem uma viagem aqui não tem nada se vocês olharem outras provas Então ver que nessas de problemas mais clássicos aí o que vejo quero te ver que pensar que cada elemento dia viram nós né verdadeiro os dois ao mesmo tempo não é gerar e o mar esta história teve que ter aquela aquele estalo né que ela ideia para converter um problema em outro mais uma vez que ele fez a conversão aí não tem nada de muito valor porque então aprovado acabaram de ver né como que a gente prova tinha um problema é

np-completo é fácil a gente converter aí um problema de otimização problema de decisão coloca lá uma meta e fala Olha se consegue achar uma solução para que o valor seja menor que essa meta se a resposta for sim né E você vai ajustando o valor do Cai Mas a questão é a gente não quer também ficar com conjunto emprestado aí né peguei os caras lá do np-completo Eu quero ter um a gente quer ter um conjunto próprio Nossa está de na verdade um conjunto de problemas mais Gerais que ainda hiper completo e foi aí que

nasceu a ideia do np-dificil um np-difícil a parte aí né é ele vai incluir qualquer tipo de problema e utilização decisão EA ideia dele é a mesma ideia do LP completo tá então Ou seja a ideia dele é teus problemas que são tão difíceis quanto problema mais difícil e ele Talvez aqui não é a classe dos programas difíceis são problemas que são difíceis quanto mais difícil tá eles podem ser todos faz a gente não sabem Tá mas por enquanto tá eles não são fáceis mas se ele foi realmente difícil é esses aí são os piores

tá são os piores lá da classe agora um cara que tá em np-dificil não necessariamente está em NP isso confunde um pouco vem aqui ó esse diagrama para ajudar entender tem os np-completo que tava falando até agora e tem o np-difícil aqui pode tá dentro do MP Mas pode estar fora também não tem problema embora essa nomenclatura aqui MP é usada ela já era um pouco de confusão porque um np-difícil lançar a mente é um MP e não precisa ser um plano de decisao se ele for de decisão ainda tá aqui não ele foi completo

mas não é difícil não precisa tem IP o edifício que está NP é bem conhecida mãe não quer comprar vocês olharem né Tem livros inclusive na própria te pedir de falar o sistema de nomeação da família np é qual foi o Zenit edifícios não são todos MP com Toma cuidado na flamini pé difícil mas não Sinceramente ele é MT porque não necessariamente um problema de decisão para definir np-difícil não tem muito segredo tranquila gente acaba tendo que recorrer aos np-completos tá ó a gente vai usar um oráculo então a definição de np-difícil recorre a um

oráculo que que é um oráculo dado um prémio de utilização a existe um algoritmo tá esse algoritmo possuia como oráculo então é um algoritmo que usa o acumular acuta Convenção Coletiva resolve uma Instância desse desse aqui uma única instrução é por isso que o oráculo só vai lá e pergunta tá uma instrução ele te dá a resposta você consegue resolver numa tacada só tem uma nesse caso ele é um oráculo E por que a gente faz a esse oráculo para relacionar os problemas MP difícil np-completo algum problema é np-difícil se existe um algoritmo de tempo

e me ao polinomial por um bnp completo quando esse algoritmo polinomial tá possui o a comemorar é um pouquinho como fazer eu entendo que a gente vai ter que ler né isso várias vezes aí até incorporar mas a ideia ele é np-difícil quando eu consigo resolver um problema lá na classe dos np-completos usando esse acumular e eu resolvo isso E aí se ele tá usando uma como oráculo ele vai ser ele tem que ser tempo polinomial então para resolver um da eles cara só np-difícil é consigo resolver um barzinho lá algum conhecido lá da classe

np-completo usando a comemorar np-difícil aí em geral é problema de otimização tá como falei pra vocês Maria dos artigos que vocês forem leia aí de problemas né de otimizar sua inteira ela falar é um problema enterrar e papo tá em geral usado problema de otimização cujo o problema de decisão corresponde a uma np-completo Então essa é a ideia do Oráculo tá o oráculo vai servir para você olhar para o plano de utilização na verdade você tá olhando é para o de decisão que permite fazer essa conversão é como eu falei para vocês caixeiro-viajante np-difícil e

você conseguir achar um algoritmo tempo polinomial para o caixeiro viajante você vai ficar milionário tá e muito mais famoso do que o pessoal do Big Brother pode ter certeza Praticamente todo ano tem alguém aí com a que dias da que provoca e pego a empresa mas que no final não falou nada estou sempre conseguir um algoritmo eficiente para um problema que ainda é difícil você Zerou aí a computação tá você conseguiu provar que ter é NP só para fechar para vocês verem a ideia e também provar um problema np-dificil é tá na classe para não

é tão difícil assim eu quero provar que o problema do caixeiro-viajante ainda está difícil para falar Nossa essa prova puxa destravado de surf não é que a gente vai usar dois problemas ó eu vou pegar o problema de decisão relacionado ao problema do caixeiro-viajante que a prova de decisão compra vocês defina uma meta cartão dado um gráfico completo né o cheiro verde com acento gráfico completo e esse número tá aí não existe uma rota fact vocês que visite todos os nossos Mônica Verde retorna para o nosso saída né de custo aí né de distância aí

no máximo carro seja menor buraco se existir assim tá problema é só isso não sei nem falar com assim e aí esse é o problema de decisão associada e relacionado ao castigo e a gente mas eu vou pegar um outro lembra que a prova para eu provar que é np-completo eu preciso sempre partir de um cara que é ele ter completa Então a partir desse problema aqui ó o discípulo a miltoniano que alguém já provoca-me qnt completo para pegar um problema de decisão np-completo chamado de ciclone ano que faz o seguinte dado um grafo G

qualquer não precisa ser completo não é fugir qualquer tem lá meus nós as minhas arestas tá a pergunta existe um ciclo Tony análise gráfica um ciclone anos não sei porque visita tudo voltar e por ser um ciclo velho tem que sair de uma lá visitar todo mundo e voltar para si mesmo é um círculo que passa por todos os nossos não tem nada a ver com minimizar a situação tá Eu quero visitar todo mundo e voltar para o mesmo lugar graça não precisa ser completamente à prova que isso ainda ter completo que que eu vou

fazer então vou e aqui eu consigo reduzir o que eu sei que ainda te completo tava reduzir o ciclo toniano aqui para o meu Cachoeiro viajar mas o caixeiro viajante de decisão esse daqui esse é o problema dois Esse é o problema não tá não tô falando para mim utilização aqui do do controle equivalente de decisão então vou fazer essa redução no tempo polinomial é possível olha como é tranquilo agora né que ela tá pronto eu vou definir custo para todas as arestas do problema de ciclamato União então lembra que ele não agrave completo mas

as arestas que olhar para ele ver lá ela tem distância um tá costume agora eu vou adicionar essas nesse gráfico até ele ficar completo e essas áreas vão ter custo 2 ou custo Ele custa que você quiser colocar dois ó tá tinha usar essas originais e Ciclone ano lá do da da Estância do problema e não necessariamente é completo Então pois custo agora eu vou adicionar novas arestas concurso dois e vai fazer o seguinte ó vou chamar o oráculo Vou Chamar esse cara aqui tá com Caio e essa conversão É bem tranquila foi feita em

Passo polinomial e porque eu tô usando cá igual a ele se a resposta nesse problema um aqui for sim tá eu consegui resolver o caixeiro viajante Visitei todo mundo e voltei concurso no máximo n agora significa que eu só percorri as arestas do problema original Então seja dado um sim aqui eu consegui resolver um um sim lá porque Lembra as arestas tem peso 1 para as originais da alguns porque esse daqui Originalmente não tava ligado com esse lá vai ter um peso dois mas se eu conseguir fazer a rota todas só cruzando os caras que

têm peso um significa que eu cruzei só arestas originais olha essas do ciclomotor então se eu achar uma resposta assim que o caixeiro viajante com custo no máximo n eu visitei ele nós E aí sim eu tenho uma resposta para o ciclo Antônia eu não consegui também não consigo não ser reduzir o ciclone ar puro Cachoeiro transformei isso para o problema do cachorro de de ó e todo Sim esse problema é um sim lá e vice-versa portanto eu consegui provar que esse problema de decisão aqui ele é NP comprar se esse problema de decisão np-completo

ou de otimização parzinho de lá o oráculo dele é np-difícil uma provinha aí você vê não com cinco itens tá então de novo não teve não precisa de me entregar a tripla Não precisei do espaço de banana que nada é isso eu queria mostrar para vocês o mais importante dessa aula tá esse slide aí eu quero que vocês entendam que cada uma dessas classes e quando você ler isso e no artigo Quando você vê isso no congresso e quando você precisar provar isso você já sabe que significar um desses conjuntos para uma dessas classes e

você sabe tá até mesmo qual que seria a ideia de uma fava para isso é E aí [Música]