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:
“When a man spends his time giving his wife criticism and advice instead of compliments, he forgets that it was not his good judgment, but his charming manners, that won her heart.”
—Helen Rowland (1875–1950)
“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)
“As I sat before the fire on my fir-twig seat, without walls above or around me, I remembered how far on every hand that wilderness stretched, before you came to cleared or cultivated fields, and wondered if any bear or moose was watching the light of my fire; for Nature looked sternly upon me on account of the murder of the moose.”
—Henry David Thoreau (1817–1862)