באמצע האלף הראשון לפנה"ס לערך, חלו התפתחויות חדשות בכתב ההירוגליפי ועניין גדל בכתב. שוב, הכתובות שופעות סימנים חדשים וקבוצות סימנים שלא היו ידועות בתקופה הקלאסית. כל הסימנים החדשים נוצרו על פי העקרונות של התקופה הקלאסית וכתבי הסתרים. ההבדל בין כתב זה של התקופה המאוחרת והכתב המוצפן הוא שכמו בכל שיטת כתב רגילה, התפתחה מסורת קבועה שמטרתה לא להסתיר, כי אם להקל על הקריאה, בעוד שההצפנה חתרה למקוריות.
סיכום השלבים בהתפתחות הכתב ההירוגליפי.
התפתחות הכתב ההירוגליפי הייתה כדלהלן: תחילה הומצאו אך ורק הסימנים שהיו לחלוטין הכרחיים, בלא שתיקבע צורתם האומנותית בקנון. בשלב השני, שיפור קלות הקריאה (כלומר שיפור מהירות הקריאה) הושגה על ידי הגדלת מספר הסימנים (ובכך נמנעו מקרים של ספק) והוספת ה"סימנים הקובעים". לבסוף, לאחר שהשלב השני התמיד ללא שינויים במשך כאלפיים שנה, מספר הסימנים גדל לכמה אלפים בערך בשנת 500 לפנה"ס. תהליך גידול פרוע זה נמשך בעזרת יישום אפשרויות של השיטה שטרם נוצלו. עם ניצחון הנצרות, הידע של הכתב ההירוגליפי נעלם, יחד עם הדת המצרית הקדומה.
כלים.
הכלים בשימוש האמנים לשם כתיבת הסמלים ההירוגליפיים כללו פטישים ואזמלים לשם חקיקת כתובות אבן ומברשות וצבעים עבור עץ ומשטחים חלקים אחרים. רק עבור שיטות הכתב המחובר, ההיראטי והדמוטי פותחו חומרים מיוחדים. עור ופפירוס הפכו משטחים לכתב. ככלי כתיבה שימשו גבעולים של קני סוף באורך 15 עד 33 ס"מ, שנחתכו באלכסון בקצה בו כתבו, והקצה נלעס על מנת להפריד את הסיבים לקצה דמוי מברשת. במאה ה-3 לפנה"ס, היוונים הכניסו למצרים את השימוש בקולמוס מקנה הסוף בעל הקצה המפוצל.
הכתב ההיראטי והכתב הדמוטי.
הכתב המחובר המצרי הקרוי כתב היראטי קיבל את שמו מהמילה היוונית היראטיקוס ("של כוהן") בזמן שהכתב היה בשימוש כתבי קודש בלבד. טקסטים חילוניים לשימוש יומיומי נכתבו בכתב אחר, הכתב הדמוטי (ביוונית "דמוטיקוס" – "עבור העם").
מבנה הכתב ההיראטי מקביל לכתב ההירוגליפי. השינויים שחלו בתווים של הכתב ההיראטי אירעו משום שניתן היה לכתבם מהר יותר עם מברשת או קנה ודיו על פפירוס. ככלל, לא ניתן להכיר או לא ניתן להכיר בקלות את הציור שעליו מתבסס התו. מכיוון שהמודלים עליהם התבססו היו ידועים היטב, ובשימוש קבוע במהלך ההיסטוריה המצרית לא סטו הסמלים ההיראטים רחוק מהם.
כל המסמכים הנפוצים: מכתבים, קטלוגים, וצווים רשמיים נכתבו בכתב ההיראטי, כמו גם טקסטים ספרותיים ודתיים. בחייהם של המצרים שיחק הכתב ההיראטי תפקיד חשוב יותר מאשר הכתב ההירוגליפי וגם נלמד מוקדם יותר בבתי הספר. במשרדים הוחלף הכתב ההיראטי בכתב דמוטי במאה השביעית לפנה"ס, אך נותר הכתב בשימוש כתבי הקודש מסוגים שונים. הטקסטים ההיראטיים האחרונים מקורם בסוף המאה הראשונה - תחילת המאה השנייה לספירה.
הפעם הראשונה שנתקלים בכתב הדמוטי הוא בתחילת השושלת ה-26, בערך בשנת 660 לפנה"ס. סימני הכתב מראים בבירור קשר לכתב ההיראטי, על אף שהיחס המדויק אינו ברור עדיין. התווים בכתב הדמוטי מחוברים יותר ובכך דומים יותר אחד למשנהו וכתוצאה מכך יותר קשים להבנה מהכתב ההיראטי.
משקל נגד לקושי זה הוא שיש לכותב פחות חופש לשינויים אישיים. נראה שהכתב הדמוטי פותח במקור במפורש עבור שימוש ממשלתי, כלומר עבור מסמכים בהם באופן נרחב השפה הייתה רשמית ומותאמת לכן לכתב מחובר תקני.
רק זמן מה לאחר שהוכנס לשימוש לראשונה במסמכים ממשלתיים, החל השימוש בו בטקסטים ספרותיים בנוסף למכתבים ומסמכים.
השיטה של הכתב הדמוטי תאמה לכתב ההיראטי ולכן לכתב ההירוגליפי. עם זאת, במקביל לאיות המסורתי היה גם איות אחר שהתחשב בשינויים הפונטיים הבולטים שחלו במילים על ידי איות מחדש. מאפיין זה יושם במיוחד בקבוצת הרחבה של מילים שלא היו קיימות בשפה הישנה, ולפיכך לא הייתה להם צורה כתובה מסורתית. האיות הבלתי מסורתי היה בשימוש גם עבור מילים וותיקות ומוכרות בשפה הישנה.
פענוח הכתב ההירוגליפי.
למעט פיתגורס, אף יווני לא הכיר את השיטה שמאחורי הכתב ההירוגליפי. היוונים אף לא קיבלו הדרכה מבני דורם המצריים, שחלקם חיו על אדמת איטליה וחרתו כתובות הירוגליפיות תקינות על אובליסקים רומאיים. במקום זאת, במסורת היוונית נקבע שההירוגליפים הם סימנים סמליים או אלגוריות. פלוטינוס, הפילוסוף היווני יליד מצרים פרש את הכתב ההירוגליפי מנקודת מבט של הפילוסופיה האזוטרית שלו.
מתוך כתבי היד היוונים הרבים שנכתבו בעת העתיקה בנושא הכתב ההירוגליפי שרד רק אחד: ה"הירוגליפיקה" של הוראפולון (אנגלית: Hieroglyphica of Horapollon), יווני מצרי שחי כנראה במאה ה-5. הוראפולון עשה שימוש במקורות טובים, אך אין ספק שלא ידע לקרוא בעצמו את הכתב ההירוגליפי, משום שהחל בהשערה המסורתית השגויה של היוונים שההירוגליפים הם סמלים ואלגוריות ולא סימנים פונטיים.
בימי הביניים לא היה ידע כלשהו לגבי הכתב ההירוגליפי ולא ידוע על מחקר בעניינו. אבל כתב היד של הוראפולון שהובא לפירנצה בשנת 1422 עורר עניין גדול בין אנשי הרוח. אומני הרנסאנס תכננו הירוגליפים לפי תיאוריו של הוראפולון ועל פי הדמיון, מבלי להתייחס לאפשרות שכתבי יד מצריים מקוריים עשויים להימצא ברומא. הם השתמשו בהירוגליפים כסמלים עתירי חוכמה באדריכלות וכן בשרטוטים ובציורים.
פענוח הכתב ההירוגליפי התאפשר הודות לגילוייה של אבן רוזטה, לוח גרנודיוריט שחור שנתגלה על ידי חייל בצבא נפוליאון ליד ראשיד (רוזטה) בדלתה של הנילוס ב-15 ביולי 1799.
האבן מכילה טקסט זהה המפאר את המלך תלמי החמישי, והכתוב בשלושה כתבי יד: יווני, הירוגליפי ודמוטי, כלומר בשתי שפות: יוונית ומצרית.
הפענוח החל כאשר הפיזיקאי הבריטי תומאס יאנג הראה כי הן הכתב הדמוטי והן הכתב ההירוגליפי מכילים גם סימנים אלפביתיים וגם סמלים, שיש ביניהם קשר הדוק.
בשנת 1822 הצליח האגיפטולוג הצרפתי ז'אן-פרנסואה שמפוליון, שנעזר בשפה הקופטית, להבין את הערך הפונטי של ההירוגליפים. בכך הוכיח את העובדה שההירוגליפים מייצגים "שפה מדוברת".
P (מחלקת סיבוכיות)
בתורת הסיבוכיות, P היא מחלקת סיבוכיות המכילה את כל בעיות ההכרעה אשר ניתנות לפתרון באופן יעיל, דהיינו בזמן ריצה פולינומי.
ידוע כי P מכילה בעיות נפוצות רבות. למשל, הבעיה של תכנון ליניארי, חישוב מחלק משותף מקסימלי של שני מספרים טבעיים, חישוב עץ פורש מינימלי ומציאת שידוך מקסימום בגרף. בשנת 2002 התגלה כי גם הבעיה של הכרעה האם מספר כלשהו הוא ראשוני שייכת ל-P.
מוטיבציה להגדרה.
הבחירה לזהות את מושג החישוב היעיל עם אלגוריתמים שזמן ריצתם פולינומי אינה שרירותית, ויש לה מספר סיבות שונות.
ראשית, כל אלגוריתם שקורא את כל הקלט שקיבל הוא בעל סיבוכיות זמן ליניארית לכל הפחות (כלומר, זמן ריצתו המינימלי הוא קבוע כפול גודל הקלט). אף שקיימים אלגוריתמים שאינם תלויים בכל הקלט, הם לרוב מבוססים על ביצוע פעולות על מבנה נתונים קיים (למשל, חיפוש בעץ חיפוש) שהיה צורך לקרוא את תוכנו על מנת ליצור אותו מלכתחילה, ולכן עיקר העניין הוא באלגוריתמים שצריכים לקרוא את הקלט כולו.
עם זאת, סיבוכיות זמן ליניארית היא קטנה מדי לרוב השימושים המעשיים. לדוגמה, אלגוריתם מיון לקלט כללי דורש זמן ריצה גדול יותר מזמן ריצה ליניארי, טרם התגלה אלגוריתם כללי לחישוב עץ פורש מינימלי הפועל בזמן ריצה ליניארי, וכדומה. נוסף על כך, זמן ריצה ליניארי יוצר בעיות של רגישות למודל התאורטי שבו משתמשים כדי להעריך את סיבוכיות זמן הריצה: לדוגמה, ישנן בעיות שניתנות להכרעה בזמן ליניארי באמצעות מכונת טיורינג עם מספר סרטים, אבל לא עם מכונת טיורינג בעלת סרט אחד.
הבחירה להרחיב את מחלקת הפונקציות שנחשבות לזמן ריצה יעיל לכל הפונקציות הפולינומיות מקנה יתרונות אחדים:
הגדרה פורמלית.
אחת ההגדרות הפורמליות הנפוצות ל-P משתמשת במושג המתמטי של מכונת טיורינג. אם עבור בעיית הכרעה קיימת מכונת טיורינג דטרמיניסטית שמכריעה את הבעיה (כלומר, עוצרת תמיד ומחזירה תשובה חיובית או שלילית נכונה), נהוג להתעניין גם בזמן הריצה של מכונה זו. צורת המדידה המקובלת לזמן הריצה היא מספר הצעדים שהמכונה מבצעת.
מכיוון שקלטים גדולים יותר גוררים לרוב זמן ריצה ארוך יותר, נהוג לחשב את גודל זמן הריצה ביחס לגודל הקלט. מכיוון שקלט למכונת טיורינג נתון בתור סדרה של סימנים על הסרט, המדד המקובל הוא מספר הסימנים שמופיעים בקלט.
תחת הגדרות אלו, אומרים שבעיה שייכת ל-P אם קיימת מכונת טיורינג דטרמיניסטית המכריעה את הבעיה, וקיים פולינום A כך שזמן הריצה של המכונה על כל קלט אינו גדול מ-A כאשר מציבים בו את גודל הקלט.
בתוך המחלקה P מבחינים בין בעיות להן קיים פתרון יעיל ומעשי, לבין כאלו שסיבוכיותם חסומה על ידי פולינום מדרגה גבוהה מאוד (לדוגמה formula_1).
יחס למחלקות אחרות.
ההכללה המקובלת של P היא המחלקה NP, שמכילה את כל הבעיות שניתנות להכרעה בזמן פולינומי באמצעות מכונת טיורינג לא דטרמיניסטית. (בניסוח שקול, זוהי המחלקה של כל בעיות ההכרעה שניתן לבדוק נכונות של פתרון שמוצע להן בזמן פולינומי). ידוע כי NP מכילה את P, אך לא ידוע אם P=NP, כלומר האם יש הכלה גם בכיוון השני (ובמילים אחרות, האם מכונות טיורינג דטרמיניסטית ולא דטרמיניסטית שוות בכוחן מבחינת זמן ריצה פולינומי). השאלה האם P=NP היא כיום אחת מהבעיות הפתוחות המרכזיות במדעי המחשב.
יעילות אלגוריתמית
במדעי המחשב, יעילות אלגוריתמית מתייחסת לכמות צריכת משאבי מערכת של אלגוריתם, ובפרט משאבי זמן וזיכרון, אך גם משאבי אנרגיה או רוחב פס יכולים להיכלל בבחינת יעילות של אלגוריתם.