133
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,...
69
To my knowledge the pumping lemma is by far the simplest and most-used technique. If you find it hard, try the regular version first, it's not that bad. There are some other means for languages that are far from context free. For example undecidable languages are trivially not context free.
That said, I am also interested in other techniques than the ...
59
First, to dispel a possible cognitive dissonance: reasoning about infinite structures is not a problem, we do it all the time. As long as the structure is finitely describable, that's not a problem. Here are a few common types of infinite structures:
languages (sets of strings over some alphabet, which may be finite);
tree languages (sets of trees over some ...
58
Proof by contradiction is often used to show that a language is not regular: let $P$ a property true for all regular languages, if your specific language does not verify $P$, then it's not regular.
The following properties can be used:
The pumping lemma, as exemplified in Dave's answer;
Closure properties of regular languages (set operations, concatenation, ...
57
It all comes from undecidability of the halting problem. Suppose we have a "perfect" dead code function, some Turing Machine M, and some input string x, and a procedure that looks something like this:
Run M on input x;
print "Finished running input";
If M runs forever, then we delete the print statement, since we will never reach it. If M doesn't run ...
56
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$]
...
47
Yes, if you can come up with any of the following:
deterministic finite automaton (DFA),
nondeterministic finite automaton (NFA),
regular expression (regexp of formal languages) or
regular grammar
for some language $L$, then $L$ is regular. There are more equivalent models, but the above are the most common.
There are also useful properties outside of the ...
45
There is no magic bullet; NP-hardness proofs are hard. However, there is a general framework for all such proofs. Many students who struggle with NP-hardness proofs are confused about what they're supposed to be doing, which obviously makes it impossible to figure out how to do it. So here is what to do to prove a problem NP-hard.
First, unless you're ...
45
Ogden's Lemma
Lemma (Ogden). Let $L$ be a context-free language. Then there is a constant $N$ such that for every $z\in L$ and any way of marking $N$ or more positions (symbols) of $z$ as "distinguished positions", then $z$ can be written as $z=uvwxy$, such that
$vx$ has at least one distinguished position.
$vwx$ has at most $N$ distinguished ...
36
Based on Dave's answer, here is a step-by-step "manual" for using the pumping lemma.
Recall the pumping lemma (taken from Dave's answer, taken form Wikipedia):
Let $L$ be a regular language. Then there exists an integer $n\ge 1$ (depending only on $L$) such that every string $w$ in $L$ of length at least $n$ ($n$ is called the "pumping length") can be ...
34
Closure Properties
Once you have a small collection of non-context-free languages you can often use closure properties of $\mathrm{CFL}$ like this:
Assume $L \in \mathrm{CFL}$. Then, by closure property X (together with Y), $L' \in \mathrm{CFL}$. This contradicts $L' \notin \mathrm{CFL}$ which we know to hold, therefore $L \notin \mathrm{CFL}$.
This is ...
34
Converting Full History to Limited History
This is a first step in solving recurrences where the value at any integer depends on the values at all smaller integers. Consider, for example, the recurrence
$$
T(n) = n + \frac{1}{n}\sum_{k=1}^n \big(T(k-1) + T(n-k)\big)
$$
which arises in the analysis of randomized quicksort. (Here, $k$ is the rank of the ...
32
To put it more concretely, if I have an approach to prove P≠NP and if I could construct oracles to make a situation like above happen, why does it make my method invalid?
Note that the latter “if” is not a condition, because Baker, Gill, and Solovay already constructed such an oracle. It is just a mathematical truth that (1) there exists an oracle relative ...
29
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 "...
28
From Wikipedia, the pumping language for regular languages is the following:
Let $L$ be a regular language. Then there exists an integer $p\ge 1$ (depending only on $L$) such that every string $w$ in $L$ of length at least $p$ ($p$ is called the "pumping length") can be written as $w = xyz$ (i.e., $w$ can be divided into three substrings), satisfying ...
28
Generating Functions $\newcommand{\nats}{\mathbb{N}}$
Every series of numbers corresponds to a generating function. It can often be comfortably obtained from a recurrence to have its coefficients -- the series' elements -- plucked.
This answer includes the general ansatz with a complete example, a shortcut for a special case and some notes about using this ...
23
Ultimately, you'll need a mathematical proof of correctness. I'll get to some proof techniques for that below, but first, before diving into that, let me save you some time: before you look for a proof, try random testing.
Random testing
As a first step, I recommend you use random testing to test your algorithm. It's amazing how effective this is: in my ...
22
First, let us make two maybe obvious, but important assumptions:
_.random_item can choose the last position.
_.random_item chooses every position with probability $\frac{1}{n+1}$.
In order to prove correctness of your algorithm, you need an inductive argument similar to the one used here:
For the singleton list there is only one possibility, so it is ...
21
Let us consider the following inductive definition:
$\qquad \displaystyle \begin{align*}
&\phantom{\Rightarrow} \quad \varepsilon \in \mathcal{T} \\
w \in \mathcal{T} \quad &\Rightarrow \quad aw \in \mathcal{T}\\
aw \in \mathcal{T} \quad &\Rightarrow \quad baw \in \mathcal{T}
\end{align*}$
What is $\mathcal{T}$? Clearly, the set of ...
21
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{\...
20
There is (at least) one way to prove unambiguity of a grammar $G = (N,T,\delta,S)$ for language $L$. It consists of two steps:
Prove $L \subseteq \mathcal{L}(G)$.
Prove $[z^n]S_G(z) = |L_n|$.
The first step is pretty clear: show that the grammar generates (at least) the words you want, that is correctness.
The second step shows that $G$ has as many syntax ...
20
Master Theorem
The Master theorem gives asymptotics for the solutions of so-called divide & conquer recurrences, that is such that divide their parameter into proportionate chunks (instead of cutting away constants). They typically occur when analysing (recursive) divide & conquer algorithms, hence the name. The theorem is popular because it is ...
19
There is no general method since the set non-context-free-languages is not semi-decidable (a.k.a. r.e.). If there was a general method, we could use it to semi-decide this set.
The situation is even worse, since given two CFL's it is not possible to decide whether their intersection is also a CFL.
Reference: Hopcroft and Ullman, "Introduction to Automata ...
19
There are already good answers, but I would like to add a few small points.
Assume that we have a technique to solve problems, e.g. diagonalization. Assume that we want to show that the technique cannot solve a specific problem e.g. $\mathsf{P}$ vs. $\mathsf{NP}$. How can be show this?
Before going further, note that a technique like diagonalization is not ...
19
You show that either model can simulate the other, that is given a machine in model A, show that there is a machine in model B that computes the same function. Note that this simulation does not have to be computable (but usually is).
Consider, for example, pushdown automata with two stacks (2-PDA). In another question, the simulations in both directions ...
19
We can absolutely prove such things.
Many problems have trivial lower bounds, such as that finding the minimum of a set of $n$ numbers (that are not sorted/structured in any way) takes at least $\Omega(n)$ time. The proof for this is simple: a hypothetical algorithm that runs in $o(n)$ time can not examine all of the numbers in the input. So if we ran the ...
18
There is a huge variety of feasible approaches. Which is best suited depends on
what you are trying to show,
how much detail you want or need.
If the algorithm is a widely known one which you use as a subroutine, you often remain at a higher level. If the algorithm is the main object under investigation, you probably want to be more detailed. The same can ...
18
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 ...
18
It may be simply that it's mistaken to think that someone would reason their way to this argument without making a similar argument at some point prior, in a "simpler" context.
Remember that Turing knew Cantor's diagonalisation proof of the uncountability of the reals. Moreover his work is part of a history of mathematics which includes Russell's paradox (...
18
In your edit, you write:
What I still don't see is what would motivate someone to define $D(M)$ based on $M$'s "self-application" $M;M$, and then again apply $D$ to itself. That seems to be less related to diagonalization (in the sense that Cantor's argument did not have something like it), although it obviously works well with diagonalization once you ...
Only top voted, non community-wiki answers of a minimum length are eligible
