CMA - Departamento de Matemática
Seminário de Investigação Operacional
Orador: Manuel Vieira - DM/CMA - FCT-UNL
Título: Relationships between minimal unsatisfiable subformulas and semidefinite certificates of infeasibility
Resumo: It is known that if the semidefinite programming (SDP) relaxation of a satistifiability (SAT) instance is infeasible, then the SAT instance is unsatisfiable. Moreover, when the SDP relaxation is infeasible, we can exhibit a proof in the form of an SDP certificate of infeasibility. We can extract information about the SAT instance from the SDP certificate of infeasibility. In particular, we show how the SDP certificate of infeasibility can provide information about minimal unsatisfiable sub-formulas.
Dia e hora: 18 de Abril, 14H00 Local: Sala de Seminários, Edifício VII