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 time to guard against corruption and tyranny, is before they shall have gotten hold on us. It is better to keep the wolf out of the fold, than to trust to drawing his teeth and talons after he shall have entered.”
—Thomas Jefferson (1743–1826)
“Play is a major avenue for learning to manage anxiety. It gives the child a safe space where she can experiment at will, suspending the rules and constraints of physical and social reality. In play, the child becomes master rather than subject.... Play allows the child to transcend passivity and to become the active doer of what happens around her.”
—Alicia F. Lieberman (20th century)
“Others apart sat on a Hill retir’d,
In thoughts more elevate, and reason’d high
Of Providence, Foreknowledge, Will, and Fate,
Fixt Fate, free will, foreknowledge absolute,
And found no end, in wandring mazes lost.
Of good and evil much they argu’d then,
Of happiness and final misery,
Passion and Apathie, and glory and shame,
Vain wisdom all, and false Philosophie:”
—John Milton (1608–1674)