Two-sided polynomial-target robustness of WPP and LWPP #
Uniform polynomial-time accepting and rejecting target lists preserve WPP and LWPP when these lists are disjoint at each input, or each natural length for LWPP. Original targets may be zero, negative or repeated; only cross-family disjointness is required. The target indices need not be computable. Binary list output charges both counts and bit lengths.
The proof follows Hemaspaandra et al., Appendix A: take the product of the differences between rejection targets and the original gap. This vanishes on rejection, and on acceptance takes one of a uniformly computed family of nonzero products. The uniform product theorem and one-sided robustness then finish the construction.
The public interfaces ask for Turing.MultiTapeTM.ComputableInPolyTime certificates.
Main results #
mem_WPP_of_disjoint_targets,mem_LWPP_of_disjoint_targets: two-sided robustness.mem_WPP_of_disjoint_indexed_targets,mem_LWPP_of_disjoint_indexed_targets: indexed two-sided robustness.mem_WPP_iff_exists_disjoint_targets,mem_LWPP_iff_exists_disjoint_targets: the full two-sided polynomial-family characterizations.
References #
- [E. Hemaspaandra, L. A. Hemaspaandra, H. Spakowski, O. Watanabe, The Robustness of LWPP and WPP, with an Application to Graph Reconstruction] [HHSW18], Definition 3.8, Corollary 3.11, Theorem 3.12 and Appendix A of the full version (arXiv:1711.01250).
Two-sided WPP robustness for disjoint uniformly computed binary integer target lists. Neither original list is required to avoid zero; no accepting or rejecting index is computed.
Two-sided LWPP robustness with both target lists computed from unary input length. Disjointness is required at every natural length, including zero. Original zero targets are allowed on either side, provided the two lists remain disjoint.
Two-sided WPP robustness for uniform indexed families, with each count computed in polynomial time with unary output. Disjointness concerns used indices; zero targets are allowed.
Two-sided LWPP robustness for uniform indexed target families depending only on unary length. Cross-family disjointness holds at all natural lengths and both counts have unary polynomial-time certificates. The standard positive polynomial-size families are instances.
(Poly,Poly)-WPP = WPP, with disjoint uniformly computed binary integer target lists. The converse uses singleton acceptance and zero-rejection lists.
(Poly,Poly)-LWPP = LWPP, with disjoint target lists uniformly computed from unary length, including length zero. This is Hemaspaandra et al., Corollary 3.11.