8/13/2019 Burdescu

1/9

Dabu Claudia-Maria

IS anul I

1

I ntr oduction to Complexi ty Theory

Space Complexi ty

Time and space are two of the most important considerations when we seek practicalsolutions to computational problems.

Space complexi ty shares many of the same features of time complexity.

Therefore, space complexity serves as a further way of classifying problems according totheir computational difculty .

We will continue to use the TM as our model, but now we look at the tape space itconsumes during its computation.

Space Complexity of an algorithm is total space taken by the algorithm with respect to theinput size. Space complexity includes both Auxiliary space and space used by input.

Auxiliary Space is the extra space or temporary space used by an algorithm.

Complexity classes correspond to bounds on resources.

One such resource is space: the number of tape cells a TM uses when solving a problem.

Defining complexity classes

The measure DSPACE is used to define complexity classes, sets of all of the decision problems which can be solved using a certain amount of memory space. For each function f (n),there is a complexity class SPACE( f (n)), the set of decision problems which can be solved bya deterministic Turing machine using space O( f (n)). There is no restriction on the amountof computation time which can be used, though there may be restrictions on some othercomplexity measures (like alternation).

Several important complexity classes are defined in terms of DSPACE. These include: REG = DSPACE( O(1)), where REG is the class of regular languages. In

fact, REG = DSPACE( o(log log n)) (that is, (log log n) space is required to recognizeany nonregular language).

L = DSPACE( O(log n))

8/13/2019 Burdescu

2/9

Dabu Claudia-Maria

IS anul I

2

PSPACE =

EXPSPACE =

DSPACE is traditionally measured on a deterministic Turing machine. Several important

space complexity classes are sublinear, that is, smaller than the size of the input. Thus,

"charging" the algorithm for the size of the input, or for the size of the output, would not truly

capture the memory space used. This is solved by defining the multi-string Turing machine with

input and output, which is a standard multi-tape Turing machine, except that the input tape may

never be written-to, and the output tape may never be read from. This allows smaller space

classes, such as L (logarithmic space), to be defined in terms of the amount of space used by all

of the work tapes (excluding the special input and output tapes).Since many symbols might be packed into one by taking a suitable power of the alphabet, for

all c 1 and f such that f (n) 1, the class of languages recognizable in c f (n) space is the same as

the class of languages recognizable in f (n) space. This justifies usage of big O notation in the

definition.

A complexity class is a set of problems of related complexity. Simpler complexityclasses are defined by the following factors:

The type of computational problem: The most commonly used problems are decision problems. However, complexity classes can be defined based on function problems,counting problems, optimization problems, promise problems, etc.

The model of computation: The most common model of computation is the deterministicTuring machine, but many complexity classes are based on nondeterministic Turingmachines, Boolean circuits, quantum Turing machines, monotone circuits, etc.

The resource (or resources) that are being bounded and the bounds: These two propertiesare usually stated together, such as "polynomial time", "logarithmic space", "constantdepth", etc.

Of course, some complexity classes have complex definitions that do not fit into thisframework. Thus, a typical complexity class has a definition like the following:

The set of decision problems solvable by a deterministic Turing machine within time f (n).(This complexity class is known as DTIME( f (n)).)

http://en.wikipedia.org/wiki/Sublinearhttp://en.wikipedia.org/wiki/L_(complexity)http://en.wikipedia.org/wiki/L_(complexity)http://en.wikipedia.org/wiki/L_(complexity)http://en.wikipedia.org/wiki/L_(complexity)http://en.wikipedia.org/wiki/Sublinear

8/13/2019 Burdescu

3/9

Dabu Claudia-Maria

IS anul I

3

But bounding the computation time above by some concrete function f (n) often yieldscomplexity classes that depend on the chosen machine model. For instance, the language { xx| x isany binary string} can be solved in linear time on a multi-tape Turing machine, but necessarilyrequires quadratic time in the model of single-tape Turing machines. If we allow polynomialvariations in running time, Cobham-Edmonds thesis states that "the time complexities in any tworeasonable and general models of computation are polynomially related" (Goldreich 2008,Chapter 1.2). This forms the basis for the complexity class P, which is the set of decision

problems solvable by a deterministic Turing machine within polynomial time. The correspondingset of function problems is FP.

