На этом шаге мы рассмотрим классы сложности NPC и NPI.

Напомним утверждение IF NP ≠ P then NP:= P∪NPC∪NPI. В соответствии с ним класс NP не исчерпывается (при условии NP≠Р) простыми полиномиальными задачами и сложными NP-полными задачами. В него входят еще и задачи промежуточной сложности, класс которых обозначен здесь как NPI. Утверждение это доказано как теорема существования, не конструктивно, т.е. без построения задачи класса NPI.

В отличие от класса NPC, в котором находиться очень много известных и практически важных задач, в "промежуточном" классе такие представители неизвестны. Возможно одна из них "задача изоморфизма двух графов".