There Exists a Linear Problem with Infinite Combinatory Complexity

G. W. Wasilkowski, H. WoŹniakowski

Research output: Contribution to journalArticlepeer-review

3 Scopus citations


We present a linear problem whose information complexity is finite but whose combinatory complexity is infinite. Thus, this linear problem has infinite complexity due to infinite combinatory complexity and not due to information complexity. This holds in a real number model in which we only allow arithmetic operations, comparisons of real numbers as well as precomputation of finitely many arbitrary elements. The result is not true if we can also evaluate logarithms, exponentials, and ceilings.

Original languageEnglish
Pages (from-to)326-337
Number of pages12
JournalJournal of Complexity
Issue number2
StatePublished - Jun 1993

ASJC Scopus subject areas

  • Algebra and Number Theory
  • Statistics and Probability
  • Numerical Analysis
  • General Mathematics
  • Control and Optimization
  • Applied Mathematics


Dive into the research topics of 'There Exists a Linear Problem with Infinite Combinatory Complexity'. Together they form a unique fingerprint.

Cite this