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:
“What time has been wasted during man’s destiny in the struggle to decide what man’s next world will be like! The keener the effort to find out, the less he knew about the present one he lived in.”
—Sean O’Casey (1884–1964)
“At first thy little being came:
If nothing once, you nothing lose,
For when you die you are the same;
The space between, is but an hour,
The frail duration of a flower.”
—Philip Freneau (1752–1832)
“It was at that moment, just after Krug had fallen through the bottom of a confused dream and sat up on the straw with a gasp—and just before his reality, his remembered hideous misfortune could pounce upon him—it was then that I felt a pang of pity for Adam and slid towards him along an inclined beam of pale light—causing instantaneous madness, but at least saving him from the senseless agony of his logical fate.”
—Vladimir Nabokov (1899–1977)