Из каких задач состоит класс NPI (NP-Intermediate)

[veg_nw]

Есть ли задачи точно принадлежащие классу NPI? Например факторизация числа или сумма делителей принадлежат ли эти задачи к классу NPI?

[Xaositect]

Неизвестно, верно ли $\mathbf{P} \neq \mathbf{NP}$. Если $\mathbf{P} = \mathbf{NP}$, то NPI, очевидно, пуст. Если $\mathbf{P} \neq \mathbf{NP}$, то пример дается в доказательстве теоремы Ладнера. Факторизация или сумма делителей - это задачи вычисления, а не задачи разпознавания, поэтому для них говорить про NPI бессмысленно.

[veg_nw]

Xaositect в сообщении #913190 писал(а):

. Факторизация или сумма делителей - это задачи вычисления, а не задачи разпознавания, поэтому для них говорить про NPI бессмысленно.

Вопрос в сложности вычислений. Сколько нужно операций чтобы сделать факторизацию. Если имеется алгоритм для которого число операций имеет полиниоминальную зависимость от вычисляемого числа, то задачу можно отнести к P классу. Для факторизации не известного алгоритма полиноминальной сложности.

Я лишь не понимаю следующее.
http://en.wikipedia.org/wiki/NP-intermediate
Задачи перечисленные здесь являются кандидатами по той причине что нет p-алгоритма или есть какой то другой критерий.

[Xaositect]

veg_nw в сообщении #913224 писал(а):

Задачи перечисленные здесь являются кандидатами по той причине что нет p-алгоритма или есть какой то другой критерий.

Нет полиномиального алгоритма и нет доказательства NP-полноты.

[veg_nw]

Xaositect в сообщении #913229 писал(а):

Нет полиномиального алгоритма и нет доказательства NP-полноты.

Ясно, спасибо.