NP on Logarithmic Space
 |
| John Forbes Nash Jr. |
In 1955, the well-known mathematician John Nash wrote to the United
States National Security Agency about a problem that had major
implications for security and scientific development. A short time later
Gödel, one of the most important mathematical logicians, came to the
same conclusion and wrote a letter to John von Neumann explaining about
the same problem and its relation to computational and mathematical
topics. John von Neumann had a successful career in this field at that
time: unfortunately he promptly died of cancer and Gödel's letter was
never answered. It took decades later for the American mathematicians
Stephen Cook and Russian Leonid Levin could be able to independently
introduce and formulate this problem during the "scientific race" of the
Cold War. The problem was called P versus NP and it consisted of
knowing whether computers were capable or not of solving problems that
seemed unfeasible with the computers of that time. The wheel of time
passed and these problems are still not feasible to be solved by current
computers despite being more powerful. The problem has been extensively
studied and it is now known to potentially cure cancer if a positive
solution is found. Not only this, the disasters caused by the
earthquakes in Syria and Turkey could have been predicted and avoided,
artificial intelligence tools would achieve their full potential within
the recent advances and would also have important industrial and social
value since many current flow processes depend on computers. The author,
found a non-constructive solution (that is, focused on a theoretical
answer rather than a practical one) that seems to be feasible not only
in speed but also in memory efficiency.
Comments
Post a Comment