# Question
Title: Correctness of Linearizability vs Sequential consistency in replication
I'm currently studying Sequential consistency vs linearizability:

I know that SC has to be consistent with the order of how the individual client issued them, and for linearizability, it's with the real-time ordering.

What I don't understand is:

"The interleaved sequence of operations meets the specification of a (single) correct copy of the objects. "

Which is the first property of both Sequential consistency and linearizability

For me, it sounds like that if 2 clients communicate with some system, the state of the objects should be the same on a single server and on a system with multiple replica managers RM.

But if that is true, how is this example SC:

Client 1:

SetBalance x in RM B to 1

Client 2:

getBalance y in RM A = 0 getBalance x in RM A = 0

Client 1:

SetBalance y in RM A to 2

But if the above example is true, that means my understanding of "The interleaved sequence..." is wrong. since that would imply that the second get balance of client 2 should be 1 ( but at the same time, that means that the system is linearizable since that follows real-time ordering).

So what does:

"The interleaved sequence of operations meets the specification of a (single) correct copy of the objects. "

Mean? and why is it used to determine the correctness of replication

# Answer
> 0 votes
A Sequential Consistent (SC) system should behave as if there is just a single copy of the data.

So lets try to determine a possible memory order for your scenario:

```
1:client2:read(y=0)
2:client2:read(x=0)
3:client1:write(x=1)
4:client1:write(y=2)

```

This is valid according to SC. Keep in mind that the real time order of requests, doesn't need to preserved. So perhaps the client2.read(x=1) happened later than the client1.write(x=1), it can be ordered in the memory order before the write.

Lets change the example a bit to make it more interesting:

```
1:client1:write(x=1)
2:client1:write(y=2)
3:client2:read(y=2)
4:client2:read(x=0)

```

This example isn't SC because the read of x=0, doesn't see the most recent write before it in the memory order. It should have seen x=1. And this is the consequence of the lack of coherence (so what you could get with replicas being out of sync).

---
Tags: distributed-systems
---


title: Time complexity for FPT algorithm

text:
# Question
Title: Time complexity for FPT algorithm
I'm studying the issue of FPT algorithms and came to the k-disjoint triangles problem as can be seen here on slide 60.

The problem summary is given a graph G and variable k, are there k disjoint triangles in the graph. There are two methods, I want to focus on one of them. (Method 1)

First I randomly color the graph in 3k colors and then go over each permutation of colors and check whether there are k triangles with distinct colors.

What I fail to understand is what the time complexity of such examination (going over all the possible permutations) and how exactly can it be done?

# Answer
> 1 votes
Suppose that you have a graph and each vertex is colored with one of three colors, and let the set of different-colored vertices be $A, B, C$.

Now, try to find a triangle with one vertex from each partition. For each vertex $a \in A$, try let $B\_a$ and $C\_a$ be $a$'s neighborhood in $B$ and $C$, respectively. Now you only need to check if there is an edge from $B\_a$ to $C\_a$. If there is one, you have your triangle, otherwise, you try another vertex from $A$.

Let us call this subroutine `colorful_triangle(G, A, B, C)`. Observe that it is not necessary that $A \cup B \cup C = V(G)$.

---

Let $G$ be the graph, $\chi$ the coloring and $\pi$ a permutation of colors.

Let $\chi(i)$ be the set of vertices that received color $i$.

Now let $A = \chi(\pi(1))$, $B = \chi(\pi(2))$, $C = \chi(\pi(3))$. Run the subrouting `colorful_triangle(G, A, B, C)`. If successful, continue with $A = \chi(\pi(4))$, $B = \chi(\pi(5))$, $C = \chi(\pi(6))$, and so on.

If you at some point are unsuccessful, move on to the next permutation.

---
Tags: time-complexity, colorings, parameterized-complexity
---


# Question
Title: Turing Machine that triples a unary format number?
I managed to figure out how to double a unary format number however I have had no such success in tripling it. An input tape would be of the following format Λ111Λ and the output would be like Λ111Λ111111111Λ with the tripled number coming directly after the initial input tape. Any help would be greatly appreciated.

# Answer
Copy the number once (as you have done already). Mark the spot between the original and the copy with a new letter. Now run again the copy, but stop copying once you see the letter $\land$.

That is, copy $\land 111\land$ into $\land 111 \\# 111 \land $. Now copy again, while thinking of $\\#$ as the new beginning of the tape. You will get $\land 111 \\# 111 \\# 111 \land$. After that, replace all $\\#$ with $\land$ to get: $\land 111\land 111\land 111\land$

Notice that this process can be done any number of times, meaning that you can clone the input any number of times you would like!

---

Also, as a general "trick" for such problems, try introducing either a new letter to the alphabet (it usually helps create edge cases that you need to solve), or to meddle with an existing machine's states (such as adding an index into their states, etc')
> 0 votes

---
Tags: turing-machines
---


# Question
Title: Are single complements the same as seperate complements?
Is **(A' + B')** the same as **(A + B)'** ?

