Откуда мы знаем, что NP-полные задачи являются самыми сложными в NP?

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

Не могут ли существовать проблемы, которые мы, возможно, не обнаружили или не доказали, существуют в NP, но НЕ МОЖЕТ быть сведена к какой-либо np-полной проблеме?

Ответ нет. По определению NP-полноты одно из двух необходимых условий для того, чтобы задача A была NP-полной, состоит в том, что каждая NP-задача должна быть сведена к A за полиномиальное время. Если вы хотите выяснить, как доказать, что каждая отдельная NP-задача может быть сведена за полиномиальное время к некоторой NP-полной задаче, взгляните на доказательство Теорема Кука-Левина, утверждающая, что задача 3-SAT является NP-полной. Это была первая доказанная NP-полная проблема, и позже было доказано, что многие другие NP-полные задачи являются NP-полными путем нахождения соответствующего сокращения от 3-SAT до этих задач.

NP состоит из всех задач, которые можно (теоретически) решить, если иметь возможность делать удачные предположения, угадывать решение и проверять за полиномиальное время правильность решения. Например, задачу коммивояжера «могу ли я посетить столицы всех 50 штатов США, проехав менее 9 825 миль» можно решить, угадывая поездку и проверяя, не слишком ли она длительна.

И одна проблема в NP заключается в том, чтобы в основном смоделировать программируемую компьютерную схему с различными входами и проверить, может ли быть достигнут определенный выход. И эта программируемая компьютерная схема достаточно мощна, чтобы решить все проблемы в NP.

Так что да, мы знаем все обо всех проблемах в NP.

(Тогда, конечно, NP-полная задача может по определению использоваться для решения любой задачи в NP. Если есть проблема, которую она не может решить, эта проблема не в NP).

Кроме того, как мы узнаем, что обнаружили все проблемы в NP?

Мы не знаем. Множество всех проблем во Вселенной не только бесконечно, но и неисчислимо.

Не могут ли существовать проблемы, которые мы, возможно, не обнаружили или не доказали, существуют в NP, но НЕ МОЖЕТ быть сведена к какой-либо np-полной проблеме?

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

Это одна из самых больших нерешенных проблем в CS. Многие блестящие умы пробовали его, но этот орешек оказалось трудным расколоть.