Complexity of deciding whether a tropical linear prevariety is a tropical variety.

Dima Grigoriev; Nicolai Vorobjov

doi:10.1007/s00200-019-00407-w

Complexity of deciding whether a tropical linear prevariety is a tropical variety.

Dima Grigoriev, Nicolai Vorobjov

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

11 Downloads (Pure)

Abstract

We give an algorithm, with a singly exponential complexity, deciding whether a tropical linear prevariety is a tropical linear variety. The algorithm relies on a criterion to be a tropical linear variety in terms of a duality between the tropical orthogonalization A ^⊥ and the double tropical orthogonalization A ^{⊥ ⊥} of a subset A of the vector space (R∪ { ∞}) ⁿ. We also give an example of a countable family of tropical hyperplanes such that their intersection is not a tropical prevariety.

Original language	English
Pages (from-to)	157-174
Number of pages	18
Journal	Applicable Algebra in Engineering Communication and Computing
Volume	32
Issue number	2
Early online date	29 Nov 2019
DOIs	https://doi.org/10.1007/s00200-019-00407-w
Publication status	Published - 31 Mar 2021

Keywords

Tropical algebra
Computer algebra
Complexity

Access to Document

10.1007/s00200-019-00407-w

1803.01068.PDF
This is a post-peer-review, pre-copyedit version of an article published in Applicable Algebra in Engineering, Communication and Computing. The final authenticated version is available online at: https://doi.org/10.1007/s00200-019-00407-w
Accepted author manuscript, 239 KB

https://arxiv.org/pdf/1803.01068

Nicolai Vorobjov
- N.N.Vorobjovbath.acuk
- Department of Computer Science - Professor
- Mathematical Foundations of Computation
Person: Research & Teaching

Cite this

@article{1e52c672c9574e86a518914eb36871f6,

title = "Complexity of deciding whether a tropical linear prevariety is a tropical variety.",

abstract = "We give an algorithm, with a singly exponential complexity, deciding whether a tropical linear prevariety is a tropical linear variety. The algorithm relies on a criterion to be a tropical linear variety in terms of a duality between the tropical orthogonalization A ⊥ and the double tropical orthogonalization A ⊥ ⊥ of a subset A of the vector space (R∪ { ∞}) n. We also give an example of a countable family of tropical hyperplanes such that their intersection is not a tropical prevariety. ",

keywords = "Tropical algebra, Computer algebra, Complexity",

author = "Dima Grigoriev and Nicolai Vorobjov",

year = "2021",

month = mar,

day = "31",

doi = "10.1007/s00200-019-00407-w",

language = "English",

volume = "32",

pages = "157--174",

journal = "Applicable Algebra in Engineering Communication and Computing",

issn = "0938-1279",

publisher = "Springer Verlag",

number = "2",

}

TY - JOUR

T1 - Complexity of deciding whether a tropical linear prevariety is a tropical variety.

AU - Grigoriev, Dima

AU - Vorobjov, Nicolai

PY - 2021/3/31

Y1 - 2021/3/31

N2 - We give an algorithm, with a singly exponential complexity, deciding whether a tropical linear prevariety is a tropical linear variety. The algorithm relies on a criterion to be a tropical linear variety in terms of a duality between the tropical orthogonalization A ⊥ and the double tropical orthogonalization A ⊥ ⊥ of a subset A of the vector space (R∪ { ∞}) n. We also give an example of a countable family of tropical hyperplanes such that their intersection is not a tropical prevariety.

AB - We give an algorithm, with a singly exponential complexity, deciding whether a tropical linear prevariety is a tropical linear variety. The algorithm relies on a criterion to be a tropical linear variety in terms of a duality between the tropical orthogonalization A ⊥ and the double tropical orthogonalization A ⊥ ⊥ of a subset A of the vector space (R∪ { ∞}) n. We also give an example of a countable family of tropical hyperplanes such that their intersection is not a tropical prevariety.

KW - Tropical algebra

KW - Computer algebra

KW - Complexity

U2 - 10.1007/s00200-019-00407-w

DO - 10.1007/s00200-019-00407-w

M3 - Article

VL - 32

SP - 157

EP - 174

JO - Applicable Algebra in Engineering Communication and Computing

JF - Applicable Algebra in Engineering Communication and Computing

SN - 0938-1279

IS - 2

ER -

Complexity of deciding whether a tropical linear prevariety is a tropical variety.

Abstract

Keywords

Access to Document

Fingerprint

Profiles

Nicolai Vorobjov

Cite this