# Question
Title: Why this pattern matching fails in Agda?
Consider function `wa''` (need natural number definition, either in stdlib or `Agda.Builtin.Nat`):

```
postulate comm : ∀ m n -> m + n ≡ n + m

wa'' : ∀ m n -> wa (m + n) ≡ wa (n + m)
wa'' m n with comm n m
...        | refl = { }0

```

The pattern matching on `comm n m` with `refl` fails. But if I add one more match:

```
wa'' : ∀ m n -> wa (m + n) ≡ wa (n + m)
wa'' m n with (n + m) | comm n m
...        | .(m + n) | refl = { }0

```

This code works. Is there any semantics-level difference between these two code snippets?

# Answer
> 4 votes
First, let's desugar the `with`s.

First definition:

```
wa''-aux : ∀ m n -> n + m ≡ m + n -> wa (m + n) ≡ wa (n + m)
wa''-aux m n refl = ?  -- cannot unify n + m with m + n

wa'' : ∀ m n -> wa (m + n) ≡ wa (n + m)
wa'' m n = wa''-aux m n (comm n m)

```

Second definition:

```
wa''-aux : ∀ m n w -> w ≡ m + n -> wa (m + n) ≡ wa w
wa''-aux m n .(m + n) refl = ?

wa'' : ∀ m n -> wa (m + n) ≡ wa (n + m)
wa'' m n = wa''-aux m n (n + m) (comm n m)

```

When checking that `refl` is a valid case, we must *unify* the two sides of the equation it is supposed to be a proof of. Remember that `refl : {x : ℕ} → x ≡ x`, so we must find a *single* value `x` that is βη-equal to both the left-hand side and right-hand side.

In the first case, this means unifying `n + m` with `m + n`, and in the second case, this means unifying `w` with `m + n`. The latter is obviously possible, where we assign `w ↦ m + n` and note that we have done this with the dot pattern `.(m + n)` in `w`'s place. The former is not obvious. How should we unify `n + m` with `m + n`? `n ↦ m` would be wrong: note, for example, that `2 + 3 ≡ 3 + 2`, but `2` does not unify with `3`.

In general, things are made difficult by the fact that Agda can't show that `_+_` is injective. This is for the good reason that it isn't (as our example showed). Agda can show that constructors are injective, justified by the fact that Agda has no quotient types or the like. This is why `suc m` and `suc n` *will* unify. Agda does not try to show that any defined functions are injective, though it in principle could (by getting the user to supply a proof, for example).

---
Tags: unification, agda
---


# Question
Title: Give a $3$-state DFA for $(01 \cup 1)^∗$
How do I change the design to accept the given language, because I think my DFA can accept $001$ as well. Is that correct?

# Answer
> 0 votes
It is correct that your DFA accepts 001, which is wrong.

Here is a strong hint. The three sets of strings accepted by the states should be the set of accepted strings, the set of accepted strings with one "0" attached at the end, the set of the strings that contains two consecutive "0"s. (From that description, you can see how to construct simple DFA by the Myhill–Nerode relation.)

In case the above hint does not ring a bell, here is the full answer, which you can reveal by hovering your mouse over it.

> Let state $S\_1$ be the set of all strings having no consecutive "0"s and ending in "1". Let state $S\_0$ be the set of all strings having no consecutive "0"s and ending in "0". Let state $S\_{00}$ be the set of all strings having two consecutive "0"s. $S\_1$ is the start state and the accepted state. Here are the transitions.
> $\quad(S\_1, 0)\mapsto S\_0$
> $\quad(S\_1, 1)\mapsto S\_1$
> $\quad(S\_0, 0)\mapsto S\_{00}$
> $\quad(S\_0, 1)\mapsto S\_1$
> $\quad(S\_{00}, 0)\mapsto S\_{00}$
> $\quad(S\_{00}, 1)\mapsto S\_{00}$
> It should be easy to see that the above DFA accepts the given set of strings, $(01\cup 1)^\*$.

# Answer
> 0 votes
Remark that at the very minimum what you need in your situation is: two transitions to discriminate 01 (this will take two states) and a third state to use as the pit (to discard words like 00).

Consider the state A, B, C. in which A is both initial and final state. C is the pit.

Transitions:

(A,0) -\> B

(A,1) -\> A

(B,1) -\> A

(B,0) -\> C

(C,0) -\> C

(C,1) -\> C

# Answer
> 0 votes
Here are the equivalence classes of the Myhill–Nerode relation:

* All strings not containing $00$ and not ending with $0$.
* All strings not containing $00$ and ending with $0$.
* All strings containing $00$.

The equivalence classes correspond to the states in the minimal DFA. In other words, these are your three states. When in the first state and reading a 0, you naturally move to the second state (since you're still avoiding 00, but now end with a 0), and when in that state and reading a 0, you naturally move to the third state (since you now contain 00). In a similar manner you can complete the description of the DFA.

---
Tags: finite-automata
---


# Question
Title: Difference between $NP\cap coNP$ and $NEXP\cap coNEXP$
$NP\cap coNP$ is low for itself: $NP^{NP\cap coNP}\cap coNP^{NP\cap coNP}=NP\cap coNP$.

Going up to exponential realm, we are considering similarities of $NP\cap coNP$ to its exponential version $NEXP\cap coNEXP$.

By padding, we already have $$NEXP^{NP\cap coNP}\cap coNEXP^{NP\cap coNP}=NEXP\cap coNEXP$$

Two questions:

1. Though it is unlikely, I do not know for sure whether $NEXP\cap coNEXP$ is low for itself: $$NEXP^{NEXP\cap coNEXP}\cap coNEXP^{NEXP\cap coNEXP}=NEXP\cap coNEXP$$
2. Being more moderate in using oracle machine, we may ask whether $$P^{NEXP\cap coNEXP}=NEXP\cap coNEXP$$

# Answer
1. **NO**. Assume to the contrary that we have that equality, the LHS contains $EXP^{EXP}=EEXP$. So, we deduce that $NEXP=EEXP$.But then the LHS can even contain $EXP^{EEXP}=EEEXP$. That is way too much over $NEXP$.
2. **YES**. By the same proof for $P^{NP\cap coNP}=NP\cap coNP$, the NEXP machine simulates the oracle machine by guessing the oracle answer and the corresponding certificate of membership (non-membership) and verify by the verifier (refuter, resp.) of the NEXP (coNEXP, resp.) machine for the language of the oracle. Then, if at any time the certuficate does not prove the guess, refute and halt. Otherwise, return the same answer as the oracle machine.

Similarly for the coNEXP machine, but you have to accept if a guess is not proven by the certificate guessed after it.
> 1 votes

---
Tags: complexity-theory
---


# Question
Title: Could someone check my recursive program correctness proof that returns $F(x, y) \rightarrow x + y$?
For $k \in \mathbb N$, we define $Q(k)$ as follows:

$Q(k): $ let $x, y \in \mathbb N$ and $x$ is a multiple of $3$ and $k = x + y$, then $FUN(x, y)$ terminates and returns $x + y$

I will prove $Q(k)$ using induction

**Base Case**: let $k = 0 \to iff (x = 0, y = 0)$

By line 1, 2, 5, $FUN(x, y)$ terminates and returns $0 + 0 = x + y$ as wanted

**Inductive step**: Let $k \> 0$. Suppose $Q(j)$ holds whenever $0 \leq j \< k$ \[I.H\]

What to prove: $Q(k)$ holds

Since $k \> 0$, it follows that line 3-7 could run since line 1 is not satisfied.

Therefore two cases: $y \> 0$ and $y \leq 0$

**Case 1**: If $y \> 0$, then line 3, 4, and 7 will run.

Since $0 \leq k - 1 \< k$, this mean IH will apply to $FUN(x+3, y - 1)$

By IH, $FUN(x+3, y - 1)$ terminates and returns $x + 3 + y - 1$

By line 3, 4 and 7. $FUN(x, y)$ terminates and returns $x + 3 + y - 1 - 2 = x + y$ by algebra, and as wanted

**Case 2**: If $y \leq 0$, then line 5, 6, and 7 will run since line 1, 3 are not satisfied

Since $0 \leq k - 1 \< k$, this mean IH will apply to $FUN(x - 3, y )$

By IH, $FUN(x - 3, y )$ terminates and returns $x - 3 + y$

By line 5, 6 and 7. $FUN(x, y)$ terminates and returns $x - 3 + y + 3 = x + y$ by algebra, and as wanted

Therefore $Q(k)$ holds as wanted

This is my attempt above, not sure if I'm correct. I'm pretty confused on how to use IH in this or if my input size is even good. Is it correct?

# Answer
> 0 votes
Your proof had been very well written till it took a sudden turn at "Since $0 \leq k - 1 \< k$, this mean IH will apply to $FUN(x+3, y-1)$". To be ale to apply the IH (induction hypothesis), it is required the sum of the arguments of $FUN$ must be smaller than $k$. However, since we are proving $Q(k)$, $x+y=k$. We have $(x+3)+(y-1)=k+2\gt k\ $, which means IH cannot apply to $FUN(x+3,y-1)\ $. So I am afraid **your proof is incorrect**.

In fact, **your recursive program never terminates for any input**! By carefully tracing the steps in your recursive program, you can verify that $FUN(0,0)$ will go into an infinite loop. Since the only possible way for the program to return any concrete result it must compute $FUN(0,0)$ at some moment, the program never terminates for any input. Apparently, line 2 of the problem is supposed to be (proper indent followed by) "return 0". Your proof is still incorrect for the corrected version of the program, though.

Indeed, it is non-trivial for a newcomer to come up with a rigorous proof since the easiest rigorous proof should involve induction on more than one counter, which is also called multidimensional mathematical induction.

Here is an outline of a correct proof. There are two steps.

1. let $\Bbb N$ be the set of 0 and positive integers. For $k\in\Bbb N$, we define $X(k)$ as the proposition that $FUN(3k, 0)$ terminates and returns $3k$. $X(k)$ can be proved by mathematical induction on $k$.
2. For $n\in\Bbb N$, define $Y(n)$ be the proposition that if $x$ is a multiple of 3, then $FUN(x, n)$ terminates and returns $x + n$. $Y(n)$ can be proved by mathematical induction on $n$. Note that the base case, $Y(0)$ is what is proved in step 1, all $X(k)$.

The hard part of the correctness proof of that algorithm and many similar ones is how to construct the propositions to facilitate mathematical induction on them. Once $X(k)$ and $Y(n)$ have been formulated as above, it is quite easy for anyone to fill the details of mathematical induction.

---

Here are **two exercises** that can be used to practice two-dimensional mathematical induction.

Exercise 1. Let $f:\Bbb N\times\Bbb N\to\Bbb Z$ such that $f(0,0)=0$. Furthermore, for any $m,n\in\Bbb N$, $f(m,n+1)=f(m,n)-2m+2n+1$ and $f(m+1, n)= f(m,n)+2m-2n+1$. Show that $f(m,n)=(m-n)^2$. (This can be proved by one-dimensional mathematical induction on $m+n$. The requirement here is, however, to prove it using a natural two-dimensional mathematical induction.)

Exercise 2. Prove the following algorithm, $PROD$ always terminates and returns the product of $x$ and $y$.

* Precondition: $x$ and $y$ are integers.
* Postcondition: Returns $xy$.
* $PROD(x,y)$:
    1. if both x and y are odd or one of them is 0:
    2. return xy
    3. if x is even:
    4. result = PROD(x/2, y) * 4
    5. else:
    6. result = PROD(x, y/2) * 2
    7. return result

# Answer
> 0 votes
As mentioned by Apass.Jack, you cannot apply IH to the $y\>0$ case, since $ (x+3)+(y-1)=x+y+2\>k$. I think you will want to do induction on $k=\min(x,\\,y)$. Then you have no problem applying IH, since either $x$ or $y$ will always be smaller in the recursive call. The only difficulty here is that in your base case, you now need to cover when one of $x$ or $y$ is zero and the other is arbitrary. I will omit the case when both are zero, for brevity.

In the case that $y$ is zero, then the result will be $\text{FUN}(x-3,\\,0)+3$. If $x$ is a multiple of 3 and positive, then this will eventually give $\text{FUN}(0,\\,0)$ and then 3s will be added until you get $x$ again. This is what you wanted, since $x+y=x+0=x$. Note that the recursive calls retain the conditions that $x\geq0$ and a multiple of 3.

In the case that $x$ is zero, then the result will be $\text{FUN}(3,\\,y-1)-2$, assuming your algorithm terminates, since if the algorithm took the $\text{FUN}(-3,\\,y)+3$ branch, then there would be an infinite recursion. This implies that $y\>0$ initially. Then this branch will continue to be taken until $y=0$, in which case we will return $\text{FUN}(3y-3,\\,0)+3$. This is the case when $x\>0$ and $y=0$, covered above. Then we get $3y-3+3-2y=y=0+y=x+y$. The $-2y$ comes from subtracting 2 recursively $y$ times.

---
Tags: program-correctness
---


# Question
Title: Proving correctness of search algorithms
I've seen correctness proofs for other searching algorithms; however, for this particular algorithm: search in a row-wise and column wise sorted matrix, I'm not able to generate a proper proof.

The algorithm is

```
Let x = element we're trying to search for in the matrix,
    e = current element we're processing in the array.
1) Start with the top right element.
2) Loop: compare this element e with x
...i) if e = x, then return the position of e, since we found x in the given matrix.
...ii) if e > x then move left to check elements smaller than e (if out of binding of the matrix, then break and return false)
...iii) if e < x then move below to check elements greater than e (if out of binding of the matrix, then break and return false)
3) repeat the i), ii) and iii) until you find the element or return false

```

Essentially, we start from the top right and traverse to the bottom left, key points being if element we're searching for is smaller then we go left if it's bigger we traverse down.

I'd like to use contradiction by saying the following: "If we traversed all the way to the bottom left of the algorithm and we didn't find the element we're searching (assuming it's in the matrix), then ..."

