Ďalší pokus o vyriešenie P vs NP, zverejnený dôkaz P != NP
Diskusia k článku: Ďalší pokus o vyriešenie P vs NP, zverejnený dôkaz P != NP
Prispievajte do diskusií ako
prihlásený užívateľ.
Komentár, na ktorý odpovedáte:
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
moze mi niekto objasnit?
Od: K-NinetyNine
|
Pridané:
2017-08-17 11:35:37
moze mi niekto objasnit?
"Daným problémom je tzv. problém kliky, zistenie či sa v grafe nachádza skupina aspoň definovaného počtu vrcholov taká, že každý z nich je spojený s každým ostatným z nich."
riesenim takeho problemu, ak tomu dobre rozumiem je "true" ak existuje taka skupina, alebo "false" ak neexistuje. ak tomu rozumiem dobre.
ak je nemozne zistit odpoved v polynomynalnom case, tak ani overit riesenie.
ak by totiz overenie riesenia bolo mozne v polynomynalnom case, tak najdenie riesenia tiez, kedze by stacilo iba v polynomynalnom case overit vysledok true a tiez v polynomynalnom case overit vysledok false.
predpokladam, ze tento problem vznikol nedostatocnym vysvetlenim problemu. tipujem, ze problem nie je zistenie, ci sa nachadza v grafe taka skupina vrcholov, ale najdenie takej skupiny vrcholov. problem nepoznam, citam o nom prvy krat tu na dsl.sk, tak sa pytam pre istotu na objasnenie.
|
neprihlásený 