| dbo:abstract
|
- 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 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 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 . Bajo el supuesto de que , existen muchos problemas naturales que requieren un 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 , 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 (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 , 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 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 concepto se formaliza de la siguiente forma: Un problema parametrizado es un lenguaje , donde es un alfabeto finito. El segundo componente sería el parámetro del problema.Un problema parametrizado es un fpt si la interrogante “¿?” puede ser resuelta en tiempo , donde es una función arbitraria que depende sólo de . La clase de complejidad correspondiente se llama FPT. Por ejemplo, hay un algoritmo que resuelve el problema de cobertura de vértices en tiempo , donde es el número de vértices y es el tamaño de la cobertura. Esto significa que la cobertura de vértice es fpt tomando como parámetro el tamaño de la solución. (es)
- Die parametrisierte Algorithmik ist ein relativ junges Teilgebiet der theoretischen Informatik, in dem genauer untersucht wird, welche Instanzen von NP-vollständigen Problemen effizient zu lösen sind. Dabei wird untersucht, von welchen Faktoren (Parametern) die Laufzeit der Algorithmen im Wesentlichen abhängt. Zum Beispiel sind viele Graphen-Probleme schnell lösbar für Graphen mit kleiner Baumweite. Formal ist ein Problem parametrisierbar (auch: fixed parameter tractable oder FPT), wenn ein Algorithmus existiert, der es mit einer Laufzeit von löst, wobei f eine berechenbare Funktion, k der Parameter, p ein beliebiges Polynom und n die Eingabelänge (z. B. bei Graphenproblemen die Anzahl der Knoten und Kanten) ist. Man beachte, dass ein Problem mit unterschiedlichen Parametern sowohl FPT, als auch nicht-FPT sein kann. Zum Beispiel ist das Cliquenproblem nicht-FPT, wenn der Parameter die Größe einer maximalen Clique ist, aber FPT, wenn der Parameter die Baumweite oder der Maximalgrad ist. Man sagt auch, dass ein Problem parametrisierbar in dem entsprechenden Parameter ist, z. B. "Das Cliquen-Problem ist parametrisierbar in der Baumweite".Anschaulich ist ein Parameter, in dem ein NP-vollständiges Problem parametrisierbar ist, eine Eigenschaft, die das exponentielle Wachstum der Laufzeiten verursacht, da diese Probleme schnell lösbar sind, bis auf Instanzen, bei denen dieser Parameter groß ist. In der Praxis ist f oft eine unangenehme Funktion wie , man geht im Allgemeinen aber davon aus, dass k sehr klein ist (weil dies bei Instanzen, die in der Praxis vorkommen, häufig der Fall ist) und n groß werden kann. Parametrisierte Algorithmen sind in der Praxis (wo k klein ist) auch für n=50–100 praktikabel, wogegen z. B. gewöhnliche Brute-Force Algorithmen mit Laufzeiten wie schon ab etwa n=20 nicht mehr praktikabel sind. Das Gebiet wurde von Rod Downey und Michael Fellows in den 1990er Jahren begründet. (de)
- 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 or output. The complexity of a problem is then measured as a function of 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 as a function of the number of bits in the input. The first systematic work on parameterized complexity was done by . Under the assumption that P ≠ NP, there exist many natural problems that require superpolynomial running time when complexity is measured in terms of the input size only, but that are computable in a time that is polynomial in the input size and exponential or worse in a parameter k. Hence, if k is fixed at a small value and the growth of the function over k is relatively small then such problems can still be considered "tractable" despite their traditional classification as "intractable". 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 (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. Problems in which some parameter k is fixed are called parameterized problems. A parameterized problem that allows for such an fpt-algorithm is said to be a fixed-parameter tractable problem and belongs to the class FPT, and the early name of the theory of parameterized complexity was fixed-parameter tractability. Many problems have the following form: given an object x and a nonnegative integer k, does x have some property that depends on k? For instance, for the vertex cover problem, the parameter can be the number of vertices in the cover. In many applications, for example when modelling error correction, one can assume the parameter to be "small" compared to the total input size. Then it is challenging to find an algorithm which is exponential only in k, and not in the input size. In this way, parameterized complexity can be seen as two-dimensional complexity theory. This concept is formalized as follows: A parameterized problem is a language , where is a finite alphabet. The second component is called the parameter of the problem.A parameterized problem L is fixed-parameter tractable if the question "?" can be decided in running time , where f is an arbitrary function depending only on k. The corresponding complexity class is called FPT. For example, there is an algorithm which solves the vertex cover problem in time, where n is the number of vertices and k is the size of the vertex cover. This means that vertex cover is fixed-parameter tractable with the size of the solution as the parameter. (en)
- En algorithmique, la complexité paramétrée (ou complexité paramétrique) est une branche de la théorie de la complexité qui classifie les problèmes algorithmiques selon leur difficulté intrinsèque en fonction de plusieurs paramètres sur les données en entrée ou la sortie. Ce domaine est étudié depuis les années 90 comme approche pour la résolution exacte de problèmes NP-complets. Cette approche est utilisée en optimisation combinatoire, notamment en algorithmique des graphes, en intelligence artificielle, en théorie des bases de données et en bio-informatique. (fr)
- Em ciência da computação, complexidade parametrizada é um ramo da teoria da complexidade computacional que foca em classificar problemas computacionais de acordo com sua dificuldade inerente com respeito a múltiplos parâmetros da entrada. A complexidade de um problema é, então, definida como uma função nesses parâmetros. Isso permite a classificação de problemas NP-difíceis em uma escala mais rigorosa que da forma clássica, em que a complexidade do problema é medida de acordo com o número de bits da entrada. O primeiro trabalho sistemático em complexidade parametrizada foi realizado por . Sob a hipótese de que P ≠ NP, existem vários problemas naturais que requerem tempo de execução superpolinomial quando a complexidade é medida apenas em termos do tamanho da entrada, mas são computáveis em tempo polinomial no tamanho da entrada e em tempo exponencial ou pior em um parâmetro . Consequentemente, se é fixado em um valor pequeno e o crescimento da função sobre é relativamente pequeno então tais problemas podem ainda ser considerados tratáveis, apesar de sua classificação tradicional como intratável. A existência de algoritmos eficientes, exatos e determinísticos que resolvam problemas NP-completos, ou mesmo NP-difíceis é considerada improvável, se parâmetros de entrada não são fixados; todos os algoritmos conhecidos que resolvem esses problemas requerem tempo (ou pelo menos superpolinomial) no tamanho total da entrada. Entretanto, alguns problemas podem ser resolvidos por algoritmos que são exponenciais apenas no tamanho de um parâmetro fixo enquanto são polinomiais no tamanho da entrada. Tal algoritmo é chamado de tratável em parâmetro fixo (fpt-)algoritmo (na sigla em inglês), porque o problema pode ser resolvido eficientemente para valores pequenos do parâmetro fixo. Problemas em que algum parâmetro é fixado são chamados de problemas parametrizados. Um problema parametrizado que permite um fpt-algoritmo é dito ser tratável em parâmetro fixo e pertence à classe , e o antigo nome para a teoria da complexidade parametrizada era tratabilidade em parâmetro fixo. Muitos problemas possuem o seguinte formato: dado um objeto e um inteiro não-negativo , possui alguma propriedade que depende de ? Por exemplo, para o problema da cobertura de vértices, o parâmetro pode ser o número de vértices na cobertura. Em muitas aplicações, por exemplo durante a modelagem de correção de erros, pode-se assumir que o parâmetro é "pequeno" em relação ao tamanho total da entrada. Sendo assim, é interessante verificar se pode-se encontrar um algoritmo que é exponencial apenas em , e não no tamanho da entrada. Dessa forma, complexidade parametrizada pode ser vista como uma teoria da complexidade bidimensional. Esse conceito é formalizado da seguinte forma: Um problema parametrizado é uma linguagem , em que é um alfabeto finito. O segundo componente é chamado de parâmetro do problema.Um problema parametrizado é tratável em parâmetro fixo se a questão “?” pode ser decidida em tempo , em que é uma função arbitrária dependendo unicamente de . A classe de complexidade correspondente é FPT. Por exemplo, há um algoritmo que resolve o problema de cobertura de vértices em tempo , em que é o número de vértices e é o tamanho da cobertura de vértices. Isso significa que o problema de cobertura de vértices é tratável em parâmetro fixo com o tamanho da solução agindo como parâmetro. (pt)
|
