התייחסו לקטע הבא ואז ענו על השאלה שאחריו באותה שפה כמו הקטע:  מעבר: לאדנר הראה שאם P ≠ NP אז יש בעיות ב-NP שאינן ב-P או NP-שלמות. בעיות כאלה נקראות בעיות NP ביניים. בעיית איזומורפיזם של גרף, בעיית הלוגריתם הדיסקרטי ובעיית הפקטוריזציה של מספרים שלמים הן דוגמאות לבעיות הנחשבות להיות NP-ביניים. הם חלק מבעיות ה-NP המעטות ביותר שלא ידוע שהן ב-P או שהן NP-שלמות.  שאלה: איך קוראים לבעיות האלה?
בעיות NP ביניים