גישה מהירה יותר מאשר בדפדפן!
24 יחסים: EXPSPACE, EXPTIME, NL (סיבוכיות), NP (סיבוכיות), P (סיבוכיות), TQBF, משפט סביץ', משלים (מתמטיקה), מחלקת סיבוכיות, מכונת טיורינג, מכונת טיורינג לא-דטרמיניסטית, איחוד (מתמטיקה), סגירות (אלגברה), סיבוכיות מקום, סיבוכיות זמן, פולינום, רברסי, רדוקציה פולינומית, תורת הסיבוכיות, בעיית הכרעה, דטרמיניזם, הקס (משחק), כמת, כוכב קלין.
EXPSPACE
בתורת הסיבוכיות, המחלקה EXPSPACE היא קבוצת כל בעיות ההכרעה הפתירות על ידי מכונת טיורינג דטרמיניסטית ב O(2^) במַקום, כאשר P(n) מייצג פונקציה פולינומית של n. (מקצת החוקרים מגבילים את P(n) להיות פונקציה ליניארית) לחלופין, אם אנו משתמשים במכונת טיורינג לא דטרמיניסטית, אנחנו מקבלים את המחלקה NEXPSPACE, אשר שווה ל-EXPSPACE על ידי משפט סביץ'.
חָדָשׁ!!: PSPACE וEXPSPACE · ראה עוד »
EXPTIME
שרטוט סכמתי של היררכיית מחלקות הסיבוכיות בתורת הסיבוכיות, מחלקת הסיבוכיות EXPTIME (נקראת גם EXP או DEXPTIME) היא קבוצת כל בעיות ההכרעה הניתנות לפתרון באמצעות מכונת טיורינג דטרמיניסטית בזמן O(2^) כאשר O הוא סימון אסימפטוטי וp(n) הוא פולינום.
חָדָשׁ!!: PSPACE וEXPTIME · ראה עוד »
NL (סיבוכיות)
בתורת הסיבוכיות, NL (לא דטרמיניסטי עם מקום לוגריתמי) היא מחלקת סיבוכיות המכילה בעיות אשר ניתנות להכרעה על ידי מכונת טיורינג לא דטרמיניסטית אשר משתמשת בזיכרון לוגריתמי לכל היותר.
חָדָשׁ!!: PSPACE וNL (סיבוכיות) · ראה עוד »
NP (סיבוכיות)
#הפניה NP (מחלקת סיבוכיות).
חָדָשׁ!!: PSPACE וNP (סיבוכיות) · ראה עוד »
P (סיבוכיות)
#הפניה P (מחלקת סיבוכיות).
חָדָשׁ!!: PSPACE וP (סיבוכיות) · ראה עוד »
TQBF
בתורת הסיבוכיות, השפה TQBF (קיצור ל-True quantified boolean formulas; או: QBF, QSAT) היא שפה פורמלית במחלקה PSPACE.
חָדָשׁ!!: PSPACE וTQBF · ראה עוד »
משפט סביץ'
משפט סביץ' (באנגלית: Savitch's theorem), שהוכח בידי וולטר סביץ' בשנת 1970, הוא משפט בתורת הסיבוכיות שקושר בין הזיכרון הנדרש לצורך פתרון בעיות בדרך דטרמיניסטית ובין הזיכרון הנדרש כאשר ניתן להשתמש באי-דטרמיניזם.
חָדָשׁ!!: PSPACE ומשפט סביץ' · ראה עוד »
משלים (מתמטיקה)
בתורת הקבוצות, משלים של קבוצה G (באנגלית: G complement of set) הוא קבוצה אחרת, אשר מכילה את כל האיברים שאינם נמצאים ב-G. זאת ביחס לקבוצה U כלשהי שהיא "הקבוצה האוניברסלית" - קבוצה שבהקשר הנוכחי של הדיון, כל קבוצה שעליה נדבר היא תת קבוצה של U. על-פי הגדרה זו, האיחוד של קבוצת G והמשלים של G הוא הקבוצה U, ואילו החיתוך ביניהן הוא קבוצה ריקה.
חָדָשׁ!!: PSPACE ומשלים (מתמטיקה) · ראה עוד »
מחלקת סיבוכיות
במדעי המחשב ובתורת הסיבוכיות, מחלקת סיבוכיות היא אוסף בעיות בעלות סיבוכיות משותפת.
חָדָשׁ!!: PSPACE ומחלקת סיבוכיות · ראה עוד »
מכונת טיורינג
הדמיה של מכונת טיורינג מכונת טיורינג (באנגלית: Turing machine) היא מודל חישובי מתמטי אשר באמצעותו ניתן לתאר באופן מופשט את פעולתו של מחשב (כולל מחשב מודרני).
חָדָשׁ!!: PSPACE ומכונת טיורינג · ראה עוד »
מכונת טיורינג לא-דטרמיניסטית
כל אלגוריתם ניתן לתיאור על ידי מודל מתמטי מופשט המכונה מכונת טיורינג.
חָדָשׁ!!: PSPACE ומכונת טיורינג לא-דטרמיניסטית · ראה עוד »
איחוד (מתמטיקה)
בתורת הקבוצות ובענפים אחרים במתמטיקה, האיחוד של אוסף של קבוצות הוא קבוצה המכילה את כל מה ששייך לקבוצות אלה, ושום דבר אחר.
חָדָשׁ!!: PSPACE ואיחוד (מתמטיקה) · ראה עוד »
סגירות (אלגברה)
באלגברה, קבוצה נקראת סגורה תחת פעולה מסוימת המוגדרת עליה, כאשר הפעלת הפעולה על איברי הקבוצה נותנת איבר הנכלל אף הוא בקבוצה.
חָדָשׁ!!: PSPACE וסגירות (אלגברה) · ראה עוד »
סיבוכיות מקום
במדעי המחשב, כאשר עוסקים בניתוח המשאבים שדורשים אלגוריתמים משתמשים במושג של סיבוכיות מקום (המכונה גם סיבוכיות זיכרון) על מנת להעריך את כמות זיכרון המחשב הדרוש להם.
חָדָשׁ!!: PSPACE וסיבוכיות מקום · ראה עוד »
סיבוכיות זמן
פונקציות הנפוצות בניתוח אלגוריתמים המציגות את מספר הפעולות הנדרשות לפונקציה לעומת גודל הקלט בתורת החישוביות, סיבוכיות זמן של אלגוריתם היא הערכה, באמצעות חסמים, על מספר הפעולות שמבצע האלגוריתם כפונקציה של גודל הקלט.
חָדָשׁ!!: PSPACE וסיבוכיות זמן · ראה עוד »
פולינום
במתמטיקה, פולינום במשתנה \ x הוא ביטוי מהצורה \ a_0 + a_1 x + \cdots + a_n x^n כאשר \ a_0,a_1,\dots,a_n הם קבועים; למשל, 3x^2+7x-5.
חָדָשׁ!!: PSPACE ופולינום · ראה עוד »
רברסי
משחק רברסי לוח רברסי מעץ רברסי או אותלו הוא משחק לוח חשיבתי ותיק ונפוץ, עבור שני שחקנים.
חָדָשׁ!!: PSPACE ורברסי · ראה עוד »
רדוקציה פולינומית
#הפניה רדוקציה חישובית.
חָדָשׁ!!: PSPACE ורדוקציה פולינומית · ראה עוד »
תורת הסיבוכיות
תורת הסיבוכיות היא ענף של מדעי המחשב, שבמסגרתו חוקרים את הסיבוכיות של בעיות; כלומר, נבחנים המשאבים הנחוצים לפתרון בעיה נתונה באמצעות מחשב, ומושווית יעילותם של אלגוריתמים שונים בפתרון בעיה זו.
חָדָשׁ!!: PSPACE ותורת הסיבוכיות · ראה עוד »
בעיית הכרעה
150 פיקסלים במתמטיקה ובמדעי המחשב, בעיית הכרעה היא בעיה אשר יש לה תשובה של "כן" או "לא".
חָדָשׁ!!: PSPACE ובעיית הכרעה · ראה עוד »
דטרמיניזם
דֵּטֶרְמִינִיזְם או כּוֹרְחָנוּת היא השקפה פילוסופית לפיה כל מאורע בעולם, פעולות, החלטות או מחשבות אנושיות נקבעים באופן בלעדי על ידי אירועים קודמים.
חָדָשׁ!!: PSPACE ודטרמיניזם · ראה עוד »
הקס (משחק)
הקס הוא שמו של משחק לוח המתנהל על לוח מרוצף משושים.
חָדָשׁ!!: PSPACE והקס (משחק) · ראה עוד »
כמת
100px בלוגיקה, כַּמָּת הוא סמל המציין את התחולה של המשתנה הצמוד לו.
חָדָשׁ!!: PSPACE וכמת · ראה עוד »
כוכב קלין
בלוגיקה מתמטית ומדעי המחשב, כוכב קלין או סגור קלין ובסימון מתמטי * (Kleene Star, Kleene Closure) היא פעולה אונארית, על קבוצה של מחרוזות או על קבוצה של תווים כלשהם.
חָדָשׁ!!: PSPACE וכוכב קלין · ראה עוד »
אזכור
[1] https://he.wikipedia.org/wiki/PSPACE
