יהי n N ותהא f:[n] [n] מחזור באורך ℓ ב f הוא סדרה k 1,k 2,...,k ℓ ∈[n] של איברים שונים עבורם f(k j)=k j+1 לכל…

יהי $n \in N$ ותהא $f:[n]\to[n]$ מחזור באורך $ℓ$ ב f הוא סדרה k_1,k_2,...,k_ℓ ∈[n] של איברים שונים עבורם $f(k_j)=k_{j+1}$ לכל $1\le j\le ℓ-1$ ובנוסף f(k_ℓ)=k_1 (תזכורת: [n] = {1,2,...,n}) נגדיר את בעיית ההכרעה הבאה. קלט: שלשה $(n,f,ℓ)$ כאשר $n,ℓ \in N$ ו f מערך המייצג פונקציה $[n]\to[n]$. שאלה: האם קיים f ב מחזור באורך לפחות $ℓ$. מהי מחלקת הסיבוכיות הקטנה ביותר אליה ידוע כי הבעייה שייכת?