ZPP היא קבוצה של בעיות שמתקבלות על ידי אלגוריתם שאף פעם לא טועה. אלגוריתם הסתברותי עושה בחירות אקראיות, כמו הטלת מטבע. תוחלת זמן ריצה היא הזמן הממוצע שהאלגוריתם לוקח.
בבעיות מסוימות יש פתרון מהיר שקובע תמיד את אותה תשובה. יש גם אלגוריתמים שמשתמשים באקראיות. חלקם יכולים לטעות לפעמים. ZPP שונה: הוא תמיד נכון. לפעמים האלגוריתם לוקח זמן ארוך, אבל בממוצע הוא קצר.
ZPP כולל בעיות שיש להן אלגוריתם שאינו טועה וזמן הממוצע שלו פולינומי. כלומר בדרך כלל הוא מהיר.
יש גם הגדרה עם מכונה שאומרת "כן", "לא" או "לא יודע". "לא יודע" פירושו לנסות שוב. המכונה לא טועה כשעונה כן או לא.
RP היא קבוצה שבה אם התשובה האמיתית היא "לא" האלגוריתם תמיד אומר "לא". אם התשובה היא "כן", הוא אולי יגיד "כן". Co-RP עושה את ההיפוך. ZPP היא החלק המשותף לשתיהן. אפשר להריץ את שני האלגוריתמים שוב ושוב עד שמקבלים תשובה ברורה.
בבעיות מסוימות יש פתרון מהיר שקובע תמיד את אותה תשובה. יש גם אלגוריתמים שמשתמשים באקראיות. חלקם יכולים לטעות לפעמים. ZPP שונה: הוא תמיד נכון. לפעמים האלגוריתם לוקח זמן ארוך, אבל בממוצע הוא קצר.
ZPP כולל בעיות שיש להן אלגוריתם שאינו טועה וזמן הממוצע שלו פולינומי. כלומר בדרך כלל הוא מהיר.
יש גם הגדרה עם מכונה שאומרת "כן", "לא" או "לא יודע". "לא יודע" פירושו לנסות שוב. המכונה לא טועה כשעונה כן או לא.
RP היא קבוצה שבה אם התשובה האמיתית היא "לא" האלגוריתם תמיד אומר "לא". אם התשובה היא "כן", הוא אולי יגיד "כן". Co-RP עושה את ההיפוך. ZPP היא החלק המשותף לשתיהן. אפשר להריץ את שני האלגוריתמים שוב ושוב עד שמקבלים תשובה ברורה.
עדיין אין תגובות. היה הראשון להגיב!
תגובות גולשים