A new criterion for tractability of multivariate problems

Anargyros Papageorgiou, Iasonas Petras

Research output: Contribution to journalArticle

15 Citations (Scopus)

Abstract

Tractability of multivariate problems studies their complexity with respect to the number of variables, d, and the accuracy of the solution ε. Different types of tractability have been used, such as polynomial tractability and weak tractability and others. These tractability types, however, do not express the complexity with respect to the number of bits of accuracy. We introduce two new tractability types, polylog tractability and ln κ-weak tractability. A problem is polylog tractable iff its complexity is polynomial in d and in lnε-1, while a problem is lnκ-weakly tractable iff its complexity is not exponential in d and lnκε-1, for some κ≠¥ 1. We study general multivariate problems and multivariate tensor product problems. We provide necessary and sufficient conditions for the respective tractability types. Moreover, we show that a multivariate tensor product problem cannot be polylog tractable and cannot be ln1-weakly tractable (i.e., with κ=1) unless it is trivial.

Original languageEnglish (US)
Pages (from-to)604-619
Number of pages16
JournalJournal of Complexity
Volume30
Issue number5
DOIs
StatePublished - Jan 1 2014

Fingerprint

Tractability
Tensors
Polynomials
Tensor Product
Polynomial
Trivial
Express
Necessary Conditions
Sufficient Conditions

All Science Journal Classification (ASJC) codes

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

Keywords

  • Complexity
  • Multivariate problem
  • Tractability

Cite this

Papageorgiou, Anargyros ; Petras, Iasonas. / A new criterion for tractability of multivariate problems. In: Journal of Complexity. 2014 ; Vol. 30, No. 5. pp. 604-619.
@article{7af83da996ec4f92ad677595fae16d3b,
title = "A new criterion for tractability of multivariate problems",
abstract = "Tractability of multivariate problems studies their complexity with respect to the number of variables, d, and the accuracy of the solution ε. Different types of tractability have been used, such as polynomial tractability and weak tractability and others. These tractability types, however, do not express the complexity with respect to the number of bits of accuracy. We introduce two new tractability types, polylog tractability and ln κ-weak tractability. A problem is polylog tractable iff its complexity is polynomial in d and in lnε-1, while a problem is lnκ-weakly tractable iff its complexity is not exponential in d and lnκε-1, for some κ{\^a}‰ ¥ 1. We study general multivariate problems and multivariate tensor product problems. We provide necessary and sufficient conditions for the respective tractability types. Moreover, we show that a multivariate tensor product problem cannot be polylog tractable and cannot be ln1-weakly tractable (i.e., with κ=1) unless it is trivial.",
keywords = "Complexity, Multivariate problem, Tractability",
author = "Anargyros Papageorgiou and Iasonas Petras",
year = "2014",
month = "1",
day = "1",
doi = "https://doi.org/10.1016/j.jco.2014.03.001",
language = "English (US)",
volume = "30",
pages = "604--619",
journal = "Journal of Complexity",
issn = "0885-064X",
publisher = "Academic Press Inc.",
number = "5",

}

A new criterion for tractability of multivariate problems. / Papageorgiou, Anargyros; Petras, Iasonas.

In: Journal of Complexity, Vol. 30, No. 5, 01.01.2014, p. 604-619.

Research output: Contribution to journalArticle

TY - JOUR

T1 - A new criterion for tractability of multivariate problems

AU - Papageorgiou, Anargyros

AU - Petras, Iasonas

PY - 2014/1/1

Y1 - 2014/1/1

N2 - Tractability of multivariate problems studies their complexity with respect to the number of variables, d, and the accuracy of the solution ε. Different types of tractability have been used, such as polynomial tractability and weak tractability and others. These tractability types, however, do not express the complexity with respect to the number of bits of accuracy. We introduce two new tractability types, polylog tractability and ln κ-weak tractability. A problem is polylog tractable iff its complexity is polynomial in d and in lnε-1, while a problem is lnκ-weakly tractable iff its complexity is not exponential in d and lnκε-1, for some κ≠¥ 1. We study general multivariate problems and multivariate tensor product problems. We provide necessary and sufficient conditions for the respective tractability types. Moreover, we show that a multivariate tensor product problem cannot be polylog tractable and cannot be ln1-weakly tractable (i.e., with κ=1) unless it is trivial.

AB - Tractability of multivariate problems studies their complexity with respect to the number of variables, d, and the accuracy of the solution ε. Different types of tractability have been used, such as polynomial tractability and weak tractability and others. These tractability types, however, do not express the complexity with respect to the number of bits of accuracy. We introduce two new tractability types, polylog tractability and ln κ-weak tractability. A problem is polylog tractable iff its complexity is polynomial in d and in lnε-1, while a problem is lnκ-weakly tractable iff its complexity is not exponential in d and lnκε-1, for some κ≠¥ 1. We study general multivariate problems and multivariate tensor product problems. We provide necessary and sufficient conditions for the respective tractability types. Moreover, we show that a multivariate tensor product problem cannot be polylog tractable and cannot be ln1-weakly tractable (i.e., with κ=1) unless it is trivial.

KW - Complexity

KW - Multivariate problem

KW - Tractability

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

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

U2 - https://doi.org/10.1016/j.jco.2014.03.001

DO - https://doi.org/10.1016/j.jco.2014.03.001

M3 - Article

VL - 30

SP - 604

EP - 619

JO - Journal of Complexity

JF - Journal of Complexity

SN - 0885-064X

IS - 5

ER -