שידוך (תורת הגרפים) – הבדלי גרסאות

בעיית מציאת מספר השידוכים המושלמים ב[[גרף דו צדדי]] היא היא שלמה ל[[Sharp-P]]., בעוד שבעית ההכרעה המקבילה לה - השאלה האם בגרף דו צדדי קיים שידוך מושלם - ניתנת לפתרון יעיל, כלומר ידוע שהיא שייכת ל-[[P| (סיבוכיות))| P]].