計算量の理論-下界の証明・計算量の正確な決定・最適アルゴリズムの一意性の問題

复杂性理论——下界证明、复杂性的精确确定、最优算法的唯一性

• 批准号: 09780257
• 负责人: 垂井 淳
• 金额: $ 1.79万
• 依托单位: The University of Electro-Communications
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Encouragement of Young Scientists (A)
• 财政年份: 1997
• 资助国家: 日本
• 起止时间: 1997 至 1998
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-09780257/
• 关键词: 否定数限定; マージング; DNF; PAC learning; permutation family; permanent; ハイパーキューブ; rearrangeability; 到達可能性判定; 領域計算量; ブール関数; sensitivity

今年度得られた結果のいくつかを以下の簡潔に述べる。1. 否定数限定回路でのmergingのcomplexityをかなり正確に決定することに成功した:2つの長さnのソートされた0,1列をマージするa個のNOT gateとAND,OR gateよりなる最小の回路のサイズは、a【less than or equal】log_2nのときΘ(nlog_2n/2^a)であることを示すことができた。2. DNF式にたいして効率的PAC(Probably Approximately Correct)学習が可能かどうかという問題は、計算論学習理論における最重要な未解決問題のひとつである。この問題についてのあるアプローチの可能性と限界にてついての結果を得た:長さがmのmonomialで、ターゲットであるDNF式との相関があるものを弱学習することとboostingよってDNF式の学習を達成しようとするとき、mがn^<1/2>より小さい場合は、弱学習が不可能であり、n^<1/2>くらいまで大きくとると可能であることを示した。3. Broder他がSTOC98で発表したMIn-wise independent permutation familyについて、その仕事で未解決問題として残されていたもののいくつかにたいしてそのようなfamily sizeにたいして上界・下界を示すことができた。4. m by n rectangular matrix(m【less than or equal】n)のPermanentをO(n2^m+3^m)arithmetic operationsによって計算するアルゴリズムを与えた。

The results of this year's report show that the following information is available. 1. The negative number limit circuit (merging) complexity circuit has correctly determined that the circuit is successful. It is shown that a column of NOT gate AND,OR gate circuits shows a number of errors, a [less than or equal] loop error (nlog_2n/ 2 ^ a), and a [less than or equal] loop error. 2. The PAC (Probably Approximately Correct) method of DNF data acquisition rate may be used to solve the most important unsolved problems. The following results are obtained: long-term monomial, long-term DNF, weak boosting, weak DNF, low-level DNF, low-level DNF, low- 1According to 2GT; it is possible to show that it is not possible. 3. Broder he

项目成果

T.Kawabata and J.Tarui: "On Complexity of Computing the Permanent of a Rectangular Matrix" IEICE Trans actions Fundamentals. volE82-A(to appear). (1999)

T.Kawabata 和 J.Tarui：“计算矩形矩阵常量的复杂性”IEICE 交易基础知识。