Premium
Checking identities is computationally intractable NP‐hard and therefore human provers will always be needed
Author(s) -
Kreinovich Vladik,
Tao ChinWang
Publication year - 2004
Publication title -
international journal of intelligent systems
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.291
H-Index - 87
eISSN - 1098-111X
pISSN - 0884-8173
DOI - 10.1002/int.10149
Subject(s) - nondeterministic algorithm , np , computer science , identity (music) , time complexity , model checking , p versus np problem , computational complexity theory , algorithm , theoretical computer science , mathematics , turing machine , physics , acoustics , computation
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. © 2004 Wiley Periodicals, Inc.