Polynomial-time membership comparable sets

• Published in: SIAM journal on computing 1995-10, Vol.24 (5), p.1068-1081
• Main Author: OGIHARA, M
• Format: Article
• Language: English
• Subjects: Applied sciences; Automata. Abstract machines. Turing machines; Computer science; control theory; systems; Exact sciences and technology; Theoretical computing
• ISSN: 0097-5397; 1095-7111
• DOI: 10.1137/S0097539793258131

This paper studies a notion called polynomial-time membership comparable sets. For a function $g$, a set $A$ is polynomial-time $g$-membership comparable if there is a polynomial-time computable function $f$ such that for any $x_{ 1}, \dotsc , x_{m}$ with $m \geq g(\max \{|x_{1}|, \dotsc, |x_{m}|\})$, $f$ outputs $b \in \{0,1\}^{m}$ such that $(A (x_{1}), \dotsc , A (x_{m})) \neq b$. The following is a list of major results proven in the paper: 1. Polynomial-time membership comparable sets construct a proper hierarchy according to the bound on the number of arguments. 2. Polynomial-time membership comparable sets have polynomial-size circuits. 3. For any function $f$ and any constant $c > 0$, if a set is $\leq_{f(n)-tt}^{p}$-reducible to a P-selective set:, then the set is polynomial-time $(1 + c) \log f(n)$-membership comparable. 4. For any $\mathcal{C}$ chosen from $\{ {\text{PSPACE}},{\text{UP}},{\text{FewP}},{\text{NP}},{\text{C}}_ {=} {\text{P}},{\text{PP}},{\text{MOD}}_{2} {\text{P}},{\text{MOD}}_{3} {\text{P}}, \dotsc \} $, if $\mathcal{C} \subseteq {\text{P-mc}}(c \log n)$ for some $c < 1$, then $\mathcal{C} = {\text{P}}$. As a corollary of the last two results, it is shown that if there is some constant $c < 1$ such that all $\mathcal{C}$ are polynomial-time $n^{c}$-truth-table reducible to some P-selective sets, then $\mathcal{C} = P$, which resolves a question that has been leftft open for a long time.