NSFCNational Natural Science Foundation of China (NSFC) [11171370]
机构署名：
本校为其他机构
院系归属：
数学与统计学学院
摘要：
This paper exhibits a distinguishing algorithmic feature of a phase transition point of a random system I of m linear equations over a finite field with n variables: the complexity of Gaussian elimination for testing satisfiability of the systems approaches maximum at the satisfiability threshold point m/n = 1, and the worst instances should be found at the point. It is very interesting that the algorithm exactly undergoes an easy/hard...
