Computational Complexity of Problems

Complexity Theory

Computational Complexity of Problems

Time complexity and space complexity

Let M be a multi-tape NTM and t a function over nonnegative integers. M is said to be t(n) time bounded if for each x in L(M), there is an accepting computation on x whose length (=the number of steps) is less than or equal to max{t(|x|), |x|+1}. Note that at least |x|+1 steps are necessary to read the whole input (and to recognize it). Also note that from the definition we need not care about those inputs which are not accepted by M.

In the literature there is another definition for time (and space, similarly) complexity in which the above underlined portion is replaced with “any accepting computation’s length on x.” Under a certain condition (constructibility of t(n)), those definitions are equivalent.

M is said to be s(n) space bounded if for each x in L(M), the maximum amount of space used on any tape at each step of some accepting computation for x is bounded by s(|x|).

By NTIME(t(n)) / DTIME(t(n)) / NSPACE(s(n)) / DSPACE(s(n)) we denote the class of languages that can be accepted by t(n) time bounded NTMs / t(n) time bounded DTMs / s(n) space bounded NTMs / s(n) space bounded DTMs. Those classes of languages are called complexity classes.

For sublinear space bounds, s(n)  n, we use the following model. An offline TM ia a multitape TM, one of whose tapes is used as the read-only input tape, where # is used as the left and right endmarkers on the input tape:

# a1 a2 …… an # read-only input tape (two-way)

q finite control

worktape 1

 s(n)

… …

worktape k

 s(n)

For superlinear space bounds, s(n)n, both TM models (offline TMs and others) define the same complexity classes.

Examples and Exercises

XcXR = {xcxR | x{a,b}*} DTIME(n+1) DSPACE(n/2+1). Show that XXR = {xxR | x{a,b}*}  NTIME(n+1)  NSPACE(n/2+1).
AnBn = {anbn | n0}DL.
HCPNP. Note that we often confuse a problem with its code under some encoding.
Show that GAPNL. GAP (graph accessability problem): Given a directed graph G and vertices s and t, determine whether or not there exists a path from s to t.

Important complexity classes

DL = {L(M) | M is an O(logn) space bounded DTM}

NL = {L(M) | M is an O(log n) space bounded NTM}

P = {L(M) | M is an O(nk) time bounded DTM for some k}

NP = {L(M) | M is an O(nk) time bounded NTM for some k}

PSPACE = {L(M) | M is an O(nk) space bounded DTM for some k}

EXP = {L(M) | M is an O(2p(n)) time bounded DTM for some polynomial p}

NEXP = {L(M) | M is an O(2p(n)) time bounded NTM for some polynomial p}

EXPSPACE = {L(M) | M is an O(2p(n)) space bounded DTM for some polynomial p}

THEOREM Linear Speedup Theorem, Linear Space Compression Theorem

(1) Suppose t(n)kn for some k>1 and any n. Then NTIME(t(n)) = NTIME(ct(n)) and DTIME(t(n)) = DTIME(ct(n)) for any constant c>0.

(2) For any function s(n), NSPACE(s(n)) = NSPACE(cs(n)) and DSPACE(s(n)) = DSPACE(cs(n)).

Thus we often use a roughly estimated upper bound, O(f(n)), instead of an exact value, f(n), as time/space complexity, where f(n)=O(g(n)) means that there exist a constant c>0 and an integer n0 such that f(n)cg(n) for all nn0.

THEOREM P=NP problem Savitch’s theorem

(1) DLNLPNPPSPACE = k0DSPACE(nk) = k0NSPACE(nk) EXPNEXPEXPSPACE…

(2) NLPSPACEEXPSPACE, PEXP, NPEXPSPACE.

(3) A deterministic time hierarchy: If t2 is a time constructible function, t1(n)t2(n) for all n, and infn[t1(n)logt1(n)]/t2(n) = 0, then DTIME(t1(n)) DTIME(t2(n)), where infnf(n) is defined to be limnh(n) with h(n) being the upper bound of {f(n),f(n+1),…}.

(4) A deterministic space hierarchy: If s1(n)n, s2(n)logn, s2(n) is a space constructible function, s1(n)s2(n) for all n, and infns1(n)/s2(n)=0, then DSPACE(s1(n)) DSPACE(s2(n)).