Many important complexity classes can be defined by bounding the time or space used by thealgorithm. Some important complexity classes of decision problems defined in this manner arethe following:

Complexity class Model of computation Resource constraint

DTIME(f (n )) Deterministic Turing machine Time f (n )

P Deterministic Turing machine Time poly( n )

EXPTIME Deterministic Turing machine Time 2 poly( n )

NTIME( f (n )) Non-deterministic Turing machine Time f (n )

NP Non-deterministic Turing machine Time poly( n )

NEXPTIME Non-deterministic Turing machine Time 2 poly( n )

DSPACE( f (n )) Deterministic Turing machine Space f (n )

L Deterministic Turing machine Space O(log n )

http://en.wikipedia.org/wiki/DTIMEhttp://en.wikipedia.org/wiki/DTIMEhttp://en.wikipedia.org/wiki/DTIME

8/13/2019 Burdescu

4/9

Dabu Claudia-Maria

IS anul I

4

PSPACE Deterministic Turing machine Space poly( n )

EXPSPACE Deterministic Turing machine Space 2 poly( n )

NSPACE( f (n )) Non-deterministic Turing machine Space f (n )

NL Non-deterministic Turing machine Space O(log n )

NPSPACE Non-deterministic Turing machine Space poly( n )

NEXPSPACE Non-deterministic Turing machine Space 2 poly( n )

It turns out that PSPACE = NPSPACE and EXPSPACE = NEXPSPACE by Savitch'stheorem.

Other important complexity classes include BPP, ZPP and RP, which are definedusing probabilistic Turing machines; AC and NC, which are defined using Boolean circuits and

BQP and QMA, which are defined using quantum Turing machines. #P is an importantcomplexity class of counting problems (not decision problems). Classes like IP and AM aredefined using Interactive proof systems. ALL is the class of all decision problems.

DSPACE is traditionally measured on a deterministic Turing machine. Several importantspace complexity classes are sublinear, that is, smaller than the size of the input. Thus,"charging" the algorithm for the size of the input, or for the size of the output, would not trulycapture the memory space used. This is solved by defining the multi-string Turing machine withinput and output, which is a standard multi-tape Turing machine, except that the input tape maynever be written-to, and the output tape may never be read from. This allows smaller space

classes, such as L (logarithmic space), to be defined in terms of the amount of space used by allof the work tapes (excluding the special input and output tapes).

Since many symbols might be packed into one by taking a suitable power of the alphabet,for all c 1 and f such that f (n) 1, the class of languages recognizable in c f (n) space is thesame as the class of languages recognizable in f (n) space. This justifies usage of big Onotation in the definition.

http://en.wikipedia.org/wiki/Sublinearhttp://en.wikipedia.org/wiki/Sublinear

8/13/2019 Burdescu

5/9

Dabu Claudia-Maria

IS anul I

5

Denition:

Let M be a deterministic TM that halts on all inputs. We dene the space complexity ofM to be the function f : NN, where f(n) is the maximum number of tape cells that M scans onany input of length n. If the space complexity of M is f(n), then we also say that M runs in spacef(n). If M is a nondeterministic TM where in all branches halt on all inputs we dene its spacecomplexity f(n) to be the maximum number of tape cells that M scans on any branch of itscomputation on any input of length n.

Denition:

Let f : NR + be a function. The space complexity classes,SP ACE(f(n)) and NSPACE(f(n)), are dened as follows,

SPACE(f(n)) ={L|Lis decided by anO(f(n))space TM}

NSPACE(f(n)) ={L|L is decided by an O(f(n))space NTM}

Low Space Classes

Definitions (logarithmic space classes):

L = SPACE(logn)

NL = NSPACE(logn)

Problem!

How can a TM use only logn space if the input itself takes n cells?!

3Tape Machines

8/13/2019 Burdescu

6/9

Dabu Claudia-Maria

IS anul I

6

The model of computation we will use is a 3-tape Turing Machine. We use this model because it is easier to deal with it. We remind that any multi-tape TM can be simulated by anordinary TM with a loss of eficiency that is only polynomial. For the reminder of this lecturenotes, Turing Machine" will refer to a 3-tape Turing Machine. The 3 tapes are:

1. input tape. Read-only

2. output tape. Write-only. Usually considered unidirectional: this assumption is notessen-tial but useful. For decision problems, as considered below, one can omit the

