基于双射函数f:N4→N的可计算性研究

• 作者: 许精明
• 来源期刊: 计算机技术与发展
• 学科: 工学
• 关键词: 计算理论 双射函数 高重笛卡尔积 可数无穷集合 NP难
• 年，卷（期）: 2009,（1）
• 所属期刊栏目: 智能、算法、系统结构
• 页码范围: 100-102
• 页数: 3页
• 分类号: TP301
• 字数: 2152字
• 语种: 中文
• DOI: 10.3969/j.issn.1673-629X.2009.01.028

摘要

对四重笛卡尔积双射函数f:N4→N计算过程进行了研究,分析了其内在启发式构造规律,导出了f:N4→N的显式计算式.运用的启发规则是,将N4集合中前三个元素和相等的四元组划归为同一类,并按顺序将各类连续排列,再用交替枚举访问的方式对N4中的各四元组进行访问,逐级构造出f:N4→N的显式计算式.并将该式整理为只含有加法和乘法的运算形式.进一步分析得: n重函数f:Nn→N的时间复杂度是指数增长的,即O(cn),c∈N.对函数f∶Nn→N的计算属NP难问题.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	许精明	安徽工业大学计算机学院	12	49	4.0	6.0