*Note: The apostrophe ( ' ) represents the complement*

# Answer
> 1 votes
No. As a counterexample pick $A=0$ and $B =1$. Then: $$ A' + B' = 0' + 1' = 1 + 0 = 1 \neq 0 = 1' = (0 + 1)' = (A+B)'. $$

---
Tags: logic
---


# Question
Title: What is the difference between designing an algorithm that solves a problem and creating a TM that decides a language?
Question: What is the difference between designing an algorithm that solves a problem and creating a Turing machine that decides a language?

A turing machine "decides" the language if it "accepts" the language and enters a rejecting state for any input not in the language.

Don't really know what the difference is

# Answer
Depending on the problem, there might not be any difference.

If the problem's goal is to answer a yes/no question, then there is no difference; accepting the input is equivalent to answering yes, and rejecting is equivalent to answering no.

However, if the goal of your problem is to output something else (e.g., output a number), then it is not identical to deciding a language. There are still ways to formulate a corresponding language, but the correspondence is not quite as direct.

To learn more, see https://en.wikipedia.org/wiki/Decision\_problem, https://en.wikipedia.org/wiki/Function\_problem, https://en.wikipedia.org/wiki/Optimization\_problem, https://en.wikipedia.org/wiki/Formal\_language.
> 1 votes

---
Tags: algorithm-analysis
---


title: Turing decidable languages

text:
# Question
Title: Turing decidable languages
On an old worksheet I came across the question

> If L1 and L2 are two Turing decidable languages, then show that 12 and 12 are Turing decidable languages (high-level description with stages is enough).

How do I go about answering this without being given a language to work from?

# Answer
> 1 votes
Both $L\_1$ and $L\_2$ are decidable. Hence, they have algorithms $A\_1$ and $A\_2$ (respectively) that decide them.

Try to create a new turing machine (algorithm) using the two algorithms $A\_1$ and $A\_2$.

For example, for the union $L\_1\cup L\_2$, you can create the following algorithm:

* run $A\_1$ on the input. If it accepted, then also accept.
* else, run $A\_2$ on the input, and return what $A\_2$ returned.

---
Tags: formal-languages, turing-machines
---


# Question
Title: How does data compression relate to the ordinary meaning of “compression”?
When I think about "compressing" outside computers I can think about a compressed car which has become a metal rectangle.

* It doesn't have *less redundancy* because it has everything it had before, just compressed and destroyed (data loss)
* It's not *delivered more efficiently* because it's destroyed and isn't restorable by any technology I know of

Perhaps the very terminology of "compression" is just misleading; is there a CS theory in which an alternative term was suggested and if so what is this term?

# Answer
> 3 votes
The ordinary meaning of “compression” is to make something smaller. The meaning of “compression” in computer science is also to make something smaller.

To compress data means to make it take less space. Removing redundancy is a *method* for compressing, it isn't the definition of “compression”. The reason it's often said removing redundancy allows data to be compressed comes from the intuition of *information*. A piece of data has a certain information content. Computer science (a branch of which is called informatics) studies information and its representation. If there are different ways to convey the same information through data, i.e. different data representations for the same information, a compression process tries to find a way to represent the data that is smaller than the original representation. Since the compressed representation is smaller than the original representation, but it has the same information content, in some sense, the original data had parts that were superfluous.

This intuition is not completely precise. Strictly speaking, the superfluous parts were not necessarily redundant in the sense of repeating information from the non-superfluous parts. They were, however, redundant in the broader sense of not being necessary. Furthermore, it is not necessarily possible to identify specific parts that are redundant. There is no general rule that compression has to look for redundant parts: it's just one way to do it, which often works. **Redundancy is a technique, not the definition**.

“Delivering more efficiently” is not related to the science of compression at all. If a system has an efficiency bottleneck that is due to the size of the data (typically transmission costs), then reducing the size of the data through compression makes the system more efficient. **It is not always the case that compression makes delivery more efficient**. There are systems where the processing time spent compressing and decompressing is larger than the transmission time saved by compression.

Part of the question is due to a misconception about English: that “compressing” something somehow implies destroying it. It is actually rare that compressing something destroys it. For example, from the Cambridge Dictionary online:

> to press something into a smaller space:
>
> > Firmly compress the soil in the pot so that the plant is secure. compressed air

> to make information, a piece of writing, etc. shorter:
>
> > The course compresses two year's training into six intensive months. I managed to compress ten pages of notes into four paragraphs.

From an Oxford dictionary via Lexico:

> 1 Flatten by pressure; squeeze or press.
>
> > ‘the skirt can be folded and compressed into a relatively small bag’
>
> 1.2 Squeeze or press (two things) together.
>
> > ‘Viola compressed her lips together grimly’
>
> 1.3 Express in a shorter form; abridge.
>
> > ‘in this chapter we compress into summary form the main findings’

(I included all the given definitions and examples for “compress” + noun, excluding technical meanings.) Note that none of them necessarily require anything to be destroyed. Note also that the meaning of expressing information in a shorter way is not related to computer science; it predates computers.

On a final note, data compression *can* destroy some information. Compression is called ***lossless*** if it allows the recovery of the original and ***lossy*** otherwise. Lossy compression removes some information from the data, whereas lossless compression can be said to only remove redundancy (but it can be well-hidden redundancy).

---
Tags: data-compression
---


# Question
Title: Proving Undecidability with reductions - Why do some proofs not use an Oracle?
I'm specifically referring to this group of questions here: https://www.cs.rice.edu/~nakhleh/COMP481/final\_review\_sp06\_sol.pdf

So as I've learnt it, say we want to prove a new Language L is undecidable using a known undecidable language D, we use Oracle calls to L to solve an instance of D right?

In none of these questions is an oracle used - For example, with L9 :"M' on input w: it runs M on x and accepts if M halts on x" That's the algorithm; no oracle is used. I understand the reasoning to their solutions, but shouldn't they be using an oracle call? I'm very new to this so sorry if I'm misunderstanding

# Answer
An oracle call is stronger than emulating a TM: it allows you in constant time to solve the task of checking if some $x$ is in the language specified by the oracle.

What you saw didn't use oracle machines, since it proved by assuming towards contradiction: It assumed there is a machine $M$, and showed how to use its code in order to build a new machine $M'$ solving a problem that can't be solved - hence $M$ doesn't exist.
> 1 votes

---
Tags: formal-languages, turing-machines, automata, reductions, undecidability
---


# Question
Title: Algorithm for finding strongest connection for a user on social network
I am working on Problem 6-1 from MIT's Fall 2011 6.006 course. The problem reads as:

> Problem 6-1. \[30 points\] I Can Haz Moar Frendz?

> Alyssa P. Hacker is interning at RenBook (人书 / 人書 in Chinese), a burgeoning social network website. She needs to implement a new friend suggestion feature. For two friends `u` and `v` (friendship is undirected), the ***EdgeRank*** `ER(u, v)` can be computed in constant time based on the interest `u` shows in `v` (for example, how frequently `u` views `v`’s profile or comments on `v`’s wall). Assume that EdgeRank is directional and asymmetric, and that its value falls in the range (0, 1). A user `u` is ***connected*** to a user `v` if they are connected through some mutual friends, i.e., $u = u\_0$ has a friend $u\_1$, who has a friend $u\_2$, . . . , who has a friend $u\_k = v$. The integer `k` is the ***vagueness*** of the connection. Define the ***strength*** of such a connection to be $$S(p) = \prod\_{i=1}^kER(u\_{i−1}, u\_i)$$ For a given user `s`, Alyssa wants to have a way to rank potential friend suggestions according to the strength of the connections `s` has with them. In addition, the vagueness of those connections should not be more than `k`, a value Alyssa will decide later.

> Help Alyssa by designing an algorithm that computes the **strength** of the strongest connection between a given user `s` and **every other user** `v` to whom `s` is connected with vagueness at most `k`, in `O(kE + V)` time (i.e., for every pair of `s` and `v` for `v ∈ V\{s}`, compute the strength of the strongest connection between them with vagueness at most `k`). Assume that the network has `|V|` users and `|E|` friend pairs. Analyze the running time of your algorithm. For partial credit, give a slower but correct algorithm. You can describe your algorithm in words, pseudocode or both.

After reading the problem, the first intuition I got is to:

* Do a BFS from the source node `s` and stop the BFS as soon as `k`th level is reached.
* And, while doing the BFS, calculate and maintain the strength that each node encountered has with `s`
* At the end, when the BFS stops after the `k` levels, we iterate the strengths stored, and find the one with maximum value.

Here is the (pseudo/Python)code for the same:

```
def find_strongest_connection(graph, source_node, k):
    nodes_discovered = deque()

    # source is already discovered
    strengths = {source_node: 1}
    parents, levels = {source_node: None}, {source_node: 0}
    nodes_discovered.append(source_node)

    while nodes_discovered:
        parent_node = nodes_discovered.popleft()

        current_level = levels[parent_node] + 1
        if current_level > k:
            break

        for current_node in graph.adj[parent_node]:
            if current_node not in levels:
                # current_node is now discovered
                strengths[current_node] = strengths[parent_node] * ER(parent_node, current_node)
                parents[current_node], levels[current_node] = parent_node, current_level
                nodes_discovered.append(current_node)

    strongest_connection, max_strength = None, -1
    for connection, strength in strengths.items():
        if strength > max_strength:
            max_strength = strength
            strongest_connection = connection

    return strongest_connection, max_strength

```

To me, this solution looks correct. But when I was going through the solutions provided by MIT for the problem set, I see they are first transforming the graph, and then applying the Bellman-Ford's algorithm. What I want to know is that am I missing something really basic in my understanding of the problem and the algorithm that I have come up with?

I am asking this because seeing the complex solution provided in the solution set is making me doubt my overly simple solution. Unfortunately, I cannot think of a case, where my solution would fail. If there is any issue with my algorithm, any hint would be much much appreciated.

PS: I am not a student looking for an answer to my homework. I am a full time working professional.

# Answer
> 2 votes
Your algorithm doesn't work. BFS doesn't explore all paths. One of the paths you haven't explored might have much higher strength than all the ones you have explored. There exists a counterexample with only four or five nodes (depending on the exact details of how you implement the steps outlined in your overview). I'll let you have the fun of finding it.

---
Tags: algorithms, graphs, time-complexity, shortest-path, breadth-first-search
---


title: Parse forest from an ambiguous grammar

text:
# Question
Title: Parse forest from an ambiguous grammar
Parser-generators like `nearleyjs` can return a parse forest instead of a parse tree.

Since not all input may result in a parse forest *(eg, the input may exercise only a non-ambiguous subset of the grammar)*, how do you programmatically choose the 'correct' parse tree from the forest?

One option is to always choose the first element from the array of parse-trees returned.

Another option is to flag the returning of a parse-forest (instead of a single tree) as an error. But then, this would defy the whole point of having Earley-like parsers that allow parsing of ambiguous grammars!

Also, since only some input may result in a parse-forest (instead of a single parse-tree), how do you rule out surprises in a live/Production environment? *Assumption: For non-trivial or non-trivially long grammars, it's not humanly possible to create tests that cover all inputs.*

# Answer
> 2 votes
To use such a parser, you need some external way to select among the possible trees in the forest. Typically there are additional constraints beyond what is encoded in the context-free grammar, which can be used to identify the correct parse. In other words, there are some rules that are part of the syntax (they are part of the context-free grammar, and thus handled by the parser), and some rules that are part of the semantics; there may be multiple parses that are compatable with the syntax rules, and then the semantic rules are used to select which one complies with the semantic rules.

---
Tags: parsers, ambiguity
---


title: Undecidable or Decidable

text:
# Question
Title: Undecidable or Decidable
In a typical data structures class, we look at a variety of problems: finding an element in a list, sorting a list, balancing a binary search tree, finding the shortest paths in a graph, etc. Would these problems be decidable or undecidable?

Wouldn't the answer to this question be both, because decidable means a clear yes/no answer and undecidable would mean that there is no clear answer to the question.

# Answer
If there is an algorithm, it is decidable. Its impossible for something to be not decidable and decidable at the same time. Take a look at the formal definition of a decidable language.
> 0 votes

# Answer
Some of those problems are decidable. Many of them are neither decidable nor undecidable.

Some problems are decision problems; some are not. If you have a decision problem, you can ask whether it is decidable or not. Most decision problems that you'll see in a data structures class will have an algorithm that terminates in a finite amount of time, so they'll be decidable. For other kinds of problems (not a decision problem), you can't ask whether they are decidable; the notion of "decidable" isn't even defined. There is a related notion of computability which is broader than decidability.

See https://en.wikipedia.org/wiki/Computability#Problems.
> 0 votes

---
Tags: algorithms, algorithm-analysis
---


# Question
Title: Should your heuristic for an A* search algorithm be the same scale as your actual weights?
I'm a bit confused about the scale of heuristics for implementing A\* search. $f(n)$ is the total cost of travelling to a node $n$. It is calculated by $f(n) = g(n) + h(n)$. $g(n)$ is the cost of the path to node $n$ from the source node. $h(n)$ is a heuristic function that estimates the cost of the cheapest path from n to the goal. (Roughly summarised from the wikipedia article on A\*)

My question is should $h$ and $g$ be on the same scale? e.g. if g(n) to node n is 10 is it ok if the h(n) is 800?

I've read some conflicting takes on it where one example of using A\* for plane routes had $g$ values in the range of 10-50 but $h$ values in the range 100 - 900 but elsewhere I read that they should be the same scale to avoid changing an A\* search into a greedy best first search?

# Answer
> 1 votes
They can't possibly be on the same scale throughout the search, if by that you mean that $g(n) \approx h(n)$ for every node encountered near the search. Near the start, you'll have $g(n) \approx 0$, so $g(n) \ll h(n)$. Near the goal node, you'll likely have $h(n) \approx 0$, so $h(n) \ll g(n)$.

On the other hand, it *is* possible to have the range of values for $g$ (min across all nodes, to max across all nodes) to be similar to the range of values for $h$ (min across all nodes, to max across all nodes). That is a good property. In particular, the range of $g(n)$ will be from 0 to the distance to the goal; if $h(n)$ is perfect (exactly accurate), it will have the same range.

If $h(n) \ll g(n)$ throughout the search (i.e., for all nodes $n$), then the search becomes similar to Dijkstra's algorithm (in particular, if $h(n)=0$ everywhere, then it is devolves to exactly Dijkstra's algorithm).

If $g(n) \ll h(n)$ throughout the search (i.e., for all nodes $n$), then the search becomes similar to a greedy best first search using only $h(n)$ (in particular, if $g(n)=0$ everywhere, it devolves to exactly greedy best first).

# Answer
> 2 votes
I think you might have misunderstood the heuristic function. It is supposed to give an *underestimate* on the distance from a node $n$ to the goal node $t$. The closer this estimate is to the true value, the better A\* will perform.

The only criterion for the heuristic function is that it never gives a higher value for $h(n)$ than the true cost of going from $n$ to $t$.

Let $\text{dist}(a, b)$ be the "true" distance from $a$ to $b$, and let $\text{dist}\_0(a,b)$ be an underestimate (e.g. the Euclidean distance from $a$ to $b$ if you have a map).

If you are searching for a path from $s$ to $t$, then $g(n)$ is defined to be $\text{dist}(s, n)$, whereas $h(n)$ is $\text{dist}\_0(n, t)$. So $$ \text{dist}(s, n) + \text{dist}\_0(n, t) = g(n) + h(n) = f(n).$$

There is nothing about *scale* of $g(n)$ and $h(n)$, except that $h(n)$ must give a lower value than (or equal to) the true distance from $n$ to $t$.

---
Tags: algorithms, search-algorithms, a-star-search
---


title: Proving that a language is a CFL

text:
# Question
Title: Proving that a language is a CFL
Assume that $L\_1 \subseteq \Sigma^\*$ is a CFL and that $y \in \Sigma^∗$ is a string.

I need to prove that the language $L\_2 = \\{x \in L\_1 \mid x \text{ does not contain $y$ as substring}\\}$ is a CFL.

I tried pumping lemma for CFLs, but it seems that is for disproving that languages are CFLs. I also tried to create a CFG for this language, but I'm having a hard time. I even took a look at the membership problem for CFGs.

Any ideas on how I would go about proving this?

