Retraso incremental de FPT
Autores: Meier, Arne
Idioma: Inglés
Editor: MDPI
Año: 2020
Acceso abierto
Artículo científico
2020
Retraso incremental de FPT
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería de Software
Palabras clave
Teoría de la complejidad computacional
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 25
Citaciones: Sin citaciones
En este documento, estudiamos la relación de las clases de complejidad de enumeración parametrizada definidas por Creignou et al. (MFCS 2013). Específicamente, introducimos dos jerarquías (IncFPTa y CapIncFPTa) de clases de complejidad de enumeración para tiempo fpt incremental en términos de cortes de exponentes y mostramos cómo se entrelazan. Además, definimos varias clases de funciones parametrizadas y, en particular, introducimos el homólogo parametrizado de la clase de funciones multivaluadas no determinísticas con valores que son verificables polinomialmente y garantizados de existir, TFNP, conocido por Megiddo y Papadimitriou (TCS 1991). Mostramos que esta clase TF(para-NP), la restricción de la variante de función de NP a funciones totales, colapsando a F(FPT), la variante de función de FPT, es equivalente al resultado de que OutputFPT coincide con IncFPT. Además, se muestra que estos colapsos son equivalentes a TFNP = FP, y también equivalentes a P igual a NP intersección con coNP. Finalmente, mostramos que estos dos colapsos son equivalentes al colapso de IncP y OutputP en el entorno clásico. Estos resultados son las primeras conexiones directas de colapsos en complejidad de enumeración parametrizada a colapsos en complejidad de enumeración clásica, complejidad de función parametrizada, complejidad de función clásica y teoría de complejidad computacional.
Descripción
En este documento, estudiamos la relación de las clases de complejidad de enumeración parametrizada definidas por Creignou et al. (MFCS 2013). Específicamente, introducimos dos jerarquías (IncFPTa y CapIncFPTa) de clases de complejidad de enumeración para tiempo fpt incremental en términos de cortes de exponentes y mostramos cómo se entrelazan. Además, definimos varias clases de funciones parametrizadas y, en particular, introducimos el homólogo parametrizado de la clase de funciones multivaluadas no determinísticas con valores que son verificables polinomialmente y garantizados de existir, TFNP, conocido por Megiddo y Papadimitriou (TCS 1991). Mostramos que esta clase TF(para-NP), la restricción de la variante de función de NP a funciones totales, colapsando a F(FPT), la variante de función de FPT, es equivalente al resultado de que OutputFPT coincide con IncFPT. Además, se muestra que estos colapsos son equivalentes a TFNP = FP, y también equivalentes a P igual a NP intersección con coNP. Finalmente, mostramos que estos dos colapsos son equivalentes al colapso de IncP y OutputP en el entorno clásico. Estos resultados son las primeras conexiones directas de colapsos en complejidad de enumeración parametrizada a colapsos en complejidad de enumeración clásica, complejidad de función parametrizada, complejidad de función clásica y teoría de complejidad computacional.