pau

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 2013-

Enunciado: Considere as linguagens MATCHING = {<G, k> : G é um grafo bipartido e possui um emparelhamento de cardinalidade k} e MAX-FLOW = {<G, k> : G é um grafo direcionado ponderado que possui um fluxo de valor k}. Qual/quais dos seguintes fatos não garante(m) que MATCHING ∈ P?

I - MATCHING pode ser reduzida polinomialmente a MAX-FLOW, sendo que MAX-FLOW ∈ P.

II - Existe um algoritmo A que, dado um certificado, verifica MATCHING em tempo polinomial.

III - Existe um algoritmo A' que decide MATCHING em tempo polinomial.

IV - Existe uma linguagem L ∈ P que pode ser reduzida em tempo polinomial a MATCHING.

a) I e IV

b) IV, somente.

c) II e IV.

d) II, somente.

e) N.D.A.

Ideia original de: Paulo Henrique Hack de Jesus