IIT Bombay faculty takes a shot at a long-standing problem in computer science
The Hindu
This is the first case in which a super-polynomial lower bound has been established for any problem in the algebraic domain.
What differentiates humans from computers? Is it only a matter of time before efficient algorithms enable a computer to perform the most creative tasks, even to the extent of proving mathematical theorems — an accomplishment that is considered the acme of human contribution to progress in Mathematics? Or is there an inherent limit to what even a super computer can do? A problem in Computer Science holds the key to the above questions. No, it is not solved yet, and is, in fact, listed as one of the “millennium problems”, along with six others, including the Riemann Hypothesis. It carries a prize of a million dollars for solving it. The problem is the P versus NP question. This is a problem that classifies computing problems into classes according to the time and resources that will be used up in tackling them and forms the cornerstone problem of computational complexity.More Related News