b'\n_START_ARTICLE_\nRa\xc4\x8dunski problem\n_START_PARAGRAPH_\nU teoretskom ra\xc4\x8dunarstvu, ra\xc4\x8dunski problem je matemati\xc4\x8dki objekt koji predstavlja pitanje koje mo\xc5\xbee biti rije\xc5\xa1eno ra\xc4\x8dunalom. Na primjer, "za dan bilo koji broj x, odredi je li x prost broj" je ra\xc4\x8dunski problem. Ra\xc4\x8dunski su problemi jedni od glavnih predmeta prou\xc4\x8davanja u teoretskom ra\xc4\x8dunarstvu, budu\xc4\x87i da je gotovo svaki zadatak koji \xc4\x8dovjek \xc5\xbeeli ostvariti primjer ra\xc4\x8dunskog problema. U polju algoritama se prou\xc4\x8davaju metode rje\xc5\xa1avanja ra\xc4\x8dunskih problema, dok se u komplementarnom polju ra\xc4\x8dunske teorije slo\xc5\xbeenosti organiziraju ra\xc4\x8dunski problemi na osnovu te\xc5\xbeine njihova rje\xc5\xa1avanja.\n_START_SECTION_\nProblemi i instance\n_START_PARAGRAPH_\nRa\xc4\x8dunski problem enkodira op\xc4\x87enit problem, neovisno o svome ulazu. Problem sa specifi\xc4\x8dnim skupom ulaza se zove instanca. Na primjer, "Za dana dva broj x i y, na\xc4\x91i zbroj x i y" je ra\xc4\x8dunski problem. Specifi\xc4\x8dna instanca tog ra\xc4\x8dunskog problema bi bila "Koji je zbroj 13 i 28?".\n_START_SECTION_\nTipovi ra\xc4\x8dunskih problema\n_START_PARAGRAPH_\nRa\xc4\x8dunski su problemi organizirani na mnogo razli\xc4\x8ditih na\xc4\x8dina. Mogu biti organizirani po na\xc4\x8dinu definicije, te po koli\xc4\x8dini ra\xc4\x8dunskih resursa koje zahtijevaju da izra\xc4\x8dunaju odgovor. Ra\xc4\x8dunski problemi koji intuitivno izgledaju vrlo sli\xc4\x8dno mogu znatno varirati u koli\xc4\x8dini resursa potrebnih za njihovo ra\xc4\x8dunanje, i neki su ra\xc4\x8dunski problemi neizra\xc4\x8dunljivi, \xc5\xa1to zna\xc4\x8di da nijedan algoritam ne mo\xc5\xbee rije\xc5\xa1iti svaku njihovu instancu._NEWLINE_Ra\xc4\x8dunski problem koji vra\xc4\x87a samo da/ne odgovor se zove problem odluke. Primjeri problema odluke uklju\xc4\x8duju "za dani cijeli broj n, odlu\xc4\x8di je li n prost broj" i "za dane brojeve x i y, odredi dijeli li x y". Problemi su odluke \xc4\x8desto kori\xc5\xa1teni u ra\xc4\x8dunskoj teoriji slo\xc5\xbeenosti, jer ih je lak\xc5\xa1e za prou\xc4\x8davati od ostalih problema._NEWLINE_Ra\xc4\x8dunski problemi koji nisu ograni\xc4\x8deni na da/ne odgovore se zovu funkcijski problemi. Primjeri funkcijskih problema uklju\xc4\x8duju "za dani cijeli broj n, izlistaj sve proste faktore od n" i "za dane brojeve x i y, ispi\xc5\xa1i na izlazu x dijeljeno sa y".'