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:
“For of those [cities] that were great in earlier times, most of them have now become small, while those which were great in my time were small formerly.”
—Herodotus (c. 484–424 B.C.)
“Oh, my. I’d forgotten how much I hate space travel.”
—George Lucas (b. 1944)
“They sat together halfway up a cliff
In a small niche let into it, the girl
Brightly, as if a star played on the place,
Paul darkly, like her shadow.”
—Robert Frost (1874–1963)