logo móvil
Contáctanos

Retraso incremental de FPT

Autores: Meier, Arne

Idioma: Inglés

Editor: MDPI

Año: 2020

Descargar PDF

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


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.

Otros recursos que podrían interesarte

Temas Virtualpro