Mi a P és NP-beli problémák közötti összefüggés?
Pontosabban ezekre keresnék választ:
Melyik igaz és melyik hamis az alábbi állítások közül? Válaszát indokolja meg minél részletesebben!
1; Minden NP-beli probléma P-beli is egyben.
2; Minden P-beli probléma NP-beli is egyben.
3; Minden NP-teljes probléma NP-nehéz is egyben.
4; Minden Np-nehéz probléma NP-teljes is egyben.
Bármely P-beli probléma az NP osztályba is beletartozik, hiszen a P-beli problémákat meg tudjuk oldani polinomiális idoben, még bizonyíték nélkül is. Nyitott kérdés, hogy P valódi részhalmaza-e NP-nek.
Az L ⊆ {0, 1} ∗ nyelv NP-teljes, ha
1. L ∈ NP és
2. Minden L 0 ∈ NP-re L 0 ≤P L. -
Ha egy nyelv rendelkezik a második tulajdonsággal, de az elsovel nem feltétlenül, akkor NP-nehéznek nevezzük. Az NP-teljes nyelvek halmazát NPC-vel jelöljük.
Kapcsolódó kérdések:
Minden jog fenntartva © 2024, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!