Teorya ng komputasyonal na komplehidad

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 problema ay nauunawaang isang gawain na sa prinsipyo na bukas na malulutas ng isang kompyuter (na simpleng ang problema ay maaaring isaad ng isang pangkat 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 likas 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.

Ang lathalaing ito na tungkol sa Kompyuter at Matematika ay isang usbong. Makatutulong ka sa Wikipedia sa pagpapalawig nito.