jor

MO417 - Questão para a prova oral

Número:

Enunciado: Considere os seguintes circuitos:

I.   (x1 OR x2) OR (NOT (x1 OR x2))
II.  NOT((NOT x1) OR (NOT x2))
III. NOT((NOT x1) AND (NOT x2))

Podemos usar alguns deles para reduzir o problema SAT a um problema de satisfabilidade com apenas duas portas lógicas válidas (NOT e AND/OR).

Quais deles podemos usar para provar este problema é NP-completo, e como? Suponha que já temos como validar este problema em O(n^k).

a. circuito I, substituindo a porta AND por ele
b. circuito I, substituindo a porta OR por ele
c. circuito I e II, substituindo a porta AND por I ou a porta OR por III.
d. circuito II e III, substituindo a porta AND por II ou a porta OR por III.
e. NDA

Idéia original de: Jorge Augusto Hongo