Question

1- P é a classe de linguagens que são ____________ em tempo polinomial sobre uma máquina de Turing ____________ de uma única fita.

Assinale a alternativa que preenche corretamente as lacunas.

Escolha uma:
a.
indecidíveis / otimizada

b.
parcialmente decidíveis / não-determinística

c.
decidíveis / não-determinística

d.
indecidíveis / determinística

e.
decidíveis / determinística

2-Sobre a classe P, analise as afirmativas a seguir:

I. P é invariante para todos os modelos de computação que são polinomialmente equivalentes à máquina de Turing determinística de uma única fita.

II. P aproximadamente corresponde à classe de problemas que são realisticamente solúveis num computador.

III. P é o conjunto de problemas que são decidíveis em tempo polinomial por uma máquina de Turing não-determinística.

Neste contexto, é correto o que se afirma em:

Escolha uma:
a.
I e II, apenas.

b.
I, II e III.

c.
II, apenas.

d.
I, apenas.

e.
II e III, apenas.

3-Considere o seguinte problema, solucionável por um algoritmo de tempo polinomial:

“Seja um grafo direcionado G que contém os nós s e t. O problema CAMINH é determinar se um caminho direcionado existe de s para t.”

Este é um tipo de problema que pertence a qual classe de problemas?

Escolha uma:
a.
Classe PSPACEN

b.
Classe PSPACE

c.
Classe NP

d.
Classe NP-completo

e.
Classe P

Answer 1

Resposta:

1 - decidíveis / determinística

2 - I e II, apenas.

3 - Classe P

Explicação:

Corrigido pelo AVA