布尔分层one-way函数的存在性

one-way函数是否存在迄今仍为一个开问题.文献[5]提出了分层one-way函数的概念.本文在布尔线路中讨论了分层one-way函数的存在性并得到结果:(1)给定k≥j>0,若存在j-honest的2k-one-way函数族{f_i},则UPSIZE^(2j)-PSIZE^(k-j)≠?.(2)给定k≥j>0,若UPSIZE^j∩CO-UPSIZE^j-PSIZE^k≠?,则存在j-honest的k-one-way函数族{f_i},且?rang(f_i)=∑~*.(3)给定j>0,j-honest的ω-one-way函数族{f_i}存在当且仅当UPSIZE^(2j)-PSIZE≠?.