However, I'm not sure how to properly follow up the "then" because whatever I say is just repeating what the algorithm does, not really proving anything.

Is there a proper way to do this? Perhaps induction? (but this seems ever more complicated)

# Answer
> 3 votes
The idea of the algorithm is to maintain the following invariant:

> If $x$ is in the matrix, then it is in the submatrix whose top right corner is $e$.

The invariant clearly holds in the beginning, since $e$ is the top right corner of the original matrix.

If $e \> x$ then all elements below $e$ are also larger than $x$, and so $x$ cannot be contained in that column. Therefore the invariant continues to hold with $e$ replaced with its left neighbor (if $e$ has no left neightbor, we can deduce that $x$ is not found in the matrix).

If $e \< x$ then all elements to the left of $e$ are also smaller than $x$, and so $x$ cannot be contained in that row. Therefore the invariant continues to hold with $e$ replaced with its neighbor below (if any).

On an $n \times m$ matrix, this process terminates in at most $n+m$ steps, either finding $x$ or determining that it does not appear in the matrix.

---
Tags: algorithms, correctness-proof, searching
---


# Question
Title: Turing machine - Transition between two states by more than one condition allowed?
Is it allowed to transit between two states $q$, $q'$ by more than one condition? Thank you in advance.

e.g. coming from state $q$, the conditions $(0,0,L)$ and $(1,0,L)$ would lead to the same state $q'$. Is this formally allowed?

# Answer
> 2 votes
Yes, it's allowed.

I guess the underlying problem here is that you're not familiar with reading mathematical definitions. Properly written definitions state *exactly* the criteria that apply. So, for example, if you read the definition "An integer is even if it is divisible by two" you should assume that divisibility by two is the *only* criterion that applies. The definition says nothing about divisibility by three, for example, so divisibility by three doesn't matter.

In our case, the transition function of a Turing machine is defined as a function whose arguments are a state and a tape character, and whose outputs are a state, a tape character and a direction to move the head. No further restrictions (such as "you can't get the same output from two different inputs") are mentioned in the definition, so no further restrictions apply.

---
Tags: turing-machines
---


# Question
Title: How do O and Ω relate to worst and best case?
Today we discussed in a lecture a very simple algorithm for finding an element in a sorted array using binary search. We were asked to determine its asymptotic complexity for an array of $n$ elements.

My idea was, that it is obvisously $O(\log n)$, or $O(\log\_2 n)$ to be more specific because $\log\_2 n$ is the number of operations in the worst case. But I can do better, for example if I hit the searched element the first time - then the lower bound is $\Omega(1)$.

The lecturer presented the solution as $\Theta(\log n)$ since we usually consider only worst case inputs for algorithms.

But when considering only worst cases, whats the point of having $O$ and $\Omega$-notation when all worst cases of the given problem have the same complexity ($\Theta$ would be all we need, right?).

What am I missing here?

# Answer
Landau notation denotes asymptotic bounds on *functions*. See here for an explanation of the differences among $O$, $\Omega$ and $\Theta$.

Worst-, best-, average or you-name-it-case time describe distinct runtime functions: one for the sequence of highest runtime of any given $n$, one for that of lowest, and so on..

Per se, the two have nothing to do with each other. The definitions are independent. Now we can go ahead and formulate asymptotic bounds on runtime functions: upper ($O$), lower ($\Omega$) or both ($\Theta$). We can do either for worst-, best- or any other case.

For instance, in binary search we get a best-case runtime asymptotic of $\Theta(1)$ and a worst-case asymptotic of $\Theta(\log n)$.
> 54 votes

# Answer
Consider the following algorithm (or procedure, or piece of code, or whatever):

```
Contrive(n)
1. if n = 0 then do something Theta(n^3)
2. else if n is even then
3.    flip a coin
4.    if heads, do something Theta(n)
5.    else if tails, do something Theta(n^2)
6. else if n is odd then
7.    flip a coin
8.    if heads, do something Theta(n^4)
9.    else if tails, do something Theta(n^5)

```

What is the asymptotic behavior of this function?

In the best case (where $n$ is even), the runtime is $\Omega(n)$ and $O(n^2)$, but not $\Theta$ of anything.

In the worst case (where $n$ is odd), the runtime is $\Omega(n^4)$ and $O(n^5)$, but not $\Theta$ of anything.

In the case $n = 0$, the runtime is $\Theta(n^3)$.

This is a bit of a contrived example, but only for the purposes of clearly demonstrating the differences between the bound and the case. You could have the distinction become meaningful with completely deterministic procedures, if the activities you're performing don't have any known $\Theta$ bounds.
> 27 votes

# Answer
Not necessarily. In this case, namely binary search on a sorted array, you can see that: (a) binary search takes at most $\[\log n + 1\]$ steps; (b) there are inputs that actually force this many steps. So if $T(n)$ is the running time on a worst-case input for binary search, you can say that $T(n) = \Theta(\log n)$.

On the other hand, for other algorithms, you might not be able to work out $T(n)$ exactly, in which case you might have a gap between the upper and lower bounds for the running time on a worst case input.

Now, for searching a sorted array, something more is true, which is that *any algorithm at all* for searching a sorted array needs to inspect $\[\log n + 1\]$. For this kind of lower bound, you need to analyze the problem itself, though. (Here is the idea: at any time, a search algorithm hasn't ruled out some set $S\subset \[n\]$ of positions where the element it's looking for can be. A carefully-crafted input can then guarantee that $|S|$ is reduced by at most a factor of $2$.)
> 6 votes

# Answer
You are right, many people sloppily use $O$ when they should use $\Theta $. For example, an algorithm analyst may end up with a time function $% T(n)=n^{2}+n+2$ and immediately conclude that $T(n)=O(n^{2})$, which is technically right, but a sharper assertion would be $T(n)=\Theta (n^{2})$. I attribute this oblivious behavior to two reasons. First, many see $O$ to be more popular and acceptable, possibly because of its long history. Recall that it was introduced more than a century ago, whereas $\Theta $ (and $% \Omega $) were introduced only in 1976 (by Donald Knuth). Second, it could be because $O$ is readily available on the keyboard, whereas $\Theta $ is not!

From a technical point of view, however, the main reason careful analysts prefer to use $O$ over $\Theta $ is that the former covers "greater territory" than the latter. If we take your example of binary search and want to use $\Theta $, we will have to make two assertions:\ one for the best case, namely $\Theta (1)$, and another for the worst case, namely $% \Theta (\log n)$. With $O$, we make only one assertion, namely $O(\log n)$. Mathematically, the functions covered by $\Theta $ are also covered by $O$, whereas the converse is not necessarily true.
> 4 votes

---
Tags: algorithm-analysis, asymptotics, landau-notation, reference-question
---


# Question
Title: How to prove that $3$-Spanning-Tree decision problem is $NP$-Complete
I am not sure what problem may reduce to $3$-**Spanning**-**Tree** where $3$-**Spanning**-**Tree** is defined as a decision problem which given an undirected graph $G$ determines if there is a spanning tree of $G$ in which every vertex has degree no larger than $3$.

I have already done this for $2$-**Spanning**-**Tree** using a reduction from Hamiltonian paths as this reduction seemed clear. A spanning tree where each node has degree at most $2$ is essentially a Hamiltonian path in the given graph.

I am not sure if I can extend this idea to $3$-**Spanning**-**Tree** or need to try a different approach entirely, any help would be welcome.

# Answer
> 1 votes
Reduce from Hamiltonian path, attach a dummy vertex to each original vertex. After removing dummy vertices, each original vertex would have degree at most $2$ in the (remaining) of the spanning tree. A connected graph every vertex of which has degree at most $2$ is a path or a cycle.

---
Tags: np-complete, reductions
---


# Question
Title: Understanding the definition of Positivity Constraints in Coq
In Interactive Theorem Proving and Program Development the authors explain constraints on constructors of inductive types in Coq.

For inductive type $T$, a constructor must have the form $t\_1 \rightarrow t\_2 \rightarrow ... \rightarrow t\_l \rightarrow T a\_1 ... a\_k$ where $k$ is the number of arguments of the inductive type $T$.

There are some restrictions placed on the $t\_i$s, which I cannot understand.

> If $t\_i$ is the type of a constant, then $t\_i$ can have the form "$g(Tb\_{1,1} ... b\_{1,k})...(Tb\_{l,1} ... b\_{l,k}),$" provided the expressions $b\_{i,j}$ also satisfy the typing rules, and $T$ does not occur in these expressions or in $g$.

and

> If $t\_i$ is the type of a function, this type can have the form $t\_1'\rightarrow ... \rightarrow t'\_m \rightarrow g(Tb\_{1,1} ... b\_{1,k})...(Tb\_{l,1} ... b\_{l,k})$ but the type $T$ cannot occur in the expressions $t'\_1, ... t'\_m$ or in the expressions $b\_{i,j}$

I am confused on what it means for a type $t\_i$ "*to have the form* of $g(Tb\_{1,1} ... b\_{1,k})...(Tb\_{l,1} ... b\_{l,k})$".

For instance, does **nat** (the type of natural numbers) *have the form* of $g(Tb\_{1,1} ... b\_{1,k})...(Tb\_{l,1} ... b\_{l,k})$"?

If so, how does **nat** obtain such a elaborate form? What is $g$ and what are the terms in the $(l,k)$ matrix $b\_{i,j}$?

If not, am I prohibited from using **nat** in type constructors of inductive types? (That would seem absurd...)

Below I have uploaded a screenshot of the page in question.

Update: I was able to construct a counterexample to the textbook:

```
Definition g := fun x y z : Type => nat.

Inductive T : Set :=
  t : (g T T T) -> T.

```

Here $l = 1, k = 0$, and $t\_1$ can only have the form $g(T)$ but I was able to use $T$ 3 times inside an actual Coq environment.

Edit 2: I think what you guys are saying about the reduced form makes sense so I tried to make another "counterexample"

```
Inductive g (x y z: Type) : Set.

Inductive T : Set :=
  t : (g T T T) -> T.

```

# Answer
Take $l = k = 0$, the matrix of $b\_{ij}$'s has size $0 \times 0$, hence we do not have to defined any $b\_{ij}$, and take $g = \mathbf{nat}$.
> 2 votes

---
Tags: coq, calculus-of-constructions
---


title: What's wrong with this grammar

text:
# Question
Title: What's wrong with this grammar
$L = \\{ w : w \in \\{a, b\\}^\* \land |w|\_a = |w|\_b\\}$ where $|w|\_a$ means number of $a$ in string $w$.

I came up with this grammar:

$S \rightarrow aSb \ |\ bSa \ | \ \epsilon .$

Can someone please tell me what is wrong with it?

# Answer
> 0 votes
Consider the string $w= abba $.
$w$ clearly belongs to $L$ as $|a|=|b|$ but there's no derivation which allows you to generate $w$ given your CFG.

In practice, your rules only deal with the imbalance in the number of $a$'s and $b$'s.
You need to make sure to generate every string $w \in (a+b)^\*$ with the same number of $a$'s and $b$'s.

A CFG grammar for your language can be the following:

$S \rightarrow \epsilon\ |\ aSbS \ | \ bSaS $

---
Tags: context-free, formal-grammars
---


# Question
Title: Is it possible to add every word in a file to a set in $\mathrm{O}(n)$ time?
**The Problem:**

I am currently analyzing a simple program that takes a file of length $n$, splits it into its individual words (seperated by white space) and adds those words to a set:

```
def file_word_set(name):
    with open(name) as f:
        res = set()
        words = f.read().split()
        res.update(words)
        return res

```

**My Analysis**:

Splitting a file of length $n$ into individual words takes $\mathrm{O}(n)$ time. The splitting will produce a list of $k$ strings where $0 \leq k \leq n$. These strings will be of varying length. Inserting a string into a set can be done in $\mathrm{O}(m)$ time where $m$ is the length of that string. This is because we must iterate through each of the characters of the array in order to determine its location in the underlying hash-table. Since the total length of all $k$ strings is no more than $\mathrm{O}(n)$, we will need to consider $\mathrm{O}(n)$ characters in total when building the set. Therefore the function takes $\mathrm{O}(n)$ time.

