Is NP=P? A Polynomial-time solution for finite graph isomorphism

Lecture Topic:Is NP=P？A Polynomial-time solution for finite graph isomorphism

Lecturer: He Jing(Professor, Doctoral Advisor at Swinburne University of Technology, Australia)

Lecture Time: Jul. 7, 2019, 10:30-12:00

Lecture Location:Sixue Building A114

Abstract: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 were 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.

About the Lecturer: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.

All students, faculties and staff are welcome to attend this lecture!

Host Organizations:

School of Science

Institute of Artificial Intelligence

Department of Science and Technology