TCS L1

Notations and Terminologies

Set and element

• Set: collection of objects.
  • is empty: contains no ele.
  • is a singleton 单集: contains only 1 ele.
  • is finite: contains finite number of eles.
  • is infinite: contains infinite number of eles.
• element / member: Objects in set.
  • $a \in A$ if $a$ is an element of the set $A$; $a \not \in A$ otherwise.
• subset: $A \sube B$ if $\forall a \in A, a \in B$
  • proper subset: $A \sube B$ and $A \not = B$
• Set Operations
  • Union $A \cup B$ / Intersection $A \cap B$
  • Complement $\overline A$
  • Powersets $2^A = \{S|S \sube A\}$
• Cartesian production:
  • $A \times B = \{(a,b)|a \in A\ and\ b \in B\}$
  • $A_1 \times A_2\times \cdots\times A_k = \{(a_1,a_2,\cdots,a_k)|a_i \in A_i\}$

Sequence

• sequence: a list of objects in some order.
• tuple: a finite sequence / k-tuple: a sequence of $k$ eles / ordered pair: 2-tuple

Relation

• relation on $k$ sets ($A_1,A_2,\cdots,A_k$): a subset of $A_1 \times A_2\times \cdots\times A_k$
• binary relation $R$ on $A\times A$ is
  • reflexive if $\forall a \in A, (a,a) \in R$
  • symmetric if $\forall (a,b) \in A\times A, \mathrm{if} (a,b) \in R\ ,\mathrm{then}\ (b,a) \in R$
  • transitive if $\forall (a,b)(b,c) \in A\times A, \mathrm{if} (a,b) \in R\ \mathrm{and}\ (b,c) \in R\ ,\mathrm{then}\ (b,a) \in R$
  • an equivalence relation: if $R$ is reflexive, symmetric and transitive.

Function

• domain $A$ / image $f(a)$ / range $f(A)$
• function $f:A \rightarrow B$ $\forall a \in A, \mathrm{uinique}\ f(a)\in B$ is
  • one-to-one / injective if $\forall a \not = a', f(a) \not = f(a')$
  • onto / surjective if $f(A) = B$
  • bijective if $f$ is one-to-one and onto.

Overview

• complexity theory: Hardness / complexity class

• automata theory: definition of problems and computing models

  • finite automata

  • pushdown automata

  • Turing automata

    church-turing thesis

• computability theory: (using turing machine)

Automata theory

Problems

Take Minimum spanning tree, MST as instance.

• Optimization problem: Given $G = (V,E,W)$, find out MST.
• Search problem: Given $G = (V,E,W), k\in \mathbb{Z}+$, find out 1 MST whose weight-sum is smaller than $k$.
• Decision problem: Given $G = (V,E,W),k \in \mathbb{Z}+$, find out whether there is a MST whose weight-sum is smaller than $k$.
• Counting problem: Given $G = (V,E,W),k \in \mathbb{Z}+$, find out the number of MSTs whose weight-sums are smaller than $k$.

It’s obvious that Optimization / Search / Counting problem is harder than Decision problem.

That’s say, if Decision is hard, then the other three is also hard.

Take Decision problem to be considered.

• problem - instance
  • yes-instance
  • no-instance

For our machine, the input $G,k$ is encoded. Then the problem could be abstracted into

Given the encodings of $G,K$, whether the code is an element of the set of the yes-instance?

A problem is uniquely decided by the set of the yes-instance, which is a Language.

$$\mathrm{Decision\ Problem} \Leftrightarrow \mathrm{Language}$$

1. $\mathrm{Decision\ Problem} \Rightarrow \mathrm{encodings\ of\ yes-instances}\Rightarrow\mathrm{Language}$
2. $\mathrm{Language} \Rightarrow \mathrm{Decision\ Problem}:\small Given\ string\ w, is\ w \in L? $

Language 是 decision problem 的数学抽象。

Language

• alphabet $\Sigma$: a finite set of symbols. e.g $\{0,1\}, \{\}$
• string $w$: a finite sequence of symbols from $\Sigma$. (duplication is allowed)
  • length of $w$: $|w| = \#symbols\ in\ w$
  • empty string $e$: $|e| = 0$ ($e$ is preserved)
• sets of string:
  • $\Sigma^i = \{w: |w| = i\}$
  • $\Sigma^* = \cup_{i>=0}\Sigma^i$
  • $\Sigma^+ = \cup_{i>0}\Sigma^i$

string operation

• concatenation:

  $u = 123, v = 456, uv = 123456$

• exponentiation:
  $w^i = ww\cdots w, w^0 = e$

• reversal:

  $w = a_1a_2\cdots c_n,w^R = a_n\cdots a_2a_1$

Language

• a language over $\Sigma$ is a subset $L \sube \Sigma^*$.
  • for $\Sigma = \{0,1\}, \empty,\Sigma^*,\{0^n1^n:n\ge 0\}$ are languages.

Finite Automata

states

• initial state $s$: >o, unique
• final state: ◎, serval

Strict definition

A finite automata $M = (K,\Sigma,\delta,s,F)$.

• $K$: a finite set of states

• $\Sigma$: input alphabet

• $s,s \in K$: initial state

• $F, F\sube K$: final states

• $\delta$ transition function：

  \delta: &K\times&\Sigma \rightarrow &K\\ &\small\small\mathrm{current\ state}&\small\small\mathrm{symbol}&\small\small\mathrm{next\ state}

  a transition function could be defined by lists. It would be better using state diagram.

configuration

A configuration is an element of $K\times\Sigma^*$, a tuple of current state and unread input symbol.

• the string read before resulted in the current state.
• the transition is decided by the current state and the symbol to read.

yields in one step

Given configuration $(q,w),(q',w')$ is yielded in one step if

$$\exist a \in \Sigma, w = aw'\ \mathrm{and}\ \delta(q,a) = q'$$