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:
“Take Time by the forelock. It is also the safest part to take a serpent by.”
—Henry David Thoreau (1817–1862)
“Though seas and land be ‘twixt us both,
Our faith and troth,
Like separated souls,
All time and space controls:
Above the highest sphere we meet
Unseen, unknown, and greet as angels greet.”
—Richard Lovelace (1618–1658)
“We [actors] are indeed a strange lot! There are times we doubt that we have any emotions we can honestly call our own. I have approached every dynamic scene change in my life the same way. When I married Charlie MacArthur, I sat down and wondered how I could play the best wife that ever was.... My love for him was the truest thing in my life; but it was still important that I love him with proper effect, that I act loving him with great style, that I achieve the ultimate in wifedom.”
—Helen Hayes (1900–1993)