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:
“The time is now propitious, as he guesses,
The meal is ended, she is bored and tired,
Endeavours to engage her in caresses
Which still are unreproved, if undesired.
Flushed and decided, he assaults at once;
Exploring hands encounter no defence;”
—T.S. (Thomas Stearns)
“Thus all our dignity lies in thought. Through it we must raise ourselves, and not through space or time, which we cannot fill. Let us endeavor, then, to think well: this is the mainspring of morality.”
—Blaise Pascal (1623–1662)
“—The man who has stood on the Acropolis,
And looked down over Attica; or he
Who has sailed where picturesque Constantinople is,
Or seen Timbuctoo, or hath taken tea
In small-eyed China’s crockery-ware metropolis,
Or sat amidst the bricks of Nineveh,
May not think much of London’s first appearance—
But ask him what he thinks of it a year hence!”
—George Gordon Noel Byron (1788–1824)