(Cartões) Complexidade: Classes P NP

Front

O que é uma instância de um problema?

Back

Um caso particular ou exemplo do problema.

Front

Qual das seguintes afirmações sobre Classe P é verdadeira?

• NP é um subconjunto de P.
• P é um subconjunto de NP.
• P e NP são conjuntos disjuntos.
• Classe P admite soluções exponenciais.

Back

P é um subconjunto de NP.

Front

O que significa a abreviação NP em teoria da computação?

Back

"Nondeterministic Polynomial"

Front

A afirmativa: "Problemas intratáveis são aqueles para os quais o melhor limite inferior conhecido é polinomial, entretanto o melhor algoritmo conhecido é exponencial" é?

Back

Verdadeiro

Front

Se demonstrarmos que P=NP então:

Back

Todos os problemas NP passarão a fazer parte da classe P.

Front

Qual o papel de um certificado na demonstração de que um problema pertence a classe NP?

Back

Provar que uma solução é verificável em tempo polinomial.

Front

O que se deve demonstrar para um problema seja atribuído à classe NP?

Back

Que ao menos 1 instância do problema seja verificável em tempo polinomial.

Front

Qual é a relação entre um problema candidato e um problema NP-Completo conhecido em uma redução polinomial?

Back

O problema conhecido se reduz ao problema candidato.