Effective simultaneous approximability of realsстатья
Информация о цитировании статьи получена из
Web of Science,
Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 18 июля 2013 г.
Аннотация:The effective simultaneous approximability of real vectors and sets of
reals is studied. A hierarchy of real vectors based on the Kolmogorov
complexity of computable approximations is constructed. We prove
that the hierarchy is nontrivial at the bottom levels but
collapses on the top levels. A hierarchy theorem which gives a
simple test for proper inclusion between two classes is established.
We also show that an effective approximation problem for a finite set
may be hard (have no computable solutions) when the corresponding
problems for all its proper subsets are simple (have computable
solutions).