What is it about?
The class P is the class of discrete problems that are tractable by a computer. The class NP is the class of dicrete problems that would be tractable by a magic, black-box based computer (aka a non-deterministic computer). A lot of important computational problems are in the class NP. Can we get rid of the black box? This is the problem to decide if P is equal or different to NP. It is currently one of the major problems in computer science. Our aim was to generalize this theory to continuous problems, taking condition number as part of the input length, and taking numerical stability into account. In this setting, we can provide an NP-complete problem.
Featured Image
Photo by Artiom Vallat on Unsplash
Why is it important?
While classical theoretical computer science is discrete, most engineering or real-world problems deal with continuous quantities. Generalizing NP-completeness theory allows to say, if you can solve one of those NP-complete numerical problem in polynomial time, you can solve them all.
Perspectives
As I said, we provided an NP-complete problem. Now I would like to see a nice, easy to describe NP-complete problem, like the travelling salesman is for the classical NP-completeness theory, or the Nullstellensatz for the theory over a ring.
Gregorio Malajovich
Universidade Federal do Rio de Janeiro
Read the Original
This page is a summary of: A Theory of NP-completeness and Ill-conditioning for Approximate Real Computations, Journal of the ACM, August 2019, ACM (Association for Computing Machinery),
DOI: 10.1145/3321479.
You can read the full text:
Contributors
The following have contributed to this page
