NP-teljesség

Magyar

Kiejtés

• IPA: [ ˈmptɛjːɛʃːeːɡ]

Főnév

NP-teljesség

1. (matematika, számításelmélet) Az NP megnevezés a "nondeterministic polynomial (time)" rövidítése. Tétel: Ha létezik polinomiális időben megoldható NP-teljes probléma, akkor P=NP, azaz ha létezik NP-ben polinomiális időben nem megoldható probléma, akkor egyetlen NP-teljes probléma sem polinomiális. Néhány NP-teljes probléma:
   • irányítatlan gráf Hamilton-köre.
   • Boole-hálózat kielégíthetőségi problémája.
   • A 3-SAT probléma.
   • Az irányítatlan gráf klikk-problémája.
   • A minimális lefedő csúcshalmaz probléma.
   • A részletösszeg probléma.
   • Az utazó ügynök probléma.

• angol: NP-completeness (en)
• orosz: NP-полнота (ru) (NP-polnota)