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