TFNP – הבדלי גרסאות

[[יחס בינארי]] <math> \ P(x,y)</math> הוא ב-FTNP [[אם ורק אם]] קיים [[אלגוריתם דטרמיניסטי]] בעל [[סיבוכיות זמן|זמן ריצה פולינומי]] היכול לזהות, בהינתן x ו-y האם האם <math>\ P(x,y)=1</math> (כלומר, היחס הוא ב-[[FNP]]), ולכל x מובטח כי קיים y כך שהזוג הסדור (x,y) מקיים <math>(x,y) \in P</math>. [[אלגוריתם]] נקרא אלגוריתם TFNP אם בהינתן [[קלט]] x, האלגוריתם מוצא [[פלט]] y אחד בדיוק כך ש-<math> \ P(x,y)=1 </math>.

 

 

== לקריאה נוספת ==