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:
“Martha, your father told me something once, a long time ago, when I first started to work with him: In the war of science, many people must die before any victory can be won.”
—Robert D. Andrews, and Nick Grindé. Dr. Paul Ames (Bruce Bennett)
“I take SPACE to be the central fact to man born in America.... I spell it large because it comes large here. Large and without mercy.”
—Charles Olson (1910–1970)
“I sat in silent musing—
The soft wind waved my hair;
It told me heaven was glorious
And sleeping earth was fair.”
—Emily Brontë (1818–1848)