Time/space SAT Tradeoff
Currently we have no way to prove that Boolean satisfiability problem (often abbreviated as SAT), which is NP-complete, requires exponential (or at least super-polynomial) time (this is the famous P versus NP problem), or linear (or at least super-logarithmic) space to solve. However, in the context of space-time tradeoff, one can prove that SAT cannot be computed if we apply constraints to both time and space. L. Fortnow, Lipton, D. van Melkebeek, and A. Viglas proved that SAT cannot be computed by a Turing machine that takes at most O steps and at most O cells of its read-write tapes.
Read more about this topic: Richard J. Lipton
Famous quotes containing the words time, space and/or sat:
“Genius is talent provided with ideals. Genius starves while talent wears purple and fine linen. The man of genius of today will in fifty years’ time be in most cases no more than a man of talent.”
—Somerset Maugham (1874–1965)
“Even the most subjected person has moments of rage and resentment so intense that they respond, they act against. There is an inner uprising that leads to rebellion, however short- lived. It may be only momentary but it takes place. That space within oneself where resistance is possible remains.”
—bell hooks (b. c. 1955)
“The poor soul sat sighing by a sycamore tree,
Sing all a green willow;
Her hand on her bosom, her head on her knee,
Sing willow, willow, willow.”
—William Shakespeare (1564–1616)