Classe de Complexidade NP e Máquinas de Turing Não Determinísticas

Classe de Complexidade NP Teoria da Computação 2021 Prof Roberto C de Araujo Teoria da Computação 2021 1 Máquinas de Turing nãodeterminísticas Considere a seguinte máquina de Turing não determinística M1 já vista em aula Ao executar M1 com a entrada abbab obtemos a seguinte árvore de configurações q0abbab aq1bbab abq1bab abq2bab abbq1ab abbq2ab abbaq1b abbabq1 abbabq2 abbabq3 OK A MT M1 aceita abbab pois existe uma sequência de configurações que resultam no aceite 2 Classe de Complexidade NP Seja N uma máquina de Turing nãodeterminística que para sobre todas as entradas O tempo de execuçãode de N é uma função f onde fn é o número máximo de passos que N usa em qualquer ramo de sua árvore de configurações sobre qualquer entrada de comprimentos n Seja t R uma função Definimos por NTIMEtn a classe de complexidade de tempo como a coleção de todas as linguagens que são decidíveis por uma Máquina de Turing não determinísticas de tempo Otn NTIMEtn L L é uma linguagem decidida por uma MT nãodeterminística de tempo Otn NP é a classe de todas as linguagens que são decidíveis em tempo polinomial por uma máquina de Turing nãodeterminística Ou seja 𝑁𝑃 𝑁𝑇𝐼𝑀𝐸𝑛𝑘 𝑘0 O termo NP vem de tempo polinomial não determinístico Para mostrar que uma linguagem L está em NP devemos Construir uma MT não determinística N que decida L e Mostrar que o tempo gasto por N no pior caso é polinomial Exemplos de linguagens em NP Usando uma máquina de Turing nãodeterminística mostre que a linguagem abaixo está em NP CamHam Gst G é um grafo orientado com um caminho hamiltoniano de s para t NPara a entrada Gst tal que G é um grafo orientado de ordem n com stVG 0 Nãodeterministicamente gere uma sequência C v1 v2 vn tal que C é uma permutação de VG 1 Avalie v1s vnt se resultar falso rejeite 2 Para cada vértice vi 1in1 consulte se o grafo tem a aresta vi vi1 se algum teste falhar rejeite 3 Aceite Para calcular o tempo de N basta preencher a tabela abaixo e calcular o tempo total gasto por M t 1 exec qtd exec t total Justifictiva Linha 0 Linha 1 Linha 2 Linha 3 Teoria da Computação 2021 Usando uma máquina de Turing nãodeterminística mostre que a linguagem abaixo está em NP Compostos x xpq para inteiros pq 1 3 Verificadores definição alternativa de NP Um verificador para uma linguagem A é um algoritmo V onde A V aceita c para alguma cadeia c A cadeia c é chamada de certificado ou prova da pertinência de a A Exercícios Obtenha um certificado para cada um dos problemas ou linguagens abaixo CamHam Gst G é um grafo orientado com um caminho hamiltoniano de s para t Compostos x xpq para inteiros pq 1 Medimos o tempo de um verificador usando apenas o comprimento de Portanto um verificador de tempo polinomial roda em tempo polinomial com relação ao comprimento de Uma linguagem A é polinomialmente verificável se ela tem um verificador de tempo polinomial NP é definida alternativamente como a classe de linguagens que têm verificadores de tempo polinomial Exercício Usando verificadores mostre que as linguagens abaixo estão em NP CamHam Gst G é um grafo orientado com um caminho hamiltoniano de s para t Compostos x xpq para inteiros pq 1 4 Exercícios 1 Um clique em um grafo nãoorientado é um subgrafo no qual todo par de vértices são adjacentes Um kclique é um clique que contém k vértices Mostre que a linguagem Cliquek Gk G é um grafo nãoorientado e G tem um kclique está em NP através de verificadores e também através de MT nãodeterminísticas 2 Um conjunto independente em um grafo não orientado é um conjunto I de vértices talque nenhum par de vértices de I são adjacentes Um conjunto independente de tamanho k é um conjunto independente que contém k vértices Mostre que a linguagem Indepk Gk G é um grafo nãoorientado e G tem um conjunto independente de tamanho k está em NP através de verificadores e também através de MT nãodeterminísticas