All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 24 Next

Displaying 461 – 480 of 2186

Showing per page

Complexity of partial inverse assignment problem and partial inverse cut problem

Xiaoguang Yang (2001)

RAIRO - Operations Research - Recherche Opérationnelle

For a given partial solution, the partial inverse problem is to modify the coefficients such that there is a full solution containing the partial solution, while the full solution becomes optimal under new coefficients, and the total modification is minimum. In this paper, we show that the partial inverse assignment problem and the partial inverse minimum cut problem are NP-hard if there are bound constraints on the changes of coefficients.

Complexity of Partial Inverse Assignment Problem and Partial Inverse Cut Problem

Xiaoguang Yang (2010)

RAIRO - Operations Research

For a given partial solution, the partial inverse problem is to modify the coefficients such that there is a full solution containing the partial solution, while the full solution becomes optimal under new coefficients, and the total modification is minimum. In this paper, we show that the partial inverse assignment problem and the partial inverse minimum cut problem are NP-hard if there are bound constraints on the changes of coefficients.

Complexity of λ -term reductions

M. Dezani-Ciancaglini, S. Ronchi Della Rocca, L. Saitta (1979)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Complexity results for prefix grammars

Markus Lohrey, Holger Petersen (2005)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Resolving an open problem of Ravikumar and Quan, we show that equivalence of prefix grammars is complete in PSPACE. We also show that membership for these grammars is complete in P (it was known that this problem is in P) and characterize the complexity of equivalence and inclusion for monotonic grammars. For grammars with several premises we show that membership is complete in EXPTIME and hard for PSPACE for monotonic grammars.

Complexity results for prefix grammars

Markus Lohrey, Holger Petersen (2010)

RAIRO - Theoretical Informatics and Applications

Resolving an open problem of Ravikumar and Quan, we show that equivalence of prefix grammars is complete in PSPACE. We also show that membership for these grammars is complete in P (it was known that this problem is in P) and characterize the complexity of equivalence and inclusion for monotonic grammars. For grammars with several premises we show that membership is complete in EXPTIME and hard for PSPACE for monotonic grammars.

Complexity theoretical results on nondeterministic graph-driven read-once branching programs

Beate Bollig (2003)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Branching programs are a well-established computation model for boolean functions, especially read-once branching programs (BP1s) have been studied intensively. Recently two restricted nondeterministic (parity) BP1 models, called nondeterministic (parity) graph-driven BP1s and well-structured nondeterministic (parity) graph-driven BP1s, have been investigated. The consistency test for a BP-model M is the test whether a given BP is really a BP of model M . Here it is proved that the consistency test...

Complexity Theoretical Results on Nondeterministic Graph-driven Read-Once Branching Programs

Beate Bollig (2010)

RAIRO - Theoretical Informatics and Applications

Branching programs are a well-established computation model for boolean functions, especially read-once branching programs (BP1s) have been studied intensively. Recently two restricted nondeterministic (parity) BP1 models, called nondeterministic (parity) graph-driven BP1s and well-structured nondeterministic (parity) graph-driven BP1s, have been investigated. The consistency test for a BP-model M is the test whether a given BP is really a BP of model M. Here it is proved that the consistency...

Currently displaying 461 – 480 of 2186