ON POLYNOMIAL-TIME BOUNDED TRUTH-TABLE REDUCIBILITY OF NP SETS TO SPARSE SETS

被引：69

作者：

OGIWARA, M ^{[1
]}

WATANABE, O ^{[1
]}

机构：

[1] TOKYO INST TECHNOL,DEPT COMP SCI,TOKYO 152,JAPAN

来源：

SIAM JOURNAL ON COMPUTING | 1991年 / 20卷 / 03期

关键词：

BOUNDED TRUTH-TABLE REDUCTION; BERMAN-HARTMANIS CONJECTURE; SPARSE SETS; POLYNOMIAL-TIME HARD SETS; CRYPTOGRAPHY;

D O I：

10.1137/0220030

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

It is proved that if P not-equal NP, then there exists a set in NP that is not polynomial-time bounded truth-table reducible (in short, less-than-or-equal-to btt(P)-reducible) to any sparse set. In other words, it is proved that no sparse less-than-or-equal-to btt(P)-hard set exists for NP unless P = NP. By using the technique proving this result, the intractability of several number-theoretic decision problems, i.e., decision problems defined naturally from number-theoretic problems is investigated. It is shown that for these number-theoretic decision problems, if it is not in P, then it is not less-than-or-equal-to btt(P)-reducible to any sparse set.

引用

页码：471 / 483

页数：13

共 18 条

[1]

BALCAZAR JL, 1988, EATCS MONOGR THEORET, V11

[2]

Berman L., 1977, SIAM Journal on Computing, V6, P305, DOI 10.1137/0206023

[3] ON SETS TRUTH-TABLE REDUCIBLE TO SPARSE SETS [J].