Algebraic properties for selector functions

被引:3
|
作者
Hemaspaandra, LA [1 ]
Hempel, H [1 ]
Nickelsen, A [1 ]
机构
[1] Univ Rochester, Dept Comp Sci, Rochester, NY 14627 USA
关键词
computational complexity theory; P-selectivity; NP-selectivity; nondeterministic selectivity; selector functions; advice complexity; nonuniform complexity; semifeasible computation; algebraic properties; associativity; commutativity; immunity; printability; tournaments; digraphs;
D O I
10.1137/S0097539703427550
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
The nondeterministic advice complexity of the P-selective sets is known to be exactly linear. Regarding the deterministic advice complexity of the P-selective sets - i.e., the amount of Karp-Lipton advice needed for polynomial-time machines to recognize them in general - the best current upper bound is quadratic [K. Ko, J. Comput. System Sci., 26 (1983), pp. 209 - 221] and the best current lower bound is linear [L. Hemaspaandra and L. Torenvliet, Theoret. Comput. Sci., 154 (1996), pp. 367 - 377]. We prove that every associatively P-selective set is commutatively, associatively P-selective. Using this, we establish an algebraic sufficient condition for the P-selective sets to have a linear upper bound ( which thus would match the existing lower bound) on their deterministic advice complexity: If all P-selective sets are associatively P-selective, then the deterministic advice complexity of the P-selective sets is linear. The weakest previously known sufficient condition was P = NP. We also establish related results for algebraic properties of, and advice complexity of, the non-deterministically selective sets.
引用
收藏
页码:1309 / 1337
页数:29
相关论文
共 50 条
  • [41] Students' Conceptions on Algebraic Properties and Their Effect on Performance in Algebra: The Case of Some Public Secondary Schools in Maguindanao and Lanao del Sur
    Mangorsi, Solaiman B.
    2013 FOURTH INTERNATIONAL CONFERENCE ON EDUCATION AND SPORTS EDUCATION (ESE 2013), PT II, 2013, 12 : 722 - 726
  • [42] Certain algebraic identities on prime rings with involution
    Mamouni, A.
    Oukhtite, L.
    Zerra, M.
    COMMUNICATIONS IN ALGEBRA, 2021, 49 (07) : 2976 - 2986
  • [43] Commutativity and Prime Ideals with Proposed Algebraic Identities
    Faraj, Anwar Khaleel
    Abduldaim, Areej M.
    INTERNATIONAL JOURNAL OF MATHEMATICS AND COMPUTER SCIENCE, 2021, 16 (04) : 1607 - 1622
  • [44] COMMUTATIVITY WITH ALGEBRAIC IDENTITIES INVOLVING PRIME IDEALS
    El Mir, Hajar
    Mamouni, Abdellah
    Oukhtite, Lahcen
    COMMUNICATIONS OF THE KOREAN MATHEMATICAL SOCIETY, 2020, 35 (03): : 723 - 731
  • [45] The Tn7 transposition regulator TnsC interacts with the transposase subunit TnsB and target selector TnsD
    Choi, Ki Young
    Spencer, Jeanelle M.
    Craig, Nancy L.
    PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 2014, 111 (28) : E2858 - E2865
  • [46] On cross-correlation properties of S-boxes and their design using semi-bent functions
    Pasalic, Enes
    Bajric, Samed
    Djordjevic, Milan
    SECURITY AND COMMUNICATION NETWORKS, 2015, 8 (05) : 790 - 800
  • [47] The characterization of monotone functions that generate associative functions
    Chen, Meng
    Zhang, Yun-Mao
    Wang, Xue-ping
    FUZZY SETS AND SYSTEMS, 2025, 500
  • [48] A Note on Fast Algebraic Attacks and Higher Order Nonlinearities
    Wang, Qichun
    Johansson, Thomas
    INFORMATION SECURITY AND CRYPTOLOGY, 2011, 6584 : 404 - +
  • [49] An Algebraic Approach to Duflo's Polynomial Conjecture in the Nilpotent Case
    Tanimura, Yoshinori
    JOURNAL OF LIE THEORY, 2019, 29 (03) : 839 - 879
  • [50] ADDITIVE MAPPINGS SATISFYING CERTAIN ALGEBRAIC EQUATIONS IN PRIME RINGS
    El Mir, Hajar
    Mamouni, Abdellah
    Oukhtite, Lahcen
    MISKOLC MATHEMATICAL NOTES, 2023, 24 (03) : 1329 - 1336