# Answer
> 1 votes
The language $L' = \Sigma^\* y\Sigma^\*$ is regular and, by the closure properties of regular languages, so is $\Sigma^\* \setminus L'$. Then, by the closure properties of context-free languages, $L\_2 = L\_1 \cap (\Sigma^\* \setminus L')$ is context-free (since it can be written as the intersection of a context free language with a regular language).

# Answer
> 0 votes
In general if you want to prove that a language is CF, even if in this case the solution proposed by Steven is shorter and more elegant, you can see if there is a PDA that accepts it, even though it my be tough not only to find it but also to formally prove it accepts every string of the language.

---
Tags: formal-languages, automata, context-free
---


title: Proving Quicksort is $O(n^2)$

text:
# Question
Title: Proving Quicksort is $O(n^2)$
So I'm trying to figure out why the worst case of Quicksort is $O(n^2)$.

I know this a very well known problem, but the funny thing is where ever I look (even Wikipedia) gives the following explanation: "The worst case is the most unbalanced case where the problem splits to a problem of size $n-1$ and a problem of size $0$ (i.e. when the array is already sorted)".

Then they use the master theorem and find it is $O(n^2)$.

Marvelous. So simple. But wait.

Do we know upfront that the worst case is $O(n^2)$? No, that's what we need to prove.

"The most unbalanced case" meaning it is the worst case? Is there any theorem that states this?

So what is actually a coherent proof that Quicksort is $O(n^2)$?

Or in other words, what is the proof for the missing part?

We can derive that the run time can be described as $T(n) = T(n\_1) + T(n\_2) + O(n)$ where $n\_1 + n\_2 + 1 = n$. How to prove $T(n)$ is the largest when $n\_1 = 0$ and $n\_2 = n-1$?

I already know this is the most unbalanced case. Why is it actually the worst case?

# Answer
> 2 votes
The running time of quicksort satisfies the recurrence $$ T(n) \leq \max\_{n\_1+n\_2+1=n} T(n\_1) + T(n\_2) + Cn, $$ with base cases of $T(1) = C$ and $T(0) = 0$, say. Let us now prove by induction that $T(n) \leq Cn^2$. The base cases obviously hold. As for the inductive step, \begin{align} T(n) &\leq \max\_{n\_1+n\_2+1=n} C(n\_1^2 + n\_2^2) + Cn \\ &= \max\_{0 \leq m \leq n-1} C(m^2 + (n-1-m)^2) + Cn \\ &= C(n-1)^2 + Cn + \max\_{0 \leq m \leq n-1} 2Cm(m-(n-1)) \\ &\leq C(n-1)^2 + Cn \\ &\leq Cn^2. \end{align}

---

Why is the worst case when $n\_1 \in \\{0,n-1\\}$? This is because the function $n^2$ is *convex*, that is, the maximum of $x^2+(n-x)^2$ over $x \in \[0,n\]$ is attained at one of the endpoints. In more complicated situations, we could trying showing this *directly*, by inductively showing that $T(n+2)-T(n+1) \geq T(n+1)-T(n)$, which should imply (I think) that the maximum of $T(n\_1)+T(n\_2)$ is attained at one of the endpoints.

---
Tags: data-structures, runtime-analysis, sorting, quicksort
---


# Question
Title: Asymptotics of of $T(n) = n + T(n - \sqrt{n})$
What is the asymptotic rate of growth of the following recurrence?

$$ T(n) = n + T(n - \sqrt{n}). $$

Since I cannot use the Master's Theorem here, I could not figure it out the answer. My initial guess is $n^{3/2}$, but I'm not sure.

Can anyone help me? What are the big-O and big-Omega complexities here?

# Answer
You can get a lower bound of $\Omega(n^{3/2})$ as follows. Consider the number of steps it takes to get from $n$ to $n/2$. Since at each step, $n$ decreases by at most $\sqrt{n}$, this takes at least $\sqrt{n}/2$ steps. At each such step, we accumulate at least $n/2$, for a total of at least $n^{3/2}/4$.

You can prove a matching upper bound using a similar approach. While the input parameter is at least $n/2$, it decreases by at least $\sqrt{n/2}$, and so it takes at most $\sqrt{n/2}$ steps to get to $n/2$. During each such step, we accumulate at most $n$, for a total of at most $n^{3/2}/\sqrt{2}$. An identical argument shows that at most $(n/2)^{3/2}/\sqrt{2}$ is accumulated while going from $n/2$ to $n/4$, and so on. Hence $$ T(n) \leq \frac{n^{3/2}}{\sqrt{2}} \left(1 + \frac{1}{2^{3/2}} + \frac{1}{4^{3/2}} + \cdots\right) = O(n^{3/2}), $$ since the geometric series inside the parentheses converges.

Numerical experiments suggest that $$ T(n) \sim \frac{2}{3} n^{3/2}. $$ We can show this heuristically as follows. Let us imagine that $T$ is a recurrence in continuous time. Then $T(n) - T(n-\sqrt{n}) \approx \sqrt{n} T'(n)$, and so $$ T'(n) \approx \sqrt{n}. $$ Integrating, we get $$ T(n) \approx \frac{n^{3/2}}{3/2} = \frac{2}{3} n^{3/2}. $$ This can probably be showed by running the argument above more carefully (replacing $n/2$ with $(1-\epsilon)n$).
> 3 votes

---
Tags: asymptotics
---


# Question
Title: MOOC recommendations for learning algorithms based on topics covered in Daspupta, Papadimitriou & Vazirani
I would appreciate some advise/mentoring on self-study of algorithms. Based on my several years of work as a software developer (non CS background), I have some good grip on standard data structures (linked lists, stacks etc.) and basic sorting and searching algorithm characteristics (time/space complexity).

My goal of learning is to take my knowledge to next level (learning graph theory and advanced algorithm techniques such as dynamic and linear programming) to be able to use it in a variety of situations incl. AI and computationally complex domain problems.

So I purchased 2 books -- Algorithm Design Manual from Skiena and Algorithms by Dasgupta et al. I am aware of the usual advice of CLRS, but decided to skip it for now as my goal at this stage is not proofs.

Now my question is: even though I found the style of writing of Dasgupta book rather appealing, topic is often difficult for unguided, unsupervised learning.

Are there any recommendable online courses (free or otherwise) which would cover topics from Dasgupta book? In general, I found the topics covered in Stanford Algorithm specialization (coursera and edX) rather good, but any further options would be helpful!

# Answer
While I cannot answer your question (MOOC for Dasgupta et al), I will make a different recommendation.

Since you seem to like the more intuitive and slightly informal approaches to learning, rather than the more formal and proof oriented approach, I think you might like the algorithms book series by Tim Roughgarden, Algorithms Illuminated.

Algorithms Illuminated is a book series of four books,

1. Part 1: The Basics
2. Part 2: Graph Algorithms and Data Structures
3. Part 3: Greedy Algorithms and Dynamic Programming
4. Part 4: Algorithms for NP-Hard Problems

The books are reasonably priced, and on the plus side, Roughgarden has made a series of videos that can be found on the aforementioned website for the books.

In addition, he has a series of lectures that have appeared as edX and coursera courses on his videos site.
> 2 votes

# Answer
I would like to share the fruits of my course research for any future references.

If you are an absolute beginner and don't mind doing implementation in Java, then two free courses from Princeton Uni. in Coursera are a good start. Part 2 covers more advanced topics. Instructor Sedgewick is a well known author of an Algorithm book. The book has an accompanying website.

Another good option would be the course from Stanford mentioned in the answer provided above, though that one costs a 40$ subscription per month if you want full features. The advantage is also that you can code in any language you want.

A third option from Coursera is a specialization from UC San Diego which is also a paid course.

MIT OCW also has an algorithm course, using CLRS as the textbook.

If you are reading Dasgupta et al. and want to be supported, then check nowhere else than https://cs170.org/
> 1 votes

---
Tags: algorithms, education, books, reference-question
---


title: Induction on recursive formula

text:
# Question
Title: Induction on recursive formula
I have this recursive formula

$$T\left(n\right)=T\left(\frac{n}{2}\right)+O\left(n\right)+O\left(n\right)+2O\left(1\right) \ \ \ ➜ \ \ \ T\left(n\right)=T\left(\frac{n}{2}\right)+O\left(n\right)$$

$$T\left(n\right) =T\left(1\right)\ +\ c\_{2}n\cdot\sum\_{k=1}^{⌊\log n⌋}\frac{1}{2^{k}}=T\left(1\right)+c\_{2}(n-1)$$

I've been trying for a few hours to prove its correctness by induction, I feel like I've tried everything. The closest I got was defining $n=2^{x}$ and proving the correctness for every $x$, but I can't seem to get the right answer. How do you prove something like that?

The main question is how do I prove $T(n) = T(n/2) + c\_{2}n = T(1) + c\_{2}(n-1)$.

# Answer
The series $\frac{1}{2^k}$ is a geometric progression. Hence, $\sum\_{k=0}^m \frac{1}{2^k} = \frac{1-\left(\frac{1}{2}\right)^m}{1-\left(\frac{1}{2}\right)}$

You can continue from here.
> 1 votes

---
Tags: recursion, induction
---


# Question
Title: Expected behavior of the maximum ranking generated in optimal assignment
Suppose n students have preferences over n different notebooks. Their preferences can be represented with a square matrix of size n where each column is a different permutation of the vector \[1:n\], where the first entry in the column represents the most desirable notebook for student 1, and so on. We are interested in the assignment of the notebooks to students that minimizes the sum of rankings.

For example, such allocation in the problem below

1 2 2

2 1 3

3 3 1

would be the allocation (1,2,3) with a ranking sum of 1+1+2=4.

My question is the following. If the matrix with preferences is chosen uniformly at random, what is the expected maximum ranking in the assignment that minimizes the sum of rankings? In the example above, this is 2. I am interested in the maximum value that occurs in expectation if one of the possible matrices is chosen uniformly at random.

Simulations show that for n=100, this is 6.44 and for n=200 this is 7.04.

See Expected behavior of an algorithm to minimize rankings for further details.

# Answer
Frieze and Sorkin showed that in the optimal solution of the assignment problem with weights chosen uniformly in $\[0,1\]$, the maximal value is $\Theta\bigl(\frac{\log n}{n}\bigr)$.

This suggests that the answer in your case is $\Theta(\log n)$.

I found this reference in the survey of Krokhmal and Pardalos mentioned in my answer to your original question. I suggest consulting the survey on your own for any further questions.
> 3 votes

---
Tags: algorithms
---


title: Definition of RP/poly is not clear!

text:
# Question
Title: Definition of RP/poly is not clear!
In Motwani and Raghavan's textbook, p38-39, they states:

> A sequence $C\_1, C\_2, C\_3, \dots$ of circuits is a circuit family for function $f\_n\colon {0,1}^n \rightarrow \\{0,1\\}$ if $C\_n$ has $n$ inputs and computes $f\_n(x\_1, x\_2, \dots, x\_n)$ at its output for all n-bit inputs $(x\_1, x\_2, \dots, x\_n)$. The family $C$ is said to be polynomial-sized circuits if the size of $C\_n$ is bounded above by $p(n)$ for every $n$, where $p(\cdot)$ is polynomial.

It is clear that this is the definition of P/poly. And the next paragraph is the definition of RP/poly.

> A randomized circuit family for $f$ is a circuit family for $f$ that, in addition to the $n$ inputs $x\_1, x\_2, \dots, x\_n$, takes $m$ random bits $r\_1, r\_2, \dots, r\_m$, each of which is equiprobably 0 or 1. In addition, for every $n$, the circuit $C\_n$ must satisfy two properties:
>
> 1. If $f\_n(x\_1, x\_2, ..., x\_n)=0$, then the output of the circuit is 0 regardless of the values of random inputs $r\_1, r\_2, \dots, r\_m$.
> 2. If $f\_n(x\_1, x\_2, ..., x\_n)=1$, the the output of the circuit is 1 with probability at least $\frac12$. In other words, at least one half of the $2^m$ choices of the bits $r\_1, \dots, r\_m$ will result in the circuit evaluating to 1. We will refer to such $m$-tuples $r\_1, r\_2, \dots, r\_m$ as witnesses for $(x\_1, x\_2, \dots, x\_n)$, in that they testify to the correct value of $f\_n(x\_1, x\_2, \dots, x\_n)$ when it is 1.

Question: I don't understand what is relationship between $n$ and $m$ or $r\_1, \dots, r\_m$ and $f\_n(x\_1, x\_2, \dots, x\_n)$? For example, we have n inputs, i.e. $x\_1, x\_2, \dots, x\_n$. But, in second property, they states that at least one half of the $2^m$ choices of the bits $r\_1, \dots, r\_m$ will result in the circuit evaluating to 1. Now, how did we bring $r\_1, \dots, r\_m$ to $f\_n(x\_1, x\_2, \dots, x\_n)$?

# Answer
The circuit $C\_n$ has $n+m$ inputs, $x\_1,\ldots,x\_n,r\_1,\ldots,r\_m$. Its size is polynomial in $n$, so without loss of generality, $m$ is polynomial in $n$. What we want is:

1. If $f\_n(x) = 0$ then $\Pr\_r\[C\_n(x,r) = 0\] = 1$.
2. If $f\_n(x) = 1$ then $\Pr\_r\[C\_n(x,r) = 1\] \ge 1/2$.

Here $x$ is shortcut for $x\_1,\ldots,x\_n$, and $r$ is shortcut for $r\_1,\ldots,r\_m$.
> 2 votes

---
Tags: complexity-theory, randomness
---


# Question
Title: Example on Referential transparency (wikipedia)
I have a rather foolish question on an example explaining the idea behind Referential transparency

Here is given an example i not understand:

> Consider a function that returns the input from some source. In pseudocode, a call to this function might be *GetInput(Source)* where Source might identify a particular disk file, the keyboard, etc. Even with identical values of Source, the successive return values will be different. Therefore, function *GetInput()* is neither deterministic nor referentially transparent.

I'm confused about the claim that even with identical values of (variable) *Source*, the successive return values will be different.

Eg if I tap an 'a' on my keyboard and apply *GetInput(Source)*, it gives my 'a' as output. Then I tap again an 'a', which of course is identical to my previuos input. Next application of *GetInput(Source)* gives me again 'a'.

Therefore I not understand how is it possible that *GetInput(Source1)* and *GetInput(Source2)* might give different values if the two imputs *Source1* and *Source2* are identical. Sorry, if it's too dumb, but I not understand this quoted example.

# Answer
> 1 votes
If *Source* refers to the keyboard, and the user types `a` the first time but `b` the second time, then *GetInput(Source)* will not return the same value both times.

It's impossible to replace *GetInput(Source)* by its value without changing the meaning of the program, because there are many possible values, depending on the actions of the user. To replace *GetInput(Source)* with `a` would be wrong if the user decides to press `b`.

An example of a consequence of the fact that *GetInput(Source)* is not referentially transparent is that if the program calls this twice, which call returns `a` and which calls return `b` depends on the order in which the calls are evaluated (or more precisely, on the order in which the calls get their input from the keyboard: you have to get down to this level of detail to be sure).

---
Tags: functional-programming, coding-theory, imperative-programming
---


# Question
Title: How can i prove that this language is not turing-recognizable?
I'm having difficulty understanting how can i prove that

L = { w | w0 is the representation of a turing machine M with input {0, 1} and M don't accept w } is not turing-recognizable

The solution I have is by contradictio.

1. Reduce w0 to w
2. Suppose a TM M', L(M') = L
3. Suppose that w' ∈ L
4. w' is the representation of a turing machine
5. If w' ∈ L then w' ∉ L is false

I can't understand step 4, why w' is the representation of a turing machine?

# Answer
Use the definition of $L$. You are told that $w' \in L$; what does that mean? Based on the definition of $L$, this tells you something about $w'$.
> 0 votes

---
Tags: turing-machines
---


# Question
Title: Reduction from SUBSET-SUM to 0-1-INT-PROG
The 0-1-INT-PROG problem is given an integer $m \times n$ matrix $A$ and an integer $m$-vector $b$, is there an integer $n$-vector $x$ with $A \cdot x \leq b$.

I am trying to prove that 0-1-INT-PROG is NP-Hard by reducing SUBSET-SUM to it.

**My attempt:**

Given an instance of SUBSET-SUM $\<\\{a\_1, a\_2, \cdots, a\_n\\}, k\>$ we construct an instance of 0-1-INT-PROG $\<\[a\_1, a\_2, \cdots, a\_n\], \[k\]\>$.

**Claim:** $\<\\{a\_1, a\_2, \cdots, a\_n\\}, k\> \in $ SUBSET\_SUM if and only if $\<\[a\_1, a\_2, \cdots, a\_n\], \[k\]\> \in $ 0-1-INT-PROG.

*proof of forward direction.* When there exists a subset $S' \subseteq S$ whose sum is $k$, for each $a\_i \in S'$, let $x\_i = 1$. If $x\_i \not \in S'$, then $x\_i = 0$. Then $x$ is an $n$-vector which achieves $\[a\_1, a\_2, \cdots, a\_n\] \cdot x = k$. So $\<\[a\_1, a\_2, \cdots, a\_n\], \[k\]\> \in $ 0-1-INT-PROG.

**Question:**

When I have tried to prove the other direction I run into a problem. Namely, just because there exists an $x$ vector with $\[a\_1, a\_2, \cdots, a\_n\] \cdot x \leq k$, does not imply that there exists a subset $S' \subseteq S$ whose sum is $k$, because of the less than or equals to.

So how can I approach the backwards direction?

# Answer
Let $\langle S, k \rangle$ be an instance of subset sum, where $S=\\{a\_1, a\_2, \dots, a\_n\\}$. Construct an $0$-$1$-integer program with $n$ binary variables $x\_1, \dots, x\_n$ and the following constraints:

$$ \begin{align} a\_1x\_1+a\_2 x\_2+ \dots+a\_n x\_n &\le k \\ -a\_1x\_1-a\_2 x\_2 - \dots-a\_n x\_n &\le -k \end{align} $$

Or, in matrix form: $A = \begin{bmatrix} a\_1 & a\_2 & \dots & a\_n \\ -a\_1 & -a\_2 & \dots & -a\_n \end{bmatrix}$ and $b=\begin{bmatrix} k \\ -k\end{bmatrix}$.

If you have a solution $S' \subseteq S$ to the subset sum instance, then you can pick $x$ as the characteristic vector of $S'$ to satisfy the constraints (as you correctly point out in your question). I.e., set $x\_i = 1$ if and only if $a\_i \in S'$ so that $Ax = \begin{bmatrix} k \\ -k\end{bmatrix} = b$.

On the other hand, if $Ax \le b$ then the first constraint is $a\_1 + a\_2 + \dots + a\_n \le k$ and second constraint implies $a\_1 + a\_2 + \dots + a\_n \ge k$. Then, we necessarily have $a\_1 + a\_2 + \dots + a\_n = k$, showing that $S' = \\{ a\_i \mid x\_i = 1\\}$ is a solution to the subset sum instance.
> 1 votes

---
Tags: np-complete, integer-programming, subset-sum, polynomial-time-reductions
---


# Question
Title: What is the time complexity of a linear search performed using 2 pointers?
For an array, I'm using a left pointer (pointing to 0) and a right pointer (pointing to end).

For every iteration, if my search element is not found, I increment left and decrement right. This iteration continues until `left <= right`. Find the code snippet below

```
left = 0
right = length - 1

while left <= right:
    // search logic
    left += 1
    right -= 1

```

What will be worst the time complexity of this algorithm?

Also, is this a type of linear search?

# Answer
> 0 votes
$O(n)$, since you still will go through the entire array.

And yes, this is a linear search since $O(n)$ is linear.

---
Tags: algorithms, time-complexity, arrays
---


# Question
Title: Addition errors in IEEE754 floating point representation
So in class, we were talking about the idea of floating point precision in IEEE754 format, and how, when some numbers are added, precision is lost. My professor then gave the following example of a large absolute error between what we think the answer might be, and what the answer actually is when our program (written in Java) actually compiles it:

$0.4 \times10^{30} + 1.1 \times10^{30}$

Compiling this in Java, i get $1.5000001 \times 10^{30}$

My question is, why does this happen? Printing out the IEEE754 format of the two numbers, I get:

$\space\space\space0\[11100010\]10111100010010010101011=+1.10111100010010010101011\times2^{99}$ $+0\[11100001\]01000011000111100001000=+1.01000011000111100001000\times2^{98}$

So, I suppose when you add these, you end up loosing precision, but exactly how? Moreover, how can I even tell, before adding, that the addition of two numbers will make them loose precision? Or is the only way to just plus into a program and see what happens? None of this was really covered in class unfortunately.

# Answer
> 1 votes
> Printing out the IEEE754 format of the two numbers, I get:
>
> $\space\space\space0\[11100010\]10111100010010010101011=+1.10111100010010010101011\times2^{99}$ $+0\[11100001\]01000011000111100001000=+1.01000011000111100001000\times2^{98}$

Compare the exact values:

$$ 1.1011110001001001010101011000111111010110011111001110000010110110100111 \times 2^{99} \\ 1.0100001100011110000011111010111001101101011100100001011111001010101 \times 2^{98} $$

Observe that both of the numbers are already rounded to represent them in IEEE 754, and it happens that both of them have rounded up.

Also note that since the values have different exponents, they've been rounded at different places.

Now add the rounded values:

```
  1.10111100010010010101011 ×2<sup>99</sup>
+ 0.101000011000111100001000×2<sup>99</sup>
 -------------------------------
 10.01011101110110000101111 x2<sup>99</sup>
 11  1         1111

```

There's overflow, so the answer will have exponent $2^{100}$ and we have to round. *Again*, we're rounding up, to $1.00101110111011000011000\times2^{100}$.

> So, I suppose when you add these, you end up loosing precision, but exactly how?

You will nearly always lose precision when adding two floating point numbers. If they're both positive and have the same exponent, the output will have a larger exponent and you lose some bits from the end. If they have different exponents, the smaller one will lose bits from the end. And if they have opposite signs and the same exponent, the output has a smaller exponent and you lose precision because you need bits beyond the end which were lost earlier. Essentially the only cases where you don't lose precision are when you add a number to itself, or when the input numbers and the result can all be represented exactly in the width of the type.

# Answer
> 0 votes
You were using single precision floating point numbers. Single precision floating point numbers look like this: You start with a mantissa, which is a number 1 ≤ m \< 2 which is a multiple of $2^{-23}$, then you multiply by a power of 2, then you multiply by +1 or -1.

So when you write 0.4e30, that is not a possible floating-point number at all. Instead, you get the floating-point number closest to 0.4e30. So we have an error. And we have another error in 1.1e30. What you are adding is really the floating-point number closest to 0.4e30, plus the floating-point number closest to 1.1e30.

Now 0.4e30 has a smaller exponent than 1.1e30. If you add the two numbers, then the two last bits of 0.4e30 *must* be lost. So you add not quite the numbers you think you are adding, and you get an error during the rounding. If by coincidence the last two bits of 0.4e30 were both zeroes, then there's no rounding error.

There are some cases where we know there is no rounding error: If you add x+y, and x, y, and x+y are all integers up to 2^24, then you can prove that you will get the correct result with zero rounding error. If you subtract x-y where x and y are positive numbers and x/2 ≤ y ≤ 2x, then you can also prove that there is no rounding error. If you add a zero then there is no rounding error. But usually you just assume there will be a rounding error, and it will be up to one half of the value of the last mantissa bit of the result.

---
Tags: arithmetic, floating-point, error-estimation
---


# Question
Title: Motivation for Inverse Reinforcement Learning
Learning a policy from sparse reward information (a reward function where a positive reward is only generated at the goal state) is challenging due to the resulting sparse feedback.

One solution is to shape the reward to enrich feedback during learning. Unfortunately, shaping the reward is challenging and often leads to unusual behavior or even situations where the learning agent just harvests intermediate rewards rather than achieving the task.

A proposed solution is to have an expert generate demonstrations of the desired task and have the learning agent learn a reward function that is consistent with the demonstrated behavior. The learning agent can then use this learned reward function to learn an optimal policy.

This last point is where I am confused. The whole motivation for IRL is **learning**, that is, finding a policy when the model is unknown, but why would the learning agent not know its own transition model? On the other hand, if the transition model is known, then finding the optimal policy from the learned reward function is not actually a learning problem.

# Answer
Often the transition model is not known in advance. For instance, consider a complex system like flying a helicopter or surfing a surfboard. It's not easy to characterize in advance what the behavior of the system will be, in response to certain control inputs; the relationship may be highly nonlinear and complex.
> 0 votes

---
Tags: reinforcement-learning
---


# Question
Title: If $f(n)=O(g(n))$ can I say there exists a $n_0$ for a specific $c$?
I've been working on an asymptotic proof and I want to start with saying that since $\log z=O(z)$ then $\log z\le\frac1 9z$ for $z\ge z\_0$. In this example I'm picking $c=\frac1 9$ and hoping $z\_0$ exists, but is $z\_0$ guaranteed to exist if I pick $c$?

# Answer
Let's take as an example $f(n) = g(n) = n$ and $c = 1/2$. Does there exist an $n\_0$ such that $f(n) \leq cg(n)$ for all $n \geq n\_0$?

In your case, you know more: $\log n = o(n)$. This means that $$ \lim\_{n\to\infty} \frac{\log n}{n} = 0, $$ which implies that for every $c$ there exists $n\_0$ such that $\frac{\log n}{n} \leq c$ for all $n \geq n\_0$.
> 1 votes

---
Tags: asymptotics
---


# Question
Title: Can a graph with more than |V| - 1 edges have the maximum weighted edge as part of its MST?
Consider a graph graph G with |V| vertices and more than |V|-1 edges, is it possible for an edge to be the 'heaviest' and also be unique, but still be part of the graph's MST? If so, in which cases is it applicable?

From what I've been thinking so far, if the maximum edge is the only part that connects some vertex with the rest of the tree, it has to be part of the MST regardless, but that is regardless of the constraint of having more than |V| - 1 edges.

So am I correct to assume that, having more than |V| - 1 edges you can have the heaviest edge as part of the MST? Also, why is the constraint of edges being more than |V| - 1 applied here, what purpose does it serve?

Thanks.

# Answer
Consider the following example:

You can clearly see that the heaviest edge (connecting vertices 3 and 4) is in any MST of this graph. In general, the heaviest edge (assuming it is unique) will be part of the MST of a graph if and only if it is a bridge (meaning that if we remove that edge the graph gets disconnected). The condition $|E| \geq |V| - 1$ doesn't really change anything. However, in order for MST to make sense, we need the graph to be connected. Note that $|E| \geq |V| - 1$ **does not** guarantee that.
> 1 votes

---
Tags: graphs, minimum-spanning-tree
---


# Question
Title: Which would be better for programming using Homotopy type theory Agda or Idris
I'm looking to model data inputs for an artificially intelligent system, which is affected by its internal parts and has feedback loops. I'd like to model it mathematically, using category theory or homotopy type theory.

Is Agda or Idris the best choice for such modelling?

# Answer
Agda is definitely the better choice if you're doing Homotopy Type Theory.

1. Idris has several features that are specifically incompatible with HoTT. Specifically, you can use dependent pattern matching to prove Uniqueness of Identity Proofs (UIP), which, when combined with Univalence, allows you to prove False. There's also a type-case feature which you can use to directly prove False from univalence.
2. Agda has some features that are specifically designed to enable HoTT. Namely, it has a `--without-K` option, which ensures that you can't prove UIP or the related Axiom K. There's also a whole language extension for Cubical Type Theory, which uses a special notion of equality gives computational meaning to univalence.

Relevant reading:

Introduction to Univalent Foundations in Agda

Pattern Matching without K

Proof-relevant Unification in Agda

Cubical Agda Paper

Cubical Agda documentation

Cubical Agda tutorial
> 3 votes

---
Tags: programming-languages, type-theory, homotopy-type-theory, agda, higher-inductive-types
---


title: Proving a problem is NP Hard

text:
# Question
Title: Proving a problem is NP Hard
Consider the following problem: Given a weighted directed graph $G$, determine if $G$ has a cycle whose total weight is $k$. All edge weights are integer but might be negative. $k$ is not an inputted value. It's fixed and known beforehand to everyone. So $k$ is NOT an input to this algorithm.

I want to show the problem is NP hard, so this means I have an oracle that tells me whether or not a graph has a cycle whose sum of edge weights equals $k$ for a fixed, known value of $k$.

I thought about reducing from Hamiltonian cycle. So I want to show that I can use this oracle to solve Hamiltonian cycle problems.

Let $G$ be a graph. I want to see if $G$ has a Hamiltonian cycle. I try to construct a new graph to provide to the oracle but I'm not sure how to do so. I think it needs to have $k$ vertices so I tried doing casework on when $G$ has more or less than this many vertices.

I can show that I can solve Hamiltonian cycle problems with $k$ vertices by constructing a new complete graph where edge weights are $1$ if it was in the original graph and a really large nunber otherwise. Then running the oracle on this graph returns true only if there's a Hamiltonian cycle with $k$ vertices. But this doesn't handle the general case. Is this proof fine?

But I'm stuck. Any help is appreciated.

# Answer
> 1 votes
Let $G$ be a graph with $2n$ vertices, and choose any node $v$. The edges touching $v$ have weight $n$, and all other edges have weight $-1$. Note that any Hamiltonian cycle in $G$ will have two edges touching $v$ (which add up to $2n$) and $2n-2$ edges of weight $-1$, so the total weight of the cycle is exactly $2$. Therefore, if $G$ has a hamiltonian cycle, it has a cycle of weight exactly $2$.

Moreover, assume $G$ has a cycle of weight exactly $2$. Such a cycle can either include $v$ or not. If it doesn't include $v$, all its edges will be negative, contradicting a total weight of $2$. If it includes $v$, then it must include two edges of weight $n$, and thus the remaining part of the cycle must be a path, using only edges of weight $-1$, and with total weight equal to $-2n+2$. That meeans such a path must contain $2n-2$ edges, and therefore have $2n-1$ nodes. When connecting said path to-and-from $v$, you have a Hamiltonian cycle.

This means that if you could decide in polynomial time whether $G$ has a cycle of weight $2$ (which is a fixed constant), you could decide whether it has a Hamiltonian cycle in polynomial time.

# Answer
> 0 votes
If $k$ is a fixed known value and does not depend on the graph, then I doubt it would be possible to do it efficiently:

Verifying if a graph has a cycle of size $k$ can be done by checking all potential paths of size $k$ and verify if one is indeed a cycle. Since there are at most $\begin{pmatrix}n\\k\end{pmatrix}(k-1)! = O(n^k)$ such path in a graph of order $n$, and the verification is done in $O(k) = O(1)$, such an algorithm would be polynomial in the size of the graph (but obviously not in $k$).

---
Tags: np-complete, reductions, np-hard, np, decision-problem
---


# Question
Title: $\omega$-automata where string is accepted iff a final state is accessible from starting state
I am wondering if $\omega$-automata with the following acceptance condition are valid.

An input string is accepted iff one of the final states occurs at least once.

This differs from Buchi automata in that the final state only has to occur *once*, not infinitely often.

Does this kind of automata have a name? Is it interesting or important?

# Answer
Yes, it was studied before. In one of the early papers on accepting infinitary languages Landweber introduced five acceptance types that included those of Büchi and Muller. On the lowest level where two types that referred to the set of states entered, and the other three levels considered the more classic set of states entered infinitely often.

Your type is called 1-acceptance (if I recall right) and a string is accepted if a state from an accepting set $D$ is entered *at least once*. The dual 1'-acceptance required that the states entered are *always* within $D$. One level up one requires that a state from $D$ is entered *infinitely often* (Büchi), respectively that *from some moment on* the states are within $D$.

These definitions can be considered not only for finite state automata, but also for automata with external storage, like pushdown automata. One common fact for all such automata is that the 1-acceptance (your type) is of low "topological" complexity. Those $\omega$-languages are of the form $L\cdot \Sigma^\omega$, where $L$ is an ordinary language of the type of automata. This means one cannot accept $(a^\*b)^\omega$.

In general there is a clear link between topological complexity of the $\omega$-language and the acceptance type.

L.H. Landweber, Decision problems for $\omega$-automata, Math. Systems Theory 3 (1969) 376-384.
> 4 votes

---
Tags: automata, finite-automata, omega-automata
---


# Question
Title: Space complexity of a variant of st-connectivity
Consider a variant of STCON, called 2STCON, which is defined like this:

$$2STCON = \\{\langle G,u,v \rangle \\} \mid \text{$G$ is a graph with } \mathit{two} \text{ paths from $u$ to $v$} \\} $$

