# Question
Title: How to prove greedy algorithm is correct
I have a greedy algorithm that I suspect might be correct, but I'm not sure. How do I check whether it is correct? What are the techniques to use for proving a greedy algorithm correct? Are there common patterns or techniques?

I'm hoping this will become a reference question that can be used to point beginners to; hence its broader-than-usual scope. Please take care to give general, didactically presented answers that are illustrated by at least one example but nonetheless cover many situations. Thanks!

# Answer
> 42 votes
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 experience, for greedy algorithms, random testing seems to be unreasonably effective. Spend 5 minutes coding up your algorithm, and you might save yourself an hour or two trying to come up with a proof.

The basic idea is simple: implement your algorithm. Also, implement a reference algorithm that you know to be correct (e.g., one that exhaustively tries all possibilities and takes the best). It's fine if your reference algorithm is asymptotically inefficient, as you'll only run this on small problem instances. Then, randomly generate one million small problem instances, run both algorithms on each, and check whether your candidate algorithm gives the correct answer in every case.

Empirically, if your candidate greedy algorithm is incorrect, typically you'll often discover this during random testing. If it seems to be correct on all test cases, then you should move on to the next step: coming up with a mathematical proof of correctness.

## Mathematical proofs of correctness

OK, so we need to prove our greedy algorithm is correct: that it outputs the optimal solution (or, if there are multiple optimal solutions that are equally good, that it outputs one of them).

The basic principle is an intuitive one:

*Principle:* If you never make a bad choice, you'll do OK.

Greedy algorithms usually involve a sequence of choices. The basic proof strategy is that we're going to try to prove that the algorithm never makes a bad choice. Greedy algorithms can't backtrack -- once they make a choice, they're committed and will never undo that choice -- so it's critical that they never make a bad choice.

What would count as a good choice? If there's a single optimal solution, it's easy to see what is a good choice: any choice that's identical to the one made by the optimal solution. In other words, we'll try to prove that, at any stage in the execution of the greedy algorithms, the sequence of choices made by the algorithm so far exactly matches some prefix of the optimal solution. If there are multiple equally-good optimal solutions, a good choice is one that is consistent with at least one of the optima. In other words, if the algorithm's sequence of choices so far matches a prefix of one of the optimal solutions, everything's fine so far (nothing has gone wrong yet).

To simplify life and eliminate distractions, let's focus on the case where there are no ties: there's a single, unique optimal solution. All the machinery will carry over to the case where there can be multiple equally-good optima without any fundamental changes, but you have to be a bit more careful about the technical details. Start by ignoring those details and focusing on the case where the optimal solution is unique; that'll help you focus on what is essential.

There's a very common proof pattern that we use. We'll work hard to prove the following property of the algorithm:

*Claim:* Let $S$ be the solution output by the algorithm and $O$ be the optimum solution. If $S$ is different from $O$, then we can tweak $O$ to get another solution $O^\*$ that is different from $O$ and strictly better than $O$.

Notice why this is useful. If the claim is true, it follows that the algorithm is correct. This is basically a proof by contradiction. Either $S$ is the same as $O$ or it is different. If it is different, then we can find another solution $O^\*$ that's strictly better than $O$ -- but that's a contradiction, as we defined $O$ to be the optimal solution and there can't be any solution that's better than that. So we're forced to conclude that $S$ can't be different from $O$; $S$ must always equal $O$, i.e., the greedy algorithm always outputs the correct solution. If we can prove the claim above, then we've proven our algorithm correct.

Fine. So how do we prove the claim? We think of a solution $S$ as a vector $(S\_1,\dots,S\_n)$ which corresponds to the sequence of $n$ choices made by the algorithm, and similarly, we think of the optimal solution $O$ as a vector $(O\_1,\dots,O\_n)$ corresponding to the sequence of choices that would lead to $O$. If $S$ is different from $O$, there must exist some index $i$ where $S\_i \ne O\_i$; we'll focus on the smallest such $i$. Then, we'll tweak $O$ by changing $O$ a little bit in the $i$th position to match $S\_i$, i.e., we'll tweak the optimal solution $O$ by changing the $i$th choice to the one chosen by the greedy algorithm, and then we'll show that this leads to an even better solution. In particular, we'll define $O^\*$ to be something like

$$O^\* = (O\_1,O\_2,\dots,O\_{i-1},S\_i,O\_{i+1},O\_{i+2},\dots,O\_n),$$

except that often we'll have to modify the $O\_{i+1},O\_{i+2},\dots,O\_n$ part slightly to maintain global consistency. Part of the proof strategy involves some cleverness in defining $O^\*$ appropriately. Then, the meat of the proof will be in somehow using facts about the algorithm and the problem to show that $O^\*$ is strictly better than $O$; that's where you'll need some problem-specific insights. At some point, you'll need to dive into the details of your specific problem. But this gives you a sense of the structure of a typical proof of correctness for a greedy algorithm.

## A simple example: Subset with maximal sum

This might be easier to understand by working through a simple example in detail. Let's consider the following problem:

*Input:* A set $U$ of integers, an integer $k$
*Output:* A set $X \subseteq U$ of size $k$ whose sum is as large as possible

There's a natural greedy algorithm for this problem:

1. Set $X := \emptyset$.
2. For $i := 1,2,\dots,k$:
    * Let $x\_i$ be the largest number in $U$ that hasn't been picked yet (i.e., the $i$th largest number in $U$). Add $x\_i$ to $X$.

Random testing suggests this always gives the optimal solution, so let's formally prove that this algorithm is correct. Note that the optimal solution is unique, so we won't have to worry about ties. Let's prove the claim outlined above:

*Claim:* Let $S$ be the solution output by this algorithm on input $U,k$, and $O$ the optimal solution. If $S \ne O$, then we can construct another solution $O^\*$ whose sum is even larger than $O$.

