Révision 162 CSL17/preliminaries.tex

preliminaries.tex (revision 162)
14 14 

  		





  15
  15
  
    
The class $\pip{i}$ is defined similarly but with first quantifier $\forall$ instead of $\exists$. 


  		





  16
  16
  
    
\end{definition}


  		





  17
  
  
    
In particular: $\sigp{0}=\pip{0}=\ptime$, $\sigp{1}=\np$, $\pip{1}=\conp$.


  		





  
  17
  
    
In particular: $\sigp{0}=\pip{0}=\ptime$, $\sigp{1}=\np$, $\pip{1}=\conp$. Note that for any $i$ we have $\pip{i}=\mathbf{co}\sigp{i}$ and $\sigp{i}\subseteq \pip{i+1}$,  $\pip{i}\subseteq \sigp{i+1}$.


  		





  18
  18
  
    

  		





  19
  19
  
    
The polynomial hierarchy is defined as $\ph:=\cup_i \sigp{i}$, and we also have $\ph=\cup_i \pip{i}$.


  		





  20
  20
  
    

  		





  ......




  23
  23
  
    

  		





  24
  24
  
    
We now define the following function classes:


  		





  25
  25
  
    
\begin{eqnarray*}


  		





  26
  
  
    
 \fphi{i+1} &= & \fptime(\sigp{i}),\\


  		





  27
  
  
    
 \fph &=& \cup_i  \fphi{i}. 


  		





  
  26
  
    
 \fphi{i+1} &:= & \fptime(\sigp{i}),\\


  		





  
  27
  
    
 \fph &:=& \cup_i  \fphi{i}. 


  		





  28
  28
  
    
\end{eqnarray*}


  		





  29
  29
  
    
One can then check that $ \fphi{i+1} =  \fptime(\pip{i})=  \fptime(\sigp{i}\cup \pip{i})$.


  		





  30
  30
  
    

  		












Formats disponibles :
  Unified diff