Здравствуйте, graniar, Вы писали:

g> ·>Все NP-полные задачи — это задачи одного класса сложности. По определению.
g> Я не про класс. Например: сложность нахождения алгоритма для проверки гамильтонова цикла на графе из N точек окажется эквивалентна сложности проверки гамильтонова цикла на графе из N+k точек.
Ага. И т.к. k — константа, то _класс_ сложности ровно тот же.
O(f(N)) == O(f(N+k))

Здравствуйте, graniar, Вы писали:

g> ·>Все NP-полные задачи — это задачи одного класса сложности. По определению.
g> Я не про класс. Например: сложность нахождения алгоритма для проверки гамильтонова цикла на графе из N точек окажется эквивалентна сложности проверки гамильтонова цикла на графе из N+k точек.
Ага. И т.к. k — константа, то алгоритмическая сложность ровно та же.
O(f(N)) == O(f(N+k))