214

Part II Continued from Part I. The previous one exceeded the maximum number of letters allowed in an answer (30000) so I am breaking it in two. $\mathsf{NP}$-completeness: Universal $\mathsf{NP}$ Problems OK, so far we have discussed the class of efficiently solvable problems ($\mathsf{P}$) and the class of efficiently verifiable problems ($\mathsf{NP}$). As ...


151

Translating Code to Mathematics Given a (more or less) formal operational semantics you can translate an algorithm's (pseudo-)code quite literally into a mathematical expression that gives you the result, provided you can manipulate the expression into a useful form. This works well for additive cost measures such as number of comparisons, swaps, statements,...


58

Before I answer your general question, let me first take a step back, give some history background, and answer a preliminary question: Do non-computable functions even exist? [notational note: we can relate any function $f$ with a language $L_f=\{ (x,y) \mid y=f(x) \}$ and then discuss the decidability of $L_f$ rather than the computability of $f$] ...


54

For simplicity, I'll begin by only considering "decision" problems, which have a yes/no answer. Function problems work roughly the same way, except instead of yes/no, there is a specific output word associated with each input word. Language: a language is simply a set of strings. If you have an alphabet, such as $\Sigma$, then $\Sigma^*$ is the set of all ...


52

Landau notation denotes asymptotic bounds on functions. See here for an explanation of the differences among $O$, $\Omega$ and $\Theta$. Worst-, best-, average or you-name-it-case time describe distinct runtime functions: one for the sequence of highest runtime of any given $n$, one for that of lowest, and so on.. Per se, the two have nothing to do with ...


32

Execution Counts of Statements There is another method, championed by Donald E. Knuth in his The Art of Computer Programming series. In contrast to translating the whole algorithm into one formula, it works independently from the code's semantics on the "putting things together" side and allows to go to a lower level only when necessary, starting from an "...


26

Consider the following algorithm (or procedure, or piece of code, or whatever): Contrive(n) 1. if n = 0 then do something Theta(n^3) 2. else if n is even then 3. flip a coin 4. if heads, do something Theta(n) 5. else if tails, do something Theta(n^2) 6. else if n is odd then 7. flip a coin 8. if heads, do something Theta(n^4) 9. else if ...


22

