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

אפשר להתייחס לכל <math>H</math> כאל טבלה ענקית שמכילה עבור כל קלט אפשרי את הפלט המתאים. בכל טבלה <math>2^n\cdot \ell(n)</math> סיביות בסך הכול ובתחום כולו קיימות בסך הכול <math>2^{\ell(n)\cdot 2^n}</math> פונקציות שונות עם קלט ופלט באורך המצוין. דרך אחרת היא להתייחס ל-<math>H</math> כאל פונקציה אקראית בתנאי אחד, עבור כל <math>x</math> הפונקציה בודקת תחילה אם הופיע בעבר, אם לא היא מחזירה <math>y</math> אקראי ושומרת את הזוג <math>x</math> ו-<math>y</math> במסד נתונים כלשהו. אם <math>x</math> כבר מופיע במסד הנתונים של הפונקציה משמע שכבר הוגשה שאילתה עם <math>x</math> זה ולכן היא תחזיר את <math>y</math> המתאים השמור במסד הנתונים.

 

 

==רעיון כללי==