ELEMENTARY

In <a href="/facts/Computational_complexity_theory/etHuVF3U">computational complexity theory</a>, the <a href="/facts/Complexity_class/IIKrcTbP">complexity class</a> 
 
 
 
 
 
 E
 L
 E
 M
 E
 N
 T
 A
 R
 Y
 
 
 
 
 {\displaystyle {\mathsf {ELEMENTARY}}}
 
 consists of the <a href="/facts/Decision_problem/cQNWjbdE">decision problems</a> that can be solved in time bounded by an <a href="/facts/Elementary_recursive_function/gxGLXF4R">elementary recursive function</a>. The most quickly-growing elementary functions are obtained by iterating an exponential function such as 
 
 
 
 
 2
 
 n
 
 
 
 
 {\displaystyle 2^{n}}
 
 for a bounded number 
 
 
 
 k
 
 
 {\displaystyle k}
 
 of iterations,

2
                    
                      
                        
                          2
                          
                            
                              
                                2
                                
                                  
                                    
                                      ⋅
                                      
                                        
                                          
                                            ⋅
                                            
                                              
                                                
                                                  ⋅
                                                  
                                                    
                                                      n
                                                    
                                                  
                                                
                                              
                                            
                                          
                                        
                                      
                                    
                                  
                                
                              
                            
                          
                        
                      
                    
                  
                
              
            
          
          }
        
        k
        .
      
    
    {\displaystyle \left.{\begin{matrix}2^{\scriptstyle 2^{\scriptstyle 2^{\scriptstyle \cdot ^{\scriptstyle \cdot ^{\scriptstyle \cdot ^{\scriptstyle n}}}}}}\end{matrix}}\right\}k.}

Thus, 
 
 
 
 
 
 E
 L
 E
 M
 E
 N
 T
 A
 R
 Y
 
 
 
 
 {\displaystyle {\mathsf {ELEMENTARY}}}
 
 is the union of the classes

E
                    L
                    E
                    M
                    E
                    N
                    T
                    A
                    R
                    Y
                  
                
              
              
                
                =
                
                  ⋃
                  
                    k
                    ∈
                    
                      N
                    
                  
                
                k
                
                  
                    
                      
                        -
                      
                    
                    E
                    X
                    P
                  
                
              
            
            
              
              
                
                =
                
                  
                    D
                    T
                    I
                    M
                    E
                  
                
                
                  (
                  
                    2
                    
                      n
                    
                  
                  )
                
                ∪
                
                  
                    D
                    T
                    I
                    M
                    E
                  
                
                
                  (
                  
                    2
                    
                      
                        2
                        
                          n
                        
                      
                    
                  
                  )
                
                ∪
                
                  
                    D
                    T
                    I
                    M
                    E
                  
                
                
                  (
                  
                    2
                    
                      
                        2
                        
                          
                            2
                            
                              n
                            
                          
                        
                      
                    
                  
                  )
                
                ∪
                ⋯
                .
              
            
          
        
      
    
    {\displaystyle {\begin{aligned}{\mathsf {ELEMENTARY}}&=\bigcup _{k\in \mathbb {N} }k{\mathsf {{\mbox{-}}EXP}}\\&={\mathsf {DTIME}}\left(2^{n}\right)\cup {\mathsf {DTIME}}\left(2^{2^{n}}\right)\cup {\mathsf {DTIME}}\left(2^{2^{2^{n}}}\right)\cup \cdots .\end{aligned}}}

It is sometimes described as iterated exponential time, though this term more commonly refers to time bounded by the <a href="/facts/Tetration/5rKeVVYv">tetration</a> function.

This complexity class can be characterized by a certain class of "iterated stack automata", <a href="/facts/Pushdown_automaton/kEPRC70F">pushdown automata</a> that can store the entire state of a lower-order iterated stack automaton in each cell of their stack. These automata can compute every language in 
 
 
 
 
 
 E
 L
 E
 M
 E
 N
 T
 A
 R
 Y
 
 
 
 
 {\displaystyle {\mathsf {ELEMENTARY}}}
 
, and cannot compute languages beyond this complexity class. The <a href="/facts/Time_hierarchy_theorem/sm75DR1s">time hierarchy theorem</a> implies that 
 
 
 
 
 
 E
 L
 E
 M
 E
 N
 T
 A
 R
 Y
 
 
 
 
 {\displaystyle {\mathsf {ELEMENTARY}}}
 
 has no <a href="/facts/Complete_(complexity)/Ine1b8Qy">complete</a> problems.
Every <a href="/facts/Elementary_recursive_function/gxGLXF4R">elementary recursive function</a> can be computed in a time bound of this form, and therefore every decision problem whose calculation uses only elementary recursive functions belongs to the complexity class 
 
 
 
 
 
 E
 L
 E
 M
 E
 N
 T
 A
 R
 Y
 
 
 
 
 {\displaystyle {\mathsf {ELEMENTARY}}}
 
.

ELEMENTARY open-in-new

ELEMENTARY