Is this correct?

# Answer
> Splitting

While splitting you have to touch every element once to see that is a delimiter or not. So it $\in \mathcal{O}(n)$

Assuming a Hash-based Map is used;

> cost of Inserting a string

It is $\in \mathcal{O}(1)$ but if you consider the hash function as not a constant then you have to analyze the hash function itself. When we are talking a hashmap, the string size, usually, is not considered.

> Total insert cost

It is $\in \mathcal{O}(n)$,

> Total cost

It is the sum of all = $ \mathcal{O}(n) + \mathcal{O}(n)= \mathcal{O}(n)$
> 1 votes

---
Tags: complexity-theory, time-complexity, strings, sets, hash-tables
---


title: Proving equivalent definitions for MSTs

text:
# Question
Title: Proving equivalent definitions for MSTs
I am working on the following homework exercise:

Let $G = (V,E)$ be an undirected graph and $c: E \rightarrow \mathbb{R}$ it's cost function. Further let $T = (V,E')$ be a spanning tree in G.

I need to show the equivalence of the following statements:

1. $T$ is a MST.
2. For all $e = \\{x,y\\} \in E \setminus E'$ holds: No edge of the (unique) path from $x$ to $y$ has a higher cost than $e$.
3. For all $e \in E'$ holds: Let $C$ one of the two connected components of $T-e$, then $e$ is an edge with minimal weight in $\delta(V(C))$.

I have done $1) \implies 2)$ and $2) \implies 3)$, but I do not know how to prove $3) \implies 1)$. Could you give me a hint?

EDIT: Please note that $\delta$ refers to the cut, i.e.:

$$\delta(X) = \\{ \ \\{u,v\\} \in E(G) : u \in X \text{ and } v \notin X \\}\\}$$

# Answer
In order to make sure $3)\implies1)\\,$ is true, let us assume that all costs of edges are different. Otherwise, there is a counterexample at Is a set of acyclic |V| - 1 light edges always a Minimum Spanning Tree?.

Here is a hint to prove $3) \implies 1)\\,$. Suppose you have some MST $T'$. Show that $T$ and $T'$ have the same number of edges. Show that $T'$ must contain every minimal cut.
> 1 votes

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


# Question
Title: Karp hardness of a diameter-decreasing planted clique
A diameter-decreasing planted clique in an undirected graph $G(V,E)$ is a set of vertices $\mathcal{C}\subseteq V$ such that if we add all the missing edges between any pair of vertices in $\mathcal{C}$ to turn it into a clique, then the diameter of the obtained graph $G'$ is at most $2$.

**Diameter-decreasing Planted Clique Problem**:

> **Input**: An undirected graph $G(V,E)$ and a natural number $k$
>
> **Output**: **YES** if there exists a diameter-decreasing planted clique of size $k$ in $G$, otherwise **NO**

What is the complexity of this problem?

# Answer
> 0 votes
This problem is $NP$-complete. Reduce from **Exact** **Cover** **by** $3$-**Sets** (**X3C**).

Given an **X3C** instance, its ground set is $\mathcal{U}=\\{e\_1,e\_2,\cdots,e\_n\\}$. Its collecion of $3$-subsets is $\mathcal{C}=\\{s\_1,s\_2,\cdots,s\_m\\}$.

> For each element in the ground set and each subset in the collection, we create a new vertex (which will be referred to by the same name, henceforth).
>
> For each pair of element $e\_i$ and subset $s\_j$ such that $e\_i\in s\_j$, connect the two vertices.
>
> **For $s\_j$'s vertices**: *Connect all pair of $s\_j$'s vertices to make these a clique.*
>
> *Then, create a new vertex $s$ and connect it to all $s\_j$'s vertices.*
>
> **For $e\_i$'s vertices**: *For each pair of elements $e\_{i\_1}, e\_{i\_2}$ that share no common subset, we create a new vertex $e\_{i\_1i\_2}$ and connect it to both of* $e\_{i\_1}$ and $e\_{i\_2}$.
>
> *Then, create a new vertex $e$ and connect it to all $e\_{i\_ai\_b}$'s vertices*.
>
> Connect $s$ and $e$ by an edge. Create a new vertex $t$ and connect it to both of $s$ and $e$.
>
> Call the newly constructed graph $G$. Set $k=\frac n3+1$.

Clearly, we only need to decrease the distance from $t$ to each of $e\_i$'s vertex.

If in the planted clique, we do not choose $t$, then for each $e\_i$, we need to connect it to either $s$ or $e$. Because $s$ and $e$ are all the neighbors of $t$. That is going to exceed the bound of $\frac n3+1$ on the cardinality of the clique.

So, $t$ must be included in the planted clique. Denote by $x$, $y$ and $z$ (*in this order*) the number of vertices included in the planted clique among the $s\_j$'s vertices, $e\_i$'s vertices and $e\_{i\_ai\_b}$'s vertices (*resp*.)

We can see that each one in $x$ vertices of $s\_j$'s vertices will decrease the distance from $t$ to $3$ $e\_i$'s vertices.

Similarly, each one in $y$ vertices of $e\_i$'s vertices will decrease the distance from $t$ to $1$ $e\_i$'s vertices.

And, each one in $z$ vertices of $e\_{i\_ai\_b}$'s vertices will decrease the distance from $t$ to $2$ $e\_i$'s vertices.

So, we must have $3x+y+2z\geq n$. But also, $x+y+z=\frac n3$.

We deduce that $x=\frac n3$ and $y=z=0$

---
Tags: np-complete, np-hard, np
---


# Question
Title: Computational complexity of finding a spanning tree in planar hybergraphs
Using a bipartite graph to represent hypergraphs as described by Wikipedia :

> A hypergraph $H$ may be represented by a bipartite graph $BG$ as follows: the sets $X$ and $E$ are the partitions of $BG$, and ($x\_1$, $e\_1$) are connected with an edge if and only if vertex $x\_1$ is contained in edge $e\_1$ in H. Conversely, any bipartite graph with fixed parts and no unconnected nodes in the second part represents some hypergraph in the manner described above. This bipartite graph is also called incidence graph.

Now if we assume that a hybergraph is planar if and only if it can be represented by a planar bipartite graph. **What is the complexity of finding a spanning tree in planar hybergraphs?** It is also ok if you can provide any source on how to approach this problem.

---

**Note**: It is known that the spanning tree problem of general hybergraphs is $NP$-complete, while spanning tree of $3$-uniform hypergraphs, where all hyperedges are of size $3$, has a polynomial algorithm using matroid matching \[ref\].

**Note**: Under the bipartite representation of hypergraphs the problem of spanning tree becomes equivalent to the problem of finding a subset of vertices that induces a tree such that the tree contains all vertices of one of the bipartitions of the bipartite graph. The problem is a bit similar to the **Induced-Tree** problem defined in this paper, but in this problem the induced tree must contain any set $S$ of vertices as part of the problem input. The **Induced-Tree** problem is $NP$-complete even for planar bipartite cubic graphs.

# Answer
> 1 votes
The answer is in this paper "Tree-Residue Vertex-Breaking: a new tool for proving hardness"

> The Hypergraph Spanning Tree problem in $k$-uniform $2$-regular hypergraphs is $NP$-complete for any $k≥4$, even when the incidence graph of the hypergraph is planar.

Basically, they define a new problem:

> **Tree-Residue Vertex-Breaking** (**TRVB**): given a multigraph $G$ some of whose vertices are marked "breakable," is it possible to convert $G$ into a tree via a sequence of "vertex-breaking" operations (replacing a degree-$k$ breakable vertex by $k$ degree-$1$ vertices, disconnecting the k incident edges)?

Proving this:

> For any k≥4, TRVB is NP-complete when the given multigraph is restricted to be planar and consists entirely of degree-k breakable vertices.

You can see that solving TRVB for the incidence graph of a hypergraph corresponds to solving SPANING TREE in hypergraphs. Where the incidence graph of a hypergraph is isomorphic to the bipartite representation of the hypergraph described above.

---
Tags: complexity-theory, graphs, np-complete, spanning-trees
---


title: KMP - longest palindromic prefix

text:
# Question
Title: KMP - longest palindromic prefix
I wanted to ask if there is a way to use KMP (Knuth-Morris-Pratt) algorithm to find the longest palindromic prefix of a word.

I've seen this algorithm used for determining if a word is rotation of the other for example. We can concatenate first word with itself and look for a pattern which would be the second word (and if found, the answer is yes). But I cannot imagine how could I use KMP for my problem. I am not sure what would the pattern be etc. Can it also be done in linear time using KMP? Thank you.

# Answer
KMP algorithm is able to solve your problem. Suppose your input string can be represented as $S=AB$ where $A$ is a palindrome ($B$ can be an empty string). Now reverse $S$ we can get $S'=B'A$. consider the string $T=S\*S'=AB\*B'A$ where '\*' is a character which doesn't appear in $S$.

As we can see, $A$ is a border of $T$. Conversely, if $X$ is a border of $T$, then $X$ is a palindrome and thus a palindromic prefix of $S$. So the answer of your problem is the longest border of $T$, which directly corresponds to the last item of "fail" array in KMP algorithm.

In fact, in order to obtain the longest palindromic prefix of a word, you can use some general methods such as Manacher's algorithm, which is the best choice in dealing palindromes.

Manacher's algorithm can find the longest palindromic substring for every palindromic center in linear time. For example, if the input string is "abbabbba", then the algorithm can give you the following results (every digit corresponds to a length of palindromic substring centered in its position):

```
a b b a b b b a
101410501252101

```

Manacher's algorithm can solve your problem easily. After getting the longest palindromic substring for every palindromic center, you can simply check for every palindromic center, whether the longest palindromic substring touches the left first character. Consequently, the whole algorithm can be done in $O(|s|)$, where $s$ is the input string.
> 5 votes

---
Tags: algorithms, search-algorithms, string-matching
---


# Question
Title: In most locality sensitive hashing implemensions of SimHash, why is the cosine distance used and not the euclidean distance?
In Chapter 3 of Mining of Massive Datasets, the basis of locality sensitive hashing is explained. They notably mention simhash for the cosine distance, where random hyperplanes are generated, and for each hyperplane, the projection of the vector to be hashed onto the hyperplane's normal is used for hashing the vector. They highlight that to instead measure euclidean distance, one can involve the use of a value $a$ as a segment length, used to split all hyperplane normals into some number of $a$-length segments. For each hyperplane, the segment into which the vector's projection falls into is used as its hash output. Hence the concatenation of this operation on each hyperplane generates a hash.

Yet a number of implementations, including what seems to be one of the most authoritative (falconn), do not use segments at all, and instead simply do a binary output depending on which side of the hyperplane the projection falls into. Why is this ? Why are segments not used ? What does the cosine distance have over the euclidean distance ?

# Answer
> 1 votes
Cosine distance is common in Information Retrieval and other text-based scenarios because text is most easily represented as high dimensional sparse vectors in the word space. A few specific advantages of cosine distance over Euclidean distance are:

* it is fast and simple - particularly, since vectors are sparse, only dimensions present in both vectors need be considered (if the vectors are pre-normalized);
* it works well for vectors with moderate overlap in support, whereas in Euclidean distance coordinates outside of the support of one vector dominate;
* it tends to work well with a wide variety of techniques - for example, in your question, LSH for cosine distance is simpler than LSH for Euclidean distance;
* the magnitude of a vector, which usually corresponds to the length of the document, is not useful - note that cosine distance ignores length but Euclidean distance doesn't;
* it is well-studied so it has momentum.

---
Tags: hash, linear-algebra, hashing, nearest-neighbour, euclidean-distance
---


# Question
Title: Given a NP Algorithm for SAT, do we expect to have Correct and Incorrect Solutions?
I am reading about Boolean Satisfiability Problem and Nondeterministic Algorithms, in the latter defination it says :

> In computational complexity theory, nondeterministic algorithms are ones that, at every possible step, can allow for multiple continuations $...$ **These algorithms do not arrive at a solution** for every possible computational path; however, they are guaranteed to **arrive at a correct solution** for some path

Assume we have a Non-deterministic algorithm for (SAT), does that mean the algorithm will show some computational paths leading to incorrect solutions (Non Satisfying Assignments) and other computational paths leading to correct solutions (Satisfying Assignment) ?

Or it is supposed to show only the correct solutions ?

# Answer
Usually, when one develops an algorithm, there is a proof of correctness. From what I know, "nondeterministic" means the algorithm *may or may not* give you the correct answer, but it will definitely not give you an incorrect one.
> -1 votes

---
Tags: algorithms, satisfiability, nondeterminism
---


# Question
Title: Regularity of language of words containing a square
$$L = \\{w\mid w\text{ contains a substring of form }yy\text{, where }y\text{ is any non-empty string}\\}.$$ Is this language regular? We do not know what $y$ looks like in advance. And why is this language regular or not regular?

