Certificat (complexité)

Exemple

Pour évaluer ${\displaystyle f(x_{1},x_{2})=1}$ aucune évaluation est nécessaire.

À l'opposé ${\displaystyle f(x_{1},x_{2})=x_{1}\wedge x_{2}}$ nécessite d'évaluer toutes ces variables.

Idée du certificat

Pour la fonction ${\displaystyle OR_{n}}$, la fonction ${\displaystyle OR_{n}}$ sur ${\displaystyle n}$ bits. Le fait de dire que ${\displaystyle x_{1}=1}$ cela permet de décider que ${\displaystyle OR_{n}(x)=1}$.

Pour la fonction ${\displaystyle TRIBES_{n}(x)=AND(Or(x_{1},\dots x_{n}),Or(x_{n+1},\dots x_{2n}),\dots ,Or(x_{n(n-1)},\dots x_{n^{2}}))}$. Pour savoir que ${\displaystyle TRIBES_{n}(x)=0}$ il suffit de connaitre un "bloc" où tous les entiers valent 0. Pour savoir que ${\displaystyle TRIBES_{n}(x)=1}$ il suffit de connaitre un 1 pour chaque "bloc".

Assignement partiel

Un assignement partiel est un élément de ${\displaystyle \rho \in \{0,1,*\}^{n}}$. On désigne par ${\displaystyle |\rho |}$ le nombre de 0 et de 1.

Par exemple ${\displaystyle |(0,0,*,*,*,1)|=3}$.

Si le ${\displaystyle i-}$ième élément vaut 0 (resp. 1) alors on va étudier les entrée lorsque ${\displaystyle x_{i}=0}$ (resp. 1). Lorsque cette propriété est toujours vrai, on notera ${\displaystyle \rho \subset x}$

Définition : ${\displaystyle \rho }$ est un 0-certificat si et seulement si pour tous x tels que ${\displaystyle \rho \subset x}$, alors ${\displaystyle f(x)=0}$ . De même on définit la notion de -certificat.

On définis la complexité de certificat : ${\displaystyle C(f,x)=\min \limits _{\rho \subseteq x}\{|\rho |,\rho {\text{ un certificat pour }}f\}}$ et on étend cela pour tous éléments en prenant 'les pires cas' :

${\displaystyle C_{0}(f)=\max \limits _{x\in f^{-1}(0)}C(f,x)\quad et\quad C_{1}(f)\max \limits _{x\in f^{-1}(1)}C(f,x)\quad et\quad C(f)=max\{C_{0}(f),C_{1}(f)\}}$.

Exemple: ${\displaystyle C_{1}(OR_{n})=1}$ car pour tous ${\displaystyle x{\text{ tels que }}OR_{n}(x)=1}$, le certificat qui vaut 1 seulement sur l'un des bit auquel ${\displaystyle x}$ vaut 1.

A l'opposé pour l'entrée ${\displaystyle x=0\dots 0}$, le seul certificat possible est ${\displaystyle \rho =(0,\dots ,0)}$ de taille ${\displaystyle n}$. Ainsi ${\displaystyle C_{0}(OR_{n})=n}$.