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 almighty has never made known to any body at what time he created [the world], nor will he tell any body when he means to put an end to it, if ever he means to do it.”
—Thomas Jefferson (1743–1826)
“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)
““you were with me all day; stood with me, sat with me, talked with me, looked at me, ate with me, drank with me; and yet, your last act was to clutch for a monster, not only an innocent man, but the most pitiable of all men. So far may even the best man err, in judging the conduct of one with the recesses of whose condition he is not acquainted.””
—Herman Melville (1819–1891)