Teoria da Computação - Atividade 8 - Análise de Classes de Complexidade

Atividade 8 Teoria da Computação 7a Etapa do Curso de Ciência da Computação FCI Mackenzie OBS Citar eventuais fontes utilizadas é obrigatório 1 Considerando três linguagens genéricas A B e C quais das afirmativas abaixo são verdadeiras a Se A PSPACE então A NPSPACE b Se A NPSPACE então A PSPACE c Se A P então A é decidível d Se A P então A NP e Se A P B e B P então A P f Se B é NPcompleto e B P C para C NP então C é NPcompleto g Se A NP então A é indecidível PESQUISAS 2 Dê exemplos nome e caracterização de problemas PSPACECompletos diferentes dos presentes nas notas de aula 3 Defina o que são as classes de complexidade de espaço L e NL dê exemplos de problemas nessas classes 4 O que é o problema da Geografia Generalizada GG e de que classe de complexidade de espaço ele é DICA Ver as páginas de 343 a 345 de Sipser 2013 Considerando três linguagens genéricas A B e C quais das afirmativas abaixo são verdadeiras a Se A Î PSPACE então A Î NPSPACE b Se A Î NPSPACE então A Î PSPACE c Se A Î P então A é decidível d Se A Î P então A Î NP e Se A p B e B Î P então A Î P f Se B é NPcompleto e B p C para C Î NP então C é NPcompleto g Se A Î NP então A é indecidível a Se A Î PSPACE então A Î NPSPACE Isso é verdade porque PSPACE é o conjunto de problemas decidíveis que podem ser resolvidos por uma Máquina de Turing Determinística em espaço polinomial c Se A Î P então A é decidível Isso é verdade porque a classe P é o conjunto de problemas decidíveis que podem ser resolvidos por uma Máquina de Turing Determinística em tempo polinomial d Se A Î P então A Î NP Isso é verdade porque a classe NP é o conjunto de problemas decidíveis que podem ser resolvidos por uma Máquina de Turing NãoDeterminística em tempo polinomial Como todo problema em P pode ser resolvido por uma Máquina de Turing Determinística em tempo polinomial ele também pode ser resolvido por uma Máquina de Turing NãoDeterminística em tempo polinomial e Se A p B e B Î P então A Î P Isso é verdade porque se um problema A pode ser reduzido a um problema B em tempo polinomial A p B e B pode ser resolvido em tempo polinomial B Î P então A também pode ser resolvido em tempo polinomial f Se B é NPcompleto e B p C para C Î NP então C é NPcompleto Isso é verdade porque se um problema B é NPcompleto e pode ser reduzido a um problema C em tempo polinomial B p C então C também é NPcompleto A afirmação b não está correta porque não há relação direta entre NPSPACE e PSPACE A afirmação g também não está correta porque a classe NP contém problemas decidíveis 2 Dê exemplos nome e caracterização de problemas PSPACECompletos diferentes dos presentes nas notas de aula Alguns exemplos de problemas PSPACECompletos são TQBF Fórmula Booleana Totalmente Quantificada Generalized Geography Geografia Generalizada e o jogo de xadrez A avaliação do valor verdade de uma fórmula booleana quantificada QBF com variáveis universalmente ou existencialmente quantificadas é o foco deste problema A complexidade do raciocínio sobre fórmulas lógicas com quantificadores é capturada por QBF que é PSPACEComplete No jogo Geografia Generalizada os jogadores se revezam para nomear as cidades cada uma das quais deve começar com a mesma letra da anterior Queremos evitar o uso de qualquer nome de cidade mais de uma vez É PSPACEComplete para determinar se um jogador em Geografia Generalizada tem uma estratégia bemsucedida O problema do emparelhamento perfeito testa se um determinado grafo possui um conjunto de arestas que corresponde perfeitamente a cada vértice ou um emparelhamento perfeito que é um conjunto de arestas que cobre cada vértice exatamente uma vez 3 Defina o que são as classes de complexidade de espaço L e NL dê exemplos de problemas nessas classes A coleção de problemas que podem ser resolvidos por uma Máquina de Turing Determinística L ou Não Determinística NL no Espaço Logarítmico é conhecida como classes de complexidade de espaço L e NL 1 A questão de saber se dois nós em um grafo estão conectados por um caminho é uma ilustração de um problema L O problema STCONN que pergunta se um caminho conecta dois nós específicos em um grafo direcionado é uma ilustração de um desafio em NL 4 O que é o problema da Geografia Generalizada GG e de que classe de complexidade de espaço ele é DICA Ver as páginas de 343 a 345 de Sipser 2013 Dois jogadores se revezam nomeando cidades no problema de Geografia Generalizada GG com a restrição de que cada cidade nomeada deve começar com a mesma letra que a cidade anterior terminou A intenção é evitar usar nomes de cidades duas vezes O jogo é ganho pelo jogador que não conseguir identificar uma cidade O problema GG se enquadra na classe de complexidade PSPACE que é um nome abrangente para questões decidíveis que uma Máquina de Turing Determinística pode resolver com uma certa quantidade de memória