1- Podemos ter a classe P como a classe de problemas que são solúveis para um computador real como sendo uma boa aproximação para seu estudo. Sendo assim, a classe P é classe de problemas que compreende precisamente aqueles problemas que admitem algoritmo polinomial.

Assinale a alternativa que apresenta corretamente um problema que admite um algoritmo polinomial (solúvel em tempo polinomial).
Escolha uma:
a.
Problema de ordenação por inserção

b.
Problema da fatoração

c.
Problema do caminho Hamiltoniano

d.
Problema do campo minado

e.
Problema do caixeiro viajante

2-A máquina de ____________ consiste, basicamente, na construção de um algoritmo de mapeamento entre as linguagens que traduzem os problemas. Assim, se a classe de uma dessas linguagens é ____________, então se pode estabelecer algumas conclusões sobre a linguagem que se deseja investigar.

Assinale a alternativa que preenche corretamente as lacunas.
Escolha uma:
a.
redução / conhecida

b.
pilha / desconhecida

c.
redução / desconhecida

d.
Post / conhecida

e.
pilha / recursiva

3-Se uma linguagem A é redutível em tempo polinomial para outra linguagem B, sabidamente decidível em tempo polinomial por uma MT determinística, segue que existe uma MT ____________ de tempo polinomial que decide A.

Assinale a alternativa que preenche corretamente as lacunas.
Escolha uma:
a.
não-determinística

b.
de fita infinita à direita e à esquerda

c.
de múltiplas fitas

d.
determinística

e.
com múltiplas cabeças de fita