NP-complete Problems on Label Updating Calculation in ATMS
スポンサーリンク
概要
- 論文の詳細を見る
We investigate the computational complexity of the label updatingcalculation in ATMS and show that the following two decisionproblems are NP-complete.(1) The problem of deciding whether there exists a consistentenvironment calculated from a new justification for a node.(2) The problem of deciding whether there exists an environmentcalculated from a new justification for a node such that it is not asuperset of any environment in the label of the node.
- Research Association of Statistical Sciencesの論文
- 1991-03-27
Research Association of Statistical Sciences | 論文
- CLUSTERING BY A FUZZY METRIC : APPLICATIONS TO THE CLUSTER-MEDIAN PROBLEM
- A FAMILY OF REGRESSION MODELS HAVING PARTIALLY ADDITIVE AND MULTIPLICATIVE COVARIATE STRUCTURE
- AN OPTIMAL STOPPING PROBLEM ON TREE
- ON THE ORDERS OF MAX-MIN FUNCTIONALS
- TREE EXPRESSIONS AND THEIR PRODUCT FORMULA