T11
16 Maio 2017, 13:00 • Isabel Gama Nunes
Polynomial time reductions (packing and covering problems).
Reductions via "gadgets": the satisfiability problem (constraint satisfaction problems).
Efficient certification and the definition of NP.
16 Maio 2017, 13:00 • Isabel Gama Nunes
Polynomial time reductions (packing and covering problems).
Reductions via "gadgets": the satisfiability problem (constraint satisfaction problems).
Efficient certification and the definition of NP.