|
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 {{harvtxt|Downey|Fellows|1999}}.
In [[computer science]], '''parameterized complexity''' is a branch of [[computational complexity theory]] that focuses on classifying [[computational problems]] according to their inherent difficulty with respect to ''multiple'' parameters of the input. The complexity of a problem is then measured as a [[Function (mathematics)|function]] in those parameters. This allows the classification of [[NP-hard]] problems on a finer scale than in the classical setting, where the complexity of a problem is only measured by the number of bits in the input.
The first systematic work on parameterized complexity was done by {{harvtxt|Downey|Fellows|1999}}.
UnderBajo theel assumptionsupuesto thatde que [[P versus NP problem|P ≠ NP]], thereexisten existmuchos manyproblemas naturalnaturales problemsque thatrequieren require superpolynomialun [[runningtiempo timecomputacional]] whensuperpolinomial complexitycuando isla measuredcomplejidad inse termsmide ofen thetérminos inputdel sizetamaño onlyde la entrada solamente, butpero thatque areson computablecomputables inen aun timetiempo thatpolinomial iscon polynomialrespecto inal thetamaño inputde size andla exponentialentrada ory worseexponencial ino apeor en un parameterparámetro ''k''. HencePor lo tanto, ifsi ''k'' isse fixedfija aten a small valueun andvalor thepequeño growthy ofel the functioncrecimiento overde ''k'' ises relativelyrelativamente smallpequeño, thenentonces sucheste problemstipo cande stillproblemas betodavía consideredpuede considerarse "tractablemanejable" despitea pesar de theirsu traditionalclasificación classificationtradicional ascomo "intractableintratable".
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.
The existence of efficient, exact, and deterministic solving algorithms for [[NP-complete]], or otherwise [[NP-hard]], problems is considered unlikely, if input parameters are not fixed; all known solving algorithms for these problems require time that is [[Exponential time|exponential]] (or at least superpolynomial) in the total size of the input. However, some problems can be solved by algorithms that are exponential only in the size of a fixed parameter while polynomial in the size of the input. Such an algorithm is called a [[fixed-parameter tractable]] (fpt-)algorithm, because the problem can be solved efficiently for small values of the fixed parameter.
ProblemsProblemas inen whichlos someque parameterse kfije isalgún fixedparámetro arek calledse parameterizedllaman problemsproblemas parametrizados. AUn parameterizedproblema problemparametrizado thatpor allowsalgún foralgoritmo suchFPT anse fpt-algorithmdice isque saides toun be'''problema atratable de parámetro fijo''' ('''fixed-parameter tractable''') problemy andpertenece belongs toa thela classclase <math>FPT</math>, andde theahí earlyque nameel ofprimer thenombre theoryque ofrecibiera parameterizedla complexityteoría wasde complejidad parametrizada fue '''tratabilidad de parámetro fijo''' ('''fixed-parameter tractability''').
ManyMuchos problemsproblemas havetienen thela followingsiguiente formforma: givendado anun objectobjeto <math>x</math> andy aun nonnegativeentero integerno negativo ''k'', doesdeterminar si ''x'' havecumple somealguna propertypropiedad thatque dependsdepende onde ''k''?. Por For instanceejemplo, forpara el problema thede [[vertexcobertura coverde problemvértices]], theel parameterparámetro canpuede beser theel numbernúmero ofde verticesvértices inen thela covercubertura. InEn manymuchas applicationsaplicaciones, forpor exampleejemplo, al modelar whenla modellingcorrección errorde correctionerrores, onese canpuede assumeasumir theque parameterel toparámetro beva "small"a comparedser to“pequeño” thecomparado totalcon inputel size.tamaño Thentotal itde isla interestingentrada. toEntonces seees whetherinteresante wever cansi findpodemos anencontrar algorithmun whichalgoritmo isque exponentialsea exponencial ''onlysólo'' inen ''k'', andy no noten inel thetamaño inputde sizeentrada.
De esta manera, la complejidad parametrizada puede verse como un tipo de teoría de la complejidad de ''dos dimensiones''. Este concepto se formaliza de la siguiente forma:
In this way, parameterized complexity can be seen as ''two-dimensional'' complexity theory. This concept is formalized as follows:
:AUn ''parameterizedproblema problemparametrizado'' ises aun languagelenguaje <math>L \subseteq \Sigma^* \times \N</math>, wheredonde <math>\Sigma</math> ises aun finitealfabeto alphabetfinito. TheEl secondsegundo componentcomponente issería called theel ''parameterparámetro'' of thedel problemproblema.
:AUn parameterizedproblema problemparametrizado <math>L</math> ises ''fixed-parameterun tractable''fpt ifsi thela questioninterrogante ““¿<math>(x, k) \in L</math>?”” canpuede beser decidedresuelta in runningen timetiempo <math>f(k) \cdot |x|^{O(1)}</math>, wheredonde <math>f</math> ises anuna arbitraryfunción functionarbitraria dependingque onlydepende onsólo de <math>k</math>. TheLa clase de correspondingcomplejidad complexity classcorrespondiente isse calledllama '''FPT'''.
ForPor exampleejemplo, therehay isun analgoritmo algorithmque whichresuelve solvesel theproblema vertexde covercobertura problemde invértices en tiempo <math>O(kn + 1.274^k)</math> time, <ref>{{harvnb|Chen|Kanj|Xia|2006}}</ref> wheredonde <math>n</math> ises theel numbernúmero ofde verticesvértices andy <math>k</math> is thees sizeel oftamaño thede vertexla covercobertura. ThisEsto meanssignifica thatque vertexla covercobertura isde fixed-parametervértice tractablees withfpt thetomando sizecomo ofparámetro theel solutiontamaño asde thela parametersolución.
==Clases de Complejidad==
== Complexity classes ==
===FPT===
FPTContiene contains thelos ''fixedproblemas parametertratables tractablede parámetro fijo'' problems, which are thoselos thatcuales canpueden beser solvedresueltos inen timetiempo <math>f(k) \cdot {|x|}^{O(1)}</math> forpara somealguna computablefunción functioncomputable ''f''. Typically,Por thislo functiongeneral, isesta thoughtfunción ofse asconsidera singlecomo exponential,única suchexponencial, ascomo <math>2^{O(k)}</math> butpero thela definitiondefinición admitsadmite functionsfunciones thatque growcrecen evenaún fastermás rápido. ThisEsto ises essentialesencial forpara auna largegran partparte ofde thela earlyhistoria historytemprana ofde thisesta classclase. TheLa crucialparte partesencial ofde thela definitiondefinición ises toexcluir excludefunciones functionsde ofla the formforma <math>f(n,k)</math>, suchtal ascomo <math>n^k</math>. La Theclase classde parámetro fijo lineal ('''FPL''' (fixedpor sus siglas parameteren linearinglés) ises thela classclase ofde problemsproblemas solvableresolubles inen timetiempo <math>f(k) \cdot |x|</math> forpara somealguna función computable function ''f'' [Grohe, 1999]. FPL is thuses auna subclasssubclase ofde FPT.
AnUn exampleejemplo ises theel problema de [[satisfiabilitysatisfacibilidad]] problem, parameterisedparametrizado bypor theel numbernúmero ofde variables. ADada givenuna formulafórmula ofde sizetamaño ''m'' withcon ''k'' variables canpuede beser checkedverificada bymediante brutefuerza forcebruta inen timetiempo <math>O(2^km)</math>. AUna [[vertexcobertura coverde vértices]] ofde sizetamaño ''k'' inen aun graphgrafo ofde orderorden ''n'' canpuede beser foundencontrada inen timetiempo <math>O(2^kn)</math>, sopor tanto thiseste problemproblema isestá alsotambién inen FPT.
AnUn exampleejemplo ofde aun problemproblema thatque isno thoughtpertenece nota toesta beclase in FPTes isla [[graphcoloración coloringde un grafo]] parameterisedparametrizada bypor theel numbernúmero ofde colorscolores. ItSe isconoce knownque thatel problema de saber si un grafo se puede colorear con a lo sumo 3-coloring iscolores es [[NP-hardduro]], andy anun algorithmalgoritmo forpara graphgrafos ''k''-colouringcoloreables inde timetiempo <math>f(k)n^{O(1)}</math> forpara ''k''=3 wouldcorre runen intiempo polynomialpolinomial timeen inel thetamaño sizede ofla the inputentrada. ThusPor tanto, ifsi este graphproblema coloringes parameterisedparametrizado byen theel numbernúmero ofde colorscolores weredentro inde FPT, thenentonces P=NP.
ThereHay arevarias a number of alternativealternativas definitionspara ofdefinir FPT. ForPor exampleejemplo, theel runningrequerimiento timede requirementtiempo cancomputacional bepuede replacedser byremplazado por <math>f(k) + |x|^{O(1)}</math>. AlsoTambién, aun parameterisedproblema problemparametrizado isestá inen FPT ifsi iteste hastiene aun so-calledcierto kernel. La [[KernelizationKernelización]] ises aun preprocessingpreproceso techniquetécnico thatque reducesreduce thela instancia original instancea toeste its“kernel “hard kernel”fuerte”, auna possiblyposible muchinstancia smallermucho instancemás thatpequeña isque equivalentes toequivalente thea originalla instanceinstancia butoriginal haspero atiene sizeun thattamaño isacotado boundedpor by auna functionfunción inen theel parameterparámetro.
FPT ises closedencerrada underdentro ade parameteriseduna [[Reduction (complexity)|reductionreducción]] calledparametrizada llamada '''''fpt-reduction''''', whichla cual simultáneamente preserva simultaneouslyel preservestamaño thede instancela sizeinstancia andy theel parameterparámetro.
ObviouslyObviamente, FPT containscontiene alla polynomial-timetodos computablelos problemsproblemas de orden polinomial. MoreoverAdemás, itcontiene containsa alltodos optimisationlos problemsproblemas inde optimización en NP thatque allowtienen aun esquema de aproximación polinomial ([[Fully polynomial-time approximation scheme]]).
===''W'' hierarchy===
===Jerarquía ''W''===
The '''''W'' hierarchy''' is a collection of computational complexity classes. A parameterised problem is in the class ''W''[''i''], if every instance <math>(x, k)</math> can be transformed (in fpt-time) to a combinatorial circuit that has weft at most ''i'', such that <math>(x, k)\in L</math> if and only if there is a satisfying assignment to the inputs, which assigns ''1'' to at most ''k'' inputs. The height thereby is the largest number of logical units with unbounded fan-in on any path from an input to the output. The number of logical units with bounded fan-in on the paths must be limited by a constant that holds for all instances of the problem.
Es una colección de clases de complejidad computacional. Un problema parametrzado está en la clase ''W[''i''], si toda instancia <math>(x, k)</math> puede ser transformada (en tiempo fpt) a un camino combinatorio que tenga un weft de a lo sumo ''i'', tal que <math>(x, k)\in L</math> si y solo si existe una asignación satisfactoria para la entrada, la cual asigne ''1'' a lo sumo ''k'' entradas. La altura es el mayor número de unidades lógicas en algún camino desde la entrada hasta la salida. El numero de unidades lógicas acotadas en el camino debe ser limitado por una constante que encierre a todas las instancias del problema.
NoteNotar thatque FPT = ''W''[0] andy W[''i''] <math>\subseteq</math> ''W''[''j''] forpara alltodo <math>i\le j</math>. Las Theclases classesen inla thejerarquía ''W'' hierarchyson aretambién alsoencerradas closeddentro underde fpt-reduction.
ManyMuchos naturalproblemas computationalcomputacionales problemsnaturales occupyocupan thelos lowerniveles levelsmás bajos, ''W''[1] andy ''W''[2].
====''W''[1]====
ExamplesEjemplos ofde problemas ''W''[1]-completecompleto problemspueden includeser
* decidingDecidir ifsi aun givengrafo graphdado containscontiene aun [[Clique (graph theory)|clique]] ofde sizetamaño ''k''
* decidingDecidir ifsi aun givengrafo graphdado containscontiene anun [[Independent set (graph theory)|independentconjunto setindependiente]] ofde sizetamaño ''k''
* Decidir si un autómata no determinista reconoce la cadena con ''k'' pasos (problema de “aceptación mínima de un autómata”).
* deciding if a given nondeterministic single-tape Turing machine accepts within ''k'' steps ("short Turing machine acceptance" problem)
====''W''[2]====
Examples of ''W''[2]-complete problems include
Ejemplos de problemas ''W''[2]-completos pueden ser
* deciding if a given graph contains a [[dominating set]] of size ''k''
* Decidir si un grafo dado contiene un [[conjunto dominante]] de tamaño ''k''.
* deciding if a given nondeterministic [[Turing machine equivalents#Multi-tape Turing machines|multi-tape Turing machine]] accepts within ''k'' steps ("short multi-tape Turing machine acceptance" problem)
* Decidir una [[Turing machine equivalents#Multi-tape Turing machines|máquina de Turing con cinta multi-pista]] reconoce la cadena usando ''k'' pasos (problema de “aceptación mínima de un máquina de Turing con cinta multi-pista”).
==== ''W''[''t''] ====
<math>W[t]</math>Puede canser bedefinido definedusando usingla thefamilia familyde ofproblemas '''Weighted Weft-<math>t</math>-Depth-<math>d</math> SAT''' problems forcon <math>d\geq t</math> : <math>W[t,d]</math> es la clase de problemas parametrizados que se fpt-reduce a este problema, y <math>W[t] = \bigcup_{d\geq t} W[t,d]</math>.
<math>W[t,d]</math> is the class of parameterized problems that fpt-reduce to this problem, and <math>W[t] = \bigcup_{d\geq t} W[t,d]</math>.
Here,El problema '''Weighted Weft-<math>t</math>-Depth-<math>d</math> SAT''' ispuede ser enunciado de thela followingmanera problemsiguiente:
* InputEntrada: A BooleanUna formula ofboleana depthde profundidad a atlo mostsumo <math>d</math> andy "weft" atmenor mostque <math>t</math>, andy aun numbernúmero <math>k</math>. TheLa ''depthprofundidad'' ises theel maximalmáximo numbernúmero ofde gatesnodos onen anyalgún pathcamino fromdesde thela root toraíz a leafuna hoja, andy theel ''weft'' ises theel maximalmáximo numbernúmero ofde gatesnodos ''ofde fan-inentradas aten leastalgún three''camino onde anyla pathraíz froma the root to auna leafhoja.
* QuestionPregunta: Does¿Existe theuna formulaasignación havesatisfactoria apara satisfyingdicha assignmentfórmula ofen la que ''Hamming weight'' sea atmenor mostque <math>k</math>?
ItSe canpuede bemostrar shownque thatel the problemproblema Weighted <math>t</math>-Normalize SAT ises completecompleto forpara <math>W[t]</math> underdentro de fpt-reductions.<ref>{{cite journal| author=Buss, Jonathan F, Islam, Tarique| title=Simplifying the weft hierarchy| journal=Theoretical Computer Science| year=2006| volume=351| number=3| pages=303–313| publisher=Elsevier| accessdate=16 April 2014| doi=10.1016/j.tcs.2005.10.002}}</ref> Este problema se puede plantear como:
Here, '''Weighted <math>t</math>-Normalize SAT''' is the following problem:
* InputEntrada: AUna Booleanfórmula formulaboleana ofcon depthprofundidad ata lo mostsumo <math>t</math> withy anun AND-gate onen topel tope, andy aun numbernúmero <math>k</math>.
* QuestionPregunta: Does¿Existe theuna formulaasignación havesatisfactoria apara satisfyingdicha assignmentfórmula ofen la que ''Hamming weight'' atsea mostmenor que <math>k</math>?
====''W''[''P'']====
''W''[''P'']Es isla thecase classde ofproblemas problemsque thatpueden canser bedecididos decideden bytiempo apolinomial nondeterministicmediante polynomial-timeun Turing-machineautómata thatno makesdeterministas aten mosta lo sumo <math>O(f(k)\cdot \log n)</math> nondeterministic choices in the computationpara oncomputar <math>(x,k)</math> (a ''k''-restricted Turing-machine).{{harvtxt|Flum|Grohe|2006}}
ItSe issabe known thatque FPT isestá containedincluido inen ''W''[''P''], andy thela inclusioninclusión ises believedconsiderada toestricta. be strict.Sin Howeverembargo, resolvingresolver thiseste issueproblema woulddebe implyimplicar ala solutionsolución tode thela relación [[P versuscontra NP]] problem.
OtherOtras connectionsconexiones topara unparameterisedla computationalcomplejidad complexitycomputacional areno thatparametrizada son que FPT equalsigual ''W''[''P''] ifsi andy onlysolo ifsi el [[circuitcamino de satisfiabilitysatisfacibilidad]] canpuede beser decideddecidido inen timetiempo <math>\exp(o(n))m^{O(1)}</math>, oro ifsi andy onlysolo ifsi therehay is auna computable, nondecreasingno decreciente, unbounded functionfunción f suchtal thatque alltodos languageslos recognisedlenguajes byreconocido aen nondeterministictiempo polynomial-timepolinomial Turingmediante machineun usingautómata no determinista usando f(n)log (n) nondeterministic choicesestán areen in ''P''.
=== XP ===
'''XP''' ises thela classclase ofde parameterizedproblemas problemsparametrizados thatque canpueden beser solvedresueltos inen timetiempo <math>n^{f(k)}</math> forpara somealguna computable functionfunción <math>f</math> computable.
{{Expand section|date=April 2011}}
[[Category:Computational complexity theory]]
[[Category:Parameterized complexity| ]]
[[en:Uplands]]
[[es:Uplands]]
| 