SEQUENCES OF LANGUAGES WHEN THE LIMIT GOES TO INFINITY
Frank Vega · HAL (Le Centre pour la Communication Scientifique Directe) · 2017
This work is specifically about an interesting class of problems called the NP-complete problems, whose status is unknown. No polynomial-time algorithm has yet been discovered for some NP-complete problem. If any single NP-complete problem can be solved in polynomial-time, then every NP problem has a polynomial-time algorithm. We study two new complexity classes which have a close relation to the NP-complete problems. We call these classes as infinite-UP and infinite-P. Informally, the class infinite-UP contains those languages that are the limit of a sequence of languages in UP when this sequence goes to infinity. The class infinite-P is similar but the languages in the sequence are in P. In addition, in those sequences every previous language is a strict subset of the next one. We show two NP-complete problems which are infinite-UP and infinite-P respectively. In this way, we demonstrate some new properties of the NP-complete problems which can help us to understand better the P versus NP problem.