This means the only difference to the "normal" STCON is that there are two paths instead of just one between $u$ and $v$.

I need to show that 2STCON belongs to NL.

What is the best way to approach this problem?

# Answer
> 0 votes
The usual proof that STCON is in NL works as follows: you guess a path from $u$ to $v$, and verify it step by step.

A very similar proof works for 2STCON: you guess two paths from $u$ to $v$, and verify them step by step. As you verify them, you also verify that they are different: either the length is different, or the $i$-th vertex is different, for some $i$.

---
Tags: complexity-theory, graphs, space-complexity
---


# Question
Title: Is there an structure that allows for a flat representation of trees with constant access to any element?
One can, for example, represent 2d arrays such as:

```
[[1,2],[3,4],[4,5]]

```

as flat arrays:

```
[1,2,3,4,5,6]

```

as long as he transforms the indices before accessing:

```
index(x,y) = x + y*2 // because internal width=2

```

This is often faster. My question is: is it possible to use a similar approach of representing an structure as a flat array, for, instead of n-dimensional tables, free-form trees such as:

```
[[1,2,3],4,[5,[6,7]],8]

```

# Answer
> 3 votes
Well, it depends a bit on the operations. You cannot do anything reasonable if you want to realize you data structure inside an $n$-elementary array. The 2d array works, since there is a bijection between the 2d array entries and the 1d array entries. There is also such a bijection for any fixed tree, but I think this is not what you are looking for.

