Dynamic problems in computational complexity theory are problems stated in terms of the changing input data. In the most general form a problem in this category is usually stated as follows:
- Given a class of input objects, find efficient algorithms and data structures to answer a certain query about a set of input objects each time the input data is modified, i.e., objects are inserted or deleted.
Problems of this class have the following measures of complexity
- Memory space to store the required data structure
- Initial construction time for the data structure
- Insertion time, time required for the update of the data structure when one more input element is added
- Deletion time, time required for the update of the data structure when an input element is deleted
- Query time: time required to answer
- Other operations specific to the problem in question
The overall set of computations for a dynamic problem is called a dynamic algorithm.
Many algorithmic problems stated in terms of fixed input data (called static problems in this context and solved by static algorithms) have meaningful dynamic versions.
Online algorithms present a special case of dynamic algorithms, in which only additions of elements are allowed, possibly starting from the empty/trivial input data.
Famous quotes containing the words dynamic and/or problem:
“Knowledge about life is one thing; effective occupation of a place in life, with its dynamic currents passing through your being, is another.”
—William James (1842–1910)
“Any solution to a problem changes the problem.”
—R.W. (Richard William)