# Answer
Slightly more formally, for an alphabet $\Sigma$, the language of repetitive strings over $\Sigma$ is defined as follows. $$ RR = \\{w: w=uyyv \text{ for some }u, y, v \in \Sigma^\*, y \text{ is not empty}\\}$$ The question is, is RR a regular language?

There are three cases.

* $\Sigma$ has one symbol.
WLOG, let $\Sigma=\\{a\\}$. Then $RR = aaa^\*$ is a regular language.
* $\Sigma$ has two symbols.
WLOG, let $\Sigma=\\{a, b\\}$. Suppose $w\in RR$ does not contain $aa$ or $bb$. That is, if an $a$ in $w$ is followed by another symbol, that symbol must be $b$; if a $b$ in $w$ is followed by another symbol, that symbol must be $a$. That means, if $w$ starts with $a$, it must contain $abab$; otherwise, it must contain $baba$. So any string in $RR$ must have one of $aa, bb, abab$ and $baba$ as its substring. Obviously, any string that contain one of those four strings is a repetitive string. So we can write $RR = (a+b)^\ast(aa+bb+abab+baba)(a+b)^\ast$ as a regular expression. Hence, $RR$ is regular.
* $\Sigma$ has 3 or more symbols. This is the most interesting case.
WLOG, let $\Sigma\supseteq\\{a,b,c\\}$. We know there is an infinite sequence $u$ of $a,b,c$'s that has no consecutive repeated substring. Let $u\_k$ be the first $k$ symbols in $u$. For example, if $u=abcabacabcb\cdots$, then $u\_1=a, u\_2=ab, \cdots, u\_6=abcaba, \cdots$. Let $i\<j$ be two positive integers. Then $u\_j=u\_iv$ for some non-empty string $v\in\Sigma^\*$. Since $u\_iv=u\_j\notin RR$ and $u\_jv=u\_ivv\in RR$, $u\_i$ and $u\_j$ are in different Myhill–Nerode equivalent classes for $RR$. So we have infinitely many Myhill–Nerode equivalent classes that are represented by $u\_1, u\_2, \cdots$ respectively. According to the Myhill–Nerode theorem, $RR$ cannot be regular.

In the analysis for the last case, we have used one of Alex Thue's results on non-repetitive string over three symbols. He showed that there are many such strings of infinite length. One of them is given by the following procedure. Let $\Sigma = \\{a,b,c\\}$. Let $A\_0 = a$ and $\phi : a \mapsto abcab, b\mapsto acabcb, c\mapsto acbcacb$. So $$\begin{aligned} A\_0 = a& \\ \phi(A\_0)= a&bcab\\ \phi^2(A\_0)= a&bcab\ acabcb\ acbcacb\ abcab\ acabcb\\ \phi^3(A\_0)= a&bcab\ acabcb\ acbcacb\ abcab\ acabcb \\ a&bcab\ acbcacb\ abcab\ acabcb\ acbcacb\ acabcb\\ a&bcab\ acbcacb\ acabcb\ acbcacb\ abcab\ acbcacb\ acabcb\\ a&bcab\ acabcb\ acbcacb\ abcab\ acabcb\\ a&bcab\ acbcacb\ abcab\ acabcb\ acbcacb\ acabcb\\ \cdots\end{aligned} $$ Note that $A\_0$ is a prefix of $\phi(A\_0)$. By a very easy mathematical induction, we can show that $\phi^n(A\_0)$ is a prefix of $\phi(\phi^{n}(A\_0))=\phi^{n+1}(A\_0)$. (Thinking about this recurrence relation, I can feel the logic beauty of self reference. That is why I cannot help but writing down this example.) So we can specify a unique infinite string, $\omega$ whose prefix can be $\phi^n(A\_0)$ for any $n$. $\omega$ is the wanted string. For a proof that $\omega$ is a string without consecutive repeated substrings, reader can check Axel Thue, *Uber die gegenseitige Lage gleicher Teile gewisser Zeichenreihen*; Norske Vid. Skrifter I Mat.-Nat. Kl.; Christiania; 1912 page 1–67.

In fact, as HendrikJan pointed out, the language of repetitive strings over three or more symbols is not context-free. This fact is proved in Repetitive strings are not context-free by R.Ross and K.Winklmann, RAIRO - *Theoretical Informatics and Applications*, 16 (1982) 191-199.

---

Since the complement of a regular language is also a regular language, the complement of the language of repetitive strings is also regular, too. In fact, if the alphabet has one or two symbols, they are finite languages. All non-repetitive strings over $\\{a\\}$ are $\\{\epsilon, a\\}$. All non-repetitive strings over $\\{a,b\\}$ are $\\{\epsilon, a, b, ab, ba, aba, bab\\}$.

---

**Exercise**. Show that an infinite language that does not contain a square is not context-free.

**Question**. Is the language of almost repetitive strings defined below regular? If no regular, is it context-free? $$ RR = \\{w: w=uyxyv \text{ for some }u, y, v \in \Sigma^\*, y \text{ is not empty}, x\in\Sigma\\}$$
> 6 votes

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


# Question
Title: How do I convert the following GNFA to regular expression?
Here is a GNFA I made from an NFA.

I'm unsure how to treat the node of b(a∪b)\* (the first node after the start node and the one below it). Since it doesn't lead to any goal state, do I disregard it in when I generate the regular expression?

# Answer
> 1 votes
Given an NFA, we can simplify it to an equivalent NFA with possibly fewer states by repeatedly applying the following two pruning steps:

1. Remove any states which are not reachable from the initial state.
2. Remove any states from which no final state can be reached.

In your case, this will result in removing the left bottom state.

---
Tags: automata, finite-automata, regular-expressions
---


# Question
Title: Boolean Algebra Simplifying complex equation
I am trying to simplify the following equation and I am getting stuck on a line and I can't cut it down any further. I'm not sure if certain 'moves' are legal or not.

F(A,B,C,D) = A'B'C' +ACD + A’BCD + A’BC’ + ABC + AB’CD'

After regrouping I got: A'(B'C' + BCD + BC') + A(CD + BC + B'CD')

I thought right after this you'd get 1 because A + A' is 1 and then after that you would get each term in parentheses leftover as the final expression. Is that right?

# Answer
> 2 votes
Whenever you are faced with two Boolean expressions $f,g$ on $n$ variables and wish to know whether they are equivalent, there is a simple algorithm you can apply:

> Go over all $2^n$ possible truth assignments, and check whether $f$ and $g$ have the same truth value on each.

While this is infeasible for large $n$, in your case $n = 4$, so there are only 16 many truth assignments to check; in fact, you could even do this by hand, though it might be less error-prone if you programmed it.

Using this approach, you should be able to tell whether your simplification is valid.

---
Tags: logic, circuits, algebra
---


# Question
Title: Probability that a random hash from a universal family is injective
This is a homework question, I don't want an actual answer, but rather guidance on how to obtain the correct answer. The question is as follows:

In class we saw universal hashing as the solution to processing N elements in the range {0,1,...u-1}, arriving one at a time. Using universal hashing we can get O(1) processing time for each request, but in expectation. Hence sometimes we might get unlucky and processing time might be longer. Consider another scenario where we are given the N requests in advance. Can we process them together and store in a hash table so that any future lookup request for any of these items can be processed in worst case O(1) time (so no uncertainty or expectation here)? In this problem you will design a solution for this, again using universal hashing.

You are given a set S of N items in the range {0,1,...u-1) in advance. Consider the following algorithm that stores these items into a table of size N\*N.

```
SquareHash(S, u)
Input: A set S of N items, an integer u such that
each item is in {0,1, ... , u-1}
Output: A hash table of size N*N and a corresponding hash function
1. Initialize a table T of size N*N
2. While true
        3. Pick a function h uniformly at random from a universal family H
        that maps {0,1, ... , u-1} to {0,1, ... , N*N-1}
        // Assume that this can be done in O(1) time
        4. Insert all the elements of S into T using h as the hash function
        5. If T has no collisions, return (T,h). Otherwise empty T

```

Clearly if the above algorithm terminates then it will produce a table with no collisions and hence any future lookup will be in O(1) time guaranteed. However in the worst case the algorithm might run forever. Show that this is unlikely. In particular, compute the expected running time of the algorithm above. \[Hint: Each time a function h is picked, compute the probability (or a lower bound on it) that the resulting table will have no collisions. Then use the fact that if a coin of bias p is flipped until it turns up Heads, the expected number of flips is 1/p\]

I understand intuitively this is unlikely to run forever. If a hash function causes a collision, it will pick another one until it finds one that does not cause any collisions. However, I am unsure of how exactly to prove this formally and how to compute the expected running time. I know that the probability of two elements colliding is 1/m, where m is the expected range of outputs.

# Answer
By definition, a family of hash functions $H$ with range of size $m$ is universal if for all $x \neq y$ in the domain of $H$, $$ \Pr\_{h \sim H} \[h(x) = h(y)\] \leq \frac{1}{m}. $$ In your case, $m = N^2$. Let the $N$ elements in $S$ be $x\_1,\ldots,x\_N$. Using the union bound, $$ \Pr\_{h \sim H} \[h(x\_1),\ldots,h(x\_N) \text{ not all distinct}\] \leq \sum\_{1 \leq i \< j \leq N} \Pr\_{h \sim H}\[h(x\_i) = h(x\_j)\] \leq \frac{\binom{N}{2}}{N^2} \leq \frac{1}{2}. $$ In other words, a random $h$ is successful with probability at least $1/2$. Therefore the expected number of times until a successful $h$ is chosen is at most $2$.
> 0 votes

---
Tags: algorithms, hashing, pseudocode
---


# Question
Title: What does "Giving an overall running time" mean in this context?
In the following image

The author refers to an overall running time linear to |E|. But the author then says this is at most O(n^2). This seems contradictory because O(n^2) is quadratic time. Did the author mean to write something else? Or am I misunderstanding something?

**EDIT!: My question is: What does the author mean when writing "overall running time linear to |E|"?**

EDIT: More context, define E, which is all the edges and is stored as variable j:

# Answer
> 1 votes
Maybe, a simpler English version is this:

> The computation of $L(j)$ then takes time proportional to the indegree of $j$, *as a result*, it takes time linear in $E$ *in total*.

# Answer
> -1 votes
$n$ is the number of vertices and there are $O(n^2)$ edges in the graph.

---
Tags: algorithms
---


# Question
Title: Find a recurrence relation for merging of sublists of an array
There are $\log n$ sublists each of size $\frac{n}{\log n}$. Write a recurrence relation for merging these lists into an $n$ element list.

**My Approach** Let $m = \log n$. Then, $T(m) = 2T(m/2) + O(n)$, where $O(n)$ is for merge algorithm.

We get $T(m) = 2T(m/2) + O(2^{m})$.

Now solving we get $T(m) = O(n)$.

But intuitively there are $O(\log\log n)$ levels each doing $O(n)$ work so complexity to merge should be $O(n\log\log n)$. Where am I wrong? Please help. Tried hard but unable to get loophole.

# Answer
> 0 votes
The same recurrence relation for the merge sort will work by changing just **base conditions**.

$T(n) = T(n/2) + \theta(n); \ n\> \frac{n}{log\_2n}$

and, $T(\frac{n}{log\_2n})= \theta(1)$

By solving above equation we get,

$T(n)=log\_2n+nlog\_2log\_2n$

# Answer
> 1 votes
The mistake is when converting $O(n)$ to $O(2^m)$, and then varying $m$. In fact, $n$ is constant here and $m$ changes. So the recurrence relation is $T(m) = T(m/2) + O(n)$, whose solution is $T(m) = O(n\log m)$. Substituting $m = \log n$, we obtain $O(n\log\log n)$.

---
Tags: algorithms, sorting, recurrence-relation, arrays, divide-and-conquer
---


# Question
Title: Is every graph with minimum degree $n/2$ connected?
> Claim: Let $G$ be a graph on $n$ nodes, where $n$ is an even number. If every node of $G$ has degree at least $n/2$, then $G$ is connected.
>
> Decide whether the above claim is true or false, and give a proof of either the claim or a counter example.

I drew out a few examples and the claim seems to hold, and I cannot find a counter example to prove it is false, which leads me to believe the claim is true. However, I am having a really hard time generating a proper proof.

# Answer
> 3 votes
Suppose that $G$ is not connected. Consider the *smallest* connected component of $G$.

You take it from here.

---
Tags: graphs, discrete-mathematics, connected
---


# Question
Title: Given a sorted dictionary of words, find order of precedence of letters
This question is found at: https://www.geeksforgeeks.org/given-sorted-dictionary-find-precedence-characters/

Given a sorted dictionary (array of words) of an alien language, find order of characters in the language.

Examples:

```
Input:  words[] = {"baa", "abcd", "abca", "cab", "cad"}
Output: Order of characters is 'b', 'd', 'a', 'c'
Note that words are sorted and in the given language "baa"
comes before "abcd", therefore 'b' is before 'a' in output.
Similarly we can find other orders.

Input:  words[] = {"caa", "aaa", "aab"}
Output: Order of characters is 'c', 'a', 'b'

```

