Problem Classification
Please use this window for displaying the computational complexity of
the currently chosen Problem Type (according
to the so-called 3-field notation).
This classification is performed by an analyisof a BibTeX database
(file classify.bib)
which is based on the collection of complexity results for scheduling
problems, see Complexity
results of scheduling problems.
How to come here:
Make sure that you have defined a
Problem Type.
Choose the menu entry
Extras|Problem Classification.
Output in the problem classification window:
- Statement which tells you if the problem is
- polynomially solvable,
- pseudo-polynomially solvable,
- NP-hard,
- NP-hard in the strong sense or
- open.
- If the complexity of the considered problem is known then
you will find a short form of the corresponding references proving the
the stated complexity.
- For displaying the corresponding complete references, please choos
the button Complete References.
Table of Contents
Date 28.10.99, MH