Checking identities is computationally intractable NP-hard and therefore human provers will always be needed
✍ Scribed by Vladik Kreinovich; Chin-Wang Tao
- Publisher
- John Wiley and Sons
- Year
- 2004
- Tongue
- English
- Weight
- 97 KB
- Volume
- 19
- Category
- Article
- ISSN
- 0884-8173
No coin nor oath required. For personal study only.
✦ Synopsis
A 1990 article in the American Mathematical Monthly has shown that most combinatorial identities of the type described in Monthly problems can be solved by known identity checking algorithms. A natural question arises: are these algorithms always feasible or can the number of computational steps be so big that application of these algorithms sometimes is not physically feasible? We prove that the problem of checking identities is nondeterministic polynomial (NP) hard, and thus (unless NP ϭ P) for every algorithm that solves it, there are cases in which this algorithm would require exponentially long running time and thus will not be feasible. This means that no matter how successful computers are in checking identities, human mathematicians will always be needed to check some of them.