標題: Improved hardness amplification in NP
作者: Lu, Chi-Jen
Tsai, Shi-Chun
Wu, Hsin-Lung
資訊工程學系
Department of Computer Science
關鍵字: computational complexity;hardness amplification;pseudorandom generator;NP
公開日期: 12-Feb-2007
摘要: 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.
URI: http://dx.doi.org/10.1016/j.tcs.2006.10.009
http://hdl.handle.net/11536/11136
ISSN: 0304-3975
DOI: 10.1016/j.tcs.2006.10.009
期刊: THEORETICAL COMPUTER SCIENCE
Volume: 370
Issue: 1-3
起始頁: 293
結束頁: 298
Appears in Collections:Articles


Files in This Item:

  1. 000244214900020.pdf