There Exists a Linear Problem with Infinite Combinatory Complexity

G. W. Wasilkowski; H. WoŹniakowski

doi:10.1006/jcom.1993.1021

There Exists a Linear Problem with Infinite Combinatory Complexity

G. W. Wasilkowski, H. WoŹniakowski

Computer Science

Research output: Contribution to journal › Article › peer-review

3 Scopus citations

Abstract

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 language	English
Pages (from-to)	326-337
Number of pages	12
Journal	Journal of Complexity
Volume	9
Issue number	2
DOIs	https://doi.org/10.1006/jcom.1993.1021
State	Published - Jun 1993

ASJC Scopus subject areas

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

Access to Document

10.1006/jcom.1993.1021

Cite this

@article{5c07a240cd2a48948076199673af8405,

title = "There Exists a Linear Problem with Infinite Combinatory Complexity",

abstract = "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.",

author = "Wasilkowski, {G. W.} and H. Wo{\'Z}niakowski",

year = "1993",

month = jun,

doi = "10.1006/jcom.1993.1021",

language = "English",

volume = "9",

pages = "326--337",

number = "2",

}

TY - JOUR

T1 - There Exists a Linear Problem with Infinite Combinatory Complexity

AU - Wasilkowski, G. W.

AU - WoŹniakowski, H.

PY - 1993/6

Y1 - 1993/6

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0011656882&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0011656882&partnerID=8YFLogxK

U2 - 10.1006/jcom.1993.1021

DO - 10.1006/jcom.1993.1021

M3 - Article

AN - SCOPUS:0011656882

SN - 0885-064X

VL - 9

SP - 326

EP - 337

JO - Journal of Complexity

JF - Journal of Complexity

IS - 2

ER -

There Exists a Linear Problem with Infinite Combinatory Complexity

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this