In dit artikel betoogt Niklas Gruhn dat de wijdverspreide angst voor NP-harde problemen onterecht is. Hoewel de theoretische worst-case scenario's suggereren dat deze problemen onoplosbaar zijn, blijkt in de praktijk dat ze voor het overgrote deel van de inputs efficiënt kunnen worden afgehandeld.
De auteur noemt verschillende voorbeelden van NP-harde problemen die inmiddels routinematig worden opgelost, zoals:
- Afhankelijkheidsresolutie en typecontrole in software.
- Planning en het handelsreizigersprobleem, waarvoor bewijsbaar optimale oplossingen mogelijk zijn zonder kwantumcomputers.
- SAT- en SMT-problemen, die op enorme schaal worden toegepast door bedrijven als Amazon.
Gruhn benadrukt dat de algoritmische versnelling tussen 1991 en 2015 veel groter was dan de winst vanuit hardware. Voor de zeldzame gevallen waarin een berekening toch explodeert, stelt hij voor om pragmatisch om te gaan met timeouts.
NP is overschat
Als je op de universiteit over NP-harde problemen hebt geleerd, was je belangrijkste les waarschijnlijk dit: NP-harde problemen zijn in theorie oplosbaar, maar in de praktijk hopeloos duur. Er is in feite bewezen dat er geen goede algoritmen bestaan.
In ieder geval is dat wat ik ervan heb onthouden. Dat geldt voor bijna iedereen met wie ik heb gesproken en voor veel mensen online. Ik zie voortdurend discussies in de trant van: "Nee, dat kun je niet doen. Het is NP-hard. Bla bla."
Deze mythe is wijdverspreid, maar deze problemen zijn niet onbeheersbaar.
Ten tijde van mijn studie sloot mijn professor het laatste college af met dramatische woorden (ik parafraseer enigszins):
"En nu hebben jullie geleerd dat bijna alle interessante problemen onbeslisbaar zijn, en van de overgebleven problemen zijn er bijna allemaal NP-hard. Voor de informatica is dat de genadeklap."
Jeetje. Ik weet niet of iedereen zo'n somber kader kreeg, maar dat zou het verklaren. De theorie is niet onjuist, maar in de praktijk is die vaak irrelevant. Zeker, elk algoritme dat je bedenkt zal bij sommige inputs exploderen. Maar je krijgt misschien een snelle oplossing voor 99,9% van de inputs. Of voor 100% van de relevantmente inputs. De theorie sluit dat niet uit.
“In theorie is er geen verschil tussen theorie en praktijk. Maar in de praktijk is er wel.” — Benjamin Brewster
Prominente NP-harde problemen
Enkele prominente NP-harde problemen zijn:
- Afhankelijkheidsresolutie (bijvoorbeeld in pakketbeheerders)
- Typecontrole (niet voor alle typesystemen)
- Planning (scheduling)
- Het handelsreizigersprobleem (Traveling Salesman)
- Booleaanse vervulbaarheid (SAT)
Voor de eerste twee punten komt het ergste scenario (worst-case) simpelweg niet voor. Ik bedoel, het installeren van pakketten en typecontrole kan zeker traag zijn, maar in mijn loopbaan heb ik nog nooit een "galactische explosie" gezien.
De punten over planning en het handelsreizigersprobleem zijn technisch gezien optimalisatieproblemen. Iedereen weet dat je die met heuristieken kunt aanpakken, maar je hoeft niet per se in te leveren op optimaliteit. We hebben absoluut tools die in redelijke tijd bewijsbaar optimale oplossingen kunnen vinden. Er is geen magie bij betrokken en er zijn geen kwantumcomputers nodig; het is simpelweg een kwestie van harder nadenken en betere algoritmen bedenken.
Dat is precies wat mensen hebben gedaan. Sterker nog, de algoritmische versnelling is de afgelopen decennia sneller gegaan dan de winst in hardware. In combinatie citeert een specifiek paper een versnelling van 450 miljard keer tussen 1991 en 2015.
Tot slot wordt zelfs SAT, het archetype van NP-harde problemen, routinematig op grote schaal opgelost. Amazon lost dagelijks een miljard SMT-problemen op. SMT is een nog moeilijkere versie van SAT. De SAT-algoritmen zijn inmiddels zo goed geworden dat dit nu als het makkelijke deel wordt beschouwd.
Wat als je toch in het ergste scenario terechtkomt?
Je hoeft dan niet te wachten tot de hitte-dood van het universum. Een HTTP-verzoek komt soms ook niet terug. Voeg een timeout toe, toon een foutmelding... je kent het spel.
NP is overschat
Als je op de universiteit over NP-harde problemen hebt geleerd, was je belangrijkste les waarschijnlijk dit: NP-harde problemen zijn in theorie oplosbaar, maar in de praktijk hopeloos duur. Er is in feite bewezen dat er geen goede algoritmen bestaan.
In ieder geval is dat wat ik ervan heb onthouden. Dat geldt voor bijna iedereen met wie ik heb gesproken en voor veel mensen online. Ik zie voortdurend discussies in de trant van: "Nee, dat kun je niet doen. Het is NP-hard. Bla bla."
Deze mythe is wijdverspreid, maar deze problemen zijn niet onbeheersbaar.
Ten tijde van mijn studie sloot mijn professor het laatste college af met dramatische woorden (ik parafraseer enigszins):
"En nu hebben jullie geleerd dat bijna alle interessante problemen onbeslisbaar zijn, en van de overgebleven problemen zijn er bijna allemaal NP-hard. Voor de informatica is dat de genadeklap."
Jeetje. Ik weet niet of iedereen zo'n somber kader kreeg, maar dat zou het verklaren. De theorie is niet onjuist, maar in de praktijk is die vaak irrelevant. Zeker, elk algoritme dat je bedenkt zal bij sommige inputs exploderen. Maar je krijgt misschien een snelle oplossing voor 99,9% van de inputs. Of voor 100% van de relevantmente inputs. De theorie sluit dat niet uit.
“In theorie is er geen verschil tussen theorie en praktijk. Maar in de praktijk is er wel.” — Benjamin Brewster
Prominente NP-harde problemen
Enkele prominente NP-harde problemen zijn:
- Afhankelijkheidsresolutie (bijvoorbeeld in pakketbeheerders)
- Typecontrole (niet voor alle typesystemen)
- Planning (scheduling)
- Het handelsreizigersprobleem (Traveling Salesman)
- Booleaanse vervulbaarheid (SAT)
Voor de eerste twee punten komt het ergste scenario (worst-case) simpelweg niet voor. Ik bedoel, het installeren van pakketten en typecontrole kan zeker traag zijn, maar in mijn loopbaan heb ik nog nooit een "galactische explosie" gezien.
De punten over planning en het handelsreizigersprobleem zijn technisch gezien optimalisatieproblemen. Iedereen weet dat je die met heuristieken kunt aanpakken, maar je hoeft niet per se in te leveren op optimaliteit. We hebben absoluut tools die in redelijke tijd bewijsbaar optimale oplossingen kunnen vinden. Er is geen magie bij betrokken en er zijn geen kwantumcomputers nodig; het is simpelweg een kwestie van harder nadenken en betere algoritmen bedenken.
Dat is precies wat mensen hebben gedaan. Sterker nog, de algoritmische versnelling is de afgelopen decennia sneller gegaan dan de winst in hardware. In combinatie citeert een specifiek paper een versnelling van 450 miljard keer tussen 1991 en 2015.
Tot slot wordt zelfs SAT, het archetype van NP-harde problemen, routinematig op grote schaal opgelost. Amazon lost dagelijks een miljard SMT-problemen op. SMT is een nog moeilijkere versie van SAT. De SAT-algoritmen zijn inmiddels zo goed geworden dat dit nu als het makkelijke deel wordt beschouwd.
Wat als je toch in het ergste scenario terechtkomt?
Je hoeft dan niet te wachten tot de hitte-dood van het universum. Een HTTP-verzoek komt soms ook niet terug. Voeg een timeout toe, toon een foutmelding... je kent het spel.
Groetjes,