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

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 的前提下存在。本計 畫將針對此問題的不可逼近性作深入研究。

This project aims to study the issues related to inapproximability, such as probabilistic checkable proof (PCP) systems, locally testable codes, construction methods and operators of expander graphs and the inapproximability of lattice problems. There does not exist a general method to prove the inapproximability of combinatorial optimization problems until 1990』s. The PCP theorem gave a reduction from an NP-hard problem to a probabilistic checkable proof system that uses O(logn) random bits and constant query complexity. Following the PCP theorem, the MAX 3SAT problem is proved to be inapproximable within some constant factor. Moreover, many inapproximable results of combinatorial optimization problems are proved by reduction from the inapproximability of MAX 3SAT. However, the original proof of PCP theorem is hard and complex. We plan to provide a much more simpler proof for the PCP theorem. Locally testable codes are used as an important tool in the proof of PCP theorem. The improvement of locally testable codes often implies an improvement of corresponding PCP system. Besides the theoretical use in PCP theorem, locally testable codes are also useful in communication area such as designing an ultra efficient error detection codes. We plan to develop new locally testable codes to improve their performance in communication area and we also plan to find the limits and properties of locally testable codes. Recently, many breakthroughs and important results in inapproximability are based on the applications of expander graphs. By derandomizing with well-constructed expander graphs and operators with appropriate properties, we can often improve the randomized analysis result. This project aims the inapproximability field, therefore we need to study expander graphs. We plan to develop new construction methods and operators for improve the inapproximable result. Lattice problems was proposed in 1980, and after more than 20 years, the best approximation factor is still superpolynomial. Micciancio and Regev showed that if SVP is inapproximable within nlogO(1)n factor then one-way function exists unless P=NP. The existence of one-way function is the most desirable result in cryptography field. We plan to focus on improving the inapproximability of lattice problems.