There Exists a Linear Problem with Infinite Combinatory Complexity |
| |
| Institution: | Department of Computer Science, University of Kentucky, Lexington, Kentucky 40506; Department of Computer Science, Columbia University, New York, New York 10027, and Institute of Applied Mathematics, University of Warsaw, Poland |
| |
| 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. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
