[1]许精明.基于双射函数f：N^4→N的可计算性研究[J].计算机技术与发展,2009,(01):100-102.
XU Jing-ming.Research on Computability Based on Bijection Function f： N^4→N[J].,2009,(01):100-102.
点击复制
基于双射函数f：N^4→N的可计算性研究(
)
《计算机技术与发展》[ISSN:1006-6977/CN:61-1281/TN]
- 卷:
-
- 期数:
-
2009年01期
- 页码:
-
100-102
- 栏目:
-
智能、算法、系统工程
- 出版日期:
-
1900-01-01
文章信息/Info
- Title:
-
Research on Computability Based on Bijection Function f： N^4→N
- 文章编号:
-
1673-629X（2009）01-0100-03
- 作者:
-
许精明
-
安徽工业大学计算机学院
- Author(s):
-
XU Jing-ming
-
Institute of Computer, Anhui University of Technology
-
- 关键词:
-
计算理论; 双射函数; 高重笛卡尔积; 可数无穷集合; NP难
- Keywords:
-
computation theory; bijection function; high - fold Cartesian product; countably infinite set; NP hard
- 分类号:
-
TP301
- 文献标志码:
-
A
- 摘要:
-
对四重笛卡尔积双射函数f：N^4→N计算过程进行了研究，分析了其内在启发式构造规律，导出了f：N^4→N的显式计算式。运用的启发规则是，将N^4集合中前三个元素和相等的四元组划归为同一类，并按顺序将各类连续排列，再用交替枚举访问的方式对N^4中的各四元组进行访问，逐级构造出f：N^4→N的显式计算式。并将该式整理为只含有加法和乘法的运算形式。进一步分析得：n重函数f：N^4→N的时间复杂度是指数增长的，即O（c^n），c∈N。对函数f：N^4→N的计算属NP难问题。
- Abstract:
-
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 st
备注/Memo
- 备注/Memo:
-
安徽省自然科学研究项目(KJ2007B245)许精明(1963-)，男，安徽人，副教授，研究方向为理论计算机科学和人工智能等。
更新日期/Last Update:
1900-01-01