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 greatest waste of time he knew of was to count the hours—what good can come of it?—and the greatest illusion in the world, to lead one’s day by the sound of the clock, and not by precepts of common sense and understanding.”
—François Rabelais (1494–1553)
“The limitless future of childhood shrinks to realistic proportions, to one of limited chances and goals; but, by the same token, the mastery of time and space and the conquest of helplessness afford a hitherto unknown promise of self- realization. This is the human condition of adolescence.”
—Peter Blos (20th century)
“Till, in a distant town,
Towns on from mine—
I sat me down;
This was a dream.”
—Emily Dickinson (1830–1886)