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:
“So we may never
Again feel fully confident of the stratagem that bore us
And lived on a certain time after that. And it went away
Little by little, as most things do. To profit
By this mainstream is today’s chore and adventure.”
—John Ashbery (b. 1927)
“I would have broke mine eye-strings, cracked them, but
To look upon him, till the diminution
Of space had pointed him sharp as my needle;
Nay, followed him till he had melted from
The smallness of a gnat to air, and then
Have turned mine eye and wept.”
—William Shakespeare (1564–1616)
“The poor soul sat sighing by a sycamore tree,
Sing all a green willow;
Her hand on her bosom, her head on her knee,
Sing willow, willow, willow.”
—William Shakespeare (1564–1616)