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:
“Harvey: About this Voltaire.
Helene: What about him?
Harvey: How’d he ever get time to do all he did?
Helene: He lived to be old.
Harvey: Even so, how many letters did he write?
Helene: Oh, I don’t know exactly. Thousands.
Harvey: I can’t remember when I even wrote one.
Helene: You should try.
Harvey: It’s too late. I wouldn’t know where to send it.”
—Tom Waldman (d. 1985)
“For good teaching rests neither in accumulating a shelfful of knowledge nor in developing a repertoire of skills. In the end, good teaching lies in a willingness to attend and care for what happens in our students, ourselves, and the space between us. Good teaching is a certain kind of stance, I think. It is a stance of receptivity, of attunement, of listening.”
—Laurent A. Daloz (20th century)
“I saw three ships come sailing by,
Come sailing by, come sailing by,
I saw three ships come sailing by,
On Christmas Day in the morning.”
—Unknown. As I Sat on a Sunny Bank. . .
Oxford Book of Light Verse, The. W. H. Auden, ed. (1938)