What are some basic mathematical definitions, notations and introductions needed for computational complexity theory formalism understanding?

by EITCA Academy / Sunday, 11 May 2025 / Published in Cybersecurity, EITC/IS/CCTF Computational Complexity Theory Fundamentals, Introduction, Theoretical introduction

Computational complexity theory is a foundational area of theoretical computer science that rigorously investigates the resources required to solve computational problems. A precise understanding of its formalism necessitates acquaintance with several core mathematical definitions, notations, and conceptual frameworks. These provide the language and tools necessary to articulate, analyze, and compare the computational difficulty of problems and the efficiency of algorithms.

1. Sets, Functions, and Relations

Sets

A set is a well-defined collection of distinct objects, called elements. In complexity theory, sets often represent collections of strings, numbers, or states. The standard notation for a set is uppercase letters, such as $S$ or $A$ . For example, $\Sigma$ commonly denotes an alphabet—a finite set of symbols.

– Example: If $\Sigma = \{0, 1\}$ , then the set of all binary strings of length 3 is $\Sigma^3 = \{000, 001, 010, 011, 100, 101, 110, 111\}$ .

Functions

A function $f: A \to B$ assigns to every element $a \in A$ exactly one element $b \in B$ . Functions are fundamental for describing algorithms, transformations, and complexity measures.

– Example: The function $f(n) = 2^n$ maps natural numbers to their respective powers of two.

Relations

A relation $R \subseteq A \times B$ is a subset of the Cartesian product of sets $A$ and $B$ . In the context of languages and decision problems, relations often describe the mapping between inputs and their associated outputs or certificates.

2. Alphabets, Strings, and Languages

Alphabet and Strings

An alphabet $\Sigma$ is a finite, non-empty set of symbols. A string over $\Sigma$ is a finite sequence of symbols from $\Sigma$ . The set of all strings over $\Sigma$ is denoted $\Sigma^*$ , where $*$ represents the Kleene star operation.

– Example: For $\Sigma = \{a, b\}$ , $abbab$ is a string in $\Sigma^*$ .

Languages

A language $L$ over $\Sigma$ is any subset of $\Sigma^*$ . In computational complexity, languages represent decision problems: for a string $x \in \Sigma^*$ , the question is whether $x \in L$ .

– Example: The language $L = \{ w \in \{0,1\}^* : w$ contains an even number of zeros $\}$ .

3. Decision Problems and Computational Models

Decision Problems

A decision problem asks a yes/no question about an input. Formally, it corresponds to a language $L \subseteq \Sigma^*$ : “Given $x$ , is $x \in L$ ?”

– Example: "Given a graph $G$ , does $G$ have a Hamiltonian cycle?" is a decision problem.

Computational Models

Complexity theory formalizes computation using abstract machines. The most prominent is the Turing machine.

– Turing Machine (TM): An abstract model defined by a finite set of states, an infinite tape divided into cells, a tape head, and a transition function. A deterministic Turing machine (DTM) has a single transition for each state-symbol pair; a nondeterministic Turing machine (NTM) may have multiple transitions.

4. Asymptotic Notation

Asymptotic notation describes the limiting behavior of functions, important for expressing the resource usage (time, space) of algorithms as input size grows.

Big O Notation

– Definition: $f(n) = O(g(n))$ if there exist constants $c > 0$ and $n_0$ such that for all $n \geq n_0$ , $|f(n)| \leq c \cdot |g(n)|$ .
– Interpretation: $f(n)$ grows no faster than $g(n)$ up to constant multiples for large $n$ .

– Example: $3n^2 + 2n + 1 = O(n^2)$ .

Omega and Theta Notations

– Big Omega ( $\Omega$ ): $f(n) = \Omega(g(n))$ if for some $c, n_0$ , $f(n) \geq c \cdot g(n)$ for all $n \geq n_0$ .
– Big Theta ( $\Theta$ ): $f(n) = \Theta(g(n))$ if $f(n) = O(g(n))$ and $f(n) = \Omega(g(n))$ .

These notations enable formal comparison of algorithmic efficiency.

5. Complexity Measures

Time Complexity

Describes the number of computational steps (e.g., transitions of a Turing machine) required as a function of input size $n$ .

– Notation: $T(n)$ or $f(n)$ for time taken on inputs of length $n$ .

Space Complexity

Describes the amount of memory (tape cells used) as a function of input size.

– Notation: $S(n)$ .

The resource bounds are typically considered in the asymptotic sense, for large input sizes.

6. Complexity Classes

Complexity classes group languages (problems) according to the resources needed to decide them.

P (Polynomial Time)

– Definition: The class of languages decidable by a deterministic Turing machine in polynomial time.
– Formalization: $P = \bigcup_{k \geq 1} \mathrm{DTIME}(n^k)$ .
– Example: Sorting a list, checking if a number is prime.

NP (Nondeterministic Polynomial Time)

