probleemklasse

Een probleemklasse (probleemklasse) is een verzamelingscategorie van problemen die gemeenschappelijke kenmerken delen, doorgaans met betrekking tot de aard van de input, de bedoelde uitkomst en de middelen die nodig zijn om een oplossing te vinden of te verifiëren. In de informatica worden probleemklassen vooral gebruikt om problemen te groeperen volgens hun rekenkundige moeilijkheid en de benodigde tijd of ruimte.

In de theoretische informatica wordt een probleemklasse meestal gedefinieerd binnen een formeel model van berekening, bijvoorbeeld deterministische of niet-deterministische Turingmachines, en voor beslissingsproblemen. Een belangrijke manier om problemen aan een klasse toe te wijzen is via reducties: als elk probleem uit de ene klasse in polynomiale tijd kan worden omgezet naar een probleem uit een andere klasse, behoudt men de fundamentele moeilijkheidskenmerken. Hiermee ontstaan ook begrip van volledige problemen: een probleem is bijvoorbeeld NP-volledig als het in NP ligt en elk probleem uit NP in polynomiale tijd naar het probleem kan worden gereduceerd.

Veel voorkomende probleemklassen zijn P (problemen die oplosbaar zijn in polynomiale tijd door een deterministische Turingmachine), NP (problemen waarvoor een oplossing in polynomiale tijd kan worden gecontroleerd), NP-complete (de moeilijkste problemen in NP onder polynomiale reductie), en verder PSPACE, EXP en co-NP. Er zijn ook klassen die gericht zijn op optimalisatie of op verschillende computationele modellen.

Probleemklassen dienen als hulpmiddel bij de analyse, vergelijking en classificatie van problemen. Ze ondersteunen het ontwerp van algoritmen en het nemen van beslissingen over haalbaarheid en efficiëntie in zowel theoretische als toegepaste contexten.