Notice that the solution calls for comparison of adjacent word-pairs only, when discovering new edges. It is unnecessary to add edges from comparing non-adjacent words. This seems straightforward and intuitive to me, but how do we prove it?

An edge-discovery is done by comparing two strings, iterating through their characters, and finding the first pair of characters which differ. The former string's character precedes the latter string's character. In the case of the former string being a substring of the latter, then the edge discovery fails to return a pair. (It's impossible for the latter string to be a substring of the former)

Given a directed acyclic graph built from pairwise edge-discoveries of adjacent pairs `<word[1], word[2]>, <word[2], word[3]>, ..., <word[n-1], word[n]>`. Prove that comparing any two words which are not adjacent will not yield any new information, i.e. the edge-ordering discovered by the new comparison will already have been present, or implied by transitivity of edge-orderings in the existing graph.

Edit to add: I have a prefix-tree-based proof, but I'm no good at writing proofs and would welcome better-written proofs.

# Answer
Thanks to your very well-written question, which makes my answer writing a real pleasure.

**Claim I**: "it is unnecessary to add edges from comparing non-adjacent words."

Let us take a look at how the algorithm pulls information when comparing two words, which is "iterating through their characters, and finding the first pair of characters which differ". Then it obtains the requirement "the former string's character precedes the latter string's character". Use $R\_{i,j}$ to denote the requirement thus obtained from two words `word[i]` and `word[j]`. In term of binary relation, $R\_{i,j}$ can be expressed in the form $\alpha\<\beta$ for some character $\alpha, \beta$. Note $R\_{i,j}$, if satisfied, determines `word[i]` and `word[j]` must be arranged in the given order as in the array `word`. In other words, any strict partial order on the characters that includes $R\_{i,j}$ must sort `word[i]` and `word[j]` in the order as given in the array `word`.

Let $O$ be the minimum strict partial order on the characters that includes $R\_{1,2}, R\_{2,3}, \cdots, R\_{n-1,n}$. Then any arrangement of words must put `word[2]` after `word[1]`, `word[3]` after `word[2]`, ..., `word[n]` after `word[n-1]` if that arrangement is in accordance with $O$. That is, all words must be arranged in the order exactly as given in the array `word`. Since any desired dictionary order, a.k.a. lexicographic order, (which can be obtained by a topological sort according to those n-1 requirements), is a strict total order (and hence also a strict partial order) that extends $O$, no more information is needed to order any pair of words.

Claim I is proved in the sense of the last statement.

---

**Lemma**: Let $\<\_1$ be a strict partial order on a set $S$ and $a,b\in S$. If $a\not\<\_1b$, (which does not implies $b\<\_1 a$), then there is a strict partial order $\<\_2$ on $S$ that extends $\<\_1$ with $b\<\_2 a$.

The lemma says that **if one element is not defined as smaller than another element in a strict partial order, then we can assign the relationship between those two elements the other way around without causing conflict.** It will be clear soon that this lemma is the crux of this answer.

In case that you are not familiar with the terminologies of partial order, here is an equivalent version in term of directed graph. **Given a directed acyclic graph whose transitive closure has no edge going from one particular vertex to another vertex, if you add an edge that goes from the latter vertex to the former vertex, the resulting graph will still be acyclic.** (One can also note that whether a directed graph is acyclic or not will not be changed if we take a transitive closure of the graph. This transitive closure corresponds to the transitivity of the strict partial order.)

I will leave the simple proof of this lemma to you.

---

**Claim II**: "Comparing any two words which are not adjacent will not yield any new information."

Let us continue to use the terms introduced in the proof of Claim I. Before we proceed to a proof, let us define what is existing information. **The existing information** is all requirements $R\_{i,i+1}$ for $1\le i\le n-1$ or, what is equivalent, $O$, the minimum strict partial order which includes those requirements (and their implications), which is able to determine the order relationship of any pair of words in the array `word`.

For the sake of contradiction, suppose comparing `word[i]` and `word[j]` could yield a requirement that can be considered as new information, i.e., assuming this new requirement is $\alpha'\<\beta'$ for some character $\alpha', \beta'$, that relationship between $\alpha'$ and $\beta'$ is not in $O$. By the above lemma, we can extends $O$ with $\beta'\<\alpha'$ to obtain another strict partial order $O'$. Note that $O'$ requires `word[i]` and `word[j]` be arranged in the reverse order of how it appears in array `word`, which contradicts our conclusion above that any strict partial order that extends $O$ must put `word[i]` and `word[j]` in the same order as it appears in array `word`.

Claim II is proved.

---

For an even higher level of rigor, we should also note explicitly what happens when two words, one of which is a prefix of the other one, are compared. We should also mention explicitly the case when the initial array `word` is not consistent, such as `['a', 'b', 'a']`. We should flesh out more details about the strict partial orders. I will not go into such detail, assuming the above explanation is enough to enable readers who are able to read thus far to fill in the details if needed.
> 1 votes

# Answer
Let's denote the words by $w\[1\],\ldots,w\[n\]$. Suppose that $i \< j$ and that $w\[i\],w\[j\]$ first differ on the $t$th coordinate. In symbols, $w\[i\]\_{\<t} = w\[j\]\_{\<t}$ but $w\[i\]\_t \< w\[j\]\_t$ (I hope the notation is obvious).

I first claim that $w\[k\]\_{\<t} = w\[k+1\]\_{\<t}$ for all $k \in \\{i,\ldots,j-1\\}$. Indeed, suppose that $w\[k\]\_{\<t} \< w\[k+1\]\_{\<t}$ for some $k \in \\{i,\ldots,j-1\\}$. Then $w\[i\]\_{\<t} \leq w\[k\]\_{\<t} \< w\[k+1\]\_{\<t} \leq w\[j\]\_{\<t}$, contradicting the assumption $w\[i\]\_{\<t} = w\[j\]\_{\<t}$.

Call an index $k \in \\{i,\ldots,j-1\\}$ *special* if $w\[k\]\_t \< w\[k+1\]\_t$. Let the special indices be $k\_1,\ldots,k\_m$. Then $$ w\[i\]\_t = w\[k\_1\]\_t \< w\[k\_1+1\]\_t = w\[k\_2\]\_t \< w\[k\_2+1\]\_t \cdots w\[k\_m\]\_t \< w\[k\_m+1\]\_t = w\[j\]\_t. $$ This shows that $w\[i\]\_t \< w\[j\]\_t$ follows from $w\[k\_1\]\_t \< w\[k\_1+1\]\_t,\ldots,w\[k\_m\]\_t \< w\[k\_m+1\]\_t$ by transitivity. (Here we are using the fact, proved earlier, that $w\[k\_r\]\_{\<t} = w\[k\_r+1\]\_{\<t}$ for $r \in \\{1,\ldots,t\\}$.)
> 1 votes

---
Tags: graphs, data-structures
---


title: Checking if a kernel is valid

text:
# Question
Title: Checking if a kernel is valid
The kernel is $K(x,z) = \sum\_{i=1}^D (x\_i+z\_i)$

My approach was trying to express $K = \phi(x)^T\phi(z) = (x\_1 x\_2 ... x\_D \quad 1 1 ...1)(1 1 ...1\quad z\_1 z\_2 ... z\_D )^T$ where $\phi$ is 2Dx1 and thus a Kernel.

The solution says:

K is not a kernel. Consider $x\_1 = \[1 \quad 0\]^T \quad x\_2 = \[0 \quad 2\]^T$. Their kernel matrix has eigenvalues −1 and 5.

What explains this discrepancy?

# Answer
> 0 votes
Your confusion is that you're using $\phi$ to denote two different mappings. The first one maps its input $v$ to the vector $\begin{pmatrix} v & \mathbf{1} \end{pmatrix}$, and the second one maps it to $\begin{pmatrix} \mathbf{1} & v \end{pmatrix}$. In the same way we can prove that $-1$ is the square of a real number: $-1 = x \cdot x = (-1) \cdot (+1)$.

---
Tags: machine-learning, kernel-functions
---


title: Strengths and limitations of arrays

text:
# Question
Title: Strengths and limitations of arrays
What are the strengths and limitations of arrays? What considerations go into choosing an array over another data structure, or vice-versa?

# Answer
> 1 votes
Here a simple answer is;

* Arrays

+ allow fast random access in $\mathcal{O}(1)$ to their elements since and they are sequential in memory.
    + $\mathcal{O}(1)$ time write or update an element
    + if not created in heap memory size is very limited.
    + The size is fixed.
* Vectors

+ Access and write is similar to array
    + The size not fixed. When capacity is full, extended.

---
Tags: data-structures, arrays
---


# Question
Title: Which Data Structure should I use to store words from a novel?
So, I was learning Data Structures in Java on my own. And there was a "challenge question" in the book. The question basically asked me to make a data structure that could store all the words in a novel, and then it would associate with the word, where it occurs (like line number and character count) and the frequency of the amount of times it occurs. I was wondering which data structure should I use to store all this while maintaining a relatively Fast look up time and such.

I was thinking either hashmaps or tries, but I don't know which trie to use and how to associate the frequency of the word and stuff

Thanks in advance!

# Answer
> 1 votes
You will probably end up using two nested data structures. I would use a hashmap with the words as keys. The value would be an array/list/set (depending on what you want to do with the occurrence data) containing an item for each occurrence of the word. The item would store whatever you needed (line number, etc). The number of occurrences would just be the size of this array/list/set.

---
Tags: data-structures, java
---


# Question
Title: Why is $\dfrac{1}{2}n^2-3n = \Theta(n^2)$?
By definition:

> For a given function $g(n)$ we denote by $\Theta(g(n))$ the set functions
>
> $\Theta(g(n))$ = $\\{f(n):$ there exists positive constants $c\_1, c\_2$ and $n\_0$ such that $0 \leq c\_1g(n) \leq f(n) \leq c\_2g(n)$ for all $n \geq n\_0$ .$\\}$

We say $6n^3 \neq \Theta(n^2)$ becuase if it was, then there would be:

\begin{equation} 6n^3 \leq c\_2n^2 \Rightarrow n \leq c\_2/6 \hspace{100px} (1) \end{equation}

which is not true because $n$ (size of the input) is not limited to any constant.

But to prove $\dfrac{1}{2}n^2-3n = \Theta(n^2)$ we can write

\begin{align\*} c\_1n^2 &\leq \dfrac{1}{2}n^2-3n \leq c\_2n^2\\ c\_1 &\leq \dfrac{1}{2}-\dfrac{3}{n} \leq c\_2 \end{align\*}

by setting $c\_1=1/14, c\_2=1/2, n\_0=7$ it becomes true.

Here is the problem,

$$\dfrac{1}{2}-\dfrac{3}{n} \leq c\_2$$

implies

$$ n \leq \dfrac{1/2-c\_2}{3} \hspace{100px} (2) $$

why in $(1)$ bounding $n$ is a contradiction, but in $(2)$ it is not?

Thanks

# Answer
Since $n\>0$, $\dfrac 3n \>0$. Hence $\dfrac{1}{2}-\dfrac{3}{n} \leq c\_2$ is implied by $\dfrac 12\le c\_2$.

That is, your (2) is not correct while everything else is fine.

Just in case you cannot see why your (2) is wrong, please take a look at the following deduction. $$ \dfrac{1}{2}-\dfrac{3}{n} \leq c\_2\\ \dfrac{1}{2}-c\_2\le\dfrac{3}{n} \\ \dfrac{1/2-c\_2}{3} \leq \dfrac 1n\\ \dfrac 1n\ge\dfrac{1/2-c\_2}{3} $$ Compare the last inequality with your (2).
> 2 votes

# Answer
Alternatively, you might find it more convenient to work with the limit definition.

To prove that $f(n) = (1/2)n^2 - 3n = \Theta(n^2)$, we must prove that

* (i) $f(n) = O(n^2)$, and that
* (ii) $f(n) = \Omega(n^2)$.

To prove (i), we must show that $\lim\_{n \to \infty} f(n)/n^2 \< \infty$. Plugging in we find that $1/2 \< \infty$, and are done. To prove (ii), we must show that $\lim\_{n \to \infty} f(n)/n^2 \> 0$. Now, we see that $1/2 \> 0$, and are done. It follows from (i) and (ii) that $f(n) = \Theta(n^2)$, concluding the proof.
> 1 votes

---
Tags: asymptotics
---


# Question
Title: Do L-systems have a corresponding automata?
So, I was reading about L-systems and it seems that L-systems are in many ways analogous to context-free grammars. Is there a corresponding automata for this? I can't seem to find anything on the Wikipedia page.

# Answer
Lindenmayer's original papers define them using arrays of finite state machines. The outputs at each time are the states at the next time, which also serve as inputs to the neighbors, much like a cellular automaton. Unlike cellular automata, the machines can output strings, and each additional symbol becomes the state of a new machine in the array.
> 1 votes

---
Tags: automata
---


# Question
Title: Is there an algorithm that can find a solution that solves the most number of equations in a linear system of equations?
My apologies if this question makes no sense. I am trying to find an algorithm that can solve a linear system of equations. Unlike most problems like this, this algorithm does not need to find a solution set that solves the entire set of equations. It only needs to solve the MOST number of these equations. For example, if a given linear system has $n$ equations, then the solution set returned by the algorithm should "fit" the most possible number of equations in the system.

**Example:** if there are $N$ linear equations in a system $S$ of linear equations, then the algorithm should return a solution set that solves $m$ linear equations in $S$, where $m\le N$.

Based on what I have researched, none of the algorithms I know of will do this. Hopefully I am just missing something and I can get pointed into the right direction. Thanks.

Also, I forgot to add in that the given system of equations will have 10,000-1,000,000 variables, with x being Sparse. Is there a mod 2 algorithm or something similar to it that works on very large matricies?

# Answer
> 3 votes
$\mathsf{3LIN}$ is the following problem:

> Given a set of linear equations of the form $x\_i \oplus x\_j \oplus x\_k = b$, where $1 \leq i,j,k \leq n$ and $b$ is a bit, find an assignment for the bits $x\_1,\ldots,x\_n$ that satisfies the largest number of equations.

There is a simple 1/2-approximation algorithm, which simply chooses a random assignment. Such an assignment satisfies half of the equations in expectation, and so at least 1/2 of the optimum. Using the method of conditional expectations, it is routine to derandomize this algorithm.

Håstad, in his paper Some optimal inapproximability results, showed that it is NP-hard to approximate 3LIN to within $1/2+\epsilon$ for any $\epsilon \> 0$. In other words, the trivial algorithm mentioned above gives the optimal approximation ratio.

---
Tags: algorithms, optimization, linear-programming, program-optimization
---


# Question
Title: Find Myhill–Nerode equivalence classes of language $\{0^n1^n: n \in \mathbb{N}_0 \}$
I'm asked to find all equivalence classes of the language

$$L = \\{0^n1^n: n \in \mathbb{N}\_0 \\}$$ where $\mathbb N\_0$ is the set of natural numbers including $0$, i.e., $0, 1, 2, \cdots.$

We have the following definition:

$$(xR\_Ly)\Leftrightarrow (\forall w\in \Sigma^\* xw\in L \Leftrightarrow yw\in L)$$

As I understand, words $x$ and $y$ belongs to different equivalence classes if $\exists z \in \Sigma^\*: xz \in L$ and $yz \notin L$ (and vice versa).

The language $L$ above is not regular so it has infinitely many equivalence classes under $R\_L$. In order to differentiate between two classes, I was thinking about defining the equivalence relation in the following way:

$$xR\_Ly = \text{"}x\[n\] = y\[n\] = 0\text{ and }x\[n+1\] = y\[n+1\] = 1\text{"}$$

with $x\[k\]$ I mean the $k$-th letter in $x$. Under this "approach", all equivalence classes are generated by taking $n$ to be any number $\in \mathbb{N}\_0$.

Under my attempt I have the following questions:

In the definition, nothing is said about $x$ and $y$ in $(xR\_Ly)$. Do I have to assume that those are two arbitrary words that **are already** in $L$? (If not, then my approach doesn't work).

For a fixed $n \in \mathbb{N}\_0$ I think $\exists$ just one word in the class $C\_n$. Then does it mean that the unique word in $C\_n$ is only equivalent to itself?

I think I'm not even close to the answer, so would appreciate any help with this.

# Answer
> 2 votes
For string $s$, call a string $e$ an extender of $s$ (with respect to $L$) if $es$ in $L$.

$x$ and $y$ are in the same equivalence class iff (a string is an extender of $x$ iff it is an extender of $y$).

Let us describe some sets.

* Let $O\_{k}=\\{0^k\\}, \ \text{ where } k \in \mathbb N\_0$.
For any string $s$ in $O\_k$, string $e$ is an extender of $s$ iff $e=0^i1^{i+k}$ for some $i\in\mathbb N\_0$.
* Let $L\_{k}=\\{0^{m+1+k}1^m1: m\in\mathbb N\_0\\}, \ \text{ where } k \in \mathbb N\_0.$
For any string $s$ in $L\_k$, string $e$ is an extender of $s$ iff $e=1^{k}$.
* Let $R=\\{x\in\Sigma^\*: x\text{ is not in any }O\_k\text{ or }L\_k\\}$, where $\Sigma\supseteq\\{0,1\\}$ is the alphabet.
Note that any string that can be extended to a string in $L$ must be $0^i1^j$ for some $i\ge j\ge0$, i.e., must be in $O\_k$ or $L\_k$ for some $k$.
Hence, for any string $s$ in $R$, there is no extender of $s$.

The description above shows that all (Myhill–Nerode) equivalence classes of $L$ in $\Sigma^\*$ are $O\_0,O\_1, O\_2,\cdots, L\_0, L\_1, L\_2, \cdots$ and $R$.

---

> In the definition, nothing is said about $x$ and $y$ in $(xR\_Ly)$. Do I have to assume that those are two arbitrary words that **are already** in $L$? (If not, then my approach doesn't work)

No, $x$ and $y$ may or may not be in $L$. Your approach doesn't work.

> For a fixed $n \in \mathbb{N}\_0$ I think $\exists$ just one word in the class $C\_n$. Then does it mean that the unique word in $C\_n$ is only equivalent to itself?

I cannot find where $C\_n$ is defined. If it means $O\_n$ defined above, then it does have only one word, $0^n$. The unique word in $O\_n$ is only equivalent to itself.

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


# Question
Title: Is $\{\langle G,x\rangle \mid x\in L(G)\}$ context-free?
Our problem is:

> Given a context-free grammar $G$ and a string $x$, decide whether $x\in L(G)$.

Is this language itself context-free?

# Answer
> 3 votes
If your language were context-free, then by intersecting it with a regular language, we would deduce that the following language would be context-free: $$ \\{ \langle G,x \rangle \mid \text{$x \in L(G)$ and $G$ contains a single production $S \to w$} \\} $$ However, this is just the celebrated language $\\{ ww : w \in \Sigma^\* \\}$ in disguise, which is known not to be context-free. It follows that your language (using any reasonable encoding) is also not context-free.

---
Tags: complexity-theory, context-free
---


# Question
Title: Nearest Neighbor Search in Spherical Coordinates
I am familiar with k-d trees being used to find nearest neighbors (NN) in 3-D euclidean space however in my particular case I am given a huge array of spherical coordinates. Due to accuracy complications as well as loss of information I cannot convert them to Cartesian coordinates. Then given these points in their spherical coordinates how can I go about determining their NN. I need an algorithm that is efficient (relatively) and more importantly accurate.

EDIT: For sake of argument and for the philosophical point let's accept the 'loss of information' to quickly summarize my research in astrophysics does not allow me to simply convert to Cartesian coordinates and use a nearest neighbor algorithm due to the universe expanding and me dealing with something called redshift. TLDR: I cannot convert to cartesian and must use an algorithm in spherical coordinates for nearest neighbor.

# Answer
> Due to accuracy complications as well as loss of information I cannot convert them to Cartesian coordinates.

I don't understand this restriction. Converting to Cartesian coordinates uses essentially the same trigonometric functions that you would need to find the distance between two points in spherical coordinates: the only fundamental difference is that working directly in spherical coordinates you can take the cosine of the difference of azimuthal angles rather than taking sine and cosine of the individual azimuthal angles.

In any case, you should be able to bound the error in converting to Cartesian coordinates and take that error bound into account to create a shortlist of candidates using k-d trees; then recalculate the distances for the points in the shortlist using the spherical coordinates directly.
> 2 votes

---
Tags: algorithms, search-algorithms, nearest-neighbour
---


# Question
Title: What can we conclude about a machine $m$ from that fact that it solves a particular problem $P$?
Note: I have not studied theoretical computer science, so this may be a trivial question.

**I am interested in the general question:** what restrictions are put on a machine $m$ (boolean circuit, TM, ...), by the assumption that $m$ solves a certain problem or class of problems? **The question I'm asking in this post is:** What field of theoretical CS should I read up on for this?

For example:

* Can all problems be solved by a lookup table? Or does assuming that $m$ solves problem $X$ tell us that $m$ has to do particular types of computations?
* If we have a boolean circuit $C$ that computes problem $f$, can we then always construct a boolean circuit $\tilde C$ that also computes $f$ but has only a depth of 2 layers (or something like this).

**What should I look in to to get an insight in questions like this?** (I'm not asking for answers to these specific two questions).

# Answer
The computational power of machines / automata / programming languages and similar computational models, is usually studied in these theoretical fields:

* Computability (for what can be computed at all)
* Complexity (for what can be computed efficiently)
* Formal languages (several kinds of automata exist, with different expressiveness)

You will find many textbooks about these topics, as well as university courses (some video lectures could even be available on the 'net)
> 1 votes

---
Tags: reference-request, education
---


# Question
Title: Can PDA model Turing Complete objects if the objects' state are finite?
I am currently reading the extended Version of the Paper Online Detection of Effectively Callback Free Objects with Applications of Smart Contract.

I am trying to understand the proofs of Chapter 6. In particular, I cannot understand the premise of proofs 6.2. Indeed, the authors use a variant of SMAC, an Object-oriented and **Turing Complete** (SMAC) and they claim that (I underlined the suspicious claim with bold)

> Thus, we focus on verifying $sECF$, namely, statically verifying whether all executions of an object are $dECF\_{FS}$ or $ECF\_{C}$, **where the domains of the object variables are restricted to finite sets. Hence, such objects can be modeled with a pushdown-automaton (PDA). Such a PDA for an object o is able to simulate any modular well-formed execution $\kappa \in \pi$ where the active object of all states in $\pi$ is o**.

In my understanding, this premise should be wrong, because although the state of this SMAC program is final, it is not computable by Push-Down-Automata (which compute total functions).

```
Foo:
     int x = 0 // field of the object
     enter // enter the single method of the object/contract
         while true do
             x = 1
     return

```

# Answer
> 0 votes
> where the domains of the object variables are restricted to finite sets. Hence, such objects can be modeled with a pushdown-automaton (PDA).

You are correct that if you understand it as using a pushdown-automaton to model the full behavior of the object, since as you indicated, you can put a Turing complete Turing machine inside any object.

However, I would believe that the authors intend to use a pushdown-automaton to mode an object in the domain with its possible states as defined by the values of its fields and its execution stack, since the whole paper is focusing on the ECF(Effectively Callback Free) property for objects. The actual moments when the object is still in the middle of changing from one state to another state are ignored/irrelevant/transparent/skipped. More specifically, the following shows the purpose of the object.

> Such a PDA for an object o is able to simulate any modular well-formed execution $\kappa \in \pi$ where the active object of all states in $\pi$ is o

---
Tags: pushdown-automata, turing-completeness
---


# Question
Title: Why does the operating system switch an active process to different cores?
When running a single-threaded application that is 'always busy', on a multi-core computer, modern operating systems will typically switch the process from one core to another from time to time. Even when the other cores are always idle.

Typically you can see 1 of 4 cores on a quad core processor at 100% load while the other cores are 0-1%. Once in a while, the active process will 'jump' to another core, now leaving the original core idle and utilizing 100% of another core.

Why does this happen?

Is it because the process was context-switched (even though other cores were idling)? Or is it because of thermal or power-related reasons? Something else?

# Answer
Multitasking works like this: allow user process to execute for a little, then switch back to OS scheduler to be able to execute something else.

In multicore architectures, every core has equal opportuninty to acquire the process.

If you want to force your process execution on the selected core, this selection must be stored somewhere. There’s usually no reason to do that.
> 2 votes

# Answer
Improving thermal problems is a good reason. Processor speed is limited by heat. By switching to another and cooler core, the new core can run at a higher clock speed.

PS. Quite possible that this happened by coincidence in the first scheduler, the happy side effect was detected, and then they kept it. You could verify this on a processor with hyper threading: If you have four cores with hyperthreading = 8 virtual cores, it would be pointless to switch to a different virtual core on the same real core to keep heat down.
> 2 votes

---
Tags: operating-systems, process-scheduling
---


# Question
Title: Can the compiler convert recursive algorithm into a dynamic programming
So I was going through the idea behind dynamic programming (memoization), and thought of this question.

Can a compiler convert any recursion into a table filling DP solution, of course given the hint(like some keyword or macro) from the programmer that the following recursive function can be solved with DP (so programmer knows that it exhibits overlapping sub-problems and optimal substructure)?

If it's possible why don't many of them have it, if there exists anyone that does?

# Answer
There is an easy way to implement dynamic programming, using a hash table. The idea is that the recursive procedure stores a huge giant table, containing all values computed so far. Whenever the recursive procedure is called, it first checks whether the value is already in the table, and if so, the value is immediately returned. Otherwise, the body of the procedure is executed, and the result is stored in the table.

This kind of memoization can be enabled, for a specific procedure, using the decorator `@memoize` in Python, and perhaps similar metaprogramming mechanisms are available in other languages.

Since the table takes up space, it is not clear that this kind of memoization is advantageous in every situation. For example, it might be that the function is easy to compute, and using a hash table would make it significantly slower (since memory access is small). Perhaps a certain code is trying to keep a certain table in cache, and using memoization would interfere with this effort. Perhaps using a table would interfere with security in some way, since it will reveal whether a function is called with the same value as before or not. There are probably many other reasons for the compiler not to perform such an optimization automatically.
> 1 votes

---
Tags: dynamic-programming, compilers
---


# Question
Title: Define a length function over $A^{*} \leftarrow{N}$ such that $length(l)$ outputs the length of $l$
Consider the following definitions

LIST:

$\overline{nil} \ \ \ \ \ \frac{l}{a \ l}$ $a \in A$

$A^\* = \mu \widehat{LIST}, \ A^{\infty} = v \widehat{LIST}$

NAT:

$\overline{0} \ \ \ \ \ \frac{x}{s(x)}$

$ N = \mu \widehat{NAT}, \ N^{\infty} = v \widehat{NAT}$

Given those definitions I have to define a length function over $A^{\*} \leftarrow{N}$ such that $length(l)$ outputs the length of $l$.

I have tried to do this problem using structural induction on a given $l$ but I don't seem to get any relevant result.

In general, how would you approach this kind of problem?

# Answer
Let `F` denote a “shape”, as your `LIST` and `NAT` shapes for example.

> Declaring $I := μF$ is tantamount to saying that $I$ is recursively defined by some $α : F(I) ≅ I$ and moreover for any $β : F(K) → K$ there is a *unique* $f : I → K$ that respects the “F”-structure.

Since you define $A^\* = μ(LIST)$, where the “LIST” structure on a set $X$ consists of a constant $c : X$ and a function $n : A × X → X$ --- c.f., your $nil, -·-$ --- we automatically obtain an operation $A^\* → ℕ$ if we can endow $ℕ$ with a “LIST” structure; namely a constant such as zero $0 : ℕ$ and an operation on ℕ such as $A \times ℕ → ℕ : (a, n) ↦ s\\, n$.

So by the μ-definition of lists, since we furnished ℕ with a LIST structure, we have that there is a unique function, call it $length$, that respects the LIST structure in that it takes the shape constants-to-constants and the shape functions-to-functions: $$ \mathsf{length}(nil) \\;=\\; 0 $$ $$ \mathsf{length}(a \cdot l) \\;=\\; s(\mathsf{length}\\, l) $$

Alternatively, these properties also serve to “define length by structural induction on the shape of lists”.

Hope that helps a bit :-)
> 2 votes

---
Tags: correctness-proof, formal-methods
---


# Question
Title: Asymptotic behavior of $n\sqrt n + n \log n$ & $\log_{100} n$
I have the following two functions

* $f(n) = n\sqrt n + n \log n$
* $\log\_{100} n$

And I need to classify them into the followings:

* $O(n)$, and/or
* $O(n^2)$, and/or
* $O(n^3)$, and/or
* $O(n^{1.5})$, and/or
* $\omega(n)$, and/or
* $o(n\log n)$ (small o)
* $\theta(n^{1.5})$,

Regarding the $\theta(n^{1.5})$, I am grasping it's idea newly, where do these functions set in. Also, does the function $f(n) =n^{0.9999}$ belong to $\theta(n^{1.5})$.

I would appreciate your feedback, as from your answers I am building up the knowledge for these.

# Answer
* $\log\_{100}n \in \mathcal{O}(log(n))$ since base change is a constant.
    + $\log n \in \mathcal{O}(n) $
    + $\log n \in \mathcal{O}(n^2) $
    + $\log n \in \mathcal{O}(n^3) $
    + $\log n \in \mathcal{O}(n^{3/2}) $
    + $\log n \not\in \mathcal{\omega}(n) $
    + $\log n \in \mathcal{o}(n \log n) $

This table gives the order;

First of all;

$$\lim\_{n \rightarrow \infty} \frac{n \sqrt n}{n \log n} = \infty$$ by using this;

* $f(n)= n\sqrt n + n\log n \in \mathcal{O}(n\sqrt n )$.
    + $ n\sqrt n \not\in \mathcal{O}(n)$
    + $n\sqrt n \in \mathcal{O}(n^2) $
    + $n\sqrt n \in \mathcal{O}(n^3) $
    + $n\sqrt n \in \mathcal{O}(n^{3/2}) $
    + $n\sqrt n \in \mathcal{\omega}(n) $
    + $n\sqrt n \not\in \mathcal{o}(n \log n) $,
> 1 votes

---
Tags: complexity-theory, time-complexity, asymptotics
---


# Question
Title: Convert ambiguous grammar $S \to 01S1\mid SS\mid\epsilon$ to unambiguous grammar
Given the ambiguous CFG : $ S \to 01S1\mid SS\mid\epsilon $

I came up with the following CFG which I think is unambiguous:

$S \to 01X \mid 011X$
$X \to 01X1 \mid \epsilon$

Is my CFG unambiguous and does it represent the same language?

# Answer
Let $D$ be the given grammar, $S \mapsto01S1\mid SS\mid\epsilon$.
Then each word $w$ generated by $D$ is a mixture of equal number of $01$'s and $1$'s such that in any prefix of $w$ there are at least as many $1$'s as 0's but at most twice as many $1$'s as $0$'s.

Let $H$ be your grammar, $S \mapsto01X\mid011X$ and $X\mapsto 01X1\mid ϵ$.
Then each word generated by $X$ is some number of $01$'s followed by the same number of $1$'s. So each word $w$ generated by $H$ starts with $01$ or $011$, followed by some number of $01$'s, followed by the same number of $1$'s.

Both $D$ and $H$ are CFGs. While $D$ is ambiguous as illustrated by $011\ \ 011011=011011\ \ 011$, $H$ is unambiguous.

The word $010111011$ is generated by $D$ but not by $H$. The word $01011$ is generated by $H$ but not by $D$. Hence, the language generated by $H$ is not the same as the given language generated by $D$.

It should not be hard to prove the various claims in the above paragraphs. Yuval Filmus' idea to treat $01$ as one symbol should be helpful.

---

Is the language generated by $D$ inherently ambiguous? Here is the spoiler.

> No. Here is a deterministic grammar for $D$
> $$ S \mapsto \epsilon\mid 01S1S $$ Note that any deterministic grammar is non-ambiguous.
> The language is actually isomorphic to the celebrated Dyck language, if we consider $01$ as the encoding of the left bracket and $1$ as the encoding of the right bracket.
> 2 votes

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


# Question
Title: Big-O Solving Recurrence Relation by iteration with fractions
I was trying to solve the recurrence relation in order to get a some big-O bound $$ B(n) = B(n-4) + \frac{1}{n} + \frac{5}{n^{2} + 6} + \frac{7n^{2}}{3n^{3} + 8}$$ by following the accepted answer here. I expanded which resulted in $$ B(n) = B(n-8) + \frac{1}{n-1} + \frac{5}{(n-1)^{2} + 6} + \frac{7(n-1)^{2}}{3(n-1)^{3} + 8} + \frac{1}{n} + \frac{5}{n^{2} + 6} + \frac{7n^{2}}{3n^{3} + 8}$$

This lead to $$ B(n) = B(n-4k) + \frac{1}{n-k} + \frac{5}{(n-k)^{2} + 6} + \frac{7(n-k)^{2}}{3(n-k)^{3} + 8} + \frac{1}{n-k} + \frac{5}{(n-k)^{2} + 6} + \frac{7(n-k)^{2}}{3(n-k)^{3} + 8}$$ However, I get stuck when replacing $k$ with $n$ since this results in dividing by zero. How do I proceed? Can it solved by the iteration?

# Answer
> 1 votes
We can rewrite your recursion as $$ B(n) = B(n-4) + \Theta\left(\frac{1}{n}\right). $$ It follows that $$ \begin{align\*} B(n) &= \Theta\left(\frac{1}{n} + \frac{1}{n-4} + \frac{1}{n-8} + \cdots\right) \\ &= \Theta\left(\frac{1}{n/4} + \frac{1}{n/4-1} + \frac{1}{n/4-2} + \cdots \right) \\ &= \Theta(\log (n/4)) = \Theta(\log n), \end{align\*} $$ using the formula for the sum of a harmonic series.

# Answer
> 0 votes
The base case will depend on $n$, but I will assume that $B(0)$, $B(1)$, $B(2)$, and $B(3)$ are known. I used the Wolfram Cloud to crunch some stuff. The following summarizes the 'simplified' results when $n=4k,\\,4k+1,\\,4k+2,\\,\text{and}\\,4k+3$ (these are given in Mathematica input form for later use in the Wolfram Cloud, etc):

```
B[n_]=Piecewise[{{(144*EulerGamma - (60*I)*Sqrt[6]*PolyGamma[0, (-I/2)*Sqrt[3/2]] + (60*I)*Sqrt[6]*PolyGamma[0, (I/2)*Sqrt[3/2]] + (60*I)*Sqrt[6]*PolyGamma[0, (-I/4)*(Sqrt[6] - I*n)] -
(60*I)*Sqrt[6]*PolyGamma[0, (I/4)*(Sqrt[6] + I*n)] + 144*PolyGamma[0, 1 + n/4] + 112*n^2*RootSum[8 + 3*n^3 - 36*n^2*#1 + 144*n*#1^2 - 192*#1^3 & , PolyGamma[0, -#1]/(n^2 - 8*n*#1 +
16*#1^2) & ] - 896*n*RootSum[-184 + 144*n - 36*n^2 + 3*n^3 - 576*#1 + 288*n*#1 - 36*n^2*#1 - 576*#1^2 + 144*n*#1^2 - 192*#1^3 & , (PolyGamma[0, -#1] + PolyGamma[0, -#1]*#1)/(16
- 8*n + n^2 + 32*#1 - 8*n*#1 + 16*#1^2) & ] + 1792*RootSum[-184 + 144*n - 36*n^2 + 3*n^3 - 576*#1 + 288*n*#1 - 36*n^2*#1 - 576*#1^2 + 144*n*#1^2 - 192*#1^3 & , (PolyGamma[0,
-#1] + 2*PolyGamma[0, -#1]*#1 + PolyGamma[0, -#1]*#1^2)/(16 - 8*n + n^2 + 32*#1 - 8*n*#1 + 16*#1^2) & ] - 7*n^2*RootSum[-1 + 24*#1^3 & , PolyGamma[0, -#1]/#1^2 & ] +
14*n*RootSum[-1 + 24*#1^3 & , (n*PolyGamma[0, -#1] + 4*PolyGamma[0, -#1]*#1)/#1^2 & ] - 7*RootSum[-1 + 24*#1^3 & , (n^2*PolyGamma[0, -#1] + 8*n*PolyGamma[0, -#1]*#1 +
16*PolyGamma[0, -#1]*#1^2)/#1^2 & ])/576, Mod[n, 4] == 0}, {((-15*I)*Sqrt[6]*PolyGamma[0, (-I/4)*(-3*I + Sqrt[6])] + (15*I)*Sqrt[6]*PolyGamma[0, (I/4)*(3*I + Sqrt[6])] +
(15*I)*Sqrt[6]*PolyGamma[0, (-I/4)*(Sqrt[6] - I*n)] - (15*I)*Sqrt[6]*PolyGamma[0, (I/4)*(Sqrt[6] + I*n)] + 28*n^2*RootSum[8 + 3*n^3 - 36*n^2*#1 + 144*n*#1^2 - 192*#1^3 & , PolyGamma[0,
-#1]/(n^2 - 8*n*#1 + 16*#1^2) & ] - 224*n*RootSum[-184 + 144*n - 36*n^2 + 3*n^3 - 576*#1 + 288*n*#1 - 36*n^2*#1 - 576*#1^2 + 144*n*#1^2 - 192*#1^3 & , (PolyGamma[0, -#1] +
PolyGamma[0, -#1]*#1)/(16 - 8*n + n^2 + 32*#1 - 8*n*#1 + 16*#1^2) & ] + 448*RootSum[-184 + 144*n - 36*n^2 + 3*n^3 - 576*#1 + 288*n*#1 - 36*n^2*#1 - 576*#1^2 + 144*n*#1^2 -
192*#1^3 & , (PolyGamma[0, -#1] + 2*PolyGamma[0, -#1]*#1 + PolyGamma[0, -#1]*#1^2)/(16 - 8*n + n^2 + 32*#1 - 8*n*#1 + 16*#1^2) & ] - 28*n^2*RootSum[-89 + 324*#1 - 432*#1^2 +
192*#1^3 & , PolyGamma[0, -#1]/(9 - 24*#1 + 16*#1^2) & ] + 56*n*RootSum[-89 + 324*#1 - 432*#1^2 + 192*#1^3 & , (-3*PolyGamma[0, -#1] + n*PolyGamma[0, -#1] + 4*PolyGamma[0,
-#1]*#1)/(9 - 24*#1 + 16*#1^2) & ] - 28*RootSum[-89 + 324*#1 - 432*#1^2 + 192*#1^3 & , (9*PolyGamma[0, -#1] - 6*n*PolyGamma[0, -#1] + n^2*PolyGamma[0, -#1] - 24*PolyGamma[0,
-#1]*#1 + 8*n*PolyGamma[0, -#1]*#1 + 16*PolyGamma[0, -#1]*#1^2)/(9 - 24*#1 + 16*#1^2) & ] + 144*DifferenceRoot[Function[{y, n}, {(4*n - n)*y[n] + 2*(-2 - 4*n + n)*y[1 + n] + (4 + 4*n
- n)*y[2 + n] == 0, y[0] == 0, y[1] == n^(-1)}]][(-3 + n)/4])/144, Mod[n, 4] > 2}, {((-15*I)*Sqrt[6]*PolyGamma[0, (-I/4)*(-I + Sqrt[6])] + (15*I)*Sqrt[6]*PolyGamma[0, (I/4)*(I + Sqrt[6])] +
(15*I)*Sqrt[6]*PolyGamma[0, (-I/4)*(Sqrt[6] - I*n)] - (15*I)*Sqrt[6]*PolyGamma[0, (I/4)*(Sqrt[6] + I*n)] + 28*n^2*RootSum[8 + 3*n^3 - 36*n^2*#1 + 144*n*#1^2 - 192*#1^3 & , PolyGamma[0,
-#1]/(n^2 - 8*n*#1 + 16*#1^2) & ] - 224*n*RootSum[-184 + 144*n - 36*n^2 + 3*n^3 - 576*#1 + 288*n*#1 - 36*n^2*#1 - 576*#1^2 + 144*n*#1^2 - 192*#1^3 & , (PolyGamma[0, -#1] +
PolyGamma[0, -#1]*#1)/(16 - 8*n + n^2 + 32*#1 - 8*n*#1 + 16*#1^2) & ] + 448*RootSum[-184 + 144*n - 36*n^2 + 3*n^3 - 576*#1 + 288*n*#1 - 36*n^2*#1 - 576*#1^2 + 144*n*#1^2 -
192*#1^3 & , (PolyGamma[0, -#1] + 2*PolyGamma[0, -#1]*#1 + PolyGamma[0, -#1]*#1^2)/(16 - 8*n + n^2 + 32*#1 - 8*n*#1 + 16*#1^2) & ] - 28*n^2*RootSum[-11 + 36*#1 - 144*#1^2 +
192*#1^3 & , PolyGamma[0, -#1]/(1 - 8*#1 + 16*#1^2) & ] + 56*n*RootSum[-11 + 36*#1 - 144*#1^2 + 192*#1^3 & , (-PolyGamma[0, -#1] + n*PolyGamma[0, -#1] + 4*PolyGamma[0,
-#1]*#1)/(1 - 8*#1 + 16*#1^2) & ] - 28*RootSum[-11 + 36*#1 - 144*#1^2 + 192*#1^3 & , (PolyGamma[0, -#1] - 2*n*PolyGamma[0, -#1] + n^2*PolyGamma[0, -#1] - 8*PolyGamma[0, -#1]*#1
+ 8*n*PolyGamma[0, -#1]*#1 + 16*PolyGamma[0, -#1]*#1^2)/(1 - 8*#1 + 16*#1^2) & ] + 144*DifferenceRoot[Function[{y, n}, {(4*n - n)*y[n] + 2*(-2 - 4*n + n)*y[1 + n] + (4 + 4*n - n)*y[2
+ n] == 0, y[0] == 0, y[1] == n^(-1)}]][(-1 + n)/4])/144, Mod[n, 4] == 1}}, ((-15*I)*Sqrt[6]*PolyGamma[0, (-I/4)*(-2*I + Sqrt[6])] + (15*I)*Sqrt[6]*PolyGamma[0, (I/4)*(2*I + Sqrt[6])] +
(15*I)*Sqrt[6]*PolyGamma[0, (-I/4)*(Sqrt[6] - I*n)] - (15*I)*Sqrt[6]*PolyGamma[0, (I/4)*(Sqrt[6] + I*n)] + 28*n^2*RootSum[8 + 3*n^3 - 36*n^2*#1 + 144*n*#1^2 - 192*#1^3 & , PolyGamma[0,
-#1]/(n^2 - 8*n*#1 + 16*#1^2) & ] - 224*n*RootSum[-184 + 144*n - 36*n^2 + 3*n^3 - 576*#1 + 288*n*#1 - 36*n^2*#1 - 576*#1^2 + 144*n*#1^2 - 192*#1^3 & , (PolyGamma[0, -#1] +
PolyGamma[0, -#1]*#1)/(16 - 8*n + n^2 + 32*#1 - 8*n*#1 + 16*#1^2) & ] + 448*RootSum[-184 + 144*n - 36*n^2 + 3*n^3 - 576*#1 + 288*n*#1 - 36*n^2*#1 - 576*#1^2 + 144*n*#1^2 -
192*#1^3 & , (PolyGamma[0, -#1] + 2*PolyGamma[0, -#1]*#1 + PolyGamma[0, -#1]*#1^2)/(16 - 8*n + n^2 + 32*#1 - 8*n*#1 + 16*#1^2) & ] - 7*n^2*RootSum[-2 + 9*#1 - 18*#1^2 + 12*#1^3 &
, PolyGamma[0, -#1]/(1 - 4*#1 + 4*#1^2) & ] + 14*n*RootSum[-2 + 9*#1 - 18*#1^2 + 12*#1^3 & , (-2*PolyGamma[0, -#1] + n*PolyGamma[0, -#1] + 4*PolyGamma[0, -#1]*#1)/(1 - 4*#1 +
4*#1^2) & ] - 7*RootSum[-2 + 9*#1 - 18*#1^2 + 12*#1^3 & , (4*PolyGamma[0, -#1] - 4*n*PolyGamma[0, -#1] + n^2*PolyGamma[0, -#1] - 16*PolyGamma[0, -#1]*#1 + 8*n*PolyGamma[0, -#1]*#1
+ 16*PolyGamma[0, -#1]*#1^2)/(1 - 4*#1 + 4*#1^2) & ] + 144*DifferenceRoot[Function[{y, n}, {(4*n - n)*y[n] + (-4 - 8*n + 2*n)*y[1 + n] + (4 + 4*n - n)*y[2 + n] == 0, y[0] == 0, y[1] ==
n^(-1)}]][(-2 + n)/4])/144]

```

This line assigns a function `B[n_]` in Mathematica which gives $B(n)$ given $n$, using the best explicit formula I could get, which was still really ugly.

---
Tags: algorithms, asymptotics, recurrence-relation
---


# Question
Title: For which c, d is Gap2SAT[c, d] in P (such that 0<c<d<1)?
For which $c, d$ is $Gap2SAT\[c, d\]$ in $P$ (such that $0\<c\<d\<1$)?

(I know if d=1 then for each c it will be in P, however with which c,d such that $0\<c\<d\<1$ can I simply return YES?)

# Answer
> 1 votes
Assuming the Unique Games Conjecture, your problem is solved for MAX-CUT in Ryan O'Donnell and Yi Wu, An optimal SDP algorithm for Max-Cut, and equally optimal Long Code tests, who determined the *gap curve* for this problem.

I am not aware of any such work for MAX-2SAT, but Per Austrin has essentially determined the optimal approximation ratio (again, assuming the Unique Games Conjecture) in his paper Balanced MAX 2-SAT might not be the hardest.

In celebrated work, Prasad Raghavendra has essentially determined the optimal approximation ratio for *any* constraint-satisfaction problem, again assuming the Unique Games Conjecture.

---
Tags: complexity-theory, 2-sat
---


title: Multiplicative Pure Type Systems

text:
# Question
Title: Multiplicative Pure Type Systems
All the references about Pure Type Systems I know consider only systems that allow to recover natural deduction systems with additive rules. Is there any variant that allows it to recover natural deduction systems with multiplicative rules? Otherwise, is it just by tradition or by inclination that such a Pure Type System is never considered, or is there any good and deep reason why it is not considered?

# Answer
The rule from Troelstra and Schwichtenberg that you call multiplicative, namely $$\frac{\Gamma \vdash A \Rightarrow B \qquad \Delta \vdash A}{\Gamma \cup \Delta \vdash B} \tag{1}$$ is equivalent to the additive formulation because we have weakening. More precisely, the multiplicative and the additive formulations prove the same judgements. In one direction, it is obvious that the additive version $$\frac{\Theta \vdash A \Rightarrow B \qquad \Theta \vdash A}{\Theta \vdash B} \tag{2}$$ follows from the above multiplicative one, just take $\Gamma = \Delta = \Theta$. In the other direction we can use weakening: assuming there are derivations of $$\Gamma \vdash A \Rightarrow B \qquad\text{and}\qquad \Delta \vdash A$$ then by weakening there are derivations of $$\Gamma \cup \Delta \vdash A \Rightarrow B \qquad\text{and}\qquad \Gamma \cup \Delta \vdash A$$ and then by the additive rule (2) we get the desired conclusion $$\Gamma \cup \Delta \vdash B.$$ So for the most part the difference in formulation is largely stylistic, although the difference may matter when we consider proof complexity, and other apsects of derivations, apart from just derivability.

Let me also say that from the semantic point of view it is a bit simpler to give the semantics of the additive formulation than the multiplicative one. In the additive rule one has to cope with the question on how the meaning of $\Gamma \vdash \mathcal{J}$ for some judgement $\mathcal{J}$ relates to $\Gamma \cup \Delta \vdash \mathcal{J}$. No such consideration is necessary in the additive formulation.
> 3 votes

---
Tags: type-theory
---


# Question
Title: Non-constructive $NP$-completeness proof
Is there any known $NP$-complete problem which hardness proof is **non-constructive**.

A **constructive** $NP$-completeness proof is a proof that $L\_1\leq\_p L\_2$ by a reduction $r$ and from the argument therein, one can extract two polynomial-time algorithms $f$ and $g$ such that:

> For every instance $x\in L\_1$, given a certificate $w\_1$ for $x$, we must have that $w\_2=f(w\_1)$ is a certificate for $r(x)\in L\_2$
>
> For every instance $x\in L\_1$, given a certificate $w\_2$ for $r(x)\in L\_2$, we must have that $w\_1=g(w\_2)$ is a certificate for $x\in L\_1$.

In $NP$-completeness result, that does not describe $f$ and $g$, we can say that it is a **non-constructive proof**. Given a certificate for an instance of $L\_1$, *one does not know how to construct a certificate for the corresponding instance of $L\_2$ and vice versa*.

**In a sense, the proof only establishes the existence of corresponding certificates.**

*More specifically*, do we have an **existence-only proof** for some $NP$-complete problem?

# Answer
> 1 votes
If worst-case one-way permutation exists (which exists iff. $P\neq UP\cap coUP$, proven here), then there exists **inefficient reduction proof** for some $NP$-complete problem.

We denote $\pi$ the one-way permutation above.

Specifically, for each proven $NP$-complete $L$, we can define:

$PERMUTED-WITNESS(L)=\\{\pi(x)\mid x\in L\\}$

with the certificate for $y\in PERMUTED-WITNESS(L)$ as: $(x,c)$ where $\pi(x)=y$ and $\pi(c)$ is a certificate for $x\in L$ (the "original" certificate). In other words, $c$ is the **pre-image** of the "original" certificate.

So, given a certificate $c'$ for $x\in L$, we cannot efficiently find $c$ (the pre-image of $c'$) for $\pi(x)\in PERMUTED-WITNESS(L)$

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


# Question
Title: Big-Oh vs Theta in recurrence tree method
I am solving this problem from here.

The given relation is

$$T(n) = 2 T(\frac{n}{2}) + n^2, \\, T(1) = 1$$

The solution via recurrence tree method is given as:

> The zeroth level has a single node with cost $n^2$. The first level has two nodes, each with cost $(n/2)^2 = n^2/4$. The third level has four nodes, with cost $(n/4)^2 = n^2/16$.
>
> In general, you can get the cost of a node by taking the subproblem size and squaring it. At the $i$th level, this cost is $n^2/4^i$. On the other hand, the $i$th level has $2^i$ nodes, so the total cost of each level is $n^2/2^i$.
>
> The height of the tree is $\log n$.
>
> Hence, summing the costs at each level we get
>
> $$\sum\_{n=0}^{\log n} \frac{n^2}{2^i} = n^2\sum\_{n=0}^{\log n} \frac{1}{2^i} \leq 2n^2$$ by the sum of an infinite geometric series. Therefore the total cost of the algorithm is $\Theta(n^2)$.

As far as I understand, we use Big-Oh to give an upper bound i.e it cannot get worse than this and we use Theta to prove a tight bound i.e when we have proved a lower and an upper bound.

However, here we have only proved an upper bound, so shouldn't the answer be $O(n^2)$?

Is this a specific case when it doesn't matter if we interchange Big-Oh and Theta?

# Answer
In this particular case $T(n) = 2T(n/2) + n^2 \geq n^2$, so the lower bound is trivial.
> 1 votes

---
Tags: asymptotics, recurrence-relation
---