„Algoritmuselmélet - Vizsga, 2013.06.06.” változatai közötti eltérés
| 267. sor: | 267. sor: | ||
A '''P osztály'''ba olyan problémák tartoznak, amelyekre ismert olyan algoritmus, ami a bemenet polinomjával megadott idő alatt lefut. Vagyis ha a bemenet '''n''', akkor az algoritmusra azt mondjuk, hogy nagy_ordó(valami), ahol a valami '''n''' egy polinomja, például n négyzet, n köb, három n négyzet meg négy meg nyolc n köb, és ilyesmik. <br><br> | A '''P osztály'''ba olyan problémák tartoznak, amelyekre ismert olyan algoritmus, ami a bemenet polinomjával megadott idő alatt lefut. Vagyis ha a bemenet '''n''', akkor az algoritmusra azt mondjuk, hogy nagy_ordó(valami), ahol a valami '''n''' egy polinomja, például n négyzet, n köb, három n négyzet meg négy meg nyolc n köb, és ilyesmik. <br><br> | ||
Az '''NP osztály'''ba olyan problémák tartoznak, amelyekre | Az '''NP osztály'''ba olyan problémák tartoznak, amelyekre nem feltétlenül ismert polinom idejű (P-beli) algoritmus, de igen válasz esetén létezik hatékony tanúsítvány. Vagyis, adott egy nagy csomó bemenet és van egy kérdés. P-idő alatt nem tudjuk megmondani a választ, de ha valaki megsúgja hogy a válasz IGEN, akkor P-időben meg tudjuk mondani, hogy ez hülyeség vagy nem hülyeség. Ha azt súgják meg hogy NEM, akkor fogalmunk sincs, P-időben nem tudjuk eldönteni hogy hülyeség-e vagy sem. (''Ha így lenne, vagyis igen és nem válasz esetén is P-időben ellenőrizni tudnánk a válasz helyességét, akkor az egész probléma P-beli lenne, hiszen megsúgjuk saját magunknak hogy NEM és ha helyes akkor NEM egyébként igen. Persze ha az IGEN-ről P-időben kiderül hogy hülyeség attól még lehet hogy IGEN, csak éppen nem az a konkrét ami meg lett súgva, hanem egy másik.'') <br><br> | ||
A '''coNP osztály''' lényegében ugyanaz mint az NP osztály, csak NEM válaszra. Vagyis (jelenleg) nem ismerünk rá P-beli algoritmust, de ha a válasz NEM, akkor P-időben (hatékonyan) ellenőrizni tudjuk, hogy ez-e a jó válasz vagy sem. Szintén, IGEN válasz esetén semmit sem tudunk mondani P-időben, a fenti okok miatt (ami a zárójelben van). <br><br> | A '''coNP osztály''' lényegében ugyanaz mint az NP osztály, csak NEM válaszra. Vagyis (jelenleg) nem ismerünk rá P-beli algoritmust, de ha a válasz NEM, akkor P-időben (hatékonyan) ellenőrizni tudjuk, hogy ez-e a jó válasz vagy sem. Szintén, IGEN válasz esetén semmit sem tudunk mondani P-időben, a fenti okok miatt (ami a zárójelben van). <br><br> | ||