# Question
Title: How is functional property guaranteed in type theory when function type is defined?
I understand that functions are not defined in type theory the same way they are defined in set theory, hence functional property is not directly defined when defining function type in type theory. But I want to know which part of function type definition in type theory guarantees functional property even if it is done so indirectly and implicitly?

# Answer
Type theory shows that every element of a function type has the "function property". Let $A$ be a type and $B(x)$ a dependent type with $x : A$. We can construct an element of $$\Pi (x : A) (y , z : B(x)) \\,.\\, f x =\_{B(x)} y \to f x =\_{B(x)} z \to y =\_{B(x)} z$$ quite easily, because we just use symmetry and transitivity of equality. For instance in Coq:

```
Definition functional_property (A : Type) (B : A -> Type) (f : forall x, B x)
  : forall (x : A) (y z : B x) (p : f x = y) (q : f x = z),  y = z
  :=
   fun _ _ _ p q => eq_trans (eq_sym p) q.

```

What this means is that, as others already pointed out, the "functional property" is there by construction. It may help to say the following: in type theory we do not think of mathematical objects as existing independently and beforehand. Instead, type theory is a theory of how objects are constructed. Thus, the elements of the function type are constructed in a certain way (known as "$\lambda$-calculus") that guarantees the desired properties *by construction*. There is no such thing in type theory as "a thing that wants to be a function but isn't because it doesnt have the right properties". That sort of thinking simply does not apply: if you have a thing, then it was constructed according to the rules of some type and therefore the thing has that type.

You are probably thinking set-theoretically, i.e., given a relation $R \subseteq A \times B$, we should be able to get a function out of it, provided that $R$ is single-valued (what you call "functional property") and total. There is a corresponding statement in type theory, but it is *not* the definition of functions. It is instead a theorem stating that the function type $A \to B$ is equivalent to the type of total functional relations.
> 5 votes

