Нп класс проблем

Question

Все проблемы в NP, как известно, сводятся друг к другу. Я знаю, если проблема X находится в NP, и любая проблема NP Y в NP сводится к X, то X является NP-полной. Таким образом, исходя из этого предположения, мы можем утверждать, что все проблемы NP сводятся друг к другу?

Answer 1

A decision problem C is NP-complete if:

C is in NP, and
Every problem in NP is reducible to C in polynomial time. 

Источник: https://en.wikipedia.org/wiki/NP-completeness

Если все проблемы NP сводимы друг к другу, это будет означать, что все проблемы NP являются NP-полными, что мы не можем сказать, поскольку мы до сих пор не можем доказать, является ли P = NP Обратитесь к изображению ниже для лучшего понимания.

Answer 2

Нет, не все проблемы в NP сводятся друг к другу. То, что есть в NP, отличается от того, что в NP-сложном. Если что-то есть в NP и является NP-сложным, это называется NP-complete. Чтобы быть в NP, проблема должна быть в состоянии быть проверенной за полиномиальное время. NP-сложная проблема - это проблема, которая считается невозможной для эффективного решения по известным алгоритмам. Чтобы быть NP-трудным, проблема должна быть в состоянии быть сведенной к другой проблеме, которая является NP-трудной. Если и X, и Y находятся в NP (как в вашем примере), тогда и Y сводится к X, это не означает, что Y или X являются NP-сложными, поскольку ни одна из них не сводится к существующей NP-сложной проблеме.