There exists a linear problem with infinite combinatory complexity (Q1260663)

For many of Information-based Complexity problems studied to date, the combinatory complexity is smaller than the information complexity and, therefore, the complexity is roughly equal to the information complexity. In particular, unsolvability of all known problems was due to infinite information complexity. The paper exhibits a problem with finite information complexity which is unsolvable due to infinite combinatory complexity. This problem is linear and is a slight modification of a problem studied by \textit{A. G. Werschulz} and \textit{H. Woźniakowski} [Aequationes Math. 31, 202-212 (1986; Zbl 0603.65036)]. The result holds in the worst case setting with a real number model of computation in which exact arithmetic operations and comparisons on real numbers as well as precomputation of finitely many elements is allowed. The result is no longer true if, additionally, the model of computation is enriched by exact evaluations of logarithms, exponentials, and ceilings (approximating these extra operations does not help). This result can be compared to the result of \textit{C. H. Papadimitriou} and \textit{J. Tsitsiklis} [SIAM Control Optim. 24, 636-654 (1980; Zbl 0604.90009)] who showed, using a Turing machine model of computation, nonpolynomial combinatory complexity for a nonlinear problem of decentralized control theory provided the \(P\neq NP\) conjecture holds. Hence, although different models of computation are used, the combinatory complexity vastly dominates the information complexity for both problems. It is, however, interesting to note that the result of \textit{C. H. Papadimitriou} and \textit{J. Tsitsiklis} [loc. cit.] holds for a nonlinear problem ad assuming that \(P\neq NP\). The problem studied in the paper is linear and its infinite complexity does not depend on the \(P\neq NP\) conjecture.