# Answer
Set theory does not have functions. Instead, we can *model* functions via special relations (i.e. sets of pairs). When we write $f(x)=y$ in a set-theoretic context, what this *actually* means is $(x,y)\in f$. If $f$ was an arbitrary binary relation, there would be absolutely nothing stopping $(x,y)\in f$ *and* $(x,y')\in f$ with $y\neq y'$. By definition of set-theoretic functions, this is not allowed, so when we propose that some relation is a set-theoretic function, we need to show that this does not happen (among other things).

(ZFC) Set theory is defined within first-order logic. It is typically defined so that the only non-logical symbol is the predicate symbol $\in$ (treating $=$ as a logical symbol). In particular, there are no function symbols. For first-order theories in general (in first-order logic *with* equality), part of the definition of equality is that it is substitutive with respect to predicates and terms. In particular, $x=y\implies f(x)=f(y)$ is either an axiom or readily derived from the logical axioms defining equality.

Again, the key thing here is that a function symbol, even in a set theory, is *not* the same thing as a set-theoretic function (and vice versa). It's interesting to consider what happens when equality isn't taken as part of the logical framework. Then it becomes an arbitrary binary predicate symbol and the statements about it imply that it is interpreted by an equivalence relation. Substitutivity then means, under interpretation, that $x\sim y\implies f(x)\sim f(y)$. A key thing here is that we only require substitutivity for formulas/terms *that we can write down* in the language of the theory.

The above was a bit of an aside to provide context. Type theory is not presented as a first-order theory like set theory. Instead, type theory is more like an alternative to first-order logic. Nevertheless, the handling of functions in type theory is more or less the same as how function symbols are handled in logic. Depending on the type theory, the issue either can't be articulated in any sensible manner, or, like for FOL, is more about properties of equality and to the extent that equality behaves as we'd expect, is trivially demonstrable.

None of this has much to do with function types in particular. The relevant claims for values of function types will follow, if the articulable at all, from substitutivity of equality with respect to the operations of the type theory. For example, if $f:B^A$ is a term of function type and $\mathsf{app}\_{A,B}$ is the operation that performs function application, then substitutivity with respect to $\mathsf{app}\_{A,B}$ will imply the analogous statement for values of function type. In other words, the fact that $\mathsf{app}\_{A,B}(f,x)$ is a term (when $f:B^A$ and $x:A$) already implies functionality.
> 3 votes

# Answer
If I understand correctly what you mean by "functional property", the functional property of an inductive type A comes from its induction rule, that defines a function with domain A and codomain any type C of the "adequate form", together with computation rules, that define how the induction rule computes on all the possible constructors of A inhabitants.
> 0 votes

---
Tags: type-theory, homotopy-type-theory
---


# Question
Title: Uncertainty whether $\{a^i b^j c^k \mid i+j \le k\}$ is context-free or not
I'm having trouble with this particular language: $$\\{a^i b^j c^k \mid i+j \le k\\}$$

If it's not context-free, I don't know how to correctly apply the Pumping Lemma for CFLs; if it is context-free, I don't know how to create a context-free grammar that generates this language.

Which one applies? Can you help me out?

# Answer
> 2 votes
**Hint**. $k = i + j + ?$, so the language is $a^ib^jc^?c^jc^i$.

# Answer
> 1 votes
Here's a context-free grammar:

$$\begin{eqnarray} S & → & AC \\ AC & → & a \\; AC \\; c & \mid & BC \\ BC & → & b \\; BC \\; c & \mid & EC \\ EC & → & \varepsilon \\; EC \\; c & \mid & \varepsilon \end{eqnarray}$$

The $\varepsilon$ in the first RHS of $EC$ is of course not necessary, but it highlights a certain symmetry.

---
Tags: context-free, pumping-lemma
---


# Question
Title: Can every Turing Machine be translated into a SAT formula?
For the proof of "Cook-Levin Theorem", for a Turing Machine $M$ that accepts a language $L \in NP$ and input $x \in \\{0,1\\}^\*$, we can create a SAT Formula, that is satisfiable if and only if $M$ accepts $x$. Could we adopt this construction so that for *any* Turing Machine $M$ and input $x \in \\{0,1\\}^\*$ we can create a SAT Formula $\phi$ that is satisfiable if and only if $M$ accepts $x$ (even if this SAT Formula has more than polynomial length of $|M|$)? Or would that contradicts Rice's Theorem?

**Edit**: As dkaeae correctly pointed out, defining a SAT formula that is satisfiable iff a TM $M$ accepts an input $x$ is indeed possible. What I meant to ask though is, whether a reduction in the sense of a computable function exists (albeit not being limited to running in polynomial time, but indeed being somehow limited in the running time).

# Answer
The proof of the Cook-Levin theorem shows that for any nondeterministic Turing machine $M$, any input $x$, and any (reasonable) time bound $t(n)$, we can construct (efficiently) a SAT formula of size proportional to $t(|x|)^2$ that is satisfiable iff $M$ accepts $x$ within $t(|x|)$ steps.

If you know that $M$ is supposed to halt within $t(n)$ steps, then the SAT formula captures the behavior of $M$ on $x$. But for a general Turing machine we don't possess any a priori bound on the running time. This is why you cannot solve the halting problem in this way.
> 6 votes

# Answer
Certainly you can. Given $M$ and an input $w \in \\{ 0,1 \\}^\ast$, produce $x \lor x$ if $M$ accepts $x$ and $x \land \lnot x$ otherwise.
> 1 votes

---
Tags: satisfiability, halting-problem
---


# Question
Title: How can the length of a string be $O(\log n)$?
I have just started learning about time complexities and am currently reading Logarithmic Complexity. Here's an example of a piece of code which is $O(\log n)$:

```
def intToStr(i):
    '''Assumes i is a nonnegative int Returns the string representation of i'''

    digits = '0123456789'
    if i == 0:
        return '0'
    result = ''
    while i > 0:
        result = digits[i % 10] + result
        i = i // 10
    return result

```

So this just gives is the str of an integer. `intToStr(1243)` returns `'1243'`. I completely understand that the above function is of logarithmic complexity.

In continuation,

```
def addDigits(n):

    '''Assumes n is a nonnegative int
    Returns the sum of the digits in n'''
    stringRep = intToStr(n)
    val = 0
    for c in stringRep:
        val += int(c)
    return val

```

My book says that: (emphasis added)

> **The complexity of converting $n$ to a string is $O(\log n)$,** and `intToStr` returns a string of length $O(\log n)$. The for loop will be executed $O(\operatorname{len}(\mathit{stringRep}))$ times, i.e., $O(\log n)$ times. Putting it all together, and assuming that a character representing a digit can be converted to an integer in constant time, the program will run in time proportional to $O(\log n) + O(\log n)$, which makes it $O(\log n)$.

Can someone please explain how `intToStr` returns a string of length $O(\log n)$? Doesn't it just return a string of length $n$, where $n$ is the length of the integer that we pass?

# Answer
The length of the binary representation of a natural number $n$ is roughly $\log\_2 n$. As an example, the number represented by the binary string $10^{n-1}$ of length $n$ is $2^n$.

Your sources are misleading. Usually $n$ is reserved for the *input length* or a related quantity, not the *input value*. If the input to a function is an integer $m$, then the input length is only $\sim \log\_2 |m|$. In particular, `intToStr` actually runs in *linear* time in the input length, rather than logarithmic time.
> 2 votes

# Answer
To answer your question literally, yes, the code does just return a string of length $n$ where $n$ is the length of the integer that we pass. And this is the right way to think about it.

Your source, though, is using $n$ to denote the *value* of the integer, not its length. This is an unusual thing to do and it is, in my opinion, a very bad idea when teaching the basics of algorithm analysis. This is a point that students find fundamentally confusing, and your book seems to be contributing to that confusion, instead of reducing it.
> 2 votes

---
Tags: time-complexity, python
---


# Question
Title: What is the most efficient way to test whether a set $X \subset \{0, 1\}^n$ and its complement $\{0, 1\}^n \setminus X$ are linearly separable?
I am interested in algorithms that have optimal running time, and ideally which are also very easy to implement. If you can also give some tips on how to implement the algorithm(s) you mention in the answer, that would be great.

# Answer
Actually, no algorithms, efficient enough for you to be interested in, are available. Your problem is exactly the membership problem for the class of linearly separable boolean functions (which are the indicator functions of your sets), and it is known to be co-NP-complete.
> 1 votes

---
Tags: algorithms, machine-learning, neural-networks, linear-programming, boolean-algebra
---


# Question
Title: What is the height of a tree with recursion formula: $T(n) = T(n - \sqrt{n})$
I know if the time complexity of an algorithm is given with the above formula, then the algorithm works in constant time but my question is that what will be the height of the recursion tree for this formula?

# Answer
If you are asking how many iterations of the function $x\mapsto x-\sqrt x$ does it take to get from $n$ below $1$:

For a lower bound, the resulting sequence is nonincreasing, hence you remove at most $\sqrt n$ at each step, hence you need at least $$\frac n{\sqrt n}=\sqrt n$$ steps.

For an upper bound: in order to get from $n$ to $n/2$, all the steps will remove at least $\sqrt{n/2}$, hence $$\frac{n/2}{\sqrt{n/2}}=\sqrt{n/2}$$ steps are enough for that. By the same argument, $\sqrt{n/4}$ steps are enough to get from $n/2$ to $n/4$, $\sqrt{n/8}$ from $n/4$ to $n/8$, etc. The total number of steps is bounded by the geometric series $$\sqrt n\left(\sqrt{1/2}+\sqrt{1/4}+\sqrt{1/8}+\cdots\right)=\sqrt n\frac{\sqrt{1/2}}{1-\sqrt{1/2}}=\frac{\sqrt n}{\sqrt 2-1}\approx2{.}4\sqrt n.$$

Thus, the required number of steps is $\Theta(\sqrt n)$; a more precise argument would show that it is $\bigl(2+o(1)\bigr)\sqrt n$.
> 3 votes

# Answer
Clearly T(n) = T(0) for all n. Which is constant, not linear. Is that really the question you wanted to ask?

And I just see a mathematical relation. I can’t see any recursion or tree or algorithm here.
> 3 votes

---
Tags: time-complexity, trees, recursion
---


# Question
Title: Recognizably turing machine question (reject / loop)
The definition of proving recognizability using dove tailing is below. However I'm wondering if we can also prove loop or reject in the same way?

Give a deterministic TM D that recognizes L such that if $w \in L$ then D accepts w. Or if $w \notin L$, then D does not accept $w$. I realized this definition states on whether D accepts a $w$ like

$A\_{\*111} = \\{\langle M \rangle \mid M$ is a TM, and $M$ accepts some string that ends with 111$\\}$, which is recognizable and easy to prove through dovetailing.

Now how about

$R\_{\*111} = \\{\langle M \rangle \mid M$ is a TM, and $M$ reject some string that ends with 111$\\}$? Is this also recognizable and would the proof be the same as the one above ? I think this will work but what about

$L\_{\*111} = \\{\langle M \rangle \mid M$ is a TM, and $M$ loops on some string that ends with 111$\\}$?

How do you check if something loops?

# Answer
As commented by dkaeae, there is no way to verify whether a general Turing machine (TM) loops forever on some input. No matter how many operations has been run by an algorithm that simulates the TM on that input, that algorithm cannot be sure the TM will loop forever. The TM may or may not stop at the next moment.

The intuition is pretty simple. The only way to know the behavior of a TM on some input is to run it, unless there are some extra information or restriction about the TM that we can take advantage of, such as only finitely many cells are used.

We can recognize all Turing machines that accepts some string that ends with 111 since we can list all such strings and we can use an universal TM to simulate all Turing machines on all such strings sort of in parallel, thanks to dovetailing. Ditto with the case of rejecting.

However, a simulation cannot be finished if the TM keeps running. There is no point of time that an algorithm can be sure that the Turing machine (TM) under inspection will loop forever. Even if it looks like the simulated TM will never stop, it might halt at the next moment. The very fact that it keeps running prevents us from making a foolproof decision on whether it will eventually halt or loop forever. So we should believe that $L\_{\*111}$ is not recognizable. In fact, we should believe the simpler language $L\_{111} = \\{\langle M \rangle \mid M$ is a TM that loop on $111\\}$ is not recognizable either.

Of course, we still need a rigorous proof that shows neither $L\_{\*111}$ nor $L\_{111}$ is recognizable. We can make a reduction from the known unrecognizable language $\overline{HALT}=\\{\langle M \rangle \mid M$ is a TM that does not halt on the empty string$\\}$ to both of them.
> 0 votes

---
Tags: turing-machines, semi-decidability
---


title: Shortest path in a incomplete graph

text:
# Question
Title: Shortest path in a incomplete graph
I know the Dijkstra algorithm to solve the "single source shortest path" problem in a graph. And I've seen people discuss solutions in a dynamic graph where edge/vertices are subject to change. Retrieving the shortest path of a dynamic graph

My question is a little different.

> Given the entry node $S$, while **the entire graph $G(V, E)$ is unknown** at the beginning. There's a function `public List<Edge> get(Node node)` to figure out the outgoing weighted edges at each node. Also, there's another function `public boolean isExit(Node node)` tells you when to stop if the node is an exit node.

The question is a lot like the shortest path finding problem in a maze, where you're at the entry, you only know the next moves of the current node and past nodes, you'd like to find the exits (multiple) in the shortest path. In this analogy, we care more about how to find the "exit" quickly, rather than finding the global optimal shortest path.

I'm wondering if the normal Dijkstra algorithm (Greedy + Relaxation) still applies in the case.

> Because we don't know the full graph, the shortest path to a node might haven't been explored yet, and exist in the unknown part. (That's my biggest concern).

I hope my explanations are clear enough, thank you very much!

# Answer
Algorithms don't care whether you find out what edges lead from a vertex by looking them up in an array, by calling a function called `get()` or by waiting for divine revelation.

The only problem with Dijkstra's algorithm is that, as it is usually described, it starts by setting the distance estimate of every node to infinity and adding every node to a queue. You can't do that if you don't know the nodes at the start of the algorithm. However, Dijkstra doesn't need to do this and, even if you do know the graph before you start, it's not very efficient. It's enough to add the nodes to the queue as you discover them. This variant of the algorithm is often called "uniform-cost search" (especially in AI), though some people argue that it's just Dijkstra's algorithm and that Dijkstra never *really* intended to add all the nodes to the queue at the start.

If you look at the two algorithms/versions of the algorithm, you'll see that a node that classical Dijkstra thinks is at distance infinity is a node that has not yet been added to the queue in uniform-cost.

Ariel Felner gave a good analysis of the relationship between classical Disjkstra and uniform-cost in *Dijkstra's Algorithm versus Uniform Cost Search or a Case Against Disjkstra's Algorithm* (*Proc. 4th Intl. Symposium on Combinatorial Search (SoCS 2011)*, AAAI Press, 2011; PDF).
> 2 votes

---
Tags: algorithms, graphs, data-structures, shortest-path, efficiency
---


title: Searching a Treasure

text:
# Question
Title: Searching a Treasure
I was selected for a UG interview and the following was one of the questions asked:

> "Suppose we have an $8 \times 8$ grid. Under one of the blocks, I (the interviewer) have hidden a treasure which you have to find by asking questions to me. The questions are to be of the form - *"Is it under this $n \times n$ square (where $n \le 8$)?"* For each question, I charge you some money and you have a finite amount with you. What is the least number of questions that you can ask to find where the treasure is?

I don't have any background in high school computer science and while discussing this problem with a senior, I discovered that the problem relates to "complexity" in computer science. Can somebody help me with this as a beginner?

# Answer
> 6 votes
7 is the least number of questions that you can ask to guarantee to find the treasure.

**the idea of binary search**

Every time when we ask a question, we try to reduce the maximum number of unit squares left to search as small as possible. That is, try to cut the number as nearly to a half as possible. This is the idea as binary search.

**the binary search on a row or column of cells**

Each unit square of the given grid is called a cell.

Whenever we are left with some number of cells that are contiguous on the same row or column, we can simulate binary search on those cells with questions on some $n$ by $n$ squares. For example, suppose the treasure is among the cells marked by "t".

$$\begin{array}{|c|c|c|c|c|}\hline &&&&\\\hline \phantom{t}&t&t&t&t\\\hline &&&&\\\hline &&&&\\\hline &&&&\\\hline \end{array}$$

We can ask whether the treasure is in the following square marked by the question marks.

$$\begin{array}{|c|c|c|c|c|}\hline &&&&\\\hline \phantom{?}&?&?&\phantom{?}&\phantom{?}\\\hline &?&?&&\\\hline &&&&\\\hline &&&&\\\hline \end{array}$$

If the answer is yes, then we have restricted the range to search to the two "$t$"-cells to the left; otherwise, to the two "$t$"-cells to the right. Continuing this way, we can accomplish binary search on a row of cells or on a column of cells.

**the full scheme**

First ask whether it is inside the 6 by 6 square at the bottom right corner.

If yes, ask whether it is inside the 4 by 4 square at the bottom right corner.

* If yes, ask whether it is inside the 3 by 3 square at the bottom right corner.

+ If yes, ask whether it is inside the 2 by 2 square at the bottom right corner.

    - If yes, we have 4 unit square left. Ask another 3 questions to find it.
        - Otherwise, it must be at one of the following cells. $$\begin{array}{|c|c|c|c|c|c|c|}\hline &&&&&&&\\\hline &&&&&&&\\\hline &&&&&&&\\\hline &&&&&&&\\\hline &&&&&&&\\\hline \phantom{t}&\phantom{t}&\phantom{t}& \phantom{t}&\phantom{t}&t&t&t\\\hline &&&&&t&&\\\hline &&&&&t&&\\\hline \end{array}$$ Now choose the following square to ask to determine whether it is on the top row of that 3 by 3 square except the top left cell. If yes, we are left with 2 cells on the same row; otherwise we are left with 3 cells on the same column. Now start binary search. $$\begin{array}{|c|c|c|c|c|c|c|}\hline &&&&&&&\\\hline &&&&&&&\\\hline &&&&&&&\\\hline &&&&&&&\\\hline &&&&&&?&?\\\hline \phantom{t}&\phantom{t}&\phantom{t}& \phantom{t}&\phantom{t}&\phantom{t}&?&?\\\hline &&&&&&&\\\hline &&&&&&&\\\hline \end{array}$$
        - Otherwise, it must be at one of the following cells. $$\begin{array}{|c|c|c|c|c|c|c|}\hline &&&&&&&\\\hline &&&&&&&\\\hline &&&&&&&\\\hline &&&&&&&\\\hline \phantom{t}&\phantom{t}&\phantom{t}& \phantom{t}&t&t&t&t\\\hline &&&&t&&&\\\hline &&&&t&&&\\\hline &&&&t&&&\\\hline \end{array}$$ Now choose the following square to ask to determine whether it is on the top row of that 4 by 4 square except the top left cell. If yes, we are left with 3 cells on the same row; otherwise we are left with 4 cells on the same column. Now start binary search. $$\begin{array}{|c|c|c|c|c|c|c|}\hline &&&&&&&\\\hline &&&&&&&\\\hline &&&&&&&\\\hline &&&&&?&?&?\\\hline &&&&&?&?&?\\\hline \phantom{t}&\phantom{t}&\phantom{t}& \phantom{t}&\phantom{t}&?&?&?\\\hline &&&&&&&\\\hline &&&&&&&\\\hline &&&&&&&\\\hline \end{array}$$
* Otherwise, ask whether it is inside the 5 by 5 square at the bottom right corner.

+ If yes, inquire an appropriate square to determine whether it is on the top row of that 5 by 5 square except the top left cell. If yes, we are left with 4 cells on the same row; otherwise we are left with 5 cells on the same column. Now start binary search.
    + Otherwise, inquire an appropriate square to determine whether it is on the top row of that 6 by 6 square except the top left cell. If yes, we are left with 5 cells on the same row; otherwise we are left with 6 cells on the same column. Now start binary search.

Otherwise, ask whether it is inside the 7 by 7 square at the bottom right corner.

* If yes, inquire an appropriate square to determine whether it is on the top row of that 7 by 7 square except the top left cell. If yes, we are left with 6 cells on the same row; otherwise we are left with 7 cells on the same column. Now start binary search.
* Otherwise, inquire an appropriate square to determine whether it is on the top row of the original 8 by 8 square except the top left cell. If yes, we are left with 7 cells on the same row; otherwise we are left with 8 cells on the same column. Now start binary search.

**Why cannot we succeed with less than 7 questions?**

Since after the first question, one of the yes or no answer will leave us at least $\min(64-5^2, 6^2)=36$ cells to search. Each question can cut the maximal number of cells to search at most in half. Since $2^5=32 \< 36$, we need at least another $5+1=6$ questions to guarantee success.

**Open problem**

Does the scheme above reach the minimum average number of questions, assuming the treasure can be in any cell with equal probability?

I believe it does. However, I am not able to obtain a complete proof as it is not clear how to reduce the many cases to a manageable level.

**Exercise**

What is the least number of questions to guarantee to find the treasure that is in one of the cells of a 7 by 7 grid?

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


title: Turing machine loop and reject example

text:
# Question
Title: Turing machine loop and reject example
I'm getting confused on these both. Reject the string does a stop while loop the machine goes on and on.

My textbook has one example on a reject state and no physical one for loop:

Assume that no reject state was given. And I input a string

$1^{q\_{1}}011$

After all the transitions the turing machine is now on the empty string $1011 \epsilon^{q\_{8}}$ with no where else to go and its not on a accept state, so it rejects.

Now consider if its on q2 at string $0$ so $$10^{q2}11$$

And it cant go anywhere. Would that also reject? Or only if its on the empty string?

Now what is a loop? My idea is

$$1^{q\_{1}}011$$

$$1^{q\_{2}}011$$

$$1^{q\_{1}}011$$

$\dots$

forever

# Answer
Here's a different way to think about it. Every step, the Turing machine looks at the current cell of the tape, then does the following:

* Optionally, move the head left or right
* Select a new state, *or* accept, *or* reject

If it accepts or rejects, it halts and doesn't do anything further. But this won't necessarily happen: it's also possible for it to get stuck in a loop it can never get out of. Imagine the following machine:

> State 0: if you see a 0, don't move, go to state 0
> State 0: if you see a 1, don't move, go to state 0

It's never going to get out of state zero, it'll just stay in it forever.

It's possible for a single machine to do all three, depending on its input:

> State 0: if you see a 0, don't move, go to state 0
> State 0: if you see a 1, move right, go to state 1
> State 1: if you see a 0, don't move, reject
> State 1: if you see a 1, don't move, accept

Given the input `0` it'll loop, given the input `10` it'll reject, given the input `11` it'll accept.
> 1 votes

---
Tags: turing-machines
---


# Question
Title: Can we find every 216 digit number combination?
This question popped to my head when I watched Pi where the mathematican told the Jews "Didnt you calculate every 216 digit number allready?"

So I want to find every possible 216 digit number possible.

Here is an example

```
001234686486484642341234567876345675433586484545856856752856846845685468523253523253253623547568768786858866567895445665446654600912323131231547568568568823568658561223133257857857131233118765432100542533525223552000

```

What I want.

A computer that finds 216 digit numbers and puts them on hard storage.

How long would it take with todays computers like IBM Summit? How much storage would be required to store all these numbers? And also how much data storage would be needed to store all these numbers with an index system? Like Index No 547 is

```
235346098435790863409863405364908736409364235253348902340983548796439082409348974369807324354364398706430253435354925364545685634754865498769675222321214241526343987230544533604234234236409340983543534460534523253532

```

# Answer
$1.0531229 \times 10^{65}$ is approximately $2^{216}$ so when you say " every possible $216$ digit number " I assume you mean every possible sequence of $216$ binary digits i.e. bits.

Each sequence occupies $216$ bits, so the *minimum* storage for all possible sequences (if we ignore factors like aligining on word boundaries) is $216 \times 1.0531229 \times 10^{65} \approx 2.27 \times 10^{67}$ bits. That's around $10^{40}$ yottabytes.

By my rough calculation, it will take a time of the order of the current age of the universe to generate all these combinations, and something around the size of the solar system to store all of them !
> 1 votes

---
Tags: computability, mathematical-programming, mathematical-analysis, mathematical-software
---


# Question
Title: What are the best ways to find errors in a sequence of messages (strings)?
I am currently working on a thesis, where the main goal is to find errors (like a missing message, wrong sequence) in message sequences. The messages are distinguishable by their name, have further information in the message body, and are available in a database. Each message can just be thought of as string-representation of its name.

The thesis should compare different concepts for finding errors in these real-life message sequences. A big amount of these messages are being collected and the goal is to check for errors in the sequence or any missing messages. The default sequence (so the standard-case) can be defined.

Now I am just lacking any ideas on how to approach this problem. So, my questions are as follows: Which approaches can be used to solve this problem? Are there any algorithms, that could be used in this context?

Further example to make it clearer:

Message sequence A, B, C, D, E is defined for one standard-case. Now, the real message sequence that is observed is A, B, C, E, D (or one message is missing entirely).

I hope the problem is comprehensible. Thanks to all who take the time to read.

# Answer
Not sure if I get your question right, as you didn't specify whether this is a theoretical problem or a practical.

Assuming it is practical problem, there are quite some algorithms (e.g. TCP) depending on which layer your messages are being send (if they are being send at all).

Assuming it is more of a theorectial problem you can use stuff like the Hamming distance.

Maybe check: *Computer Networks by Andrew S. Tanenbaum*
> 0 votes

---
Tags: algorithms
---


# Question
Title: Is computer science really a branch or sub-branch of physics?
Given that a computer is basically an electronic machine, is computer science really a branch of electronics, which is in turn a branch of physics?

# Answer
No it is not. Computer science has as much to do with computers as astronomy does with telescopes: they're a tool.

Even if computers didn't exist the science of computing things still would. IMO Computing Science would be a much better name, but we're stuck with what we have I guess.
> 5 votes

---
Tags: physics
---


# Question
Title: Is the language L = {(a,b)* | #a * #b is an odd number} regular?
Is the following language regular? $$\\{ w \in \\{a, b\\}^\* |\ \text{the product of the number of $a$'s and the number of $b$'s is an odd number}\\} $$

If i'm not mistaken the condition is the same as having an odd number of $a$'s and an odd number of $b$'s. I have tried using the Pumping Lemma without success. So I'm suspecting it's regular. But I can't think of a regular expression or an automaton that accepts it.

# Answer
It is.

Since only the product of two odd numbers is an odd number, you can construct a DFA that only accepts when #$a$ and #$b$ are (both) odd.

The followings states would be:

* $Q\_1$ : #$a$ even, #$b$ even
* $Q\_2$ : #$a$ even, #$b$ odd
* $Q\_3$ : #$a$ odd, #$b$ even
* $Q\_4$ : #$a$ odd, #$b$ odd (an accepting state)

The transitions are fairly simply, and I'll leave them to you.
> 3 votes

# Answer
To find the equivalent regular expression, try this approach.

If $\\#a$ and $\\#b$ are both odd then the total length of the string is even. Divide the string into two character blocks. Each block is either $aa$, $bb$, $ab$ or $ba$.

$aa$ and $bb$ have no effect of the parity of $\\#a$ and $\\#b$ so they are equivalent as far as our regular expression is concerned. Similarly $ab$ and $ba$ both change the parity of $\\#a$ and the parity of $\\#b$ so they are also equivalent.

So our regular expression will consist of blocks like $(aa+bb)$ and $(ab+ba)$.

We don't care how many $(aa+bb)$ blocks we see, but we need to see at least one $(ab+ba)$ block, so our regular expression will start with

$(aa+bb)^\*(ab+ba) \dots$

After this we need to see an even number of $(ab+ba)$ blocks (remember zero is an even number), possibly interspersed with zero or more $(aa+bb)$ blocks. I'll let you take it from there.
> 3 votes

---
Tags: automata, regular-languages, finite-automata
---


# Question
Title: Question on the paper ``Self-Testing/Correcting for Polynomials and for Approximate Functions''
I am having some trouble really getting to a precise understanding of some of Self-Testing/Correcting for Polynomials and for Approximate Functions and would greatly appreciate help. Here is my understanding of section 3, **Self-Testing Polynomials**.

My main problem is that the definition of the function $g$ seems to require a theorem that isn't cited. Details below.

---

One is given a program $P$. This program (supposedly) computes a polynomial function $f$. This polynomial $f$ is defined *implicitly* by saying that $f$ is the interpolating polynomial, over some finite field $F$, of data points $(x\_0,y\_0)$, $(x\_1,y\_1)$, $\dots$, $(x\_n,y\_d)$. In other words, $f$ is the lowest degree polynomial satisfying for all $i=0,1,\dots,d$, $f(x\_i)=y\_i$. In any case, $P$ ought to be very quick to compute, the best case scenario certainly being where $P$ is a list of (supposedly) all values of $f$ pre-computed.

One wants a quick way to verify that $P$ does its job as advertized, at least mostly.

During the proof that the program **Polynomial Self-Test** has the desired properties, one introduces the function $g$ defined as $$\forall x\in F,\quad g(x)=\mathrm{maj}\_{t\in F} \left\\{\sum\_{i=1}^{d+1}\alpha\_i P(x+i\cdot t)\right\\}$$ where the $\alpha\_i$ are the field elements that satisfy, for any polynomial $Q$ of degree $\leq d$, $$Q(X)=\sum\_{i=1}^{d+1}\alpha\_i Q(X+i\cdot T)$$ These exist and can be defined in terms of the inverse of a Vandermonde matrix, and the paper even tells us they are binomial coefficients up to a sign.

The goal is nicely summed up by the authors: prove that under certain circumstances, the function $g$ thus \`\`defined'' is indeed the interpolating polynomial of the data, and mostly agrees with $P$:

> It is not clear to me how to interpret the definition of $g$. There are two definitions one could come up with:
>
> > 1) $g(x)$ is the value that comes up most often from all the $\sum\_{i=1}^{d+1}\alpha\_i P(x+i\cdot t)$, but this would require us to break ties (probably arbitrarily). **This is unacceptable** considering a lemma further down that tells us that under certain conditions $g$ is *precisely* the function $f$ sought after
> >
> > 2) If we consider the totality of values $\sum\_{i=1}^{d+1}\alpha\_i P(x+i\cdot t)$, for all $t\in F$, there *always* is a $50\\%+\epsilon$ majority of one value. In which case the definition is unambiguous, but which **would require a proof**, likely saying that if $\delta$ is small enough (and hopefully \`\`small enough'' can entirely de defined in terms of $d$ and $\delta$, i.e. not using the cardinality $|F|$ of the finite field $F$)
> >
> > 2') Or we could leave $g$ undefined in those cases where no $50\\%+\epsilon$ majority arises, but that would surely make the analysis more complicated.
>
> It seems only the second one makes sense, and when considering a proof that comes afterwards, it seems this is indeed the definition they are using. However, it would require proof that with $\delta$ small enough, a $50\\%+\epsilon$ always happens.

Here $1-\delta$ is defined as (I believe there is a typo in the paper here):

When doing a similar analysis with $F\_2$-linear maps $F\to F\_2$ for a field of characteristic $2$, there is a very cute result from representation theory that tells us that if $f$ satisfies the defining equation of a linear map \`\`$f(x+y)=f(x)+f(y)$'' often enough, then it agrees with an actual linear map at least as often (in terms of Hamming distance). It seems the authors are aiming for a similar result here, but there is a piece missing as far as I can tell.

# Answer
The definition of $g$ should be interpreted in the following way:

> Any function $g$ for which $g(x)$ is a majority value of $\sum\_{i=1}^{d+1} \alpha\_i P(x+i\cdot t)$ satisfies what follows.

Since it is later proved that $g = f$, it follows that $g(x)$ is always a strict majority (if it weren't, you would be able to define two different realizations of $g$, and prove that both of them are equal to $f$, contradicting their being different).

If you don't like this interpretation, you could fix a tie-breaking rule and use it to define $g$ conclusively. For example, you could take $g(x)$ to be the smallest majority value of $\sum\_{i=1}^{d+1} \alpha\_i P(x+i\cdot t)$. The exact tie-breaking rule makes no difference, since the proof shows that it is never actually used.

This kind of definition is common in the literature, and it is best to get used to it. Sometimes the authors explicitly mention that ties can be broken arbitrarily, but otherwise it is just implicitly assumed.
> 2 votes

---
Tags: polynomials, testing
---


# Question
Title: pseudo-polynomial reduction from 3-Partition to Partition
A problem $\Pi'$ is *pseudo-polynomially reducible* to the problem $\Pi$ ($\Pi' \leq\_{pp} \Pi$) if, for any instance $I'$ of $\Pi'$, an instance $I$ of $Π$ can be constructed in *pseudo-polynomially bounded time*, such that, given the solution $S\_I$ to $I$, the solution $S\_I'$ to $I'$ can be found in pseudo-polynomial time.

It follows that, $\forall \Pi,\Pi' \in NP$, if $\Pi'$ is *strongly NP-complete*, and $\Pi' \leq\_{pp} \Pi$, then $\Pi$ is *strongly NP-complete*.

And it is easy to show that "**3-Partition** $\leq\_{pp}$ **Partition**."

Hence, I can conclude that **Partition** is *strongly NP-complete*. (However, we already know that **Partition** problem is *ordinary NP-complete*.)

Am I missing something!?

# Answer
> 1 votes
The claim

> It follows that, $\forall \Pi,\Pi' \in NP$, if $\Pi'$ is *strongly NP-complete*, and $\Pi' \leq\_{pp} \Pi$, then $\Pi$ is *strongly NP-complete*.

is wrong (at least for how "pseudo-polynomically reducible" is defined here).

If $\Pi'$ is strongly $NP$-complete, then \`\`pseudo-polynomially reducible'' is equivalent to polynomially reducible.

Recall that a problem is strongly $NP$-complete if it is $NP$-complete even if we assume all the integers that appear in the input are polynomial in the length of the input.

Recall that an algorithm runs in pseudopolynomial time if it runs in polynomial time in the integers that appear in the input.

So, a pseudopolynomial reduction must run in time polynomial in the integers that appear in the input. Which, for a strongly $NP$-complete problem, can be assumed to be polynomial in the length of the input. Which means the reduction must run in time polynomial in the length of input.

So, if $\Pi'$ is strongly $NP$-complete, $\Pi' \leq\_{pp} \Pi$ is equivalent to $\Pi' \leq\_p \Pi$. Clearly, the existence of such a reduction does not imply that $\Pi$ is strongly $NP$-hard.

The only place in the literature that I can find any mention of this notion of \`\`pseudopolynomial reduction'' is in the appendix an OR & Management Science book. I cannot find any other literature mentioning this notion; one would expect to be able to find some mention of it in complexity theory circles.

We should use a different definition for $\leq\_{pp}$. A pseudopolynomial reduction should be defined as a reduction, running in pseudpolynomial time, that in addition *does not increase integer values in the input more than polynomially*. **Then** the claim would hold true.

---
Tags: complexity-theory, np-complete, reductions, pseudo-polynomial
---


title: Proving a problem as NP-complete

text:
# Question
Title: Proving a problem as NP-complete
According to this article, A problem X can be proved to be NP-complete if an already existing NP-complete problem (say Y) can be polynomial-time reduced to current problem X. The problem also needs to be NP. Now my question is:

> Do we also need to prove that problem X can be reduced to at least one NP problem?

According to the definition of NP-completeness, each and every NP problem must be reducible to NP-complete problem. As problem X is NP, are we not supposed to prove that this NP problem can be reduced to other NP-complete problems? Why does this reduction have to be only one way to prove a problem is NP-complete?

# Answer
> 2 votes
As you have stated, there are two very clear requirements for a problem $X$ to be $\mathbf{NP}$-complete:

1. $X \in \mathbf{NP}$.
2. $X$ is $\mathbf{NP}$-hard. That is, for every $Y \in \mathbf{NP}$, $Y$ is (poly-time many-one) reducible to $X$.

> Do we also need to prove that problem $X$ can be reduced to at least one $\mathbf{NP}$ problem?

No, as this is not one of the above requirements. However, if you are able to do so, you've proved that $X \in \mathbf{NP}$ (i.e., requirement no. 1): Suppose $X$ is reducible to $Y \in \mathbf{NP}$. Then verifying $x \in X$ can be done in poly-time by reducing $x$ to an instance $y$ of $Y$ and then verifying $y \in Y$.

> As problem $X$ is $\mathbf{NP}$, are we not supposed to prove that this $\mathbf{NP}$ problem can be reduced to other $\mathbf{NP}$-complete problems?

There is no need to. If you know $Y$ is $\mathbf{NP}$-complete and you show $X \in \mathbf{NP}$, then necessarily $X$ is reducible to $Y$. There is no need for you to do "extra" work.

> Why does this reduction have to be only one way to prove a problem is $\mathbf{NP}$-complete?

I am afraid I am not quite sure which reduction you are referring to, but if you are talking about reducing $X$ to $Y$, then the answer is simply: That is what the definition of $\mathbf{NP}$-completeness requires you to do.

# Answer
> 1 votes
> Do we also need to prove that problem X can be reduced to at least one NP problem?

No. Every problem in **NP** can be reduced to some problem in **NP**: namely, to itself. "Can be reduced to at least one **NP** problem" isn't a part of the definition of **NP**-completeness, so you don't need to prove it. You just need to prove the things required by the definition.

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


# Question
Title: Proving NP completeness of maximal length path
I have this question to answer:

For each node i in an undirected network $G = (N,E)$, let $N(i) = \\{j \in N : \\{i, j\\} \in E\\}$ denote the set of neighbors of node $i$ and let $c\_e\geq0$ denote the length of edge $e \in E$. For each node $i \in N$, suppose the set $N(i)$ is partitioned into two subsets, $N^+(i)$ and $N^-(i)$ such that $j \in N^+(i)(j \in N^-(i))$ is referred to as a positive (negative) neighbor of $i$. (Note: Regardless of whether $j$ is a positive or negative neighbor of $i$, $i$ can be either a positive or negative neighbor of j.) Consider the problem of ﬁnding a maximum-length path $(s =) i(0)–i(1)–···–i(h)(= t)$ in $G$ between two nodes $s ∈ N$ and $t ∈ N$ subject to the following restriction: For each internal node $i(k)(k \in\\{1,...,h − 1\\})$ on the path, the set $\\{i(k − 1),i(k + 1)\\}$ must contain exactly one positive neighbor and one negative neighbor of $i(k)$. Prove NP-completeness of the decision problem and state whether it strongly NP-complete or not.

I wonder about the steps of the proof and whether shall I start from the longest path problem or from another problem instance.

# Answer
I think here is a pitfall due to inaccurate notation. Notation for me:

1. A *trail* is a sequence of distinct connected edges.
2. A *path* is a trail with distinct vertices.

In the problem instance $MNPL$ (maximum neighbor path length) the sets $(G,N^+, N^-)$ and the weight function $c\_e$ are given as input(and hereby fixed). Since $N$ is **partitioned**, for two vertices $u,v$ either $\\{u,v\\}\notin E$ or $u$ is a positive neighbor of $v$ or vice-versa. Especially $u$ and $v$ cannot be a positive neighbor of each other by definition ($N$ would not be partitioned). Hence $G$ must be a **directed graph**. Now, for any **path** $s \rightsquigarrow (u,v,w) \rightsquigarrow t$(not way nor cycle nor walk!) the neighbor-condition is fullfilled.

Maybe this was the real challenge of this exercise?

So, claim: $MNPL$ is $NP$-complete.

Proof: $MNPL \leq\_p LPP$ (longest path problem) Consider the reduction $f$. For $(G,N^+,N^-,c\_e)$ construct $G'=(V',E',c\_e')$ as the following:

1. $c\_e'$ = $c\_e$
2. $V' = V$
3. $E' = \bigcup\_{v \in N^+(u), u \in N} (u,v) \cup \bigcup\_{u \in N^-(v), v \in N} (v,u)$

Clear: $f$ is computable and runs in poly-time ($O(|E|)$). By construction and with the observations above $f$ will construct a digraph from $N$ and the neighbor sets.

So $f$ is a reduction and $MNPL \in NP$ is obvious using "guess and check". Since $LPP$ is strongly $NP$-complete, $MNPL$ is as well strongly $NP$-complete. This is no decision problem but a maximization problem.
> 1 votes

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


# Question
Title: How to calculate Big O of $T(n) = aT(n^b) + f(n)$?
I'm a student studying Big O. I know that we can solve $T(n) = aT(\frac{n}{b}) + f(n)$ by compering $n^{\log\_b{a}}$ to $f(n)$ or

> $O(n^{\log\_b{a}} + f(n))$

---

Today I was faced with $T(n) = T(\sqrt n) + 1$ and I think it is $O(\log\log n)$. and I was faced with this too, $T(n) = T(\sqrt n) + O(\log\log n)$ that I think it is $O(\log^2\log n)$.

I'm wondering what is the formula (or method) to solve any kind of this type of problems (my guess is $O(f(n)a^n\log\log n)$). so:

> How to calculate Big O of $T(n) = aT(n^b) + f(n)$ with $0\<b\<1$?

Thanks in advance.

# Answer
> 4 votes
> How to calculate Big O of $T(n) = aT(n^b) + f(n)$ with $0\<b\<1$?

The powerful technique you are searching for is variable substitution.

Let $S(m)=T(2^m)$. Then $$S(m)=T(2^m)=aT(2^{mb}) + f(2^m)=aS(mb)+g(m),$$ where $g(m)=f(2^m)$.

Now that we have a recurrence relation about $S(m)$, to which we might be able to apply the master's theorem. Here are some examples.

* If $f(n)$ is a constant, so is $g(m)$. If $a=1$ and $b=\frac12$, then we know that $S(m)=O(\log m)$. Hence, $$T(n)=S(\log n)=O(\log \log n).$$
* If $f(n)=\log n$, $a=1$ and $b=\frac23$, then $S(m)=S(2m/3)+m$. So $S(m)=O(m)$. Hence,
$$T(n)=S(\log n)=O(\log n).$$
* If $f(n)=\log\log n$, $a=1$ and $b=\frac12$, then $S(m)=S(m/2)+\log m$. So $S(m)=O((\log m)^2)$. Hence,
$$T(n)=S(\log n)= O((\log\log n)^2).$$

Note that the above reasoning is rather loose as $\log n$ and $\sqrt n$ might not be an integer when $n$ is. A lot of careful sandwiching together with some kind of continuity or monotonicity is needed to establish the result rigorously.

---
Tags: complexity-theory, time-complexity, big-o-notation
---


# Question
Title: Prove Subset-Sum is NP-complete - Alternative reduction?
It is well known the Subset-Sum problem is NP-complete. This can be shown using a reduction from the 3SAT problem. I am wondering: is there any other NP-Complete problem that could be reduced to the Subset-Sum problem?

# Answer
In general, each $NP$-hard problem can be reduced to all other known $NP$-hard problems (there exist hundreds).

For the subset-sum there is for a example *knapsack*. Subsetsum is a specialisation of knapsack.

The other way, if you could solve subset-sum in poly-time, then you would also be able to solve PARTITION (and 3-PARTITION and 4-PARTITION)
> 1 votes

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


# Question
Title: Thought process for the following problem?
We are given a 1-d array and we have to return the smallest array attainable after removing all the continuous same numbers. We can only eliminate those numbers which repeat continuously more than or equal to 3 times.

So for eg. `[1, 3, 3, 3, 2, 2, 2, 3, 1]` should return `[1, 1]` i.e. first the elimination of `2`'s occuring three times and after its elimination there is `3` for four times at stretch. After eliminating `3`'s we are left with `1`'s which occur less than three times, so no elimination.

Similarly `[3,1,2,2,2,1,1,1,2,2,3,1,1,2,2,2,1,1,1,2,3]` should return `[3,1,3,2,3]`. Here we can jumble the eliminations in different ways but no order of eliminations can lead to an array less than in size than `[3,1,3,2,3]`.

The time complexity should have a tighter upper bound than $O(n^2)$.

I am thinking of this problem but I haven't been able to identify a specific technique for solving it. I am thinking of `hashing`, `graphs` and also `recursion` but till now I have failure tackling the order of eliminations as the eliminations can happen in random order. More than the solution I would like to know the technique and thought process walkthrough of this problem.

# Answer
Using O(n) extra space, you need to record start for each run of same numbers. Scan the array linearly. Once you removed a run, you either continue previous run, or start a new one.

```
for i:
  if a[i] != a[i-1]:
    if run[x] - run[x-1] >= 3:
      x--
      // avoid copying the run into output array
    if a[run[x]] != a[i]:
      x++
    run[x] = i

```

On the second thought, you don't need the `run[]` array - only start the of current run. Once a run eliminated, you can check that previous run is at least 3 elements long in `O(1)` operations. You still need `O(n)` place to store the list of eliminated ranges, though.
> 1 votes

---
Tags: algorithms, arrays
---


# Question
Title: Can BPP be bounded around any constant other than 1/2?
A language $L$ is in BPP if there exists a randomised TM such that it outputs a correct answer with probability at least $1/2+1/p(n)$ for some polynomial $p(n)$, where $n$ is the length of the input. This probability can be amplified to $1-2^{q(n)}$, for some polynomial $q(n)$ by repeating the algorithm polynomially many times and taking the majority.

I was wondering if it is necessary to have this bound around the constant $1/2$? Can we have a randomised algorithm that answers correctly with probability $c+1/p(n)$ for some $c\<1/2$ and still amplify the probability in polynomial time?

The proof for the case of $1/2 + 1/p(n)$ uses Chernoff bound on lower tail that requires $0 \< \delta \<1$. $\delta= 1-1/2p$ in that case which means $p$ should be greater than $1/2$. Proof here.

However here is a proof that weak BPP = Strong BPP where strong BPP is BPP as we know it and weak BPP is when if $x\in L,$ $P(TM\ accepts\ x) \geq s(n)+1/p(n)$, and if $x \not\in L, P(TM\ accepts\ x ) \leq s(n)$, where $p(n)$ is any polynomial and $s(n)$ is any polynomial time computable function.

# Answer
If $c \< 1/2$ then for any problem there is an algorithm that answers correctly with probability at least $c+1/n$, say. For small $n$, the algorithm just outputs the hardwired correct answer. When $n$ is large enough so that $c + 1/n \leq 1/2$, the algorithm just tosses a coin.

What went wrong? For BPP amplification to work, we need a gap between the promise for a Yes instance and the promise for a No instance. In your definition of "weak BPP" (not a standard term), you are given an algorithm such that:

* On a Yes instance, accepts with probability at least $s(n) + 1/p(n)$.
* On a No instance, accepts with probability at most $s(n)$.

In contrast, in your suggested definition, we have the following promise:

* On a Yes instance, accepts with probability at least $c + 1/p(n)$.
* On a No instance, accepts with probability at most $1 - c - 1/p(n)$.

If $c \< 1/2$ then for large enough $n$, the two acceptance intervals overlap (at acceptance probability $1/2$), and so the definition is meaningless. When $c = 1/2$, there is an inverse polynomial gap, which can be amplified to a constant gap, to match the standard definition of BPP.
> 1 votes

---
Tags: randomized-algorithms, probabilistic-algorithms, chernoff-bounds
---


title: Complexity of "half cycle"

text:
# Question
Title: Complexity of "half cycle"
I'm working on the following problem:

*HALFCYCLE (HALFC):*

**Input:**

A directed graph $G = (V,E)$.

**Output:**

Whether the longest cycle in $G$ has length $ \lfloor |V|/2 \rfloor$.

> Prove that if $\mathsf{PH} \ne \mathsf{coNP}$ then HALFCYCLE is not NP-complete.

I have no idea how to solve this implication.

# Answer
Show that if HALFCYCLE is NP-complete then $\mathsf{NP}=\mathsf{coNP}$, and so the polynomial hierarchy collapses to NP.

How do you prove that if HALFCYCLE is NP-complete then $\mathsf{NP}=\mathsf{coNP}$? There are two options:

1. Show that coSAT reduces to HALFCYCLE. Since HALFCYCLE is NP-complete, in particular it is in NP, and so coSAT is in NP, implying NP=coNP.
2. Show that HALFCYCLE is in coNP. Since HALFCYCLE is NP-hard, in particular SAT reduces to HALFCYCLE, and so SAT is in coNP, implying NP=coNP.

(You can replace SAT with any NP-hard problem, and coSAT with any coNP-hard problem.)

Good luck!
> 0 votes

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


# Question
Title: Can the difference of a non-regular and a regular language be regular?
I have some trouble understanding some exercises related to operations on regular languages.I tried to apply their closure properties, but I am not sure how to do the following exercises:

1. If $L\_2,L\_3$ are regular and $L\_1 \setminus L\_2 = L\_3$, is $L\_1$ also regular?
2. If $L\_2,L\_3$ are regular and $L\_1 \cap \overline{L\_2} = L\_3$, is $L\_1$ also regular?

# Answer
> 2 votes
When $L\_2 = \Sigma^\*$, then $L\_3 = \emptyset$ no matter what $L\_1$ is.

---

Let us say that a language $L$ is *subset-regular* if $L \cap L'$ is regular for all languages $L'$. In other words, $L$ is subset-regular if all of its subsets (including $L$ itself) are regular.

**Theorem.** A language is subset-regular iff it is finite.

**Proof.** Clearly every finite language is subset-regular. In the other direction, an infinite language has uncountably many subsets, so not all of them can be regular. $\quad\square$

We can replace $\Sigma^\*$ above with the complement of any subset-regular language, that is, with any cofinite language. Moreover, due to the theorem above, only cofinite languages work: if $L$ has a non-regular (proper) subset $L'$, then $\overline{L'} \setminus \overline{L} = \overline{L'}$ isn't regular.

---
Tags: automata, regular-languages
---


# Question
Title: Random Access Machines with only addition, multiplication, equality
The literature is fairly clear that unit-cost RAMs with primitive multiplication are unreasonable, in that they

1. cannot be simulated by Turing machines in polynomial time
2. can solve PSPACE-complete problems in polynomial time

However, all of the references I can find on this topic (Simon 1974, Schonhage 1979) also involve boolean operations, integer division, etc.

Do there exist any results for the "reasonableness" of RAMs that **only** have addition, multiplication, and equality? In other words, which **do not** have boolean operations, truncated integer division, truncated subtraction, etc?

One would think that such RAMs are still quite "unreasonable." The main red flag is that they enable the generation of exponentially large integers in linear time, and due to the convolution-ish effects of multiplication, this can get particularly complex. However, I cannot actually find any results showing that this allows for any sort of "unreasonable" result (exponential speedup of Turing machine, unreasonable relationship to PSPACE, etc).

Does the literature have any results on this topic?

# Answer
> 2 votes
The other day I was reading a paper on parallelized random access machines without bit operations, which sounded very much like what you are describing. For these models NC is known not to equal P. See here: https://epubs.siam.org/doi/10.1137/S0097539794282930

The paper can also be found on Professor Mulmuley’s website.

---
Tags: complexity-theory, reference-request, computation-models, history
---


# Question
Title: Matching Algorithm - How to maximize matched quantity with unique matching rules?
Given a set $S=\\{A,B,\cdots,H\\}$. Elements in $S$ can be matched according to the following rules:

$$\begin{aligned} A\leftrightarrow B\\ C\leftrightarrow D\\ B+C\leftrightarrow F\\ D+A\leftrightarrow E\\ G+H\leftrightarrow B\\ \end{aligned}$$

The input to the matching algorithm is an array of variable size consisting of elements in $S$. Each item in the array has a particular size or "quantity" that can be matched (I imagine this can simply be modeled as edge weights).

For notational clarity -

$A \leftrightarrow B$ indicates "If an item exists in the input array of type A, it may match with an item of type B". The reverse is also true, so if there is $B$ it may match with $A$.

$B+C\leftrightarrow F$ indicates "If an item exists in the input array of type $B$, and another of type $C$, they may together match with an item of type $F$", the reverse is also true, so if there is $F$ and $C$, they may together match with $B$. $F$ by itself may not match with either $B$ or $C$.

---

The first question is, how to maximize the total quantity matched?

Second question is, how to optimize time complexity? If the algorithm is NP, please provide some proof or reason as to why it cannot be solved in P.

Intuitively, I think the problem could be modeled as a weighted bipartite graph and solved with a max-flow algorithm or dynamic programing. Once I construct the bipartite graph, the problem becomes easy to solve as bipartite graphs have been heavily studied.

The challenge is I'm not sure how to algorithmically construct the graph in a provably correct way given the rules or if it implies a different approach should be used. I'm thinking it may help to sort the input array by quantity and then not connect an edge if a vertex is marked as 'matched', but that alone doesn't solve the problem (i.e. BFS/DFS do not seem so help). Other potential avenues may be more generally 2D dynamic programing or set covers (although set covers are also in NP).

---

**An Example with the (not quite bipartite) Graph Approach:**

Take input array $\[A:5,\ A:4,\ D:6,\ B:3,\ E:5\]$, where $A:5$ indicates an item A with quantity 5. The bipartite graph should look like the below where the colors indicate potential matches (ignoring quantities) **except that it allows for impossible matches, namely $\\{A, E, A, B\\}$ should not be possible but is according to the graph**:

The potential matches should be:

1. $A, E, D$ (top edges)
2. $A, B$ (bottom edges)
3. $A, E, D$ (first bottom then top edges)
4. $A, B$ (top then bottom edges)

Ultimately the solution including quantity would be 2 matches with some quantity left over:

* ${A:5/5,\ E:5/5,\ D:5/6}$
* ${A:3/4,\ B:3/3}$

Left over

* $D:1$
* $A:1$

# Answer
The problem you are describing is a special case of the (weighted) 3-dimensional matching problem.1

Unlike regular 2-dimensional matching, maximum cardinality 3-dimensional matching is NP-hard, which means that weighted 3-dimensional matching is NP-hard. Therefore, solving this problem exactly in polynomial time doesn't seem feasible, unless the specific case you have here is easier than the general problem.

---

This special case *seems* easier than the general problem. My idea is to represent it as a minor modification to the regular 2d maximum weight matching problem. Note that for each of your combinations of 3 items, there is at least one item type that is not present in another combination (e.g. $E$ is only present in the combination $(A,D,E)$), I will call such an item type *conflict-free*. First, select a conflict free type for each combination of $3$ types: Here, I pick $E$ for $(A,D,R)$, $F$ for $(B,C,F)$, and $H$ treat items of such type differently than the others.

More concretely, for any combination of items $x,y,z$ of type $X,Y,Z$, where $Z$ is the chosen conflict-free type, we add only the edge $(x,y)$ of weight $f(q(x), q(y),q(z))$, where $q(i)$ denotes the quantity of item $i$ and $f$ is a function that determines the value of a matching based on the weight (including the type is of course also possible). Combinations with only $2$ types can be modeled as usual. Solving the maximum weight matching problem on this graph (which in your case is bipartite) provides the maximum sum of values that can be made.

For example, on the input $\[A:5,\ A:4,\ D:6,\ B:3,\ E:5\]$, the graph will look like the following:

Red edges and their weights indicate the maximum matching. Note that the item of type E is not part of the graph, but *only influences the weight* of the two edges between types A and D. So the approach works for this case.

However, if we have items of type E with different quantity, we the weights of the edges will depend on which edges are selected. To see this, take the input $\[A:5,\ A:4,\ D:6,\ D:4,\ B:3,\ E:5,\ E:1\]$. We now get the following graph:

The edges between type $A$ and $D$ now no longer have a simple value as their weight, but a list of values. This is because each edge has to use one of the two $E$'s, but the same one cannot be reused. This means in particular that the blue matching has a value of $12+3=15$ instead of $12+12=14$, because the item $E$ of quantity $5$ can only be used once. Therefore, it is the red matching of value $21$ that is optimal.

I do not know whether the standard algorithms for weighted bipartite matching can deal with this modification on the weights or whether there we can make a modification to the standard algorithm to handle this.

---

1: Possible matches of the form $X+Y\leftrightarrow Z$ for items $x, y, z$ can be represented by the 3d-edge $(x,y,z)$ of weight the minimum of the quantities of the items $x,y,z$. Matches of the form $X\leftrightarrow Y$ for items $x,y$ can be represented by the 3d-edge $(x,y,d)$ of weight minimum of the quantities of items $x,y$ and a dummy vertex $d$ that is in no other 3d-edge.
> 2 votes

---
Tags: algorithms, graphs, time-complexity, matching, bipartite-matching
---


title: What is the graphic TSP?

text:
# Question
Title: What is the graphic TSP?
I'm not sure if I understand the following definition of the (well-known apparently) *Graphic TSP*, also known as *graph-TSP* :

> ...graph-TSP, that is, the traveling salesman problem where distances between cities are given by any graphic metric, i. e., the distance between two cities is the length of the shortest path in a given (unweighted) graph.

this is from Mömke and Svensson's paper : https://arxiv.org/pdf/1104.3090.pdf

I understand this as follows :
\- one is given an input graph, say G, that is unweighted (and supposedly connected).
\- one then can construct a complete graph, say G', where cost of edge (u,v) is the minimum distance between u and v in G.
\- obtaining an optimal TSP solution in G' results in an optimal solution for the graphic TSP on G.

Is this correct?

# Answer
> 2 votes
Your understanding is correct.

The key point about TSP is that we are given a distance between every pair of cities. In other words, formally speaking, TSP is the problem of finding a minimum-weight Hamiltonian path/cycle on a weighted complete graph, given the weight function. This doesn't quite correspond to the standard intuition where a salesman is travelling around an actual road network and is forbidden from visiting the same city twice, for reasons nobody can really explain.

In graphic TSP, the distance function is defined in terms of some (possibly weighted, possibly directed) graph on the given vertices. This is much closer to the usual intuition about what TSP is: driving from, say, Baltimore to New York by the fastest route might involve passing through Philadelphia but, even if we've already visited Philadelphia, we're allowed to pass through again without stopping.

# Answer
> 0 votes
Yes, I agree with your characterization for connected graphs. In the case where $G$ is disconnected, you instead create a $G'$ which is the disjoint union of cliques, each corresponding to a different connected component of $G$. $G'$ will always contain edges not present in $G$, except in the case where $G$ is the disjoint union of cliques.

I generally think it's best to think of graph TSP as a data structure that augments the TSP that it is derived from.

---
Tags: graphs, weighted-graphs, traveling-salesman
---


title: One-taped RAM vs Multi-taped RAM

text:
# Question
Title: One-taped RAM vs Multi-taped RAM
In Turing Machine, we know that there's (fine-grained complexity) difference between one-tape, 2-taped and multi-taped TM, even though they could be simulated efficiently.

(Well, actually I'm not quite sure they are indeed seperated: i.e. $TIME(t)\neq TIME\_{2-taped}(t)\neq TIME\_{multi-taped}(t)$ )

But today I'd like to focus on RAM model, is there any complexity seperation between one-taped RAM model and multi-taped model? Though we might expect it be quite small because of random accessibility.

# Answer
> 3 votes
Random-access machines support the following operation in constant time: $$ x \gets M\[y\], $$ where $M$ is the memory array, and $y$ is an index whose allowable size depends on the exact model. Whether $M$ is an array of bits or an array of words depends on your exact model.

If you had several different memory arrays, say $M\_1\[y\],\ldots,M\_r\[y\]$, then you could simulate the command $$ x \gets M\_i\[y\] $$ with the command $$ x \gets M\[ry + i\] $$ which also takes constant time.

Therefore there is nothing to be gained by allowing several "memories".

---
Tags: complexity-theory, turing-machines
---


title: String matching and bioinformatics

text:
# Question
Title: String matching and bioinformatics
I'm interestd in string-matching, I would like to know recent open problems in string-matching in field of bioinformatics.

# Answer
The list of open problems in bioinformatics: string matching is outlined in Some string matching problems from Bioinformatics which still need better solutions this article is old, but problems remain.
There is also presentation Analytic pattern matching: From DNA to Twitter.

Some are related to graph automorphism (so may remain open for a bit longer) for example:

> Extend String Pattern Matching to Graph Pattern Matching, that is, replace the text T by a graph G and find the number of occurrences of a given subgraph/pattern *g* in G for different models of graph G generation.
> 0 votes

---
Tags: reference-request, bioinformatics, string-matching
---


# Question
Title: calculating a shortest path in a table structure that changes in real time
I have a table that looks like this

In table NPC - are AI like characters that move from one point to another. Player - a character that is controlled by the user.

In any moment the player character might move to any cell of the table. But NPC has a particular goal cell that they should reach while moving. For example, blue NPC needs to read blue cell.

Other NPC are also moving. My goal is to write an algorithm that would allow NPC to reach the cell using the shortest path. As far as I understand it is a typical shortest path problem.

My question is - is there some algorithm that particularly optimized to handle such workflows, or any algorithms will suffice - just with recalculating the path after each move?

# Answer
There are many; you can find a list here. The most applicable is probably D\*-lite.

However, there are not many off-the-shelf implementations for it, so the vast majority of games just recalculate the best path using A\*. There are many visual and technical tricks for recalculating as infrequently as possible without negatively affecting the game, but that's more of a question for gamedev.stackexchange.com.

For NPCs in particular, you may also want to look into pathfinding with many units at once. Some typical search-terms for this are "swarm pathfinding", "boids", "flocking behaviors", and "collision avoidance pathfinding"
> 1 votes

---
Tags: shortest-path
---


title: Are all compilers Turing Machines?

text:
# Question
Title: Are all compilers Turing Machines?
So the definition of a compiler I got is that:

> A compiler takes a string as input and checks if that string is syntactically correct, then outputs "Yes" or "No".

So does that mean all compilers are Turing Machines?

# Answer
> 5 votes
No, a compiler takes as string as input and checks if that string is syntactically correct. If it is, it outputs another string (code in a different language, e.g., machine code) that is equivalent to the input; if it is not, it outputs "syntax error".

A Turing machine is an abstract machine (i.e., a description of a machine, rather than an actual physical thing) that performs computations. According to the Church–Turing thesis, anything that can be computed by any physical system can be computed by a Turing machine. Since compilers are implemented on physical systems, one could, in principle, design a Turing machine that computes the same mapping from strings to strings as any given compiler. But it's not true that a compiler *is* a Turing machine; rather, a compiler does something that a Turing machine can also do.

---
Tags: turing-machines, compilers
---


# Question
Title: Given n standard C++ STL maps, can I merge them?
I was wondering if it is possible to merge standard STL maps in O(log(n)) using DSU trick.

For example, Map a={{1,2},{3,2},{4,3}}, Map b={{2,3},{3,2},{4,1}} and Map c={{2,1},{3,2},{4,4}}

Then the resultant map will be : {{1,2},{2,4},{3,6},{4,8}}

If not achieveable by DSU, is there any other algorithm to achieve this in O(logn) complexity?

Here n is the number of maps and the sum of the sizes of all maps is 10^5. n can range from 1-10^5.

# Answer
STL maps are stored in a data structure which is effectively sorted by key, typically some kind of binary search tree. BSTs have the property that finding the smallest key and finding the next larger key are both amortised O(1) (assuming you can find a node's children in constant time).

So doing your merge is similar to merging `n` sorted arrays, which has complexity $N log n$, where $N$ is the total number of elements in all the arrays. (Sorting the concatenation of all the arrays is $O(N log N)$, which is both practically and theoretically slower.

A simple $O(N log n)$ algorithm is to repeatedly do the following until only one array is left:

* Divide the arrays into two $n/2$ pairs. If there is an odd number of arrays, one array is treated as though it were paired with an empty array.
* Merge each pair into a single array using the standard merge algorithm, which involves iterating through both arrays in parallel.

The total number of elements scanned in each iteration is at most $N$. (It will be slightly less because the merge procedure combines two elements with the same key, so that the next iteration will involve fewer elements. But $O(N)$ is an acceptable estimate.)

Since the number of trees is halved each time, it will take $\lceil log\_2 n\rceil$ iterations to reduce the number of groups to one. So the he total time is the product of the number of iterationss and the total number of elements scanned, which is $O(N log n)$.
> 1 votes

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


# Question
Title: Algorithm for generating random incrementing numbers up to a limit
I'm trying to write a code to generate incremental sequences of numbers such as:

```
0 + 1 + 3 + 5 + 1 = 9
0 + 5 + 1 + 1 + 1 = 8
0 + 1 + 1 + 2 + 1 = 5

```

I have 3 constraints:

1) I need to have limited number of addends (here it is `=5`)

2) final sum must be smaller than certain limit ( here limit is `<9`)

3) addends must be random

As for now, I generate sequences randomly and select only suitable ones. For 2-digit numbers and for long sequences (`>8`) my algorithm takes significant time.

Is there a better algorithm for such problem?

As least could you tell me, what branch of CS is studying such problems?

UPDATE (algorithm):

```
0) array = [0,]; // initial array
1) if sum(array) > 99, go to 6)
2) generate random number in [1..99], let's say rand = 24
3) rand = array[-1] + rand // add random number to last value of array
4) array.push(rand) // add the random number to array
5) goto 1)
6) if length(array) < 5, goto 0) // 5 is desired sequence length

