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:
“This I do know and can say to you: Our country is in more danger now than at any time since the Declaration of Independence. We don’t dare follow the Lindberghs, Wheelers and Nyes, casting suspicion, sowing discord around the leadership of Franklin D. Roosevelt. We don’t want revolution among ourselves.”
—Lyndon Baines Johnson (1908–1973)
“There is commonly sufficient space about us. Our horizon is never quite at our elbows.”
—Henry David Thoreau (1817–1862)
“Most of us who turn to any subject we love remember some morning or evening hour when we got on a high stool to reach down an untried volume, or sat with parted lips listening to a new talker, or for very lack of books began to listen to the voices within, as the first traceable beginning of our love.”
—George Eliot [Mary Ann (or Marian)