.png){kind=icon}
返回
Efficient Compression in Semigroups
.png){kind=icon}
PRE
AI
DOI：10.4230/LIPIcs.STACS.2026.80.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
直线程序是计算机科学多个领域中的核心工具，包括数据压缩、代数复杂度理论和代数方程的算法求解。在代数设置中，直线程序可被解释为半群或群等代数结构上的电路，它们在计算复杂度方面提供了深刻的见解。Babai和Szemerédi（1984）的一项关键结果表明，有限群可通过直线程序实现高效压缩，从而为群设计了一种黑盒计算模型。基于他们的成果，Fleischer（2019）将某些有限半群（拟变异类）的Cayley表成员问题置于NPOLYLOGTIME类中，某些情况下甚至置于FOLL类。他还提供了可进行高效压缩的有限幺半群的拟变异类的完全分类。在本工作中，我们完成了Fleischer开创的分类计划，精确表征了可通过直线程序实现高效压缩的有限半群的拟变异类。在此过程中，我们还改进了半群、幺半群和群上直线程序长度和宽度的多个已知界限。这些结果为Cayley表模型中的成员问题提供了新的上界：对于所有可进行高效压缩且不包含任何非可解群的拟变异类，我们获得了FOLL算法。特别地，我们解决了Barrington、Kadau、Lange和McKenzie（2001）的一个猜想，表明所有可解群的成员问题属于FOLL类。
Keyword:
Semigroups
straight-line programs
compression
membership problem
期刊
机构
引用论文
暂无论文信息