*Proof.* Assume $S \ne O$, and let $i$ be the index of the first iteration where $x\_i \notin O$. (Such an index $i$ must exist, since we've assumed $S \ne O$ and by the definition of the algorithm we have $S=\\{x\_1,\dots,x\_k\\}$.) Since (by assumption) $i$ is minimal, we must have $x\_1,\dots,x\_{i-1} \in O$, and in particular, $O$ has the form $O=\\{x\_1,x\_2,\dots,x\_{i-1},x'\_i,x'\_{i+1},\dots,x'\_n\\}$, where the numbers $x\_1,\dots,x\_{i-1},x'\_i,\dots,x'\_n$ are listed in descending order. Looking at how the algorithm chooses $x\_1,\dots,x\_i$, we see that we must have $x\_i \> x'\_j$ for all $j\ge i$. In particular, $x\_i \> x'\_i$. So, define $O^\* = O \cup \\{x\_i\\} \setminus \\{x'\_i\\}$, i.e., we obtain $O^\*$ by deleting the $i$th number in $O$ and adding $x\_i$. Now the sum of elements of $O^\*$ is the sum of elements of $O$ plus $x\_i-x'\_i$, and $x\_i-x'\_i\>0$, so $O^\*$'s sum is strictly larger than $O$'s sum. This proves the claim. $\blacksquare$

The intuition here is that if the greedy algorithm ever makes a choice that is inconsistent with $O$, then we can prove $O$ could be *even better* if it was modified to include the element chosen by the greedy algorithm at that stage. Since $O$ is optimal, there can't possibly be any way to make it even better (that would be a contradiction), so the only remaining possibility is that our assumption was wrong: in other words, the greedy algorithm will never make a choice that is inconsistent with $O$.

This argument is often called an *exchange argument* or *exchange lemma*. We found the first place where the optimal solution differs from the greedy solution and we imagined exchanging that element of $O$ for the corresponding greedy choice (exchanged $x'\_i$ for $x\_i$). Some analysis showed that this exchange only can only improve the optimal solution -- but by definition, the optimal solution can't be improved. So the only conclusion is that there must not be any place where the optimal solution differs from the greedy solution. If you have a different problem, look for opportunities to apply this exchange principle in your specific situation.

# Answer
> 14 votes
I will use the following simple sorting algorithm as an example:

```
repeat:
  if there are adjacent items in the wrong order:
     pick one such pair and swap
  else
     break

```

To prove the correctness I use two steps.

* First I show that the algorithm always terminates.
* Then I show that the solution where it terminates is the one I want.

For the first point, I pick a suitable cost function for which I can show that the algorithm improves it in every step.

For this example I choose the number of inversions in the input list. An inversion in a list $A$ is a pair of entries $A\[i\]$, $A\[j\]$ such that $A\[i\] \> A\[j\]$ but $i\<j$. The number of inversions is always non-negative and a sorted list has 0 inversions.

Clearly swapping two adjacent items $A\[i\]$, $A\[i+1\]$ that are in the wrong order removes the inversion $A\[i\],A\[i+1\]$ but leaves any other inversion unaffected. Hence the number of inversions is reduced in every iteration.

This proves that the algorithm eventually terminates.

The number of inversions in a sorted list is 0. If all goes well the algorithm will reduce the number of inversions down to 0. We only need to show that it doesn't get stuck in a local minimum.

I usually prove this by contradiction. I assume that the algorithm stopped, but the solution is not correct. In the example, this means the list is not yet sorted, but there are no adjacent items in the wrong order.

If the list is not sorted, there must be at least two items that are not in the correct position. Let $A\[i\]$ and $A\[j\]$, $i\<j$, $A\[i\]\>A\[j\]$ be two such items s.t. the difference between $i$ and $j$ is minimal. Since the algorithm didn't stop, they are not adjacent, so $i+1 \< j$. Because we assumed minimality, $A\[i\]\<A\[i+1\]$ and $A\[i+1\]\<A\[j\]$, but then $A\[i\]\ 4 votes
Jeff Ericson in his "Algorithms" states three conditions:

1. **Greedy choice:** There is an optimal solution that includes the choice the algorithm makes.
2. **Inductive structure:** The smaller subproblem that remains after fixing the choice by the algorithm is such that a viable solution of it can be combined with the choice to give a viable solution to the original (there are no *external restrictions*; in practice, it directs you to define the resulting smaller problem so this holds).
3. **Optimal substructure:** An optimal solution to the subproblem combined with the greedy choice gives an optimal solution to the original problem.

Proving (3) is critical, (1) is key.

# Answer
> 2 votes
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.

# Answer
> 0 votes
It is great if you can construct cases where the optimal solution is known. In that case generate a million cases and check if they find the expected result.

Or find a mate who implements a different algorithm independently. Generate a million random cases with no known result, run both algorithms, and every time you have different results, one algorithm is proven non-optimal.

For bin packing there is an obvious rule that if you make some weights bigger, you will need the same or a larger number of bins. Or if you increase the bin size the number of bins needed will be less or the same. I did this with thousand items of size sqrt(n), rounded to 9 decimals, with the bin size increasing in steps of 0.001 with a reasonable clever algorithm, and the number of bins needed jumped up and down.

Now nothing here is specific to a greedy algorithm. Here you would check whether one decision could make later decisions bad.

# Answer
> -2 votes
When you are unable to prove correctness, it is always worth it to try to construct some test case that contradicts your greedy approach. Even if you fail, you might get more intuition about why the greedy approach indeed works.

---
Tags: algorithm-analysis, proof-techniques, correctness-proof, greedy-algorithms
---


# Question
Title: Can a branch be pipelined with certainty if the branch condition can be known significantly before the actual branch?
A common issue with CPU performance is that pipelining requires the knowledge of what will come next, and what comes next can only be known once a branch condition is evaluated, so that instructions in the branch can be preloaded.

As such, CPUs employ branch predictors to predict which branch will be taken so that the pipeline can be preloaded.

However, depending on the circumstance, if there is a lot of work to be done between the evaluation of the branch condition and the actual branch, the next instructions in the pipeline to be preloaded do not yet depend on the outcome of the branch. If the condition can be known before the first `do_something()` or `do_something_else()` instruction has to even be prefetched, then can the branch be *'predicted'* with certainty (i.e., no chance of pipeline flush due to misprediction), because there are enough intermediate instructions that at the time the condition becomes known, none of the branch-dependent instructions need to have been loaded. For starters, does what I am saying make sense, and can CPUs work this way? Is my understanding correct?

```
const bool condition = some_condition();
do_work();
if (condition) {
    do_something();
} else {
    do_something_else();
}

```

# Answer
> 2 votes
The delay slot is one realisation of this idea. On many first-generation RISC CPUs (e.g. MIPS, PA-RISC, SPARC), the next instruction after a branch is *always* executed. Some special-purpose machines (e.g. DSP) have *multiple* delay slots. If no useful work can be done, the instructions following a branch can be filled with NOPs.

Compilers would often spend a lot of effort to try to fill that delay slot.

For a scalar in-order pipeline, this makes a certain amount of sense. But the modern CPU design trend is to much longer instruction windows, and much deeper branch prediction to go with it. The chance that there is a pipeline full of work to be done between the time that the branch is "resolved in software" and the time that the branch is taken/not taken is essentially zero.

# Answer
> 0 votes
Various PowerPCs had a count register that was part of the branch unit, with an instruction “decrement and branch if non-zero”. Setting the count register had significant latency, but the “decrement and branch if non-zero” was *not* predicted. The processor handled it like an unconditional branch. Or like a no-operation if the counter reached zero.

I wonder if that would be a win on a modern processor.

More to your question: Prefetching isn’t a problem. Those instructions will be put into some cache, so the work isn’t lost. And often the code is already cached. The real problem and gain is executing instructions when you don’t know (yet) that they should be executed. So you execute an instruction but mark it as “predicted”. Once the branch result is known, either the instructions are committed (changed from predicted to executed), or the results are thrown away.

So your question is: If there is a conditional branch, and the condition is already known, will any overhead for conditional execution be avoided? Answer: Processors will try to make the cost as little as possible, and try very hard to make the cost zero. So you might not be able to see or measure a difference.

---
Tags: cpu, cpu-pipelines
---


title: Linked Finite State Machine

text:
# Question
Title: Linked Finite State Machine
Let us assume, we have a FSM (to be precise, an epsilon-NFA) in which I've got redundant structures.
I am looking for a framework that allows to factor out the redundant part into some kind of subautomaton, respectively a more canonical representation and naming of this kind of NFA.

As illustration I've got the following NFA as example (It is just an example. I don't want to discuss, whether it could be minimized or designed more intelligently.)

I imagine a representation like this:

What I am specifically looking for is the possibility, to research scientific ressources and algorithms, to basically do this kind of "refactoring", which help me argue that though the grammar I'd extract from the result may be context-free, the language is still regular (since it is naturally identical to the orignal language accepted by an NFA).

So ideally, the accepted language class of the kind of automaton is *regular*.
Basically nothing more than a compact representation of highly redundant NFAs.

# Answer
> 4 votes
You may want to have a look at SCCharts, which extend FSMs (a.o.) with hierarchy and named sub-machines.

# Answer
> 1 votes
To answer this conclusively, we'd need to know more about how you intend to describe your NFAs with (named?) sub-NFAs.

If the directed graph obtained by having your (sub-)NFAs as nodes and your dashed arrows as directed edges has no cycles, then a copy semantics would necessarily give a finite traditional NFA and regularity of the language would follow.

If however you allow a collection of named NFAs with references to NFA names then regularity is at risk. For ease of expostion I'm borrowing from regular expressions here. Imagine a syntax for a list of declarations such as $N = \mathsf{a}N\mathsf{b} | \epsilon$ where $N$ is such a name. We'd have $L(N) = \\{~\mathsf{a}^n\mathsf{b}^n~|~n\in\mathbb{N}~\\}$, which is of course not regular.

---
Tags: finite-automata
---


# Question
Title: Can any SAT problem be converted to a system of linear equations over $\mathbf{Z}_2$?
Can any SAT problem be converted into one with only affine formulas?

*Handbook of Satisfiability* p. 672:

> **Affine formulas.** A *linear equation over the two-element field* is an expression of the form $x\_1 ⊕ … ⊕ x\_k = δ$ where $⊕$ denotes the sum modulo $2$ and $δ$ stands for $0$ or $1$. Such an equation can be expressed as a CNF formula consisting of $2k−1$ clauses of length $k$. An *affine formula* is a conjunction of linear equations over the two-element field \[$\mathbf{Z}\_2=\langle Bool , +, ∧, 0, 1\rangle$\]. Using Gaussian elimination, we can test satisfiability of affine formulas in polynomial time.

In other words: Can any SAT problem be converted to a system of linear equations over $\mathbf{Z}\_2$?

# Answer
> 3 votes
Equivalence: Not every SAT instance can be expressed as a system of linear equations. For instance, $x\_1 \lor x\_2$ cannot be expressed as a system of linear equations.

(Why not? Systems of linear equations have the following property: if $x\_1,x\_2$ is a solution to the system, and $y\_1,y\_2$ is a solution, and $z\_1,z\_2$ is a solution, then $x\_1 \oplus y\_1 \oplus z\_1,x\_1 \oplus y\_2 \oplus z\_2$ is also a solution. Yet it is easy to verify that True,False is a solution to the SAT instance $x\_1 \lor x\_2$, and False,True is a solution, and True,True is a solution; yet the xor of these three solutions is False,False, which is not a solution. Therefore, the satisfying assignments to $x\_1 \oplus x\_2$ cannot be represented as a solution to a system of linear equations.)

(See also https://en.wikipedia.org/wiki/Schaefer%27s\_dichotomy\_theorem, https://en.wikipedia.org/wiki/Boolean\_satisfiability\_problem#XOR-satisfiability.)

Equisatisfiability: Every SAT instance is either satisfiable or not satisfiable, i.e., is equisatisfiable to either True or False. Both of those can be expressed as systems of linear equations. However, figuring out which one is correct is not believed to be possible in polynomial time (specifically, not unless P=NP).

# Answer
> 0 votes
No, unless P=NP.

Cook-Levin showed SAT is an NP-complete problem. Solving a system of linear equations is a polynomial time problem. Also, Schaefer's Dichotomy Theorem says that SAT problems can divided into P or NP-complete classes.

cf. *Introduction to Mathematics of Satisfiability*

---
Tags: satisfiability, linear-algebra
---


title: Time complexity of function

text:
# Question
Title: Time complexity of function
```
int q(int n)
{
        if (n <= 0) return 0;
        return 1-q(q(n-1));
}

```

I'm not sure how to approach this. I tried representing the time complexity as a function $T(n)$ and then use repeated substitutions: So I got $T(n)=C+T(T(n-1))$ where $C$ is a constant representing a constant amount of lines we have in the function. Using repeated substitution we get: $T(n)=C+T(C+T(...T(C+T(0))))$, but $T(0)=0$ so $T(n)=C+T(C+T(...T(C)))$ and now we got a function that is only dependent on $C$ which is a constant, but I don't know how to continue from here.

# Answer
> 1 votes
First observe $q(n)$ always returns either $0$ or $1$. This can be proven formally by induction.

If $n \le 0$ this is immediate. If $n=1$ then the return value is $q(q(0)) = 1-q(0) = 1$. Suppose now that the claim holds up to some $n \ge 1$ and consider $q(n+1)$. The return value is $1-q(q(n))$ which is either $1-q(0)=1$ or $1-q(1)=0$.

You can now bound the time complexity of your function. Let $T(n)$ be the time spent by $q(n)$. If $n \le 1$, $T(n)$ is a constant. Otherwise the following recurrence relation holds: $$ T(n) = T(n-1) + \Theta(1), $$ where $T(n-1)$ accounts for the time spent computing $q(n-1)$ and the constant additive term accounts for time needed by the outer call to $q$ (which is either $q(0)$ or $q(1)$) and all other operations.

This recurrence has solution $T(n) = \Theta(n)$.

# Answer
> 0 votes
You can do these observations:

* $n\le 0\to q(n)=0$;
* $n=1\to q(n)=1-q(q(0))=1-q(0)=1$;
* $n=2\to q(n)=1-q(q(1))=1-q(1)=0$;
* $n=3\to q(n)=1-q(q(2))=1-q(0)=1$;
* $n=4\to q(n)=1-q(q(3))=1-q(1)=0$;
* $\cdots$

The pattern is obvious. From this, a call for $n\>0$ involves $2n$ recursive calls of which one is made with argument $0$ or $1$, thus in constant time. So if all elementary operations are done in constant time,

$$T(n)=\begin{cases}n\le0\to c&=\Theta(1) \\n\>0,\text{odd }\to an+b&=\Theta(n) \\n\>0,\text{even}\to an+b'&=\Theta(n). \end{cases}$$

---
Tags: time-complexity
---


title: Huffman tree and maximum depth

text:
# Question
Title: Huffman tree and maximum depth
Knowing the frequencies of each symbol, is it possible to determine the maximum height of the tree without applying the Huffman algorithm? Is there a formula that gives this tree height?

# Answer
> 4 votes
Huffman coding (asymptotically) gets within one bit of the entropy of the sequence. This means that if you calculate the entropy of your symbol frequencies, you will be (asymptotically) within one bit of the average length (i.e. height) of your code. You can use this average to bound the longest length (on average), or you can use combinatorial methods to get determinsitic bounds.

# Answer
> 0 votes
The pathological case would be when the sorted symbol frequency resembles that of Fibonacci sequence. N:= # of symbols. for N\>2, max possible height: N-1. for N == 1 or 2: 1

# Answer
> 0 votes
According to this paper,

> it is shown that if $p$ is the range $0\<p\leq 1/2$, and if $K$ is the unique index such that $1/F\_{K+3}\< p \leq 1/F\_{K+2}$, where $F\_K$ denotes the $K$-th Fibonacci number, then the longest Huffman codeword for a source whose least probability is $p$ is at most $K$, and no better bound is possible.

```
use std::io;

fn find_k(p: f64) -> Option<usize> {
    let (mut a, mut b, mut c) = (0, 1, 1); // starting with the first three Fibonacci numbers

    let mut i = 0;
    loop {
        if (1.0/c as f64) < p && p <= (1.0/b as f64) {
            return Some(i - 1);
        }
        // rolling the Fibonacci sequence
        let temp_a = b;
        let temp_b = c;
        c = b + c;
        a = temp_a;
        b = temp_b;

        i += 1;

//         if i > 1e299 as usize { // added a safety measure to prevent potential infinite loops
//             break;
//         }
    }

    return None; // K not found for given constraints
}

fn main() {
    let mut input = String::new();
    io::stdin().read_line(&mut input).unwrap();
    let p: f64 = input.trim().parse().unwrap();
    input.clear();

    match find_k(p) {
        Some(k) => println!("{}", k),
        None => println!("No suitable K found.")
    }
}

```

Try it online!

---

---
Tags: trees, coding-theory
---


# Question
Title: warning: ISO C++ forbids converting a string constant to ‘char*’
I am new to C++, and upon running this code I am getting the following error, can someone please explain what's wrong with the code? Thank you.

main.cpp:8:17: warning: ISO C++ forbids converting a string constant to ‘char\*’ \[-Wwrite-strings\] 8 | C(char \*s = " ",int i =0, double d=1){

# Answer
> 0 votes
As you probably know, raw strings (not to be confused with the `std::string` class) are stored by placing the characters in consecutive memory locations, followed by a null-byte terminator. Then to reference a string you simply use a pointer to the first character, hence its type is `char *`.

String literals are stored in your compiled binary and can be shared among multiple occurrences. As such they should be treated as immutable, i.e., each character is logically of type `const char` and the corresponding pointer is of type `const char*`.

The compiler is warning you that are using a variable of type `char*` instead of `const char*`. To see why this is problematic consider the following snippet of code:

```
char *mystring1 = "Hello world!";
const char *mystring2 = "Hello world!";
*mystring1 = 'B';
std::cout << mystring1 << "\n" << mystring2 << std::endl;

```

What should this print? If the string "Hello world!" is stored only once the, the assignment would modify it and the `std::cout` statement would output

```
Jello world!
Jello world!

```

Instead of the expected (?):

```
Jello world!
Hello world!

```

Besides, it's likely that your program won't even have write access to the memory area used to store the string literal, resulting in a memory access violation.

---
Tags: object-oriented
---


# Question
Title: What does it mean to prove that software is bugless?
A computer science lecturer said that one should use test as programs can't be proved to be bugless. Is this true? What does it mean to prove that program is bugless? Is there a proof that it is impossible to find such a proof? And is there a method to transform a program to a mathematical statement whose proof can or can't be found?

# Answer
Only trivial *programs* can be proven to be without bugs and even then, only in theory, not in practice. The problem is that there are too many places for a program to go wrong, many of which aren't actually part of the program itself, but, instead, part of the system(s) on which the program runs. Since a program can run essentially forever, there are an infinite number of possibilities.

It is even impossible to prove that a non trivial program even eventually halts. See The Halting Problem, for example.

You need to distinguish, however, between programs (implementations) and algorithms (logical structures). The latter can be proven in many cases.

One can use mathematical techniques to prove the correctness of an algorithm in many cases, but not the program built from it: the implementation. A course in Data Structures and Algorithms (sometimes two courses) explores this topic.

In practice, however, one uses testing methods to show that a program meets its specification in as many important situations as can be imagined. Both pre-test (test first) and post-test (acceptance testing) techniques are used for this, but they are imperfect as (a) we don't think of everything and (b) machines themselves can be imperfect and can differ in the nature of their imperfections.

Even the physics of electronics can lead to errors in the execution of programs. We hear of new "zero-day" vulnerabilities very frequently. Some of them are caused by the fact that electronics emit various electronic fields that can be read or can interfere with various components. Such things are nearly impossible to anticipate and can't be anticipated without failure.
> -1 votes

# Answer
One can indeed prove algorithms and programs using techniques such as Hoare's logic. The basic idea is to establish properties linked to the current values of the variables, and check how they evolve throughout program execution. There are formal rules associated to all basic constructs of programming languages (assignment, sequence, selection, iteration). A key concept is that of invariant which, in a way, concentrates the spirit of the algorithm.

Such proofs are as robust as any mathematical proof. For a gentle introduction, read "A Method of Programming" by Edsger W. Dijkstra and W.H.J. Feijen. You will find numerous examples there.

Nowadays, proofs can be assisted by computer, using formal verification systems such as Coq.

---

Anyway, no technique can guarantee a program bug-free because

* we are humans, not fault-free cyborgs,
* a proof can be buggy as well,
* tests can be buggy as well and are always incomplete,
* specifications are often lacunary so that some behavior can be declared buggy *after the fact*.
> 4 votes

---
Tags: correctness-proof
---


# Question
Title: Does a language/maschine/system need to be able to halt to be universal?
Is it possible for a language (or machine or system) to be universal or turing complete, when there is no possibility to write a program for it that halts?

Lets say we create a new language, brainfuck-nonstop, that like brainfuck with a single change: When the program pointer reaches the end, it goes back to the start and doesn't stop (like it would in brainfuck). This means there is no way for any program to ever halt. Would brainfuck-nonstop still be universal or turing complete?

# Answer
A system that does not stop does not deliver results so it can be neither universal nor complete: it is rather a non-system.
> 0 votes

# Answer
Yes, you can define a programming language that is Turing-complete even though there is no way for any program to halt.

Consider a variant of a standard programming language, with the restriction that every valid program has to be wrapped in an outermost "while True {...}" loop. Assuming this language has the ability to produce output. Such a programming language is Turing complete. For instance, you can add a boolean variable (initially True) that records whether the program is "done", and write a program of the following form:

```
while True {
    if !done {
        ...
    }
}

```

where you fill in "..." with anything you want. Now any time you would ordinarily halt, instead just set "done" to False. For instance, you can simulate a Turing machine; when the Turing machine halts, you output whether it accepted or rejected, set "done" to False, and let the program continue running but doing nothing.

There might be a little confusion about terminology. A programming language can be Turing-complete (or not). A Turing machine can be universal (or not). But there is no meaning of "universal" for programming languages; it doesn't make sense to ask whether a programming language is universal.
> 0 votes

# Answer
Automata (e.g. of the Büchi variety) for accepting infinite words necessarily run forever. Looking into those might be a good starting point.
> -1 votes

---
Tags: turing-completeness
---


# Question
Title: When to do proof by structural induction Vs defining a recursive function?
I'm trying to isolate the key differences between induction and recursion so that I am able to know when to use one over the other.

From my understanding, both can be used to prove properties about recursive structures.

For example:

Consider a recursive structure $x \in X$. In order to prove that for all $x$, $P(x)$ is $true$ one could do this inductively by showing that its $true$ for a base case, then for an inductive case that says if its $true$ for the constituents of a non-base $x$, its $true$ for $x$.

This can also be proved by defining the property $P(x)$ as a function $P:X \xrightarrow{} Bool$ which evaluates to $true$ for every $x$.

Which approach is better in general? I'm leaning towards defining recursive functions as it seems more natural for me as a programmer but maybe its just better here for this specific case, how would one decide what to do in general?

For example lets consider a simple P(x) below. It should be clear to see P(x) is true for all x, given x is an instance of a simple binary tree node.

```
boolean P(BinaryTreeNode x){
   if (x instanceof Leaf){
        return true;
   } else {
        return P(x.getLeft()) || P(x.getRight());
   }
}

```

# Answer
There seems to be some confusion here. Proof by induction is a valid way to prove facts about recursive structures.

I don't know what you mean by recursion, and the writing in your question doesn't make sense to me. A recursive function is not a proof. Defining a property $P(x)$ or a function is not a proof. I suspect there are some aspects here that you're not explaining well or you haven't fully understood.

In general, recursion is a technique for defining an algorithm, not a technique for proving a statement. See also https://math.stackexchange.com/q/3779213/14578.

Many recursive algorithms can be proven correct by using proof by induction. Perhaps that is what you are thinking of. But there is still an induction proof hidden in there somewhere (even if it hasn't been made explicit).
> 1 votes

# Answer
Recursive functions and induction are closely related, however Recursive functions do not have to terminate, and a proof using induction does have to terminate, so the induction should include a demonstration of this.
> 0 votes

# Answer
Here are some predicates/proofs in Agda, a programming language/proof assistant where induction and recursion are essentially the same thing. I can define a type of binary trees like so:

```
data Tree : Set where
  leaf : Tree
  node : Tree -> Tree -> Tree

```

Then, I can define a boolean predicate that matches yours like this:

```
P : Tree -> Bool
P leaf = true
P (node x y) = P x ∨ P y

```

The  operator is boolean or in the standard library. Now, suppose we tell Agda that 'it should be clear' that this predicate is always true:

```
P-true : ∀ t → P t ≡ true
P-true t = refl

```

`refl` being the reflexive proof that $x = x$. Agda rejects this with the message:

`P t != true of type Bool`

So, to Agda, it is not obvious that that predicate is true for all $t$. The predicate does not just reduce to `true` for an abstract `t`. We must prove it by induction:

```
∨-true-left : ∀{p q} → p ≡ true -> p ∨ q ≡ true
∨-true-left refl = refl

P-true : ∀ t → P t ≡ true
P-true leaf = refl
P-true (node x _) = ∨-true-left (P-true x)

```

As you can see, this proof by induction looks just like the recursive definition of the predicate. But, the recursive definition *of* the predicate is not sufficient to establish the universal truth of the predicate. The proof by induction recursively constructs a *proof* that the predicate is always true. This isn't particularly difficult, and the structure of the inductive proof closely follows the structure of the predicate's definition, which is why you probably consider it "clear." But giving the full details requires actually making this argument.

This structure is not much different than a full-fledged predicate in Agda, which looks like this:

```
P : Tree -> Set
P leaf = ⊤
P (node x y) = P x ⊎ P y

all-P : ∀ t → P t
all-P leaf = tt
all-P (node x _) = inj₁ (all-P x)

```

is the trivially 'true' type, and  is disjoint union, which is 'true' (has a value) if either of its sides is 'true'. The proof that the predicate holds for all $t$ has exactly the same structure as the boolean version.

There are occasionally reasons to prefer one of these sorts of definitions in Agda (or others that are roughly equivalent). But they have to do with technical details about how Agda behaves. In general they are largely the same.
> 0 votes

---
Tags: recursion, induction
---


# Question
Title: Are integer linear *feasibility* problems NP-hard?
I know that Integer Linear Programming problems are NP-hard. But it seems like this answer is only applicable to Integer Linear ***optimization*** problems.

It seems like integer linear ***feasibility*** problems should be able to be solved in polynomial time.

I was thinking that this would look something like this:

1. Solve the linear feasibility problem normally, and get the solution space.
2. Then, see if there is an integer solution point in this solution space.

This seems like it should be a polynomial time algorithm.

Does anyone know what I am missing here? Or have any papers that could help?

# Answer
> 3 votes
Feasibility of integer linear programming (ILP) is also NP-hard.

(Why? See https://cs.stackexchange.com/a/29916/755, Is 0-1 integer linear programming NP-hard when $c^T$ is the all-ones vector?, which reduces the SAT problem to feasibility of ILP. Or, alternatively, note that if you could test feasibility of ILP in polynomial time, then you could solve all ILPs in polynomial time too. In particular you could find the optimal value of the objective function $\Phi$ by using binary search: add the inequality $\Phi \ge c$ for some constant $c$ to your ILP, and then use binary search on $c$ to find the largest $c$ for which this system is feasible.)

You can't solve ILP using a linear programming solver. To put it another way, there is no known polynomial-time algorithm to "see if there is an integer solution point in \[the\] solution space" to a linear program -- that is exactly the ILP problem, which is known to be NP-hard.

To help you build your intuition, check out the examples in Linear programming vs integer linear programming.

---
Tags: complexity-theory, time-complexity, discrete-mathematics, linear-programming
---


# Question
Title: Weighted interval scheduling with m-machines ---greedy solution with approximation factor
Weighted interval scheduling with m-machines ('Weighted interval scheduling with m-machines')

I encountered the problem of weighted interval scheduling on m identical machines (as discussed in the link above). My greedy solution is exactly the same as the answer provided by D.W. in that link. 1. sort the interval by profit-to-duration in decreasing order, 2. then select intervals in that order. If there is still an available machine left, select it; Otherwise, skip the currently scanned interval. The selection is done when all intervals are considered.

I found the greedy solution provided pretty good empirical performance, and I wish to derive a theoretical approximation factor for this greedy solution. From the empirical result, I guess the approximation factor is very close to 1. I read about how to prove the approximation factor for greedy solutions in most general cases, but I can not transfer that knowledge to my case here. I think it is necessary to derive certain characteristics out of my greedy solution (in a mathematical form), which I can't :(.

In short, I would like to know how to derive an approximation factor for my greedy solution.

# Answer
> 1 votes
Unfortunately, the approximation guarantee of the algorithm is unbounded.

For example, Consider a single machine and only two intervals: interval $I\_1$ with profit $1$ and length $1$; and interval $I\_2$ with profit $w \gg 1$, and length $w+1$. Suppose the two intervals overlap. Then, the greedy algorithm gives a solution of profit $1$, i.e., interval $I\_1$. Whereas, the optimal solution is of profit $w$, i.e., interval $I\_2$.

---
Tags: approximation, scheduling
---


# Question
Title: Why does Schaefer's theorem not prove that P=NP?
This is probably a stupid question, but I just don't understand. In another question they came up with Schaefer's dichotomy theorem. To me it looks like it proves that every CSP problem is either in P or in NP-complete, but not in between. Since every NP problem can be transformed in Polynomial time into CSP (because CSP is NP-complete), why does this not prove that there is no space between P and NP-Complete and so that P=NP?

For example my thoughts go like, Integer factorization can be rewritten as a satisfiability problem, so using Schaefer's theorem it should be either in P or NP-complete but not in between (even if we can't find out which one it is).

A different way to look at the entire question: Why can't we use Schaefer's theorem to decide whether integer factorization is in P or in NP-complete?

---

EDIT: in response to David Richerby's answer (it is too long for a comment):

Interesting, but I don't yet fully understand. When defining the set of relations gamma while using Schaefer's theorem, we may impose restrictions on it. For example, we may restrict gamma to use only relations of arity 2 (then the problem is in P). What kind of restrictions can we impose on gamma?

Why can't we impose such restrictions that all instances of CSP(gamma) are exactly the same as (isomorphic to?) L? For example, when transating Integer factorization for uneven numbers, one of the two divisors is binary represented as xn .. x3 x2 1. Now, I want this number to be greater than 1. So, I have the relation (xn or .. or x3 or x2). So I say that gamma can have an or-relation of arity n-1. But I don't want that or-relation to be used to include other instances than L in the language, so I furthermore impose that x2..xn in the or-relation are not allowed to have a negation. Of course, I also need to impose the restriction that only specific variables are used there.

Isn't it possible in this way to let CSP(gamma) be isomorphic to integer factorization? The main question is: what kind of restrictions may we impose on gamma?

EDIT 2: in response to Yuval Filmus' answer.

I understand your answer and it seems correct, though about the same as David's answer. For example, we may reduce factorization to 3-sat and then conclude that factorization is NP complete, which is wrong because 3-sat has other instances that are probably not factorization.

The part that I don't understand, is when an instance is (non-)arbitrary. For example, 2-SAT also seems non-arbitrary to me, because only clauses of arity 2 are allowed (although I must admit that the proof then still holds because it is an upper bound and in this case the upper bound is P).

Perhaps a better example is an NP-completeness one: the question linked above. One answerer gives a full Schaefer's proof. But I impose non-trivial restrictions on the input (2-SAT clauses are allowed and xor-clauses, but nothing else). Of course, the proof still holds because the CSP problems considered in the proof are exactly the same as the original one.

The part that I don't understand is why we can't do similar for factorization? Of course it's no use to reduce it to 3-SAT, but allow me to give the CSP instance that factorizes a number and only factorizes a number (of 4 bits). (skip to END-OF-SKIP if you believe this is possible).

Factorization instance.

INPUT:

(N=)$n\_4n\_3n\_2n\_1$ (the 4 bits of the number to factorize)
(M=)$m\_4m\_3m\_2m\_1$ (the 4 bits of the minimum value of the first divisor)

Now, let's transform this to a CSP instance

INPUT:
unary domains for $n\_5..n\_1$ and for $m\_5..m\_1$ (representing that N and M are given)

variables with domain {0,1}:
(D=)$d\_4d\_3d\_2d\_1$ (the first divisor)
(E=)$e\_4e\_3e\_2e\_1$ (the second divisor)

relations:

$e\_4 \lor e\_3 \lor e\_2$ (representing E\>1)

$(d\_4 \land \neg m\_4) \lor (d\_4=m\_4 \land d\_3 \land \neg m\_3) \lor (d\_4=m\_4 \land d\_3=m\_3 \land d\_2 \land \neg m\_2) \lor (d\_4=m\_4 \land d\_3=m\_3 \land d\_2=m\_2 \land d\_1 \land \neg m\_1)$
(representing D\>M)

$d\_1 \land e\_1 = n\_1$ (representing least significant bit multiplication)
$(d\_1 \land e\_2) \oplus (d\_2 \land e\_1) = n\_2$ (representing the next bit multiplication)
$n\_3 = ... ; n\_4 = ...$

END-OF-SKIP

The crux is, *when applying Schaefer's theorem, we must only consider such CSPs*. (Just like for 2-SAT we only consider CSPs with arity 2). When doing that, either one of the six polymorphisms holds, or it does not (save some quirks in set theory). In either case, factorization is not NP-intermediate.

This can also be done for 3-SAT. Then, we should only consider (using the reduction) 3-SAT instances that represent factorization instances (which is not 3-SAT anymore).

Where do I go wrong?

# Answer
> 10 votes
When you translate an arbitrary **NP** problem $L$ to CSP, you end up with some set of instances with some constraint language (set of relations) $\Gamma$. What Schaeffer's theorem says is that deciding *all* instances of CSP($\Gamma$) is either in **P** or is **NP**-complete. But, if you only need to decide some restricted set of instances (e.g., the instances you get by translating the problem $L$), it might be easier. In particular, if $L$ is **NP**-intermediate, then solving the corresponding instances of CSP($\Gamma$) would also be **NP**-intermediate – you could just translate the instances back to instances of $L$ and solve them there. But solving the class of all CSP($\Gamma$) instances would be **NP**-complete.

# Answer
> 12 votes
Schaefer's theorem covers a very specific situation: you are given a finite set $\Gamma$ of relations, and are interested in the complexity of $\mathrm{CSP}(\Gamma)$. Schaefer's theorem gives you an algorithm to decide whether this problem is NP-complete or in P. It doesn't cover any other situation.

When you translate a problem like integer factorization into a CSP, you will use a set of relations $\Gamma$ such that $\mathrm{CSP}(\Gamma)$ is NP-complete (this, given the common belief that integer factorization is not in P). But your instances are not arbitrary, so Schaefer's theorem only gives an upper bound on the complexity. It could well be that integer factorization is in fact not NP-complete.

# Answer
> -3 votes
Marek, V. Wiktor. *Introduction to Mathematics of Satisfiability*. Boca Raton; London; New-York: CRC Press, 2009, p. 310:

> ***THEOREM 13.3 (Schaefer Theorem)***
> *Let $Γ$ be a collection of Boolean tables. If one of conditions (1)–(6) below holds, then $CSP(Γ)$ is solvable in polynomial time. Otherwise, it is NP-complete.*

If P = NP-complete, the aforementioned conditions have no bearing on the runtime:

> If the conditions hold, then $CSP(Γ)$ is solvable in P = NP-complete time.
> Otherwise, $CSP(Γ)$ is solvable in P = NP-complete time.

Which amounts to: "$CSP(Γ)$ is solvable in P = NP-complete time."

---

Review of *Introduction to Mathematics of Satisfiability* by M. I. Dekhtyar:

> Chapter 13 ends with a proof of the well-known Shaefer dichotomy theorem which divides classes of Boolean constraints into solvable in polynomial time and NP-complete.

---
Tags: np-complete, satisfiability, p-vs-np
---


# Question
Title: Is there any computation formalism based on general relativity?
Quantum mechanical principles have already been used to attack computer science problems in the form of quantum computing. In a similar vein, is there any usage of general relativity principles to generate algorithms in favor of computer-scientific problems? One (fairly trivial) example would be solving the shortest path problem, as the solution to the geodesic equation.

# Answer
> 1 votes
The reason quantum computing is useful is not (just) that the problems in QM are applicable to problems that'd we'd like to solve in computing generally, but because we can *physically realize* setups that model these problems in a way such that the (quantum) dynamics of the physical system solves our problem for us. In classical physics, the Difference Engine is useful because it reduces a problem of abstract arithmetic into a physical state in such a way that the physical dynamics of that state (i.e. turning the handle of the Engine) correspond to solving the problem, and the same reduction takes the "end state" of the physical machine back to the correct (abstract) answer. The same fundamentally applies for quantum computers, they just have access to dynamics that can perform certain operations faster than classical machines.

In (practical) relativity, there's not really the same opportunity for exploitation, because the local dynamics are still classical and you don't gain any new "magic powers" like you do in quantum. You can't build physical systems that make nature solve the problems for us. Time dilation in principle would be such a power, but there's no practical benefit in making a device slower. That said, Relativity may be a good inspiration for how to think about distributed systems, down to even multi-threaded programs on the same host, because the former is essentially a set of rules for determing which events within spacetime are ordered with respect to one another, and in a very fundamental sense, the (apparent) order of everything else cannot be relied upon. A similar idea of "locality" shows up in programming notions like the actor model, where it becomes very intuitive that anything "not in the same place" is not syncronised and it is unsafe to rely on the ordering of remote events.

However, on the (massively) *impractical* side, Relativity is also the theory that formalised notions of time travel. If you have a time machine that works in the sense of "you already changed the past", this *is* a magic power, because it allows you to build time loop logic which can solve $\text{PSPACE}$ problems in $\text{P}$ time, by essentially threatening to cause a paradox if you don't get what you want. The scheme goes like this:

1. Receive a candidate answer from the future
2. Check whether the answer is right
3. If it isn't, send back to the past the "next" candidate, however that's defined in the context.
4. If it is, send back the value you got as-is.

The issue being of course, 3 means that the value you sent back is not the one you received, which is paradoxical. The self-consistency principle asserts that a paradox cannot happen, so just like Raymond Chen's time-travelling undefined behaviour, we conclude that the only possible case is 4, meaning step 2 cannot fail and therefore the answer we got in step 1 *must* have been correct all along, even though nobody originally found it at any point.

(Sadly, nobody knows how to build a time machine, so whether this would actually work is of course up in the air.)

---
Tags: algorithms, reference-request
---


title: Time complexity of GPU computing

text:
# Question
Title: Time complexity of GPU computing
The time complexity of the matrix product is $O(n^3)$ if calculated normally for each element.

If computed on GPU, is it $O(n)$?

What I thought:

* GPU can compute each element of the matrix product in parallel.
* Each element is computed by a inner product of vectors $\sum\_{k=1}^n a\_kb\_k$
* Each $a\_kb\_k$ can be calculated in parallel, but the sum takes $O(n)$

# Answer
> 1 votes
If you assume $n^2$ processing elements (which is unbounded), then yes the complexity is $O(n)$. But the *total cost* (complexity times number of PEs) remains $O(n^3)$.

On the opposite, if the number of PEs is bounded, the complexity remains $O\left(\dfrac{n^3}{p}\right)$, which is $O(n^3)$.

# Answer
> 0 votes
it's still O(n^3), big o notation is about asymptotics.

# Answer
> 0 votes
From wikipedia

> Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm

It doesn't take into consideration the computing capabilities of the underlying machine. No matter the machine on which it is computed, the number of operations remain the same.

What you are looking after, would more suitably be called as order of *"running time"* or *"execution time"*.

---
Tags: complexity-theory, time-complexity, complexity-classes
---


# Question
Title: Weighted interval scheduling on K-identical machines --- approximation factor
This is a follow-up for Weighted interval scheduling with m-machines ---greedy solution with approximation factor.

As suggested by @D.W., I will present the problem more comprehensively.

$\textbf{Problem Definition}$:
Given $n$ intervals and $K$ identical machines, each with a duration $t\_{(\cdot)}$, fixed start time, fixed end time and a profit $p\_{(\cdot)}$ (meaning that has to be processed by this time range, and the preprocessing time or its duration is its end time minus its start time). I would like to schedule these $n$ intervals on $K$ identical machines, so that their profit sum is maximized.

There are a few practical constraint besides the general form of the problem above:
$\cdot$ $t\_{(\cdot)} \geq 1, t\_{(\cdot)} \in N^{+},$
$\cdot$ $p\_{(\cdot)} \geq 1, p\_{(\cdot)} \in N^{+},$
$\cdot$ $n \leq KT$ ($T$ is the max end time for any given interval, such that $t\_{(\cdot)} \leq T$).

$\textbf{My Greedy Solution}$:

1. sort the interval by profit-to-duration $\frac{p\_{(\cdot)}}{t\_{(\cdot)}}$ in decreasing order.
2. Select intervals in that order. For any given considered interval, if there is still an available machine left, select it; Otherwise, skip it. The selection is done when all intervals are considered.

$\textbf{My Question in This Post}$:
I would like to know the approximation factor by my greedy solution, something like $ALG\_{Greedy} \geq \frac{OPT}{\alpha}$. Based on the previous discussion Weighted interval scheduling with m-machines ---greedy solution with approximation factor, I think the approximation factor $\alpha$ should be $T$. But I would like to derive a formal and comprehensive proof for it. If the approximation factor $\alpha$ is not $T$, I would like to know its correct approximation factor (parameterizing allowed) and the corresponding proof :).

---

Or is there any other efficient (approximation) algorithm with approximation guarantees? :)

# Answer
Under the setting of the presented problem definition, if we sort the intervals by profit first instead of profit-to-duration first, I found an obvious approximation factor $n$ for this the other greedy-like solution (number of intervals).
> 0 votes

---
Tags: algorithms, approximation, scheduling
---


# Question
Title: Raise gaussian integer to gaussian integer power
Gaussian integer is a complex number whose real and imaginary parts are both integers.

Say I want raise $(a + b\*i)$ to power $(c + d\*i)$ and have result modulo $m$.

I can do it with floating-point approximation using normal complex power, as defined with exp and ln. But this is not precise, I can lost important last digits and this make result with small $m$ utterly wrong.

Is there an algorithm like Ancient Egyptian multiplication generalized for gaussian integers and for raising to power instead of multiplication to effectively obtain exact answer?

# Answer
In general the result is transcendental, so no.

E.g., $i^i=e^{-\pi/2}$.
> 1 votes

---
Tags: number-theory, multiplication
---


# Question
Title: What are very short programs with unknown halting status?
This 579-bit program in the Binary Lambda Calculus has unknown halting status:

```
01001001000100010001000101100111101111001110010101000001110011101000000111001110
10010000011100111010000001110011101000000111001110100000000111000011100111110100
00101011000000000010111011100101011111000000111001011111101101011010000000100000
10000001011100000000001110010101010101010111100000011100101010110000000001110000
00000111100000000011110000000001100001010101100000001110000000110000000100000001
00000000010010111110111100000010101111110000001100000011100111110000101101101110
00110000101100010111001011111011110000001110010111111000011110011110011110101000
0010110101000011010

```

That is, it is not known whether this program terminates or not. In order to determine it, you must solve the Collatz conjecture \- or, at least, for all numbers up to 2^256. On this repository there is a complete explanation of how this program was obtained.

Are there (much) shorter BLC programs that also have unknown halting status?

# Answer
> 33 votes
Yes.  This page says there are 98 5-state Turing machines whose halting statuses are unknown.  Annoyingly, it does not give any examples of such machines, but this 26-year-old page gives 2 5-state Turing machines whose halting statuses were apparently unknown at that time.  (Searching for "simple counter" will take you right between those 2.)  I copied them here in case that link goes down:

```
Input Bit   Transition on State     Steps            Comment
             A   B   C   D   E

    0       B1L C1R D0R A1L H1L   > 2*(10^9)       ``chaotic''
    1       B1R E0L A0L D0R C0L

    0       B1L A0R C0R E1L B0L       ?        complex ``counter''
    1       A1R C0L D1L A0R H1L

```

# Answer
> 5 votes
**Collatz conjecture:**

The following program always halts:

```
void function( ArbitraryInteger input){
     while( input > 1){
            if(input % 2 == 0)
                input /= 2;
            else
                input = (input*3) + 1;
     }

     // Halt here
}

```

**Slight variation (still a conjecture, because it's based on a result from Collatz's one):**

For some input the following program will never enter the same state twice (where the state is determined by the value held by "input"):

```
void function( ArbitraryInteger input){
     while( input >= 1){ // notice the "="
            if(input % 2 == 0)
                input /= 2;
            else
                input = (input*3) + 1;
     }
}

```

Note that the second program never halts, regardless of whether the first program halts or not.

It is believed that the first program always terminates for any input, however, we don't have the proof of that, and there may still exist some integer for which the program don't halt (there's also a $100 prize for proving it).

The second program is interesting too: it states that the program will never enter the same state twice for some input, which basically requires the first program to have a sequence known to diverge without repeating. It does not only require the Collatz conjecture to be false, **but it requires it to be false and without loops**, apart from the obvious 1,4,2,1 loop.

* If Collatz has only looping counter-examples the variation on the conjecture is false
* If Collatz is false without loops, the variation on the conjecture is true
* If Collatz is true, the variation is false
* If Collatz is false both because it has loops and because it has a number for which it diverges, the variation on the conjecture is true (it just requires a number for which it diverges without entering a loop)

**I think the variation is more interesting** (not just because I found it by accident and noticed it thanks to @LieuweVinkhuijzen), but because it actually requires a real proof. By brute forcing, we may be able to find a loop one day or another (and that will be a loop longer than 70 numbers: current state of the art is that there can't infinite loops shorter than 68 or so), and brute forcing is not interesting: it is just number crunching. However we cannot brute-force an infinite divergent sequence, we don't know if it will really end without a real proof.

EDIT: I skipped the part about Collatz Conjecture sorry, I genuinely answered by heart with an algorithm I read about some years ago, I didn't expect that was already mentioned.

EDIT2: A comment made me notice I wrote the algorithm with a mistake, however, that mistake indeed makes my answer different from Collatz conjecture (but a direct variation of it).

# Answer
> 4 votes
**Overview of Turing Machine decidability starting on the a blank tape (Busy Beaver style)**

For the blank tape input only:

The best overview of "lists of unproven machines" by various sources currently is this page from the "The Busy Beaver Challenge" (bbchallenge): https://bbchallenge.org/story#skelets-43-undecided-machines As of 2023 The bbchallenge is the most visible ongoing project to calculate BB(5), the Busy Beaver "shift" function of 5 AKA `s(5)` in some older literature, which counts how many steps a Turing machine runs for on a tape full of 0's before halting. Non-halting ones are excluded. So calculating BB(5) implies solving the halting problem for every single Turing machine with 5 states.

As highlighted by the bbchallenge, it also depends a lot on what you consider "verified", ranging from manual proof, to unverified programmatic checks, to formal proofs.

One of the major features of the bbchallenge are deciders. Deciders are programs that attempt to decide if a large number of Turing machines halt or not. But note that all deciders seem to be parameterized with "search depth like parameters", so it is not easy to be sure if more would be solved with larger parameters and more computational time. And in is a notable example of that some rare cases, time can get ridiculously large, requiring more advanced/specialized techniques in practice for proving specific machines, Skelet #1 below.

Back in 2003, Skelet produced a list of only 43 machines that he was not able to decide with a large formally unverified Pascal decider program, plus a few manual proofs. That list has generally considered to contain some of the "most likely unproven/hardest to prove ones".

Then more recently and independently, bbproject contributors also managed to decide all machines except 34 with deciders, but with much better review/verification procedures: https://discuss.bbchallenge.org/t/the-30-to-34-ctl-holdouts-from-bb-5/141/3

So it is interesting to see that both approaches found about ~30-40 machines that were not "easily" automatically provable and required manual proofs. This is of course where the gold lies, as these non-automatable machines are the ones most likely to represent "complex theorems worthy of mathematician's brain time", see also: ""Real" open conjectures reduced to Turing Machines below."

If these are worth a mathematician's brain time or not, is another story. Some of the machines appear to require computational + brain approaches, e.g. Skelet #1, which while epic, might not hold that much insight into Life, the Universe and Everything. Some however will hold deeper meaning of course.

**Skelet's 43 holdouts**

Skelet's holdouts were initially published at: https://skelet.ludost.net/bb/nreg.html

Dan Briggs manage to prove some of Skelet's 43 never halt circa 2021: https://github.com/danbriggs/Turing/blob/master/paper/HNRs.pdf

The BB challenge also solved some with their own deciders: https://bbchallenge.org/skelet

The "individual machines" section of the bbchalenge Discuss is likely best way to find an publish state of the art, it is basically the "Journal of BB(5) Research" if you will! https://discuss.bbchallenge.org/c/individual-machines/7 Some early movements occasionally also happen on Discord, go figure: https://discord.com/channels/960643023006490684/1026577255754903572 Notably, #1 and #34 also fell:

#1 was particularly epic, a shifted cycle with cycle of about ~8 billion steps.

It seems likely that the bbproject managed to resolve all of the holdouts as mentioned at: http://discuss.bbchallenge.org/t/the-30-to-34-ctl-holdouts-from-bb-5/141/4?u=cirosantilli and surrounding posts.

**BB(6)**

It currently looks like will likely never know BB(6). Or it would require a CERN-like mega-project, or AGI. Therefore if you are looking for some small Turing machines to prove, going through BB(6) one a time, trying every known decider on it, and failing that going for manual proof seems like a good approach!

A good argument we think BB(6) might never be known is that $BB(6) \ge 10 \uparrow \uparrow 15$, overview: https://www.sligocki.com/2022/06/21/bb-6-2-t15.html (Pavel Kropitz, 2022) i.e. Pavel came up with a machine he managed to prove halts after that time/many 1's written.

Therefore, if there are any BB(6) holdouts that take nearly as much computation time to decide, we might really never solve them. Compare that e.g. to BB(5), where the current champion halts after ~47 million steps, but where Skelet #1 has a cycle of the order of billions.

**"Real" open conjectures reduced to Turing Machines**

Some mathematical problems can be reduced to deciding the halting problem of a specific Turing machine. The best example of this is perhaps Goldbach conjecture, where it is obvious how you can make a Turing machine that just walks every positive number one by one, tries every possible pair of smaller numbers that sum up to it, and checks if they are prime. Then it halts if no valid pair is found for a number, or continues to infinity otherwise.

Such Turing machines serve therefore as examples of "known hard to prove problems". Going down that route also allows to show that certain Turing machines are undecidable in a certain proof system, e.g. ZF. This is done by modelling the logic system itself with a Turing machine.

https://bbchallenge.org/story#what-is-known-about-bb is the best list available as of 2023:

* BB(15) is at least as hard as Erdős' conjecture on powers of 2: "for n \> 8, there is at least one digit 2 in the base-3 representation of 2n". \[Stérin and Woods, 2021\]
* BB(27) is at least as hard as Goldbach conjecture: “for n \> 2, every even integer is the sum of two primes” unverified construction \[Aaronson, 2020\]
* BB(744) is at least as hard as Riemann Hypothesis \[Matiyasevich and O’Rear and Aaronson, unpublished\]
* BB(748) is independent of ZF \[O’Rear, unpublished\]
* BB(5,372) is at least as hard as Riemann Hypothesis \[Yedidia and Aaronson, 2016\]
* BB(7, 910) is independent of ZFC \[Yedidia and Aaronson, 2016\]

Most/all of these proofs involved compiling down simple programming languages to Turing machines programmatically, see also: Compiler that compiles to a Turing machine?

It is worth noting however that not all mathematical problems can be directly reduced to a "simpler halting problem" (that does not directly involve proving another Halting problem). E.g. this is not the case for Collatz conjecture, as a counterexample would go off to infinity and you wouldn't be able to tell: https://mathoverflow.net/questions/309044/is-there-a-known-turing-machine-which-halts-if-and-only-if-the-collatz-conjectur Goldbach is fundamentally different from Collatz in that you can just try every smaller number and be done for each integer.

Some real cool but mostly philosophical aspects of such reductions are:

* they allow us to estimate how hard a conjecture might be to prove: the more states in the Turing machine the harder
* they might allow for automated proofs to be carried out via deciders. In this way, they can be seen as a sort of "normal form" for large chunks of mathematics, much like 3SAT is a kind of normal form for NP.

**Blank tapes vs arbitrary tapes**

As highlighted by Marzio, the question of "decide every N-state Turing machine for every possible input" has already reached the wall basically:

* 3 states: decidable
* 4 states: unknown believed to be decidable
* 5 states: a Collatz-like problem
* 10 states: Collatz itself
* 15 states: Turing machine simulation (Universal Turing machine)

These numbers were extracted from the following answers which give their references:

Also note that the second image is already outdated as we have a 15-state universal machine as per first image, just it simulates slower than the previously known 19-state one.

While those could potentially be reduced slightly if an even smaller machine is found, we are already basically bricked at 5 states in terms of what we can prove.

This is what makes the blank-tape only problem more compelling to me. It is fundamentally simpler, as we don't have to consider infinitely many inputs for each machine: one machine, one input, can I decide it.

As a result, we get to zoom in much more, and the boundary between decidable, hard maths problem and undecidable has humongous gaps that beg to be improved. Notably, given that we got away with only 30-40 manual proofs for BB(5), it is not clear if BB(6) will present fundamentally hard maths problems or not. What about BB(7)? And so on. Because now we are at BB(15), which is a monumental gap away from BB(5).

---
Tags: algorithms, computability, kolmogorov-complexity
---


# Question
Title: What is the fastest algorithm for multiplication of two n-digit numbers?
I want to know which algorithm is fastest for multiplication of two n-digit numbers? Space complexity can be relaxed here!

# Answer
As of now Fürer's algorithm by Martin Fürer has a time complexity of $n \log(n)2^{Θ(log\*(n))}$ which uses Fourier transforms over complex numbers. His algorithm is actually based on Schönhage and Strassen's algorithm which has a time complexity of $Θ(n\log(n)\log(\log(n)))$

Other algorithms which are faster than Grade School Multiplication algorithm are Karatsuba multiplication which has a time complexity of $O(n^{\log\_{2}3})$ ≈ $O(n^{1.585})$ and Toom 3 algorithm which has a time complexity of $Θ(n^{1.465})$

Note that these are the fast algorithms. Finding fastest algorithm for multiplication is an open problem in Computer Science.

References :

1. Fürer's algorithm
2. FFT based multiplication of large numbers
3. Fast Fourier transform
4. Toom–Cook multiplication
5. Schönhage–Strassen algorithm
6. Karatsuba algorithm
> 24 votes

# Answer
Note that the FFT algorithms listed by avi add a large constant, making them impractical for numbers less than thousands+ bits.

In addition to that list, there are some other interesting algorithms, and open questions:

* ***Linear time multiplication on a RAM model* (with precomputation)**
* **Multiplication by a Constant is Sublinear** (PDF) - this means a sublinear number of additions which gets for a total of $\mathcal{O}\left(\frac {n^2} {\log n} \right)$ bit complexity. This is essentially equivalent to long multiplication (where you shift/add based on the number of $1$s in the lower number), which is $\mathcal{O}\left({n^2} \right)$, but with an $\mathcal{O}\left(\log n\right)$ speedup.
* ***Residue number system*** and other representations of numbers; multiplication is almost linear time. The downside is, the multiplication is modular and {overflow detection, parity, magnitude comparison} are all as hard or almost as hard as converting the number back to binary or similar representation and doing the traditional comparison; this conversion is at least as bad as traditional multiplication (at the moment, AFAIK).
    + Other Representations:
        - \[***Logarithmic representation***\]: multiplication is addition of the logarithmic representation. Example: $$ 16 \times 32 = 2^{\log\_2 16 + \log\_2 32} = 2^{4+5} = 2^{9} $$
            * Downside is conversion to and from logarithmic representation can be as hard as multiplication or harder, the representation can also be fractional/irrational/approximate etc. Other operations (addition?) are likely more difficult.
        - ***Canonical representation***: represent the numbers as the exponents of the prime factorization. Multiplication is addition of the exponents. Example: $$ 36 \times 48 = 3^2\cdot 5^1\times 2^{2}\cdot 3^1\cdot 4^1 = {2^2}\cdot {3^2} \cdot 4^1 \cdot 5^1 $$
        - Downside is, requires factors, or factorization, a much harder problem than multiplication. Other operations such as addition are likely very difficult.
> 9 votes

# Answer
**`n log(n)` by Harvey and van der Hoeven (2021)**

This was mentioned in two comments previously (, ), but it deserves its own answer.

Published as: "Integer multiplication in time O(n logn)"

This achieves the long conjectured (e.g. by Schonhage and Strassen in 1971) but not yet proven optimum of `n log(n)`.

It would be good to include a summary of the method here, but I have not tried to understand it as I have better things to do with my life like learning about the busy beaver problem.

Discussions of practical usage considering non asymptotic considerations:

Some relevant quotes from the paper itself:

> All of the algorithms presented in this paper can be made completely explicit, and all implied big-O constants are in principle effectively computable. On the other hand, we make no attempt to minimise these constants or to otherwise exhibit a practical multiplication algorithm. Our aim is to establish the theoretical O(n log n) bound as directly as possible.

and:

> 4.4. Further remarks. Our presentation of the Gaussian resampling technique has been optimised in favour of giving the simplest possible proof of the main M(n) = O(n log n) bound. In this section we outline several ways in which these results may be improved and generalised, with an eye towards practical applications

and further down:

> After making this modification, it would be interesting to investigate whether this method is competitive for practical computations of complex DFTs of length s when s is a large prime. One would choose a smooth transform length t somewhat larger than s, say 1.25s \< t \< 1.5s, and use the algorithm to reduce the desired DFT of length s to a DFT of length t; the latter could be handled via existing software libraries implementing the Cooley–Tukey algorithm. For large enough s, perhaps around $2^{20}$ or $2^{30}$, we expect that the invocations of S and J would be quite cheap compared to the FFT of length t
> 4 votes

# Answer
If space and amount of hardware is no concern, then you can do what most CPUs do: For two n-bit numbers, use n^2 AND gates to produce n^2 zeroes and ones, then use n^2 full adders to reduce the number of values by 1/3, do that again until you can get the final result with one set of full adders.

Time = O(log n), hardware cost = O(n^2). Could realistically be done today for n = 256, but there isn’t that much demand.

Otherwise, for small n (let's say you have a computer with 64 bit arithmetic, and your numbers are less than 5 x 64 bits) the speed will change dramatically at certain sizes. For small sizes, you could perform Karatsuba by hand. And look how the number of operations changes very carefully. For example from 16x16 to 17x17 words there could be a massive change.

One source claims Karatsuba is fasted up to 10^96 (320 bits, 5 64-bit words). But I could see Toom-Cook being faster, calculating products of 3 128-bit quantities, and calculating the 128 bit products using Karatsuba. So for the fastest for small n, I'd expect many individual cases. Plus this would be very implementation dependent.
> 0 votes

---
Tags: algorithms, mathematical-programming
---


# Question
Title: Is it actually the case that $Yg \to_\beta g(Yg)$?
For reference, the $Y$-combinator is the expression

$$ Y = \lambda f . (\lambda x . f (xx)) (\lambda x . f (xx)) $$

in the untyped lambda calculus. If $g$ is any lambda expression, then

\begin{align} Y g &= \lambda f . (\lambda x . f (xx)) (\lambda x . f (xx)) g \\ &\to\_\beta (\lambda x . g (xx)) (\lambda x . g (xx)) \\ &\to\_\beta g ((\lambda x . g (xx))(\lambda x . g (xx))), \end{align}

and the $\beta$-reductions used are at the top level (so this is possible using call-by-name evaluation). However, it is then claimed (see below) that

$$ g ((\lambda x . g (xx))(\lambda x . g (xx))) = g(Yg). $$

But this seems to be wrong, at least if we interpret equality as actual equality and not some sort of $\beta$-equivalence. Furthermore, the right-hand side reduces to the left-hand side, not vice-versa, and this reduction is not possible using call-by-name.

Nonetheless, the nLab claims that there is a multi-step reduction $Yg \to\_\beta g(Yg)$, it is implicit on this Wikipedia page, it is stated on these lecture slides (pdf-warning; page 17), etc. So apparently it is supposed to be the case. Am I missing something, or is it actually false that $Yg \to\_\beta g(Yg)$?

(Note: I mention call-by-name evaluation because $Y$ is used to construct recursive functions when using call-by-name. So presumably we should restrict ourselves to only perform reductions compatible with call-by-name for the reduction to be useful in that context?)

# Answer
> 1 votes
I think it is technically incorrect that $Y g →\_β g(Yg)$ using the definitions you've given. However, the one step $β$ reduction of $Yg$ is a fixed point of $g$ under reduction. Since the things you've given names to give no easy way to refer to this one step reduction, people just write $Yg$ instead, and don't worry about this minor detail (and often they are working up to $β$ equivalence, where it is exactly true).

I can't think of any situation where it'd be important whether $Yg$ itself is a fixed point of $g$ or immediately reduces to a fixed point of $g$.

---
Tags: lambda-calculus
---


# Question
Title: Polynomial representations of Boolean functions
The AND boolean function $AND(x)$ can be represented using the polynomial $P(x) = x\_1x\_2\cdots x\_n$. I have a few questions:

1. Is there a similar polynomial for the PARITY boolean function?
2. Is there a boolean function whose polynomial doesn't have a maximum possible degree?

# Answer
Regarding $1$: $$ \text{PARITY}(x\_1,x\_2,\dots,x\_n) = \frac{1}{2} \cdot(1-2x\_1) \cdot (1-2x\_2) \cdot \ldots \cdot (1-2x\_n) + \frac{1}{2} $$

The idea is that the term $(1-2x\_i)$ will be $1$ if $x\_i=0$ and $-1$ otherwise. The product of all these terms will have absolute value $1$ and the sign will encode the parity. To map $-1$ and $1$ back to $0$ and $1$ we multiply by $\frac{1}{2}$ and add $\frac{1}{2}$.

Regarding $2$: I'm not sure if this answers the question but every function $f(x\_1, x\_2, \dots, x\_n)$ can be expressed with a polynomial (in $x\_1, \dots, x\_n$) that is linear in each of the $x\_i$.

Let $A = \\{ (a\_1, \dots, a\_n) \in \\{-1, 1\\}^n \mid f(\frac{a\_1}{2}+\frac{1}{2},\dots,\frac{a\_n}{2}+\frac{1}{2}) = 1 \\}$. In other words $A$ contains all vectors that encode inputs for which $f$ is $1$, with the convention that "false" is represented by $-1$ and "true" is represented by $1$. Consider: $$ \sum\_{a\_1, \dots, a\_n \in A} \prod\_{i=1}^n \left( \frac{1}{2} (2x\_i-1) a\_i + \frac{1}{2} \right) = \sum\_{a\_1, \dots, a\_n \in A} \prod\_{i=1}^n \left( x\_i a\_i -\frac{a\_i}{2} + \frac{1}{2}\right) $$

The expression $x\_i a\_i-\frac{a\_i}{2} + \frac{1}{2}$ returns $1$ if $x\_i \in \\{0,1\\}$ and $a\_i \in \\{-1,1\\}$ are both "true" or both "false", and $0$ otherwise. Then the product is $1$ if $x\_1,\dots,x\_n$ matches $a\_1, \dots, x\_n$ and $0$ otherwise. Finally, the whole expression is $1$ if $x\_1, \dots, x\_n$ matches at least one vector in $A$, and $0$ otherwise.
> 1 votes

# Answer
*Any* Boolean function of $n$ variables can be realized by a polynomial of degree $n$, using multilinear interpolation.

$$f(x\_1, x\_2, x\_3,\cdots x\_n)=(1-x\_1)f(0, x\_2, x\_3,\cdots x\_n)+x\_1f(1, x\_2, x\_3,\cdots x\_n)$$

and so on inductively.

You can expand the result as a linear combination of your $AND$ polynomials. E.g., in two variables, the function with truth table $(a,b,c,d)$ is

$$a(1-x\_1)(1-x\_2)+b(1-x\_1)x\_2+cx\_1(1-x\_2)+dx\_1x\_2\\\=(a-b-c+d)x\_1x\_2+(c-d)x\_1+(b-d)x\_2+d.$$

---

Another method is to implement the Boolean operators by elementary real functions, and systematically substitute in the expressions:

* $\lnot x\_1\equiv 1-x\_1$,
* $x\_1\land x\_2\equiv x\_1x\_2$,
* $x\_1\lor x\_2\equiv x\_1+x\_2-x\_1x\_2$,
* $x\_1\oplus x\_2\equiv x\_1+x\_2-2x\_1x\_2$.
> 1 votes

---
Tags: boolean-algebra, polynomials, algebra
---


# Question
Title: Is binary tree balanced if and only if the morris traversal of the tree produces ordered list?
I'm trying to check if the binary tree is binary search tree. My idea is to use Morris traversal. Intuitively a binary tree is balanced **iff** Morris traversal produces a sorted threaded linked list.

The problem is I could not prove this proposition strictly. Is it even correct so it's safe to use it for binary search tree validation?

# Answer
A binary tree is a binary search tree iff its inorder traversal yields an ordered list.

Inorder (or symmetric) traversal is recursively defined as left-node-right. This recurrence is of course directly connected to the defining property of search trees: the items of the left subtree are smaller than the root, which in turn is smaller than the items of the right subtree. This makes the statement above rather straightforward.

So, in order to test the tree one needs to perform an inorder traversal. It is not important whether that traversal is done with recursion, with a stack or with temporal threads using Morris traversal.

(I am a little puzzled by your use of the word balanced. Usually that is related to the number of nodes or heights in subtrees.)
> 2 votes

---
Tags: algorithms, trees, binary-search-trees, tree-traversal
---


# Question
Title: How can a fault tolarent Distributed Data Saving Algorithm can be developed?
I am trying to design an algorithm. For now, I am trying to give myself a large overview.

Assume I have `K` (for example, `K` can equal 8) perfect slave machines, and one master machine. Each slave has a perfect HDD. I want to save the string "ABCDEFGHIJKLMNOP". My wished are

1. I want to only save a fragment of the string to each HDD belonging to an unique slave
2. I want to make sure, that an adversary can only recover the full string, if and only if he can access at least `P` fraction of the slaves (for example, `P` can be 50%).
3. However, an authorized user can recover the complete string, even if a few slaves are offline, or not accessible. Let's call the number of offline slaves `n`, let's also assume that `n < PK`. For example, in this case `n` can be 2, which is less than 50% of 8 total slaves.

Note that I am differentiating between compromised and accessible. A prefect adversary compromises a slave without rendering it accessible. However, a slave can become inaccessible with or without the involvement of an adversary.

How should I go about designing an algorithm that can do it?

**My attempt to solution** was to experiment with Reed Solomon Encoding - but I can't find a way that would allow both the fault tolerance, and significant difficulty for an attacker.

As an answer, I would like a detailed pseudocode with explanation with step by step explanation. In this question, I have not set any limit on `K` or `p` because I don't know if that is necessary or not. However, if a fully general answer isn't possible, then may be you can set suitable limits on these, to develop a special solution.

Thank you.

# Answer
> 1 votes
Use secret sharing. With a $k$-out-of-$n$ secret sharing scheme, the string is distributed among $n$ "slaves". Access to any $k$ "slaves" is enough to recover the string; but with access to $k-1$ or fewer "slaves", an adversary cannot learn anything about the string.

There are many standard secret sharing schemes in the literature. For instance, you can use Shamir secret sharing.

---
Tags: error-correcting-codes, algorithm-design
---


title: Upper bounding this expression

text:
# Question
Title: Upper bounding this expression
I need to prove that the following expression is $\mathcal O(n \log n)$ with the substitution method: $$ T(n) \leq 3\log n + n + \frac{6}{n}\sum^{n - \frac{\log n}{3}}\_{i=\frac{\log n}{3}} T(i)$$

This is my attempt, assumming $T(n) \leq c n \log n$: \begin{align\*} T(n) &\leq 3\log n + n + \frac{6c}{n}\int^{n - \frac{\log n}{3}}\_{\frac{\log n}{3}} x\log x dx\\ &= 3\log n + n + \frac{6c}{n}\left\[ \frac{x^2 \log x}{2} - \frac{x^2}{4}\right\]\bigg|^{n - \frac{\log n}{3}}\_{\frac{\log n}{3}}\\ &= 3\log n + n +\frac{6c}{n}\left\[ \frac{n^2}{2}\log \left(n-\frac{\log n}{3}\right)-\frac{n}{3}\log n \log \left(n - \frac{\log n}{3}\right) + \frac{\log^2 n \log(n-\frac{\log n}{3})}{18}-\frac{n^2}{4}+\frac{n\log n}{6}-\frac{\log^2 n\log (\frac{\log n}{3})}{18}\right\]\\ &=3\log n + n + 3cn \log(n - \frac{\log n}{3})-2c \log n \log(n - \frac{\log n}{3})+\frac{c\log^2n \log(n - \frac{\log n}{3})}{3n} - \frac{3nc}{2}+c\log n-\frac{c\log^2 n \log (\frac{\log n}{3})}{3n}. \end{align\*}

What else can I do?

# Answer
Consider the right hand side. Use $\log(n-\frac{\log n}{3})\leq \log n,$ to simplify the $\log n$ terms. Clearly the second term is at most $3 c n \log n.$

Since all other terms are of lower order (since they are powers of $\log n$ or smaller (such as being divided by $n$ for example)) the right hand side is $\leq 3c n\log n.$

For any positive constant $c$, the LHS for which you guessed $c n \log n$ is smaller than $3c n \log n$ so you can apply the substitution method and you are done.
> 0 votes

# Answer
Clearly,

$$ \frac{6}{n}\sum^{n - \frac{\log n}{3}}\_{i=\frac{\log n}{3}} T(i)\<\frac{6}{n}\sum^{n}\_{i=1} T(i)$$

and using your integral, this is smaller than

$$\frac6n\frac{n^2\log n}2=3n\log n.$$

Now,

$$n\log n\<3\log n+n+3n\log n.$$
> 0 votes

# Answer
If you have T(n) \<= c n log n for all n \< N, then you show that T(N) \<= 3 c N log N. That’s just not good enough.

It seems that T(n) for large n is quite exactly 6 times the average of all smaller values. T(n) = c * n^5 would do that. And c * n^4 wouldn’t. Integral of n^5 is n^6/6, times 6/n is n^5 again.

I’d say T(n) / n^5 converges to some constant c \> 0. Write a program to calculate the first 2^30 values of T(n) and print T(n) / n^5 when n is a power of two. The calculation takes linear time and O(log n) space.
> 0 votes

---
Tags: asymptotics, big-o-notation, landau-notation, upper-bound
---


# Question
Title: Sorting an array of length $n$ with $k$ distinct elements
There is an integer array that contain $n$ numbers, in the array there are $k$ distinct elements up to $k = 50$.
Is it possible to sort this array in linear time, by using only comparisons?

I know that comparison sorts cannot perform better than $\mathcal O(n\log n)$, so maybe I have to show a sort function that sort this array in less than $\mathcal O(n\log n)$, and it will be a contradiction.

# Answer
> 5 votes
Consider quicksort with $w$ unique values, where the pivot is taken arbitrarily from the list. In the worst case the pivot will be an extrema (either the minimum or maximum of the list), and so the algorithm will recurse for $w-1$ and 1, and a list of 1 unique value is already sorted.

As the time complexity is linear, $O(n)$, for each pass, and the number of passes is in worst case the number of unique values, $O(w)$, then the time complexity is $O(nw)$, which for constant $w=50$, is $O(n)$

# Answer
> 1 votes
In O (n log k + k^2) you can trivially create an array with all distinct values in the array, for each k the indices of all array elements equal to k. And then you can create the sorted array in another O (n) operations.

So for k with a fixed upper bound, yes, it's easily done in linear time. If k can vary with n, and k is a lot larger than $n^{1/2}$ then you need a slightly more clever algorithm.

# Answer
> 0 votes
Create an AVL tree with nodes containing unique integers as keys and their respective counts then simply do inorder traversal

Since there are k distinct integers , the height of tree will grow upto atmost k , evenif k is unknown Each insertion or updation will take logk time , and building this tree will take nlogk Initial insertion is with count 1, if node already exists then simply increment the count of that key Inorder Traversal is O(n) Total time is O(nlogk) You can't do better than O(nlogk) (if k is not known, and without finding k) AVL Sort is best.

If k is known priori or found, then it's O(n) with bucket or count sort. You can determine k in O(n) too

---
Tags: algorithms, sorting
---


# Question
Title: Confused with the proof that Edmonds-Karp always monotically increases the shortest-paths
The proof for the lemma from "Introduction to Algorithms by Cormen et. al." is not clear for me. I can't comprehend a few things. Here is a lemma and its proof. My questions are below.

> The notation $\delta(u, v)$ is used to denote shortest-path from $u$ to $v$.

---

---

**Question 1:**

> Because of how we chose $v$, we know that the distance of vertex $u$ from the source $s$ did not decrease, i.e., $\delta\_{f'}(s, u) \geq \delta\_{f}(s, u)$

Why the shortest-path from $s$ to $u$ after the augmentation of flow $f$ must be **greater than** or equal to the distance before the augmentation ? How it is possible to have greater distance that it was ? The augmentation only removes the edge $(u, v)$. But, the vertex $u$ still in place, isn't it must be strictly equal ?

**Question 2:**

> If we had $(u, v) \in E\_f$, then we would also have $\delta\_f(s,v) \leq \delta\_f(s, u) + 1$

This looks like ok for me to have such case. We claim that distance from $s$ to $v$ is less than or **equal** to the distance from $s$ to $u$ plus 1. But in the graph before the first augmentation this case must be true. It is false for **less than** case, but true for **equal** case.

**Question 3:**

> How can we have $(u, v) \notin E\_f$ and $(u, v) \in E\_{f'}$ ? The augmentation must have increased the flow from $v$ to $u$. The Edmonds-Karp algorithm always augments flow along shortest paths, and therefore the shortest path from $s$ to $u$ in $G\_f$ has $(v, u)$ as its last edge.

The edge set $E\_f$ is before the first augmentation and $E\_{f'}$ is after it. The first augmentation must remove the edge $(u, v)$ and put the **reverse** edge $(v, u)$ into the edge set $E\_{f'}$, but not the same edge $(u, v)$. That is why how we can have $(u, v)$ in $E\_{f'}$ ?

# Answer
> 1 votes
# Answer to Question 1:

> Because of how we chose , we know that the distance of vertex from the source did not decrease, i.e., ′(,)≥(,)
>
> Why the shortest-path from to after the augmentation of flow must be greater than or equal to the distance before the augmentation ? How it is possible to have greater distance that it was ? The augmentation only removes the edge (,). But, the vertex still in place, isn't it must be strictly equal ?

Because in the Proof, "We will suppose that for **some** vertex $v \in V - \left \\{ s, t\right \\}$, there is a flow augmentation that causes the shortest-path distance from $s$ to $v$ to decrease". So, if we consider $u$ is the opposite type compared to $v$, that is to say, the shortest-path distance from $s$ to $u$ does not decrease: equation (26.13) $\delta \_{f'}\left ( s,u \right )\geq \delta \_{f}\left ( s,u \right )$ holds.

Of course, if you suppose that $u$ is same type as $v$, which has decreasing shortest-path distance from $s$ to $u$, then we can take $u$ to replace the $v$, and find the path, $p:s\rightarrow x \rightarrow u$, where $\delta \_{f'}\left ( s,x \right )\geq \delta \_{f}\left ( s,x \right )$ holds. In this case $x$ takes the place of $u$ in eq(26.13).

# Answer to Question 2:

> If we had (,)∈, then we would also have (,)≤(,)+1
>
> This looks like ok for me to have such case. We claim that distance from to is less than or equal to the distance from to plus 1. But in the graph before the first augmentation this case must be true. It is false for *less than* case, but true for equal case.

If the shortest path from $s$ to $v$, $p\_v: s\rightarrow u \rightarrow v$ **overlaps** with the shortest path from $s$ to $u$, $p\_u: s\rightarrow u$, the equal case happens. $\delta\_f(s,v)=\delta\_f(s,u)+1$.

If the two paths $p\_v$ and $p\_u$ are not overlapped, the shortest path from $s$ to $v$, $p\_v: s \rightarrow v$ would not contain the node $u$. Since $p\_v$ is the shortest path, obviously the length of $p\_v$ should be shorter than the length of $p\_u$ \+ $(u,v)$ (another path from $s$ to $v$). Therefore the *less than* case happens: $\delta\_f(s,v)\<\delta\_f(s,u)+1$.

# Answer to Question 3:

> How can we have (,)∉ and (,)∈′ ? The augmentation must have increased the flow from to . The Edmonds-Karp algorithm always augments flow along shortest paths, and therefore the shortest path from to in has (,) as its last edge.
>
> The edge set $\_$ is before the first augmentation and $\_{′}$ is after it. The first augmentation must remove the edge (,) and put the reverse edge (,) into the edge set $\_{′}$, but not the same edge (,). That is why how we can have (,) in $\_{′}$ ?

$(u,v)\notin E\_f$ and $(u,v)\in E\_{f'}$ mean that the newly augmentation augments flow (a cancellation flow for $(u,v)$) along the edge $(v, u)$. Recall that, augmentation happens on the shortest path, which means that $(v,u)$ is on the shortest path $p$ from $s \leadsto v \rightarrow u \leadsto t$. If $p$ overlaps with the shortest path from $s \leadsto u$, $\delta \_{f}\left ( s,v \right ) = \delta \_{f}\left ( s,u \right )-1$ holds. However I am not sure now that the overlapping does happen.

# Answer
> 0 votes
**To answer fist question**: notice that we chose v whose distance did change and that has the smallest new distance. If u's distance did change after the augmentation, then we could have picked u instead of v because its new distance is smaller than that of v but since we chose v, we know that u's distance after augmentation could not have decreased. Makes sense?

---
Tags: correctness-proof, network-flow
---


title: Why do we use CYK algorithm?

text:
# Question
Title: Why do we use CYK algorithm?
Why do we use the CYK algorithm? In my book is written that with CYK algorithm you can faster see if a word is generated by a given Grammer. However I dont get it, because I need like 5 min in order to divide the word into other subwords.. and so on and only few seconds just to derive the word using the predicates.

# Answer
> 0 votes
We use CYK algorithm to check whether the give string is present in the given context free language or not.

By using the CYK algorithm we can check the string belongs to given CFL or not.And also we can find the substrings of that string present in that language.

The process used in the CYK algorithm is

1.Construct a table DP for size n × n.

2.If w = e (empty string) and S -\> e is a rule in G then we accept the string else we reject.

3.For i = 1 to n:

For each variable A:

```
 We check if A -> b is a rule and b = wi

```

for some i:

```
    If so, we place A in cell (i, i) of our table.

```

4.For l = 2 to n:

For i = 1 to n-l+1:

```
   j = i+l-1

    For k = i to j-1:

       For each rule A -> BC:

    We check if (i, k) cell contains B and (k + 1, j) cell contains C:

         If so, we put A in cell (i, j) of our table.

```

5.We check if S is in (1, n):

If so, we accept the string

Else, we reject.

# Answer
> 0 votes
As Wikipedia states:

> The importance of the CYK algorithm stems from its high efficiency in certain situations.

In particular, its relevance is that it allows parsing an arbitrary context-free grammar, with running time that is polynomial in the input size (in particular, cubic in the input size). Many other parsing strategies cannot handle arbitrary context-free grammars.

There are other parsing strategies that are typically faster in practice, including ones that can handle arbitrary grammars, but CYK is particularly simple and has this nice property of being able to handle an arbitrary grammar, so it is handy to present in an introductory class.

---
Tags: formal-languages
---


# Question
Title: Comparing a greedy and a brute force algorithm for NMS
Hello I am trying to implement Non Max suppression algorithm for removing overlapping bounding boxes. I have a list of bounding detected by an object detector in the format B(x,y,w,h,s) x,y are coordinates, w,h are size, and s is confidence score. Aim of NMS is to remove overlapping boxes and retaining only ones with high confidence score.

For that I came across 2 approaches:

1. Brute Force approach: Compute IOU (Intersection-over-Union, a metric to measure overlap) of every two boxes in the list. For every pair having IOU greater than threshold, remove the box with low confidence score
2. GreedyNMS: Sort the list in descending order of score. pick the box with highest score and discard all the boxes overlapping with highest one with IOU\> threshold. Repeat till end of the list.

I found that the greedy approach this way does not give same result as Brute force. It fails to remove boxes with low score which have low overlap with highest scored box.

Now here is my issue, I came up with a modified version of the above GreedyNMS. I traverse the list in ascending order. This gave me same results as brute force for all the cases I tested. But I am trying to establish that both give exactly same result theoretically.

# Answer
> 1 votes
Your description of the problem and your solutions are not very accurate. I will rephrase as follows: "any rectangle that has a sufficient overlap with another rectangle of a higher score must be discarded".

With this interpretation, you have to proceed by *increasing scores*, to make sure that you don't discard a rectangle *before* you compare it to lower ones.

---
Tags: algorithms, greedy-algorithms
---


# Question
Title: Is there a faster algorithm than FFT if interested only on the maximum amplitude frequency?
Given an $n$ input array, is there an algorithm that is faster than Fast Fourier Transform if we are only interested in obtaining the maximum amplitude frequency?

Looking at the Cooley–Tukey algorithm it seems there would be a way to "prune" frequencies that are guaranteed to not be of maximum amplitude.

The application seems common enough that some other people might have already worked on a similar problem.

I am both interested in algorithms that are time-complexity-wise faster and practically faster through small "shortcuts" arising from this particular problem.

Is there such an algorithm?

# Answer
Partial FFT and Sparse FFT can exploit an expected range of said maximum.

Practically, the range of frequencies over which the maximum may occur is often known. There are also approaches to estimate said location. These are signals, not algorithms questions.

Generally, the maximum can occur anywhere. That is also a signals question. The FFT is merely a fast computation of the Discrete Fourier Transform, so the place to look is Fourier theory.

> Cooley–Tukey ... seems there would be a way to "prune" \[non-maximum\] frequencies

FFT devotes equal compute to all bins, and bin amplitude isn't known before computation is complete. If there's a way to conditionally "intercept" the computation, it'll likely add way more compute than it saves - even when the interval is known ahead of time (as in the two linked algos), the savings are marginal. Put simply, the FFT is *brutally* fast for what it computes - it's not just math, but hardware optimizations.
> 5 votes

---
Tags: time-complexity, fast-fourier-transform
---