Logic & Set TheoryLógica y Teoría de Conjuntos
P vs NP.
Turing Machines and Complexity Classes. P vs NP asymmetry.
0. Index.
-
Introduction: Algorithms and Time Complexity.
-
1.1. Algorithms.
-
1.2. Time complexity.
-
-
Solving problems and verifying solutions.
-
2.1. Problems.
-
2.2. Definitions. Languages, Decisions Problems, N/DTMs and Time in TMs.
-
2.2.1. Languages.
-
2.2.2. Decisions Problems and Languages.
-
2.2.3. Turing Machines.
-
2.2.4. Build a Turing machine that accepts a string and increments the number of a's within the string.
-
2.2.5. Time in Turing Machines. Configurations and Computations.
-
2.2.6. Time of a Language: Solvable problems.
-
2.2.7. Time Complexity. Big-O. Efficient algorithms.
-
-
-
Complexity classes: P, NP and PSPACE. PvsNP problem.
-
3.1 Certificate/verifier characterization of NP. Verification.
-
3.1.1 Deterministic conception of NP.
-
3.1.2. Formalizing the witness encoding.
-
3.1.3. Generalizating V as a verifier of L.
-
3.1.4. Caracterization of NP. NP deterministic approach.
-
-
3.2. P class: Efficiently solvable problems. Witness.
-
3.3. Problems in PSPACE: Not all problems have solutions that can be efficiently verified.
-
3.3.1. Space-bounded Turing Machines.
-
3.3.2. Space-problems example.
-
-
3.4. NP. Problems that can be quickly verified but not quickly computed.
-
3.5. Explanation of PvsNP.
-
1. Introduction: Algorithms and Time Complexity.
1.1. Algorithms.
An algorithm is a finite sequence of well-defined instructions that transforms an input into an output and satisfies the following three properties:
- Definiteness: Each step has exactly one interpretation.
- Finiteness: Must terminate after a finite number of steps, not loop infinitely.
- Effectiveness: Steps are basic enough to be carried out by a computing agent.
The following is an example of an algorithm:
Greater Common Divisor
By definition, the greatest common divisor of two natural numbers a and b (notated as \(gcd(a,b)\)), is the greatest natural that divides those two numbers, this is:
\[g = gcd(a,b) \iff g \in \mathbb{N^*} \ : \begin{cases} \ g | a \land g | b \\ \ \nexists \ d \in \mathbb{N^*} : d | a , d | b \land d > g \end{cases}\]Note that this is a straightforward definition, but a universal and unambiguous declaration would also be:
\[g = gcd(a,b)\ \Longleftrightarrow\ g \in \mathbb{N}^{*}:\ (g \mid a \wedge g \mid b)\ \wedge\ \forall d \in \mathbb{N}^{*}\big((d \mid a \wedge d \mid b)\Rightarrow d \leq g\big)\](We are just saying that for any other integer, being a common divisor of \(a\) and \(b\) implies being smaller than or equal to \(g\))
Let's consider \(a,b \in \mathbb{N^*}\) (we can safely assume that is \(a>b\), otherwise \(gcd(a,b) = gcd(a,a) = a\)). Then:
\[\exists (q_1,r_1) \in \mathbb{N^2}: a = bq_1 + r_1 \ \land \ b>r_1 \geq 0\]For this same reason, it's also true that:
\[\exists (q_2,r_2) \in \mathbb{N}^2 : b = r_1q_2 + r_2 \ \land \ b > r_1 > r_2 >=0\]Aware that this process is finite, the sequence \(b, r_1, r_2\), and so on are strictly positive and decremental, this means that \(\exists \ n : r_n = 0\).
Since this is just an approach, we are not going to demonstrate the generic case, although it is also easy to extrapolate from a concrete case. Let's suppose that \(r_3 = 0\), thus we would have:
\[a = b·q_1 + r_1 = (r_1·q_2 + r_2)q_1 + r_1 = [(r_2·q_3 + \cancel{r_3})q_2 + r_2]q_1 + r_2·q_3 + \cancel{r_3} = r_2·(q_3q_2q_1 + q_1 + q_3)\]Thus, that \(a \vert r_2\) and also is evident that \(b \vert r_2\) so this number meets the first condition.
Also, consider from above that every divisor of \(a\) and \(b\) is also divisor of the remainder:
\[\forall d \in \mathbb{Z} : d | a \land d | b \implies d | (a \ \% \ b)\]So, as also happens that if we call \(r_1 = a \ \% \ b\):
\[d | (a \ \% \ b) \implies d | (b \ \% \ r_1)\]This means that the first remainder which also complies to be a divisor of a pair \((a,b) \in \mathbb{N}^2\) is in fact the greatest common divisor since every other divisor of this pair also divides it for being his reminder.
In formal terms, being \((a,b) \in \mathbb{N^*} \times \mathbb{N^*} : a \geq b\), we define the reminder sequence as:
Then, \(\exists! \ n \in \mathbb{N} : (r_n \neq 0 \ \land \ r_{n+1} = 0) \implies r_n =gcd(a,b)\)
Then, if there are \((a,b) \in \mathbb{N^2} : a \geq b > 0\), in order to get the \(gcd(a,b)\) we can make a computing agent to follow a finite sequence of instructions to return the \(gcd(a,b)\):
int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
This is an algorithm: we get two values a and b and calculate the remainder; if this is not zero, then we calculate the remainder between the second operand of the modulo operation and the last calculated remainder.
We continue this way until the remainder is 0; this would mean that, as we saw in the demonstration above, the last calculated remainder (kept in a) is \(gcd(a,b)\).
1.2. Time complexity.
The example above shows in a clear way that algorithms are structures, finite sequences of instructions, which aim to automate large repetitive tasks; in some way they are time-saving machines.
Here we introduce a very important parameter, the time that it takes the algorithm to return an output from a given input. This is known as the time complexity problem.
Returning to the gcd() function shown above, given two integers, how much time it would require for the algorithm to return an output is related to how many times the while loop would iterate. In each iteration \(r_1 = a \ \% \ b\) gets computed and then shift the value \((a, b) → (b, r_1)\). So, when the sequence would end depends on how fast the \(b\) operand on \(a \ \% \ b\) operation would decrease.
Note that after two consecutive iterations, the \(b\) value will decrease by at least \(a/2\), so after \(2k\) iterations: \(min \ value ≤ b / 2^k\), then the iterations would terminate when \(2^k > b \iff k > log₂(b)\), thus total iterations \(k\) is a function of the logarithm of the minimum value of the \((a,b)\) pair: \(k(a,b) = \mathcal{O}(log(min(a, b)))\).
This means that the number of iterations that it will take the algorithm to finish depends on a logarithmic function of the minimum value of the pair, which means that these iterations grow slowly as the size of the integer grows:
| Complexity | Name | Growth rate |
|---|---|---|
| O(1) | Constant Time | Instant |
| O(log n) | Logarithmic Time | Very slow growth |
| O(n) | Linear Time | Proportional |
| O(n²) | Quadratic/Polynomial Time | Fast growth |
| O(2ⁿ) | Exponential | Explodes |
An algorithm runs in polynomial time when its execution time can be bounded by some polynomial function of the input size. We say an algorithm takes polynomial time if it runs in \(\mathcal{O}(n^c)\) time or faster, where \(n\) is the size of the input and \(c\) is a non-negative constant. We may refer to algorithms that run in polynomial time or faster as efficient algorithms because their running time doesn’t grow too quickly with the input size.
2. Solving problems and verifying solutions.
2.1. Problems.
Intimately attached to the idea of algorithms are the questions that algorithms are prepared to solve. We define the term problem as a specification of what we want to compute, this is; what is to be solved by an algorithm implemented on a Turing machine (we can think of this as a computing agent that can follow instructions and execute operations based on a language).
Formally, a problem is a relation that maps an input to a set of valid outputs; the algorithm is a set of instructions that a computing agent processes to go from the input to an acceptable output.
There are many types of problems we can encounter:
- Search Problems: Where the output is a concrete solution like "find all the possible divisors of 'n'".
- Optimization Problems: Output is the best possible solution, "the shortest path between two nodes".
- Decision Problems: Where the output maps over a boolean value (YES/NO, TRUE/FALSE, 1/0), "Is number 'p' prime".
For all we care about, we are going to focus on decision problems.
2.2. Definitions. Languages, Decisions Problems, N/DTMs and Time in TMs.
2.2.1. Languages.
Let's formalize the concept of a decision problem, we already said that a problem is a relation between inputs and outputs. Let's take some definitions:
-
An alphabet is a finite nonempty set of symbols, usually referred to as \(\Sigma\). For example, consider:
\[\Sigma = \{0, 1\}\] -
We also consider the set \(\Sigma^*\) of all possible strings of symbols of \(\Sigma\) (including the empty string \(\epsilon\)). This way, the set of all possible "binary numbers" would be:
\[\Sigma^* = \{0,1\}^* = \{\epsilon,0,1,10,11,110,111,1110,1111,...\}\]Considering \(x \in \Sigma^*\) we define as the length of \(x \text { as } \vert x \vert \in \mathbb{N}\); as the number of symbols \(\sigma \in \Sigma\) that constitutes that string.
-
According to this definitions, we define as a language; \(L\) over the alphabet \(\Sigma\) to any subset of \(\Sigma^*\); \(L \subseteq \Sigma^*\).
2.2.2. Decisions Problems and Languages.
A decision problem (as used in complexity) can be formalized as a Boolean-valued function on strings, with two valid outputs; NO or YES:
\[\Pi : \Sigma^{*} \to \{0,1\}\]Associated with the previous decision problem is the subset of \(\Sigma^*\) (language) of those elements which maps through \(\Pi\) to a YES.
\[L_{\Pi} = \{x \in \Sigma^* \ | \ \ \Pi(x)= 1\} \subseteq \Sigma^*\]Observe that this way, we have reduced the problem solution to language membership question.
Also, observe that for any given language \(L \subseteq \Sigma\), we can define an associated decision problem \(\Pi\) as:
\[\Pi_{L}(x)= \begin{cases} 1 & \text{if } x \in L\\ 0 & \text{if } x \notin L \end{cases} \ : \ x \in \Sigma^*\]Being:
\[L = \{ x \in \Sigma^* \ | \ \Pi_L(x) =1 \}\]This essentially means that any decision problem identifies itself with a language and we can talk indiscriminately about decision problems or languages. In these terms, solving a decision problem is equivalent to finding a reliable decider of a certain language.
2.2.3. Turing Machines.
A good way to think about a Turing Machine, \(TM\) is as a mathematical abstraction of an algorithm, a formal definition of a computable function.
A (single-tape) Turing Machine consists of:
-
An infinite tape divided into cells (memory).
-
A tape head that at any moment scans exactly one cell and operates (read, write or move) on it.
-
A finite control unit which contains internal information divided in a finite amount of pieces, called "states".
-
A deterministic rule telling it what to do next based only on:
-
The current state.
-
The symbol currently under the head.
-
Computation is discrete: one transition per step.
The following diagram shows a representation of what we are talking about:
Finite Control Unit (states Q)
┌──────────────────────────────────┐
│ current state: q │
│ deterministic rule: │
│ δ(q, σ) = (q', b, R) │
└─────────────┬────────────────────┘
│ depends on (current state, symbol under "head")
│
▼
(Infinite Tape) … | σ | a | σ | σ | b | σ | σ | a | σ | σ | b | c | c | a | …
▲
│
┌─────┴───────────┐
│ Tape Head │
│ scans 1 cell │
│ read / write │
│ move Left/Right │
└─────────────────┘
We will come back to this diagram when the components gets explained and acquire full meaning.
For now, think of a Turing Machine as an abstract computing agent that manipulates symbols step by step on an unbounded tape.
Conceptually, it behaves as if it were executing an algorithm: at each step it consults a finite set of rules and updates its state and the tape accordingly, until a task is resolved. (It is worth mentioning that the conception of the algorithm as if it were an external, separate entity from the computational model is wrong and is only included for pedagogical purposes; the algorithm is the TM itself, or said in other words, any algorithm is a concrete instance of a Turing Machine).
A deterministic Turing Machine is a 7-tuple
\[M = (Q, \Sigma, \Gamma, \delta, q_0, q_{\mathrm{acc}}, q_{\mathrm{rej}})\]Where:
-
\(Q\) is a finite, nonempty set of states, including the initial state: \(q_0\).
We will see later what a state is in depth; for now, we can say that a state is a finite piece of internal information that \(M\) uses to make decisions about the next move.
-
\(\Sigma\) is the input alphabet.
-
\(\Gamma\) is the tape alphabet which includes a special symbol, \(\square \in \Gamma\) which basically refers to an empty cell in the tape.
\[\Sigma \subseteq \Gamma \ \ \land \ \ \square \notin \Sigma\]The reason why we distinguish between two alphabets is, besides the need of the empty cell conception \(\square\), because remember that \(M\) is the model of an algorithm, which receives an input and transforms it to an output, thus there can be symbols in the output which cannot be part of the input.
Essentially, \(\Gamma\) is the set of all possible symbols which can be written on the tape, a subset of this one is \(\Sigma\), only the part of \(\Gamma\) that can be part of the input and not of the output.
-
The transition function:
\[\delta : \bigl(Q \setminus \{q_{\mathrm{acc}}, q_{\mathrm{rej}}\}\bigr)\times \Gamma \to Q \times \Gamma \times \{L,R\}\] \[\delta(q_p,\gamma_q) = \ (q_m, \gamma_n, D)\]Intuitively, the transition function specifies the next state transited from the current state, which symbol to overwrite the current symbol pointed by the head, and the next head movement (shift).
Where:
- \(q_{\mathrm{acc}}\): Is the accepted state.
- \(q_{\mathrm{rej}}\): Is the rejected state.
Thus, let's develop the concepts above more precisely.
-
The \(Q\) set or set of states, is also called; Finite Control Unit.
When an algorithm transforms an input to an output it performs operations in one or more steps. A state is the abstraction of one of those steps for the Turing Machine in the sense that it is used to decide what to do next when the tape head reads the tape symbol.
This abstraction consists in a parameter \(q \in Q\), which is known as a Control Mode, that, in combination with a tape symbol \(\gamma \in \Gamma\), gets associated by \(\delta\) function as a pair \((q, \gamma) \in Q \times \Gamma\) to a 3-uple \(\delta(q,\gamma)\) which is another pair plus a movement (a shift \(L/R\)) to another cell in the tape. We will get into \(\delta\) soon, for now lets say that \(q\) is a fundamental parameter used to decide which step to take next in the computation chain.
So, \(\delta(q,\gamma) = (q',\gamma',D)\) gets read as: for state \(q\) if \(\gamma\) is read, then writes \(\gamma'\) on the tape, moves the head one cell in direction \(D\) and enter state \(q'\).
Note that \(q_{\mathrm{acc}}, q_{\mathrm{rej}}\) are both excluded from the domain of \(\delta\) meaning that those states have no transition, they are the end of the sequence in \(M\).
In summary, as we said before, these are small pieces of information which \(M\) uses to make decisions about the next move along with other factors.
-
Input alphabet \(\Sigma\), these are the symbols you allow in the input string, what \(M\) receives as input is a string from \(w \in \Sigma^*\).
-
Tape alphabet \(\Gamma\), symbols that may appear on the tape during computation. It contains the input alphabet (because the input is written on the tape initially), but it can be larger because you may need work symbols / markers or the "blank" symbol, \(\square\).
-
Transition function \(\delta\), this is the computational part of \(M\). For each pair \((q,a)\) of current state \(q\) and scanned symbol \(a\) there is at most one next action (and in the standard definition: exactly one, unless \(q\) is halting (\(q_{\mathrm{acc}}, q_{\mathrm{rej}}\)).
A value:
\[\delta(q,a) = (q', b, D)\]means:
-
If you are in state \(q\) scanning symbol \(a\).
DIAGRAM A — “Read” (the configuration that determines δ’s input) Finite Control Unit (states Q) ┌──────────────────────────────────┐ │ current state: q │ │ δ takes input from: │ │ (q, a) │ └─────────────┬────────────────────┘ │ │ a = symbol currently under head ▼ (Infinite Tape) … | σ | σ | a | σ | σ | … ▲ │ ┌────┴──────┐ │ Tape Head │ │ reads: a │ └───────────┘ -
Write symbol \(b\) in the current cell.
DIAGRAM B — “Apply δ” (computing the unique next action) Finite Control Unit (states Q) ┌──────────────────────────────────┐ │ current state: q │ │ scanned symbol: a │ │ │ │ δ(q, a) = (q', b, D) │ └─────────────┬────────────────────┘ │ │ next state + write symbol + move dir ▼ OUTPUTS next state: q' write: b move: D ∈ {L, R} DIAGRAM C — “Write” (overwrite the scanned cell with b) Finite Control Unit (states Q) ┌────────────────────────────────┐ │ δ(q, a) = (q', b, D) │ │ action step: WRITE b │ └─────────────┬──────────────────┘ │ ▼ (Infinite Tape) … | σ | σ | b | σ | σ | … ▲ │ ┌────┴──────┐ │ Tape Head │ │ wrote: b │ └───────────┘ -
Move the head one step in direction \(D \in \{L,R\}\).
DIAGRAM D — “Move Right” (D = R, head shifts one cell to the right) Finite Control Unit (states Q) ┌──────────────────────────────────┐ │ δ(q, a) = (q', b, R) │ │ action step: MOVE RIGHT │ └─────────────────┬────────────────┘ │ ▼ (Infinite Tape) … | σ | σ | b | σ | σ | … │ ▲ │ │ (was here) └── head after move ┌────────────────────────────────┐ │ Tape Head now scans next cell │ └────────────────────────────────┘ DIAGRAM E — “Move Left” (D = L, head shifts one cell to the left) Finite Control Unit (states Q) ┌──────────────────────────────────┐ │ δ(q, a) = (q', b, L) │ │ action step: MOVE LEFT │ └──────────┬───────────────────────┘ │ ▼ (Infinite Tape) … | σ | σ | b | σ | σ | … ▲ │ │ │ head after mov └──── (was here) ┌────────────────────────────────┐ │ Tape Head now scans prev cell │ └────────────────────────────────┘ -
Change state to \(q'\).
Diagram F — “State Update” (complete the transition: new configuration) Finite Control Unit (states Q) ┌──────────────────────────────────┐ │ BEFORE: state = q │ │ δ(q, a) = (q', b, D) │ │ current state = q' │ └─────────────┬────────────────────┘ │ │ configuration after one step: │ (new state, updated tape, moved head)
-
Before ending, it is worth making the distinction between Non-Deterministic Turing Machines; \(NTM\), and Deterministic Turing Machines; \(DTM\).
The difference between those two is that in NTMs, \(\delta\) is a relation, which means that for each input, the output is a subset of the codomain with the possibility that it is greater than one:
\[x \in X, \ y = \delta(x) \subset Y: \ |\delta(x)| \leq |Y|\]where \(\vert \delta(x) \vert\) is \(\delta(x)\)'s cardinality (the number of elements of the set).
While in DTM, \(\delta\) is a function (a partial function to be accurate), which is a restricted subset of the relations. It means that for each input of the domain \(x \in X\), \(\delta\) maps at most (because it could be zero elements to map; partial) with one output
\[y = \delta(x) \subset Y : |\delta(x) | \leq 1\]To consolidate the concepts, let's take an exercise:
2.2.4. Build a Turing machine that accepts a string and increments the number of a's within the string.
We remember that a Turing Machine, \(M\), is defined as a 7-tuple: \(M = (Q, \Sigma, \Gamma, \delta, q_0, q_{acc}, q_{rej})\). These are the entities we have to define.
First, based on what we know about a Turing machine and how it works, let's think conceptually about how \(M\) will work.
-
The machine starts in a state \(q_0\), in which the string is represented on the tape. The tape head is located above the first letter.
Finite Control Unit (states Q) ┌──────────────────────────────────┐ │ current state: q_0 │ │ action step: read first cell │ └────────────┬─────────────────────┘ │ ▼ (Infinite Tape) … | | | h | o | l | a | | | … -
The mechanism consists of, whenever it encounters a non-empty symbol, writing the same letter that already exists on the tape in the box, moving to the right, and assigning the state \(q_0\).
Finite Control Unit (states Q) ┌───────────────────────────────────┐ │ current state: q_0 │ │ READ: symbol, h (not blank) │ │ action step: │ │ writes 'h', assigns q_0, move R │ └────────────┬──────────────────────┘ │ R ▼ > ▼ (next cell to read) (Infinite Tape) … | | | h | o | l | a | | | … Finite Control Unit (states Q) ┌───────────────────────────────────┐ │ current state: q_0 │ │ READ: symbol, o (not blank) │ │ action step: │ │ writes 'o', assigns q_0, move R │ └─────────────────┬─────────────────┘ │ R ▼ > ▼ (next cell to read) (Infinite Tape) … | | | h | o | l | a | | | … [...] -
When the tape head finds an empty cell, it writes an \(a\), changes the state to \(q_{acc}\) and moves to the right.
Finite Control Unit (states Q) ┌────────────────────────────────────┐ │ current state: q_0 │ │ READ: symbol, " " (blank) │ │ action step: │ │ writes 'a', assigns q_acc, move R │ └────────────────┬───────────────────┘ │ ▼ > ▼ (next cell to read) (Infinite Tape) … | o | l | a | | | | | | … Finite Control Unit (states Q) ┌──────────────────────────────────────┐ │ current state: q_acc (HALT, SUCCESS) │ │ READ: symbol, " " (blank) │ │ action step: - │ │ (q_acc, no action defined) │ └────────────────────┬─────────────────┘ │ ▼ (Infinite Tape) … | o | l | a | a | | | | | …
Thus, according to our model, we define the following elements:
- \[Q = \{q_0, q_{\mathrm{acc}},q_{\mathrm{rej}}\}\]
- \(\Sigma = \{h,o,l,a\}\), \(\Sigma^*=\{\epsilon,h,hh,ho,hola,la,a,...\}\)
- \[\Gamma = \{\square\} \bigcup \ \Sigma\]
- \(\delta : \bigl(Q \setminus \{q_{\mathrm{acc}}, q_{\mathrm{rej}}\}\bigr)\times \Gamma \to Q \times \Gamma \times \{L, R\}\) satisfying:
2.2.5. Time in Turing Machines. Configurations and Computations.
For a \(M \in DTM\), we define time as the number of discrete transition steps (a computation) that \(M\) performs before it halts. Relative to a problem, time-solving always refers to the number of steps that \(M\) requires for solving the problem or, in other words, the maximum transition steps (worst-case number) that it would take to solve the problem.
Let \(M\) be a DTM with \(\delta\) his transition function. Let's now fix a conventional input encoding:
- Input \(x \in \Sigma^*\) is written on the tape (or input tape) initially.
- The head starts at the leftmost symbol of \(x\).
- The rest of the tape is blank.
- Computation proceeds by repeatedly applying \(\delta\), one application is equal to one transition step.
Then, we define as a configuration the 3-upla \(C = (q, t, i)\), where:
- \(q \in Q\),
- \(i \in \mathbb{Z}\) refers to the head-tape position,
-
\(t: \mathbb{Z} \to \Gamma\), is the tape-content function. Observe that, with this convention, \(t(i)\) is the tape-symbol of the cell being pointed by the head-tape of \(M\). We consider the set of all the tape-content function as \(T_M\).
Note also that whenever a transition takes place in which the tape gets written, \(t\) function gets modified. For example let's say \(x = h\). Then by the convention it would be:
\[t: \mathbb{Z} \to \Gamma\]\(t(i) = \ \begin{cases} \ \square \ \ \ \ \ \forall i \in \mathbb{Z} \setminus\{0\} \\ \ h \ \ \ \ \ \ \text{ if } \ i = 0 \end{cases}\)
Now, a transition step takes place and write \(a\), then \(t\) goes to \(t'\), where:
\[t': \mathbb{Z} \to \Gamma\] \[t'(i) = \ \begin{cases} \ \square \ \ \ \ \ \ \ \ \ \forall i \in \mathbb{Z} \setminus\{0,1\} \\ \ t(i) \ \ \ \ \ \ \text{ if } \ i = 0 \\ \ a \ \ \ \ \ \ \ \ \ \ \text{ if } \ i = 1 \end{cases}\]This tape-content function acts kind as a log of the symbols present in the tape in a static snapshot of \(M\) in a precise moment.
In this context, we read \(C_i(x)\) as the \(i\)-th configuration of \(M\) processing \(x\); it is an abstraction of a snapshot of the relevant features of \(M\) (these are the state, the tape and the head-tape). We also consider \(\Omega_x\) as the set of all the possible 3-uples \(C(x)\).
Being \(C_i(x) = (q, t, n), \ C_j(x) = (q',t',m) \in \Omega_x\), then we define the following one-step transition relation; \(\vdash_{M} \ \subseteq \ \Omega_x \times \Omega_x\) such as:
\[C_i(x) \vdash_{M} C_j(x) \iff \delta(q,t(n)) = (q',t'(m-1), R) \ \vee \ \delta(q,t(n)) = (q',t'(m+1), L)\ : \ D \in \{L,R\}\]This means basically that two configurations are sequential if they are immediate transitional steps through \(\delta\) in the processing of the \(x\) input. If this condition is met, then the effects of \(\delta\) over the \(C_i\) configuration must be reachable by the \(C_j\) configuration in concrete, well-defined terms.
Consider for example (let's conveniently overlook that in this particular case \(n=0\) in order to illustrate the relation shown above):
C_i = (q, t, n)
Finite Control Unit (states Q)
┌───────────────────────────────────┐
│ current state: q │
│ READ: t(n) = h │
│ action step: │
│ writes 'j', assigns q', move R │
└────────────┬──────────────────────┘
│
▼
(Infinite Tape) … | | | h | o | l | a | | | …
C_j = (q',t', m)
Finite Control Unit (states Q)
┌───────────────────────────────────┐
│ current state: q' │
│ READ: t'(m) = o │
│ action step: │
│ ... │
└────────────────┬──────────────────┘
│
▼
(Infinite Tape) … | | | j | o | l | a | | | …
t'(m - 1) = d(t(n)) = j
from a state \(q\) and a current tape symbol \(t(n)\), then \(M\) writes the symbol referenced by \(t'(m)\) and goes to \(q'\), then \(C_i(x)\) and \(C_j(x)\) are sequential.
Having the following scheme, the computation of \(x\) by \(M\) is a finite sequence of configurations,
\[C_{0}(x)\ \vdash_{M}\ C_{1}(x)\ \vdash_{M}\ \cdots\ \vdash_{M}\ C_{p}(x) \ \iff \ C_{0}(x)\ \vdash_{M}^{\,p}\ C_{p}(x)\ : p \in \mathbb{N}\]where \(C_0(x)\) is the initial configuration, \(\vdash_{M}\) is the “one-step yields” relation, and \(C_t(x)\) is halting, this is usually expressed as \(C_t(x) = (q_{acc}/q_{rej},t,n): t \in T_M, n \in \mathbb{Z}\).
A little parenthesis: for a given input \(x \in \Sigma^*\), we usually say that:
\[M \text{ accepts } x \iff \exists ! p \in \mathbb{N} : C_{0}(x)\ \vdash_{M}^{\,p}\ C_{p}(x)\ \land \ C_{p}(x) = (q_{acc},t,n)\] \[M \text{ rejects } x \ \iff \exists ! p \in \mathbb{N} : C_{0}(x)\ \vdash_{M}^{\,p}\ C_{p}(x)\ \land \ C_{p}(x) = (q_{rej},t,n)\]This is, if there exists a finite computation by \(M\) which ends either in the \(q_{acc}\) or \(q_{rej}\) states. Note that for DTMs, \(p\) necessarily has to be unique; we will discuss this matter later, after a time definition.
Then, we define two measures of time for DTMs. First, we introduce the time that \(M\) takes to process a given input \(x \in X\):
\[\mathrm{Time}_{M}(x)=\min\{\,p\in\mathbb{N} : C_{0}(x)\ \vdash_{M}^{\,p}\ C_{p}(x)\ \land \ C_{p}(x) = (q,t,n) : q \in \{q_{acc}, q_{rej}\}\}\]Essentially it is the size (in transition steps) of the smallest computation path of \(x\) by \(M\).
Now we extend this concept to the worst-case scenario; consider, for any input \(x \in \Sigma^*\) of size \(n\), the largest time that \(M\) takes to process it:
\[t_{M}(n)=\max\{\,\mathrm{Time}_{M}(x) : |x|=n\}\]Observe that in this case, we are considering the worst-case scenario, the upper limit of all the possible times. This last definition is what we call the time of \(M\) as an algorithm. So in summary, we understand the time that an algorithm takes to solve a problem as the number of steps (abstracted in the chain of configurations of a DTM) that it needs to compute an input of a determined size \(n\).
Until here, we defined time for DTMs, we can extend this concept to NTMs.
As a brief reminder, the DTM's main feature is that \(\delta\) is a partial function, so there is only one "transition" for a given state and symbol; this means that there is only one unique configuration that follows from a given non-halting one:
\[M \in DTM \Rightarrow \forall C = (q,t,n) : q \in Q \setminus \{q_{\mathrm{acc}},q_{rej}\} \ \exists! \ D : C \vdash_{M}D\]since each \(D\) is unique, is easy to see that at the end this process lies in a unique computation (which besides is the only existent computation) for each input \(x\) by \(M\):
\[M \in DTM \Rightarrow \forall x\, \forall p\, \forall C\, \forall D\ \bigl(C_{0}(x)\ \vdash_{M}^{\,p}\ C\ \wedge\ C_{0}(x)\ \vdash_{M}^{\,p}\ D\ \Rightarrow\ C=D\bigr)\]In contrast, in NTMs \(\delta\) is a relation, not a function, which means that can have one or more "one-step transition" configuration for a given configuration, this means that \(D\) is no longer unique:
\[M \in NTM \Rightarrow \forall C = (q,t,n) : q \in Q \setminus \{q_{\mathrm{acc}},q_{rej}\} \ \exists D : C \vdash_{M} D\]Then, relative to NTMs, we no longer talk about "computation paths" (understand it as single chains of configuration steps as we saw before) but about branches of chains of configurations, making the computation of a given input look like a tree, instead of a single path:
\[\begin{cases} C \vdash_{M} C_1 \begin{cases} C_1 \vdash_{M} C_{11} \ \ ...\\ C_1 \vdash_{M} C_{12} \ \ ...\\ ... \\ C_1 \vdash_{M} C_{13}\ \ ...\end{cases} \\ C \vdash_{M} C_2 \begin{cases} C_2 \vdash_{M} C_{21} \ \ ...\\ C_2 \vdash_{M} C_{22} \ \ ...\\ ... \\ C_2 \vdash_{M} C_{23} \ \ ...\end{cases} \\ ... \\ C \vdash_{M} C_m \begin{cases} C_m \vdash_{M} C_{m1}\ \ ... \\ C_m \vdash_{M} C_{m2} \ \ ...\\ ... \\ C_m \vdash_{M} C_{m3} \ \ ...\end{cases} \end{cases}\]In the nondeterministic case, the notation \(C_0 \vdash_{M}C_p\) is referring to the tree, not a branch in the tree. Also, in the present notes the \(C_0(x) \vdash^p_{M}C_p(x)\) notation can be read as; there exists a computation branch of length \(p\) from \(C_0\) to \(C_p\).
Then we define for \(M \in NTM\):
-
Acceptance (NTM); if there exists at least one halting-branch ending in \(q_{acc}\):
\[M \text{ accepts } x \iff \exists p \in \mathbb{N} : C_{0}(x)\ \vdash_{M}^{\,p}\ C_{p}(x)\ \land \ C_{p}(x) = (q_{acc},t,n)\] -
Rejects (NTM); if all branches that halt end in \(q_{rej}\), or, equivalently, if no branch halts in \(q_{acc}\):
\[M \text{ rejects } x \ \iff \ \nexists p \in \mathbb{N} : C_{0}(x)\ \vdash_{M}^{\,p}\ C_{p}(x)\ \land \ C_{p}(x) = (q_{acc},t,n)\]
Thus, for NTMs, the time is a bit more complex than for DTMs, starting with the fact that we distinguish two time conceptions:
-
On one hand, if \(x\) is accepted then it makes sense to consider the accepting time as the number of transitional steps in the shortest accepting branch:
\[\mathrm{AccTime}_{M}(x)=\min\{\,p\in\mathbb{N} : C_{0}(x)\ \vdash_{M}^{\,p}\ C_{p}(x)\ \land \ C_{p}(x) = (q_{acc},t,n)\}\] -
But there is a more general and realistic concept of time for NTMs, universal over branches, which considers the number of steps of the largest branch (without considering whether it halts or not):
\[\mathrm{Time}_{M}(x)=\max\{\,p\in\mathbb{N} : C_{0}(x)\ \vdash_{M}^{\,p}\ C_{p}(x)\}\]Equivalently, the depth of the computation tree; no upper bound case is considered (the time may be \(\infty\)). This is the standard definition. Associate with it is the worst-case input-length definition:
\[t_{M}(n)=\max\{\,\mathrm{Time}_{M}(x) : x\in\Sigma^{*},\ |x|=n\,\}\]
2.2.6. Time of a Language: Solvable problems.
Now that we covered foundational material about Turing Machines, let's see how this structure fits in our conception of decision problems.
As a reminder, we were saying that a decision problem over an alphabet \(\Sigma\) can be understood as a Boolean function \(\Pi: \Sigma^* \to \Set{0,1}\) whose solution eventually lands over a language:
\[L_{\Pi} = \Set{x|\Pi(x)=1} \subseteq \Sigma^*\]This way, solving \(\Pi\) becomes deciding the membership of \(L_\Pi\), which could be decided by a Turing Machine. That is the formal connection: a decision problem is (identified with) a language and a TM solves it by being a decider for that very language.
Let \(M \in TM\) over an alphabet \(\Sigma\), then we say that \(M\) decides \(L \subseteq \Sigma^*\) when:
\[M \text{ accepts } x \iff x \in L \ \ \land \ \ M \text{ rejects } x \iff x \notin L\]We say that \(\Pi\) is solvable or has a solution if \(\exists M \in DTM: M \text{ decides } L_\Pi\) (if there exists a Turing Machine that decides its solution); we consider the set
\[M_\Pi = \Set{ M | M \text{ decides } L_\Pi} \subseteq DTM\]With this terms, we can also give a more accurate conception about what \(\Pi(x) = 1\) means;
\[\Pi(x) = 1 \iff \exists M \in M_\Pi : M_\Pi \text{ accepts } x\]This definition, despite being redundant since it doesn't include any new concept, is more human-friendly because we are just saying that for a decision problem, a given input is part of the solution whenever there exists a mechanism (a Turing machine mapping the solution of the problem) which accepts this input.
\[L_{\Pi} = \{x \in \Sigma^* \ | \ \exists M \in M_\Pi : M_\Pi \text{ accepts } x\}\]Let's observe one thing. Although we consider multiple Turing machines that could solve a concrete problem \(\Pi\), \(L_\Pi\) does not depend on the Turing machine selected as long as this Turing machine belongs to \(M_\Pi\). Consider for example \(N,M \in M_\Pi\) and consider the language
\[L_i = \{x \ | \ i \text{ accepts } x \} \subseteq \Sigma^*\]for \(i \in TM\).
Then it is:
\[x \in L_N \iff N \text{ accepts } x \iff \Pi(x) = 1 \iff M \text { accepts } x \iff x \in L_M\]so
\[\forall N,M \in M_\Pi \ \ \ L_N = L_M = L_\Pi\]This basically means that no matter what TM we consider, all of them map \(L_\Pi\) equally since all refer to the \(\Pi\) criteria.
We end saying that we define the resolution-time of a decision problem \(\Pi\) over an alphabet \(\Sigma\) as
\[T_{\Pi}(n)=\inf_{M\in\mathcal{M}_{\Pi}} t_{M}(n)\]It is worth noting that all the time definitions we provided are not fixed values; they depend on the input size; \(\vert x \vert\). How the value of this time grows as the length of the input grows is a subject called Time Complexity, and it will be discussed in the next section.
2.2.7. Time Complexity. Big-O. Efficient algorithms.
Until here, we have a step-count model; \(\mathrm{Time}_{M}(x)\), and the induced worst-case length function time; \(t_M(n)\), and ultimately we defined the time associated with a decision problem as the fastest length function time of the set of the length function time from the turing machines that decides the language associated to that problem \(T_{\Pi}(n)\).
Now, we want to discuss the upper asymptotic growth of those functions as \(n\to \infty\), which is also called the time complexity subject. We remember briefly that: an asymptote is a line or curve that a function's graph approaches infinitely closely but never touches or crosses as the graph heads toward infinity (or negative infinity).
Big-O notation is a mathematical notation that describes the approximate size of a function on a domain, specifically, Big-O describe an asymptotic upper bound behaviour which is perfect for the time complexity question.
Being \(f,g: \mathbb{N} \to \mathbb{R_+}\) then:
\[f(n)\in \mathcal{O}(g(n))\ \Longleftrightarrow\ \exists c>0,\ \exists n_{0}\in\mathbb{N},\ \forall n\ge n_{0}:\ f(n)\le c\,g(n)\]This is as far from some point \(n_0\) on the domain; \(f\) is bounded above by a constant multiple of \(g\), meaning that \(f\) grows no faster than \(g\) (up to constants). The \(f\)'s upper behavior is enveloped over the one of a model function \(g\).
Let's observe that this does not mean that \(f\) and \(g\) behave the same (which would be reasonable to think since we are going to use this notation to refer to time functions; "\(f\) belongs to a family of functions that behave as \(g\)" is what we would be inclined to imagine when describing a time function in relation to another). In fact, again, we are not defining the behaviour of \(f\), but its upper asymptotic behavior at some point in the domain, which is being described through a model function \(g\) up to constant factors. Also note that no asymptotes are required; that's just nomenclature, it is just upper behaviour.
This basically means that from a certain point in the domain, \(f\) is at most as big as a multiple of \(g\).
| Name (informal) | Typical bound (\(t(n)\in\mathcal O(\cdot)\)) | What it means (intuition) | Canonical example(s) |
|---|---|---|---|
| Constant | \((1)\) | Time does not scale with | Array index access (RAM model), fixed-size checks |
| Logarithmic | \(log \ n\) | Each step shrinks problem size by a constant factor | Binary search; balanced BST search |
| Polylogarithmic | \((log \ n)^k\) | Slightly more than logarithmic | Some advanced data structure ops; certain graph queries |
| Sublinear | \(n^\alpha \ : \ 0<\alpha<1\) | Reads/uses only a fraction of the input (often not possible if you must inspect all input) | Property testing (probabilistic), sampling-based algorithms |
| Linear | \(n\) | Proportional to input length | Single pass scan; counting; verification passes |
| Linearithmic | \(n · log \ n\) | “Divide-and-conquer + linear combine” pattern | Merge sort, heap sort; many FFT-like routines |
| Polynomial (general) | \(n^k : k\ge 1\) | Considered “efficient/tractable” in complexity theory | Many classic deterministic algorithms; defines (\mathbf P) |
| Exponential | \(c^n : c>1\) | Branching search; scales very poorly | Brute-force SAT assignment search; subset enumeration |
| Factorial | \(n!\) | Enumerating permutations | Traveling Salesman brute force; permutation search |
We say that an algorithm runs in a concrete time if it is in the Big-\(\mathcal{O}\) family of the prototype function of that set (note also that there is an inclusion relation between those sets; \(\mathcal{O}(1) \subset \mathcal{O}(log \ n) \subset ... \subset \mathcal{O}(n^k)\)).
Cobham’s thesis asserts that a computational problem is feasibly/efficiently solvable iff it has an algorithm that runs in polynomial time in the length of the input, often referred to as a tractable problem. Thus, for all we are concerned with, we distinguish two types of algorithms; those which run in polynomial time or less, which solve "tractable" problems, and those which run in super-polynomial time.
Note that we refer to Cobham's assertion as a thesis and not a theorem because it is not a theorem; it is a design choice that turned out to be unusually robust.
3. Complexity classes: P, NP and PSPACE. PvsNP problem.
A complexity class is a set of decision problems (languages) that are solvable within a specified resource budget, typically:
-
time (number of steps),
-
space (number of tape cells used),
measured as a function of the input length \(n = \vert x \vert\).
Let's consider the following two sets. For a function \(T:\mathbb{N} \to \mathbb{N}\):
\[DTIME(T(n)) = \{L \subseteq \Sigma^* \ | \ \exists M \in DTM: \big( M \ decides \ L \land \ t_M(n) \in \mathcal{O}(T(n))\big) \}\] \[NTIME(T(n)) = \{L \subseteq \Sigma^* \ | \ \exists M \in NTM: \big( M \ decides \ L \land \ t_M(n) \in \mathcal{O}(T(n))\big) \}\]These are basically the classes of those languages for which there exists, respectively, a deterministic and a non-deterministic Turing machine which decides it in \(T(n)\) time.
Then, we define:
-
\(\mathbf{P}=\displaystyle\bigcup_{k\ge 1}\mathrm{DTIME}(n^{k})\). The class of the languages that can be deterministically decided in polynomial time. This is, that exists a DTM that can decide, for a given input \(x\), if it is \(x \in L\) or \(x \notin L\).
-
\(\mathbf{NP}=\displaystyle\bigcup_{k\ge 1}\mathrm{NTIME}(n^{k})\); which is the class of the languages for which there exists a non-deterministic Turing machine that decides it in polynomial time.
Note that, in this context, if we apply the identification of decision problems with languages, we are just talking about those problems for which there exist, respectively, deterministic and non-deterministic time-efficient solutions. Note that \(P \subseteq NP\).
3.1 Certificate/verifier characterization of NP. Verification.
3.1.1 Deterministic conception of NP.
At this point, “efficient” is being used relative to the underlying machine model: in \(P\) the efficiency bound is measured along the unique deterministic computation, whereas in \(NP\) it is measured along computation branches of a nondeterministic machine.
The relation between these two notions of efficiency is not immediate, because nondeterminism is a theoretical construct rather than a direct physical assumption about how computation is executed. This motivates the distinction between the abstract models (DTM/NTM) and implementable computation, and explains how this leads to a deterministic conception of NP languages as the class of those languages for which there exists a polynomial-time "verification".
Let's remember acceptance in NTMs. Being \(M \in NTM\), then \(M\) accepts \(x_0 \in \Sigma^*\) if there exists at least one branch in the computation halting in \(q_{acc}\):
\[M \text{ accepts } x_0 \iff \exists p \in \mathbb{N} : C_{0}(x_0)\ \vdash_{M}^{\,p}\ C_{p}(x_0)\ \land \ C_{p}(x_0) = (q_{acc},t,n)\]Consider as \(c_0: C_{0}(x_0)\ \vdash_{M}\ C_{1}(x_0) \vdash_{M} ... \vdash_{M} C_p(x_0)\) to this single configuration chain. And if we consider \(t_M(n) \in \mathcal{O}(n^k) : k \geq 1\), then we can consider the existence of:
\[V_{x_0} \in DTM :C_{0}(x_0)\ \vdash_{V_{x_0}}^{\,p}\ C_{p}(x_0)\ \land \forall i <p \ \big(C_{i}(x_0)\ \vdash_{V_{x_0}}^\ C_{i+1}(x_0) = C_{i}(x_0)\ \vdash_{M}^\ C_{i+1}(x_0) \in c_0\big)\]This basically means a deterministic algorithm computing \(x_0\) through the accepting computation branch of the non-deterministic Turing machine.
Let's observe that from the definition of \(V_{x_0}\), the following statements immediately follow:
-
Let's consider \(w_0\) a codification of the following statement:
\[C_{0}(x_0)\ \vdash_{V_{x_0}}^{\,p}\ C_{p}(x_0)\ \land \forall i <p \ \big(C_{i}(x_0)\ \vdash_{V_{x_0}}^\ C_{i+1}(x_0) = C_{i}(x_0)\ \vdash_{M}^\ C_{i+1}(x_0)\big)\]such as \(V_{x_0}(x_0,w_0) = 1 \iff C_{p}(x_0) = (q_{acc},t,n)\), then
\[M \text{ accepts } x_0 \iff \exists w_0:V_{x_0}(x_0,w_0)=1\]And it also has an immediate corollary; if \(M\) is a decider of \(L \subseteq \Sigma^*\), then:
\[x_0 \in L \iff \exists w: V_{x_0}(x_0,w_0)=1\] -
For \(V\) as is described before is: \(\ Time_V(x_0) \in \mathcal{O}(n^k) : k \geq 1\)
From the definition is known that: \(\mathrm{Time}_{V_{x_0}}(x_0) = AccTime_M(x_0) \leq t_M(n) \in \mathcal{O}(n^k) \ \Rightarrow \ \mathrm{Time}_{V}(x_0) \in \mathcal{O}(n^k)\), so \(V_{x_0}\) computes \(x_0\) in polynomial time.
We refer to \(w_0\) as the witness and \(V_{x_0}\) as the verifier of the pair \((x_0,w_0)\).
We can think of \(w_0\) as a piece of encoded information about how a deterministic Turing machine (\(V_{x_0}\)) has to compute the specific \(x_0 \in \Sigma^*\) input to obtain a halt-accepted configuration \(C_p\) equivalent to the one reached by \(M \in NTM\).
3.1.2. Formalizing the witness encoding.
Let's now formally nail down the formulation of \(w_0\).
We can reformulate what we understand as an accepting branch for \(x_0\) like a finite sequence of configurations:
\[c_0 = (C_0,C_1,...,C_p): C_0 = C_0(x_0) \ \land \ C_p = (q_{acc},t,n) \ \land \ C_i \vdash_{M} C_{i+1} \ \ \forall i < p\]Then, from this point, we can define a witness as an encoding of this accepting branch in a string of symbols of the input alphabet of \(M\), \(w_0 = enc(c_0) \in \Sigma^*\). Let's observe that, as a string of symbols, this witness is only encoding a path in the computation tree of \(M\), a sequence of nondeterministic choices.
Since we are considering \(M\) as a decider NTM, then infinite branches are out of scope and we can consider, for any given computation, the set of the successors from a departing configuration:
\[Succ(C) = \{D : C \vdash_{M} D\} : |Succ(C)| \leq b \in \mathbb{N}\]observe we can fix this set to consider the deterministic ordering of successors for each C:
\[Succ(C) = (D_{C,1},D_{C,2},...,D_{C,m_C}):1\leq m_C \leq b\]Now, given a branch like \(c_0 = (C_0,...,C_p)\), define its choice sequence as the set: \(choice(c_0) = (a_0,...,a_{p-1})\) where each \(a_i \in {0,...,b}\) is an index such that \(C_{i+1} = D_{C_i,a_i}\), an identifier for each deterministic successor in the branch.
So essentially, we are providing a deterministic methodology for mapping the branch \(c_0\): as in \(Succ(D_c)\) choose \(a_1\) which leads to \(D_{C,1} = C_1\); now for \(Succ(D_{C_1})\) choose \(a_2\) which will lead to \(D_{C,2} = C_2\) and so on. Now, let's find a way to encode this information in the witness \(w\).
Considering the alphabet \(\{0,1\}\), we define \(w_0 \in \{0,1\}^*\). Since the \(a_i\), as described before, are just natural numbers, we can encode them in binary and conceive:
\[w_0 := \mathrm{enc}(\pi) = \mathrm{bin}_{m}(a_{0})\,\mathrm{bin}_{m}(a_{1})\cdots \mathrm{bin}_{m}(a_{p-1}) \in \{0,1\}^{mp},\]This way, without entering into details, \(w\) is a string of \(m=log_2b\) length blocks of bits encoding the \(a_i\) numbers. Thus, a deterministic TM could be crafted to do:
- Start at \(C_0(x)\).
- At step \(i\), read the \(i\)-th block \(bin_m(a_i)\) from \(w_0\). If \(a_i > m_{C_i}\) reject, otherwise, \(C_{i+1} := D_{C_i,a_i}\)
- Continue up to at most \(T(\vert x \vert)\) steps and accept iff an accepting configuration is reached.
So we have demonstrated that \(w\) is a piece of encoded information polynomially bounded in \(\vert x \vert\).
3.1.3. Generalizating V as a verifier of L.
At this point, we have a strong conception for \(w_0\), but we only conceived \(V_{x_0}\) and \(w_0\) as a mechanism specific to a given input, \(x_0\). Let's now formalize this idea for a language \(L\).
Since \(w_0\) departs from an accepting branch \(c_0\) in the computation tree of \(x_0 \in \Sigma^*\) by \(M\) and \(V_{x_0}\) is a deterministic mechanism that computes \(x_0\) using \(c_0\) following \(w_0\), we can now consider a generic case of \(V_{x_0}\) for a language \(L \subseteq \Sigma^*\).
Considering a \(L\subseteq \Sigma^*\) and \(M \in NTM: M \ decides \ L\). Then we can consider \(x \in L\) and \(c\) the accepting-halting branch of the computation \(C_{0}(x)\ \vdash_{M}^{\,p}\ C_{p}(x)\).
Then we define \(V \in DTM\) in a manner that guarantees a finite computation of \(x\) following the non-deterministic choices of \(C_{0}(x)\ \vdash_{M}^{\,p}\ C_{p}(x)\) to ultimately reach the same accepted-halt configuration \(C_p\).
Formally \(V\), as defined above, satisfies:
\[\forall x \in L \ \exists p \in \mathbb{N} : \Big(C_{0}(x)\ \vdash_{V}^{\,p}\ C_{p}(x)\ \land \forall i <p \ \big(C_{i}(x)\ \vdash_{V_{x_0}}^\ C_{i+1}(x) = C_{i}(x)\ \vdash_{M}^\ C_{i+1}(x) \in c\big)\Big)\]In these terms, encoding \(c\) in \(w\) as seen before, we also define:
\[V(x,w) = 1 \iff C_p = (q_{acc},t,n)\]and reformulate the characterization of \(V\) as:
\[\forall x \in L \ \exists w : |w| \in \mathcal{O}(|x|^k) \ \land \ V(x,w) = 1\]The \(\vert w \vert \in \mathcal{O}(\vert x \vert^k)\) condition means that the encoding uses a reasonable amount of space resources.
And ultimately we can say that \(V\) is a verifier of \(L\):
\[\forall x\in \Sigma^* \ \big( x\in L \iff \exists w : |w| \in \mathcal{O}(|x|^k) \ \land \ V(x,w) = 1 \big)\]Observe that also is:
\[x \notin L \ \iff \ \forall w\ \bigl(|w|\le p(|x|)\ \Rightarrow\ V(x,w)=0\bigr)\]It is worth noting that \(t_M(n) \in \mathcal{O}(f(n)) \Rightarrow t_V(n) \in \mathcal{O}(f(n))\) since we are referring to computations built from non-deterministic choices.
Informally, we can say that a verifier is kind of a decider with some aid.
3.1.4. Characterization of NP. NP deterministic approach.
Reaching this point, having understood that, for a non-deterministic machine, we can always think about a deterministic machine that can compute a set of nondeterministic choices reaching the same accepting-halted configuration for a given input with the aid of encoded information, we can now present a deterministic conception of \(NP\) as the class of the languages that can be verified in polynomial time.
First of all, we've already seen that for a language \(L \subseteq \Sigma^*\) and \(M \in NTM\) exists \(V \in DTM\) that acts as a verifier for \(L\) running in the same time that \(M\) if \(t_M(n) \in \mathcal{O}(n^k)\), so fixing \(t_M(n) \in \mathcal{O}(n^k)\) we can say that any \(L \in NP\) has a verifier running in polynomial time.
Also, considering \(L\) a language that has a verifier \(V\) running in polynomial time, then we can consider an \(M \in NTM\) also running in polynomial time that has one branch which reproduces the deterministic path of \(V\) for any \(x \in L\). Then \(M\) becomes a decider of \(L\) and \(L \in NP\).
These two approaches, despite lacking formalization and being poorly accurate, are enough to see that it is not difficult to imagine the equivalence between those two classes once the idea of the verifier and the witness are formally understood. Then, \(NP\) can be considered as the class of those languages for which there exists a verifier which runs in polynomial time.
Thus, essentially we have:
-
\(\mathbf{P}=\displaystyle\bigcup_{k\ge 1}\mathrm{DTIME}(n^{k})\). The class of the languages that can be deterministically decided in polynomial time. This is, that exists a DTM that can decide, for a given input \(x\), if it is \(x \in L\) or \(x \notin L\).
-
\(\mathbf{NP}= \{ \ L \ \vert \ \forall x \ \big( x\in L \iff \exists w : \vert w \vert \in \mathcal{O}(\vert x \vert^k) \ \land \ V(x,w) = 1 \big)\}\); which is the class of the languages that can be verified in polynomial time.
3.2. P class: Efficiently solvable problems. Witness.
Let's review some examples for \(P\) class:
-
Sorting a list: we can efficiently sort a list in \(\mathcal{O}(n·log(n))\) with mergesort; check that \(log(n) < n\) for any base bigger than 1, so \(n·log(n) <n^2\) and this is indeed a polynomial-time algorithm. Also, we can efficiently verify that a list is sorted in \(\mathcal{O}(n)\).
-
Returning the index of a number in a list, if it occurs in the list: Taking a given list, we can sort it in \(\mathcal{O}(n)\) time, while checking if a given number of the list is in a position is immediate, \(\mathcal{O}(1)\).
-
Determining if two nodes in a graph are connected: We can efficiently determine if two nodes in a graph are connected by using breadth-first search; start at a node, then visit all of its neighbors except nodes we’ve already visited, then search the neighbors of the neighbors, and so forth. Discovering the path between nodes using breadth-first search will take \(\mathcal(O)(n + e)\) time, where is the number of nodes in the graph and is the number of edges. We can verify the proposed path is valid in \(\mathcal(O)(n)\) time simply by following the proposed path to see if the two points really are connected by that path.
In all the examples above, both computing and verifying the solution can be done in polynomial time.
Witness example
When we discussed the \(NP\) class we defined what a witness was, a piece of encoded information that helps a verifier (deterministic Turing machine) to perform a verification about some given input for a decision problem. We remember that this means: if the verifier accepts the pair, then the input is part of the solution of the problem; if not, it is not conclusive, it may be a problem of the verifier.
Expanding this concept, at a high level, in computer science we can think of a witness as a proof that you solve an instance of the problem, that a particular input is a YES-instance.
A witness can be a direct solution to the problem. For the examples above, that can be solved deterministically, these are things we could use as a witness:
- The sorted list
- The index where a number appears in the list
- The path between two nodes in a graph
But in most cases a witness does not necessarily have to be a direct solution to a problem, or, in other words, the solution to the original problem. This is especially true when a deterministic approach is not efficient at first glance. This is when the idea of the verifier as a separate entity and the witness gains more weight. Then, the verifier can be thought of as a deterministic algorithm that decides an alternative representation of the same problem.
For example, consider the following question: "Given a number \(n\), is \(n\) composite?". The direct solution would be: find two integers \(a,b>1\) such that \(n=ab\). If we have for example the number \(341\) the direct solution would be: \(341 = 11·31\), so it is composite.
But we can provide a different proof avoiding the factorization.
We know that if a number cannot be decomposed into factors different from one and itself, then it is prime, so demonstrating that a number is prime is the boolean-opposite of demonstrating that it is composite.
For this matters, we can use the Miller–Rabin primality test, which says that:
For a given odd integer \(n > 2\), let’s write \(n − 1\) as \(2^sd\) where \(s\) is a positive integer and \(d\) is an odd positive integer. Let’s consider an integer \(a\), which is coprime to \(n\). Then, \(n\) is said to be a strong probable prime to base \(a\) if one of these congruence relations holds:
- \[a^d \equiv 1 \pmod n\]
- \[\exists r \in \mathbb{Z}: 0 \leq r < s \land a^{2^rd} \equiv -1 \pmod n\]
We were saying that \(p=341\), then \(a=2\) (obviously a coprime), so \(p−1=340 = 2^{2}·85\), then:
\[a^d \equiv 1 \pmod n \iff 2^{85} \ mod \ 341 = 32\]So this fails the first test; the second test requires the retest with \(r\) between 0 and 1. We already know that (for \(r = 0\)) \(32 \neq -1\), so for \(r=1\):
\[2^{2·85} \ mod \ 341 = 2^{170} \ mod \ 341 = 1 \neq -1\]This means that, for base \(2\), our integer does not satisfy any of the conditions to be likely a prime, which means that it is definitively not a prime.
Then, in terms of computation, the integer \(a=2\) applied to the theorem above is our witness to the decision problem we proposed at the start: is \(341\) prime?. The primality test could be thought of as the verifier \(V\), and \(V(2,341) = 1\) (since it fails both tests so it is not prime; otherwise it would be a strong probable prime, but not a definitive prime) is equivalent to solving the question about whether it is composite, which was our original decision problem.
3.3. Problems in PSPACE: Not all problems have solutions that can be efficiently verified.
We talked about two classes which have conditions that consider the time in which a problem can be either verified or solved by a deterministic model. In this case, PSPACE considers the amount of space invested; the only requirement relative to time is that it eventually finishes.
3.3.1. Space-bounded Turing Machines.
Being \(M \in DTM\) with \(\Gamma\) being the tape alphabet, we recover that a configuration \(C = (q,t,n): q \in Q, t:\mathbb{Z} \to \Gamma, n \in \mathbb{Z}\).
Then, consider the halting computation \(C_0(x) \vdash_M C_1(x) \vdash_M ... \vdash_M C_p(x)\), then we would write \(C_i(x) = (q_i,t_i,n_i)\). We define
\[Space_M(x):= |\{\ n_i \ | \ 0 \leq i \leq p\ \}|\]If \(n\) reflects, in \(C = (q,t,n)\), in which cell of the tape the tape head is on that current snapshot, then we are just considering the number of all the different tape cells the head visits in the computation of a given input.
Then, for a function \(s:\mathbb{N} \to \mathbb{N}\):
\[DSPACE(s(n)) = \{ L \subseteq \Sigma^* \ | \ \exists \ M \in DTM \ deciding \ L: space_M(x) \in s(|x|)\}\]this is, the set of those languages for which there exists a DTM that has a use-space function upper bounded by \(s(\vert x \vert)\).
We define \(PSPACE\) as the set of those DSPACES for a polynomial use-space function:
\[PSPACE = \displaystyle\bigcup_{k \in \mathbb{N}} DSPACE(n^k)\]This are all of those problems that can be decide with a reasonable amount of space.
The relation withother class discussed before is:
\[P\subseteq NP\subseteq PSPACE\]3.3.2. Space-problems example.
This class of problems has been researched extensively, yet no efficient algorithm to solve them has been discovered. Many researchers believe no efficient algorithm to solve these problems exists at all. If an efficient solution to these problems could be discovered, it would also be possible to reuse the algorithm to break all modern encryption and fundamentally alter computing as we know it.
Despite significant incentives for finding efficient solutions to these problems, evidence suggests such solutions likely do not exist. These problems are so challenging that you cannot provide easily verifiable proof (witness) even if you solve them correctly.
Let see some examples:
-
Given an started chess-state, find the optimal chess move. If we ask a computer about the optimal next move for a given position, the computer give a straight answer based on a calculation of all the future game-state from the given position. There is no efficient way to check the best move, and as you optimize the calculation about the move more resource you need to invest.
-
Determining if regexes (regular expressions) are equivalent. Checking if two arbitrary regexes are equivalent takes exponential time to compute. Even if a powerful computer told you they match the same strings, there is no short proof (witness) the computer can give you to show the answers are correct. Similar to the chess example, you’d have to search a very large space of strings to check if the regexes are equivalent, and that will take exponential time.
3.4. NP. Problems that can be quickly verified but not quickly computed.
If we can quickly verify the solution to a problem, then the problem is in NP. However, finding the solution might require exponential resources.
As we say before: any problem whose proposed solution (witness) can be quickly verified as correct is an NP problem. If the problem also has an algorithm for finding the solution in polynomial time, then it is a P problem. All P problems are NP problems, but it is extremely unlikely that all NP problems are also P problems.
Let's check some examples:
-
Sudoku: Given a Sudoku puzzle solution, we can quickly verify the solution is correct simply by looping over the columns and rows. The witness can be verified in polynomial time. However, computing the solution requires significantly more resources — there are an exponential number of combinations to search. Note that as the sudoku grows, the time needed to check the solution grows exponentially.
-
Three-coloring a map: Any 2D map of territories can be “colored” with just four colors (see the four color theorem). That is, we can assign a unique color (one of four colors) to each territory such that no neighboring territories share the same color. The three-coloring problem asks whether a map can be colored using just three colors instead of four. Discovering a three-coloring (if it exists) is a computationally intensive search problem. However, verifying a proposed 3-coloring is easy: loop through each of the regions and check that no neighboring regions have the same color of the territory currently being checked.
3.5. Explanation of PvsNP.
Now that we have a solid understanding about, what P, NP are. Lets face some core question about complexity theory.
-
First, we did see that \(P\) is the class of problems for which exists a deterministical solution running in polynomial time (efficient time),
-
Then, we see that \(NP\) is the class of those languages that admit a non-deterministical but never the less time-efficient solution and also we see that a deterministical perspective of NP problems is needed. That was the characterization of NP as the class of those languages that admit a verification in polynomial time.
Now, a convenient question is put on the table. Do thouse quick verificable problems admit a efficient solution also? Or said in other words, is NP part of P?
\[P \supseteq NP\]Remember that above we said that \(P \subseteq PN\), both statements together are equal to propose the equivalence between those two setsL
\[P \subseteq NP \land P \supseteq NP \iff P = NP\]This is, any problem that can be efficiently verified can also be efficienctly decided?
\(P = NP\) is a powerful statement, it would mean that whenever we can find an efficient verifier for a YES-instance input of a decision problem, we can be sure that there exists also an efficient solution that decides the problem.
As a summary, we dedicated a part of the course to understand PvNP subject (among with turing machine, efficient time-solving problems, etc) because ZK cares about the verifying aspect of the computation, this means, to the subject of develop a witness that efficiently proof a YES-instance of a problem.