Déterminer les plus petits paramètres possibles pour FPT

Question

Je lis un livre sur l'analyse de la complexité et je ne trouve aucun moyen de résoudre un problème dans ce livre. Le problème est que je ne comprends pas comment déterminer les plus petits paramètres possibles, compte tenu de l'exécution d'un algorithme. Dois-je juste insérer certains nombres et voir si les paramètres dépassent n à un moment donné? Peut-être que quelqu'un peut m'expliquer cela.

Considérez l'exercice suivant:

Les expressions O (.) Suivantes représentent des temps d'exécution les pires cas de différents algorithmes, où n est une mesure de la taille de l'entrée et P, Q et R sont des paramètres (où p, q, r <= n). Lequel des temps de fonctionnement suivants est les temps de fonctionnement FPT? Donnez le plus petit ensemble de paramètres possible pour lesquels les temps de fonctionnement sont FPT (s'il existe) et expliquez.

un) $ O (p ^ q * n ^ 2) $

Maintenant, je sais que par la définition de FPT, ce temps d'exécution est FPT (parce que nous avons une fonction des paramètres Times N ^ constant). Cependant, quels sont les plus petits $ p $ et $ q $ dans ce cas?

Il y en a d'autres, mais je veux juste comprendre comment le résoudre, puis j'essaierai à nouveau le reste.

Pris à partir de:

ROOIJ, IV, Blokpoel, M., Kwisthout, J., et Wareham, T. (2019). Temps tractable à paramètre fixe. Dans Cognition and Intrautabilité: un guide de l'analyse de complexité classique et paramétrée (p. 125). Cambridge, Angleterre: Cambridge University Press.