Classe de Complexidade P e Máquina de Turing

Classe de Complexidade P Teoria da Computação 2021 Prof Roberto C de Araujo Teoria da Computação 2021 Seja M uma máquina de Turing determinística que para sobre todas as entradas O tempo de execuçãode pior caso ou complexidade de tempo de pior caso de M é uma função f onde fn é o número máximo de passos que M usa sobre entradas de comprimentos n e onde representa o conjunto dos números naturais Se fn for o tempo de execução de M dizemos que M roda em tempo fn e que M é uma Máquina de Turing de tempo fn Normalmente n representa o comprimento da entrada da máquina Seja t R uma função Definimos por TIMEtn 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 de tempo Otn Exemplo Para a linguagem A 0k1k k 0 mostramos que ATIMEn2 Máquina M1 ATIMEnlog n Máquina M2 e ATIMEn Máquina M3 É dado destaque a quatro classes de complexidade de tempo mais importantes P NP NPcompleto e NPdifícil 1 Classe de Complexidade P P é a classe de todas as linguagens que são decidíveis em tempo polinomial sobre uma máquina de Turing determinística de uma única fita Ou seja Informalmente dizermos que um problema X pertence à classe P Isto é equivalente a dizer que X pode ser resolvido de modo eficiente e em termos formais que a linguagem formal associada ao problema X é decidível em tempo polinomial Normalmente os problemas X são formulados como problemas de decisão CAM Gst G é um grafo orientado que tem um caminho orientado de s para t A linguagem CAM está na classe de complexidade P Para provar isto devemos Apresentar uma MT M determinística de uma fita que decide CAM Mostrar que o tempo gasto por M é polinomial M Para a entrada Gst tal que G é um grafo orientado e s e t são vértices de G 1 Marque o vértice s 2 Enquanto existir uma arco u v tal que u é um vértice marcado e v é um vértice desmarcado 21 Marque o vértice v 3 Se o vértice t está marcado aceite caso contrário rejeite Para calcular o tempo de M basta preencher a tabela abaixo e calcular o tempo total gasto por M t 1 exec qtd exec t total Justifictiva Linha 1 Linha 2 Linha 21 Linha 3 2 Exercícios 1 Mostre que a linguagem abaixo está em P Conexo G G é um grafo orientado conexo OBS um grafo é conexo sse para qualquer par de vértices existir um caminho entre eles 2 Considere o seguinte problema dado um número natural n codificado em binário decidir de n é um número par Mostre que este problema está em P