NP и 3-SAT и один факт

Question

Любой эксперт может помочь мне, почему это предложение верно?

, если L ∈ NP и L ≤ _р 3-SAT (то есть: L снизить до 3-SAT в поли время), то L является NP-полным.

Answer 1

Это утверждение неверно. Так как 3SAT NP-complete, каждый проблема в полиномиальном времени NP сводится к 3SAT, поэтому, если вы выберете любой язык в NP, тогда он будет полиномиально-временным сокращением до 3SAT. В частности, если вы выберете пустой язык ∅, который, как известно, не является NP-полным, то ∅ ∈ NP и ∅ уменьшают пятки 3SAT, но ∅ не является NP-комплектом.

Надеюсь, это поможет!