ミニ研究集会（福岡）
文部科学省科研費「新世代の計算限界」の活動の一環として、
各地で「ミニ研究集会」が催されています。本記事では、2005年3月28日に福岡で行われた、
論理関数に関するミニ研究集会について、簡単にご報告したいと思います。
学会の研究会のようなフォーマルな研究集会とは異なり、発表者も聴講者も気
楽にディスカッションしようというのが、ミニ研究集会の基本的な姿勢です。
特に福岡での集会では、発表時間枠などを全く設けずにやりました。また、プ
ログラムを前もって決めるでもなく、その場でボランティアとして発表者を募っ
たり、もしくは出席者からのリクエストで発表者を決めたりと、かなりインフォー
マルに行いました。
本ミニ研究集会は、九州工業大学・宮野英次先生に会場のお世話をして頂き、
福岡市の九州工業大学天神サテライトキャンパスで開かれました。天神は福岡
一番（というか九州一番）の繁華街です。この会場は「イムズ」というビル
（少なくとも筆者が福岡に住んでいた頃は、天神で最もおしゃれなビルでした）
の11階に、福岡市での講習会・研究会用の教室として九州工業大学が借りてお
られるもので、40人ほど収容できる部屋です。発表用機器も揃っており、イン
ターネット接続も快適で、申し分ありませんでした。玄海沖での大規模な地震
が起こった1週間ほど後のことであり、建物の損壊などが激しいのではないか
と心配でしたが、それほど目立った跡はありませんでした。余震がまだ続いて
いる時期でしたが、筆者の滞在中は、体に感じる揺れは一度もありませんでし
た。出席者は12名。若手の研究者と学生さんが中心でした。上で書いたように、
特にプログラムは決めていなかったのですが、全員の方が討論用のネタを用意
して下さっていたようです。残念ながら時間の都合上、下記の5名の方にのみ
お話頂くことになりました。以下、各お話の内容を簡単に紹介することで、本
記事を締めたいと思います。
- 原口和也（京都大学）、決定木のサイズの平均値について (10:30〜12:00)
-
原口氏が現在取り組んでいるテーマが紹介された。n変数論理関数fを表現
する頂点数最小の二分決定木の頂点数を、fのサイズと定義する。n変数関
数全体のサイズの平均値はいくらになるかというのが問題であった。
nlog n下限の議論が原口氏から説明され、
その証明が正しいであろうことが参加者の間で確認されたが、
実際の値は2nであろうというのが大方の予想であった。
また、決定木が定数割合エラーを許して良いという緩和の下で、どの
程度サイズを減らすことができるかについても議論された。
- 玉置卓（京都大学）、3SATに対するアルゴリズムの計算時間の上限 (13:00〜14:30)
-
玉置氏の研究成果の紹介がなされた。3SATに対する確率アルゴリズムの計算時
間の上限は、1999年にSchöing によって発表された1.334nが最良であったが、
それを1.324nへと改良した。そのアイデアは以下の通りである。
Schöingのアルゴリズムで解が多い場合の計算時間を解析し、解の数が多い
ほど高速になることを示した。また、PPSZというアルゴリズムは、逆に解が少
ないほど高速になる。これらを同時に走らせることにより、互いの欠点を補い、
高速化できることを示した。
SATは直感的には解の数が多いほど易しいが、PPSZの計算時間解析はその逆で
ある。この現象は解析の都合によるものが大きいと見られており、実際には
PPSZも解が唯一である場合の計算時間が最悪であろうことが予想できる。この
直感を証明することができれば、上限の大幅な改良が可能となる。
- 森住大樹（京都大学）、回路計算量の下限 (14:30〜16:00)
-
森住氏の研究成果が報告された。ここでは、2入力のAND、ORと、NOTのみを使
用する論理回路を考える。論理回路Cのサイズとは、Cに含まれるAND素子
の数とOR素子の数の和である。論理関数fの回路計算量とは、fを計算する
最小サイズの論理回路のサイズである。これまで具体的な関数での最良の下限
は、LachishとRazによる4.5n-o(n)であったが、それを5n-o(n)へと改良し
た。LachishとRazの下限は、Strongly-two-dependent な関数に対して入力を
削除していく手法を用いていたが、その場合分けを細かく解析することにより、
下限の改良を成功させた。
- 定兼邦彦（九州大学）、Right-hand-on-the-wall walk (16:00〜16:30)
-
定兼先生の研究成果が報告された。与えられたグラフの各頂点v（次数を
d(v)とする）に対して、その接続枝に番号を1からd(v)まで重複なく割り
当てる（枝(u,v)に対して、uから見た番号とvから見た番号は異なって
良い）。このとき、以下の条件を満たす番号割り当てができるかどうかという
問題を考える。（以下では、頂点vから見て番号kが付けられた枝を
vkと書く。）
条件： 枝11から出発し、グラフの枝を辿り、全ての頂点を訪れて
頂点1に戻る。ただし、頂点vに枝vkから入ってきた場合は、枝
vk+1から出ていく。
任意のグラフに対して、この条件を満たす番号割り当てが存在し、その閉路の
長さは高々10nであることが、この研究で明らかにされた。また、閉路長を
4nよりも短くすることができないグラフの存在も示された。このギャップを
埋めることは興味深い未解決問題である。ちなみに、定兼先生の予想は4nで
ある。
- 小野廣隆（九州大学）、無線ネットワークにおける通信電力量に対するオンラインアルゴリズム(16:30〜17:00)
-
小野先生の研究成果の紹介があった。1台のサーバと複数のクライアントが無
線で通信する状況を考える。サーバはn台のクライアントと通信を行いたい
が、クライアントがどの位置にいるかを知らないため、どの程度の電力で発信
すれば良いかが分からない。例えば、多くのクライアントに一度に届くように
大きな電力量で発信すると、多くのクライアントが近くにいた場合の損が大き
い。逆に少しずつ到達エリアを拡大しながら（つまり電力量を大きくしながら）
繰り返し送信すると、遠い場所にクライアントがいる場合に、何度も送信しな
ければならないので損失が大きい。ここでは、送信したいクライアント数に応
じたある割合でエリアを広げながら送るアルゴリズムの競合比3/2+\sqrt{2}
を示し、そのアルゴリズムが最適であることも示した。
- 開催日時：
- 2005年3月28日(月) 10時30分〜17時
- 開催場所：
- 九州工業大学 天神サテライトキャンパス (福岡市中央区天神1丁目7番11号 イムズ11F)
- 参加者：
- 朝廣雄一（九州産業大学）、小野廣隆（九州大学）、
黒田太陽（九州工業大学）、定兼邦彦（九州大学）、玉置卓（京都大学）、
原口和也（京都大学）、堀山貴史（京都大学）、牧野和久（大阪大学）、
宮崎修一（京都大学）、宮野英次（九州工業大学）、森住大樹（京都大学）、
山下雅史（九州大学）
