English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Linear and semidefinite programming (LP, SDP), regularisation through basispursuit (BP) and Lasso have seen great success in mathematics, statistics, datascience, computer-assisted proofs and learning. The success of LP istraditionally attributed to the fact that it is "in P" for rational inputs. Onthe other hand, in his list of problems for the 21st century S. Smale calls for"[Computational] models which process approximate inputs and which permitround-off computations". Indeed, since e.g. the exponential function does nothave an exact representation or floating-point arithmetic approximates everyrational number that is not in base-2, inexact input is a daily encounter. Themodel allowing inaccurate input of arbitrary precision, which we call theextended model, leads to extended versions of fundamental problems such as:"Are LP and other aforementioned problems in P?" The same question can be askedfor an extended version of Smale's 9th problem on the list of mathematicalproblems for the 21st century: "Is there a polynomial time algorithm over thereal numbers which decides the feasibility of the linear system ofinequalities, and if so, outputs a feasible candidate?" One can thus pose thisproblem in the extended model. Similarly, the optimisation problems BP, SDP andLasso, where the task is to output a solution to a specified precision, canlikewise be posed in the extended model, also considering randomisedalgorithms. We will collectively refer to these problems as the extendedSmale's 9th problem, which we settle in both the negative and the positiveyielding two surprises: (1) In mathematics, sparse regularisation, statistics,and learning, one successfully computes with non-computable functions. (2) Inorder to mathematically characterise this phenomenon, one needs an intricatecomplexity theory for, seemingly paradoxically, non-computable functions.

The extended Smale's 9th problem -- On computational barriers and paradoxes in estimation, regularisation, computer-assisted proofs and learning