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 fundamental things apply
As time goes by.”
—Herman Hupfeld (1894–1951)
“It is the space inside that gives the drum its sound.”
—Hawaiian saying no. 1189, ‘lelo No’Eau, collected, translated, and annotated by Mary Kawena Pukui, Bishop Museum Press, Hawaii (1983)
“Sir Walter, being strangely surprised and put out of his countenance at so great a table, gives his son a damned blow over the face. His son, as rude as he was, would not strike his father, but strikes over the face the gentleman that sat next to him and said “Box about: ‘twill come to my father anon.””
—John Aubrey (1626–1697)