隨機驗證系統、不可逼近性與擴張圖之研究

Abstract

本計畫為期三年，主要的目的於研究不可逼近性領域的相關議題，如隨機可驗證系統 (Probabilistic checkable proof systems，簡稱PCP 系統)，區域可測試編碼(Locally testable codes， 擴張圖(Expander graphs)，以及晶格問題(Lattice problems)之不可逼近性。 在1990 年之前，不可逼近性的議題上始終找不到自NP-hard 問題至組合最佳化問題一般 性的直接化簡(Reduction)。直到隨機可驗證系統的計算模型被提出之後，隨著PCP 定理即 NP=PCP[O(logn),O(1)]的證明，Max 3SAT 的不可逼近性隨之獲得證明，使得許多組合最佳化 的不可逼近性獲得了證明。但PCP 定理的原始證明相當的繁複冗長，本計畫將著手研究簡潔 的PCP 定理證明。 隨機可驗證系統的證明過程中使用了區域可測試編碼作為證明的工具，而區域可測試編 碼除了在於隨機可驗證系統的證明中扮演了重要的角色之外，在通訊領域方面也有許多的應 用。本計畫隨著研究隨機可驗證系統的研究，亦同時開發新的以及改良既有的區域可測試編 碼供通訊上實務的應用，並進一步瞭解其性質。 而近來許多不可逼近性的相關研究上重要結果與突破均使用了擴張圖作為證明工具。藉 由良好擴張圖的設計與運算，使用去隨機化的手法往往能夠立即改進現有使用隨機分析的結 果。本計畫主要研究題為不可逼近性，故需要先對擴張圖此一工具作相關研究，以應用在證 明實務上。 晶格問題自1980 年被提出至今二十餘年來最佳的逼近演算法仍無法逼近到最佳解的多項 式倍，而學者已經證明如晶格中最短向量問題(Shortest Vector Problem)若不可逼近至 nlogO(1)n，則密碼學中的重要元素單向函數(One-way function)能在P≠NP 的前提下存在。本計 畫將針對此問題的不可逼近性作深入研究。