Révision 235 CSL17/soundness.tex

soundness.tex (revision 235)
55 55 
We will use the programs $\charfn{}{}$ in the witness functions we define below.
56 56 
Let us write $\charfn{}{i}$ to denote the class of functions $\charfn{}{A}$ for $A \in \Pi^\safe_{i-1}$.
57 57 
For the notion of bounding polynomial below we are a little informal with bounds, using `big-oh' notation, since it will suffice just to be `sufficiently large'.
58 
Notice that, while we write $p(l)$ below, we really mean a polynomial in the \emph{length} of $l$, as a slight abuse of notation.
58 
Notice that, while we refer to $b_A(l), p(l)$ etc.\ below as a `polynomial', we really mean a \emph{quasipolynomial} (which may also contain $\smsh$), i.e.\ a polynomial in the \emph{length} of $l$, as a slight abuse of notation.
59 59 

  		





  60
  60
  
    

  		





  61
  61
  
    
\begin{definition}


  		





  ......




  138
  138
  
    
	\[


  		





  139
  139
  
    
%	\vec a^\nu = \vec u ,


  		





  140
  140
  
    
%	\vec b^\sigma = \vec u, 


  		





  141
  
  
    
	\bigwedge\limits_{A \in \Gamma} \wit{\vec u ; \vec x}{ A} (l, \vec u ; \vec x , w_A) =1


  		





  142
  
  
    
	\ \implies \


  		





  143
  
  
    
	\bigvee\limits_{B\in \Delta} \wit{\vec u ; \vec x}{B} (l, \vec u ; \vec x , f^\pi_B((\vec u ; \vec x )\mode l, \vec w \mode p(l))) = 1


  		





  
  141
  
    
%	\bigwedge\limits_{A \in \Gamma} \wit{\vec u ; \vec x}{ A} (l, \vec u ; \vec x , w_A) =1


  		





  
  142
  
    
%	\ \implies \


  		





  
  143
  
    
%	\bigvee\limits_{B\in \Delta} \wit{\vec u ; \vec x}{B} (l, \vec u ; \vec x , f^\pi_B((\vec u ; \vec x )\mode l, \vec w \mode p(l))) = 1


  		





  
  144
  
    
	\begin{array}{rl}


  		





  
  145
  
    
&	\bigwedge\limits_{A \in \Gamma} \wit{\vec u ; \vec x}{ A} (l, \vec u ; \vec x , w_A \mode b_A(l)) =1 \\


  		





  
  146
  
    
\noalign{\medskip}


  		





  
  147
  
    
\implies & 	\bigvee\limits_{B\in \Delta} \wit{\vec u ; \vec x}{B} (l, \vec u ; \vec x , f^\pi_B((\vec u ; \vec x )\mode l, \vec w \mode p(l))) = 1


  		





  
  148
  
    
	\end{array}


  		





  144
  149
  
    
	\]


  		





  145
  150
  
    
	for some polynomial $p$.


  		





  146
  151
  
    
%	\anupam{Need $\vec w \mode p(l)$ for some $p$.}


  		












Formats disponibles :
  Unified diff