```

# Answer
**A simple remedy**

The reason why your algorithm produces desired sequences in a very low rate might be that you are generating random numbers that are so large on average that it is not easy for the sum of them to be smaller than the limit 100. A simple remedy is to change line 2) of your pseudocode to

```
2) generate random number between 1 and 55, let's say rand = 24

```

Here the upper limit, 55 is a number near 48 = 99//4 \*2, where 4 = 5 - 1 is the number of numbers to be generated (it seems you require the first number must be 0) and 99//4 is about the average of each number. Then the algorithm will be much more likely succeed without going back to line 0). It is possible that the upper limit should be slightly bigger than 2 times the average to approximate the maximum rate of production. I profiled a few times so as to determine that 55 is the fastest number. You can experiment to find what is the best limit.

**As successive differences**

Here is another way to generate the desired sequences with length $m$ and sum less than $n$. It works well if $n$ is not large, in which case it does not take long to complete the sorting step.

1. Generate $m$ random numbers between 0 inclusive and $n$ exclusive.
2. Sort them so we obtain $a\[0\]\le a\[1\]\le\cdots\le a\[m-1\]$.
3. Return sequence $b\[0\], b\[1\], \cdots, b\[m-1\]$, where $b\[0\]=a\[0\]$ and $b\[i\]=b\[i\]-a\[i-1\]$ for all $i\gt1$.

**Scaling technique, the fastest way**

1. Generate m random numbers between 0 inclusive and 1, a\[0\], a\[1\], ..., a\[m-1\].
2. Let s be the sum of them. Compute the scaling factor f = u/s, where u is the given upper limit of the sum.
3. Let b\[i\] be a\[i\] multiplied by f, chopping off the fraction part.
4. Return sequence b\[0\], b\[1\], ..., b\[m-1\].

You can also try generating m + k of them, following by the same scaling step, but returning only the first m numbers. You can either fix k or even let k be random.

---

Note that different algorithms generate sequences with different "randomness", which may or may not be significant for your purpose.

---

You can search for how to generate random sequences with given sum for more methods. If you prefer sum to be less than a given limit, just generate a longer sequence with a sum that is bigger than the given limit. Then take the first m numbers.
> 0 votes

---
Tags: algorithms
---


# Question
Title: Complexity and hardness of undirected path
Let $PATH = \\{(G,s,t) \mid \exists \text{path from}~s\text{ to }t\text{ in }G\\}$, where $G$ is a directed graph. We know that $PATH$ is $NL$ complete. I am wondering what the complexity class of $PATH$ on undirected graphs is and whether any hardness results for $PATH$ on undirected graphs are known?

# Answer
The undirected version of PATH, usually known as USTCON, is in L due to Reingold's theorem.

USTCON is trivially complete for L with respect to logspace reductions. I don't know if it is L-complete with respect to weaker reductions such as $\mathsf{AC}^0$ reductions; see this question.
> 1 votes

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


# Question
Title: Showing that a language is NP Complete (advice)
I am currently getting ready for my final exam in computational models. I know that there aren't any rules or rule of thumb to show that a language is NP-complete and each problem has its own tricks, but I am really struggling with questions where they give me a language and showing that the language is NP-complete by showing that an NPC problem is polynomial reducible to the given language.

So I wanted to ask for advice. How can I approach such problems? Are there any steps that I can take before to help me somehow? Or is it just literally figuring out which NPC problem is "closest" to the the given language and try to construct a polynomial reduction?

I'd appreciate any advice. Thank you.

# Answer
Typically, yes, it's a matter of finding a known **NP**-complete problem that's somehow similar to the one you're trying to work with. So if you're dealing with a problem about formulas, you probably want to reduce some version of SAT or 3SAT to it.

For graph problems, you probably want to reduce some other graph problem. Problems about long paths and cycles probably come from Hamiltonian path/cycle. Problems about classifying vertices into types sound like colouring problems. Problems about graphs containing or not containing some structure might come from clique or independent set. Problems about dividing graphs in two might be Max Cut, or Subset Sum.

Reductions from one type of problem to another are typically more difficult. If you ahve to do that, think about how you can use your target problem to encode things that are needed in the known **NP**-complete problem. For example, when you reduce 3SAT to independent set, being in or out of the independent set corresponds to being true or false; when you reduce 3SAT to 3-colourability, the three colours you use are "true", "false" and "er, the other colour". But, in these cases, the reduction gadgets tend to be quite fiddly.

Another thing to bear in mind is that, if problem $A$ looks like problem $B$, which you already know to be **NP**-complete, it might be possible to modify that proof to make it work for $A$. For example, consider 4-colourability. The easy reduction is from 3-colourability: given a graph $G$, add a new vertex, connect that to everything and the new graph is 4-colourable if, and only if, the original graph was 3-colourable. But, if you didn't see that and you knew the reduction from 3SAT to 3-colourability well, it probably wouldn't be very hard to modify that reduction so the four colours were "true", "false", "er, the other colour" and "gee, there are a lot of colours today".
> 4 votes

---
Tags: complexity-theory
---


# Question
Title: Help with figuring out if MAX(L) is a CF language
We call the word $x\_1$ a true prefix of the word $x$, if a non-empty word $x\_2$ exists so that $x=x\_1x\_2$. For the language L (over some finite $abc$..). We define MAX(L) as:

$MAX(L)$ = {$w\_1 \in L $| $w \notin L$ so that $w\_1$ is a true prefix of $w$}

prove (or disprove): If the language L is CF then the language $MAX(L)$ is CF.

I think that the correct direction here is to disprove. The question is, how do I disprove it for a general $L$?

I know how to use the pumping lemma to disprove a certain language, but I'm not sure if it can work for a general $L$?

Am I going in the right direction or am I completely wrong?

# Answer
Let $L = a^\*b^\*c^\* \setminus \\{ a^n b^n c^k : k \> n \\}$. To see that $L$ is context-free, note that we can write it as follows: $$ L = \\{ a^n b^m c^k : n \> m \\} \cup \\{ a^n b^m c^k : m \> n \\} \cup \\{ a^n b^m c^k : k \leq n \\}. $$ The only way in which a word in $L$ cannot be extended non-trivially into another word in $L$ is if the word is of the form $a^nb^nc^n$ for $n \geq 1$. Therefore $$ \mathrm{MAX}(L) = \\{ a^n b^n c^n : n \geq 1 \\}, $$ which is known to be non-context-free.
> 2 votes

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


# Question
Title: Solving recurrence relation with minimum and factorial
I need to solve the following recurrence relation, where $T(n,m)$ is defined over $\Bbb N\_+\times\Bbb N\_+$.

$T(n,m)=\begin{cases} 1, & n=1\text{ or }m\leq 2(n-1)!\\ \min\limits\_{a,b,c\geq 1,\ c\le n-1\\a\leq c!,\ b\leq(n-c)!}{T(c,a)+T(n-c,b)+T(n,m-ab)}, & \text{else.} \end{cases}$

Note: This question is highly related to my previous question here, since $ab\leq\max\limits\_{1\leq c\leq n-1}{c!(n-c)!}=(n-1)!$

I guess that the minimum is obtained at $c=\lceil n/2\rceil,a=c!,b=(n-c)!$, but I don't know how to prove it.

The first 10 values of the first n's are:

$T(1,\*)=1, 1, 1, 1, 1, 1, 1, 1, 1, 1,\dots\\ T(2,\*)=1, 1, 3, 5, 7, 9, 11, 13, 15, 17,\dots\\ T(3,\*)=1, 1, 1, 1, 3, 3, 5, 5, 7, 7,\dots\\ T(4,\*)=1, 1, 1, 1, 1, 1, 1, 1, 1, 1,\dots$

Experiments show that

$$T(n,m)=\begin{cases}1 & n=1 \text{ or }f(n,m)\leq 0,\\ 3+2\Big\lfloor\frac {f(n,m)-1}{g(n)}\Big\rfloor & \text{otherwise},\end{cases}$$

for $f(n,m)=m-2(n-1)!$, and for some $g$ whose first values are: 1, 1, 2, 4, 12, 48, 240. I guess that $$g(n)=\begin{cases}1 & \text{if }n\<3,\\ 2(n-2)! & \text{otherwise.}\end{cases}$$

# Answer
### Summary

It is not true that the minimum can always be obtained at $c=\lceil n/2\rceil,a=c!,b=(n-c)!$. Here is the smallest counterexample, $$T(5,49) = T(1,1) + T(4,1) + T(5,48) = 3 \not=5=T(3,6)+T(2,2)+T(5,12).$$ Instead, the minimum can always be obtained at $c=1$, $a=1$, $b=2(n-2)!.$

The following neat formula conjectured in the question is correct. $$T(n,m)=\begin{cases} 1 & n=1 \text{ or }f(n,m)\leq 0,\\ 3+2\Big\lfloor\dfrac {f(n,m)-1}{g(n)}\Big\rfloor &\text{otherwise}, \end{cases}$$ where $f(n,m)=m-2(n-1)!$ and $g(n)=\begin{cases}1 &\text{if }n\<3,\\ 2(n-2)! &\text{otherwise.}\end{cases}$

### Observations

1. $T(n,m)=1,$ if $n=1$ or $m\le 2(n-1)!$.
2. $T(n,m)$ is nondecreasing with respect to $m$.
3. $T(n,m)\ge3$ if $m\gt 2(n-1)!$.
4. $T(2,m)=\begin{cases} 1 & m\le2,\\ 2m-3 & \text{otherwise}.\end{cases}$
5. If $n=3,4,5$, then the conjectured formula is correct.
6. The following proposition $p(n,j)$ is true for all $n\ge3$ and $j\ge0$. $$\text{If $n\ge3$ and $j=\lfloor\frac{f(n,m)-1}{2(n-2)!}\rfloor$ for some $j\ge0$ and $m$, then $T(n,m)=3+2j.$}$$

The conjectured formula is the same as the combination of observations 1, 4, and 6.

All observations above except observation 6 can be proved easily, although observation 5 might take a while to sort out case by case.

Let $S(n,m,a,b,c)=T(c,a)+T(n-c,b)+T(n, m-ab)$. Then for $m\gt 2(n-1)!$, $T(n,m)= \min\limits\_{a,b,c\geq 1,\ c\le\frac n2\\a\leq c!,\ b\leq(n-c)!}S(n,m,a,b,c).$ The reason why we can replace the condition $c\le n-1$ by $c\le \frac n2$ is that $(n,m,a,b,c)=(n,m,b, a, n-c)$.

## Proof of observation 6 by well-founded induction

Here are the steps. Steps 1 and 2 are the induction bases while step 3 is the induction step.

1. Suppose $j=\lfloor\frac{f(n,m)-1}{2(n-2)!}\rfloor=0$, i.e., $2(n-1)!\lt m\le2(n-1)!+2(n-2)!$. Since $m\gt 2(n-1)$, $$T(n,m)\ge3.$$ On the other hand, $$T(n,m)\le S(n,m,1,2(n-2)!,1)=1+1+1=3.$$ So $T(n,m)=3$, i.e., $p(n,j)$ is true when $j=0$.
2. Observation 5 says that $p(n,j)$ is true for $n=3,4,5$.
3. Let $n\ge6$ and $j\ge1$. As induction hypothesis, suppose $p(x,y)$ is true for all $x\le n$ or $x=n$ and $y\lt j$, i.e., $T(x,y)=3+2\lfloor\frac{f(x,y)-1}{2(x-2)!}\rfloor$, which implies, by the definition of $\lfloor\cdot\rfloor$, $$(x-2)!(T(x,y)+2x-5)\<y\le (x-2)!(T(x,y)+2x-3).$$

We will prove that $p(n,j)$ is true, i.e., $T(n,j)\le 3+2j$.

Let $j=\lfloor\frac{f(n,m)-1}{2(n-1)!}\rfloor$ for some $m$.

**Proof for $T(n,m)\le 3+2j$**

By induction hypothesis, we know that $T(n, m-2(n-2)!)=3+2(j-1)$. Hence, $$T(n,m)\le S(n,m,1,2(n-2)!,1)=1 + 1 + T(n, m-2(n-2)!)=3+2j.$$

**Proof for $T(n,m)\ge 3+2j$**

Because $T(n,m)$ is nondecreasing with respect to $m$ (observation 2), we will assume $m=2(n-1)!+2(n-2)!j+1$, the smallest value possible such that $j=\lfloor\frac{f(n,m)-1}{2(n-2)!}\rfloor.$

We will prove that $S(n,m,a,b,c)\ge 3+2j$ for all valid choices of $(a,b,c)$. The case when $c=1$ or $c=2$ is relatively easy. From now on assume $3\le c\le \frac n2$.

Let $A=T(c,a)$ and $B=T(n-c,b)$. The case when $A=1$ or $B=1$ is much easier to prove. Now assume $A,B\ge2$.

* Since $c\<n$, we have $a\le(c-2)!(A+2c-3)$.
* Since $n-c\<n$, we have $b\le(n-c-2)!(B+2n-2c-3)$.
* Since $ab\ge1$, we have $\lfloor\frac{f(n,m-ab)-1}{2(n-2)!}\rfloor\<j$, so we can apply induction hypothesis to yield the first equality below.

Since $T(n,m)$ is nondecreasing w.r.t $m$, $$\begin{aligned} &S(n,m,a,b,c)\\ &\ge A+B+T(n,m-(c-2)!(A+2c-3)\\,(n-c-2)!(B+2n-2c-3))\\ &= A+B+3+ 2\lfloor\frac{f(n,m-(c-2)!(A+2c-3)(n-c-2)!(B+2n-2c-3))-1}{2(n-2)!}\rfloor\\ &= 3+2j+ A+B +2\lfloor\frac{-(c-2)!(A+2c-3)(n-c-2)!(B+2n-2c-3))}{2(n-2)!}\rfloor\\ &\gt 3+2j+ \frac{(c-2)!(A+2c-3)(n-c-2)!(B+2n-2c-3)}{(n-2)!}(h(c,A,B)-1) \\ \end{aligned}$$

where $$h(n,A,B,c)=\frac{(A+B-2)(n-2)!} {(c-2)!(A+2c-3)(n-c-2)!(B+2n-2c-3)}.$$ Since $n-c\<n$, induction hypothesis yields the second equality below. $$\begin{aligned} B&=T(n-c,b)\le T(n-c, (n-c)!)\\ &=3+2(\frac{(n-c)(n-c-1)}2-(n-c-1)-1)\\ &=(n-c)(n-c-3)+3. \end{aligned}$$ Since $n\ge6$ and $c\ge3$, $(n-2)!\ge (n-2)(n-3)(n-4)(c-2)!(n-c-2)!.$
Since $n\ge6$, $c\le \frac n2$ and $A,B\ge2$, $(n-2)(A+B-2)\gt A+2c-3.$

$$\begin{aligned}h(n,A,B,c) &\ge\frac{(A+B-2)(n-2)(n-3)(n-4)}{(A+2c-3)(B+2n-2c-3)}\\ &\ge\frac{(n-3)(n-4)}{B+2n-2c-3}\frac{(n-2)(A+B-2)}{A+2c-3}\\ &\ge\frac{(n-3)(n-4)}{(n-c)(n-c-1)}\frac{(n-2)(A+B-2)}{A+2c-3}\\ &\gt1 \end{aligned}$$

So $S(n,m, a,b,c) \gt 3+2j.$

The proof is complete. By the way, the proof for $T(n,j)\le 3+2j$ shows that the minimum can always be obtained at $c=1,$ $a=1,$ $b=2(n-2)!.$

### Exercises

**Exercise 1.** Prove the formula for $T(2,m)$.

**Exercise 2.** (Observation 5) Prove the formula for $T(3,m)$, $T(4,m)$, and $T(5,m)$. Hint, the proof of observation 6 above might be helpful.

**Exercise 3.** Let $T\_1$ be defined over $\Bbb N\_{+}\times\Bbb N\_{+}$. $$T\_1(n,m)=\begin{cases} 1, & n=1\text{ or }m\leq (n-1)!\\ \min\limits\_{a,b,c\geq 1,\ c\le n-1\\a\leq c!,\ b\leq(n-c)!}T\_1(c,a)+T\_1(n-c,b)+T\_1(n,m-ab), & \text{else} \end{cases}$$ Show that $$T\_1(n,m)=\begin{cases} 1 & n=1 \text{ or }m\le (n-1)!,\\ 3+2\Big\lfloor\dfrac {m-(n-1)!-1}{(n-2)!}\Big\rfloor & \text{otherwise}.\end{cases}$$
> 5 votes

---
Tags: recurrence-relation, factorial
---


# Question
Title: How to find size of each tree in a forest?
Let $T$ be a tree with $n$ nodes. If I remove $k$ edges from $T$, I will have $k+1$ new trees i.e. a forest of $k+1$ trees.

How do I calculate the number of nodes in each of these new trees formed?

I need to do this for $q$ queries.

My approach: I can remove the $k$ edges from the original tree and run DFS on each nodes from which edge was deleted and find the size of the new tree. And then join the nodes back after getting size of each tree. But this is not optimal, can anyone suggest a better approach.

# Answer
You can use any number of Dynamic Connectivity data structures, namely, an euler tour dynamic connectivity tree.

To summarize the reference, if you label the vertices of the original tree $T$ according to the *first* (denoted $label\_f$) and *last* (denoted $label\_l$) euler-tour visit order on $T$, you can maintain a BST $T^\*$.

Each node $x$ in $T$ is linked to two nodes in $T^\*$: $v\_1$, $v\_2$, where $key(v\_1) = label\_f(x)$ and $key(v\_2) = label\_l(x)$. Note $|T^\*| = 2n $ and BST operations on $T^\*$ will cost $O(\log n)$

Now, we can support the following operations on $T$:

* $cut(u, v)$: Disconnect the edge $(u,v)$. Denote $x$ the vertex whose $label\_f$ is lesser. It is done simply by splitting from $T^\*$ the interval $\[label\_f(x),label\_l(x)\]$ which can be done in $O(\log n)$ by splitting and merging.
* $findroot(v)$: Since the root of the tree has the minimum $label\_f$, the root of $v$ will be the minimum node in the euler-tour BST in which he belongs

Since each node $x$ in $T$ is represented by exactly two nodes in $T^\*$, by simply saving rank (tree size) on the euler tour BST ($T^\*$), and dividing by $2$ you can answer the question "How many nodes are in the tree of $x$?" in $O(1)$, granted you are willing to pay $O(\log n)$ each time you disconnect an edge.
> 2 votes

---
Tags: trees
---


title: Universal hashing function probability

text:
# Question
Title: Universal hashing function probability
Can somebody explain the following:

<sub>(source: fbcdn.net)</sub>

U is a universe of keys, and H is a finite collection of hash functions mapping U to {0, 1, … , m-1}.

I do not understand definition 2, and thus why amount of funtions that map x and y to the same location is given by |H|/m.

# Answer
Let’s begin by talking about the intuition for universal hash families. Intuitively, a family of hash functions is universal if for any distinct objects x and y that you’d like to hash, if you select a random hash function from the hash family, the probability that you get a collision between those two elements is at most 1/m, where m is the number of buckets. In other words, universal hash families tend to spread elements out in a way where the probability of a pair colliding is the same as if the elements were distributed randomly.

Let’s see how the definition accomplishes this. Here’s the definition from your question:

> H is universal if ∀ x, y ∈ U where x ≠ y | { h in H : h(x) = h(y) } | = |H| / m.

For starters, I’m assuming that we’re talking about hash functions that map from some set U to the integers 1 through m or 0 through m-1. With that in mind, let’s unpack some of this notation.

If we replace the universal quantifier (∀) with the plain English “for all,” this definition says “H is universal if for every choice of two different items x and y to hash, some inequality is true.” So let’s look at that inequality. First, what is this bit?

> | { h in H : h(x) = h(y) } |

The vertical bars here represent the size of a set, and the set in question is this one:

> { h in H : h(x) = h(y) }

Read literally, this is the set of all hash functions h in the family H where h(x) = h(y). Keeping in mind that we’re talking about hash collisions here, we can think of h(x) = h(y) as saying that hash function h causes x and y to collide with one another (have the same hash code). With that in mind, the complex expression

> | { h in H : h(x) = h(y) } |

means “the number of hash functions in H where x and y collide.” Combining that with our earlier bit, we can rewrite the entire definition as

> H is universal if for any two distinct elements x and y that we want to hash, the number of hash functions in H where x and y collide is at most |H| / m.

So what’s |H| / m? That’s the total number of hash functions (|H|) divided by the number of possible outputs for any one single hash function (m). It might help to divide the entire expression through by |H|, which would then give this final definition:

> H is universal if for any two distinct elements x and y that we want to hash, the probability of picking a hash function h where x and y collide (that is, the total number of hash functions where x and y collide divided by the total number of hash functions) is at most 1/m.

Hope this helps!
> 3 votes

# Answer
As you found it is just a definition. You can ask about what is the meaning of the definition. It means the set of function `H` is universal if for every two different members of `U`, has exactly the same number of hash function exists in `H` and that number is `|H|/m`.

The intuition behind this definition comes from the application over this definition. As a set of function is universal (satisfy the definition), the probability of choosing a function from `H` to have the same value over two different members of `U` is `1/m`, and it means this probability depends uniformly on the size of `m` (the range space of those hash functions).
> 0 votes

---
Tags: hash
---


# Question
Title: Superset of another language and recognizability of turing machines
$L\_1$ = $\\{\langle M \rangle \mid M$ is a turing machine and $M$ halts on some string$\\}$

$L\_2$ = $\\{\langle M \rangle \mid M$ is a turing machine and $M$ halts on all strings $\\}$

a) Is $L\_2$ a superset of $L\_1$ ?

b) Is $L\_2$ not co-recognizable and not recognizable ?

(without formally proving)

---

**my attempt**

$a)$ $L\_2$ is a superset of $L\_1$ since all strings are in $L\_2$ whereas $L\_1$ is some string

$(b)$ $L\_2$ is not recognizable because, out of the infinite enumerations of strings, a single one could not halt disproving it from being recognizable.

For not co-recognizable: It can be written like this

$\bar{L\_2} = \\{ \langle M \rangle \mid M$ is a turing machine and $M$ loops on some string $\\}$.

It's not possible to make a recognizer for loops so its instantly not co-recognizable. This is because looping means it never stops so to come up with a recognizer for anything to prove it loops is impossible since we are working with infinite combinations.

Not sure about it being a superset or not and my explanation for co-recognizable

# Answer
If a machine halts on all strings then it halts on some string. Therefore $L\_2 \subseteq L\_1$.

If a machine halts on some string but not on all strings then it is in $L\_1 \setminus L\_2$. Since there are such machines, $L\_1 \subsetneq L\_2$.

---

The language $L\_2$, usual known as TOT, is well known to be $\Pi\_2$-complete. In particular, it is neither r.e. nor co-r.e. This can also be proved directly by reducing both the halting problem and its negation to $L\_2$:

* Given a Turing machine $M$ and an input $x$, construct a Turing machine $M'$ which erases its input and then runs $M$ on input $x$. Then $M$ halts on $x$ iff $M' \in L\_2$.
* Given a Turing machine $M$ and an input $x$, construct a Turing machine $M'$ which on input $n$ simulates $M$ on $x$ for $n$ steps, and loops if $M$ halted within $n$ steps. Then $M$ doesn't halt on $x$ iff $M' \in L\_2$.
> 0 votes

---
Tags: turing-machines
---