תורת החישוביות/סיבוכיות קולמוגורוב: הבדלים בין גרסאות בדף

 

כאנלוג למושג האינפורמציה ההדדית בתורת האינפורמציה, אפשר להגדיר את האינפורמציה בין שתי מחרוזות כ:

כמו במושג המקורי, גם כאן אין סימטריה (יש הבדל בין <math>I(x;y)</math> לבין <math>I(y;x)</math>). עם זאת, המשפט כאן מראה כי ההבדל בין שני הגדלים הוא לכל היותר לוגריתמי באורך המחרוזות, ולכן יש סימטריות מסויימת.

}}