scientific article; zbMATH DE number 3968574
[For the entire collection see Zbl 0592.00028.] The computational complexity of functions is investigated when input data are presented in some succinct form. It is shown that easily computable functions which are approached this way become intractable. Next, the data representations which are resaonable in a sense of being convenient for effective manipulation of arithmetics are considered. The existence of reasonable data representations which permit an arbitrary compact compression of initial information is shown. Thus for such representations an ordinary polynomial time algorithms runs in exponential time if the representation exponentially compresses binary codes of some numbers. This implies the necessity of seeking for feasible algorithms which manipulate directly with the codes of succinct representations of initial data. However, it is often difficult to find or even to prove the existence of such algorithms. To illustrate this, we provide an example of a function computable on a finite automaton and of a reasonable encoding such that finding of the polynomial (from the length of data codes) algorithm for this function is the same as proving the equality \(P=NP\).
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3735699)