# Question
Title: Difference between $\Rightarrow$, $\Longrightarrow$ and $\rightarrow$ in Isabelle/HOL?
I haven't been able to find a good explanation of how these are different and relate to each other. I know that $\to$ is part of HOL and $\Rightarrow$ and $\Longrightarrow$ part of Isabelle, but it seems that they are basically doing the same thing and we could just have one object $\to$? (Taking into account the CH correspondence). Why does Isabelle/HOL have 3 operators for essentially the same thing? How are they different?

# Answer
> I haven't been able to find a good explanation of how these are different and relate to each other. I know that → is part of HOL and ⇒ and ⟹ part of Isabelle, but it seems that they are basically doing the same thing and we could just have one object →? (Taking into account the CH correspondence).

The basic answer is because it depends on whether you want implication in the metalanguage ($\Longrightarrow$ or `==>`) or the object language (all other arrows), since Isabelle is a "metalogical framework" for reasoning within a specific "object logic".

Curry-Howard is relevant for the *metalogic*. If you try to use Curry-Howard with the object logic, you get an "object level" correspondence, which is already implicit in the object logic.

According to the documentation:

* $P\to Q$ (ascii `P --> Q`) is for "object language" logical implication "$P$ implies $Q$", i.e., implication in the object logic (encoding, e.g., implication in HOL); this is **not** part of the Isabelle's underlying "meta" logic;
* $\tau\_{1}\Rightarrow\tau\_{2}$ (ascii `tau => tau`) is used in Isabelle/HOL for the \[total\] function HOL type from HOL type $\tau\_{1}$ to produce a HOL term of HOL type $\tau\_{2}$;
* $\Longrightarrow$ (ascii `==>`) is the "meta-implication", i.e., the implication in the "metalogical framework" \[i.e., the Pure language\]. It's used for encoding "object logic" inference rules; if used for stating theorems, then those theorems may be used directly with forward or backward chaining (whereas theorems stated using `-->` needs to invoke implication inference rules), as Paulson tells us.

Really, you should use "$\Longrightarrow$" (`==>`) as much as possible when stating theorems. But there are times when you want to state *in the object logic* "$P$ implies $Q$"...and that requires "$\to$" (`-->`).

Further useful reading:
> 3 votes

---
Tags: proof-assistants, interactive-proof-systems, isabelle
---


# Question
Title: How does partial word lookup work in an inverted index?
I know that an inverted index is a mapping from `words -> documents`. In the database I'm using, I'm able to do a search for `apple*`, and it will return `apple banana`, `banana apple banana`, and `applepie`. The one that confuses me is `applepie`. I assumed the inverted index would only have the word `applepie` in the mapping from `words -> documents`. How could this result of returning `applepie` be achieved? Does the inverted index also store the values `a`, `ap`,... `apple`,... and which documents they map to, or something else?

