|
篇目详细内容 |
|
【篇名】 |
Complexity of comparing expressions in max-plus algebra |
|
【刊名】 |
Frontiers of Electrical and Electronic Engineering in China |
|
【刊名缩写】 |
Front. Electr. Electron. Eng. China |
|
【ISSN】 |
1673-3460 |
|
【EISSN】 |
1673-3584 |
|
【DOI】 |
10.1007/s11460-009-0055-5 |
|
【出版社】 |
Higher Education Press and Springer-Verlag |
|
【出版年】 |
2009 |
|
【卷期】 |
4
卷4期 |
|
【页码】 |
392-396
页,共
5
页 |
|
【作者】 |
Qianchuan ZHAO;
|
|
【关键词】 |
max-plus algebra; NP-hard; discrete event dynamic systems |
【摘要】 |
|
Max-plus algebra has been widely used in the study of discrete-event dynamic systems. Using max-plus algebra makes it easy to specify safety constraints on events since they can be described as a set of inequalities of state variables, i.e., firing times of relevant events. This paper proves that the problem of solving max-plus inequalities in a cube (MAXINEQ) is nondeterministic polynomial-time hard (NP-hard) in strong sense and the problem of verifying max-plus inequalities (VERMAXINEQ) is co-NP. As a corollary, the problem of solving a system of multivariate max-algebraic polynomial equalities and inequalities (MPEI) is shown to be NP-hard in strong sense. The results indicate the difficulties in comparing max-plus formulas in general. Problem structures of specific systems have to be explored to enable the development of efficient algorithms. |
