tractabiliteit

Tractabiliteit is de mate waarin een probleem, model of systeem op een beheersbare manier kan worden geanalyseerd of opgelost binnen redelijke rekentijd en middelen. In wiskunde en informatica verwijst tractabiliteit vaak naar de snelheid waarmee een algoritme een oplossing oplevert.

In de context van computatieproblemen wordt vaak gesproken over polynomial-time solvability. Een probleem is tractabel als er een algoritme bestaat dat het probleem kan oplossen in tijd die polynomial is in de invoergrootte n; dit komt overeen met de klasse P. Problemen waarvoor geen efficiënte algoritme bekend is en die als moeilijk worden beschouwd bij grote invoer, worden aangeduid als intractabel; veel NP-hard en NP-complete problemen vallen hieronder. Er bestaan echter tractabele uitzonderingen in speciale gevallen of onder bepaalde aannames. Ook is er het concept van fixed-parameter tractability (FPT): een probleem kan, afhankelijk van een parameter k, in tijd F(k)·n^c opgelost worden, waardoor het tractabel kan zijn als k klein blijft.

In de praktijk draait tractabiliteit vaak om afwegingen tussen rekentijd en nauwkeurigheid. Men kan kiezen voor vereenvoudigde modellen, heuristische methoden of benaderingsalgoritmen die in redelijke tijd bruikbare oplossingen leveren, hoewel niet altijd optimaal. Modellering kan ook de tractabiliteit beïnvloeden: verfijnde, maar complexere representaties kunnen onhandelbaar worden, terwijl vereenvoudigde representaties wél tractabel zijn.

Tractabiliteit speelt een centrale rol in diverse vakgebieden zoals operations research (planning en logistiek), database- en informatiewetenschap, kunstmatige intelligentie en economische modellering. Het begrip helpt bij het inschatten van de haalbaarheid van oplossingen en bij het ontwerpen van efficiënte algoritmen en systemen. Het is een dynamisch onderzoeksgebied waarin men voortdurend zoekt naar tractabele subklassen, betere heuristieken en praktische benaderingen.