Nonuniform Reductions and NP-Completeness

被引:1
作者
Hitchcock, John M. [1 ]
Shafei, Hadi [2 ]
机构
[1] Univ Wyoming, Dept Comp Sci, Laramie, WY 82071 USA
[2] Northern Michigan Univ, Dept Math & Comp Sci, Marquette, MI 49855 USA
关键词
Computational complexity; NP-completeness; Reducibility; Nonuniform complexity; SETS;
D O I
10.1007/s00224-022-10083-y
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
Nonuniformity is a central concept in computational complexity with powerful connections to circuit complexity and randomness. Nonuniform reductions have been used to study the isomorphism conjecture for NP and completeness for larger complexity classes. We study the power of nonuniform reductions for NP-completeness, obtaining both separations and upper bounds for nonuniform completeness vs uniform complessness in NP. Under various hypotheses, we obtain the following separations: There is a set complete for NP under nonuniform many-one reductions, but not under uniform many-one reductions. This is true even with a single bit of nonuniform advice. There is a set complete for NP under nonuniform many-one reductions with polynomial-size advice, but not under uniform Turing reductions. That is, polynomial nonuniformity cannot be replaced by a polynomial number of queries. For any fixed polynomial (), there is a set complete for NP under uniform 2-truth-table reductions, but not under nonuniform many-one reductions that use () advice. That is, giving a uniform reduction a second query makes it impossible to simulate by a nonuniform reduction with fixed polynomial advice. There is a set complete for NP under nonuniform many-one reductions with polynomial advice, but not under nonuniform many-one reductions with logarithmic advice. This hierarchy theorem also holds for other reducibilities, such as truth-table and Turing. We also consider uniform upper bounds on nonuniform completeness. Hirahara (2015) showed that unconditionally every set that is complete for NP under nonuniform truth-table reductions that use logarithmic advice is also uniformly Turing-complete. We show that under a derandomization hypothesis, every set that is complete for NP under nonuniform truth-table reductions is also uniformly truth-table complete.
引用
收藏
页码:743 / 757
页数:15
相关论文
共 29 条
  • [11] Berman L., 1977, SIAM Journal on Computing, V6, P305, DOI 10.1137/0206023
  • [12] Berman L., 1976, P 17 IEEE S FDN COMP, P76, DOI DOI 10.1109/SFCS.1976.22
  • [13] Buhrman H, 1999, J COMPUT SYST SCI, V59, P327, DOI 10.1006/jess.1999.1650
  • [14] Non-Uniform Reductions
    Buhrman, Harry
    Hescott, Benjamin
    Homer, Steven
    Torenvliet, Leen
    [J]. THEORY OF COMPUTING SYSTEMS, 2010, 47 (02) : 317 - 341
  • [15] Identifying an Honest EXPNP Oracle Among Many
    Hirahara, Shuichi
    [J]. 30TH CONFERENCE ON COMPUTATIONAL COMPLEXITY (CCC 2015), 2015, 33 : 244 - 263
  • [16] Hardness hypotheses, derandomization, and circuit complexity
    Hitchcock, John M.
    Pavan, A.
    [J]. COMPUTATIONAL COMPLEXITY, 2008, 17 (01) : 119 - 146
  • [17] Comparing reductions to NP-complete sets
    Hitchcock, John M.
    Pavan, A.
    [J]. INFORMATION AND COMPUTATION, 2007, 205 (05) : 694 - 706
  • [18] Autoreducibility of NP-Complete Sets under Strong Hypotheses
    Hitchcock, John M.
    Shafei, Hadi
    [J]. COMPUTATIONAL COMPLEXITY, 2018, 27 (01) : 63 - 97
  • [19] WEAK COMPLETENESS IN E AND E(2)
    JUEDES, DW
    LUTZ, JH
    [J]. THEORETICAL COMPUTER SCIENCE, 1995, 143 (01) : 149 - 158
  • [20] Kabanets V., 2000, Proceedings of the Thirty Second Annual ACM Symposium on Theory of Computing, P73, DOI 10.1145/335305.335314