Teo12
22 Maio 2018, 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.
22 Maio 2018, 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.