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:
“The nearer a conception comes towards finality, the nearer does the dynamic relation, out of which this concept has arisen, draw to a close. To know is to lose.”
—D.H. (David Herbert)
“Our political problem now is “Can we, as a nation, continue together permanentlyforever—half slave, and half free?” The problem is too mighty for me. May God, in his mercy, superintend the solution.”
—Abraham Lincoln (1809–1865)