基于双射函数f∶N^4→N的可计算性研究  

Research on Computability Based on Bijection Function f∶N^4→N

作　　者：许精明[1] 

机构地区：[1]安徽工业大学计算机学院,安徽马鞍山243002

出　　处：《计算机技术与发展》2009年第1期100-102,共3页Computer Technology and Development

基　　金：安徽省自然科学研究项目(KJ2007B245)

摘　　要：对四重笛卡尔积双射函数f:N4→N计算过程进行了研究,分析了其内在启发式构造规律,导出了f:N4→N的显式计算式。运用的启发规则是,将N4集合中前三个元素和相等的四元组划归为同一类,并按顺序将各类连续排列,再用交替枚举访问的方式对N4中的各四元组进行访问,逐级构造出f:N4→N的显式计算式。并将该式整理为只含有加法和乘法的运算形式。进一步分析得:n重函数f∶Nn→N的时间复杂度是指数增长的,即O(cn),c∈N。对函数f∶Nn→N的计算属NP难问题。The process of computation for four - fold Cartesian product bijection function f：N^4→N is researched in this paper and the heuristic rules of the function are analyzed. A formula of the function f： N^4→N is deduced. The heuristic rules are that if the strm of pre - three elements of 4 -ary relation of N4 is equal, they are put in one class regularly, and all classes are formed successively, then visit all elements of N alternately. The formula of function f： N^4→N is simplified as simply as possible only containing addition and multiplication operations. Further analysis appears that the time complexity of function f： N^4→N is O （c^n ）, c ∈ N , the computing to f： N^4→N is an NP hard problem.

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

分 类 号：TP301[自动化与计算机技术—计算机系统结构]