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:
“It would seem that man was born a slave, and that slavery is his natural condition. At the same time nothing on earth can stop man from feeling himself born for liberty. Never, whatever may happen, can he accept servitude; for he is a thinking creature.”
—Simone Weil (1909–1943)
“This moment exhibits infinite space, but there is a space also wherein all moments are infinitely exhibited, and the everlasting duration of infinite space is another region and room of joys.”
—Thomas Traherne (1636–1674)
“a politician is an arse upon
which everyone has sat except a man.”
—E.E. (Edward Estlin)