Grammars are inherently recursive objects, so the answer seems obvious: by induction. That said, the specifics are often tricky to get right. In the sequel I will describe a technique that allows to reduce many a grammar-correctness proof to mechanical steps, provided some creative preprocessing is done. $\newcommand{\lang}[1]{\mathcal{L}(#1)} \newcommand{\...


19

The Special Case Assume we want to show $L_1 \leq_R L_2$ with respect to some notion of reduction $R$. If $L_1$ is a special case of $L_2$, that is quite trivial: we can essentially use the identity function. The intuition behind this is clear: the general case is at least as hard as the special case. In "practice", we are given $L_2$ and are stuck with ...


17

Skiena provides a sorted list of the dominance relations between the most common functions in his book, The Algorithm Design Manual: $$n!\gg c^n \gg n^3 \gg n^2 \gg n^{1+\epsilon} \gg n \lg n \gg n \gg n^{1/2}$$ $$ \gg \lg^2n \gg \lg n \gg \frac{\lg n}{\lg\lg n} \gg \lg\lg n \gg \alpha(n) \gg 1$$ Here $\alpha(n)$ denotes the inverse Ackermann function.


15

The Akra-Bazzi method The Akra-Bazzi method gives asymptotics for recurrences of the form: $$ T(x) = \sum_{1 \le i \le k} a_i T(b_i x + h_i(x)) + g(x) \quad \text{for $x \ge x_0$} $$ This covers the usual divide-and-conquer recurrences, but also cases in which the division is unequal. The "fudge terms" $h_i(x)$ can cater for divisions that don't come out ...


15

Leveraging a known nearby problem When faced with a problem that feels hard, it is often a good idea to try to search for a similar problem that is already proven hard. Or, perhaps you can immediately see that a problem is very similar to a known problem. Example problem Consider a problem $$\text{DOUBLE-SAT} = \{ \varphi \mid \varphi \text{ is a ...


14

A practical approach that in many examples works [but not always, I know] is trying to find the nesting structure of the strings in the language. "Nested dependencies" have to be generated at the same time in different parts of the string. Also we have the basic toolbox: concatenation: $S\to S_1S_2$ if you can split the language in two consecutive ...


13

Other answers have addressed this from a more theoretical perspective. Here is a more practical approach. For "typical" NP-complete decision problems ("does there exist a thingy that satisfies all these constraints?"), this is what I would always try first: Write a simple program that encodes your problem instance as a SAT instance. Then take a good SAT ...


13

A stronger version of the Ogden's condition (OC) is the Bader-Moura’s condition (BMC) A language $L\subseteq \Sigma^*$ satisfies BMC if there exists a constant $n$ such that if $z \in L$ and we label in it "distinguished" positions $d(z)$ and $e(z)$ "excluded" positions, with $d(z) > n^{e(z)+1}$, then we may write $z = uvwxy$ such ...


13

One useful tool is Rice's theorem. Here is what it says: Let $\emptyset \subsetneq P \subsetneq \mathcal{P}$ a non-trivial set of partially computable unary functions and $\varphi$ a Gödel numbering of $\mathcal{P}$. Then the index set of $P$ $\qquad I_P = \{ i \in \mathbb{N} \mid \varphi_i \in P \}$ is not recursive. You find it also ...


13

Excellent question! Nondeterminism first appears (so it seems) in a classical paper of Rabin and Scott, Finite automata and their decision problems, in which the authors first describe finite automata as a better abstract model for digital computers than Turing machines, and then define several extensions of the basic model, including nondeterministic finite ...


12

Summations Often one encounters a recurrence of the form $$ T(n) = T(n-1) + f(n), $$ where $f(n)$ is monotone. In this case, we can expand $$ T(n) = T(c) + \sum_{m=c+1}^n f(m), $$ and so given a starting value $T(c)$, in order to estimate $T(n)$ we need to estimate the sum $f(c+1) + \cdots + f(m)$. Non-decreasing $f(n)$ When $f(n)$ is monotone non-...


11

Copying my answer to a similar question on Stack Overflow: The easiest way to explain P v. NP and such without getting into technicalities is to compare "word problems" with "multiple choice problems". When you are trying to solve a "word problem" you have to find the solution from scratch. When you are trying to solve a "multiple choice problems" you have ...


11

Elementary methods Finite automata (possibly nondeterministic, with empty transitions). Regular expressions. Right (or Left, but not both) linear equations, like $X = KX + L$ where $K$ and $L$ are regular. Regular (Type 3) grammar. Operations preserving regular languages (Boolean operations, product, star, shuffle, morphisms, inverses of morphisms, reversal,...


11

There is one characterisation of CFL that can be of use, the Chomsky-Schützenberger theorem. Dyck language Let $T$ an alphabet. We define the Dyck-language $D_T \subseteq (T \cup \hat{T})^*$ of $T$ by the context-free grammar $G = (\{S\}, T \cup \hat{T}, \delta, S)$ with $\delta$ given by $\qquad\displaystyle S \to aS\hat{a}S \mid \varepsilon, \quad ...


10

Algorithm analysis, like theorem proving, is largely an art (e.g. there are simple programs (like Collatz problem) that we do not know how to analyze). We can convert an algorithm complexity problem to a mathematical one, as answered comprehensively by Raphael, but then in order to express a bound on the cost of an algorithm in terms of known functions, we'...


9

From the P vs. NP and the Computational Complexity Zoo video. For a computer with a really big version of a problem... P problems easy to solve (rubix cube) NP problems hard to solve - but checking answers is easy (sudoku) Perhaps these are all really P problems but we don't know it... P vs. NP. NP-complete Lots of NP problems boil down to the same ...


9

There may be times when you come across a strange recurrence like this: $$T(n) = \begin{cases} c & n < 7\\ 2T\left(\frac{n}{5}\right) + 4T\left(\frac{n}{7}\right) + cn & n\geq 7 \end{cases}$$ If you're like me, you'll realize you can't use the Master Theorem and then you may think, "hmmm... maybe a recurrence tree analysis could work." Then ...


9

First of all, when people talk about big O complexity, they refer to the complexity of an algorithm, usually its running time. A somewhat better term is big O asymptotics. Big O makes sense to functions beyond the running time of an algorithm, indeed beyond any kind of complexity measure of an algorithm. Big O notation actually first appeared in the context ...


8

In the case of unary languages (languages over an alphabet of size 1), there is a simple criterion. Let us fix an alphabet $\{ \sigma \}$, and for $A \subseteq \mathbb{N}$, define $$ L(A) = \{ \sigma^n : n \in A \}. $$ Theorem. Let $A \subseteq \mathbb{N}$. The following are equivalent: $L(A)$ is regular. $L(A)$ is context-free. There exist $...


8

Following the answer here, I will describe a method of proving non-regularity based on Kolmogorv complexity. This approach is discussed in "A New Approach to Formal Language Theory by Kolmogorov Complexity", by Ming Li and Paul M.B. Vitanyi (see section 3.1). Let $K(x)$ denote the Kolmogorov complexity of a string $x$, i.e. the length of the shortest ...


8

After checking this post again, I'm surprised this isn't on here yet. Domain Transformation / Change of Variables When dealing with recurrences it's sometimes useful to be able to change your domain if it's unclear how deep the recursion stack will go. For instance, take the following recurrence: $$T(n) = T(2^{2^{\sqrt{\log \log n}}}) + \log \log \log n$...


7

Case 2 of the master theorem, as usually stated, handles only recurrences of the form $T(n) = aT(n/b) + f(n)$ in which $f(n) = \Theta(n^{\log_ab}\log^k n)$ for $k \geq 0$. The following theorem, taken from a handout of Jeffrey Leon, gives the answer for negative $k$: Consider the recurrence $T(n) = a T(n/b) + f(n)$ with an appropriate base case. ...


Only top voted, non community-wiki answers of a minimum length are eligible