сводится к нп трудно

Question

Вики говорит, что когда вы преобразуете проблему NPP в Poly Poly в время A, A - это сложно. см http://en.wikipedia.org/wiki/NP-hard

Но в приведенном ниже pdf-файле сказано, что при преобразовании сложной задачи np в задачу A за полиномиальное время A является сложной задачей np http://compgeom.cs.uiuc.edu/~jeffe/teaching/algorithms/notes/21-nphard.pdf

В кого мне верить?

Answer 1

Оба. NP-complete - это подмножество NP-hard; NP-полные задачи, по определению, NP-сложные. Если вы собираетесь запомнить только одно утверждение, запомните последнее: если задачу в NP-hard можно свести к проблеме A за полиномиальное время, то A также NP-hard.

Что касается стоимости, NP-твердость относится к случаю, когда любая проблема в NP может быть сведена к проблеме за полиномиальное время. NP-полнота относится к случаю, когда проблема находится как в NP, так и в NP-hard.