Space-time tradeoff

2013-10-25T01:39:27Z

76.7.227.224:

{{unsimple|date=July 2012}}

In [[computer science]], a '''space-time''' or '''time-memory tradeoff''' is a way of solving a problem or calculation in less time by using more storage space (or memory), or by solving a problem in very little space by spending a long time. Most computers have a large amount of space, but not infinite space. Also, most people are willing to wait a little while for a big calculation, but not forever. So if your problem is taking a long time but not much memory, a space-time tradeoff would let you use more memory and solve the problem more quickly. Or, if it could be solved very quickly but requires more memory than you have, you can try to spend more time solving the problem in the limited memory.

The most common condition is an [[algorithm]] using a [[lookup table]]. This means that the answers for some question for every possible value can be written down. One way of solving this problem is to write down the entire lookup table, which will let you find answers very quickly, but will use a lot of space. Another way is to calculate the answers without writing down anything, which uses very little space, but might take a long time.

A space-time tradeoff can be used with the problem of [[Data storage device|data storage]]. If data is stored uncompressed, it takes more space but less time than if the data were stored compressed (since compressing the data decreases the amount of space it takes, but it takes time to run the [[Data compression|compression]] [[algorithm]]).

Larger code size can be used to increase program speed when using [[loop unwinding]]. This [[technique]] makes the [[Computer program|program code]] longer for each iteration of a loop, but saves the computation time needed for jumping back to the beginning of the loop at the end of each iteration.

In the field of [[cryptography]], using space-time tradeoff, the attacker is decreasing the [[Exponential function|exponential]] time required for a [[brute force attack]]. [[Rainbow table]]s use partially precomputed values in the hash space of a [[cryptographic hash function]] to [[Cryptanalysis|crack]] [[password]]s in minutes instead of weeks. Decreasing the size of the rainbow table increases the time required to [[Iteration|iterate]] over the hash space. The [[meet-in-the-middle attack]] attack uses a space-time tradeoff to find the [[Key (cryptography)|cryptographic key]] in only <math>2^{n+1}</math> encryptions (and <math>O(2^n)</math> space) compared to the expected <math>2^{2n}</math> encryptions (but only <math>O(1)</math> space) of the normal attack.

[[Dynamic programming]] is another example where the time of solving problems can be decreased by using more memory.

==Other websites==
* [http://lasecwww.epfl.ch/pub/lasec/doc/Oech03.pdf Philippe Oechslin: Making a Faster Cryptanalytic Time-Memory Trade-Off.]
* [http://www.cs.sjsu.edu/faculty/stamp/RUA/TMTO.pdf Once Upon a Time-Memory Tradeoff.]

{{tech-stub}}

[[Category:Computer science]]

Prolog

2013-10-25T01:18:23Z

76.7.227.224:

'''Prolog''' is a [[programming language]] that uses [[first order logic]].It is the most widespread [[logic programming]] language. It is declarative. [[Alain Cormerauer]], a [[France|French]] [[computer scientist]] developed Prolog in the early 1970s. Prolog is rather different from other programming languages. It uses facts and rules. Given the facts, the rules can be used to derive new facts.

Note that Prolog uses a [[paradigm]] called [[Negation as failure]], which means that <math>\mathrm{not}~p</math> is assumed if <math>p</math> cannot be derived. This is different from true [[logical not|logical negation]]. While negation is failure has its benefits, it often confuses people starting to learn Prolog, as they expect true logical negation.

Prolog also uses [[Horn clause]]s. It is a [[Turing completeness|turing-complete]] programming language.

{{tech-stub}}
[[Category:Programming languages]]

TCS Wiki - User contributions [en]

Space-time tradeoff

Prolog