Valaki elmagyarázná, hogy mik azok a N, NP és coNP nyelvosztályok?
Figyelt kérdés
Elnézést, nem konkrétan programozás téma, de gondolom a böngészők között van pár aki ért valamennyire számítógéptudomanyhoz is.2019. máj. 30. 22:05
2/3 anonim 
válasza:
válasza:Van egy nemdeterminisztikus Turing-géped, ami eldönt egy nyelvet.
NTIME(f(n)) tartalmazza azokat a nyelveket, amiknek az eldöntéséhez maximum f(n) (vagy ennek a konstans-szorosa az ordó miatt) "idő" kell.
Ha az f(n)-t n^k függvénynek választjuk, és minden 1<=k-ra vesszük az NTIME(n^k)-k unióját, akkor megkapjuk az NP-t.
Azaz ha kiveszel az NP halmazból egy nyelvet, akkor arra létezni fog egy olyan Turing-gép, ami nemdeterminisztikus, és létezik egy polinom, amivel lehet becsülni, hogy mennyi idő alatt végez.
A coNP ha jól tudom olyan elemeket tartalmaz kizárólag, amelyeknek a komplementere NP-ben van.
3/3 anonim 
válasza:
válasza:#2 Kiegészítve, az NP definíciója kettős, egyrészt NP azon elemekből áll, amelyeket egy nemdeterminszitikus Turing-géppel polinomiális időben el lehet dönteni (ez az, amit te írtál), másfelől NP elemeire adott megoldás helyességét polinomiális időben (determinsiztikus módon) ellenőrizni lehet (rendszerint inkább erre a definícióra szoktak hivatkozni). Ez két különböző definíció, de lényegében ekvivalensek.
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
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!
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!