Računski problem

U teoretskom računarstvu, računski problem je matematički objekt koji predstavlja pitanje koje može biti riješeno računalom. Na primjer, "za dan bilo koji broj x, odredi je li x prost broj" je računski problem. Računski su problemi jedni od glavnih predmeta proučavanja u teoretskom računarstvu, jer je gotovo svaki zadatak koji čovjek želi ostvariti primjer računskog problema. U polju algoritama se proučavaju metode rješavanja računskih problema, dok se u komplementarnom polju računske teorije složenosti organiziraju računski problemi na osnovu težine njihova rješavanja.

Problemi i instance

Računski problem enkodira općenit problem, neovisno o svome ulazu. Problem sa specifičnim skupom ulaza se zove instanca. Na primjer, "Za dana dva broj x i y, nađi zbroj x i y" je računski problem. Specifična instanca tog računskog problema bi bila "Koji je zbroj 13 i 28?".

Tipovi računskih problema

Računski su problemi organizirani na mnogo različitih načina. Mogu biti organizirani po načinu definicije, te po količini računskih resursa koje zahtijevaju da izračunaju odgovor. Računski problemi koji intuitivno izgledaju vrlo slično mogu znatno varirati u količini resursa potrebnih za njihovo računanje, i neki su računski problemi neizračunljivi, što znači da nijedan algoritam ne može riješiti svaku njihovu instancu.

Računski problem koji vraća samo da/ne odgovor se zove problem odluke. Primjeri problema odluke uključuju "za dani cijeli broj n, odluči je li n prost broj" i "za dane brojeve x i y, odredi dijeli li x y". Problemi su odluke često korišteni u računskoj teoriji složenosti, jer ih je lakše za proučavati od ostalih problema.

Računski problemi koji nisu ograničeni na da/ne odgovore se zovu funkcijski problemi. Primjeri funkcijskih problema uključuju "za dani cijeli broj n, izlistaj sve proste faktore od n" i "za dane brojeve x i y, ispiši na izlazu x dijeljeno sa y".