Metraipolis › archive › dc_3be71413b7ec
Complejidad parametrizada — Wikipedia (es)
- Source
- Wikipedia (es)
- Original
- https://es.wikipedia.org/wiki/Complejidad_parametrizada
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-11-04T05:34:48.048Z
- SHA-256 of the archived text
f640351a3339be1e481a7448e076a34ac904fd3c0ca5fbb9f8d4845d231b4df1- Stable URL of this page
https://metraipolis.com/documento/dc_3be71413b7ec
How to cite
Complejidad parametrizada — Wikipedia (es) — Wikipedia (es), https://es.wikipedia.org/wiki/Complejidad_parametrizada (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_3be71413b7ec (Metraipolis archive dc_3be71413b7ec, sha256 f640351a3339be1e481a7448e076a34ac904fd3c0ca5fbb9f8d4845d231b4df1)
BibTeX
@misc{dc3be71413b7ec,
title = {Complejidad parametrizada — Wikipedia (es)},
howpublished = {Wikipedia (es)},
url = {https://es.wikipedia.org/wiki/Complejidad_parametrizada},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_3be71413b7ec; sha256 f640351a3339be1e481a7448e076a34ac904fd3c0ca5fbb9f8d4845d231b4df1},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (es), https://es.wikipedia.org/wiki/Complejidad_parametrizada. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
En ciencias de la computación, la complejidad parametrizada es una rama de la teoría de la complejidad computacional que se centra en la clasificación de problemas computacionales de acuerdo a su dificultad con respecto a varios parámetros de la entrada. La complejidad de un problema se expresa entonces mediante una función en esos parámetros. Esto permite clasificar los problemas NP-duros en una escala más fina que en la configuración clásica, donde la complejidad de un problema sólo se mide por el número de bits en la entrada. Los primeros aportes sobre complejidad parametrizada fueron realizados por Downey y Fellows (1999). Bajo el supuesto de que P ≠ NP, existen muchos problemas naturales que requieren un tiempo computacional superpolinomial cuando la complejidad se mide en términos del tamaño de la entrada solamente, pero que son computables en un tiempo polinomial con respecto al tamaño de la entrada y exponencial o peor en un parámetro k. Por lo tanto, si k se fija en un valor pequeño y el crecimiento de k es relativamente pequeño, entonces este tipo de problemas todavía puede considerarse "manejable" a pesar de su clasificación tradicional como "intratable". La existencia de algoritmos eficientes, exactos y deterministas para solucionar problemas NP-completo, o por otra parte NP-duro, se considera poco probable, si los parámetros de entrada no son fijos; todos los algoritmos conocidos para resolver estos problemas requieren tiempo exponencial (o al menos superpolinomial) en el tamaño total de la entrada. Sin embargo, algunos problemas pueden ser resueltos por algoritmos que son sólo exponencial en el tamaño de un parámetro fijo y a la vez polinomiales en el tamaño de la entrada. Tales algoritmos son llamados fixed-paramater tractable (fpt-algorithm), debido a que el problema puede resolverse eficientemente para valores pequeños del parámetro fijo. Problemas en los que se fije algún parámetro k se llaman problemas parametrizados. Un problema parametrizado por algún algoritmo FPT se dice que es un problema tratable de parámetro fijo (fixed-parameter tractable) y pertenece a la clase F P T {\displaystyle FPT} , de ahí que el primer nombre que recibiera la teoría de complejidad parametrizada fue tratabilidad de parámetro fijo (fixed-parameter tractability). Muchos problemas tienen la siguiente forma: dado un objeto x {\displaystyle x} y un entero no negativo k, determinar si x cumple alguna propiedad que depende de k. Por ejemplo, para el problema de cobertura de vértices, el parámetro puede ser el número de vértices en la cobertura. En muchas aplicaciones, por ejemplo, al modelar la corrección de errores, se puede asumir que el parámetro va a ser “pequeño” comparado con el tamaño total de la entrada. Entonces es interesante ver si podemos encontrar un algoritmo que sea exponencial sólo en k, y no en el tamaño de entrada. De esta manera, la complejidad parametrizada puede verse como un tipo de teoría de la complejidad de dos dimensiones. Este
Tema degli esploratori: scibile generale (retro-catalogo completo della fonte, senza filtro di tema) (deposito sistematico; retro-catalogo: tutte le voci di Wikipedia in spagnolo, in ordine alfabetico).
Fonte: Wikipedia in spagnolo, voce «Complejidad parametrizada» — https://es.wikipedia.org/wiki/Complejidad_parametrizada
Wikidata Q1570441: «branch of computational complexity theory» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q1570441
Autori: i contributori di Wikipedia (cronologia: https://es.wikipedia.org/wiki/Complejidad_parametrizada?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 175266780, consultata il 2026-11-04T05:25:15.697Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: e17599c0e120a9078b56bebf854116f5f571b284fd830213f80d0e930ec07d62