איזה מהשאלות הבאות איננה סיווג לבעיות: NP, co-NP, או RSA? בהתחשב בשאלה הקודמת, כתוב את ההקשר שמכיל את התשובה. זה יכול להיות 1 - 20 משפטים. -הקשר:
בעיית הפקטוריזציה של מספר שלם היא בעיית החישוב של קביעת הפקטוריזציה הראשונית של מספר שלם נתון. במונח של בעיית החלטה, זוהי בעיית ההחלטה אם לתשומת הלב יש גורם קטן מ-k. לא ידוע על אלגוריתם יעיל לפקטוריזציה של מספרים שלמים, והעובדה הזו מהווה את הבסיס לכמה מערכות קריפטוגרפיות מודרניות, כגון אלגוריתם RSA. בעיית הפקטוריזציה של מספרים שלמים היא ב-NP וב-co-NP (ואפילו ב-UP וב-co-UP). אם הבעיה היא NP-שלמה, היררכיית הזמן הפולינומי תתמוטט לרמה הראשונה שלה (כלומר, NP יהיה שווה ל-co-NP). האלגוריתם הידוע ביותר לפקטוריזציה של מספרים שלמים הוא מחיטת שדה המספרים הכללית, אשר לוקחת זמן O(e(64/9) 1 / 3 ((n.log 2) 1 / 3 ((log (n.log 2)) 2 / 3) לפקטוריזציה של מספר שלם n-bit. עם זאת, האלגוריתם הקוונטי הידוע ביותר לבעיה זו, אלגוריתם של שור, פועל בזמן פולינומי. למרבה הצער, עובדה זו לא אומרת הרבה על איפה הבעיה שוכנת ביחס לכיתות מורכבות לא קוונטיות.