output-tape altogether and have the decision in the machine's state.

3. work tape. Read and write. Space complexity is measured by the bounds on themachine's position on this tape.

Writing is not allowed on the input tape: this way space is measured only on theworktape.

If we allowed writing on the input tape then the length of the input itself should be takeninto account when measuring space. Thus we could only measure space complexities which areat least linear. In order to consider also sublinear space bounds we restrict the input tape to be

read-only.

Define W M (x) to be the index of the rightmost cell on the worktape scanned by M oninput x.

Define S M (n) = max |x|=n W M(x). For any language L define XL (x) so that if x L thenXL (x) = 1 otherwise XL (x) = 0.

8/13/2019 Burdescu

7/9

Dabu Claudia-Maria

IS anul I

7

Definition 4.1 (Dspace):

We may multiply s(.

) by log 2 |T M | where T M is the alphabet used by M. Otherwise, we

could always linearly compress the number of space cells using a bigger alphabet. We may alsoadd log 2(|x|) to s(

.), where x is the input. (However, this convention disallow treatment of sub-

logarithmic space,and therefore will not be done when discussing such space bounds.) This isdone in order to have a correspondence to the number of configurations.

Definition: A configuration of M is an instantaneous representation of the computationcarried on by M on a given input x. Therefore if |x|= n a configuration gives information aboutthe following:

state of M (O(1) bits)

contents of the work tape (s(n) bits)

head position in the input tape (log (n) bits)

head position in the work tape (log (s(n)) bits)

Sub-L ogarith mic Space Complexity

Working with sublogarithmic space is not so useful. One may b e tempted to think thatwhatever can be done in o(log (n)) space can also be done in constant space. Formally thiswould mean Dspace(o(log (n)))

and since obviously we may also (incorrectly) arguethat in fact

This intuition comes from the following imprecise observation: if space is not constant,machine M must determine how much space to use. Determining how much space to use seemsto require the machine counting up to at least |x|= n which needs O(log (n)) space. Therefore anyM that uses less than O(log (n)) cells, is forced to use constant space. It turns out that thisintuition is wrong and the reason is that the language itself can help in deciding how much spaceto use.

8/13/2019 Burdescu

8/9

Dabu Claudia-Maria

IS anul I

8

Going further on, we can consider Dspace (o(log log (n)) and Dspace (O(1)). We willshow that these two complexity classes are equivalent. The kind of argument used to prove theirequivalence extends the one used to prove the following simpler fact.

Theorem . For any s(n) : s(n) > log(n)

Proof: Fix an input x: | x |= n and a deterministic machine M that accepts x in space s(n).Let be C the number of possible configurations of M on input x. Then an upper bound for C is:

where Q M is the set of states of M, n is the number of possible locations of the head onthe input tape, s(n) is the number of possible locations of the head on the worktape and 2 o(s) is thenumber of possible contents in the worktape { the exponent is o(s) because the alphabet is not

necessarily binary. We can write s(n) .2o(s(n)) = 2 o(s(n)) and since s is at least logarithmic, n 2 s(n) . Otherwise, Mwill go through the same configuration at least twice, entering an infinite loop and never stop.Then necessarily M has to run in time t(n)*2 o(s) .

Theorem Dspace (o(log2log2(n)) = Dspace (O(1))

Proof: Consider a s(.) -bounded machine M on the alphabet { 0;1 }.

Claim: given input x : |x| = n such that M accepts x, then M can be on every cell on the

input tape at most k = 2 s(n) *s(n)*|Q M |= O( 2 s(n) ) times. The reason being that if M wereto be on the cell more than k times then it would be in the same configuration twice, and thusnever terminate.

We dene a semi-configuration as a configuration with the position on the input tapereplaced by the symbol at the current input tape position. For every location i on the input tape,we consider all possible semi-configurations of M when passing location i. If the sequence ofsuch configurations is C i = C 1 i,, C r i then by the above claim its length is bounded: r

8/13/2019 Burdescu

9/9

Dabu Claudia-Maria

IS anul I

9

Since s(n) = o(log 2log 2n) then and therefore there exists such

that . We then show that . Thus

Dspace (O(1)) proving the theorem.

The number of sequences of semi-configurations at any position in the input tape is