Teoriya ng komputasyonal na kompleksidad

Mula sa Wikipediang Tagalog, ang malayang ensiklopedya
Tumalon sa: nabigasyon, hanapin

Ang teoriya ng komputasyonal na kompleksidad (Ingles: Computational complexity theory) ang sangay ng teoriya ng komputasyon teoretikal na agham pangkompyuter at matematika na pumopokus sa pag-uuri ng mga komputasyonal na proiblema ayon sa kanilang likas na kahirapan at inuugnay ang mga klaseng ito sa bawat isa. Sa kontekstong ito, ang komputasyonal na problem ay nauunawaang isang gawain na sa prinsipyo na bukas na malulutas ng isang kompyuter (na simpleng ang problema ay maaaring isaad ng isang hanay ng mga instruksiyong matematikal). Sa inpormal na paglalarawan, ang isang komputasyonal na problema ay binubo ng mga instansiya ng problema at mga solusyon sa mga problemang instansiyang ito. Halimbawa, ang pagsubok ng primalidad ang problema ng pagtukoy kung ang isang bilang ay bilang na prima (prime number) o hindi. Ang mga instansiya ng problemang ito ang mga natural na bilang at ang solusyon sa isang istansiya ay oo o hindi batay sa kung ang isang bilang ay bilang na prima(prime number) o hindi.