18
votes
False proofs that look correct
One of my favourites is the "brothers paradox":
https://en.wikipedia.org/wiki/Boy_or_Girl_paradox
I tell it as I learned it*, as follows:
in a village, each family has two children, elder ...
16
votes
False proofs that look correct
Merge-sort can be done in linear time!
Indeed, the time complexity to sort a list or array of length $n$ verifies$^{(1)}$:
$$T(n) = T\left(\left\lfloor\frac{n}2\right\rfloor\right) + T\left(\left\...
9
votes
False proofs that look correct
This one is regarding $\mathsf{FPT}$ time algorithm.
Suppose an algorithm has time complexity of: $O((\log n)^k \cdot n^{O(1)})$.
Is it an $\mathsf{FPT}$ time algorithm in parameter $k$?
Well ...
9
votes
False proofs that look correct
I have often seen among undergraduates that they believe that the heaps are constructed in $\Theta(n \log n)$ time.
The standard algorithm for that is to insert an element to a heap one after another. ...
8
votes
False proofs that look correct
This one is classic.
$0$-$1$ Knapsack problem is polynomial time problem since there is dynamic programming solution with running time $O(n W)$ time.
However, it is incorrect.
Note that the input size ...
6
votes
False proofs that look correct
An simple example that I can think of, which is commonly use as introductory topic in amortized analysis, is the analysis of dynamic table. The usual scenario is to analyze the total time needed to ...
6
votes
can we computably list every primitive recursive function?
The primitive recursive functions can be defined in terms of the following five axioms:
Constant function: $C_n^k$ is a $k$-ary function that always returns $n$
Successor function: $S$ is a 1-ary ...
5
votes
False proofs that look correct
Induction often yields great wrong proofs because there are many things which can fail:
The induction base $P(0)$ can be false, or it may be missing at all and hence the rest of the induction is ...
4
votes
PSPACE≠co-NP?Is the statement true?
If P = PSPACE then since $\text{P} \subseteq \text{coNP} \subseteq \text{PSPACE}$, we can conclude that coNP=PSPACE, and by contrapositive this means that if $\text{coNP} \neq \text{PSPACE}$ then $\...
4
votes
How to prove greedy algorithm is correct
Jeff Ericson in his "Algorithms" states three conditions:
Greedy choice: There is an optimal solution that includes the choice the algorithm makes.
Inductive structure: The smaller ...
3
votes
False proofs that look correct
Along the lines of rexkogitans's remark that proofs by induction are fertile ground for false proofs: one of my favorites is that every natural number can be uniquely described in fifteen English ...
3
votes
False proofs that look correct
Spaghetti sort can sort numbers in linear time.
Assume without loss of generality that the numbers to be sorted are all in the interval $(0,1)$. A whole spaghetti has length $1$.
For each number cut ...
3
votes
False proofs that look correct
Maybe not exactly what you're looking for, but the Monty Hall problem is famously counterintuitive.
There are three doors. One conceals a car, and the other two goats. You select one door. The host ...
3
votes
Accepted
can we computably list every primitive recursive function?
I'll build on Pål's answer to be a bit more explicit about how we can code PR functions using those operations. First of all, note that we can code any finite sequence of (positive) numbers into a ...
3
votes
Accepted
Prove maximum score is achieved by being greedy
If $(t_0, t_1, …, t_{n-1})$ is the sequence of tokens played by your greedy solution, you can show by induction that for any $k\in \{0, …, n\}$, the sequence $(t_0, …, t_{k-1})$ is the sequence of $k$ ...
2
votes
How to prove greedy algorithm is correct
There is a very nice theory on when greedy algorithms work in general. It is based on the abstract concept of matroids. A detailed explanation is given by Jeremy Kun.
2
votes
Proving why decreasing an edge weight in a graph may change it's MST by one edge
Let $T$ be the original spanning tree, and let $uv$ be the modified edge. Let $xy$ be a heaviest edge on the unique $u$-$v$-path in $T$.
Remove $xy$ from $T$ to obtain $T'$, two disconnected trees ...
2
votes
False proofs that look correct
As a general idea, maybe a 'proof' of a greedy algorithm as applied to a problem where the failure case is not immediately obvious?
A classic example (used for introducing Ford-Fulkerson) would be ...
2
votes
Accepted
Invariance Textbook Problem: Clarification Needed
I think they don't mean to consider a "set" of numbers (where $\{3, 4, 5, 5\} = \{3, 4, 5\}$) but rather a list or multiset of numbers.
In that case the result is true: initially the sum of ...
1
vote
Accepted
Greedy algorithms criterion/ intution
Sometimes it is good to delete the maximum element even when its value is larger than the sum of the two minimum elements. Deleting it allows the algorithm to remove the smaller elements in the next ...
1
vote
Accepted
The formal proof that one Turing Machine recognizes one specific language
The halting problem doesn't really tell you anything about whether you can prove that a TM recognises a given language.
We can prove that the TM recognises $\{0^n1^m : n \geq 1\}$ using the definition ...
1
vote
Accepted
Amortised cost - transferring tokens
To prove a lower bound simply take a worst case example. We will prove the following:
Induction Hypothesis: There exists a sequence of moves that results in $n$ tokens at position $\log n$ that ...
1
vote
Is the time complexity of a loop that simultaneously increments and multiplies $O(\log_k n)$ when $k = 1$?
In the incomplete GeeksForGeeks question #8, it is only correct when $k > 1, k \in \mathbb{Z}$. The code is equivalent to for(int i=0;i<n;i=1+i*k). We can ...
1
vote
Accepted
Does Cutting Planes solve Pigeongole Principle for holes of different sizes?
Let $x_{ij}$ state that pigeon $i$ goes to hole $j$. One can axiomatize the pigeonhole principle as follows:
Booleanity: $0 \leq x_{ij} \leq 1$.
Pigeon axioms: for all $i$, $\sum_j x_{ij} \ge 1$.
...
1
vote
Accepted
Greedy Algorithm and Proof of Correctness for Minimum Denominations of US Coinage System Problem
I decided to write a python script that generates all the optimal solutions for all the change. You can literally scroll through the solutions and observe there are no denomination expansions. So, my ...
1
vote
Greedy Algorithm and Proof of Correctness for Minimum Denominations of US Coinage System Problem
The greedy algorithm is optimal if it only picks 1c coins. It is optimal if it picks a 5c coin as the highest because the alternative is five 1c. It is optimal if it picks one or two 10c because the ...
1
vote
Union of non regular and regular language
Given regular $R$ and nonregular $N$ you investigate whether their union $R\cup N$ is regular or not, and you state that you are aware that the outcome depends. Now you consider special cases. Two of ...
1
vote
Union of non regular and regular language
Cases $1$, $2$, and $5$ are trivial:
If $L \subseteq L'$ then $L \cup L' = L'$, which is non-regular by hypothesis.
If $L' \subseteq L$ then $L \cup L' = L$, which is regular by hypothesis.
When $L \...
1
vote
Accepted
Trying to give a proof about graphs. Having a hard time giving proof for Kruskals algorithm. Can you check my answer?
To prove correctness of Kruskal's algorithm (and Prim's), you can use the cut property.
Lemma (The cut property).
Let $\emptyset \subset S \subset V$ be a set of vertices and $e$ a cheapest edge with ...
Only top scored, non community-wiki answers of a minimum length are eligible
Related Tags
proof-techniques × 693algorithms × 90
complexity-theory × 77
formal-languages × 75
turing-machines × 48
computability × 47
correctness-proof × 47
induction × 47
regular-languages × 46
graphs × 45
reductions × 38
logic × 38
undecidability × 38
algorithm-analysis × 37
context-free × 37
finite-automata × 33
asymptotics × 33
np-complete × 31
recurrence-relation × 28
automata × 27
pumping-lemma × 23
formal-grammars × 19
greedy-algorithms × 17
time-complexity × 15
recursion × 15