– Definition: The class of languages for which a solution can be verified in polynomial time by a deterministic Turing machine, or equivalently, decided by a nondeterministic Turing machine in polynomial time.
– Formalization: $NP = \bigcup_{k \geq 1} \mathrm{NTIME}(n^k)$ .
– Example: Satisfiability (SAT), Hamiltonian cycle.

Other Classes

– PSPACE: Languages decidable in polynomial space.
– EXPTIME: Languages decidable in exponential time.

7. Reductions

Reductions are mappings from one problem to another, demonstrating relative computational difficulty.

Many-One Reduction ( $\leq_m$ )

A language $A$ is many-one reducible to $B$ ( $A \leq_m B$ ) if there exists a computable function $f$ such that $x \in A \iff f(x) \in B$ .

– Purpose: If $B$ is easy, and $A \leq_m B$ , then $A$ is at most as hard as $B$ .

Polynomial-Time Reduction ( $\leq_p$ )

A polynomial-time computable reduction is used for comparing problems within $P$ and $NP$ . If $f$ is computable in polynomial time, and $x \in A \iff f(x) \in B$ , then $A \leq_p B$ .

8. NP-Completeness

A problem is NP-complete if:
1. It is in $NP$ .
2. Every problem in $NP$ is polynomial-time reducible to it.

Notation: $L$ is NP-complete if $L \in NP$ and $\forall L' \in NP, L' \leq_p L$ .

– Example: The SAT problem is the canonical NP-complete problem.

9. Decision vs. Search Problems

While decision problems ask yes/no questions, search problems require finding an explicit solution. Complexity theory often focuses on decision problems, but search problems are closely related, particularly in cryptography and algorithm design.

10. Formal Language Theory

Complexity theory leverages formal language theory to represent and analyze problems.

– Regular languages: Recognized by finite automata.
– Context-free languages: Recognized by pushdown automata.
– Recursive (decidable) and recursively enumerable (semi-decidable) languages: Recognized by Turing machines with or without halting guarantees.

11. Notation for Turing Machines

A Turing machine $M$ is specified by a tuple $(Q, \Sigma, \Gamma, \delta, q_0, q_a, q_r)$ , where:

– $Q$ : Finite set of states
– $\Sigma$ : Input alphabet (does not include blank symbol)
– $\Gamma$ : Tape alphabet ( $\Sigma \subseteq \Gamma$ ), includes blank symbol
– $\delta$ : Transition function
– $q_0$ : Start state
– $q_a$ : Accept state
– $q_r$ : Reject state

The computation of $M$ on input $w$ is denoted $M(w)$ .

12. Input Size

The length of the input, denoted $n$ , is measured as $|x|$ , the number of symbols in the input string $x$ . All complexity measures (time, space) are expressed as functions of $n$ .

13. Universal Turing Machine

A universal Turing machine $U$ can simulate any Turing machine $M$ on input $w$ , given a description $\langle M \rangle$ and $w$ . This forms the theoretical basis for the Church-Turing thesis.

14. Certificates and Verifiers

For $NP$ problems, a verifier is a deterministic Turing machine $V$ such that for any input $x$ , there exists a certificate $y$ (with $|y|$ polynomial in $|x|$ ) satisfying $V(x, y) = 1$ if and only if $x$ is a "yes" instance.

– Example: For SAT, the certificate is a satisfying assignment.

15. Randomized Complexity Classes

– RP (Randomized Polynomial Time): Problems for which a probabilistic Turing machine can decide membership with one-sided error in polynomial time.
– BPP (Bounded-error Probabilistic Polynomial Time): Problems for which a probabilistic Turing machine can decide membership with two-sided error in polynomial time.

16. Oracle Machines

An oracle Turing machine has access to an "oracle" that instantly decides membership in a fixed language $A$ . This concept is used to study relative computability and separations between classes.

17. Hierarchy Theorems

Hierarchy theorems formalize the idea that more resources allow for the solution of more problems.

– Time Hierarchy Theorem: There exist problems solvable in more time but not less.
– Space Hierarchy Theorem: Analogous statement for space.

18. Completeness and Hardness

– Hardness: A problem $L$ is $C$ -hard if every problem in class $C$ reduces to $L$ .
– Completeness: $L$ is $C$ -complete if $L \in C$ and $L$ is $C$ -hard.

19. Boolean Circuits

Boolean circuits model computation as acyclic networks of logical gates. Circuit complexity studies the size (number of gates) and depth (levels of gates) needed to compute functions.

20. Encoding and Representation

All objects (Turing machines, graphs, formulas) must be encoded as strings over a finite alphabet for analysis within complexity theory. Standard encodings ensure uniform treatment and comparability of problems and algorithms.

—

Mastery of these definitions and formal notations is necessary for a precise and rigorous understanding of computational complexity theory. These formal tools underpin the classification of computational problems, the design and analysis of algorithms, and the study of cryptographic security assumptions.

EITCA Academy

LOG IN TO YOUR ACCOUNT

FORGOT YOUR PASSWORD?

CREATE AN ACCOUNT