Dear Iago Augusto Carvalho,

I thank you for your point of view. Here is a Yoshinori Shiozawa's phrase from https://www.researchgate.net/post/I_have_written_an_introductory_section_on_computing_complexity_Are_there_any_errors

"Of course, even if a problem is soluble in polynomial time, it does not assure that we can effectively solve the problem".

That is, is recognized the fact that a good polinomial algrithm is not always effective in practice Thus, the topic is marked with the aim of solving this problem. I suggested my model for its solution and introduced a class E, which should collect all the algorithms with the properties that were mentioned in the question. This class should be an alternative to classes P and NP in practice. It does not mean to find an approximate solution only, but the goal is to understand the measure of the closeness of this solution to the optimal solution. As you know, a huge number of heuristic algorithms are known at the moment. However, these algorithms know nothing about the fact that they sometimes give good (even optimal) results. These algorithms are blind.

As I am a simple amateur in the theory of computing complexity, it is astonishing that I was quoted in this argument.

Although P and NP are interesting and useful concepts, as they refer to the upper bounds, there are many aspects which evade P or NP complexity concepts. P and NP problems are all concerned with class of problems. It is natural however to ask what is the a rough estimates of an instance of a class of problem. Is there any particular type of distribution? For example, if we take the popular knapsack packing problem,it seems that most problems can be solved rapidly but the upper bound of NEO seems exponential. Does this mean there are some singular instances which requires computing time of high degree polynomials?

This kind of question is not only mathematically relevance but may have significant importance on the economic behavior of humans. I have argued these points in my consideration on the microfoundations of evolutionary economics:

Working Paper Microfoundations of Evolutionary Economics

If someone knows information on this kind of results, please let me know even if it is a provisional one.

Dear Yoshinori Shiozawa,

I thank you for your answer. Now I would want to try to answer your question

"For example, if we take the most popular knapsack packing problem, it seems that most problems can be solved rapidly  but the upper bound of NEO seems exponential.  Does it mean that some polynomials? "

I know very well the "knapsack packing problem". Let's stop in more detail on the one-dimensional knapsack packing problem. There are n integer positive numbers a_1, a_2, a_3, ... a_n. Let S = a_1 + a_2 + a_3 + ... a_n . Let a integer positive number B

Dear Gennady,

Thank you for the excellent introduction.

In this domain and using the complexity theory,

Manindra Agrawal, Neeraj Kayal, and Nitin Saxena succeed to prove the most surprising fantastic result "primes is in P."

They present an unconditional deterministic polynomial-time algorithm that determines whether an input number is prime or composite.

See the attached paper.

best wishes

Dear Issam Kaddoura,

In my opinion, the main problem facing today's Complexity Theory is the problem of Scalability. What was quite acceptable yesterday was now unacceptable. It is with the problem of scalability were faced, for example, the crypto currencies of Bitcoin, Epherium and others. The time has come when, with a large number of incoming transactions per unit of time, the systems stop working reliably. This fact led to the so-called problem of Segwit in Bitcoin https://en.wikipedia.org/wiki/SegWit, when it was necessary to reprogram the program for the miners. This led to the division of Bitcoin into two crypto-currencies. The program for crypto currency is the same combinatorial problem. Thus, what was acceptable earlier for large n becomes unacceptable today for very large n. You shared your reference about the algorithm of Manindra Agrawal, Neeraj Kayal, and Nitin Saxena. Here is a phrase from https://en.wikipedia.org/wiki/AKS_primality_тест "In 2005, Carl Pomerance and HW Lenstra, Jr. demonstrated a variant of AKS that runs O ({log (n)} ^ 6) ..." However, for very large n, for example, for n = 2 ^ m, where m - too very large number, the complexity of the AKS-algorithm will be O (m ^ 6), that is, the algorithm becomes unacceptable in practice for very large m in spite of the fact that the complexity O ({log (n)} ^ 6) from the class P . Since the problem of "Is a number prime or composite?" has only two possible answers YES or NO, it can not be solved approximately. That is, I conclude that this problem for very large n is not solvable.

Thus, the problem of scalability leads to a significant need to solve the problem approximately within a given time limit, which is acceptable for practice. However, it should be noted that not all combinatorial problems are scalable, that is, not all problems allow us to consider another scalable problem with new initial data D', instead of an original problem with the input data D, for which would be OPT(D)

Dear Dr. Gennady.

Your interpretation is amazing.

Best wishes

Actually there is a lot of good stuff already out there. You might find it helpful to do a web search on "polynomial-time approximation scheme" (PTAS), "fully polynomial-time approximation scheme" (FPTAS), "APX-hard", "MAX-SNP" and "primal-dual approximation algorithm". The book on approximation algorithms by Williamson and Schmoys is great as well.

Dear Adam N. Letchford,

your answer does not answer the question, because the class of algorithms with the ability to find an approximate solution A (D) = (1 + ε) * OPT (D) is infinitely small compared to the total number of combinatorial optimization problems. In other words, the mentioned "polynomial-time approximation scheme" (PTAS), the "fully polynomial-time approximation scheme" (FPTAS), "APX-hard", "MAX-SNP" and "primal-dual approximation algorithm" absolutely not applicable for the overwhelming number of combinatorial optimization problems.