Notice that your tree decoding \[\[1,2,3\],4,\[5,\[6,7\]\],8\] also uses more structure than a normal 1d array. So if you ask for data structures of size $O(n)$ with $O(1)$ operations than you can actually do something.

One idea is to use a array where you store the DFS-tour (sometimes called Euler tour) of your tree, and the information about the time when you discover and when you finished a vertex in the DFS search. This can be stored inside an array of size $4n$ plus another $n$ for the values at the nodes, and it allows you to navigate through the tree using $O(1)$ operations per step.

With more involved data structures you can also answer level ancestor queries (what is the $i$-th vertex about vertex $x$?) or lowest common ancestor queries in constant time with a data structure of size $O(n)$. If you want to know more about these two data structures, look up the references in wikipedia.

# Answer
> 1 votes
No, it does not seem to be possible, if there are no constraints on the shape or size of the tree.

(If you are able to impose some strict requirements on the structure of the tree, there are known methods. For instance, heaps are one example of exactly this optimization, applied to a particular kind of binary tree. However, I realize this doesn't address your request for a data structure for free-form trees.)

Since you care about performance, it is also important to understand that performance depends not solely upon the number of memory accesses, but also upon locality: how well those accesses play with caches. Cache-friendly data structures are not studied as much in typical undergraduate data structures classes, but they have been studied extensively in other contexts (e.g., databases).

# Answer
> 1 votes
Yes and no. If the structure of your tree has a known maximum depth and constant structure, you can statically calculate a matrix that defines the transform of `I` indexes to a single linear index in k time. Calculating this matrix, though, requires `I*N` time for `N` elements.

# Answer
> 0 votes
I'd rather make this a comment, but I don't have enough reputation.

I feel like you should provide more information of what is expected from the structure. Like what kind of access you need, and what kind of operations are going to be performed, etc.

For example, you have already provided one of the flat structures for a general tree. Notice, that brackets \[\], represent your subtrees as a continuous ranges in the array. You can utilize that if you need to access the whole subtrees in constant time.

Also, as answered by sqykly, if the graph is constant you can pre-calculate the transform I. If the tree allows dynamic changes to its structure, you should be able to update your transform in sub-linear time.

# Answer
> 0 votes
**Yes, you can** represent tree structure in flat list.

One example in world of databases is called **Closure Table Pattern**.

It lets you get all ancestors or all childs of specific node without using recursive query. Best article (the most simple and straightforward) I found is: https://towardsdatascience.com/closure-table-pattern-to-model-hierarchies-in-nosql-c1be6a87e05b

The only missing thing in above article is exact definition of create, delete and update parent of node, but you can deduce it basing on image that contains tree structure and table of Ancestors and Descendants.

---
Tags: algorithms, data-structures
---


# Question
Title: How to show working for summing of Big O notation
The equation below is intuitively correct, but how do you show that this is actually the case? What is the working out needed?

$$\sum\_{i=1}^{n-1}O(\lg n)=O(n\lg n)$$

# Answer
Summand inside sum is not depend on summation index, then pull it out and you have n−1 before log.

**Addition 1**.

I specially copy above @plop's comment in case to keep it:

> The equation is not correct in general. For example, $i\ln(n)\in O(\ln(n))$, but $\sum\_{i=1}^{n-1}i\ln(n)=\frac{n(n-1)}{2}\ln(n)\notin O(n\ln(n))$.

Now about error in this reasoning: it's mistake to write $i\ln(n)\in O(\ln(n))$, when $i$ is in range from $1$ to $n$. In such case $i$ is not constant, but dependent on $n$. Obviously for each $i$ we have such $j$ for which $i=n-j$, but, hope, is clear that sentence $(n-j)\ln(n)\in O(\ln(n))$ is false. There is also some other subtle and very important detail, which I'll write in next addition - I beg pardon for mentioned in comment below "nearest days", but I have it almost ready and "hope in nearest days I'll find time to write it down".

**Addition for silent down voters**.

Down voting without argumentation doesn't help neither OP, neither readers, nor writers and nor this site - I sincerely welcome anyone who openly criticizes any proposal I wrote. An open, professional discussion of issues and responsibility for own words is the best friend and helper in our work. Dear down voter, I thought for a long time before writing Addition 1., I even found similar considerations in well-known sources (let's not name them for now) - do you have something to say/write?
> -3 votes

