Új hozzászólás Aktív témák

• #26 Gabboo tag Stalker-2572 #22

  Új Válasz 2008-04-08 13:38:55 #26

  Új hozzászólás

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  Privát üzenet küldése

  

  Gabboo

  tag

  válasz Stalker-2572 #22 üzenetére

  Uff!

  Eldöntési probléma az, amikor az input egy olyan kérdés, amire az output "igen" vagy "nem".

  Az eldöntési problémák azon osztályát, amelyek az input méretének polinomiális függvényével felülről becsülhető időben megoldhatók, jelöljük P-vel (pl egy gráf összefüggésének eldöntése).

  Ha van egy varázsló, és megmondja, hogy egy G gráfban van Hamilton-kör és meg is mutatja, melyik az, akkor én vizsgán be tudom bizonyítani, hogy G-ben van ilyen. Ez egy NP-beli probléma. Kínaiul: Egy eldöntési probléma akkor NP-beli, ha minden olyan I inputhoz, melyre a válasz "igen", létezik egy olyan, I-től függő T "tanú", hogy egyrészt T hossza felülről becsülhető I hosszának egy polinomjával, másrészt I és T ismeretében polinom időben ellenőrizhető, hogy a válasz igenlő.
  Nemleges válaszra hasonló analógiával létezik a co-Np osztály.

  Egy problémát NP-nehéznek nevezünk, ha minden NP-beli probléma visszavezethető rá. Ha ez a probléma maga is része NP-nek, akkor NP-teljesnek hívjuk. Ha egy NP-teljes problémát meg tudnánk oldani polinom időben, akkor minden NP-beli probléma is megoldható lenne polinom időben.
  Cook és Levin bebizonyították, hogy létezik NP-teljes probléma. Később sikerült belátni, hogy a Hamilton-kör problémája NP-teljes, úgy mint a Klikk-probléma és a pontszínezési probléma.

  Na valami ilyesmiről van szó.
  Bye Gabboo

Új hozzászólás Aktív témák