报告题目：Is NP=P？A Polynomial-time solution for finite graph isomorphism

报 告 人：何静（澳大利亚斯威本科技大学软件与电子工程学院教授）

报告时间：2019年5月23日（星期四）下午3：50

报告地点：工学二号馆621

个人简介：Dr. Jing He is a professor in school of software and electrical engineering, Swinburne University of Technology. She was awarded a PhD degree from the Academy of Mathematics and System Science, Chinese Academy of Sciences in 2006. Prior to joining Victoria University, she worked in the University of Chinese Academy of Sciences, China during 2006-2008. She has been active in areas of Algorithm and Chips, Artificial Intelligence, Data Mining, Web service/Web search, Spatial and Temporal Database, Multiple Criteria Decision Making, Intelligent Systems, Scientific Workflow and some industry fields such as E-Health, Petroleum Exploration and Development, Water recourse Management and e-Research. She has published over 160 research papers in refereed international journals and conference proceedings, including ACM Transaction on Internet Technology (TOIT), IEEE Transaction on Knowledge and Data Engineering (TKDE), Information Systems, the Computer journal, Computers and Mathematics with Applications, Concurrency and Computation: Practice and Experience, International Journal of Information Technology & Decision Making, Applied Soft Computing, and Water Resource Management. She has received over 3.5 million Australian dollar research funding from the Australian Research Council (ARC) with ARC Early Career Researcher Award (DECRA), ARC Discovery Project, ARC Linkage Project and National Natural Science Foundation of China (NSFC) since 2008.

报告摘要：This talk will introduce a polynomial-time solution for finite graph isomorphism. It targets to provide a solution for one of the seven-millennium problems: NP versus P. Three new representation methods of a graph as vertex/edge adjacency matrix and triple tuple are proposed. A duality of edge and vertex and a reflexivity between vertex adjacency matrix and edge adjacency matrix were first introduced to present the core idea. Beyond this, the mathematical approval is based on an equivalence between permutation and bijection. Because only addition and multiplication operations satisfy the commutative law, we proposed a permutation theorem to check fast whether one of two sets of arrays is a permutation of another or not. The permutation theorem was mathematically approved by Integer Factorization Theory, Pythagorean Triples Theorem and Fundamental Theorem of Arithmetic. For each of two n-ary arrays, the linear and squared sums of elements were respectively calculated to produce the results.