Weboldalunk cookie-kat használhat, hogy megjegyezze a belépési adatokat, egyedi beállításokat, továbbá statisztikai célokra és hogy a személyes érdeklődéshez igazítsa hirdetéseit. További információ

Főoldal Belépés/Regisztráció Egy véletlen kérdés Facebook






Kategória: Közoktatás, tanfolyamok » Házifeladat kérdések

A kérdés

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.



Keress kérdéseket hasonló témákban: p probléma, np probléma, számításelmélet, algoritmuselmélet

 2017. jún. 24. 20:59  Privát üzenet  

A válasz
A kérdező kommentje:

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.



# 1/1Időpont 2017. jún. 25. 15:14 Privát üzenet

Értesítsünk róla, ha új válasz érkezik? Válasz küldése



Kapcsolódó kérdések
Mi a töltés és az áram közötti összefüggés?
Hogyan igazolható az egyes égitestek látszólagos helyzete és a földi történések közötti összefüggés?
Rendszám és kor közötti összefüggés kocsiknál?
Érdekelne a bolygók tömege, keringési sebessége és a Naptól való távolsága közötti összefüggés. Ezek következetesen igazak a naprendszer összes bolygójára?
Ovuteszt és hőmérőzés közötti összefüggés, nálatok hogy volt?
Mit szóltok az iwiw és a facebook közötti hasonlósághoz? Van valami összefüggés?

Kérdések a Közoktatás, tanfolyamok rovatbólKérdések a Házifeladat kérdések rovatból








Minden jog fenntartva © 2019, www.gyakorikerdesek.hu | GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | WebMinute Kft. | Kapcsolat: info (kukac) gyakorikerdesek.hu

A weboldalon megjelenő anyagok nem minősülnek szerkesztői tartalomnak, előzetes ellenőrzésen nem esnek át, az üzemeltető véleményét nem tükrözik.
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!