|
כאשר רמת הסיבוכיות של בעיה היא [[פולינום|פולינומית]] (או פחות מזה) הבעיה נחשבת כבעלת פתרון "[[חישוב יעיל|יעיל]]", משום שהגדלת אורך הקלט אינה מביאה לשינוי דרמטי בזמן הנחוץ לפתרון הבעיה. לעומת זאת, כאשר לבעיה סיבוכיות [[פונקציה מעריכית|מעריכית]] (אקספוננציאלית), שינוי קטן באורך הקלט מביא לשינוי מהותי בזמן הנחוץ לפתרון הבעיה. לדוגמה, כאשר הזמן הנחוץ לפתרונה של בעיה הוא <math>\ O(2^n)</math> (סיבוכיות מעריכית) הגדלת אורך הקלט ב-1 מביאה להכפלת הזמן הנחוץ לפתרון הבעיה.
==סוגים שונים של סיבוכיות== ▼==בעיות הכרעה==
בנוסף ל[[סיבוכיות זמן]] ו[[סיבוכיות מקום]] שהוזכרו קודם, ישנם סוגים נוספים של מדדי סיבוכיות המשמשים בעיקר ל[[הבטחת איכות תוכנה]]. הבולט שבהם הוא [[סיבוכיות קוד]]. '''סיבוכיות קוד''' הוא מדד המאפיין את המורכבות של קוד תוכנה, ולמימושים שונים של אותו [[אלגוריתם]] יכולים להיות ערכי סיבוכיות קוד שונים, למרות שסיבוכיות המקום והזמן תשאר זהה. ▼חלק ניכר מתורת הסיבוכיות עוסק ב[[בעיית הכרעה|בעיות הכרעה]], שהן בעיות שבהן נדרשת התשובה הקצרה "כן" או "לא". דוגמה: הבעיה האם [[מספר טבעי]] נתון הוא [[מספר ראשוני]]. העניין בבעיות הכרעה נובע מכך שהטיפול המתמטי בהן הוא פשוט, שכן התשובה לבעיה מוגבלת ל"כן" ו"לא". עם זאת, בעיות שאינן בעיות הכרעה ניתנות להמרה בבעיות הכרעה שקולות.
דוגמה לכך היא הבעיה ''האם יש גורם ראשוני'': כאשר נתונים שני [[מספר טבעי|מספרים טבעיים]], n ו-k, ענה האם ל-n יש גורם ראשוני קטן מ-k. אם אנו מסוגלים לפתור את בעיית ההכרעה הזו באמצעות משאבים בסדר גודל מסוים, אנו יכולים לפתור את הבעיה "פירוק לגורמים", שאינה בעיית הכרעה, באמצעות משאבים מאותו סדר גודל, וזאת על ידי סדרה של שאלות התוחמות את ערכו האפשרי של k.
תורת הסיבוכיות מבחינה לעתים קרובות בין התשובה "כן" לתשובה "לא". דוגמה: הקבוצה [[NP (סיבוכיות)|NP]] היא קבוצת הבעיות שבהן התשובה "כן" ניתנת לבדיקה בזמן סביר. הקבוצה [[Co-NP]] היא קבוצת הבעיות שבהן התשובה "לא" ניתנת לבדיקה בזמן סביר. הקידומת Co היא קיצורה של המלה complement - משלים. המשלים של בעיה נתונה היא הבעיה שבה כל התשובות "כן" ו"לא" מוחלפות זו בזו. הבעיה "האם ראשוני" והבעיה "האם פריק" (מספר פריק הוא מספר שאינו ראשוני) משלימות זו את זו.
'''האם [[P=NP]]?'''
הקבוצה [[P (סיבוכיות)|P]] היא קבוצת כל בעיות ההכרעה שניתן לפתור אותן באמצעות [[מכונת טיורינג|מכונה דטרמיניסטית]] ב[[זמן ריצה פולינומי|זמן פולינומי]]. הקבוצה [[NP (סיבוכיות)|NP]] היא קבוצת כל בעיות ההכרעה שניתן לפתור אותן באמצעות [[מכונת טיורינג לא-דטרמיניסטית|מכונה לא דטרמיניסטית]] ב[[זמן ריצה פולינומי|זמן פולינומי]], או - לחליפין - לבדוק נכונות של פתרון נתון ב[[זמן ריצה פולינומי|זמן פולינומי]]. השאלה "האם הקבוצה [[P (סיבוכיות)|P]] שווה לקבוצה [[NP (סיבוכיות)|NP]]" היא השאלה המרכזית במדעי המחשב. זו שאלה פתוחה, [[מכון קליי למתמטיקה]] מציע פרס של מיליון דולר לראשון שיפתור אותה.
ניתן יהיה להכריע בשאלה האם [[P=NP]] על ידי הכרעת השאלה האם יש ב-P בעיה [[NP-שלמה]].
מכונה דטרמיניסטית היא [[מכונת טיורינג]], או, לצורך הפשטות, מחשב רגיל, כזה המבצע את הוראות תוכנית צעד אחר צעד. מכונה לא דטרמיניסטית היא מכונה שבה ניתן לבצע גם הוראת התפצלות, שבה ביצוע התוכנית מתפצל למסלולים מקבילים, ודי שבאחד מהם תתקבל תשובה לבעיית ההכרעה. כל בעיה שניתן לפתור באמצעות מכונה לא דטרמיניסטית ניתן לפתור גם באמצעות מכונה דטרמיניסטית. במבט ראשון נוצר הרושם שמכונה לא דטרמיניסטית מהירה ממכונה דטרמיניסטית, בזכות המסלולים המקבילים שהיא מבצעת. עד כמה משמעותי ההבדל במהירויות של שתי המכונות? זו למעשה השאלה "האם הקבוצה P שווה לקבוצה NP". תשובה חיובית לשאלה זו פירושה שההבדל במהירויות אינו משמעותי.
[[תמונה:Complexity classes-he.png]]
▲==סוגים שונים של סיבוכיות==
▲בנוסף ל[[סיבוכיות זמן]] ו[[סיבוכיות מקום]] שהוזכרו קודם, ישנם סוגים נוספים של מדדי סיבוכיות המשמשים בעיקר ל[[הבטחת איכות תוכנה]]. הבולט שבהם הוא [[סיבוכיות קוד]]. '''סיבוכיות קוד''' הוא מדד המאפיין את המורכבות של קוד תוכנה, ולמימושים שונים של אותו [[אלגוריתם]] יכולים להיות ערכי סיבוכיות קוד שונים, למרות שסיבוכיות המקום והזמן תשאר זהה.
==ראו גם==
[[קטגוריה:סיבוכיות|*]]
[[en:Complexity]]
{{Link FA|de}}
[[ar:تعقد]]
[[ca:Pensament complex]]
[[en:Computational complexity theory]]
[[cs:Komplexita]]
[[ar:نظرية التعقيد الحسابي]]
[[de:Komplexität]]
[[bg:Теория на изчислителната сложност]]
[[es:Complejidad]]
[[bn:গণনামূলক জটিলতা তত্ত্ব]]
[[eo:Komplikeco]]
[[ca:Complexitat computacional]]
[[fa: نظریه پیچیدگی محاسباتی]] ▼[[cs:Teorie složitosti]]
[[fr:Complexité]]
[[de:Komplexitätstheorie]]
[[gl:Teoría da complexidade]]
[[el:Θεωρία πολυπλοκότητας]]
[[it: TeoriaEpistemologia della complessità computazionale]] ▼[[es:Teoría de la complejidad computacional]]
[[kk:Күрделілік]]
[[et:Algoritmiline keerukus]]
[[hu:Komplexitás]]
▲[[fa:نظریه پیچیدگی محاسباتی]]
[[nl:Complexiteit]]
[[fi:Aikavaativuusluokka]]
[[fr:Théorie de la complexité des algorithmes]]
[[no:Kompleksitet]]
[[hr:Računska teorija složenosti]]
[[pt:Complexidade computacional]] ▼▲[[it:Teoria della complessità computazionale]]
[[simple:Complexity]]
[[fi:Kompleksisuus]]
[[ko:계산 복잡도 이론]]
[[sv:Komplexitet]]
[[lt:Algoritmų sudėtingumas]]
[[tr:Karmaşıklık]]
[[ms:Teori kekompleksan pengiraan]]
[[zh:复杂]]
[[nl:Computationele complexiteitstheorie]]
[[no:Kompleksitetsteori]]
[[pl:Złożoność obliczeniowa]]
▲[[pt:Complexidade computacional]]
[[ro:Teoria complexității]]
[[ru:Вычислительная сложность]]
[[sh:Računska teorija složenosti]]
[[simple:Computational complexity theory]]
[[sk:Teória zložitosti]]
[[sr:Теорија комплексности]]
[[sv:Komplexitetsteori]]
[[th:ทฤษฎีความซับซ้อนในการคำนวณ]]
[[uk:Теорія складності обчислень]]
[[vi:Lý thuyết độ phức tạp tính toán]]
[[zh:計算複雜性理論]]
| 