Improved hardness amplification in NP

檔案

日期

2007-02-12

類型

期刊名稱

THEORETICAL COMPUTER SCIENCE

卷期與頁次

第 370 卷第 1-3 期,頁 293–298

ISSN

0304-3975

語言

英文

摘要

We study the problem of hardness amplification in NP. We prove that if there is a balanced function in NP such that any circuit of size s(n) = 2(Omega(n)) fails to compute it on a 1/poly(n) fraction of inputs, then there is a function in NP such that any circuit of size s(n) fails to compute it on a 1/2 - 1/s'(n) fraction of inputs, with s'(n) = 2(Omega(n2/13)). This improves the result of Healy et al. (STOC'04), which only achievess s' (n) = 2(Omega(n1/2)) for the case with s(n) = 2(Omega(n)). (c) 2006 Elsevier B.V. All rights reserved.

所屬典藏

期刊論文
顯示完整詮釋資料 統計資料

引用此條目

Lu, C.-J., Tsai, S.-C., & Wu, H.-L. (2007). Improved hardness amplification in NP. THEORETICAL COMPUTER SCIENCE, 370(1-3), 293–298. https://doi.org/10.1016/j.tcs.2006.10.009

BibTeX RIS

引用文字依 APA 第 7 版格式自動產生,使用前請再核對。

分享

永久網址:https://ir.lib.nycu.edu.tw/handle/11536/11136