Back نظرية التعقيد الحسابي Arabic Teoría de la complexidá computacional AST Hesablama mürəkkəbliyi nəzəriyyəsi Azerbaijani Теория на изчислителната сложност Bulgarian পরিগণনামূলক জটিলতা তত্ত্ব Bengali/Bangla Teoria de la complexitat computacional Catalan Teorie složitosti Czech Komplexitätstheorie German Θεωρία πολυπλοκότητας Greek Computational complexity theory English
| Principes |
| Computationele complexiteitstheorie |
| Modellen |
| Algoritme |
| Turingmachine |
| Lambdacalculus |
| Theorieën |
| Berekenbaarheid |
| Complexiteitsgraad |
| NP-volledig |
Computationele complexiteitstheorie is een tak van theoretische informatica en wiskunde die als doel heeft computationele problemen te classificeren in een aantal categorieën die de inherente moeilijkheidsgraad van deze problemen aangeven. Een computationeel probleem is een probleem dat door een computer kan worden opgelost. Een voorbeeld van een probleem dat computationeel is, is de vraag of een getal wel of niet priem is. Dit kan worden bepaald door middel van een priemgetaltest. Een probleem wordt gezien als inherent moeilijk, als het voor alle denkbare algoritmes veel tijd of geheugen in beslag neemt. Computationele complexiteitstheorie beschrijft dus de praktische limieten van computers.