# Answer
So expanding on what zkutch said in their answer, we can take out the $O(lgn)$ from the summation as follows: \begin{equation} \begin{split} \sum\_{1}^{n-1} 1 \cdot O(lgn) &= O(lgn) \cdot \sum\_{1}^{n-1} 1\\ &= O(lgn) \cdot (1 + 1 + ... +\_{n-1~times})\\ &= O(lgn) \cdot (n - 1)\\ &= O(nlgn) \end{split} \end{equation} And hence arrive at the answer you intuitively assumed is correct.
> -3 votes

---
Tags: algorithm-analysis, asymptotics, big-o-notation
---


# Question
Title: For a set of points P, connected by weighted edges (distances) I need a path through all points while minimizing the travel on any edge longer than X
For a given set of coordinates (lat/lng) I need a path which will visit each coordinate only once. The path needs to be selected to minimize the number of times the haversine distance between two subsequent points along the path is greater than X (ex: 200 miles).

The practical application:

I have airports on a map. I have a string of LED lights which are connected by a fixed distance of wire between them. I want the optimal path between all the airports where I minimize the number of times I need to splice additional wire into the string.

Suggestions on the approach? Maybe some type of genetic algorithm implementation?

# Answer
> 2 votes
Create a graph from the airport coordinates where edges have the haversine distance as weights. Since the graph is a *metric graph*, you can apply Christofides algorithm. This algorithm is a $\frac 3 2$-appoximation, which means that it gives a solution which is not worse than 50% longer than the optimal.

However, since you want to also minimize the number of long edges, you can remove all edges that are longer than you would like, *but* you now have a non-metric graph (it does no longer satisfy the triangle inequality).

One related problem is the Bottleneck traveling salesman problem, in which you want to find a Hamiltonian path that minimizes the longest edge. Since your original graph is a metric graph, you can apply the 2-approximation to get an algorithm in which the longest edge is not more than twice possible.

---

Since you seem to be set on using genetic algorithm, you can consider using both of these algorithms for seeding the initial pool for the GA. Run both algorithms many times to get many different solutions (introduce some randomness), and you might have a very good starting pool.

# Answer
> 0 votes
Build a graph with one vertex per point. Add an edge of length 0 between a pair of vertices $v,w$ if they are at most $X$ distance apart; otherwise add an edge of length 1. Then, use any existing algorithm for the travelling salesman problem in this graph. Solving the TSP in this graph will solve your problem. There are many algorithms, heuristics, etc., including many software packages you can download that implement them for you. (Note that this TSP instance will be an instance of metric TSP, which may enable some algorithms that take into account that additional structure.)

This could reasonably be called an instance of (0,1)-TSP. I have not been able to find any papers in the literature on (0,1)-TSP, though I have found several on approximation algorithms for (1,2)-TSP.

---
Tags: graph-traversal, traveling-salesman, genetic-algorithms
---


title: sum of array with O(1)

text:
# Question
Title: sum of array with O(1)
I have an array of n elements. Smallest element that exists in the array is x and the largest element is x+n. None of the numbers between x to x + n is missing from the array. i need an algorithm to get the sum of all numbers in the array provided that x is already known. The time complexity of this algorithm should be O(1).

# Answer
Since you strictly want $O(1)$, you can just do the math and get that $$\sum\_{i\ \in \ Array}i=\sum\_{i=x}^{x+n} i =\sum\_{i=1}^{x+n}i\ -\sum\_{i=1}^{x-1}i =\frac{(x+n)(x+n+1)}{2}-\frac{(x-1)(x)}{2}$$

I do not see any iterative way to do it as you require the runtime to be $O(1).$
> 1 votes

# Answer
Adding to @Djrocks192s answer, we can also calculate it like that:

$$\sum\_{i=x}^{x+n} i = \sum\_{k=0}^n x+k = nx + \sum\_{k=0}^n k = nx + \frac{n(n+1)}{2}$$
> 1 votes

---
Tags: algorithm-analysis
---


# Question
Title: Adding two numbers in base 2(floating point) vs Multiplying two numbers in base 2(floating point)
Is it true that adding two numbers in base 2 is more complex than multiplying them? If so can someone please explain why this is the case?

# Answer
> 1 votes
Floating point numbers are stored as $x \cdot 2^e$, where typically $1 \leq x \< 2$ (unless your number is denormalized). When multiplying $x \cdot 2^e$ and $y \cdot 2^f$, we simply compute $xy \cdot 2^{e+f}$ (we have to truncate $xy$). When adding $x \cdot 2^e$ and $y \cdot 2^f$, we first have to shift one of the numbers (the one with smaller exponent) so that we have a "common denominator". For example, to add $1 \cdot 2^0$ and $1 \cdot 2^{-3}$, you have to rewrite the latter as $0.125 \cdot 2^0$.

