Uma transformação polinomial é uma ferramenta fundamental na demonstração de que determinado problema é NP-difícil.

Avalie as afirmações sobre propriedades que transformações polinomiais devem satisfazer.

I. Para toda transformação polinomial, deve existir uma Máquina de Turing determinística que a computa em tempo polinomial.

II. Se uma transformação polinomial transforma um elemento de linguagem A em um elemento de linguagem B, então A é um subconjunto não necessariamente próprio de B.

III. Se uma transformação polinomial transforma um elemento de uma linguagem A em um elemento de linguagem B, e A pertence a NP, então B pertence a NP.

IV. A quantidade de espaço utilizada pela transformação pode ser limitada por uma constante.

Está correto apenas o que se afirma em

A teoria de algoritmos de aproximação, às vezes chamados de algoritmos aproximativos, é extremamente útil para tratar problemas NP-difíceis.

Sobre algoritmos de aproximação, é correto afirmar que

Avalie as afirmações abaixo:

I. A classe P e a classe NP são disjuntas.

II. A classe P é um subconjunto da classe co-NP.

III. Problemas coNP-completos admitem um certificado tal que uma resposta negativa pode ser verificada em tempo polinomial.

IV. A interseção das classes NP e co-NP é vazia.

Está correto apenas o que se afirma em

Referente aos ciclos de vida de demanda, conforme ANSOFF, H. I.; MCDONNELL, E. J. (1993), associe as colunas, relacionando as temáticas às suas respectivas fases.

Temáticas de Procedimentos

1. Surgimento

2. Crescimento acelerado

3. Maturidade

4. Declínio

Definições conceituais

( ) Volume mais baixo de demanda, determinado por fatores demográficos e econômicos seculares, e pelas taxas de obsolescência do produto ou de consumo de produto.

( ) É o momento quando a saturação é atingida e há um substancial excesso de capacidade.

( ) Período em que o crescimento da demanda normalmente é mais rápido do que o da oferta.

( ) Período turbulento no qual uma indústria nasce e vários concorrentes procuram conquistar a liderança (ANSOFF; MCDONNELL, 1993).

A sequência correta dessa associação é