15. apríla 2021

Problémy tisícročia: je ľahšie Sudoku vyriešiť alebo overiť správnosť riešenia?

Jeden zo šiestich problémov, za ktorých vyriešenie ponúka Clayov matematický inštitút odmenu milión dolárov, je takzvaný P verzus NP problém. Ak zanedbáme niektoré podstatné technikality, jeho zadanie je prekvapivo jednoduché: Úlohou je rozhodnúť, či sa problémy, ktorých riešenie vieme jednoducho overiť, dajú aj jednoducho vyriešiť. Problémy, kde vieme riešenie jednoducho overiť, spadajú do triedy nazývanej NP. Problémy, ktoré vieme jednoducho vyriešiť, patria do triedy P. Otázka teda znie: platí P = NP?