Geek asks and answers

Double exponential problems?

Are there any serious problems in computer science that can only be solved in double exponential time? And if they exist, then to which class of problems do they belong?

+5
source share
1 answer

From Wikipedia :

In the theory of computational complexity, some algorithms take two-exponential time:

  • Each Presburger arithmetic decision procedure is provably provable with at least two exponential time

  • Calculation of the Gröbner basis over the field. In the worst case, the Gröbner basis can have a number of elements that are twice exponential in the number of variables.

  • -

  • CTL + (, , 2-EXPTIME-complete)

  • (. ).

+8

More articles:


All Articles