Relationship between type i languages and complexity classes

THEOREM NSPACE(n) = ℒ(type 1 grammar) = ℒ1.

In summary, we have the following relationship between type i grammars and various kinds of automata:

Grammar / Language / Automaton / Deterministic vs Nondet. / Complexity / Comments
Type 3 / Regular set / Finite automaton / ℒ(DFA) =
ℒ(NFA) / = DSPACE(1) / DSPACE(1)=NSPACE(1)
Type 2 / Context-free language / Pushdown automaton / ℒ(DPDA) 
ℒ(NPDA) / DTIME(n3)
 P
Type 1 / Context-sensitive language / Linear bounded automaton / ℒ(DLBA) ?
ℒ(NLBA) / = NSPACE(n) / The LBA
problem is
still open
Type 0 / Phrase-structure language / Turing machine / ℒ(DTM) =
ℒ(NTM) / Arbitrarily complex

Chomsky hierarchy: The LBA problem

ℒ3 ℒ2 ℒ1  the class of recursive sets ℒ0 ….

AnBn AnBnCn LD

LU={M#x | xL(M)}

Practically tractable / intractable problems

Usually we regard P as the class of languages (=problems) that are “practically computable.” Why P ?

 Note that even if there is an algorithm that solves a given problem P in an exponential time, the algorithm is not practical in the sense that the solutions for most instances in P cannot be obtained within realistic time (Compare polynomials, n6 for example, and exponential functions, 2n for example, where n is the size of problem, for example, the number of vertices in case of graph problems:

n6 picosecond (1 picosec=1012 sec)  less than 1 sec for n=100

2n picosec  more than 10000 years for n85 ).

 Class P is mathematically stable. For example, compositions of polynomials are polynomials again.

 Time/space complexities defined by most computation models are equivalent within polynomial factor (More precisely, let i(f(n)) be a class of languages whose complexity with respect to computation model i (i=1,2) is f(n). Then for any f(n), 1(f(n))=2(p(f(n))) for some polynomial p, and vice versa. Provides a model-independent theory of complexity.

While programs  # of times assignment statements are executed

RAM  # of times basic instructions are executed

 In most cases, there exist an encoding  and a polynomial p that satisfy |(x)|p(n) for each instance x whose size is n. For example, for graph problems such as Hamiltonian circuit problem, the size, n, of an instance (= a graph, G) is the # of vertices (or edges) while our encoding used on page 2, Handout #011, gives |G|=O(n2log n). Thus there is at most polynomial factor of difference between the actual sizes of instances and the sizes (=lengths) of their codes.

Practically intractable problems

Let L and L’ be languages (=problems). We say that L is polynomial time reducible [log-space reducible, resp.] to L’, L poly L’ [L log L’, resp.], if L m L’ via some polynomial time bounded (i.e, nk time bounded for some k) [logn space bounded] DTM M.

Lemma Let L poly L’ or L poly L’. Then, if L’ is in P / NP / PSPACE, so is L.

Proof. Suppose L poly L’ via M1 (suppose that M1 is p1(n) time bounded for some polynomial p1) and that L is in P (the proof for poly case is similar). Let M2 be a DTM accepting L. Consider the following DTM, say M. On input x, M calls M1 to compute M1(x), which can be obtained in p1(n) time (n=|x|). Then M will use M1(x) to check if M1(x) can be accepted by M2. If M2 accepts/rejects M1(x) then M accepts/reject x; M2 rejects otherwise. The time necessary to do this is bounded by p2(|M1(x)|). Since M1 is p1(n) time bounded, |M1(x)|p1(|x|)=p1(n). Therefore M is a p1(n)+p2(p1(n)) time bounded DTM and

xL  M1(x)L’, since L poly L’ via M1,

 M2 accepts M1(x), since L’=L(M2),

 M accepts x,

which means that M accepts L. Thus L is in P.

accept accept

x M1 M1(x) M2

reject reject

p1(|x|) p2(|M1(x)|)

NP-hard and NP-complete problems

Let ℒ be a class of languages. A language L is said to be ℒ-hard if L’log L holds for any L’ in ℒ (In case Pℒ, L’log L can be replaced with L’poly L). L0 is said to be ℒ-complete if it is in ℒ and it is ℒ-hard. Roughly speaking, ℒ-hard problems are those problems which are as complex as or more complex than any problems in ℒ, and ℒ-complete problems are those problems which are the most complex among problems in ℒ.

Examples of NP-complete problems

SAT (satisfiability problem for boolean formulas)

Given a logical formula, determine whether or not it is satisfiable (a logical formula f is said to be satisfiable if there is an assignment of values to the variables appearing in f such that the value of f is true under the assignment.

Hamiltonian circuit problem
Vertex cover problem: A vertex cover of a graph G=(V,E) is a set AV such that every edge, say e=(u,v), satisfies either uA or vA (e is said to be covered by u / v if uA / vA).
Independent set: Let G=(V,E) be a graph and U a subset of V. U is said to be independent if u,vU implies uvE (uv is the edge connecting u and v). Find a maximum (w.r.t. the number of vertices) independent set of G. This kind of maximization (or minimization) problem is not a decision problem. However, we can consider the following decision version of the problem: Given G and integer k, determine whether or not there is a max independet set X such that |X|k.
Clique: A clique of a graph is a complete subgraph of it. Find a maximal clique of a given graph.
3-colorability: Determine if a given graph is 3-colorable (i.e., there exists a coloring of vertices with at most 3 colors such that any pair of adjacent vertices has different colors. It is known that 2-colorability is in P and that every planar graph is 4-colorable.
Liner integer programming: Given an mn integer matrix A and an m1 integer vector b, determine if there is an n1 integer vector x satisfying Axb. If x needs not to be integer, then this problem is in P.
Set partition: Given a finite set A of integers, determine if there is BA such that xB x = x(AB) x.
Subset sum: Given a finite set A of nonnegative integers and an integer k, determine if there is BA such that xB x = k.
Zigsaw puzzel: Given polygons P1,…,Pn, determine if it is possible to arrange them so that they form a regular rectangle.
Knapsack problem: Given a napsack whose weight limit is W, n items whose weights and values are w1,…,wn and v1,…vnrespectively, find a selection of items so that they can be put in the napsack and the sum of the values of them is maximized.
Bin packing: There are enough number of bins each of whose capacity is C. Given n items whose weight are a1,…anC, determine the minimum number of bins so that all the items can be put in some of the bins.
The shortest common superstring: Given strings x1,…,xn over alphabet , find a shortest string that contains all the strings as substrings. NP-complete even if ||=2. Belongs to P if |xi|2 for each i.
Quadratic congruence: Given positive integers a,b,c, determine if there is a positive integer x<c satisfying x2a (mod b).
Given integers a,b,c, determine if ax2+by=c has a positive solution (x,y).

Thousands of problems are known to be NP-complete.

Examples of reduction among NP-complete problems

1.3-SAT is a special case of SAT: Given a 3-CNF boolean expression (a logical formulaf is said to be k-CNF if it is a conjunction (, logical and) of exactly k literals (a literal is either a logical variable or its negation), determine whether or not f is satisfiable. 3-SAT is known to be NP-complete, while 2-SAT is in P and NL-complete, and 1-SAT is in DL.

The NP-completeness of 3-SAT can be shown by proving SAT poly 3-SAT.To show that, it is necessary to give a deterministic polynomial time algorithm that produces for each boolean formula , a 3-CNF boolean formula ’ such that is satisfiable iff ’ is.Note that it is suffficient that the polynomial is a polynomial in the number of boolean variables in , since the corresponding formal algorithm that produce G from  is also bounded by a polynomial in ||, the length of the code of the instance (This observation is generally true for most cases).

2. 3-SAT poly Clique:Given a 3-CNF C1…Ck, construct the graph G as follows.Supose Ci=Li1Li2Li3, where each Lij is a literal.For each Ci, let vi1,vi2,vi3 be vertices of G.Define the edges of G so that there is an edge between vir and vjs iff ij and Lirand Lis are not the negation of each other.The algorithm to produce G from  is deterministic polynomial time bounded (in the number of boolean variables in C1…Ck)and  is satisfiable iff G has a clique such that the number of vertices of which is k.