Vplyv veľkosti a štruktúry dát na algoritmickú zložitosť v triedach P a NP

Abstract

Computational complexity and the classification of problems into the categories P and NP represent critical aspects in the field of algorithmic complexity. This article focuses on the interaction between the size and structurality of data sets and their impact on the categorization of problems into these categories. While problems in the P category can be efficiently solved, problems in the NP category are characterized by quick verification of their solutions. In the context of Big Data, a new level of complexity emerges, complicating the classification of problems. The article also extends the discussion to Nos-Nob data sets, which are too large for regular computers but too small for distributed systems, and often require a specialized approach. Based on an analysis within structured, semi-structured, and unstructured data in the context of small, big, and nos-nob data, the article shows that it is possible to estimate into which data category a task falls, and therefore the most suitable processing technology, based on its categorization into P or NP.