论文标题：Local holographic transformations: tractability and hardness（局部全息变换——可解性与困难性）

期刊：Frontiers of Computer Science

作者：Peng YANG, Zhiguo FU

发表时间：15 Apr 2023

DOI：10.1007/s11704-022-1231-5

微信链接：点击此处阅读微信文章

导读

文献[10]引入了局部全息变换，并在图片中发现了新的可解类，即局部仿射函数。本文对一般的 d，把局部仿射函数推广到图片, 并在图片中发现了新的可解类，其可解性由局部全息变换和全局全息变换相结合得到。另外，本文展示了使用局部全息变换来证明困难性的方法，这在计数问题的计算复杂性分类中有着独立的意义。

文章精要

相关内容推荐：

随机RB模型的超解研究 2022 16(6)：166406

一种用于基于定理证明同步模型验证的动态逻辑 2022 16(4)：1644057

赋范下推自动机互模拟等价的参数复杂性 2022 16(4)：164405

随机正则(s,c,k)-SAT问题的可满足临界 2022 16(3)：163408

图mCn的全友好指数集 2022 16(3)：163403

正则区间图边删除问题的一个改进算法 2022 16(2)：162401

再论近似部分优化问题的线性规划舍入加贪心方法 2022 16(1)：161402

Frontiers of Computer Science

Frontiers of Computer Science （FCS）是由教育部主管、高等教育出版社和北京航空航天大学共同主办、SpringerNature 公司海外发行的英文学术期刊。本刊于 2007 年创刊，双月刊，全球发行。主要刊登计算机科学领域具有创新性的综述论文、研究论文等。本刊主编为周志华教授，共同主编为熊璋教授。编委会及青年 AE 团队由国内外知名学者及优秀青年学者组成。本刊被 SCI、Ei、DBLP、INSPEC、SCOPUS 和中国科学引文数据库（CSCD）核心库等收录，为 CCF 推荐期刊；两次入选“中国科技期刊国际影响力提升计划”；入选“第4届中国国际化精品科技期刊”；入选“中国科技期刊卓越行动计划项目”。

《前沿》系列英文学术期刊

由教育部主管、高等教育出版社主办的《前沿》（Frontiers）系列英文学术期刊，于2006年正式创刊，以网络版和印刷版向全球发行。系列期刊包括基础科学、生命科学、工程技术和人文社会科学四个主题，是我国覆盖学科最广泛的英文学术期刊群，其中12种被SCI收录，其他也被A&HCI、Ei、MEDLINE或相应学科国际权威检索系统收录，具有一定的国际学术影响力。系列期刊采用在线优先出版方式，保证文章以最快速度发表。

中国学术前沿期刊网

http://journal.hep.com.cn