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 purpose of playing, whose end, both at the first and now,
was and is, to hold as ‘twere the mirror up to nature: to show
virtue her feature, scorn her own image, and the very age and
body of the time his form and pressure.”
—William Shakespeare (1564–1616)
“The woman’s world ... is shown as a series of limited spaces, with the woman struggling to get free of them. The struggle is what the film is about; what is struggled against is the limited space itself. Consequently, to make its point, the film has to deny itself and suggest it was the struggle that was wrong, not the space.”
—Jeanine Basinger (b. 1936)
“I am a rose of Sharon, a lily of the valleys. As a lily among brambles, so is my love among maidens. As an apple tree among the trees of the wood, so is my beloved among young men. With great delight I sat in his shadow, and his fruit was sweet to my taste.”
—Bible: Hebrew, Song of Solomon 2:1-3.