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:
“Imagination is always the fabric of social life and the dynamic of history. The influence of real needs and compulsions, of real interests and materials, is indirect because the crowd is never conscious of it.”
—Simone Weil (1909–1943)
“It is part of the educator’s responsibility to see equally to two things: First, that the problem grows out of the conditions of the experience being had in the present, and that it is within the range of the capacity of students; and, secondly, that it is such that it arouses in the learner an active quest for information and for production of new ideas. The new facts and new ideas thus obtained become the ground for further experiences in which new problems are presented.”
—John Dewey (1859–1952)