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:
“At a time when pimpery, lick-spittlery, and picking the public’s pocket are the order of the day—indeed, officially proclaimed as virtue—the poet must play the madcap to keep his balance. And ours.”
—Studs Terkel (b. 1912)
“from above, thin squeaks of radio static,
The captured fume of space foams in our ears—”
—Hart Crane (1899–1932)
“There was on old person of Fratton
Who went to church with his hat on.
“If I wake up,” he said,
“With my hat on my head,
I shall know that it hasn’t been sat on.””
—Anonymous.