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:
“That time I flew,”
—Emily Dickinson (1830–1886)
“In the tale proper—where there is no space for development of character or for great profusion and variety of incident—mere construction is, of course, far more imperatively demanded than in the novel.”
—Edgar Allan Poe (1809–1849)
“I sat on cushioned otter-skin:
My word was law from Ith to Emain,
And shook at Invar Amargin
The hearts of the world-troubling seamen,
And drove tumult and war away....”
—William Butler Yeats (1865–1939)