Teoría de la Complejidad Computacional
Máster Universitario en Matemáticas
(Curso 2022-2023)
Tratabilidad del problema
2-SAT
El problema del subgrafo bipartito
Problemas numéricos presuntamente intratables
El problema del recubrimiento exacto de vértices
El problema del subgrafo acíclico
El problema de la satisfactibilidad para cláusulas de HORN
(
ASIGNADO:
Javier Díaz Carrera)
Sobre el
Common Algorithmic Problem
El problema TRIPARTITE-MATCHING
(
ASIGNADO:
Karen Arriagada Arévalo)
Problemas del camino hamiltoniano
Poblemas fuertemente
NP
-completos
La técnica del grafo de dependencia
Un sistema P generador de cuadrados de números naturales
(
ASIGNADO:
Aarón Ocampo Amaya)
Un sistema P generador de un conjunto numérico
Un sistema P que calcula una función parcial
Una solución del problema KNAPSACK usando sistemas P con membranas activas
Una solución del problema SAT usando sistemas P con creación de membranas
Máquinas de virus
The Relative Efficiency of Propositional Proof Systems
(
ASIGNADO:
Kevin Alexander López Aquino)
Hora
19 de enero
2 de febrero
10:30 - 11:30
Javier Díaz
Kevin López
11:30 - 12:30
Aarón Ocampo
Karen Arriagada