Algebraisk kompleksitet er en gren af beregningsmæssig kompleksitetsteori , der beskæftiger sig med polynomier. Det blev skabt hovedsageligt takket være F. Strassens arbejde [1] [2] [3] .
Den algebraiske kompleksitet af et polynomium , som er betegnet med , er længden af det korteste ikke-forgrenende program, der beregner [4] . Et ikke-forgrenende program er en række funktioner defineret som følger:
, … , …hvor og er polynomier af første grad. Længden af et ikke-forgrenende program er antallet af termer i sekvensen . Et ikke-forgrenende program af længde beregner et polynomium , hvis .
Overvej operationen med at gange en kvadratisk matrix med konstante elementer: med en vektor .
Den additive kompleksitet af en kvadratisk matrix er længden af den korteste sekvens af funktioner , der beregner produktet af en vektor og en tabelrække og er defineret som følger: , ..., , ... hvor , og er konstanter.
Klassen VP er mængden af alle familier af polynomier , for hvilke . For eksempel hører problemet med at beregne determinanten af en matrix til VP-klassen. Beregningskompleksitetsklassen VP er en algebraisk analog til klassen P fra beregningskompleksitetsteorien [6] .
En VNP-klasse inkluderer en familie af polynomier , hvis den har en familie af polynomier fra VP-klassen, således at . Summeringen udføres over alle vektorer af nuller og længdeenheder og er lig med værdien af den -te koordinat af vektoren e. For eksempel hører problemet med at beregne permanenten af en matrix til VNP-klassen. VNP-beregningskompleksitetsklassen er en algebraisk analog til NP-klassen fra beregningsmæssig kompleksitetsteori.