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:
“Their time past, pulled down
cracked and flung to the fire
Mgo up in a roar
All recognition lost, burnt clean
clean in the flame, the green
dispersed,”
—William Carlos Williams (1883–1963)
“In bourgeois society, the French and the industrial revolution transformed the authorization of political space. The political revolution put an end to the formalized hierarchy of the ancien regimé.... Concurrently, the industrial revolution subverted the social hierarchy upon which the old political space was based. It transformed the experience of society from one of vertical hierarchy to one of horizontal class stratification.”
—Donald M. Lowe, U.S. historian, educator. History of Bourgeois Perception, ch. 4, University of Chicago Press (1982)
“There were twa sisters sat in a bour;
Binnorie, O Binnorie!
There cam a knight to be their wooer,
By the bonnie milldams o’ Binnorie.”
—Unknown. Binnorie; or, The Two Sisters (l. 1–4)