Strolling through informatics #9 – Algorithms at the boundary

previous #8 ––– next #10

by Enrico Nardelli

(versione italiana qua)

To complete our picture of algorithmic problem solving, we need to discuss one more situation that is extremely important in today's context. Based on what was said in the previous post (How long does this algorithm take?), there can exist problems for which no algorithms with polynomial complexity functions are known (and therefore we cannot say they belong to class P), but for which proof of the impossibility of obtaining them has not yet been found (and therefore we cannot say they properly belong to class EXP). This means that for these problems we know at least one solution algorithm (whose complexity function is exponential), and this classifies them as computable problems, but we cannot say whether they are problems that belong to the "good" variety (i.e., they admit polynomial algorithms, meaning they are tractable) or the "bad" variety (with only exponential algorithms, meaning they are intractable). In this case the problem is in a kind of limbo, in which theoretical computer scientists have identified a very important set called class NP, which marks the boundary between tractability and intractability.

Without going into the details of how this class is defined (for which I refer to the book The Computer Revolution), we can say that it includes problems whose solutions can be verified in polynomial time and for which only solution algorithms of exponential complexity are known. Indeed, hundreds of these problems exist (thousands if we consider their variants), for which mutual equivalence has been proven. This equivalence means that if a polynomial algorithm were found for just one of them, then all these problems would fall into class P (they would be, that is, tractable problems). If just one of them were instead proven to properly belong to class EXP, then they would all be classified as intractable (though this latter hypothesis seems unlikely to most scholars).

Given the current state of knowledge in theoretical informatics, we know that class P is strictly contained in class EXP (I remind you that a set A is strictly contained in set B if every element of A also belongs to B and furthermore we are certain of the existence of elements that belong to B and do not belong to A). However, the known relationships between classes P, NP and EXP are only of containment, meaning that P is contained in NP and that NP is contained in EXP, but we don't know exactly which of these containments is strict. The most interesting aspect concerns the relationship between classes P and NP. It could be strict or the two classes could coincide. The problem of whether class P and class NP coincide or not, that is

P=NP ?

is probably the most famous open problem in theoretical informatics. The Clay Mathematics Institute included it in 2000 among the seven millennium problems and has offered a prize of one million dollars for its proof.

The problem has particular interest since problems in class NP that are thought not to be in P often form the basis of cryptographic methods that protect the security of commercial transactions on the Internet. For example, the RSA public key encryption system bases its security on the fact that the decomposition of an integer into prime factors is one of these problems.

Since no efficient algorithms (i.e., executable in polynomial time) are currently known for decomposing an integer into its prime factors, the system cannot be broken in an acceptable time. It should be noted that, with sufficient dedicated hardware equipment (which is within reach of large organizations that can count on substantial economic resources such as, for example, the NSA, acronym for National Security Agency, the national security agency of the United States) it is possible to decompose integers of 1,024 bits, which was the recommended value for constructing RSA keys until a few years ago. Bruce Schneier, a US security expert, recommended in 2007, when the decomposition of an integer of about 1,024 bits was announced (albeit of a particular type that made the work simpler), to abandon keys of this length. The availability of so-called "quantum" computers is another possible threat to RSA public key encryption, but appropriate countermeasures are being taken for this eventuality as well.

[[The posts in this series are based on the Author's book (in Italian) La rivoluzione informatica: conoscenza, consapevolezza e potere nella società digitale, (= The Informatics Revolution: Knowledge, Awareness and Power in the Digital Society) to which readers are referred for further reading]].

--
The original version (in italian) has been published by "Osservatorio sullo Stato digitale" (= Observatory on Digital State) of IRPA - Istituto di Ricerche sulla Pubblica Amministrazione (= Research Institute on Public Administration) on 20 November 2024.