Whether this makes addition more complex than multiplication is a matter of opinion. Multiplying $x$ and $y$ is still harder than addition.

# Answer
> 0 votes
The straightforward algorithm for addition is more complicated than the straightforward algorithm for multiplication. For addition, you need to compare the exponents, shift the mantissa of the operand with smaller exponent, add or subtract (the signs might be different) and then check for overflow or check for an unnormalised result. Lots of complicated steps.

For multiplication, you multiply the mantissas, normalise the product of mantissas, check for overflow and under flow. Much simpler.

However, the number of operations for the multiplication is much higher, quadratic for typical fast hardware implementations. It’s just easier to describe.

---
Tags: computer-architecture, arithmetic, floating-point
---


# Question
Title: Why, really, is the Halting Problem so important?
I don't understand why the Halting Problem is so often used to dismiss the possibility of determining whether a program halts. The Wikipedia article correctly explains that a deterministic machine with finite memory will either halt or repeat a previous state. You can use the algorithm which detects whether a linked list loops to implement the Halting Function with space complexity of O(1).

It seems to me that the Halting Problem proof is nothing more than a so-called "paradox," a self-referencing contradiction in the same way as the Liar's paradox. The only conclusion it makes is that the Halting Function is susceptible to such malformed questions.

So, excluding paradoxical programs, the Halting Function is decidable. So why do we hold it as evidence of the contrary?

**4 years later**: When I wrote this, I had just watched this video (**update**: the video has been taken down). A programmer gets some programs, must determine which ones terminate, and the video goes on to explain that it's impossible. I was frustrated, because I knew that given some arbitrary programs, there was some possibility the protagonist could prove whether they terminated. I knew many real-life algorithms had already been formally proven to terminate. The concept of generality was lost somehow. It's the difference between saying "some programs cannot be proven to terminate," and, "no program can be proven to terminate." The failure to make this distinction, by every single reference I found online, was how I came to the title for this question. For this reason, I really appreciate the answer that redefines the halting function as ternary instead of boolean.

# Answer
> 244 votes
Because a lot of really practical problems are the halting problem in disguise. A solution to them solves the halting problem.

You want a compiler that finds the fastest possible machine code for a given program? Actually the halting problem.

You have JavaScript, with some variables at a high security level and some at a low security level. You want to make sure that an attacker can't get at the high security information. This is also just the halting problem.

You have a parser for your programming language. You change it, but you want to make sure it still parses all the programs it used to. Actually the halting problem.

You have an anti-virus program, and you want to see if it ever executes a malicious instruction. Actually just the halting problem.

As for the Wikipedia example, yes, you could model a modern computer as a finite-state machine. But there's two problems with this.

1. Every computer would be a different automaton, depending on the exact number of bits of RAM. So this isn't useful for examining a particular piece of code, since the automaton is dependent on the machine on which it can run.
2. You'd need $2^n$ states if you have n bits of RAM. So for your modern 8GB computer, that's $2^{32000000000}$. This is a number so big that wolfram alpha doesn't even know how to interpret it. When I do $2^{10^9}$ it says that it has $300000000$ decimal digits. This is clearly much too large to store in a normal computer.

The Halting problem lets us reason about the relative difficulty of algorithms. It lets us know that, there are some algorithms that don't exist, that sometimes, all we can do is guess at a problem, and never know if we've solved it.

If we didn't have the halting problem, we would still be searching for Hilbert's magical algorithm which inputs theorems and outputs whether they're true or not. Now we know we can stop looking, and we can put our efforts into finding heuristics and second-best methods for solving these problems.

UPDATE: Just to address a couple of issues raised in the comments.

@Tyler Fleming Cloutier: The "nonsensical" problem arises in the proof that the halting problem is undecidable, but what's at the core of undecidability is really having an infinite search space. You're searching for an object with a given property, and if one doesn't exist, there's no way to know when you're done.

The difficulty of a problem can be related to the number of quantifiers it has. Trying to show that there exists ($\exists$) an object with an arbitrary property, you have to search until you find one. If none exists, there's no way (in general) to know this. Proving that all objects ($\forall$) have a property is hard, but you can search for an object without the property to disprove it. The more alternations there are between forall and exists, the harder a problem is.

For more on this, see the Arithmetic Hierarchy. Anything above $\Sigma^0\_0=\Pi^0\_0$ is undecidable, though level 1 is semi-decidable.

It's also possible to show that there are undecidable problems without using a nonsensical paradox like the Halting problem or Liar’s paradox. A Turing Machine can be encoded using a string of bits, i.e. an integer. But a problem can be encoded as a language, i.e. a subset of the integers. It's known that there is no bijection between the set of integers and the set of all subsets of the integers. So there must be some problems (languages) which don't have an associated Turing machine (algorithm).

@Brent: yes, this admits that this is decidable for modern computers. But it's decidable for a specific machine. If you add a USB drive with disk space, or the ability to store on a network, or anything else, then the machine has changed and the result doesn't still hold.

It also has to be said that there are going to be many times where the algorithm says "this code will halt" because the code will fail and run out of memory, and that adding a single extra bit of memory would cause the code to succeed and give a different result.

The thing is, Turing machines don't have an infinite amount of memory. There's never a time where an infinite amount of symbols are written to the tape. Instead, a Turing machine has "unbounded" memory, meaning that you can keep getting more sources of memory when you need it. Computers are like this. You can add RAM, or USB sticks, or hard drives, or network storage. Yes, you run out of memory when you run out of atoms in the universe. But having unlimited memory is a much more useful model.

# Answer
> 57 votes
In practical terms, it is important because it allows you to tell your ignorant bosses "what you're asking is mathematically impossible".

The halting problem and various NP-complete problems (e.g. the traveling salesman problem) come up a *lot* in the form of "Why can't you just make a program that does X?", and you need to be able to give an explanation of why it's impossible or infeasible within the remaining lifetime of the universe.

Do note that it is possible to design a language that is *not* Turing-complete, so can be analyzed, by forbidding unbounded recursion and iteration.

# Answer
> 49 votes
> You can use the algorithm which detects whether a linked list loops to implement the Halting Function with space complexity of O(1).

To do that, you need to store at least two copies of the partial state of the program in memory, plus the overhead of the checking program. So on a given computer, you cannot test all programs that can execute on that computer, only the programs that execute on a smaller computer with less than half as much memory.

The halting problem for a given finite-size computer cannot be solved on *that* finite-size computer. It can only be solved on a bigger computer. (This is true for any method, not just the one you propose. I'm not going to give a formal proof, but here's the gist. If a computer C can run N different programs of which at least one P doesn't terminate, then a computer V that can test whether these N program halts must be able to run N different verifier programs too. If C and V are the same computer, then P isn't one of the N different programs that V runs, so the computer must run at least N+1 different programs, which contradicts the assumption that C runs N different programs.)

In addition, you can't *just* use the algorithm to detect a loop in a linked list. You need to know when to stop. You can stop once you've executed as many steps as there are states in the computer. If a program uses up to $M$ bits of memory, then it can have $2^M$ different states. This very quickly becomes impossible. For example, a typical computer executes on the order of a billion instructions per second; one billion seconds is a little over 30 years. So if you run a computer for 8 years, you can test whether one program with about 250 million billion potential states halts. But that's only $2^{56}$ states, i.e. you can only test a program that works in 7 bytes of memory.

The numbers there illustrate that thinking of a computer as a finite-state machine is rarely practical. The number of states may be finite, but it's mind-bogglingly, impractically huge. The only way to reason about non-toy programs is in the abstract, not by enumerating states but through logical reasoning.

> So excluding paradoxical programs, the Halting Problem is decidable

The paradox does not come from the problem, but from the attempt at a solution. For any given program, there is an algorithm that says “yes” if the program terminates, and “no” if the program doesn't terminate. It's trivial: either `print "yes"` or `print "no"` will do. The problem is to determine which one to call. The impossibility of solving the halting problem means that there is no algorithm to make this determination. The reason the proof uses a diagonalization argument is that it needs to show that *no* solution works; to do that, it starts from an arbitrary purported solution, and shows that it must miss some programs by constructing a missed program. The diagonalization (what you inappropriately call a “paradox”) is in the construction, not in the resulting program. The resulting programs is not self-referential.

There is a more general result called Rice's theorem which states that *any non-trivial property* of programs is undecidable — any property that depends only on the behavior of the program and not in the specific way it's written (for example, “does the source code consist of less than 42 characters?” is clearly decidable, whereas “is there a program whose source code consists of less than 42 characters and that returns the same result for all inputs?” is not, nor is “does this program ever output anything?”). Halting is just one example. It's an important one because it often comes up in practice (usually, we want to know whether a program will return a result in reasonable time given the finite resources of the computer it's running on, but since this is rarely practically answerable, we're willing to settle for the simpler question as to whether the program will eventually terminate given enough time and memory).

# Answer
> 33 votes
> It seems to me that the Halting Problem is nothing more than a so called "paradox," a self referencing (at the very least cyclical) contradiction in the same way as the Liar's paradox. The only conclusion it makes is that the Halting Function is susceptible to such malformed questions

No, that's *not* what the halting problem is about. Paradoxes like the liar's paradox aren't true or false, they simply don't make sense. A deterministic algorithm on the other hand will either halt for a given input or it will run forever. The function `halts(program, input)` has a perfectly well-defined, deterministic value for every program, for every input. We just can't *decide* it for any program. Or, more precisely: We can't write a program that can decide it for every program/input pair.