(The database is unimportant but it's MySQL full text search.)

# Answer
> 1 votes
The mapping from word to postings almost certainly uses some variant of a B-tree, storing case-folded (and possibly stemmed) string keys in lexicographic order. With that data structure, prefix search can be implemented as a straightforward index scan.

Other kinds of partial search (e.g. substring search, or hamming-distance search) would be much slower, or require a different data structure.

---
Tags: data-structures, database-theory
---


# Question
Title: If the halting problem is NP hard, would P = NP with a hypercomputer capable of computing the halting problem in polynomial time?
The halting problem is NP hard, to my knowledge any NP problem can be reduced to a NP hard problem. Let us define a new computational complexity class called HP(Hypercomputational polynomal-time), The class of all problems solvable in polynomial time on this particular hyper computer. This would include the halting problem. Would HP = NP or(HP ⊇ NP)? As a stronger version of this, would HP = RE? and/or CO-RE?

# Answer
Assume a polynomial-time Halting Decider $H$ such that given the input string $\langle M, s \rangle$ it accepts if $M$ run on string $s$ halts in finite time, rejects otherwise, and completes this computation in polynomial time.

Let $L$ be *any* decision problem in $NP$. Let $M$ be a Turing Machine that decides $L$. Let $M'$ be a new Turing Machine modified such that if $M$ rejects an input string $s$, $M'$ will loop forever on an input string $s$.

Now $H(\langle M', s \rangle)$ decides $L$ in polynomial time, hence *all* decidable problems would be in $P$. As a result, given a polynomial-time solution to the Halting Problem, $NP = P$.
> 1 votes

# Answer
Since the halting problem is not computable, your hyper computer would be in violation of the laws of mathematics, and therefore capable of doing anything.
> 1 votes

---
Tags: complexity-theory, np-hard, p-vs-np, hypercomputation
---


# Question
Title: kolmogorov complexity for finite Language?
In lectures my professor proved that there is no Turing machine that for every x it calculates k(x).

On the other hand, I saw a claim online that for finite language L there is a Turing machine that calculate k(x) for every x in the finite language L.

But how does it work, why is this possible.

# Answer
This is not a property specific to kolmogorov complexity - it works with any function over strings (no matter what the function is!).

Since $L$ is finite, then also the set $K:=\\{(x,k(x))\mid x\in L\\}$ is finite.

Therefore there exists some TM that has the entire set $K$ stored in a large table. When the TM is given input $x$, it will look through this table and output the appropriate $k(x)$.
> 1 votes

---
Tags: formal-languages, turing-machines, programming-languages, turing-completeness, kolmogorov-complexity
---


title: Height of AVL Tree

text:
# Question
Title: Height of AVL Tree
I found an AVL tree implementation on the internet and experimented: For a tree with node count of 2^20, the minimal and maximal tree heights are 16 and 24. While these heights are lg(n)-ish, I am concerned about their difference. Doesn't AVL guarantee maximal-minimal height difference to be 1?

The repositoryfrom which I got the code

# Answer
The AVL invariant does *not* guarantee that, given any two tree paths, their length differs at most by one unit. They can differ by more than one unit, as shown by the following tree (Fibonacci AVL tree from Wikipedia):

Instead, the AVL invariant only requires that the heights of the two subtrees of any nodes differ at most by one. Note that the height of a (sub)tree is the *maximum length* of its paths. Therefore, the AVL invariant is equivalent to requiring that, for all nodes, the *maximum* length of a path in the left subtree and the *maximum* length of a path in the right subtree differ at most by one unit.

Note how we only take the paths giving the *maximum* length, and never the paths giving the *minimum* length.
> 3 votes

---
Tags: search-trees, balanced-search-trees, binary-search-trees, avl-trees
---


# Question
Title: Question on worst-to-average-case reductions
Consider two decision problems A and B.

We know that A reduces to B in polynomial time --- if we could solve B, we have a procedure to solve A.

Now, let's say it is known that the worst case instances of A reduce to the average case instances of A.

Does it imply the same worst-to-average-case reduction for B?

If not, what are some known counterexamples, considering standard problems/complexity classes?

# Answer
Let $A$ be any decidable problem, and let $B$ be the following encoding of the halting problem: $$ B = \\{(\langle T\_1 \rangle, \langle T\_2 \rangle) : T\_1 = T\_2 \text{ and } T\_1 \text{ halts on the empty input}\\}. $$ Since $A$ is decidable, it can be reduced to $B$, even in polynomial time. But there are natural probability distributions under which $B$ is easy on average.
> 1 votes

---
Tags: complexity-theory, time-complexity, reductions, polynomial-time-reductions
---


# Question
Title: Proving irregularity of $a^{k!}$ using Nerode's theorem
> Use Nerode's theorem to prove that the following language $L$ is not regular:
>
> $$ L=\\{a^{k!} \mid 1\leq k\\} $$

Here is my attempt:

Let $A$ be an infinte set of words s.t- $$ A=\\{a^n \mid n\in \mathbb{N}\\}$$

Then we shall consider 2 words from the set $a^{i!}$ and $a^j$ s.t-
$$ i!\leq n, i!\ne j$$

$$a^{i+1} \longrightarrow a^{i!}\cdot a^{i+1}=a^{(i+1)!}\in L$$ $$a^j\cdot a^{i+1}=a^{j+i+1}\notin L$$

I understand my attempt is not correct since when multiplying $a^{i!}\cdot a^{i+1}$ the exponent doesn't multiply . I cant seem to overcome this obstacle and would appreciate help.

# Answer
You can prove the following using Myhill-Nerode: If $x\_n$ is a non-decreasing sequence, and the differences $x\_{n+1} - x\_n$ are not bounded, then the language $\\{a^{x\_n}\\}$ is not regular.

That covers lots of problems that you will find in a course, like your n!, or $a^p$ where p is prime, or $a^{n^2}$, or any infinite subsequence of such sequences.

Someone else asked about the language $\\{0^{2^n}\\}$. Same solution.
> 0 votes

---
Tags: formal-languages, regular-languages
---


# Question
Title: Is proving NP-(in)completeness generally NP-complete?
Is even distinguishing between NP complete and incomplete problems an NP-hard problem?

# Answer
> 2 votes
Distinguishing between complete and incomplete problems is not an NP-hard problem because it is not in fact, even a decision problem. A decision problem must be a set of strings. In this case, you have not specified an input and a set of strings that we wish to accept vs reject.

However, if you decide to represent a **"problem"** in a specific finitary way, then you can rephrase your question. For example, one way to represent a problem is as a Turing machine. So you could ask, for example, is it NP-hard to determine on input a machine $M$, whether the language of $M$ is NP-complete? The answer is yes, and in fact it is much worse than NP-hard, it is undecidable. (But take note that not all undecidable problems are NP-hard -- see this answer.)

There are other ways to represent problems, though. One way to represent a problem is as a well-defined description in a certain **logic**, such as Peano Arithmetic (PA) or Set Theory (ZFC). That would be expressive enough to express any well-defined mathematical question about decision problems, restricted to decision problems that are definable within the logic in question. And if the logic is *weak* enough (i.e., nowhere near as strong as PA or ZFC), you might end up with a set of definable decision problems for which NP-hardness is decidable.

---
Tags: undecidability, decision-problem, p-vs-np
---


title: Is 2-DNF NP-complete?

text:
# Question
Title: Is 2-DNF NP-complete?
I want to know whether the 2-DNF problem is NP-complete or not? If it is NP-complete, can anyone provide a proof?

# Answer
> 14 votes
If you are referring to the problem of deciding whether a formula given in 2-DNF form is satisfiable, then it is in $P$, as well as general DNF satisfiability. Indeed, such a formula is satisfiable iff there is a clause that does not contain an inner contradiction. That is, a clause that does not contain both $p$ and $\neg p$ for some atomic proposition $p$. This can be checked in linear time.

Perhaps you are referring to 2-CNF? (Which is also in $P$, but it's less trivial.)

# Answer
> 6 votes
An additional note to Shaull's answer.

Checking if a DNF formula $\phi$ is *valid* (i.e. is a *tautology*) is co-NP-complete.

Indeed a formula $\phi$ is valid if and only if its negation is not satisfiable. But if you negate a DNF formula and apply De Morgan's laws you get a CNF formula. So the problem is equivalent to CNF unsatisfiability.

But if you restrict to 2-DNF, the validity can be checked in polynomial time because the corresponding negated formula is equivalent to the (un)satisfiability of a 2-CNF formula (that can be checked in polynomial time).

# Answer
> 2 votes
#2SAT and #2DNF are both #P-complete however. #2SAT can be converted to #2DNF by taking a not of the equation and applying DeMorgans law. If you have n literals then #2SAT=2^n-#2DNF, you subtract the total possible solutions from the number of unsatisfiable to get the number of satisfiable equations. #2CNF reduces to #3CNF which reduces to #3CNF-balanced which reduces to the (-1,0,1) permanent which reduces to the {0,...,m} permanent which reduces to the (0, 1) permanent which is #P-complete per Valiant. You could also likewise reduce #3CNF to #3DNF and then #3DNF-monotone (or convert to monotone while still at #3CNF) then reduce further to #2SAT-monotone. And just like that you can circle around from #2SAT to #2SAT-monotone. Regardless all of these problems and more are #P.

---
Tags: complexity-theory, np-complete, satisfiability
---


# Question
Title: find vertex cover of size at most 30 of a graph
This is a question from an exam I got wrong. Given an undirected graph $G$. Consider the decision problem of finding if there exists a vertex cover of size at most 30. Can we find a polynomial time algorithm for this problem? I answered that it is not possible because vertex cover is NP hard, but it turns out that there is a polynomial time algorithm. What is the reasoning behind this?

# Answer
Be careful about constants! There is a huge difference between the problem $$ \text{On input } G, n, \text{ does there exist a vertex cover of size at most } n? $$ and $$ \text{On input } G, \text{ does there exist a vertex cover of size at most 30}? $$

Notice, in particular, that the first problem has two inputs, $G$ and $n$. The second problem only has one input, $G$.

The first problem is NP-hard because it is very hard to find vertex covers. But the second problem should look intuitively much easier (when put in this form, where you see that $n$ is not part of the input) -- because we don't have to look for an arbitrary vertex cover, and instead we only have to look for a vertex cover of size at most 30. How does that help us?

Well, how many vertex covers are there of size at most 30? If $|V|$ is the number of vertices in the graph, then there are at most $|V|^{30}$ vertex covers. That's a big number, but $30$ is a constant -- so it's a **polynomial** in $|V|$ -- that is, it's polynomially many vertex covers that we have to check.

Therefore, this problem is in $P$, and the algorithm is as follows: check all lists of $30$ vertices -- of these lists there are only polynomially many, and they can be enumerated explicitly. For each of these $|V|^{30}$ lists, check if the list is a vertex cover (take a moment to think about how we would check that a given list is a vertex cover or not). Then finally, if any of them *is* a vertex cover, accept; otherwise, if *none* of them is a vertex cover, reject.
> 4 votes

---
Tags: algorithms, complexity-theory, graphs, time-complexity
---


# Question
Title: Is there a way to represent multi-dimensional arrays in lambda calculus?
I am currently studying lambda calculus, and would like to represent an array that accepts multiple dimensions. I still haven't figured out how to implement uni-dimensional arrays though.

I have found an interesting article on how to represent lists in lambda-calculus, but nothing for arrays. I have been unsuccessfully trying to extend the definition of lists into that of arrays.

I appreciate any help provided.

# Answer
> 3 votes
Two important properties of the pure lambda calculus are that (1) it is untyped, and (2) it is not very precise about efficiently representing data structures. There are extensions to the lambda calculus which fix these problems, but if you are interested in representing data structures directly in the lambda calculus, you have to accept that they will not have a notion of type and will not necessarily represented very efficiently.

As a result of these properties: **in the lambda calculus, there is no fundamental difference between a list and an array.** That is, you can represent an array *as* a list. This gives you exactly the properties you need: the array should support accessing elements by index, and it should support initialization, and it should support iterating over elements. Since lists support all these features, they can be used as arrays. Now you may object that this is not the kind of implementation of arrays you are expecting, because it *also* supports other operations including concatenation, and it is not necessarily efficient. But it is a perfectly valid implementation of arrays in the lambda calculus, and since we don't have types, we have no way of annotating the difference between the two; both lists and arrays are just lambda terms, which support certain operations.

Furthermore, you can represent a multidimensional array in the usual way as a single uni-dimensional array. For example, a 2D array with dimensions $m \times n$ is represented as a single array of length $mn$; and to access the element at $(i, j)$, we access the $(ni + j)$th element of the unidimensional array.

---
Tags: arrays, lambda-calculus
---


# Question
Title: In a rigorous mathematical sense, what is the significance of Turing-completeness?
I know that Turing-completeness is the ability to simulate a Turing machine, and from what I've read, the reason why we should care about Turing-completeness is that it demonstrates that a machine can "run any program" or "compute the result of any algorithm." While I understand these descriptions, I'm wondering if there's a more mathematically rigorous description of this significance. At a fundamental level, what exactly defines an "algorithm" or "program" or "instruction"? If Turing-completeness is a measure of a machine's ability to manipulate data, what do we mean by "manipulate" and "data"?

# Answer
The mathematical significance of the concept of Turing machines is to give one possible rigorous mathematical definition of concepts such as "algorithm", "program", "instruction" and "data". It is a very satisfying definition which is known to be equivalent in computational power to many others.

It should be said that there are of course other approaches, which refine and further develop these concepts. For example, in programming language theory operational semantics gives a good account of "instruction" and "computation step". But Turing was the first one.
> 3 votes

---
Tags: turing-machines, computability, turing-completeness
---


# Question
Title: Where does each part of the $1 - (1 - 1/k)^k$ approximation for the Maximum Coverage problem come from?
A solution to an instance of the Maximum Coverage problem with a budget of k subsets can be approximated with a greedy algorithm that, at each iteration, picks one of the subsets that adds the most additional coverage. This has been shown to lead to a worst case performance of $(1 - 1/e) \cdot \mathsf{OPT}$, where $\mathsf{OPT}$ is the optimal amount of coverage possible for the problem. See Section 2 of this lecture.

The quantity $(1 - 1/e)$ is the asymptotic lower bound of a function $f(i) = 1 - (1 - 1/i)^i$, where $i$ is the current iteration within the interval $\[1, k\]$. Therefore, on the $k$th and final iteration, we have an approximation factor of $1 - (1 - 1/k)^k \cdot \mathsf{OPT}$.

What I am wondering is where each part of the $1 - (1 - 1/k)^k$ is derived from.

Here is my current understanding: During every iteration, the greedy algorithm picks the subset that offers the most additional coverage, which means we are adding at least $1/k$ elements to our total coverage.

This leaves at most $1 - 1/k$ elements still uncovered. There are k iterations, so we can multiply this quantity by itself k times. This gives us the quantity $(1 - 1/k)^k.$ Okay.

So where does the first $1$ in the quantity $1 - (1 - 1/k)^k$ come from? If $1/k$ shows the minimum number of **additional** elements covered on any iteration, $(1 - 1/k)^k$ shows the remaining elements **not** covered after k iterations, then does that mean $1 - (1 - 1/k)^k$ represents the portion of elements that **are covered** by the end? Am I missing anything here?

# Answer
> 1 votes
You are almost correct but not precisely correct.

Your this statement is incorrect:

> If $1/k$ shows the minimum number of additional elements covered on any iteration.

It should rather be:

> "At least $1/k$ fraction of uncovered elements are covered in any iteration".

Let us prove this statement. At any stage of the algorithm, let $U' \subseteq U$ be the set of uncovered elements. Here $U$ is the initial set of elements. Let $S\_1,S\_2,\dotsc,S\_k$ be the optimal solution. In other words, $S\_1,S\_2,\dotsc,S\_k$ cover all elements from $U$. Suppose that after $t$ iterations, the algorithm has picked $p$ sets from $S\_1,S\_2,\dotsc,S\_k$ for some $0 \leq p\leq t$. Without loss of genrality, suppose these sets are $S\_1,\dotsc,S\_p$. Note that $S\_{p+1},\dotsc,S\_{k}$ covers $U'$. Therefore, there exists a set in the collection that covers at least $1/(k-p)$ fraction of $|U'|$. Since $1/(k-p) \geq 1/k$, we have that at least $1/k$ fraction of uncovered elements are covered in any iteration. This completes the proof of the statement. Now, we will apply this statement.

Since the algorithm picks the set with maximum cardinality; the chosen set always contains $1/k$ fraction of uncovered elements. Therefore, after the first iteration, at least $(1/k) \cdot |U|$ elements are covered. Hence at most $(1-1/k) \cdot |U|$ elements remain uncovered. Let the actual number of uncovered elements be $n\_1$.

Applying the statement again for the second iteration. At most $(1-1/k) \cdot n\_1$ elements remain uncovered after the second iteration. Let $n\_2$ be the actual number of uncovered elements. Then, $n\_2 \leq (1-1/k)^2 \cdot |U|$ since $n\_1 \leq (1-1/k) \cdot |U|$.

Using induction, you can prove that after $k$ iterations, $(1-1/k)^k \cdot |U|$ elements are uncovered. Therefore, the number of covered elements after $k$ iterations are at least $(1-(1-1/k)^k) \cdot |U|$.

---
Tags: np-hard, approximation, greedy-algorithms, number-theory
---


# Question
Title: Solving a recurrence relation with two variables
I have this function which traverses each node of a left child-right sibling binary tree once and I want to solve the recurrence relation of the function.

First of all I think the relation looks like this:
`T(n) = 1+m[4+T(n-m)] = 1+4m+mT(n-m)`

Where `m` is the number of nodes on a level and `n` the total amount of nodes in the tree.

Is this correct? And how could I solve this recurrence relation with two variables?

```
void maxWidth(Node node, int height, vector<int> &width){
    if(node==nullptr){
        return;
    }
    while(node!=nullptr){
        if(width.size()==height){
            width.push_back(0);
        }
        if(width.size()>height){
            width[height]=width[height]+1;
        }
        if(node->left_child!=nullptr){
            maxWidth(node->left_child,height+1,width);
        }
        node=node->right_sib;
    }
}

```

# Answer
If you insist on solving a recurrence formula, you might want to compute $T$ based on the *height* of the tree first. Computing $T$ based on the number of nodes is much more complicated, and the $T(n-m)$ there is not correct - it needs to be $T(n-\sum\_{i=1}^m{k\_i})$ where $k\_i$ is the size of the sub-tree which is rooted in the $i$'th child.

Otherwise (which is what I recommend doing), just notice that you will visit each node at most once. In each visit you will pay no more than $O(1)$ before each recursive call, and hence this algorithm will total to be $O(n)$.

However the above reasoning will need to be formalized if you want to keep it as a proof. That is, you will have to prove that indeed you will not visit each node more than once.
> 0 votes

---
Tags: algorithms, time-complexity, recurrence-relation, binary-trees
---


# Question
Title: Why is a Language L(M) {has at least 10 strings} turing recognizable and L(N) {has at most 10 strings} is not?
Why is a Language L(M) {has at least 10 strings} recognizable and L(N) {has at most 10 strings} is not?

```
{⟨⟩:() has at least 10 strings}

{⟨N⟩:(N) has at most 10 strings}

```

My proof (I dont know if I'm wrong)

L(N) =\> I could think of a turing machine that takes as an input 10 strings of the language and accept them, if the turing machine accepts them then it's turing recognizable but not turing decidable (given Rice's Theorem)

But I can't figure it out a proof for L(M) even though I know it's undecidable also fro Rice's Theorem

Please, If I'm doing something wrong also on L(N) reasoning, let me know

# Answer
> 1 votes
I had to dig a little bit because 2nd Rice's Theorem wasn't included in my lectures

I proved this example using 2nd Rice's Theorem on Language N:

given 2 Turing Machines N1 and N2, N1 exists for L(N1) = Ø and N2 exists for L(M2) = Σ\* . since L(N1) ⊂ L(N2) then the language N is not turing recognizable

Given that it's easy to prove that the complement (M) is turing recognizable

# Answer
> 2 votes
Let $S\_\ge = \\{\langle M \rangle \mid |L(M)| \ge 10\\}$. You can prove that it is Turing-recognizable by applying the definition directly. The following algorithm terminates on machines in $S\_\ge$ and runs forever on machines that are not in $S\_\ge$:

* For $k = 0,1,2,\ldots$:
    + Let $c := 0$
    + For every string $w$ of length at most $k$:
        - Run $M$ on the input $w$ for at most $k$ steps. If $M$ halts, increment $c$.
        - Terminate if $c$ reaches $10$.

If this algorithm terminates on a machine $M$, then it has run $M$ on 10 string on which $M$ terminates. Conversely, if $M$ is in $S\_\ge$, then take 10 strings that it accepts, let $k\_1$ be their maximum length and let $k\_2$ be the maximum number of steps that it takes to accept one of them; the algorithm above terminates with $k \le \max\\{k\_1, k\_2\\}$.

This algorithm only proves recognizability, not decidability, since it'll go on forever on machines that don't accept at least 10 strings. This doesn't prove that $S\_\ge$ is not Turing-decidable: there could be another algorithm that works. A straightforward application of Rice's theorem does prove that $S\_\ge$ is not Turing-decidable.

Now let's look at $S\_\le = \\{\langle M\rangle \mid |L(M)| \le 10\\}$. Note that $S\le \cup S\_\ge$ is Turing-decidable: it's the set of all machines. And $S\_\le \cap S\_\ge = \\{\langle M\rangle \mid |L(M)| = 10\\}$ is not Turing-decidable, by Rice's theorem.

If $S\_\le$ was Turing-recognizable, then $S\_\ge \cap S\_\le$ would be Turing-decidable by the following algorithm:

* Run the recognizer for $S\_\le$ and the recognizer for $S\_\ge$ in parallel, doing one step of each at a time. Terminate if one of the two terminates.

Since every input is recognized by one of the two recognizers, this process terminates on all inputs, so $S\_\ge \cap S\_\le$ is decidable. But we saw abov that it isn't. So $S\_\le$ cannot be Turing-recognizable and $S\_\ge$ is not Turing-decidable.

---
Tags: turing-machines, undecidability, semi-decidability, rice-theorem
---


# Question
Title: Does proving undecidability implies that H is RE-Complete
If I want to show that H is RE-Complete is it enough to show it's undecidable? or should I prove something else alongeside?

$H$ is the halting problem: $H = \\{\<p,x\>|p \textit{ halts on } x\\}$\

# Answer
> 1 votes
No, its not enough.

For a language $L$ to be $RE$-complete, one needs to show two things:

1. $L\in RE$
2. For any $L'\in RE$, it holds that $L'\le\_m L$ (there is a many-to-one reduction between $L'$ and $L$).

An implication of this, is that any $RE$-complete language is also undecidable. But not the other way around.

---
Tags: undecidability, halting-problem
---


# Question
Title: Is there a sometimes-efficient algorithm to solve #SAT?
Let $B$ be a boolean formula consisting of the usual AND, OR, and NOT operators and some variables. I would like to count the number of satisfying assignments for $B$. That is, I want to find the number of different assignments of truth values to the variables of $B$ for which $B$ assumes a true value. For example, the formula $a\lor b$ has three satisfying assignments; $(a\lor b)\land(c\lor\lnot b)$ has four. This is the #SAT problem.

Obviously an efficient solution to this problem would imply an efficient solution to SAT, which is unlikely, and in fact this problem is #P-complete, and so may well be strictly harder than SAT. So I am not expecting a guaranteed-efficient solution.

But it is well-known that there are relatively few really difficult instances of SAT itself. (See for example Cheeseman 1991, "Where the *really* hard problems are".) Ordinary pruned search, although exponential in the worst case, can solve many instances efficiently; resolution methods, although exponential in the worst case, are even more efficient in practice.

My question is:

> Are any algorithms known which can quickly count the number of satisfying assignments of a typical boolean formula, even if such algorithms require exponential time in the general instance? Is there anything noticeably better than enumerating every possible assignment?

# Answer
> 22 votes
### Counting in the general case

The problem you are interested in is known as #SAT, or model counting. In a sense, it is the classical #P-complete problem. Model counting is hard, even for $2$-SAT! Not surprisingly, the exact methods can only handle instances with around hundreds of variables. Approximate methods exist too, and they might be able to handle instances with around 1000 variables.

Exact counting methods are often based on DPLL-style exhaustive search or some sort of knowledge compilation. The approximate methods are usually categorized as methods that give fast estimates without any guarantees and methods that provide lower or upper bounds with a correctness guarantee. There are also other methods that might not fit the categories, such as discovering backdoors, or methods that insist on certain structural properties to hold on the formulas (or their constraint graph).

There are practical implementations out there. Some exact model counters are CDP, Relsat, Cachet, sharpSAT, and c2d. The sort of main techniques used by the exact solvers are partial counts, component analysis (of the underying constraint graph), formula and component caching, and smart reasoning at each node. Another method based on knowledge compilation converts the input CNF formula into another logical form. From this form, the model count can be deduced easily (polynomial time in the size of the newly produced formula). For example, one might convert the formula to a binary decision diagram (BDD). One could then traverse the BDD from the "1" leaf back to the root. Or for another example, the c2d employs a compiler that turns CNF formulas into deterministic decomposable negation normal form (d-DNNF).

If your instances get larger or you don't care about being exact, approximate methods exist too. With approximate methods, we care about and consider the quality of the estimate and the correctness confidence associated with the estimate reported by our algorithm. One approach by Wei and Selman \[2\] uses MCMC sampling to compute an approximation of the true model count for the input formula. The method is based on the fact that if one can sample (near-)uniformly from the set of solution of a formula $\phi$, then one can compute a good estimate of the number of solutions of $\phi$.

Gogate and Dechter \[3\] use a model counting technique known as SampleMinisat. It's based on sampling from the backtrack-free search space of a boolean formula. The technique builds on the idea of importance re-sampling, using DPLL-based SAT solvers to construct the backtrack-free search space. This might be done either completely or up to an approximation. Sampling for estimates with guarantees is also possible. Building on \[2\], Gomes et al. \[4\] showed that using sampling with a modified randomized strategy, one can get provable lower bounds on the total model count with high probabilistic correctness guarantees.

There is also work that builds on belief propagation (BP). See Kroc et al. \[5\] and the BPCount they introduce. In the same paper, the authors give a second method called MiniCount, for providing upper bounds on the model count. There's also a statistical framework which allows one to compute upper bounds under certain statistical assumptions.

### Algorithms for #2-SAT and #3-SAT

If you restrict your attention to #2-SAT or #3-SAT, there are algorithms that run in $O(1.3247^n)$ and $O(1.6894^n)$ for these problems respectively \[1\]. There are slight improvements for these algorithms. For example, Kutzkov \[6\] improved upon the upper bound of \[1\] for #3-SAT with an algorithm running in time $O(1.6423^n)$.

As is in the nature of the problem, if you want to solve instances in practice, a lot depends on the size and structure of your instances. The more you know, the more capable you are in choosing the right method.

---

\[1\] Vilhelm Dahllöf, Peter Jonsson, and Magnus Wahlström. Counting Satisfying Assignments in 2-SAT and 3-SAT. In Proceedings of the 8th Annual International Computing and Combinatorics Conference (COCOON-2002), 535-543, 2002.

\[2\] W. Wei, and B. Selman. A New Approach to Model Counting. In Proceedings of SAT05: 8th International Conference on Theory and Applications of Satisfiability Testing, volume 3569 of Lecture Notes in Computer Science, 324-339, 2005.

\[3\] R. Gogate, and R. Dechter. Approximate Counting by Sampling the Backtrack-free Search Space. In Proceedings of AAAI-07: 22nd National Conference on Artificial Intelligence, 198–203, Vancouver, 2007.

\[4\] C. P. Gomes, J. Hoffmann, A. Sabharwal, and B. Selman. From Sampling to Model Counting. In Proceedings of IJCAI-07: 20th International Joint Conference on Artificial Intelligence, 2293–2299, 2007.

\[5\] L. Kroc, A. Sabharwal, and B. Selman. Leveraging Belief Propagation, Backtrack Search, and Statistics for Model Counting. In CPAIOR-08: 5th International Conference on Integration of AI and OR Techniques in Constraint Programming, volume 5015 of Lecture Notes in Computer Science, 127–141, 2008.

\[6\] K. Kutzkov. New upper bound for the #3-SAT problem. Information Processing Letters 105(1), 1-5, 2007.

# Answer
> 8 votes
In addition to the papers listed by Juho, here are some others that describe work on this topic, especially on approximating the number of solutions:

# Answer
> 1 votes
I would like to point in the direction of First Order Logic. In First Order Logic there are entire fragments (FO$^2$,C$^2$), where model count for arbitrary ground formulae can be computed in Polynomial Time w.r.t domain cardinality. For example, given a domain $\Delta$ consisting of people and the following formulas: $$\forall x \forall y. Smokes(x) \rightarrow Cancer(x)$$ $$\forall x \forall y. Smokes(x) \land Freinds(x,y) \rightarrow Smokes(x)$$

The the model counting can be performed in polynomial time w.r.t $|\Delta|$

---
Tags: complexity-theory, reference-request, satisfiability
---


# Question
Title: Why can’t we use FPRAS for #DNF to estimate #CNF?
Why cant we approximate the number of satisfying assignments of a CNF formula $g$ by first counting the solutions to $\neg g$ (which is in DNF) using the FPRAS for $\\#DNF$ and then estimating the $\\#g$ to be $2^{n}-\\#(\neg g)$?

PS: I say why we cant, because I don't see this approach tried anywhere and seems too trivial to not have been thought of !

# Answer
The complement of an independent set is a vertex cover, and vice versa.

There is a very simply 2-approximation algorithm for vertex cover.

In contrast, it is NP-hard to approximate independent set better than $\Omega(n^{1-\epsilon})$, for any constant $\epsilon \> 0$.

The problem is that if we take a 2-approximation for vertex cover and complement it, we don't necessarily get a 2-approximation for independent set. As an example, consider a matching on $2n$ vertices. The minimum vertex cover here is $n$, and this is also the maximum independent set. The set of all vertices is a 2-approximation for minimum vertex cover, but its complement, the empty set, is not a 2-approximation of maximum independent set.

Your problem is similar.
> 4 votes

---
Tags: counting
---


# Question
Title: What are some interesting/important Programming Language Concepts I could teach myself in the coming semester?
I’m a CS senior with and Individual Study period this coming semester, and I’ve decided I’d like to learn more about Programming Language Concepts. More specifically, different programming paradigms, like Functional and Logic programming.

Not sure how most universities handle ISs but I’m to essentially write a syllabus outlining what I’ll be learning, and how I’ll show that I’ve learned it.

Since I’ve only really spent time working in an Object Oriented context, I’m looking for some recommendations for concepts from Functional/Logic/any other paradigms I might benefit from learning about.

Apologies if this is not the place to be asking this question.

# Answer
> 31 votes
Very good explanations of programming paradigms and the programming concepts from which those paradigms are built are found in Peter van Roy's works. Especially in the book *Concepts, Techniques, and Models of Computer Programming* by Peter Van Roy and Seif Haridi. (Unfortunately, the companion wiki does not seem to exist any more.) CTM (as it is colloquially known) uses the multi-paradigm Distributed Oz programming language to introduce all the major programming paradigms.

Peter van Roy also made this amazing poster that shows the 34 major paradigms and their relations and positions on various axis. The poster is basically an incredibly compressed version of CTM. A more thorough explanation of that poster is contained in the article Programming Paradigms for Dummies: What Every Programmer Should Know which appeared as a chapter in the book *New Computational Paradigms for Computer Music*, edited by G. Assayag and A. Gerzso. It explains for example very concisely and easily understandable, what a programming paradigm actually *is*, what a programming concept is, and how the two are related.

There are about 34 principal Programming Paradigms, as identified by Peter van Roy and Seif Haridi:

* active object programming / object-capability programming
* ADT functional programming
* ADT imperative programming
* concurrent constraint programming
* concurrent object-oriented programming / shared-state concurrent programming
* constraint (logic) programming
* continuation programming
* descriptive declarative programming
* deterministic logic programming
* event-loop programming
* first-oder functional programming
* functional programming
* functional reactive programming (FRP) / weak synchronous programming
* imperative programming
* imperative search programming
* lazy concurrent constraint programming
* lazy dataflow programming / lazy declarative concurrent programming
* lazy functional programming
* monotonic dataflow programming / declarative concurrent programming
* multi-agent dataflow programming
* multi-agent programming / message-passing concurrent programming
* nonmonotonic dataflow programming / concurrent logic programming
* relational & logic programming
* sequential object-oriented programming / stateful functional programming
* software-transactional memory (STM)
* strong synchronous programming

Programming Paradigms, in turn, are composed of Programming Concepts, and Peter van Roy and Seif Haridi have identified 18 of those:

* by-need synchronization
* cell (state)
* closure
* continuation
* instantaneous computation
* local cell (private state)
* log
* name (unforgeable constant)
* nondeterministic choice
* port (channel)
* procedure
* record
* search
* single assignment
* solver
* synchronization on partial termination
* thread
* unification (equality)

Note, that poster completely ignores typing, and there is of course a significant difference between a System F\<:ω-style type system, a Scala-style type system, or a dynamic duck-typed type system, let alone a dependent type system à la Idris, Agda, Coq, Guru, or ATS.

*Another* great book that demonstrates several major programming paradigms is *Structure and Interpretation of Computer Programs* by Harold Abelson and Gerald Jay Sussman. This book was the basis of MIT's CS101 for several decades.

The main difference between CTM and SICP is that CTM demonstrates most major paradigms using a language that supports them (mostly Distributed Oz, but also some others). SICP OTOH demonstrates them by *implementing* them in a language that does *not* support them natively (a subset of Scheme). Seeing Object-Orientation implemented in a dozen or so lines of code is friggin' awesome.

You can find video recordings and course materials of the course from MIT's short-lived ArsDigita University project.

Lambda the Ultimate – The Programming Languages Weblog is a great resource for all things programming languages. Activity has slowed down in recent years, but there is still a lot going on. The discussions below the articles and the discussions in the forums are at least as valuable as the articles themselves, if not more.

If you are interested in some controversial views, I can recommend studying the *Design Principles behind Smalltalk* by Dan Ingalls. For example, they contain this nugget of wisdom:

> *Operating System*: An operating system is a collection of things that don't fit into a language. There shouldn't be one.

On a personal note, my own experience has been that *really* understanding a programming paradigm is only possible

* one paradigm at a time and
* in languages which *force* you into the paradigm

Ideally, you would use a language which takes the paradigm to the extreme. In multi-paradigm languages, it is much too easy to "cheat" and fall back on a paradigm that you are more comfortable with. And using a paradigm as a library is only really possible in languages like Scheme which are specifically designed for this kind of programming. Learning lazy functional programming in Java, for example, is not a good idea, although there are libraries for that.

Here's some of my favorites:

* **object-orientation in general**: Self
    + **prototype-based object-orientation**: Self
    + **class-based object-orientation**: Newspeak
        - **static class-based object-orientation**: Eiffel
    + **multiple dispatch based OO**: Dylan
    + **functional + object-orientation**: Scala
* **functional programming**: Haskell
    + **pure functional programming**: Haskell
        - **lazy pure functional programming**: Haskell
    + **static functional programming**: Haskell
    + **dynamic functional programming**: Clojure
* **imperative programming**: Lua
* **concurrent programming**: Clojure
    + **message-passing concurrent programming**: Erlang
* **metaprogramming**: Racket
* **language-oriented programming**: Intentional Domain Workbench
* **other interesting ideas**:
    + Unison: code is immutable and content-adressable, which has some deep implications.
    + Rust: "safe" and "low level / bare metal" don't need to be mutually exclusive.
    + TypeScript: how do you capture all the crazy stunts ECMAScript programmers pull into a mostly-sound static type system? Note that there are many languages in the "typed web programming" field, but most of them try to be "better" ECMAScripts or "better *than*" ECMAScript, whereas TypeScript tries to make *existing* ECMAScript safe.

Equally important as the language semantics is its *Type System*. Unfortunately, I don't know of any similarly informative visualization of the different aspects of type systems. I am also not intimately familiar with Type Theory, unfortunately. (If you want to understand type systems, you should read Benjamin Pierce's *Types and Programming Languages*.)

Some of the important aspects are:

* dynamic vs. static typing, also gradual typing, optional typing, soft typing
* latent vs. manifest typing
* implicit vs. explicit typing
* structural vs. nominal vs. duck typing
* strong vs. weak typing
* parametric polymorphism (also higher-rank and higher-kinded), ad-hoc polymorphism, inclusion polymorphism, bounded polymorphism, subtype polymorphism
* at the intersection of subtyping and parametric polymorphism: covariance, contravariance, invariance
* System F, System Fω, System F\<:, System Fω\<:, and its various extensions, variants, subsets, and derivatives, including Damas-Hindley-Milner, but also type systems that move away from System F (e.g. the Dependent Object Type Calculus underlying Scala's Type System)
* the Barendregt Lambda Cube
* various forms of Type Inference, including Algorithm W, Flow-based, unification-based, etc.
* Kinds
* Dependent Typing, Linear Types, Ownership Types, Effect Types, World Types

And probably many other things I forgot.

In your question, you mention that you have experience with OO. In my personal experience, OO tends to almost universally be taught really badly. I am not saying that is what happened to you, but it is something I have noticed. So, even though you specifically asked about Functional and Logic Programming, here are some OO pointers as well.

The term "Object-Orientation" was coined by Dr. Alan Kay, and he defines it thus:

> OOP to me means only messaging, local retention and protection and hiding of state-process, and extreme late-binding of all things.

Let's break that down:

* messaging ("virtual method dispatch", if you are not familiar with Smalltalk)
* state-process should be
* locally retained
* protected
* hidden
* extreme late-binding of all things

Implementation-wise, messaging is a late-bound procedure call, and if procedure calls are late-bound, then you cannot know at design time *what* you are going to call, so you cannot make any assumptions about the concrete representation of state. So, really it is about messaging, late-binding is an implementation of messaging and encapsulation is a consequence of it.

He later on clarified that "The big idea is 'messaging'", and regrets having called it "object-oriented" instead of "message-oriented", because the term "object-oriented" puts the focus on the unimportant thing (objects) and distracts from what is really important (messaging):

> Just a gentle reminder that I took some pains at the last OOPSLA to try to remind everyone that Smalltalk is not only NOT its syntax or the class library, it is not even about classes. I'm sorry that I long ago coined the term "objects" for this topic because it gets many people to focus on the lesser idea.
>
> The big idea is "messaging" -- that is what the kernal of Smalltalk/Squeak is all about (and it's something that was never quite completed in our Xerox PARC phase). The Japanese have a small word -- ma -- for "that which is in between" -- perhaps the nearest English equivalent is "interstitial". The key in making great and growable systems is much more to design how its modules communicate rather than what their internal properties and behaviors should be. Think of the internet -- to live, it (a) has to allow many different kinds of ideas and realizations that are beyond any single standard and (b) to allow varying degrees of safe interoperability between these ideas.

(Of course, today, most people don't even focus on objects but on classes, which is even more wrong.)

Messaging is *fundamental* to OO, both as metaphor and as a mechanism.

If you send someone a message, you don't know what they do with it. The *only* thing you can observe, is their response. You don't know whether they processed the message themselves (i.e. if the object has a method), if they forwarded the message to someone else (delegation / proxying), if they even understood it. That's what encapsulation is all about, that's what OO is all about. You cannot even distinguish a proxy from the real thing, as long as it responds how you expect it to.

A more "modern" term for "messaging" is "dynamic method dispatch" or "virtual method call", but that loses the metaphor and focuses on the mechanism.

So, there are two ways to look at Alan Kay's definition: if you look at it standing on its own, you might observe that messaging is basically a late-bound procedure call and late-binding implies encapsulation, so we can conclude that #1 and #2 are actually redundant, and OO is all about late-binding.

However, he later clarified that the important thing is messaging, and so we can look at it from a different angle: messaging is late-bound. Now, if messaging were the *only* thing possible, then #3 would trivially be true: if there is only one thing, and that thing is late-bound, then *all* things are late-bound. And once again, encapsulation follows from messaging.

Similar points are also made in *On Understanding Data Abstraction, Revisited* by William R. Cook and also his *Proposal for Simplified, Modern Definitions of "Object" and "Object Oriented"*.

> Dynamic dispatch of operations is the essential characteristic of objects. It means that the operation to be invoked is a dynamic property of the object itself. Operations cannot be identified statically, and there is no way in general to exactly what operation will executed in response to a given request, except by running it. This is exactly the same as with first-class functions, which are always dynamically dispatched.

Benjamin Pierce in *Types and Programming Languages* argues that the defining feature of Object-Orientation is *Open Recursion*.

So: according to Alan Kay, OO is all about messaging. According to William Cook, OO is all about dynamic method dispatch (which is really the same thing). According to Benjamin Pierce, OO is all about Open Recursion, which basically means that self-references are dynamically resolved (or at least that's a way to think about), or, in other words, messaging.

As you can see, the person who coined the term "OO" has a rather metaphysical view on objects, Cook has a rather pragmatic view, and Pierce a very rigorous mathematical view. But the important thing is: the philosopher, the pragmatist and the theoretician all agree! Messaging is the one pillar of OO.

Note that there is no mention of inheritance here! Inheritance is not essential for OO. In general, most OO languages have some way of implementation re-use but that doesn't necessarily have to be inheritance. It could also be some form of delegation, for example. In fact, *The Treaty of Orlando* discusses *delegation* as an alternative to inheritance and how different forms of delegation and inheritance lead to different design points within the design space of object-oiented languages. (Note that actually even in languages that support inheritance, like Java, people are actually taught to avoid it, again indicating that it is not necessary for OO.)

# Answer
> 10 votes
Check out the book Types and Programming Languages (TAPL) by Benjamin Pierce. This is an excellent introduction to the fundamental concepts of the field of programming languages.

# Answer
> 2 votes
Teach yourself how to make a compiler and learn about computer architecture/digital design. Knowing that material will distinguish you from beginners very easily. This free course material from the University of Hawaii covers computer architecture and a bit about compilers, I highly recommend exploring it. Also, learn about networking. It is very nice to know that, this course from Coursera covers the basics of computer networking.

# Answer
> -1 votes
All the basic concepts of computer science must be known to you in order to facilitate effective learning. Read about how CPU works, register versus stack machines, how does fetch/decode/execute cycle work, how does CPU pipelining work. After you have the basics, familiarize yourself with oscilloscope diagnosis of electronic circuits. Learn about the physical fundamentals about how do semiconductors work and how lithography allows us to make CPUs. Get essential knowledge about power grid and how it generates electricity that powers your computer. At some point, you won't be able to advance any further in computer science if you do not fully understand how electricity travels through conducting media (both wire and wireless). A real, true computer scientist should be able to memorize and recite names of all the existing programs and programming languages without stuttering. Helpful and useful thing is also to know some interesting anecdotes from the lives of famous computer researches, like Dijkstra, Turning, Lovelace, Kolmogorov.

---
Tags: programming-languages, lambda-calculus, functional-programming, programming-paradigms, logic-programming
---


title: About NP-completeness and reduction

text:
# Question
Title: About NP-completeness and reduction
Probably this is a basic question but I'm not sure how to finish this proof. I have a problem $X$ and I want to prove that it is possible to reduce $X$ to another problem $Y$. I know that $Y$ is NP-complete and that $Y$ can be reduced to $X$. Can I just conclude that $X$ is also NP-complete and thus $X$ can be reduced to $Y$? Is it necessary to show that $X$ is in NP?

# Answer
You cannot conclude that.

Knowing that $Y$ is NP-complete and reduces to $X$ is only enough to conclude that $X$ is NP-hard.

To show that $X$ can be reduced to $Y$ you will have to either prove that $X\in NP$, or show a reduction directly (don't do this, it is probably harder than just solving $X$ itself).
> 1 votes

---
Tags: complexity-theory, np-complete
---


title: Computing tr(ABCD...)

text:
# Question
Title: Computing tr(ABCD...)
Suppose we have $k$ $n\times n$ matrices $A,B,C,\ldots$. Is there a way to compute/approximate the trace of their product much faster than computing/approximating the full matrix product? IE, computing

$$\text{tr}(ABC\ldots)$$

A related problem of computing vector matrix product $v'ABC$ can be done in $O(n^2)$ time by skipping most of the computation needed for the full matrix product, so I'm wondering if there's a trick to speed up the trace as well

# Answer
> 2 votes
For the worst-case time complexity, no algorithm faster than $\Theta(n^{\omega})$ time is known, even for the approximation version.

Indeed, there is a simple reduction from the triangle counting problem to the trace computation of a product matrix. Let $A$ be an adjacent matrix of an undirected graph, then $\mathrm{tr}(A^3)/2$ is the number of triangles of the graph. Note that this reduction preserves approximation factors.

As far as I know, this is the best-known way to count triangles in dense graphs. I don't have a proper reference but see this question on TCS.SE https://cstheory.stackexchange.com/questions/48539/fastest-approximate-triangle-counting-algorithms-in-dense-graphs for example.

---
Tags: algorithms, complexity-theory, matrices
---


# Question
Title: Online approximation algorithm for median?
Is there a well-known or (relatively) easily-implementable streaming algorithm for approximating the median of the last, say, $k$ elements of a stream $c\_1,c\_2,c\_3,\dots$?

The scenario is: I have a stream of numbers, and at any point in the streaming process I should be able to query for the (approximate) median in the last $k$ elements.

Thanks!

# Answer
There is an incredibly simple to implement algorithm available in Qiang Ma, S. Muthukrishnan, Mark Sandler. Frugal Streaming for Estimating Quantiles:One (or two) memory suffices. CoRR abs/1407.1121 (2014)

The algorithm you are searching for is Algorithm 1 in the paper. It uses just one unit of space to store the variable. Another, more accurate algorithm, uses two units of space and is shown in the paper as Algorithm 3. Algorithm 1 works as follows. Initialize a variable $m$ related to the estimated value of the median to zero. For each incoming stream item $x$, if $x \> m$ then increase $m$ by one, otherwise decrement $m$ by one. Despite its simplicity, the analysis shows that the algorithm is quite effective.

Of course much better algorithms for tracking not just the median but all of the quantiles exist. Among the latest relative-error approximation algorithms, you can take into account DDSKETCH and UDDSKETCH (implemented and used by TimescaleDB). The source code for both is freely available (e.g., this is the UDDSKETCH repository).
> 2 votes

# Answer
If you need the exact median, store the last $k$ elements in a self-balancing binary search tree. Also keep a linked list of the last $k$ elements. At each time step you can delete the oldest element (the list will tell you which one) from the tree, then insert the newest one into the tree. It is easy to obtain the median from the tree in $O(\log k)$ time. Thus, you will do $O(\log k)$ work at each time step, and you will need $k$ space.

If you want to use much less than $k$ space, and are satisfied with the approximate median (you don't need the exact value), you can use various methods for approximating a streaming histogram.
> 0 votes

---
Tags: optimization, approximation, online-algorithms
---


# Question
Title: Number of nodes of a binary tree at height $i$
It is well known that at height $i$ the number of nodes is bounded by $ \frac{n}{2^{i+1}} $, for example there are at most $n/2$ leafs.

Now, it makes sense only if we're taking $ \left\lceil \frac{n}{2}\right\rceil $, because for example, a binary tree with $7$ nodes has $4$ leafs at most.

My question is: why do we take $ \left\lceil \frac{n}{2}\right\rceil $ and not $ \left\lfloor \frac{n}{2}\right\rfloor $?

Asympotically, isnt it safer to assume we have more nodes then there actually are?

# Answer
> 1 votes
We use $\lceil \frac{n}{2} \rceil$ instead of $\lfloor \frac{n}{2} \rfloor$ since our task is to find an *upper bound*.

To understand this, lets take for example two real positive numbers $0\<x\<y$. In this expression, $y$ is an upper bound for $x$, but is not necessarily a whole number. However, both $\lceil y \rceil$ and $\lfloor y \rfloor$ are whole numbers. We still want to retain a similar bound, but now using $\lceil y \rceil$ or $\lfloor y \rfloor$ instead of $y$.

Note, that $y\le \lceil y \rceil$, and therefore $x\<y\le \lceil y \rceil$ and thus $\lceil y \rceil$ is an upper bound.

But $\lfloor y \rfloor \le y$, and thus it is not necessarily true that $x \< \lfloor y \rfloor $. For example, $x=0.5,y=0.75$ will be a counter-example, since $\lfloor y \rfloor=0 \< x$.

Therefore, for correctness we must use the ceiling for upper bounds. Similarly, for lower bounds we will use the floor instead.

As a side note, asymptotically taking a ceiling is equivalent to taking a floor, since they must both be at most distance $1$ from each other: $\lceil y \rceil \le \lfloor y \rfloor + 1$.

---
Tags: binary-trees
---


# Question
Title: Dijkstra complexity analysis using adjacency list and priority queue?
I just got to look at the Implementation of Dijkstra using adjacency list and priority queue. The time complexity is $O(E\log V +V)$, I tried looking for the proof but couldn't find one. Any help will be appreciated.

# Answer
> 2 votes
Dijkstra's algorithm visits every node once ($=O(V)$), and tries to relax all adjecent nodes via the edges. Therefore it iterates over each edge exactly twice ($=O(E)$), each time accessing the priority queue up to two times in $O(\log V)$.

Therefore the complexity is $O(E \log V + V)$.

For a proof of the correctness, just look it up at any basic algorithms book, like CLRS.

# Answer
> 0 votes
I want to clarify that I believe the $O(E\log V+V)$ runtime requires a special priority queue implementation: the fibonacci heap. I'm just adding this clarification because I couldn't understand the $O(E\log V+V)$ analysis since I had never heard of the fibonacci heap (currently taking data structures and we never mentioned it). Apparently it has some pretty crazy runtime analyses! https://en.wikipedia.org/wiki/Fibonacci\_heap

A standard n-ary heap would lead to a $O((E+V)\log V)$ runtime.

The proof I'm used to (it would work with fibonacci heap just substitute the better runtimes for the priority queue operations) is what Jakube showed.

Every vertex is pushed into the queue when it is first discovered and popped off when it is processed. This gives $O(V \cdot \log (V))$ ($O(\log V)$ `insert()` and `removeMin()` since in the worst case the queue has almost all of our vertices).

Then every edge will be checked twice. In the worst case, one of those times will be one where we update a distance to another node. So we get $O(E \cdot \log V)$ for all of those.

Combined you end up with $O(V \cdot \log (V) + E \cdot \log V)$ which becomes $\boxed{O((V + E) \log V)}$

With the fibonacci heap the insertions and `removeMin()` calls (the pops) are amortized O(1) and the `decreaseKey()` call is still $O(\log V)$ as far as I understand, so the vertex part goes from $O(V \log V)$ to $O(V)$ and the edge analysis stays the same, hence you get the runtime quoted in the question and selected answer.

---
Tags: graphs, shortest-path
---


title: A complexity class between P and FPTAS

text:
# Question
Title: A complexity class between P and FPTAS
The question is about approximation algorithms to NP-hard optimization problems. For concreteness, let $M$ be a minimization problem with $n$ inputs, where all inputs and outputs are integers in the range $1,\ldots,V$, and $\log V$ is polynomial in $n$, so that the problem size is polynomial in $n$.

A FPTAS (Fully Polynomial Time Approximation Scheme) for $M$ as an algorithm that, for every $\epsilon\>0$, returns a solution with value at most $(1+\epsilon)$ of the optimal solution, in time $\text{poly}(n,1/\epsilon)$.

Define a **RPTAS** (Range-based Polynomial Time Approximation Scheme) as an algorithm that, for every $\epsilon\>0$ and $v\in\\{1,\ldots,V\\}$, returns a solution in the range $\[v,\ldots,(1+\epsilon)v\]$, if and only if the optimal solution is in that range, and runs in time $\text{poly}(n,1/\epsilon)$.

If there exists an RPTAS, then there exists an FPTAS: partition the range $1,\ldots,V$ into intervals $\[(1+\epsilon)^i,(1+\epsilon)^{i+1}\]$ for $i\geq 0$, and run the RPTAS on each range. Note that the number of ranges is $\log\_{1+\epsilon}V = \log V / \log {(1+\epsilon)}\approx \log{V}/\epsilon$, so the total run-time is polynomial in $n$ and $1/\epsilon$.

My question is if the opposite is also true: given an FPTAS, can it somehow be adapted to an RPTAS? Stated differently: denote by FPTAS / RPTAS the class of optimization problems that have an FPTAS / RPTAS respectively. Obviously, P is a subset of RPTAS, and I showed above that RPTAS is a subset of FPTAS. Is it a strict subset (assuming P$\neq$NP)?

More generally: was this notion of RPTAS studied before? I checked the complexity zoo and they do not mention subsets of FPTAS, but maybe it was studied under a different name?

# Answer
> 2 votes
Suppose that you have an RPTAS. For each $v$, you can determine in polynomial time whether the optimal solution is at least $v$ by running your RPTAS on $\[2^iv,2^{i+1}v\]$ for $0 \leq i \leq \log\_2 V$. Now you can use binary search to find the optimal value in polynomial time.

---
Tags: complexity-theory, optimization, approximation
---


# Question
Title: When inserting a new vertex in a DAG, what possible changes are there to the edges
Background: I'm trying to program a generic method to add a node to a Directed Acyclic Graph. This method should allow the caller to specify the possible effects on the graph, specifically the edges.

So far, I have identified the following possible changes, but I'm not sure if this set is complete.

1. Add a new edge from an existing node to the new node
2. Add a new edge from the new node to an existing node
3. Change one existing edge to point to the new node, keeping the existing tail
4. Change one existing edge to originate from the new node, keeping the existing head
5. Splice in the new node between two existing nodes, removing the original direct edge and replacing it with two new edges.

Of course, combinations of these changes are also possible. But is this set of changes complete? My problem in proving the completeness of this set of operations is relating the old and new set of edges. I think it's obvious that changes 1 and 2 keep the old graph as a subgraph of the new graph; changes 1,2 and 5 do not decrease reachability of the existing nodes, but you can create new reachability if you combine changes of type 1 & 2. Changes 3 and 4 can decrease reachability, not increase it.

Just for clarity: I do not consider changes to "unrelated" edges, e.g. adding a new edge between two existing nodes is out of scope.

# Answer
Based on the comments, I missed one case:

6. Add an unconnected node.

I considered another approach to answering the same question. Consider the set of edges E in the original graph, and the set E' after adding the new node. How do these differ?

The missed case was the edge case E=E'. If the two sets are not equal, there are either edges in E that are not in E', edges in E' that are not in E, or both.

The "no unrelated changes" requirement means that any new edge starts or ends in the new node. It also means that an edge which existed in E but not in E' was not simply removed, but changed, and therefore there must also exist a corresponding new edge in E'.

Hence, we have two possible explanations for new edges in E', but only one explanation for edges that have gone missing from E. So if N is the number of new edges in E', and M is the number of missing edges from E, then we know N\>=M. We can match M out of the N new edges to the M missing edges; each of these M pairs of (old edge, new edge) represents a "changed" edge. (This might not be a unique pairing). This will leave N-M edges that are entirely new.

We can split the M changed edges further in two groups; those edges that were changed to point to the new node and those that were changed to originate at the new node. (per the "no unrelated changes" assumption). Similarly, we can divide the new edges in two groups.

At this point, we have found back the categories 1-4 from the original answer. As noted in the comments, the 5th category (spliced in) can be represented as a combination of changes 1+4 or as the combination 2+3. It can make sense to semantically identify this as a unique change, because splicing in one node keeps the graph connected (and it remains a DAG). This gives us the full set of 6 change types that were identified before.

I have intentionally ignored adding edges that both originate and terminate at the new node, because that type of change certainly introduces a cycle. No other single change will introduce a cycle, but it's fairly obvious that if the old DAG had at least one edge, you can trivially add a new node and two new edges to introduce a cycle containing that original edge.
> 2 votes

---
Tags: graphs, dag
---


title: Uses of irreducible control flow

text:
# Question
Title: Uses of irreducible control flow
What are some applications where irreducible control flow is required\*?

I'm particularly interested in programming language features that will be tricky to efficiently compile if the compile target does not permit irreducible control flow. For example, a programming language offering GOTO will generate irreducible control flow for some programs. What other language constructs are like this? For example, is irreducible control flow required to implement resumable exceptions?

I'm also interested in application-level uses of irreducible control flow.

(\*: irreducible control flow graphs (CFGs) can be converted to reducible CFGs at some cost, and also some compiler optimizations can convert reducible CFGs to irreducible CFGs, so what I mean is that the original, unoptimized CFG produced by the source code is irreducible. Less formally, I mean that the "programmer's intent" naturally includes irreducible control flow)

# Answer
Spitballing here, but the automata used to implement regular expressions, inside a lexical analyzer for example, could have irreducible control flow. This might happen for example if your lexer bounces back and forth between states (think "normal", "string literal", "comment") and if the automaton is compiled down to code, not interpreted.
> 2 votes

---
Tags: compilers
---


title: What does zsh: suspended ./a.out mean?

text:
# Question
Title: What does zsh: suspended ./a.out mean?
I was writing a program to count lines from an input text stream. This is the program. It compiles perfectly but when I execute `./a.out` to get the output my program doesn't seem to run. I enter the text and then enter the command `^z` (control z) and it shows the error mentioned. (`zsh: suspended ./a.out`)

I just want the program to get me the result which it is not showing.

Can you help me, I have just started learning programming.

This is the program just in case you want to check.

```
include <stdio.h>

int main()
{
  int blank_char, tab_char, new_line;
  blank_char = 0;
  tab_char = 0;
  new_line = 0;
  int c;
  printf("Number of blanks, tabs, and newlines:\n");
  printf("Input few words/tab/newlines\n");
  for (; (c = getchar()) != EOF;)
  {
    if ( c == ' ' ){
      ++blank_char;
    }
    if ( c == '\t' ){
      ++tab_char;
    }
    if ( c == '\n' ){
      ++new_line;
    }
  }
  printf("blank=%d,tab=%d,newline=%d\n",blank_char,tab_char,new_line);
}

```

# Answer
> 1 votes
`Control`+`Z` suspends a job, i.e. it stops it temporarily, and you can restart it by using the commands `fg` or `bg` (resume the job in the foreground or background, respectively, see also `jobs --help`, `fg --help`, `bg --help`). Technically, it asks the kernel to send the `SIGSTOP` signal to the process.

Similarly, `Control`+`C` *kills* the job by sending it the `SIGINT` signal. This makes it impossible to resume the job. (See also `man kill`.)

However, your program waits for *end of file* (EOF). `Control`+`D` (the `^D` character) is a special control character that the terminal interprets as *end of file* (or *end of transmission*). Since your program has a `while` loop that runs until EOF, sending `^D` to the program terminates the `while` loop.

You can read more at TLDP:Controlling Processes, TLDP:Other Key combinations, TLDP:Appendix E. Exit Codes With Special Meanings.

---
Tags: coding-theory, c
---


# Question
Title: Is a one step derivation grammar context free?
Suppose we have a grammar having a one step derivation like

S -\> a

where 'S' is a variable and 'a' is a terminal.

Since this grammar does not pump terminals, can we say that the language generated is context free by using pumping lemma?

# Answer
If $S\to a$ is the only rule of a grammar $G$, then $L(G) = \\{a\\}$ is finite hence context-free.

You cannot use the pumping lemma to prove that the language is context-free for two reasons:

* the conclusion of the pumping lemma is a necessary condition to be context-free, not a sufficient condition. It is often used to prove that languages or grammars are **not** context-free;
* the conclusion of the pumping lemma applies to words with size above a certain threshold (depending on the language). You cannot conclude anything on words below this threshold.
> 3 votes

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


# Question
Title: Irregularity of $\{a^x b^y c^z : x=2y \lor y>z\}$
> Show that $L=\\{a^x b^y c^z : x=2y \lor y\>z\\}$ is not regular using the pumping lemma.

I know that in order to use the pumping lemma, I have to assume that $L$ is regular. Then I know that there is a $p$ such that every $w \in L$ such that $|w| \ge p$ can be represented as $xyz$ with $|y| \ne 0$ and $|xy| \le p$, so that $xy^iz \in L$ for all $i \geq 0$. But I have not been able to choose $w \in L$ that serves me to finish with the lemma, taking into account the restrictions that $L$ has.

# Answer
> 1 votes
Simpler using Myhill-Nerode: Given a string $b^y$, $y ≥ 1$. Which is the longest string $c^z$ such that $b^y c^z$ is in L? The answer is different for every for every y, therefore a state machine must end in different states after processing $b^y$ for each y, therefore L cannot be recognised by a finite state machine.

# Answer
> 0 votes
Suppose towards a contradiction that $L$ is regular, and let $n \ge 1$ be its pumping length.

Consider the word $a^{2n}b^nc \in L$. By the pumping lemma there is some value of $k \in \\{1, \dots, n\\}$ such that, for every $i \ge 0$, the word $a^{2n+(i-1)k} b^nc$ also belongs to $L$.

Picking $i=0$ yields the sought contradiction since $a^{2n-k} b^n c \not\in L$. We can then conclude that $L$ is not regular.

# Answer
> 0 votes
It follows immediately from the pumping lemma that there is a k (the pumping length) and a $0 ≤ j ≤ k$ such that $a^k w$ in L implies $a^{k-j} w$, $a^{k+j} w$, $a^{k+2j}w$, $a^{k+3j}w$ etc. must all b in L.

That’s obviously not in L.

---
Tags: regular-languages, pumping-lemma
---


# Question
Title: Questions about the Param and Call instructions of three-address code
Section 6.2.1 of the book "Compilers: Principles, Techniques, and Tools" describes three-address code. Specifically,

Procedure calls and returns are implemented using the following instructions: **$\text{param } x$** for parameters; **call $p, n$** and **$y = \text{call } p, n$** for procedure and function calls, respectively; and $\text{return } y$, where $y$, representing a returned value, is optional. Their typical use is as the sequence of three-address instructions

$$ \text{param } x\_{1} \\ \text{param } x\_{2} \\ \ldots \\ \text{param } x\_{n} \\ \text{call } p, n $$ generated as part of a call of the procedure $p(x\_{1}, x\_{2}, \ldots, x\_{n})$.

However, I am confused about the following explanation:

*The integer $n$, indicating the number of actual parameters in "$\text{call } p, n$", is not redundant because calls can be nested. That is, some of the first $\text{param}$ statements could be parameters of a call that comes after $p$ returns its value; that value becomes another parameter of the later call.*

Could you please show me an example where the integer $n$ is necessary?

# Answer
Consider this sequence of instructions:

```
param u
param v
param w
call f
call g

```

Should the above code be interpreted as calling `g(u,f(v,w))`, or as calling `g(u,v,f(w))`? Without the `n`, there's no way to tell: both compile to the same assembly code.

A way you could discover this would be to try to implement an interpreter for this language, and notice that without the `n` there is no way to implement the `call` because it is not clear how far up the stack to look for parameters.
> 2 votes

---
Tags: compilers
---


# Question
Title: A dynamic program to decide whether the solution is in a given range
In the subset sum problem, the input is a list of positive integers $x\_1,\ldots,x\_n$ and an integer $T$, and the goal is to decide whether there is a subset of sum exactly $T$. The problem can be solved by dynamic programming in time $O(n T)$: for every $i\in\\{1,\ldots,n\\}$ and $j\in\\{1,\ldots,T\\}$, we compute whether it is possible to attain a sum of exactly $j$ using the inputs $x\_1,\ldots,x\_i$.

Suppose that, instead of finding a subset of sum exactly $T$, we only ask if there is a subset of sum between $T$ and $T+k n$, for some fixed integer $k$. Initially, I thought that this could be done faster: round down each input $x\_i$ to the nearest multiple of $k$. The inaccuracy for each input is at most $k$, so the cumulative inaccuracy is at most $k n$. Now, we have to consider only $j\in\\{1,\ldots,T\\}$ which are multiples of $k$, so the run-time is in $O(n T / k)$. However, this solves a slightly different problem:

* If there is a subset with sum $T$, then return a subset with sum in $(T- k n, T)$;
* If there is no subset with sum between $T$ and $T+ n k$, then do *not* return a subset with sum $T$.

Is there an algorithm to decide whether there is a subset with sum in $\\{T,\ldots, T+kn\\}$, asymptotically faster than $O(n T)$, for example, in time $O(n T / k)$?

# Answer
Dynamic programming solves the problem in $O(\sum v)$, where $\sum v$ is the sum of item sizes. The subset sum problem is trivial if the item sizes are small and only gets hard when the item sizes grow.

Finding an approximation without a precise range is roughly equivalent to solving the original problem with slightly smaller numbers. But solving it with an exact range is just as hard as the original problem if there is no solution.

Imagine I ask you to decide whether there exists a subset with sum $T \leq sum \leq T+d$. And in addition I guarantee there is no subset with $T \< sum \<T+d$. Then your problem is to decide whether there exists a subset with sum exactly $T$ or exactly $T+d$.
> -1 votes

---
Tags: dynamic-programming, approximation
---


# Question
Title: Finding all solutions to subset sum for integers with bounded weights
Suppose I have the set of weights $W = \\{w\_1,w\_2,\ldots,w\_{50}\\}$ where each $1 \le w\_i \le 60$ is an integer. I am interested in determining **all** subsets (not just one, and not just the number of them) of $W$ with a fixed sum $s$. I realize this is obviously NP-hard, but are there some efficient ways (e.g. dynamic programming) to obtain this result for these relatively nice conditions (e.g. only 50 items, weights integer and bounded)?

# Answer
> 4 votes
The dynamic programming algorithm can be adapted to give all solutions. You create a table $A$. The cell $A\_{k,w}$ contains enough information to enumerate all subsets of $\\{w\_1,\ldots,w\_k\\}$ summing to $w$. When $k = 0$, this is trivial. Given $A\_{k-1,\cdot}$, $A\_{k,w}$ points at the two cells $A\_{k-1,w},A\_{k-1,w-w\_k}$ (if they exist). The second pointer is also annotated with $w\_k$. If you look at $A\_{50,W}$, you can reconstruct all subsets by considering all paths going all the way to $A\_{0,0}$. This can be done using a simple recursive procedure.

# Answer
> 2 votes
Yes, there is. Have a look at: http://en.wikipedia.org/wiki/Subset\_sum\_problem#Pseudo-polynomial\_time\_dynamic\_programming\_solution

# Answer
> 0 votes
I created a Python module called "subsetsum" that does exactly this. Hope it helps.

# Answer
> -1 votes
Look at the coin change problem. Solutions are known which will give all results. If you have a problem with it, I can provide some code.

See http://www.algorithmist.com/index.php/Coin\_Change for example

---
Tags: dynamic-programming, np-hard
---


# Question
Title: Find a minimum-cardinality Hall-violator
Given a bipartite graph $(X,Y，E)$, in which there is no perfect matching, I want to find a smallest subset that violates Hall's condition, i.e., a minimum-cardinality set $S \subseteq X$ for which $|N(S)|\<|S|$.

This problem is the optimization version of a former question Finding a subset in bipartite graph violating Hall's condition, from which I know there exists a polynomial-time algorithm for finding such $S \subseteq X$. Does there exists a polynomial algorithm for the optimization problem?

# Answer
This problem is $\mathsf{NP}$-hard. The problem is also known as Hall set problem and there is a reduction from Clique problem. See Theorem 3.2.5 from this thesis.

---

I was thinking along the direction of the Minimum $k$-Union problem. Then, I came across this thesis.
> 3 votes

# Answer
This is not an answer but a collection of notes.

## ILP formulation

Consider the following integer linear program:

\begin{align} \text{minimize} && \sum\_{i\in X} x\_i \\ \text{subject to} && y\_j - x\_i \geq 0 && \forall (i,j)\in E \\ && \sum\_{i\in X} x\_i - \sum\_{j\in Y} y\_j \geq 1 \\ && x\_i\in\\{0,1\\} && \forall i\in X \\ && y\_j\in\\{0,1\\} && \forall j\in Y \end{align} In this program, there is a variable $x\_i$ for each node $i$ in $X$, and a variable $y\_j$ for each node $j$ in $Y$. Let $S$ be the subset of $X$ defined by $\\{i\in X: x\_i=1\\}$, and $T$ the subset of $Y$ defined by $\\{j\in Y: y\_j=1\\}$.

First, we show that every feasible solution corresponds to a Hall violator:

* The constraints $y\_j -x\_i \geq 0$ ensure that, if some vertex $i$ is in $S$, then all its neighbors are in $T$, so $T\supseteq N(S)$.
* The constraint $\sum\_{i\in X} x\_i - \sum\_{j\in Y} y\_j \geq 1$ guarantee that $|S| \> |T|$, so $|S| \> N(S)$ and $S$ is a Hall violator.

Next, we show that every Hall violator corresponds to a feasible solution. Indeed, if $S$ is a Hall violator, then taking $T = N(S)$ yields a feasible solution.

Therefore, minimizing $|S|$ yields a minimum-cardinality Hall violator.

In general, integer programs are NP-hard, but maybe this specific program can be solved efficiently?

## Inclusion-minimal Hall violator

there is a polynomial-time algorithm for a closely-related problem: finding a *minimal* Hall violator (one that does not contain a smaller Hall violaor). It is described in Lemma 2.1 of following paper:

Gan, Suksompong and Voudouris: Envy-freeness in house allocation problems, Mathematical Social Sciences, 2019.

## Relation to vertex cover

The question is related to the problem of Minimum vertex cover with minimum overlap of one side . Suppose we have a minimum vertex cover $C$ of size $m$. By Konig's theorem, $m$ also equals the size of the maximum matching, so $m \< n$.

Since $C$ is a vertex cover, any vertex not in $C$ must have all its neighbors in $C$. So $N(X\setminus C)\subseteq Y\cap C$. Hence: \begin{align} |N(X\setminus C)| &\leq |Y\cap C| \\ &= m-|X\cap C| \\ &= m-n+|X\setminus C| \\ &\< |X\setminus C| \end{align} so $X\setminus C$ is a Hall-violator. Now, if $X\cap C$ is large, then $X\setminus C$ is small.

However, I am not sure that finding a $C$ which maximizes $X\cap C$ also yields the smallest Hall violator.
> 2 votes

# Answer
**tl;dr**: I've found a fatal gap in this proof that I've been unable to close. I'll leave this answer up in case either: a) I figure out how to fix it or b) it inspires someone else to figure out how to fix it.

---

Let $G = (X \cup Y, E)$ be a bipartite graph without a perfect matching. We'll say that a subset $S$ is *deficient* if $|N(S)| \lt |S|$. We are looking for a minimum, deficient subset of $X$. The general approach will be to identify potential minimum, deficient sets by characterizing (and finding) all the mini*mal*, deficient sets, i.e.: deficient sets $S\subset X$ that contains no deficient subsets. Let's make a few observations on the properties of these minimal, deficient sets.

**Observation 1**: A subset $S$ is a minimal deficient subset of $X$ iff for all $s \in S$, the set $S\setminus \\{s\\}$ has a perfect matching in $G$. This is just Hall's Theorem.

**Observation 2**: If $S$ is a minimal deficient subset of $X$, then for all $s\_1, s\_2 \in S$, there exists a path in $G$ from $s\_1$ to $s\_2$. Otherwise, we could decompose $S$ into two (or more) components, at least one of which would have to be deficient, thus contradicting minimality.

Now, let us fix $M$, some maximum matching in $G$. Let $X' \subset X$ and $Y' \subset Y$ be the vertices that are matched by $M$ and let $U = X\setminus X'$ be the subset of unmatched vertices in $X$. For any subset $S$ of $X$, we will also denote $m(S)$ as the set of vertices in $G$ reachable from $S$ via $M$-alternating paths.

In an answer to the question linked in the OP, we see a proof that if we take $S = U \cup (m(U) \cap X)$ then $S$ is deficient. Careful reading of that proof reveals that it works not just for $U$ but any subset of $U$. That is to say, if we take any subset $U\_1 \subseteq U$, then $U\_1 \cup (m(U\_1) \cap X)$ is a deficient subset of $X$. In particular, we may take $U\_1$ to be a singleton set. For any $u \in U$, let's define $D\_u = \\{u\\} \cup (m(\\{u\\}) \cap X)$.

**Lemma 1**: $D\_u$ is a minimal, deficient set for all $u \in U$.

**Proof**: We'll take for granted that $D\_u$ is deficient via proof given in the previously referenced answer. To show that $D\_u$ is minimal w.r.t. deficiency, we observe that $D\_u \setminus \\{u\\}$ is simply a subset of $X'$, hence there exists a perfect matching for it inside of $G$ (just take the restriction of $M$ to $D\_u\setminus \\{u\\}$). For any other $y \in D\_u$, we follow the $M$-alternating path from $y$ to $u$, flip all the edges along this path, and obtain a perfect matching of $D\_u \setminus \\{y\\}$ in $G$. So, by Observation 1, $D\_u$ is a minimal, deficient set. $\square$

Ok, now that we've identified one collection of minimal, deficient subsets of $X$, we need to ask: what about any others?

To add a little structure, let us consider any set $S \subseteq X$ to be in the form $S = U\_1 \cup Z\_1 \cup Z\_2$ where $U\_1 \subseteq U$, $Z\_1 \subseteq m(U\_1)$ and $Z\_2 \subseteq X' \setminus m(U\_1)$. In other words, we break $S$ into the portion that's unmatched by $M$ ($U\_1$), the portion that's reachable from $U\_1$ via $M$-alternating paths ($Z\_1$), and the portion that's not reachable from $U\_1$ via $M$-alternating paths ($Z\_2$). It's trivial to observe that if $S$ is a deficient set, then $U\_1$ must be non-empty.

Via Lemma 1, we have covered the case where $Z\_1 = m(U\_1)$ and $Z\_2$ is empty. This leaves three cases to examine:

1. $Z\_2$ is non-empty
2. $|U\_1| \> 1$ and $Z\_1 \subsetneq m(U\_1)$
3. $Z\_1$ and $Z\_2$ are both empty (i.e.: $S \subseteq U$).

**Lemma 2**: If $S = U\_1 \cup Z\_1 \cup Z\_2 \subseteq X$ is such that $Z\_2 \neq \emptyset$, then $S$ is not a minimal, deficient subset of $X$.

**Proof**: Let $M(Z\_2)$ be the elements of $Y$ that are matched with $Z\_2$ in $M$. By definition, there can be no edges from $U\_1$ nor $Z\_1$ to $M(Z\_2)$ since that would imply an $M$-alternating path from $U\_1$ to vertices in $Z\_2$.

If $S$ is a minimal, deficient set, then every subset of $S$ has a complete matching. In particular, $U\_1 \cup Z\_1$ has a complete matching, say $M\_1$. By our previous observation, we note that this complete matching $M\_1$ does not use any of the vertices in $M(Z\_2)$. Thus, the matching formed by using $M\_1$ to match $U\_1 \cup Z\_1$ and $M$ to match $Z\_2$ is a complete matching for $S$, contradicting the assumption that $S$ was deficient. $\square$

In a previous version of this answer, I had neglected case 2), assuming that it was somehow covered during the proof of Lemma 1. However, this is not the case. There can exist minimal, deficient sets which do not look like $D\_u$. The following diagram shows such an example. Taking the bolded edges as the matching $M$, we can see that $S = \\{A, B, C\\}$ is a minimal, deficient set and is not of the form $D\_u$. I haven't yet been able to find an effective characterization of minimal deficient sets that fall into case 2, so I am currently unable to complete this proof.
> 2 votes

---
Tags: np-hard, matching, bipartite-matching
---


# Question
Title: Resolution algorithm does not seem to generate the empty clause
Let's assume I have the following 3 clauses:
$\neg T$,$\neg Q$, ($\neg P \lor Q \lor S \lor T)$,$(\neg U, T, \neg S)$,$(\neg U, T, P)$

and I want to see if our KB entails $\neg U$ so I tried to apply the resolution algorithm like below:

$$ (\neg P \lor Q \lor S \lor T) \land \neg T \land \neg Q \land (\neg U \lor T \lor \neg S) \land (\neg U \lor T \lor P) \land U $$ By applying the algorithm on the first two clauses we'll have: $$ (\neg P \lor Q \lor S) \land (\neg Q) \land (\neg U \lor T \lor \neg S) \land (\neg U \lor T \lor P) \land U $$ Again by applying the algorithm on the first two clauses we'll have: $$ (\neg P \lor S) \land (\neg U \lor T \lor \neg S) \land (\neg U \lor T \lor P) \land U $$ By applying full resolution on the first two clauses(for $S$) we'll have: $$ (\neg P \lor \neg U \lor T) \land (\neg U \lor T \lor P) \land U\\ \rightarrow (\neg U \lor T) \land U\\ \rightarrow T $$ I don't know where to go from here. Obviously, our knowledge base entails $\neg U$ and the resolution algorithm is supposed to be complete, but I don't know which step in my solution is wrong.

# Answer
> 4 votes
Here is a simpler example. The clauses $A \lor B$, $\lnot A$, $A$ are clearly contradictory. Applying resolution, we resolve the first two clauses, and are left with the two clauses $B$ and $A$. Now we are stuck.

Your issue is similar. When applying the Resolution rule, we don't remove the resolved clauses. Rather, we retain them. The completeness of Resolution states that if the original clauses are unsatisfiable, then there is a way to repeatedly apply the Resolution rule, *not removing the resolvents*, that will eventually produce the empty clause. In fact, the following rule will work:

> Repeat until no longer possible: resolve a pair of clauses which produce a clause not already present.

---
Tags: logic, satisfiability, artificial-intelligence, first-order-logic
---


# Question
Title: Why word embeddings are compared with cosine distance and not euclidean?
In most articles that compare word embeddings they use cosine distance to determine if words are similar. Why?

I guess that euclidean distance should work too. So, my question is: it doesn't? And why cosine distance doesn't fail?

# Answer
Those are two different measures of similarity. You could in principle use either one.

Both metrics are very closely connected. Let $v,w$ be two unit-length vectors (i.e., $\\|v\\|=\\|w\\|=1$), and let $d(v,w)=1-v \cdot w$ be the cosine distance between them. Then the Euclidean distance $\\|v-w\\|$ satisfies $$\\|v-w\\|^2 = 2 d(v,w).$$ In other words, if your embedding vectors are unit-length, there's effectively no meaningful difference between the two distance measures.
> 1 votes

# Answer
In a certain sense, angles between embedding vectors are a more natural measure than their distances. Consider the case when your embeddings are generated using a classification neural network, and the last few operations of this networks are the following:

* Apply the linear transformation to the embeddings: $v \to Av$
* Predict the class by selecting the maximum coordinate: $arg\max\_i (Av)\_i$

In other words, you have vectors $a\_1, \ldots, a\_n$, where $n$ is the number of classes, and you select the max of $\langle a\_1, v \rangle, \ldots, \langle a\_n, v \rangle$, where $v$ is the embedding vector. Comparing two different products: $$\langle a\_i, v \rangle \> \langle a\_j, v \rangle \iff \\|a\_i\\| \cos(a\_i,v) \> \\|a\_j\\| \cos(a\_j,v)$$ Since $\\|a\_i\\|$ and $\\|a\_j\\|$ are fixed, the only things that actually depend on $v$ are $\cos(a\_i,v)$ and $\cos(a\_j,v)$. While it doesn't directly explain why $\cos(v\_i,v\_j)$ is a good similarity measure, it at least makes it look more natural than distances.
> 1 votes

---
Tags: machine-learning, natural-language-processing
---


title: Euler Tour in Christofides Algorithm

text:
# Question
Title: Euler Tour in Christofides Algorithm
The penultimate step of the Christofides algorithm in solving the TSP asks us to find an Eulerian tour of the subgraph formed by uniting the MST of the original graph and MPM of a subgraph. I understand the starting point for the Eulerian tour will make a difference to the Hamiltonian circuit found after deleting the duplicate vertices in the next step. I am wondering if there is a way of finding what the best Euler tour would be? Or would you have to test every single one? This would seem inefficient for cases with lots of cities to visit.

Thanks for your help in advance!

# Answer
The problem of finding the minimum-weight cycle from the Euler tour computed by Christofides algorithm is called *minimum-weight Christofides shortcutting problem* \[1\]. Papadimitriou and Vazirani \[2\] prove this problem is NP-hard even for planar Euclidean TSP.
> 1 votes

---
Tags: algorithms, shortest-path, traveling-salesman
---


title: The origin of list data structure

text:
# Question
Title: The origin of list data structure
Does anyone know when the list data structure was mentioned in computer programming/algorithms? Who gave birth to this list concept?

# Answer
> 8 votes
Knuth gives a good overview on the history of lists and linked data structures. From *The Art of Computer Programming*, Volume I, Section 2.6:

> Linked memory techniques were really born when A. Newell, J. C. Shaw, and H. A. Simon began their investigations of heuristic problem-solving by machine.

# Answer
> 3 votes
The first use of linked lists in their modern form seems to have been by Peter Luhn in 1953, when he implemented a chaining-based hash table on the IBM 701 machine.

Linked lists are often misattributed as being due to Newell et al. during their development of the IPL language (an early version of lisp), but that wasn't until 1956. The IPL language did *popularize* linked lists, however. It just didn't invent them.

A good reference is pages 457 and 458 of Knuth's Art of Computer Programming Vol 1.

# Answer
> 2 votes
List processing is simultaneously three things in the development of computer science. (1) It is the creation of a genuine dynamic memory structure in a machine that had heretofore been perceived as having fixed structure. It added to our ensemble of operations those that built and modified structure in addition to those that replaced and changed content. (2) It was an early demonstration of the basic abstraction that a computer consists of a set of data types and a set of operations proper to these data types, so that a computational system should employ whatever data types are appropriate to the application, independent of the underlying machine. (3) List processing produced a model of designation, thus defining symbol manipulation in the sense in which we use this concept in computer science today.

Computer Science as Empirical Inquiry: Symbols and Search (1975 Alan Turing Award Lecture - Allen Newell and Herbert A. Simon)

---
Tags: algorithms, data-structures, linked-lists, lists
---


# Question
Title: Edmonds Karp time complexity based on graph's diameter
Suppose we have a graph such that we want to apply a maximum flow algorithm(for example Edmonds Karp) on it. And suppose we only know that **graph's diameter is 70** so we want to calculate that's time comlexity .
As you know , Edmonds Karp time complexity is O(V.E^2).

We can conclude that we must know V and E of the graph to compute it's worst case time complexity. But I don't know how to find vertices or edges of the graph based on the diameter . Any ideas?

# Answer
Whenever you think about graphs of bounded diameter, you should consider what happens when you add a universal vertex. A universal vertex is a vertex whose neighborhood is the entire graph.

Suppose that you are given an instance $G, s, t$ with $n$ vertices and $m$ edges. Multiply all capacities with $2(n+m)$. Then you add a universal vertex with capacities 1 on every edge. The diameter of this new graph is 2, but to find the maximum flow, you have to compute the maximum flow of the original graph. If you take the final flow and divide it by $2(n+m)$ and floor it, you get the maximum flow of $G$.

The two problems are equivalent.
> 2 votes

---
Tags: algorithms, graphs
---


# Question
Title: Any context-free grammar generating a regular language is unambiguous
I am not sure whether this statement is true or not. Could there be an example of CFG generating a regular language and is ambiguous?

# Answer
Consider the grammar:

> $S\to aS\mid Sa\mid \varepsilon$

or even simpler, the grammar:

> $S\to S \mid \varepsilon$
> 0 votes

---
Tags: automata, context-free, ambiguity
---


# Question
Title: If the time hierarchy theorem holds relative to every oracle, what about a halting(RE) oracle?
I may be misunderstanding this. But the halting problem ∈ RE-complete. P ⊂ RE EXP ⊂ RE. therefore EXP^RE = P^RE = RE(my logic might be(is probably)) wrong here, please edit it if it is to be right) Hopefully you get the idea.. Isn't the time hierarchy theorem supposed to hold relative to every oracle, but here it seems as if every single complexity class collapses into whatever class O(1) is. I'm probably wrong here in some context. I'm very new to this so if you down-vote please explain why.

# Answer
> 3 votes
The problem with your reasoning is the precise definition of $RE$-completeness.

$RE$-complete is defined in terms of **computable** many-one reductions. This means that you may not be able to solve every question in $O(1)$ by applying the oracle, since you don't know how much time the reduction itself needs to take.

---

For completeness of the answer, on why we care about the type of reduction:

An oracle is defined to be a "black box" that can solve a single pre-defined language. For example, you can ask about an oracle to SAT, or Vertex-Cover. And you can ask about an oracle to the halting problem - but what you cannot do, is ask for an oracle of a family of languages. You might be confused since sometimes people say "oracle to NP" - what they really mean is an oracle to some NP-complete problem, say an oracle to SAT. Since NP-completeness is defined relative to polynomial reductions, this is not a problem to say you have an "oracle to NP".

---
Tags: time-complexity, halting-problem, oracle-machines
---


# Question
Title: It's possible to solve this problem in $O(n)$?
Suppose given two strings $s\_1$ and $s\_2$ each of length $n$.

We consider $s\_1$ and $s\_2$ as dual, if one of the following conditions satisfied:

1. Strings are equal.
2. Else, if $n$ is even then:

Divide $s\_1$ into two equal partitions $a\_1,a\_2$, also divide $s\_2$ into $b\_1,b\_2$ then:

* $a\_1$ with $b\_1$ and $a\_2$ with $b\_2$ are dual.
    * Or $a\_1$ with $b\_2$ and $a\_2$ with $b\_1$ are dual.

The description above implies a recursive algorithm in $O(n\log n)$. But my question is that, is it possible to solve the problem in $O(n)$?

# Answer
> 1 votes
This problem can be formulated as a rooted tree isomorphism problem. Let $k$ be the maximum integer such that $2^k$ divides $n$. Then, each input string represents a full binary tree of height $k + 1$. Each leaf $i$ has the label $s\[i n/2^k, (i+1)n/2^k-1\]$ while internal nodes are unlabeled. Two trees are isomorphic if and only if the strings are dual.

Assume the alphabets of the strings can be represented as an integer less than $O(n^c)$ for constant $c$. Then, the bottom-up tree canonization algorithm of Aho-Hopcroft-Ullman solves the tree isomorphism problem in $\Theta(n)$ time in the word-RAM model. Explanation of the algorithm can be found in e.g. this lecture slide https://www.cs.uu.nl/docs/vakken/an/an-isomorphism-2016.pdf.

Because the trees are binary in this case, the algorithm can be simplified. Also, the algorithm can be implemented without integer sorting algorithms if a hash table is used, though the runtime bound becomes an expected time theoretically. Pseudocode is:

labels = {} # a hash table

def canonicalize(s, depth, i):
  if depth == k:
    return s[i] # Assumes n == 2^k for simplicity

  l = canonicalize(s, depth + 1, i * 2)
  r = canonicalize(s, depth + 1, i * 2 + 1)
  if l > r:
      l, r = r, l

  if (l, r) not in labels:
    labels[(l, r)] = labels.len()

  return labels[(l, r)]

label1 = canonicalize(s_1, 0, 0)
label2 = canonicalize(s_2, 0, 0)
print(label1 == label2)
```

---
Tags: algorithms
---