On polynomial time one-truth-table reducibility to a sparse set

摘要

In this paper, we measure “intractability” of complexity classes by considering polynomial time 1-truth-table reducibility (in short, ≤1−ttP-reducibility) to a sparse set. We mainly investigate nondeterministic complexity classes that are defined in relation to one-way functions: UP, FewP, UBPP, and UP. We show that if UP (resp., UBPP and UP. has a polynomial time unsolvable problem, then it indeed has a problem that is “tractable”ot only by being polynomial time unsolvable, but also by being ≤1−ttP-reducible to no sparse set. As an immediate consequence of our observation, we can also prove that if R ≠ NP (resp., P ≠ FewP and P ≠ UP) then no NP-complete set is ≤ 1−ttP-reducible to a sparse set, and thus no NP-complete set has a p-close approximation; this provides a partial answer to a question asked by Schöning.