Positive relativizations of the P = ? NP problem

摘要

Whether or not P is properly included in NP is currently one of the most important open problems in computer science. A deterministic polynomially time-bounded reducibility ⩽rP and its nondeterministic analogue ⩽rNP provide a positive relativization of this problem if P = NP is equivalent to P · r(B) = NP · r(B) for all oracle sets B. Initial attempts to relativize the P = ?NP problem considered reducibilities which are not known to yield positive relativizations. Baker, Gill, and Solovay [1] provided oracle sets B and B′ such that P · T(B) ≠ NP · T(B) and P · T(B′) = NP · T(B'); however, it remains open whether P ⩞ NP or, equivalently, whether the polynomially time-bounded Turing reducibility of Cook (in “Proceedings, 3rd Annual ACM Symposium on Theory of Computing, 1971,” pp. 151–158) provides a positive relativization of the problem. Book, Long, and Selman (SIAM J. Comput.13 (1984), 461–487) found a restricted form of Cook's reducibility that does provide a positive relativization. Several reducibilities between polynomially time-bounded Turing reducibility and polynomially time-bounded many-one reducibility are investigated for their ability to positively relativize the P = ?NP problem.