Un compendio de problemas parametrizados en niveles superiores de la jerarquía polinómica
Autores: de Haan, Ronald; Szeider, Stefan
Idioma: Inglés
Editor: MDPI
Año: 2019
Acceso abierto
Artículo científico
2019
Un compendio de problemas parametrizados en niveles superiores de la jerarquía polinómica
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería de Software
Palabras clave
Lista
Problemas parametrizados
Clasificación de complejidad
Reducción tratable de parámetros fijos
SAT
Jerarquía Polinómica
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 31
Citaciones: Sin citaciones
Presentamos una lista de problemas parametrizados junto con una clasificación de complejidad sobre si permiten una reducción tratable de parámetros fijos a SAT o no. Estos problemas son versiones parametrizadas de problemas cuya complejidad se encuentra en el segundo nivel de la Jerarquía Polinómica o superior.
Descripción
Presentamos una lista de problemas parametrizados junto con una clasificación de complejidad sobre si permiten una reducción tratable de parámetros fijos a SAT o no. Estos problemas son versiones parametrizadas de problemas cuya complejidad se encuentra en el segundo nivel de la Jerarquía Polinómica o superior.