A similar (maybe less abstract) example is the "busy beaver" function, intuitively defined as $\Sigma(n):=$The longest sequence of 1's a Turing machine with $n$ states, starting with an empty tape, can write before it terminates. For any $n$, there's only a finite number of Turing machines, and each of them either terminates at some point (then you can count the number of ones), or it runs forever (then the busy beaver doesn't carea about it - it only looks at programs that terminate). So, the busy beaver function *has* a deterministic value for every $n$. (We even know it for a few small $n$, because we can look at each program and find proofs why they will never halt.) But there can't be a program that calculates $\Sigma(n)$.

# Answer
> 26 votes
> I don't understand why the Halting Problem is so often used to dismiss the possibility of determining whether a program halts. The Wikipedia article correctly explains that a deterministic machine with finite memory will either halt or repeat a previous state. You can use the algorithm which detects whether a linked list loops to implement the Halting Function with space complexity of O(1).

First, yes, *theoretically* it makes sense to view a real computer, which has finite memory, as a finite state machine. But in *practice* the number of states of a real computer is so large, that real computers are much better modelled by Turing machines or other infinite state models of computation.

And second, even *theoretically* it makes sense to view a modern computer as an infinite state machine. A Turing machine does not have an infinite tape, it has a tape which can always be extended when the machine runs out of memory. And isn't that exactly what we can do with real computers? (And if the address space of the CPU runs out, we can use the cloud, etc.)

> It seems to me that the Halting Problem is nothing more than a so called "paradox," a self referencing (at the very least cyclical) contradiction in the same way as the Liar's paradox. The only conclusion it makes is that the Halting Function is susceptible to such malformed questions. So excluding paradoxical programs, the Halting Problem is decidable. So why do we hold it as evidence of the contrary?

There is a difference between the halting problem and the proof of its undecidability. The halting problem is just a specification for a program $H$: as input the program gets the source code of a program $P$ and an input $x$, and the program $H$ must return true if $P$ halts on input $x$ and false otherwise. This is a very clear specification; there is nothing paradoxical about it: every pair of source code and input has a single well-defined correct answer.

Turing's *proof of the undecidability* of the halting problem uses a trick which is similar to the Liar paradox, yes. A paradox is often defined as a *apparent* contradiction, and some people infer from that that a paradox is therefore not a *real* contradiction. However, Russel's paradox (the formal set-theoretic counterpart to the liar's paradox) showed a *real* contradiction in mathematics, and the proof of the undecidability of the halting problem uses a *real* contradiction for its proof by contradiction.

# Answer
> 19 votes
jmite has answered the question really nicely. Let me add a small side-note regarding the perceived similarity with the "Liar's Paradox" which I think is caused by their usage of a self-reference mechanism.

> **Self-reference is not paradoxical!**

Self-reference is a really useful tool in computation (that an algorithm can refer to its code, reflection) and human language (that we can refer to ourselves, self-consciousness).

The problem that causes the Liar's Paradox is not self-reference, it is trying to use the truth predicate for a (formal) language inside the language. It will cause problems even without self-reference, we don't need the ability to use self-reference to get a paradox: **self-reference can be eliminated!**. It would just make the sentence less nice and concise but it is not difficult to do. It is essentially how Kleene's Fixed Point theorem is proven. What the Liar's Paradox implies is that truth of statements in a (formal) language is transcendental to that language, not that self-reference is problematic.

---

It seems to me that your discomfort is not because of the undecidability of the halting problem (for Turing machines) but with acceptance of Turing machines as the theoretical model for computers. Typically (though not always) Turing machines (and equivalent models of computation like Random Access Machines) are much useful for discussion of computation on actual computers than finite automata and there are good reasons for that (keep in mind that a Turing machine does not have an infinite amount of memory, it has an unbounded amount of memory and these are different things: unbounded means that we can provide the machine with more memory when it needs, not that it uses an infinite amount of memory).

Sure, if you want to think of computers as finite automata, and that makes sense for your purpose, then the halting problem for finite automata is decidable (and by decidable we mean decidable by a Turing machine, not by a finite automata). That is however not what people normally mean when they use the halting problem, they mean the halting problem for Turing machines.

Also note that automata theory is actually used a lot in program analysis and software verification. If you know that $s$ is an upperbound on the amount memory your algorithm is going to use, it cannot run for more than $2^s$ steps and halt. But 1. it needs you to know an upperbound on the amount of memory the algorithm is going to use, 2. even then the decision whether that algorithm halts or not takes an exponential amount of time which is usually not a very useful algorithm.

# Answer
> 17 votes
You seem to be confusing the classic "self referential" based proof that the Halting problem cannot be solved with the Halting problem (aka Halt) itself.

That self-referential program -- the program that halts if and only if it doesn't halt -- is constructed in order to make it easy to prove you cannot solve Halt. The fact that we prove X is impossible via technique Y does **not** imply Y is the only reason why we cannot solve X.

To put it another way, not only can we not solve Halt, we cannot detect that a program the kind of program that we cannot determine if it Halts, other than a crude measure like "if it takes more than 1 minute to run, pretend it does not halt".

If you start from the Halting problem, and reduce other problems to it, you eventually reach the point that you have reduced almost every question about programs about it. We end up with Rice's Theorem:

Let S be some non-trivial property of1 what a Turing Machine accepts. That means there is at least one Turing Machine that accepts input with property S, and one that does not.

Then it is undecidable if a given Turing Machine T accepts input with property S.

You want to know if a Turing Machine accepts even integers? Undecidable.

You want to know if a Turing Machine accepts accepts arithmetic sequences? Undecidable.

You can reason about Turing Machine's guts in general. You can reason about a particular Turing Machine, and prove if it will halt/accept some sequence/etc. But you cannot know if your technique will work on the next Turing Machine you feed it.

---

1 By `property of` it does not include the mechanism of how it is accepted -- just of *what* is accepted. "It accepts in 100 or less steps" is a property how it accepts, not of what is accepted.

# Answer
> 16 votes
the halting problem introduced a new mathematical concept of "undecidability" that did not previously exist in mathematics. it was a ("seemingly paradoxical") proof that some problems have no "proofs". its connected to the Godelian concept of unprovability. Godels theorem preceded the halting problem formulation by Turing by a few years. Godels result was considered rather abstract at the time and was only known to researchers and specialists. Turings formulation showed that the principle of undecidability was related to highly practical/ pragmatic/ *applied* questions in computer science such as determining whether arbitrary programs halt and it is regarded as a far less theoretical concept, it shows up in modern challenges such as "automated theorem proving" (a challenge whether computers can discover theorems) and proving program termination.

another interesting angle is that there are some very old problems in (Diophantine) number theory originating with the Greeks that are unproven for millenia. there is a related result that general questions on Diophantine equations are undecidable called Hilberts 10th problem/ theorem. Hilbert lived at the turn of the 20th century and proposed as a research program that mathematics could find systematic approaches to math problems. this challenge/ plan was seriously struck by the discovery of undecidability from a few decades later. undecidibility continues to be a very advanced area of research and the boundary between undecidable and decidable problems will probably always be under further study and analysis.

# Answer
> 9 votes
You are right that the halting problem as commonly introduced and stated is a mere gotcha. It doesn't prove that there cannot be a three-valued (‘halts’, ‘loops’, ‘don't know’) halt-function that in practice always returns ‘halts’ or ‘loops’ and only returns ‘don't know’ for specially constructed corner-cases for example.

Two reasons the halting problem is significant:

1) This is one of the first provably undecidable problems. Even if hypothetically there were only one ‘don't know’, it would still be of huge mathematical interest.

2) Some problems reduce to the halting problem where a malicious attacker can supply the case to be analysed. This forces us to accept that there may be valid cases that we still have to reject.

As an afterthought to the second point, software analysis is a hard problem, although a lot of progress has been made both in analysis and in language design so as to make analysis easier. If you can show that a certain task is similar to software analysis, yes, it's Hard with a capital H. ‘It's impossible because it would amount to solving the halting problem’, although technically wrong or irrelevant in many cases, is often used a shorthand for this observation.

# Answer
> 6 votes
There is a contrarian argument put forth by Eric Hehner in a series of papers that argue that the unsolvability of the Halting Problem is commonly misunderstood. The papers, " Epimenides, Gödel, Turing: an Eternal Golden Tangle", "Problems with the Halting Problem", "Reconstructing the Halting Problem", and "Halting Problem", can be found here. So that this answer is not "link only" I will try to summarize one of his conclusions, but not the argument.

The conclusion is that: the reason that the halting problem is unsolvable is not because a program purported to solve it can be used to create a contradiction, but rather because the problem itself is unimplementable, in the same sense that a specification of a function that must return both 1 and 2 at the same time is unimplementable. We don't find it remarkable that there is no program to satisfy a specification $f(0)=1 \\;\land\\; f(0)=2$, so we shouldn't find it so remarkable that there is no program to solve the halting problem. The standard view is that there is a well-defined predicate $h$ such that $h(M)$ is true if Turing machine $M$ halts on a blank tape and false otherwise, but that there is no program $H$ that implements $h$. Hehner's view is that the predicate $h$ is not well defined to start with.

# Answer
> 4 votes
I would like to offer a different explanation of the importance of the halting problem that involves people rather than machines.

It's the last lecture of the MIT 1986 Structure and Interpretation course; the professor asks *"Are there any questions?"* and prepares to end the lecture, when one of the students asks: *"Is this the last question?"*

Think about it for a moment. How can the teacher answer this? If the student decides to contradict the teacher, there is no valid answer the teacher can give - this is just like the halting problem.

We're used used to think about the halting problem abstractly, using functions and machines, but it's much deeper than that. Fundamentally, it means that there are perfectly valid questions that cannot be answered.

PS: If you don't know what course I'm talking about, go watch it, it's awesome.

# Answer
> 0 votes
I can easily write a program which given an input n, either outputs the smallest prime p \> n such that p+2 is also a prime, or runs forever if no such p exists. If you can solve the problem to predict whether my program halts for every input, you just solved the Twin Prime Conjecture.

It is quite possible that this conjecture might be proven undecidable, in which case we’d have a straightforward program where the halting program fails.

# Answer
> -1 votes
I’m not going to address the math or science, except to say it proves we can’t do a whole bunch of things and that there are even more where we can’t say they are solvable until we have solved them.

Instead I’m going to address what seems to be a common emotional reaction to the Halting Problem: that it is a cheap trick like a little boy running around chanting “fooled ya, fooled ya. I’m rubber, you’re glue whatever bounce off of me sticks to you”.

If the Halting Problem was a song it would be a dirge. It ends the idea that all problems can be solved with computers. This new toy we had created was not as boundless as it had at first seemed. Some problems are and will remain, forever unsolvable. What’s even worse, is that in many cases there’s no way to tell the difference between “unsolvable” and “solution not know”, only between “solved” and “unsolvable”.

---
Tags: computability, halting-problem
---


# Question
Title: Existence of a CFL $L$ such that $\sqrt{L}$ is not CFL
Does there exist a CFL L such that the language defined as $L' = \sqrt{L} = \\{w | ww \in L\\}$ is not CFL? I feel that there is no such $L$ but obviously, I am unable to prove it.

I am sorry but I have not made any mentionable progress with my attempts on this problem.

I would appreciate any hint to the proof or a language $L$ that could satisfy this.

# Answer
> 8 votes
There is an example, and $L = \\{a^nb^na^{2m}b^ka^k \mid n,m,k \in \mathbb{N}\\}$ does the trick. We get that $\sqrt{L} = \\{a^nb^na^n \mid n \in \mathbb{N}\\}$, which is a standard example of a non-context-free language.

To elaborate a bit on how to get there: CFLs can express that two numbers are the same, but not that three numbers are the same. So I want the square-root operation to introduce another equality, as it seems predisposed to do so.

---
Tags: formal-languages, finite-automata, context-free, formal-grammars, pumping-lemma
---