G
G
gghaker2016-08-12 14:02:04
Mathematics
gghaker, 2016-08-12 14:02:04

What are the pros and cons of constructive P=NP proof (with algorithm)?

It’s clear with the minuses - encryption stops working and everything that depends on it: mobile phones, satellite TV, online games ...
Are there any pluses?

Answer the question

In order to leave comments, you need to log in

1 answer(s)
V
Vladimir Dubrovin, 2016-08-12
@z3apa3a

Assuming that the proof will be algorithmic and can be used in practice, this will make the solution of the entire class of NP-complete problems more efficient, their complexity will become not exponential, but polynomial.
The list of tasks is here: https: //en.wikipedia.org/wiki/List_of_NP-complete
_...
in a specific problem with specific dimensions, the required polynomial may turn out to be less efficient than the exponent.

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question