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

摘要：

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

关键词：计算理论、双射函数、高重笛卡尔积、可数无穷集合、NP难

所属期刊栏目：19

分类号：TP301(计算技术、计算机技术)

资助基金：安徽省自然科学研究项目KJ2007B245

在线出版日期：2009-03-31（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：100-102