本研究の目的は，フィルタリングルール中のルール $r_{i}$ の位置で評価が決まるパケットの数を求める問題 (Packet Evaluation problem, PE)が，#P-Complete であることを示すことである．ここで，外部ネットワークから到着するパケットの頻度分布 $F$ の下でのルール $r_{i}$ の位置によって評価が決まるパケットの数を，$r_{i}$ の評価パケット数と呼び，$\|E(\mathcal{R}, i)\|_F$ と表す．
初めは田中研で研究されてきた「フィルタリングルール最適化問題」がNP困難であることを示す，ことを目的として研究を始めた．しかし，「フィルタリングルール最適化問題」を考える為には各ルールの評価パケット数を求める必要があり，評価パケット数を求める問題も相当難しいのでは，という疑問から本研究が始まった．
「評価パケット数」について説明する．
本研究室では，パケットを $0,1$ のビット列で表し，フィルタリングルールを $0, 1, *$ のビット列と評価型$=\{P, D\}$の組（ビット列，評価型）で表す．但し，$*$ は don't care を意味し，$P$ は Permit を $D$ は Deny を意味する．以下にルールリストの例を示す．
| Source Adress | Destination Adress | |
|---|---|---|
| $r_{1}^{D}$ | $0$ $0$ $0$ $0$ | $0$ $0$ $0$ $1$ |
| $r_{2}^{D}$ | $1$ $1$ $*$ $0$ | $1$ $1$ $1$ $0$ |
| $r_{3}^{P}$ | $0$ $0$ $0$ $*$ | $0$ $0$ $0$ $0$ |
| $r_{4}^{P}$ | $1$ $0$ $*$ $*$ | $1$ $1$ $*$ $*$ |
| $r_{5}^{D}$ | $*$ $*$ $0$ $0$ | $1$ $0$ $*$ $1$ |
| $r_{6}^{P}$ | $*$ $1$ $0$ $*$ | $1$ $*$ $*$ $*$ |
| $r_{7}^{D}$ | $0$ $*$ $1$ $*$ | $0$ $*$ $1$ $*$ |
| $r_{8}^{P}$ | $0$ $*$ $*$ $1$ | $0$ $*$ $1$ $*$ |
| $r_{9}^{D}$ | $0$ $*$ $1$ $*$ | $*$ $*$ $*$ $1$ |
| $r_{10}^{D}$ | $*$ $*$ $*$ $*$ | $*$ $*$ $*$ $*$ |
入力パケットは，ルールリストの上位のルール($r_{1}$)から順番に一つずつ比較される．
以下にパケットを分類する例を示す．例に用いるパケットを $0110$ $1001$ とする．
パケット $0110$ $1001$ をルールリストの $r_{1}$ から順番に比較すると，$r_{1} \sim r_{8}$ には合致せず，$r_{9}$ で初めて合致するので，パケット $0110$ $1001$ に $r_{9}$ の評価型 $D$ を与える．つまり，パケット $0110$ $1001$ を破棄する．
下記に，ルール $r_{i}$ との比較により評価が決まるパケットの数 $\|r_{i}(F, {\mathbf R})\|$ を $r_{i}$ の Number of Evaluating Packet の項目に加えたルールリストを示す．但し，到着するパケットの頻度分布は一様とする（$00000000, 00000001, \sim , 11111111$ の計 $256$ パケットがフィルタに通される．）
| Source Adress | Destination Adress | Number of Evaluating Packet | |
|---|---|---|---|
| $r_{1}^{D}$ | $0$ $0$ $0$ $0$ | $0$ $0$ $0$ $1$ | $1$ |
| $r_{2}^{D}$ | $1$ $1$ $*$ $0$ | $1$ $1$ $1$ $0$ | $2$ |
| $r_{3}^{P}$ | $0$ $0$ $0$ $*$ | $0$ $0$ $0$ $0$ | $2$ |
| $r_{4}^{P}$ | $1$ $0$ $*$ $*$ | $1$ $1$ $*$ $*$ | $16$ |
| $r_{5}^{D}$ | $*$ $*$ $0$ $0$ | $1$ $0$ $*$ $1$ | $8$ |
| $r_{6}^{P}$ | $*$ $1$ $0$ $*$ | $1$ $*$ $*$ $*$ | $27$ |
| $r_{7}^{D}$ | $0$ $*$ $1$ $*$ | $0$ $*$ $1$ $*$ | $16$ |
| $r_{8}^{D}$ | $0$ $*$ $*$ $1$ | $0$ $*$ $1$ $*$ | $8$ |
| $r_{9}^{P}$ | $0$ $*$ $1$ $*$ | $*$ $*$ $*$ $1$ | $24$ |
| $r_{10}^{D}$ | $*$ $*$ $*$ $*$ | $*$ $*$ $*$ $*$ | $152$ |