# Question
Title: Prove Recursive formula (Dynamic programming) N(C,i)
I've been asked to prove the correctness of the following recursive formula. The formula is trying to define, how many ways you can spend your money C on the i amount of beers. I did the following recursive formula where you either bought a beer and losing $P-i$ money, or passed the beer and went for the next in the array $i-1$. You cannot buy the same type of beer twice.

$$N(C,i)=\begin{cases} 0 & \quad \text{if } C\<0\\;||\\; i\<0 \\ 1 & \quad \text{if } C=0\\ N(C,i-1)+N(C-P\_i,i-1) & \quad otherwise \end{cases} $$

I'm not certain how to prove the correctness of the algorithm. Especially because the assignment is about dynamic programming, and I can't find any repeated subproblems. The amount of money you will have will differ unless some of the different beers cost the same. I asked a fellow student who said the problem will always give overlapping subproblems.  The problem has also been talked about here (Making a recursive formula for finding amount of ways to spend money on beer), but I think my recursive formula is correct.

Sorry, if the question is unclear, or if I've done something wrong. It's the first time on stackexchange, and I think, this is the place to ask the question and not the mathmatics site.

# Answer
> 0 votes
I figured it out.

**Overlapping-subproblems:**

1. $P\_i == P\_{i\_1}$: If two beers has the same price it will give overlapping subproblems. The assignment thinks this is okay.
2. $P\_i == P\_{i-1}+P\_{i-2}$: If a collection of beer has the same price as another collection of beers they will end up with the same parameter $C$. Because every left call doesn't change the value of $C$ it will give overlapping subproblems.

**Proof of Correctness**

I thought I had to prove the algorithm through induction with a mathematical equation. This wasn't the case. I had to prove that simple base-cases would give the correct value, and that the recursive calls would get closer to the 1st and 2nd statement and prove that the algorithm would eventually terminate.

* Case 1: If $C = 0$, then $N(C,i)=1$
* Case 2: If $i = 0$ and $C!=0$, then $N(C,i)=0$ (Had to edit my formula. The assignment specified that you had to use all your money)
* and more...

---
Tags: dynamic-programming, recursion, correctness-proof
---


# Question
Title: If a connected graph has a bridge then it has a cut vertex
Is it true that if a connected graph has a bridge then it has a cut vertex?

In my point of view, I don't think it is true to consider that a graph having a cut edge will definitely have cut vertex.

Consider a graph with a single edge $uv$; if we remove this edge, the graph will get disconnected but if we remove $u$, the graph will be connected as a graph with the single vertex is still consider connected.

# Answer
> 3 votes
An edge $e=uv$ is a bridge in $G$ if there is no path between $u$ and $v$ in $G-e$.

In general, $u$ and $v$ are cut vertices, but there are some special cases you must treat with care.

(1) If $G \simeq K\_2$, then depending on the definition of *connectivity*, the $G-u \simeq K\_1$ might and might not be considered connected\*.

(2) There is another case in which you would not consider $u$ to be a cut vertex; An edge $uv$ is called a *pendant* edge if $\deg(u) = 1$. In this case, if $uv$ is a pendant edge and $\deg(v)\>1$, you would not typically call $u$ a cut vertex.

*Postlude*

All that being said, definitions in graphs are hard (case in point: Diestel). When we try to make definitions very general, special cases sometimes become absurd.

*Note*

*1*

* To address David Richerby's objection, $K\_1$ is considered *disconnected* when deriving connectivity from k-connectivity, in which you require the graph to have *more than $k$ vertices*. By that definition ("a 1-connected graph is called connected"), $K\_1$ is disconnected by having too few vertices.

*2*

To answer Thinker's follow-up question; since you wanted to know what to answer to a hypothetical exam question, I would do it this way:

Let $e = uv$ be a bridge. We have three cases:

1. $\deg(u), \deg(v) \> 1$. The statement is true.
2. $\deg(u) = 1, \deg(v) \> 1$. The statement is true, $e$ is a pendant.
3. $\deg(u) = \deg(v) = 1$. The statement is true if and only if $K\_1$ is considered connected.

---
Tags: graphs
---


# Question
Title: Can we approximate the number of possible witnesses for an NP language?
Assuming $L \in NP$, meaning that L could be verified by some $V(x,y)$, such that there exists a polynomial $P(X)$ such that $|y| \leq P(|x|)$ for every $x \in L$.

I was wondering - can I assume something about the possible witness space? My intuition says that this number is bounded by $O(2^{P(|X|)})$ (all possible subsets of a certain problem, all possible strings by the length at most $P(X)$ etc...)

Thanks

# Answer
The class of counting problems associated to languages in NP is called #P. More formally, $f:\mathbb{N}\rightarrow\mathbb{N}$ is in $\\#P$ if there exists a nondeterministic polynomial time Turing machine $M$ such that for all $x\in\Sigma^\*$, $f(x)$ is the number of accepting paths of $M$ on input $x$. This is equivalent to requiring the existence of a deterministic verifier $M(x,y)$ such that $f\_M(x)=\big|\big\\{y: M(x,y) \text{ accepts}\big\\}\big|$.

You ask, given a language in $NP$ with it's verifier $M(x,y)$, can we approximate $f\_M$? If the witnesses are of length $p(|x|)$ then obviously $0\le f\_M(x)\le 2^{p(|x|)}$, but without knowing more about $M$ then we can't really say anything else about $f\_M$. Note that computing $f\_M$ is harder than asking whether a witness exists (obviously if you could count then you could determine existence). In fact, counting is considered much harder, as demonstrated by Toda's theorem (given an oracle for counting, one could decide the entire polynomial hierarchy in polynomial time).

So how hard is approximating such functions, or (allow me to focus on a specific $\\#P$ complete language) how hard is it to approximate $\\#SAT(\varphi)$, the number of satisfying assignments of a given CNF. In these lecture notes by Jonathan Katz, a constant factor approximation is considered, i.e. an algorithm producing a number inside the range $\left\[2^{-k}\\#SAT(\varphi),2^k\\#SAT(\varphi)\right\]$ for some fixed $k\in\mathbb{N}$. They show that with high probability, given an oracle for regular SAT, one can produce such an approximation in polynomial time (the algorithm can also be strengthen to yield an $1\pm p^{-1}(|\varphi|)$ approximation). So while exact counting is considered much harder than $NP$, an $NP$ oracle is enough to approximate $\\#SAT$ with high probability.
> 2 votes

---
Tags: time-complexity, np
---


# Question
Title: Time Complexity: Intuition for Recursive Algorithm
I decide to learn more about dynamic programming, so I started reading the Dynamic Programming chapter from the CLSR book.

The first example problem presented there is Rod Cutting (15.1). Given a rod of length n and a list of prices for rods of any sizes figure out how to cut the rod so that the price of the pieces will be maximized (and one can only cut at even positions).

The first recursive algorithm presented there is the following

```
CutRod(p, n)
  if n == 0
    return 0
  q = -inf
  for i = 1 to n
    q = max(q, p[i] + CutRod(p, n -1))
  return q

```

n is the size of the rod and p an array that contains the prices.

I understand the algorithm, the problem I have is that I thought intuitively the time complexity of such an algorithm would be O(b^d) (where b is the branching factor and d the depth of the recursion tree) which would be O(n^n).

In the book the recurrence relation is presented: T(0) = 1 and T(n) = 1 + sum(j=0, n-1, T(j)) Then it is explained that the complexity following from this is O(2^n) which you can easily be seen by expand the recurrence relation.

How can I quickly see that my initial intuition was wrong? And in general when looking at a recursive algo how can I figure out weather the time complexity is O(b^d) or not.

# Answer
Based on the code you show there, your intuition is right.

However, it looks like there is a typo in the code and the next-to-last line should have been

```
  q = max(q, p[i] + CutRod(p, n-i))

```

i.e., `n-i` rather than `n-1`. Try to work through a proof of correctness, or through a few examples, to see why I say that. The running time analysis they show is for the corrected code, rather than the code with the typo, and then once you make that correction to the code, the recurrence relation they provide is correct.
> 2 votes

---
Tags: time-complexity, dynamic-programming, recurrence-relation
---


title: How does TLC check liveness properties?

text:
# Question
Title: How does TLC check liveness properties?
The paper "Model Checking TLA+ Specifications" published in 1999 explained how TLC (Temporal Logic Checker) checks safety properties written in TLA+ developed by Lamport. At that time, TLC did not yet check liveness properties.

Today, TLC is able to check liveness properties. I want to know:

* What liveness properties is TLC able to check?
* How does TLC check liveness properties?

Any references?

# Answer
> 9 votes
Presumably it can check any "liveness" property that that can be formulated in LTL. A "liveness" property is typically described as a property stating that "something good eventually happens". This is usually contrasted to a "safety" property which states that "nothing bad ever happens". See e.g. Slide 20 of this SPIN tutorial. Basically, a basic safety property will look like $\square P$ which states that it is always the case that $P$ holds, e.g. the temperature is always below boiling. A basic liveness property might look like $\lozenge Q$ which states that $Q$ eventually happens, e.g. eventually the HALT state is reached.

A seminal paper is An Automata-Theoretic Approach to Automatic Program Verification. The idea is to use a Büchi automaton, which is just a normal finite state automaton with a notion of acceptance that works on infinite words. The key result is that you can turn an LTL formula into a Büchi automaton that accepts exactly the computations that satisfy the LTL formula. A model checker takes your specification and produces a Büchi automaton, then it takes the LTL constraint, negates it, and produces a Büchi automaton for it. Finally, it intersects the two Büchi automata and endeavors to show that the resulting automaton accepts nothing, i.e. describes the empty language. It does this by conceptually (and to a large extent actually) enumerating all the states. In practice, the state space is way too large to be completely enumerated and this is why model checkers are not theorem provers.

So what's the issue with "liveness" properties that would cause them not to be included from the beginning? To check (the failure of) $\square P$ in a model checker is straightforward. You simply check $P$ for each state. If $P$ ever fails to hold, then you've found a counter-example to $\square P$. On the other hand, checking $\lozenge Q$ requires producing a trace that will never hit a state satisfying $Q$. There are two ways this could happen. First, we could reach a final state without ever going through a state satisfying $Q$. This is straightforward to check. Second, we could enter an infinite loop without ever reaching a state satisfying $Q$. To check this, we need to check if we reach a state that this particular trace has been to before without ever passing through a state satisfying $Q$.

It's the "this particular trace" that is problematic. For safety properties, it is enough to visit each state. *How* you get to a state for the most part doesn't matter. You'll want to keep track of which states have been visited to avoid (potentially infinite) repeated work, but it doesn't matter which trace visited a state. For liveness properties, it is not enough to know that *some* trace has visited a state. You need to know if *this* trace has visited that state. The upshot is that checking a safety property just requires enumerating the reachable states, while checking a liveness property requires cycle detection. Of course, there are linear-time algorithms for calculating strongly connected components. Due to the sheer number of states, transcribing textbook algorithms is often not adequate. You can see an indication of some of the issues here. As far as I can tell from the source code and that page, TLC does just do Tarjan's algorithm, but this interacts poorly with distribution (i.e. liveness checking is not supported in the distributed mode) and with symmetry reduction techniques to reduce the state space. It is also just inherently slower than checking safety properties.

---
Tags: formal-languages, reference-request, formal-methods, model-checking, tlaplus
---


# Question
Title: Can a weaker version of the Halting Problem be solved?
I've been learning about the Halting Problem and the proof that it is undecidable in its general case. The proof that it cannot be solved generally goes something like this:

1. Assume that some machine $H$ exists that can solve the halting problem on a given machine $A$ with input $x$ ($H$ determines whether the machine $A$ halts on input $x$).
2. Now build a machine $Q$ which consists of $H$ and an extra component that takes in the output of $H$ and functions by never halting whenever $H$ returns "true", and halts whenever $H$ returns "false".
3. Then feed into $Q$ *itself* as both its given machine and the machine's input. Now, what does $Q$ return? If the machine $H$ inside $Q$ determines that the system halts, thereby returning "true", then $Q$ does not halt, as outlined above. However, if $H$ determines that $Q$ does not halt, then it does halt, as outlined similarly above. Therefore $H$ cannot exist.

I understand how this prevents any machine from existing that provides a general solution to the halting problem for any input, but does it also prevent solutions to certain smaller problems as well?

Specifically, could there theoretically be a 1000-state or larger Turing machine which can solve the halting problem for all Turing machine inputs with 50 states or fewer (the specific values aren't relevant)? That way, the machine cannot be input itself as a parameter, and the contradiction above would not be relevant.

To be clear, I'm not asking whether such a machine could be *feasibly built*, but rather whether is it theoretically possible for such a program to exist that solves the problem for machines smaller than a certain limit?

# Answer
If you define $H$ to take a 50-or-fewer state Turing machine (TM) and an arbitrarily large input, then if you can build a universal Turing machine (UTM) in 50-states, then you can simulate $H$ by encoding its description as well as its input into the input of the 50-state UTM.

If $H$ merely needs to tell whether any 50-or-fewer state TM halts *with an empty tape as input*, then, since there are finitely many such TMs, it can simply have a table hard-coded into it. Producing this table may be difficult, but it "exists" in the usual mathematical sense.1 Given values of the Busy Beaver function, we can actually easily describe one potential implementation. Simply simulate the input TM up to the appropriate Busy Beaver number of steps, and if it hasn't halted by that point, then it never halts.

To give an idea of how difficult it is to produce the aforementioned table, just note that we can write a program that terminates only if ZFC set theory is inconsistent. Gödel's incompleteness theorem then implies that if ZFC is consistent, then it is not possible to prove that that program doesn't halt. The upshot of this is after a certain number of states (and not a very large number) even if you were outright *given* the (correct) TM to do what you describe, you could not prove that it was correct in ZFC. (This isn't particular to ZFC. ZFC is just the formal system that is usually considered the "foundation" of mathematics. Other formal systems will merely have different cut-offs.) In other words, even if you were given the answer, you could not convince yourself that it was correct.

1 Actually, it exists in a stronger sense than many mathematical objects in that we can actually enumerate all the Turing machines and at some point the correct one will come up. We just won't realize it when it happens, in general.
> 6 votes

---
Tags: turing-machines, undecidability, halting-problem
---


title: To prove 4-SAT CNF is NP-complete

text:
# Question
Title: To prove 4-SAT CNF is NP-complete
To answer the question below,

4-SAT: Given a formula in Conjunctive Normal Form, where each clause contains exactly 4 literals, does it have a satisfying truth assignment?

I was going to prove that 4-SAT is in NP-complete. But I saw that the way to prove CNF-SAT is in NP-complete is a bit different to the way of proving 4-SAT is in NP-complete.

Is it sufficient that I just answer that question by proving 4-SAT is in NP-complete?

Thanks in advance!

# Answer
In order to prove that 4-SAT is NP-complete, you need to prove that it is in NP and that it is NP-hard.

## Prove 4-SAT $\in$ NP

Given an instance of 4-SAT and an answer that evaluates to TRUE, it's pretty quick to verify.

## 4-SAT is NP-hard

Like the comments suggested, reduce 3-SAT, which is a known NP-complete problem, to 4-SAT:

Assume that you are given an instance of 3-SAT. The goal is to convert it in polynomial time into an instance of 4-SAT in such a way that the answer is preserved.

Take each clause $(x \lor y \lor z)$ and turn it into $(x \lor y \lor z \lor a) \land (x \lor y \lor z \lor \neg a)$, where $a$ is arbitrarily set.

* If any $(x \lor y \lor z)$ clause is satisfied, then $(x \lor y \lor z \lor a) \land (x \lor y \lor z \lor \neg a)$ will also be satisfied. If the instance of 3-SAT is satisfiable, then the new instance of 4-SAT is satisfiable.
* If $(x \lor y \lor z \lor a) \land (x \lor y \lor z \lor \neg a)$ is satisfied, then $(x \lor y \lor z)$ must also be true because $a$ is opposite of $\neg a$. If the new instance of 4-SAT is satisfiable, then the instance of 3-SAT is satisfiable.
> 9 votes

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


# Question
Title: Does minimum cost flow problem work for real valued edge weights/costs?
I'm a bit confused about the definition of the Minimum Cost Flow problem, in terms of the edge cost (or weight) values.

I don't remember a integral requirement on the cost/weight values for the edges when first learning the problem. But when I start to look for implementations, most algorithmic code I found require the edge weights to be integers. (I haven't delved into Simplex or LP related code though). For example, in here, and here, weight values are defined as `int cost;` and `typedef long long int price_t; ... price_t _cost; // cost of arc;`, resp.

Boost Graph Library (BGL) seems to allow different weight types through C++ templates, but the examples in documentation are using integer weight values. The only use of floating weight values I can find is a SO question about the errors associated with using the floating points (https://stackoverflow.com/questions/35746487/). Google optimization tool also has a bug/feature request for floating point weight values, which is closed immediately stating it only supports `int64`, currently.

Is there a fundamental reason behind this lack of real valued weights in mincost flow implementations (such as complexity)? That is, is the real valued Min Cost Flow more difficult or impossible to solve, or is this just a coincidence?

# Answer
In the case of the Ford-Fulkerson algorithm, yes, it's due to complexity. When the edge weights/capacities aren't integers, things get really annoying, really fast.

If you allow all real numbers, you can end up with an instance that doesn't terminate. Normally, you augment paths until you can no longer do so. An irrational capacity value could allow the algorithm to continually find smaller and smaller augmenting paths.

Uri Zwick came up with a good example to show this:

> Consider the flow network shown on the right, with source $s$, sink $t$, capacities of edges $e\_1$, $e\_2$ and $e\_3$ respectively $1$, $r=(\sqrt{5}-1)/2$ and $1$ and the capacity of all other edges some integer $M \ge 2$. The constant $r$ was chosen so, that $r^2 = 1 - r$. We use augmenting paths according to the following table, where $p\_1 = \> \\{ s, v\_4, v\_3, v\_2, v\_1, t \\}$, $p\_2 = \\{ s, v\_2, v\_3, v\_4, t \\}$ and $p\_3 = \\{ s, v\_1, v\_2, v\_3, t \\}$.
>
> Note that after step 1 as well as after step 5, the residual capacities of edges $e\_1$, $e\_2$ and $e\_3$ are in the form $r^n$, $r^{n+1}$ and $0$, respectively, for some $n \in \mathbb{N}$. This means that we can use augmenting paths $p\_1$, $p\_2$, $p\_1$ and $p\_3$ infinitely many times and residual capacities of these edges will always be in the same form. Total flow in the network after step 5 is $1 + 2(r^1 + r^2)$. If we continue to use augmenting paths as above, the total flow converges to $\textstyle 1 + 2\sum\_{i=1}^\infty r^i = 3 \> + 2r$, while the maximum flow is $2M + 1$. In this case, the algorithm never terminates and the flow doesn't even converge to the maximum flow.

(Wikipedia)

The Stoer-Wagner algorithm will work with non-integer capacities, and so will Simplex/LP algorithms.
> 4 votes

---
Tags: network-flow
---


# Question
Title: Average Case Analysis for finding max in array with duplicated element
I've read some posts about counting the number of assignment inside code of finding the maximum value in array like this:

```
FindMax(L):
   n = len(L)
   max = L[1]
   for i = 2..n:
      if (max < L[i])
          max = L[i] (**)
   return max

```

According to this post and post, it's about the array that elements are strictly distinguish. So if the array contains values may be duplicated *(for example, elements are integer in range \[1, m\], m = 3, with any length of array)*, how could we calculate the number of (\**) will be executed in average case?

# Answer
Let us consider the following distribution: each array element is chosen independently and uniformly from $\\{1,\ldots,m\\}$. Let us denote by $I\_i$ the indicator variable for the event that ( \** ) gets executed for the $i$th element (so $I\_i = 1$ if ( \** ) gets executed, and $I\_i = 0$ otherwise). Linearity of expectation shows that the expected number of times that (\**) gets executed is $$ \sum\_{i=2}^n \Pr\[I\_i\]. $$ (This uses the fact that $\mathbb{E}\[I\_i\] = \Pr\[I\_i\]$.)

It remains to compute the probability of $I\_i$. If $A\[i\] = j$ then (\**) happens iff $A\[1\],\ldots,A\[i-1\] \in \\{1,\ldots,j-1\\}$, which happens with probability $\bigl(\tfrac{j-1}{m}\bigr)^{i-1}$. Therefore $$ \Pr\[I\_i\] = \sum\_{j=2}^m \frac{1}{m} \left(\frac{j-1}{m}\right)^{i-1}. $$ In total, we get $$ \sum\_{i=2}^n \Pr\[I\_i\] = \sum\_{j=2}^m \frac{1}{m} \sum\_{i=2}^n \left(\frac{j-1}{m}\right)^{i-1}. $$ You take it from here.
> 1 votes

---
Tags: runtime-analysis
---


# Question
Title: Serializability and the Lost Update Problem
Serializability is the strongest consistency level with regard to the execution of two concurrent transactions T1 and T2. That is, if T1 and T2 independently change the application between consistent states, and a concurrent execution of T1 and T2 is equivalent to a serial execution of T1 and T2, then that concurrent execution results in a consistent state, after committing both transactions.

For example, the following concurrent execution (time advances to the right)

```
T1: w(a=1)         w(c=4)
T2:     w(a=2)w(b=3)

```

where `W(x=v)` sets (i.e., writes) `x` to the value `v`, is equivalent to the serial execution `T1;T2`, thus it is serializable and both transactions are committed.

However, it is clear that T2's write of `a` causes T1's write of `a` to be lost, i.e., we have a lost update despite serializability.

That is, **serializability ensures consistent states in face of concurrency, though it does not prevent lost updates**, which may have serious consequences (for example, imagine that T1 writes the correct delivery address of a VIP customer, and T2 writes the wrong address, T1 and T2 are run concurrently by different operators, who do not notice the mistake).

Is my statement correct about serializability and lost updates?

If it is correct then the table in "Isolation levels, read phenomena, and locks" in this wiki page can only be wrong with regard to serializability and lost updates.

If so, what other stronger consistency level ensures that there are no lost updates?

Thanks

# Answer
> 1 votes
You say:

> **serializability ensures consistent states in face of concurrency, though it does not prevent lost updates**

This is not true, since by definition the *lost update* is the phenomenon arising in presence of Write-write conflict, that is when a transaction B overwrites a value written by a transaction A *before the commit of A*. This operation *can* lead to a state which cannot arise from any serial execution of A and B.

Consider for instance, in your example, the case in which the transaction T2 is executed one hour after the transaction T1: this could happen in real life, the execution of the two transactions is serial, that is there is no interference between the two transactions, however the update is wrong since someone wrote a bad address. But this means bad data, not data base inconsistency in itself (in other words, you have a database inconsistent with the reality, but this has nothing to do with concurrency and transaction management, that are properties related to the execution of concurrent operations over the database).

# Answer
> 0 votes
The case above of transactions T1 and T2 is one of Dirty Writes, not of Lost Update. Let me explain what I have been learning regarding this phenomena (see paper A Critique of ANSI SQL Isolation Levels by Berenson et al, 1995).

I confounded these two phenomena because they are very similar when comparing the execution schedules of two concurrent transactions provoking each phenomenon. The trap is that both phenomena involve writes to the same data item in two transactions.

A Dirty Write happens when one transaction writes a data item, but does not finish (i.e., commit or abort) before another transaction writes the same data item in concurrency. Dirty writes are precluded in all databases, typically by putting a write (exclusive) lock as the data item is written, thus blocking other transactions trying to write the same data item until the one holding the lock finishes. This means that the schedule in this question (above) cannot happen in reality because T2 would block waiting for T1 to finish.

In contrast, a Lost Update happens when one transaction writes a data item and commits, then a second (concurrent) transaction writes the same data item based on a value of the data item read before the write of the first transaction, therefore if the second transaction commits the update of the first is lost. Lost Updates are avoided at isolation levels stronger than READ COMMITTED.

---
Tags: concurrency, database-theory
---


# Question
Title: How to apply a Hadamard gate to one qubit in a 2-qubit system?
**Edit:**

I've pinpointed that the difference between solutions occurs when I apply the $H$, up to there, the solutions match. So, perhaps it is better to phrase my question as: how to apply an $H$ gate to one qubit in a 2-qubit system?

**End Edit**

I have the following quantum circuit, and I need to calculate the values of the two qubits afterwards.

Now I know the values are:

* $\lvert \psi\_1 \rangle = \frac{1}{\sqrt{2}}(\lvert 0 \rangle+\lvert 1 \rangle)$
* $\lvert \psi\_2 \rangle = \lvert 0 \rangle$

It's pretty simple to see, and I checked them with a simulator just to be sure.

The trouble I'm getting into is when I try to express this as a two qubit system.

As I understand it should be as follows:

$$\lvert \psi\prime \rangle=M\lvert \psi \rangle=\frac{1}{\sqrt{2}}(\lvert 00 \rangle+\lvert 10 \rangle)$$

Where $\lvert \psi\prime \rangle$ is the state after the circuit is complete, $\lvert \psi \rangle = \lvert 00 \rangle$ is the initial state, and $M$ is the matrix representing the combined effect of all the gates of the circuit.

Now, I calculate $M$ as follows:

$$M=\frac{1}{\sqrt{2}}(I\otimes X)\begin{bmatrix}I&0\\0&X\end{bmatrix}(I\otimes X)(H\otimes I)$$

I wrote the $CNOT$ matrix in block matrix form here, and extracted the $\frac{1}{\sqrt{2}}$ from $H$ to the beginning.

$$\begin{align}M&=\frac{1}{\sqrt{2}}\begin{bmatrix}X&0\\0&X\end{bmatrix}\begin{bmatrix}I&0\\0&X\end{bmatrix}\begin{bmatrix}X&0\\0&X\end{bmatrix}\begin{bmatrix}I&I\\I&-I\end{bmatrix} \\ &=\frac{1}{\sqrt{2}}\begin{bmatrix}X&0\\0&I\end{bmatrix}\begin{bmatrix}X&0\\0&X\end{bmatrix}\begin{bmatrix}I&I\\I&-I\end{bmatrix} \\ &=\frac{1}{\sqrt{2}}\begin{bmatrix}I&0\\0&X\end{bmatrix}\begin{bmatrix}I&I\\I&-I\end{bmatrix} \\ &=\frac{1}{\sqrt{2}}\begin{bmatrix}I&I\\X&-X\end{bmatrix}\end{align}$$

Now, plugging $M$ back into the first equation...

$$\begin{align}\lvert\psi\prime\rangle &=\frac{1}{\sqrt{2}}\begin{bmatrix}I&I\\X&-X\end{bmatrix}\lvert\psi\rangle \\ &=\frac{1}{\sqrt{2}}\begin{bmatrix}1&0&1&0\\0&1&0&1\\0&1&0&-1\\1&0&-1&0\end{bmatrix}\begin{bmatrix}1\\0\\0\\0\end{bmatrix}\\\&=\frac{1}{\sqrt{2}}\begin{bmatrix}1\\0\\0\\1\end{bmatrix}\\\&=\frac{1}{\sqrt{2}}(\lvert 00\rangle + \lvert 11\rangle)\end{align}$$

Which is *not* the correct solution. Where am I at fault?

# Answer
The problem is in the order of the transformations. The first transformation you apply in the circuit is $I\otimes X$, whereas in the computation of $M$ it is actually the last. Recall that the rightmost operator is the first to act on the state (matrix multiplication is not commutative).

Fixing that we obtain:

$$ M=(H\otimes I)(I\otimes X)CNOT(I\otimes X) = \begin{bmatrix} H & 0 \\ 0 & H \end{bmatrix} \begin{bmatrix} X & 0 \\ 0 & X \end{bmatrix} \begin{bmatrix} I & 0 \\ 0 & X \end{bmatrix} \begin{bmatrix} X & 0 \\ 0 & X \end{bmatrix}= \begin{bmatrix} H & 0 \\ 0 & H \end{bmatrix} \begin{bmatrix} X & 0 \\ 0 & X \end{bmatrix} \begin{bmatrix} X & 0 \\ 0 & I \end{bmatrix}= \begin{bmatrix} I & I \\ I & -I \end{bmatrix} \begin{bmatrix} I & 0 \\ 0 & X \end{bmatrix}= \begin{bmatrix} I & X \\ I & -X \end{bmatrix} $$

Now applying $M$ on $|00\rangle$ will yield the right result.
> 2 votes

---
Tags: quantum-computing
---


# Question
Title: Impact of Polynomial Time Algorithm for an NP Complete problem on Complexity Theory
Assuming (hypothetically) someone proves $P=NP$ by providing a polynomial time algorithm for a $NP-Complete$ problem the Polynomial Hierarchy collapses.

What are the other (important) questions that are still left in complexity theory in respect to the remaining complexity classes?

If possible can someone help with a link where it might have been answered already (which I am guessing it might be) is perfectly fine too.

# Answer
If P=NP, then it follows that P=co-NP, and NP=NP-complete (i.e. there are no NP-intermediate problems, which are in NP but not NP-complete).

But there are plenty of other divisions in the hierarchy which might still hold, and might not. P=NP wouldn't necessarily tell us anything about this.

On the higher end of things, how does NP relate to PSPACE? It's entirely possible that they're the same (only if P=NP: if P≠NP, they're definitely different), in which case all the classes in the middle (such as PP, which uses a probabilistic Turing machine) are collapsed together too.

On the lower end, how does P relate to L (logarithmic space)? There are various classes between these ones too, such as NL (nondeterministic log space), and these might all be collapsed into a single class also.
> 3 votes

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


# Question
Title: In Hindley-Milner system, how can I prove that let id=\x.x in id id is well-typed?
I am trying to infer the type and prove that this is well-typed:

let $f =\lambda x.x$ in $f f$

Obviously the $f$ is the identity function, so it's the same as

let $id =\lambda x.x$ in $id$ $id$

I am trying to use these rules to infer the type, going bottom-up:

First I am using (T-LET') and on the left-hand side it's easy to show that $\lambda x.x$ is of type $\alpha \rightarrow \alpha$.

However, I have a trouble with the right hand side. Can someone please help me how to finish this?

# Answer
> 6 votes
If I understand you question correctly, you are wondering how the typing judgment $f : \forall \alpha. \alpha \to \alpha \vdash f\\;f : \beta$ can be proved, where $\beta$ is some (yet unknown) type.

As we are dealing with an application, the only rule that applies is T-App, so we end up with the following (partial) typing derivation, where $\gamma$ is yet another (unknown) type. $$ \dfrac{\dfrac{\dfrac{}{x : \alpha \vdash x : \alpha}} {\vdash \lambda x.x : \alpha \to \alpha} \quad\quad \dfrac{f : \forall \alpha.\alpha \to \alpha \vdash f : \gamma \to \beta \quad\quad f : \forall \alpha.\alpha \to \alpha \vdash f : \gamma} {f : \forall \alpha. \alpha \to \alpha \vdash f\\;f : \beta}} {\vdash let \\; f = \lambda x.x \\;\\; in \\;\\; f\\;f : \beta} $$

Now, to complete the two open branches of the derivation, the only possibility is to use the T-Var rule, which has two preconditions. Applying it in the left branch, you can easily see that $\gamma$ must actually be $\beta$. And similarly, applying the T-Var rule in the right branch, you learn that $\gamma$ (or rather $\beta$) must be an arrow type of the form $\delta \to \delta$. So in the end, you obtain the following derivation (omitting the "$f : \forall \alpha.\alpha\to\alpha \in f : \forall \alpha. \alpha \to \alpha$") for the second premise of the T-Let rule. $$ \dfrac{\dfrac{\forall \alpha.\alpha\to\alpha \subseteq (\delta \to \delta) \to (\delta \to \delta)}{f : \forall \alpha.\alpha \to \alpha \vdash f : (\delta \to \delta) \to (\delta \to \delta)} \quad\quad \dfrac{\forall \alpha.\alpha\to\alpha \subseteq \delta \to \delta}{f : \forall \alpha.\alpha \to \alpha \vdash f : \delta \to \delta}} {f : \forall \alpha. \alpha \to \alpha \vdash f\\;f : \delta \to \delta}$$

Note that the conclusion of the full derivation then becomes $\vdash let \\; f = \lambda x.x \\;\\; in \\;\\; f\\;f : \delta \to \delta$.

# Answer
> 4 votes
As a starting note, the rules are *syntax-directed*: there's only one rule for each language construct. This means that you can construct the typing proof from the bottom up, by always using the rule for the syntactic construct at the bottom of the program. The only uncertainty is what types to use. To do the type inference manually, use variables where you don't know what a type should be, and replace a variable by a type expression (which may itself contain other variables) throughout the derivation when you reach a point where you do know something about that variable. (This is called doing *unification* during type inference.)

The expression $\mathsf{let}\\; f = \lambda x.x \\;\mathsf{in}\\; f \\, f$ cannot be typed in the simply-typed lambda calculus since the two occurrences of $f$ need to have different types. It's a typical example of a program that requires polymorphism. This tells you that you'll need to make use of polymorphism: you'll need to apply the (T-Var') rule for the two occurrences of $f$ with different types, and you'll need to apply the (T-Let') rule in a way that allows using $f$ with different types.

When you write “$\lambda x. x$ is of type $\alpha\to\alpha$”, keep in mind that $\alpha$ is a variable which must be bound somewhere. In Hindley-Milner terminology, a variable in an environment has a *type scheme*. $\lambda x. x$ has the type scheme $\forall \alpha. \alpha\to\alpha$. You could choose to give it other type schemes, but this one is the most general (it's called the *principal type scheme* of the expression): all other type schemes $\tau$ for $\lambda x. x$ satisfy $\tau \sqsubseteq \forall \alpha. \alpha\to\alpha$.

The application of the (T-Let') rule that gives $\lambda x. x$ its most general type scheme is $$ \dfrac{\vdash \lambda x.x : \alpha\to\alpha \qquad f: \forall \alpha. \alpha\to\alpha \vdash f \\, f : \color{blue}{\tau'}} {\vdash \mathsf{let}\\; f = \lambda x.x \\;\mathsf{in}\\; f \\, f : \color{blue}{\tau'}} \textsf{(T-Let')} $$ for some type $\tau'$. To find $\tau'$, find a type derivation for the second premise. The expression is an application, so you have to apply the (T-App) rule. $$ \dfrac{f: \forall \alpha. \alpha\to\alpha \vdash f : \color{green}{\tau} \to \color{blue}{\tau'} \qquad f: \forall \alpha. \alpha\to\alpha \vdash f : \color{blue}{\tau'}} {f: \forall \alpha. \alpha\to\alpha \vdash f \\, f : \color{blue}{\tau'}} \textsf{(T-App)} $$ Each premise is a variable so you need to apply the (T-Var') rule. The first premise tells you that whatever $\color{green}{\tau}$ and $\color{blue}{\tau'}$ are, they must be equal, since $\color{green}{\tau} \to \color{blue}{\tau'} \sqsubseteq \forall \alpha. \alpha\to\alpha$. The second premise tells you that $\color{blue}{\tau'}$ must have the form $\color{red}{\tau''} \to \color{orange}{\tau'''}$, since $\color{blue}{\tau'} \sqsubseteq \forall \alpha. \alpha\to\alpha$. You thus have the derivation $$ \dfrac{\dfrac{\vdots}{\vdash \lambda x.x : \alpha\to\alpha} \qquad \dfrac{\dfrac{}{\Gamma\_1 \vdash f : \color{red}{\tau''} \to \color{orange}{\tau'''} \to \color{red}{\tau''} \to \color{orange}{\tau'''}} \qquad \dfrac{} {\Gamma\_1 \vdash f : \color{red}{\tau''} \to \color{orange}{\tau'''}}} {\Gamma\_1 \vdash f \\, f : \color{red}{\tau''} \to \color{orange}{\tau'''}}} {\vdash \mathsf{let}\\; f = \lambda x.x \\;\mathsf{in}\\; f \\, f : \color{red}{\tau''} \to \color{orange}{\tau'''}} $$ where $\Gamma\_1 = f: \forall \alpha. \alpha\to\alpha$ and $\color{red}{\tau''}$ and $\color{orange}{\tau'''}$ can be any types.

---
Tags: lambda-calculus, type-inference, typing, haskell
---


# Question
Title: Prove that Weighted Independent Set is NP Complete using Independent Set?
> **$k$-Weight Independent Set**
> Input: A vertex weighted graph $G=(V,E,w)$ and an integer $k$.
> Question: Is the a set $V'\subset V$ such that $V'$ is an independent set and $\sum\_{v\in V'} w(v) \geq k$?

Showing that this problem is in NP is trivial, but I'm suck on showing that $X \Longleftrightarrow Y$. The forward direction is simple I think.

$\Longrightarrow$ If you have a $k$-Independent Set, then we know that each node has a weight that is a natural number ( $\ge 1$ ), so the graph has weighted independent set of at least $k$.

But how would you show the reverse direction $\Longleftarrow$?

# Answer
You reduce to this problem quite easily from the Independent Set problem.

Given a graph $G=(V,E)$ and a natural number $k$ define a simple weight function $w:V\to\mathbb{R}$ by

$$\forall v\in V:w(v)=1$$

The output of the reduction is $\langle G'=(V,E,w),k\rangle$.

If $G$ has an Independent set $S$ of size at least $k$ then $S$ is an independent set in $G'$ and

$$\sum\limits\_{v\in S}w(v)=\sum\limits\_{v\in S}1=|S|\geq k$$

So, $G'$ has an independent set of weight at least $k$, as needed.

If $G'$ has an Independent set $S'$ such that

$$\sum\limits\_{v\in S'}w(v)\geq k$$

Then, observe that $S'$ is an independent set in $G$ also and

$$|S'|=\sum\limits\_{v\in S'}1=\sum\limits\_{v\in S'}w(v)\geq k$$

So, $G$ has an Independent set of size at least $k$, as needed.
> 2 votes

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


# Question
Title: Simple Representation of Matrices with the Given Equivalence Relationship
I'm currently working on an algorithm that requires me to come up with unique matrices. Two matrices are considered equivalent if one's rows and columns can be swapped to make it match the other. For example, $\begin{bmatrix} 0 & 0 \\ 1 & 1 \end{bmatrix} \equiv \begin{bmatrix} 1 & 1 \\ 0 & 0 \end{bmatrix} \not\equiv \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} \not\equiv \begin{bmatrix} 0 & 1 \\ 0 & 1 \end{bmatrix}$. I think it would be immensely helpful to find a nice way to represent each matrix so that equivalent matrices have the same representation. The best I could come up with is just making a list of the rows and columns and comparing them. For example, $\begin{bmatrix} 0 & 0 \\ 1 & 1 \end{bmatrix}=\>\\{R:((0, 0), (1, 1))\\}, \\{C:((0, 1), (0, 1))\\} $ $\begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}=\>\\{R:((0, 1), (0, 1))\\}, \\{C:((0, 1), (0, 1))\\}$ $\begin{bmatrix} 0 & 1 \\ 0 & 1 \end{bmatrix}=\>\\{R:((0, 1), (0, 1))\\}, \\{C:((0, 0), (1, 1))\\}$

but I feel like there's a better way because this looks messy. Any suggestions?

Edit: This is not always binary matrix. Numbers can range from 0-19.

# Answer
When you are dealing with binary matrices, this is the problem of graph canonization. There is no known polynomial-time algorithm for this problem, and determining whether it can be done in polynomial time is a famous open problem, but there are techniques that are often reasonably efficient in practice (e.g., Nauty). (The relationship is that every graph corresponds to a binary matrix, namely, it adjacency matrix, and versa.)

When you have non-binary matrices, you can think of this as a graph with labels on the edges. There are standard techniques for reducing this to the standard graph canonization problem, by converting each labelled edge to a small subgraph. See, e.g., Graph isomorphism problem for labeled graphs, On graph isomorphism for weighted graphs, What equivalence relation does this algorithm produce for an cyclic directed graph with labeled edges?.
> 1 votes

---
Tags: matrices
---


# Question
Title: Checking claim in paper "A Read-Only Transaction Anomaly Under Snapshot Isolation" by Alan Fekete et al
In the 2004 paper "A Read-Only Transaction Anomaly Under Snapshot Isolation" by Alan Fekete et al. (which can be found here and here) the authors state:

> We also note that any execution of T1 and T2 (with arbitrary parameter values) without T3 present will always act serializably.

I have tested this claim inside PostgreSQL, like this

```
create table variables (
    name char(1) not null,
    value integer not null
);
insert into variables values ('x', 0), ('y', 0);

T2: begin
T2: set transaction isolation level serializable;
T2: select * from variables where name = 'x'
T2: select * from variables where name = 'y'
T1: begin
T1: set transaction isolation level serializable;
T1: select * from variables where name = 'y'
T1: update variables set value = 20 where name = 'y'
T1: commit
T2: update variables set value = -11 where name = 'x'
Connection reset. Reconnect (Y/n):

```

but as shown, when executing the T2's update, this transaction is aborted (I know this because the client, in the case `pgcli`, disconnected), which means that the schedule was not serializable.

What is happening here? Is the authors claim wrong? Is it a bug inside PostgreSQL? Or most probably, I made some mistake I am not aware of?

Thanks

# Answer
The claim in the paper is true (I never doubt about it, but just wanted to know why) because only the dependencies between the reads and writes of concurrent transactions determine if these are serializable, but not their commits (nor their aborts, obviously).

In the example above, extracted from the paper's claim, the fact that PostgreSQL aborts T2 has nothing to do with serializability between T1 and T2, but only with some design decision in PostgreSQL that I ignore (if someone knows I, please write a comment to this answer).
> 0 votes

---
Tags: concurrency, database-theory, databases
---


# Question
Title: What does "AC0 many-one reduction" mean?
> What does *$\mathsf{AC^0}$ many-one reduction* mean?

I know about polynomial time reductions, but I'm not familiar with $\mathsf{AC^0}$ reductions.

# Answer
> 8 votes
An AC0 many-one reduction is a many-one reduction that can be implemented by an AC0 circuit. It's just like a polynomial-time many-one reduction, except that instead of requiring that the mapping takes polynomial time, we require that the mapping is in AC0.

David Richerby further explains: "AC0 is a very low-complexity class so it can be used, for example, to study reductions between logspace problems, which doesn't make sense with polytime reductions since, then, the reduction would be more powerful than the problem class being studied." For instance, if problems A,B can be reduced to each other with polynomial-time reductions, then you learn that their complexity can't be exponentially different (if one is polynomial, the other must be too), but it's possible that they still might be fairly different (polynomially different). If they can be reduced to each other with AC0 reductions, then this has stronger implications about their complexity (it has to be pretty similar).

# Answer
> 7 votes
The "what is" part of the question was succinctly answered by D.W.:

> An AC0 many-one reduction is a many-one reduction that can be implemented by an AC0 circuit. It's just like a polynomial-time many-one reduction, except that instead of requiring that the mapping takes polynomial time, we require that the mapping is in AC0.

I mentioned (in a comment) that AC0 many one reduction is normally understood to mean Dlogtime-uniform AC0 reduction. This implies that AC0 reductions are provably weaker than log-space reductions (and polynomial time reductions).

This is important for answering the implicit "why do we care about AC0" part of the question. Many complete problems stay complete under extremely weak notions of reduction, like Dlogtime many-one reductions (or even Immerman's quantifier-free projection reductions). However, Dlogtime many-one reductions are not closed under composition (and Immerman's quantifier-free projection reductions are hard to explain to the non-specialist), and they still don't capture the really extremely weak nature of typical reductions.

So AC0 many-one reductions are used as a reasonably weak (and provably so) notion of reduction, which still works with common notions that are sufficiently easy to explain. But it unfolds into quite a number of different notions, like *circuit classes* and the distinction between *uniform* and *non-uniform*, or like *many-one reductions* and hence *function classes*. Here, the devil is in the details, like really understanding Dlogtime-uniformity, or making sense of function classes for alternating Turing machines, given the fact that the logarithmic time hierarchy (LH) is equal to Dlogtime-uniform AC0. And even that non-uniform vs. P-uniform vs. Dlogtime-uniform issue is not as clear cut as one would hope, see the discussion in the answer here about details behind Algebra, Logic and Complexity in Celebration of Eric Allender and Mike Saks by Neil Immerman.

---
Tags: reductions, circuits
---


# Question
Title: Proving that Pre(L) is regular using automatas: Should I prove that Pre(L) is the semantic of the new automata?
Let $L$ be a regular language, and $Pre(L)$ be the set of all words that are prefix of some word in $L$. Prove that $Pre(L)$ is regular.

My proof:

> Let $M = (\Sigma, Q, \delta, q\_0, F)$ be an automata such that $\mathcal{L}(M) = L$ and $Q' = \\{ q \in Q \ | \ (\exists q\_f, w \ | \ q\_f \in F \ \wedge \ w \in \Sigma^{\*}: \[q, w\] \mapsto^{\*} \[q\_f, \lambda\] ) \\}$, that is, $Q'$ is the set of all states that have a path to a final state of $M$.
>
> Hence, $M' = (\Sigma, Q', \delta, q\_0, Q')$ is an automata such that $\mathcal{L}(M') = Pre(L)$. QED.

Is the last step right or should I now proof that the semantic of $M'$ is in fact $Pre(L)$?

# Answer
If you are unsure whether it is right, yes, you should prove it! This is a good general principle. If you are unsure whether or why a particular step is correct, there's a good chance a reader will be unsure, too -- so prove it in more detail until there is no doubt.
> 1 votes

---
Tags: formal-languages, regular-languages, automata, closure-properties
---


# Question
Title: Finding the most efficient paths to cover an area from multiple starting locations
I'm looking to design an algorithm for a problem I have, and was hoping there may be someone that could provide some insight on where to start.

In my picture above, the grid is the area they needs to be explored by the circles. Each cell is a unit of work, so currently I've got lat/lng coordinates for the exact center of each of the grid cells. The goal is to visit every cell in the grid. Circles must start in their home locations, and must end in their home locations.

In my current algorithm (SUPER simple, but it works), I'm simply taking the center coordinates of each of those grid cells, splitting them up into lists (number of lists = number of circles), then adding the home location to the beginning and end of each of those lists. As you can imagine, this leads to some very inefficient routes.

The grid areas can vary wildly, as well as the location of the "Homes", so an algorithm that simply determines the best possible route, by minimizing the total distance travelled for each circle to complete the entire task, is what I'm looking for.

I'm thinking this may be some sort of variant of Dijkstra's algorithm, where the distances between all the different center points as well as the home locations are all calculated before determining the lowest possible solution. Where my understanding kind of falls apart is Dijkstra's algorithm is shortest path from A to B, whereas this algorithm is more of a "shortest path from A to A, given that an individual circle can complete X many units of work, with the end goal of the entire grid area being completed".

With this algorithm, I'm picturing that it would take into account the return trip, since its part of the calculated distance I'm trying to minimize, so it would try to complete units of work that are on the way back home.

Any insight or guidance is greatly appreciated. Thank you.

# Answer
> 4 votes
If I understand your description correctly, there is no polynomial-time algorithm that solves each instance optimally. Intuitively, if you had an efficient algorithm for your problem, we could use it to find a Hamiltonian cycle (i.e., a cycle that visits each vertex exactly once) in a grid graph which is known to be NP-complete \[1\]. (The paper also contains hardness results for various "grids"; see whether some of the definitions actually capture your concept of a "grid").

In other words, we can reduce the problem of determining whether a grid graph has a Hamiltonian cycle to your problem where we have single circle.

You should not be discouraged too much by such a result though. It is perfectly possible you can do considerably better than your current algorithm, i.e., perhaps maybe even most of your instances are actually quite simple to solve. For instance, you could look at various metaheuristics and consider using (say) a genetic algorithm to find a good solution.

---

\[1\] Arkin, Esther M., Sándor P. Fekete, Kamrul Islam, Henk Meijer, Joseph SB Mitchell, Yurai Núñez-Rodríguez, Valentin Polishchuk, David Rappaport, and Henry Xiao. "Not being (super) thin or solid is hard: A study of grid Hamiltonicity." Computational Geometry 42, no. 6-7 (2009): 582-605.

# Answer
> 3 votes
You are looking for a vertex cycle cover for the grid graph, with some added constraints: we are given $k$ vertices $v\_1,\dots,v\_k$ (the "home locations"), and the $i$th cycle must include the vertex $v\_i$; and we want to minimize the length of the longest cycle (or maybe the total lengths of all the cycles, I'm not clear).

Unfortunately, as Juho explains, your specific problem is NP-hard, so you shouldn't expect any algorithm that is efficient on the worst case, scales to large graphs, and always gives the optimal solution. So, you're left with looking for heuristics or approximation algorithms, or accepting that your algorithm might take exponential time in the worst case.

You might consider a local search algorithm, e.g., simulated annealing or something similar. One could imagine that a particular state assigns each vertex in the graph to the "circle" that will visit it. To make a small change, you might pick one vertex $v$ that are assigned to assigned to some circle (say circle A) and is adjacent to a vertex assigned to another circle (say circle B), and change $v$ so it is assigned to circle B; then recalculate the Hamiltonian cycles for A and B, and use that to score how good this modified solution is. (How to calculate Hamiltonian cycles? You might in turn use local search for that, or any other standard heuristic for finding Hamiltonian cycles.) Then apply standard local search algorithms to this neighbor relation; e.g., hill climbing or simulated annealing. That's just an idea -- I have no idea whether it will work well or not. Your best bet is probably to try several different approaches like this and see how well they work in practice.

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


# Question
Title: Matrix multiplication in recurrent neural networks
I was looking at a tutorial for recurrent neural networks in Python, and I have a question in regards to multiplying matrices of different sizes. Specifically, why does S\[t\] have 100 elements in it?

> `s[t] = np.tanh(self.U[:,x[t]] + self.W.dot(s[t-1]))`

Earlier in the tutorial, the author lists the dimensions for each variable:

> \begin{aligned} x\_t & \in \mathbb{R}^{8000} \\ o\_t & \in \mathbb{R}^{8000} \\ s\_t & \in \mathbb{R}^{100} \\ U & \in \mathbb{R}^{100 \times 8000} \\ V & \in \mathbb{R}^{8000 \times 100} \\ W & \in \mathbb{R}^{100 \times 100} \\ \end{aligned}

From how I understand the above line of code, it multiplies U by x\[t\] and adds it to the product of W and s\[t-1\], then computes tanh for each element.

Sources like this say that you cannot add matrices of different dimensions, however that seems to be what is happening here (because multiplication is just repeated addition). In fact, it seems that U is 2D and x\[t\] is 1D. How are these added? Also, how is the sum of the two products then 100 elements?

# Answer
> 1 votes
Matrix-by-matrix multiplication is very different from scalar-by-scalar. It has no connection to repeated addition, and in fact isn't even commutative: it's entirely possible that $AB \neq BA$. It's only called multiplication because it has some similar properties to repeated addition of scalars.

Matrix multiplication requires that the *inner dimensions match*. Nothing more, nothing less. You can multiply an (a×b) matrix by a (b×c) matrix, for instance, and the result is an (a×c) matrix. For the full details, Wikipedia has a good summary.

In addition, that code isn't adding or multiplying $U$ and $x\[t\]$. Rather, it's removing one dimension from $U$, taking only the columns (or rows depending on your definitions) which correspond to 1s in $x\[t\]$.

---
Tags: neural-networks, matrices
---


# Question
Title: is it necessary to cover all the verticies in eular path?
I was going through graph theory and came across the term Euler path or some people prefer Euler trail as vertices can repeat.

According to the definition from wiki (https://en.wikipedia.org/wiki/Eulerian\_path), Euler path is defined as under

> In graph theory, a Eulerian trail (or Eulerian path) is a trail in a graph which visits every edge exactly once.

Following are the conditions for Euler path,

> An undirected graph (G) has a Eulerian path if and only if every vertex has even degree except 2 vertices which will have odd degree, and all of its vertices with nonzero degree belong to a single connected component.

So as per the definition, I need to cover all edges in a connected graph with non zero degrees.

The same information is stated here at geeks for geeks(https://www.geeksforgeeks.org/eulerian-path-and-circuit/).

so if I need to only consider vertices with non zero degrees then graph (G)can be disconnected?

Note: These are the other information I collected from the wiki page

1)Finite connected graph (with vertices of even degree except 2 or 0 with the odd degree) will have a Euler path. 2)But Euler path can also be present in the disconnected graph as shown in the following picture

3) Doubt does following graph have Euler path,

My answer ,No as all vertices are not in same connected component.

# Answer
It really comes down to your definition of an Euler trail. The one I'm familiar with is similar to the one on Wikipedia:

> An *Euler trail* is a trail (path that allows repeats) that uses every edge exactly once.

With this definition, an Euler trail doesn't have to touch every vertex: if there's a vertex with no edges, the Euler trail doesn't have to go anywhere near it.

However, if there's a vertex with positive degree, and another vertex with positive degree, and they're not (weakly) connected, then there can be no Euler trail. Because if you use the edges on one, there's no way to reach the edges on the other.
> 5 votes

---
Tags: algorithms, graphs
---


# Question
Title: Given a random number generator rand5() generate gen7()
Given a pseudo random number generator rand5() that generates a random integer in the set \[0,1,2,3,4\], how would someone use this to generate a function rand7() that outputs \[0,1,2,3,4,5,6\] with equal probability.

I was thinking of approaching it this way: reduce the problem to generate number from 0 to 6 using a coin.

```
We can represent [0,1,2,3,4,5,6] using bit-wise from 000 to 111.
Selecting each bit from LSB to MSB can be done using tossing a coin.
However, if we continue in this fashion from LSB to MSB then we
can get all bits as 111 which is decimal 7. So, in the case of MSB
if we get 1 then discarding it and starting again should give
the result? Right?

```

Reducing the problem from rand5() to coin can be done in this way: if the number is 0,2 then we can consider it as head and getting 1,3 can be considered as tail.

Is my solution right?

# Answer
> 3 votes
(For some reason, this old question came up first)
rand5()+rand5()\*5 would give numbers 0-24, each with a probability of 1/25. You could use the first 21 of these to return 0-6 with equal probabililty.
Likewise, rand2()+rand2()\*2+rand2\*4) gives numbers 0-7, each with a probability of 1/8. You could use the first 7 of these to return 0-6 with equal probability.
In pseudocode:

```
function rand7a() {
  do { rand7 = rand5() + rand5()*5 } while (rand7 >= 21);
  return rand7 mod 7;
}
function rand7b() {
  do { rand7 = rand2() + rand2()*2 + rand2()*4 } while ( rand7 == 7);
  return rand7;
}

```

EDIT: Elaboration:
1st approach:
rand2() in binary is 000 or 001 with 50-50 probability.
rand2()\*2 is 000 or 010 with 50-50 probability.
rand2()\*4 is 000 or 100 with 50-50 probability.
So the sum is binary xxx where each x has a 50-50 probability of 0 or 1; so each 000 to 111 has a probablilty of 1/8.

2nd approach: going through each of the 8 possibilities of the 3 rand2()s:
0+0+0 or 1+0+0 or 0+2+0 or 1+2+0 or 0+0+4 or 1+0+4 or 0+2+4 or 1+2+4
all of these with equal probablilty 1/8.

# Answer
> 3 votes
It can work, but there is no need for an intermediate step: just convert from base 5 to base 7, picking the least significant base-7 digit. The algorithm is as follows:

1. Use rand(5) to generate a and b; let n = 5 * a + b.
2. If n \>= 21, discard n and go back to step 1, else go to step 3.
3. Return n mod 7.

---
Tags: algorithms, pseudo-random-generators
---


title: CFG where u has same number of 1s as v

text:
# Question
Title: CFG where u has same number of 1s as v
$$L=\\{uv\in\\{0,1,2\\}^\*\mid u\in\\{0,1\\}^\*,v\in\\{1,2\\}^\*, \text{ and }u\text{ has the same number of 1s as }v\\}.$$

Here is my attempt solution, but it is not completely correct, any hint is appreciated (not sure how I can ensure that $u$ and $v$ to have the same number of 1).

\begin{align} S &\rightarrow S\_l \mid S \mid S\_r\\ S\_l &\rightarrow 0S\_l \mid 1S\_l \mid S\_l0 \mid S\_l1 \mid \varepsilon \\ S\_r &\rightarrow 1S\_r \mid 2S\_r \mid S\_r1 \mid S\_r2 \mid \varepsilon \end{align}

# Answer
The idea is to extract a pair of 1s one by one, so the key grammar is

\begin{align} S&\rightarrow S\_01S1S\_2 \\ S&\rightarrow S\_0S\_2 \end{align}

where $S\_0$ represents $0^\*$ and $S\_2$ represents $2^\*$.
> 2 votes

# Answer
This answer refers to the question as originally stated, in which $L$ is defined as follows: $$ L = \\{uv \in \\{0,1,2\\}^\* \mid u,v \in \\{0,1\\}^\*, \text{and $u$ has the same number of $1$s as $v$}\\}. $$

Your language is regular, since it consists of all words over $\\{0,1\\}$ with an even number of $1$s.
> 0 votes

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


title: How to interpret $BPP^{NP}$

text:
# Question
Title: How to interpret $BPP^{NP}$
I have taken one basic class in complexity and understand the fundamentals. E.g. P, NP, NP-hardness. But I can't understand how to interpret $BPP^{NP}$. I believe it means "BPP with an NP oracle" but how should I interpret that?

Does this mean that members of this class are problems for which there exist randomized algorithms that run in polynomial time but which can call another algorithm that can solve any problem in NP in constant time? If so, how is this different from just having an algorithm that can solve any problem in NP in constant time?

# Answer
You should think of this as the class of problems who lie in $BPP$, but in a new (relativised) world where the model of computation is slightly different. Turing machines now have an additional query tape and three new special states, $q\_{\text{query}},q\_{\text{yes}},q\_{\text{no}}$. Upon entering the state $q\_\text{query}$, if the contents of the query tape is $s\in\Sigma^\*$, then the machine goes to either the yes or no state depending on whether or not $s\in SAT$.

The key point is that nothing changes in the BPP part, the only thing different is the computational model. This actually changes everything, but luckily we can integrate the oracle to the standatd Turing machine without changing basic notions such as time/space complexity. This allows us to talk about classes such as $P, NP, BPP$ in the new model (we can define them in exactly the same way).

Note that we don't have a general definition of $A^B$ for two complexity classes $A, B$. We use this notation when $A$ has a natrual extension to the relativised (oracle) world.

Additionally, to define our model of computation precisely we need to specify exactly what is the oracle (we need to define the transition function from $q\_{\text{query}})$. Thus, we can't have an algorithm solve every NP problem in a single step, we need to choose a problem in order to specify a well defined behavior for the machine. It is not hard to show that for every two NP complete languages $L,L'$ it holds that $\mathsf{BPP^L=BPP^{L'}}$. So when we write $BPP^{NP}$ we mean languages having a BPP machine with access to a SAT oracle (or any other NP complete language of your choosing). In cases where the definition of $A^B$ might depend on the exact choosing of the oracle, statements involving $A^B$ usually hide a universal quantifier on the oracle, and should be read as "for all $o\in B$ ...".
> 4 votes

---
Tags: complexity-theory
---


# Question
Title: Language L and its complementary both not recursively enumerable?
Is it possible to proof for a Language L and its L-complemented to be both not recursively enumerable? Can be useful to consider the (Ld) diagonalization Language? thank you.

# Answer
AS you know the number of Turing machines is countable while the number of subsets of sigma star is uncountable , so definitely the number of languages that are not recursively enumerable is uncountable. If the complement of all such languages is recursivelu enumerable, so their complement should have Turing machine, that this means that the number of languages that is not recursively enumerable but their complement is recursively enumerable, is countable,

so we have so many languages that both the language and its complement is not recursively enumerable, and the set of such languages is uncountable.
> 3 votes

# Answer
By the Rice-Shapiro theorem, both these sets are not recursively enumerable.

$$ \begin{array}{l} L= \\{ n \ |\ \mathrm{dom}(\varphi\_n) \mbox{ is finite} \\} \\ \bar L= \\{ n \ |\ \mathrm{dom}(\varphi\_n) \mbox{ is infinite} \\} \end{array} $$

If you want languages instead of sets, you can adapt the above to sets of encodings of Turing machines.

Another language which is not RE and has a non RE complement is

$$ L = \\{0\langle M \rangle \ |\ M \mbox{ halts on empty input}\\} \cup \\{1\langle N \rangle \ |\ N \mbox{ does not halt on empty input}\\} $$

Indeed, it is easy to reduce the halting problem to both $L$ and $\bar L$, and then prove that neither is RE.
> 2 votes

---
Tags: computability
---


title: NP-completeness of vertex cover

text:
# Question
Title: NP-completeness of vertex cover
> Show that the following language is NP-complete $$ L = \\{ \langle G,k \rangle \mid \text{$G$ is a graph with a set $S$ of $k$ vertices hitting every edge of $G$}\\}. $$

I know I should reduce the problem to SAT. But how I can do it?

# Answer
A related, but different problem is **Independent Set**: it asks for a set of $k$ vertices that hits each edge *at most* once (instead of *at least* once).

A simple reduction from 3-SAT to Independent Set is as follows:

1. For each clause, we take a clique on $3$ vertices (i.e., a triangle). Each vertex of this triangle corresponds to specific literal appearing in a clause. E.g., a clause $(x\_1\vee \neg x\_2 \vee x\_3)$ would have vertices corresponding to literals $x\_1,\neg x\_2,x\_3$.
2. Whenever two vertices correspond to conflicting literals, we make those vertices adjacent. E.g., all vertices corresponding to $x\_1$ are made adjacent to all vertices corresponding to $\neg x\_1$.

We now ask whether an independent set of size $m$ (the number of clauses) exists.

Note that since there is a partition of the graph into $m$ cliques (created in step 1), the size of a maximum independent set is at most $m$ (one vertex from each clique). If there is an independent set of size $m$, then there is a satisfying assignment: such an independent set much select exactly one vertex from each clique, and which vertex is selected tells us which variable is used to satisfy that clause. This gives a satisfying assignment because the edges added in step 2 ensure that no conflicting literals are selected. Conversely, it is easy to see how a satisfying assignment corresponds to an independent set of size $m$.

This reduction should give you a good idea of how to approach the case for Vertex Cover (but this will require some slight modifications).
> 1 votes

---
Tags: np-complete, proof-techniques, satisfiability, 3-sat
---


# Question
Title: What is Follow(X) when there's a rule, A -> XBCD where First(B) and First(C) contain empty, but First(D) do not
I have a question about follow sets.

Suppose there's a rule,

> A -\> XBCD
>
> B -\> $\beta$ | $\epsilon$
>
> C -\> $\gamma$ | $\epsilon$
>
> D -\> $\delta$

What is Follow(X)?

Is it (First(B) - $\epsilon$) $\cup$ (First(C) - $\epsilon$) $\cup$ First(D) = {$\beta$ , $\gamma$, $\delta$ } ?

# Answer
> 0 votes
I am answering my own question. As @rici made a comment, I misunderstood the meaning of Greek letters in the discussion of Follow sets in the book I am reading. Greek letters mean sequences of symbols.

Using the definition,

> If there is a production B-\> $\alpha$ A $\gamma$, then First ($\gamma$) \- {$\epsilon$} is in Follow (A)

First(BCD) is in Follow(X) where

> A -\> XBCD

BCD corresponds to $\gamma$ in the definition.

---
Tags: parsers
---


# Question
Title: Crossover operator in genetic algorithms in Neural Networks
I am developing a neural network that is trained using a genetic algorithm. The neural network is a multilayer perceptron using $\tanh$ as its activation function. Currently, the genotype of the neural network is by its weights. I used the method of making a connectivity matrix and linearizing it according to this paper: http://sci2s.ugr.es/keel/pdf/keel/articulo/NN-Garcia05.pdf

What is a good crossover method for this? I've tried uniform crossover but it is too disruptive as there is no improvement whatsoever. Single-point crossover is discouraged as I have read, so what should I use?

# Answer
> 1 votes
I don't think you should.

But, supposing the structure is the same in all individuals, you could take a random set of nodes from one, and the rest from the other, and just keep all out edges from nodes you selected.

Another alternative is taking a random set of edges from one, and the rest from the other.

A third alternative is to take the first $\ell$ layers from the first individual and the last $L-\ell$ layers from the second individual.

As you can see, there are very many approaches, and I don't think any of them will be satisfactory, but I hope you try and see for yourself.

---
Tags: neural-networks, genetic-algorithms
---


# Question
Title: Can an FO formula with infinite length be expressed with an infinite set of finite formulas?
I'm confused as to why we can't write formulas of infinite length in FO. For example, to express reachability, I understand the proof that there cannot be a single formula for it, but it is expressible with a set of formulas?

Since any formula has an equivalent formula in CNF, if we transform a formula of infinite length to some CNF, and then break the conjunct up into clauses and put them in a set, is it then expressed with an infinite set of finite formulas?

On the other hand, can an infinite set of finite formulas be joined by conjunctions to obtain an equivalent formula of infinite length?

# Answer
You are getting at infinitary (first-order) logic. While a well-defined (and natural, and extensively studied) concept, it is quite different from ordinary first-order logic. Before diving into more detail, let me point out the main issue with your suggestion:

> There are "infinitely long" expressions which aren't just infinite conjunctions of finite expressions.

That is to say, your idea

> Since any formula has an equivalent formula in CNF, if we transform a formula of infinite length to some CNF, and then break the conjunct up into clauses and put them in a set, is it then expressed with an infinite set of finite formulas?

is incorrect. One way to see this is with the **compactness theorem**. For example, suppose I had a set $\Gamma$ of (finitary) first-order sentences which expressed *connectedness*. Then consider the expansion of $\Gamma$ to include sentences saying "$c$ is at distance at least $n$ from $d$," for each natural number $n$, where $c$ and $d$ are new constant symbols. By the usual compactness argument, this has a model, but (the reduct of) this model isn't a connected graph; contradiction.

The usual manipulations we perform with finitary formulas don't behave intuitively in general when we look at "infinitary" formulas, and in fact infinitary logic (see below) is a very different beast from its finite counterpart.

---

Having said what infinitary logic *isn't*, let me end by saying a couple sentences about what infinitary logic *is*.

For a start, let's look at the simplest nontrivial example: $\mathcal{L}\_{\omega\_1,\omega}$. This is smallest class containing all first-order formulas, closed under (a) quantifiers and (b) *countably infinite* conjunctions and disjunctions. This logic is much stronger than first-order logic - for example, connectedness (in the language of graphs) is definable by an $\mathcal{L}\_{\omega\_1,\omega}$-formula, namely

$$\forall x,y\[\bigvee\_{n\in\mathbb{N}}\exists z\_1,...,z\_n(z\_1=x,z\_n=y, z\_1Ez\_2E...Ez\_n)\].$$ This is a relatively simple infinitary formula, and there are much more complicated ones we can consider; there is a rich (and non-collapsing) hierarchy of infinitary formulas, and in fact many *fragments* of $\mathcal{L}\_{\omega\_1,\omega}$ of mathematical interest (see e.g. this paper for a good starting point).

We can go beyond $\mathcal{L}\_{\omega\_1,\omega}$ by either allowing longer Boolean combinations, or infinitely long blocks of quantifiers, but as we go further up the hierarchy of infinitary logics things get progressively much nastier. $\mathcal{L}\_{\omega\_1,\omega}$ is quite abstract, but still "concrete" enough to be relevant outside of infinitary logic - see e.g. the notion of a Scott sentence, which is useful in computability theory, classical model theory, and set theory.

There are several texts on infinitary logic; I recommend Marker's recent book as a good starting point, and Barwise's old book for a more in-depth treatment of the "local" flavor.
> 3 votes

# Answer
Assuming "FO formula" means a formula in first-order logic (aka a well-formed formula), it's part of the definition that a formula has to be finite. The set of well-formed formulas is defined by induction, and induction can only give you a finite formula. See https://en.wikipedia.org/wiki/First-order\_logic#Formulas.

---

Also: If you had an 'infinite formula' in first-order logic (whatever that means; let's assume it is somehow meaningful) that contained infinitely many variables, as Derek Elkin explains, there might not be a way to translate it to an infinite CNF formula that is equivalent (it's not obvious whether that should be possible, and it would presumably depend on how you defined "infinite formula").
> 1 votes

---
Tags: logic
---


title: Longest repeated substring

text:
# Question
Title: Longest repeated substring
I am trying to solve a problem- Longest repeated substring in a string. Firstly, I built a suffix tree that takes O(n) time and then I traversed the suffix tree to find the deepest internal node. I am not sure whether traversing in a suffix tree would be O(n) or not?

These are the properties of a suffix tree-

1. A suffix tree will contain n leaves which are numbered from 1 to n.
2. Each internal node (except root) should have at least 2 children.

If each internal node can have more than 2 children,How can I say that number of nodes in a suffix tree is O(n)? So, How will the complexity be O(n)?

Here is the code that I have written for traversal. I am aware that this platform is language independent so I have added the relevant comments along with my code.

```
struct StNode
{
    string str;
    StNode* child[256];
};
void lrs(StNode* t,string s,string &res)
{
    if(leafNode(t)){    //leafNode means no child
        string str=t->str;
        s.erase(s.length()-str.length());   //erasing the leafNode's string
        int k=s.length();
        if(k>res.length())   res=s;
        return;
    }
    for(int i=0;i<256;i++){     //traversing through all childs
        if(t->child[i]!=NULL){
            string str=t->child[i]->str;
            lrs(t->child[i],s+str,res);
        }
    }
}

```

# Answer
Yes, the number of nodes in the suffix tree is $O(n)$.

Here's how you could infer that. The suffix tree can be constructed in $O(n)$ time. There's no way to construct a tree with strictly more nodes than that, since it takes at least $\Omega(1)$ time per node you construct; so from the fact that the running time of the suffix tree algorithm is $O(n)$, you can conclude that its output must have size $O(n)$, i.e., the suffix tree must have $O(n)$ nodes.

Here's another way you could have inferred that. There are $n$ leaves. Also, each internal node has at least two children. In such a tree, the number of internal nodes is at most the number of leaves, so in this case, there are at most $n$ internal nodes and $n$ leaves. It follows that the number of nodes in the tree is at most $2n = O(n)$.

This information is actually found in the Wikipedia page on suffix trees, which explains that any suffix tree has at most $2n$ nodes. In the future, before asking a question here, please check standard resources, such as Wikipedia and a textbook.

It follows that the tree can be traversed in $O(n)$ time.
> 0 votes

---
Tags: algorithms, strings, substrings, suffix-trees
---


# Question
Title: Why is $L := \{b^2a^nb^ma^3|m,n \geq 0\}$ a regular language?
(Pre-note: I'm learning Theory of Computation on my own, so bear with me if I'm saying something wrong/stupid.)

> Why is $L := \\{b^2a^nb^ma^3\mid m,n \geq 0\\}$ a regular language?

This question appeared in a problem set, whose answer is the following:

> The language is regular. Indeed, it can be expressed by the regular expression $\mathcal{R} := b^2a^\*b^\*a^3$.

---

However, I (think I) can find a contradiction using the *pumping lemma*.

Consider $s = xyz = b^2 a^{p-3}b^1a^3$. (I assume one can take a specific string from the language.)

Clearly, $\forall p\>3, s \in L$, and $|s|\geq p$, the *pumping length*.

Take $x = b^2$, $y=a^{p-3}b^1$, $z = a^3$. (I assume one can take specific values for $x, y, z$).

The *pumping lemma* says that if $L$ is regular, there is a number $p$ (*pumping length*) where, if $s \in L \wedge |s| \geq p$, $s$ may be split into three pieces, $s = xyz$, satisfying the conditions:

1. $|y| \> 0$,
2. $|xy| \leq p$,
3. $\forall i \geq 0, xy^iz \in L$.

Conditions (1) and (2) are fulfilled. As for condition (3) ...

$xy^iz = b^2(a^{p-3}b^1)^ia^3$

For $i=0$, $xy^0z = b^2a^3 \in L$.

However, for $i = 2$, $xy^2z = b^2(a^{p-3}b)(a^{p-3}b)a^3$, and taking $p=4$, it is clear that $xy^2z = b^2ababa^3 \notin L$.

Thus, we find a contradiction (because $xy^2z \notin L$) and $L$ is not regular.

(Could you help understand where is the fallacy here?)

# Answer
The pumping lemma says that there is *some* $p$ such that every string longer than $p$ can be split in *some* way that can be pumped.

You've shown that there's some $p$ and some splitting that doesn't work but (since the language is regular), that just means you chose the wrong $p$ and/or the wrong splitting of your string.

In fact, the value of $p$ is the number of states in the smallest automaton that accepts the language (plus one, I think). The language you give is going to need about eight or nine states, so your $p$ was too small. However, that doesn't much matter. Given the string $b^2a^{p-3}ba^3$, we can split it as $x=b^2$, $y=a$, $z= \[\text{the rest}\]$ and now $xy^iz\in L$ for all $i\geq 0$, as the pumping lemma claims. Sure, some other splits don't work, but that one does and the lemma just claims that *some* split works.

Remember: to show that a language is non-regular using the pumping lemma, you need to show that, for *every* $p$, there is at least one word of length at least $p$ in the language such that *every* valid splitting as $xyz$ results in $xy^iz\notin L$ for at least one $i$.
> 2 votes

---
Tags: regular-languages, finite-automata, regular-expressions, pumping-lemma
---


# Question
Title: Finding pair of non-adjacent cliques in a dense graph
I have a graph consisting of about 5000 vertices, with density around 0.5. I'm trying to find two disjoint 6-cliques, which are not connected by an edge. I have tried bruteforcing this, by firstly looking for any 6-cliques, and then checking pairs for being non-adjacent. However, although it finds a lot of 6-cliques it is too slow to find a non-adjacent pair. Is there a faster way to do this?

# Answer
Here is one approach:

1. Find any 6-clique, call it $C$.
2. Find all vertices that aren't adjacent to any vertex in $C$. Mark them red.
3. Find a 6-clique among the red vertices.

How long will this take? Let's analyze the running time of each step.

1. You should be able to find a 6-clique by randomly sampling $2^{15}$ possible ways to choose 6 vertices and checking whether it forms a clique; a random collection of 6 vertices has a $1/2^{{6 \choose 2}} = 1/2^{15}$ probability of being a clique, so you're likely to find one in this way after about $2^{15}$ trials. There are faster ways to find a 6-clique, but this will already be very fast.
2. This can be done in $6 \times 5000$ operations, i.e., very fast.
3. Now you have the problem of finding a 6-clique in a smaller graph. How many red vertices do you expect to have? If you pick a vertex at random, then it has a $1/2^6$ probability of being red. Therefore, we expect about $(5000-6)/2^6 \approx 78$ red vertices. It is very likely that a 6-clique exists among them, as there are ${78 \choose 6} \approx 2^{28}$ possible ways to choose a subset of 6 nodes, and each one has about a $1/2^{15}$ chance of being a 6-clique. You can find a 6-clique among the red vertices in the same way as before (randomly choosing a collection of 6 red vertices and checking to see if they form a clique). This takes about $2^{15}$ trials.

So all in all you expect this to be successful, and to take about $2^{16}$ trials, where each trial is very fast. So this algorithm should be very fast. There are probably ways to optimize it further, by using standard algorithms for finding a clique more efficiently than brute force, but I'd guess this should already be adequate, and it has the advantage of being easy to implement.
> 2 votes

---
Tags: graphs
---


# Question
Title: Explanation about the condition for connectivity in Erdos Reyni model
I am currently studying the **Erdos-Reyni** model, the $G(n,p)$ model to be specific.

Its easy to understand that all graphs with $m$ edges have generating probability of $p^{m}(1-p)^{n(n-1)/2 - m}$ where p is the probability that there is an edge between a pair of vertices.

What I am not able to understand is the following:

Almost every graph in $G(n, 2ln(n)/n)$ is connected. In other words, As $n$ tends to infinity, the probability that a graph on $n$ vertices with edge probability $p = 2ln(n)/n$ is connected, as $n$ gets very large.

Any idea how to get this?

# Answer
If a graph is not connected then there must be a set $S$ of vertices not connected to its complement. Furthermore, we can assume that $|S| \leq n/2$. For a given set $S$, the probability that $S$ is not connected to its complement is $$ (1-p)^{|S|(n-|S|)} \leq e^{-p|S|(n-|S|)}. $$ The union bound shows that the probability that some such $S$ exists is at most $$ \epsilon := \sum\_{k=1}^{n/2} \binom{n}{k} e^{-pk(n-k)} = \underbrace{\sum\_{k=1}^{n/4} \binom{n}{k} e^{-pk(n-k)}}\_{\epsilon\_1} + \underbrace{\sum\_{k=n/4+1}^{n/2} \binom{n}{k} e^{-pk(n-k)}}\_{\epsilon\_2}. $$ When $k \leq n/4$, we have $n-k \geq (3/4)n$ and so $$e^{-p(n-k)} \leq e^{-(3/4)pn} = \frac{1}{n^{3/2}}.$$ Using the bound $\binom{n}{k} \leq n^k$, we get $$ \epsilon\_1 \leq \sum\_{k=1}^{n/4} n^k \cdot n^{-(3/2)k} = \sum\_{k=1}^{n/4} \frac{1}{n^{k/2}}. $$ We can estimate this by considering separately $k=1$, $k=2$, and $k \geq 3$: $$ \epsilon\_1 \leq \frac{1}{\sqrt{n}} + \frac{1}{n} + \sum\_{k=3}^{n/4} \frac{1}{n^{3/2}} \leq \frac{1}{\sqrt{n}} + \frac{1}{n} + \frac{n}{4} \cdot \frac{1}{n^{3/2}} = O\left(\frac{1}{\sqrt{n}}\right). $$ When $n/4 \< k \leq n/2$, we have $n-k \geq n/2$ and so $e^{-p(n-k)} \leq e^{-pn/2} = 1/n$. Using the sharper upper bound $\binom{n}{k} \leq (\frac{en}{k})^k$, we get $$ \epsilon\_2 \leq \sum\_{k=n/4+1}^{n/2} \left(\frac{en}{k}\right)^k \cdot \frac{1}{n^k} = \sum\_{k=n/4+1}^{n/2} \left(\frac{e}{k}\right)^k. $$ The summands $(e/k)^k$ are decreasing, and so $$ \epsilon\_2 \leq \frac{n}{4} \left(\frac{4e}{n}\right)^{n/4} \leq \left(\frac{4e}{n}\right)^{n/4-1} = O\left(\frac{1}{\sqrt{n}}\right), $$ since when $n \geq 6$, the exponent is at least $1/2$.

Putting everything together, we get that the probability that the graph is not connected is at most $$ \epsilon = O\left(\frac{1}{\sqrt{n}}\right). $$

Using more refined arguments, one can show that when $p = \frac{\ln n + c}{n}$ for constant $c$, the probability that $G(n,p)$ is connected tends to $e^{-e^{-c}}$. Moreover, in a certain precise sense, the only obstacle to connectivity (whp) is isolated vertices.
> 2 votes

# Answer
Hint: Try to compute the probability of a node not connected to at least $\frac{n}{2}$ of vertices: $$P= (1-\frac{2\ln(n)}{n})^{n/2}$$ If $n$ goes to $\infty$, we have: $$P = \frac{1}{e^{\ln(n)}} = \frac{1}{n} \rightarrow0$$

Hence, the probability of each node is connected to at least $\frac{n}{2}$ of nodes goes to $1$. You can get help from this to proof the connectivity.
> 0 votes

---
Tags: algorithms, graphs
---


# Question
Title: Minimum number of moves required to transfer items from source bins to target bins?
I have a set of source bins, each with some number of items, and a set of target bins. I want to move all of the items from the source bins to the target bins, using the minimum number of moves. Each move can move any number of items from one source bin to one target bin.

The bins do not have the same size, but the total capacity of source and target bins is the same.

I came up with a few possible formulations for this problem:

1) as a problem of finding the sparsest solution to an underdetermined system of linear equations with variables in $\mathbf N\_0$. Lots of literature about this but very sparse (no pun intended) on $\mathbf N$.

2) I could also describe it as finding the min cost flow of a bi-partite network $G=\\{U,V,E\\}$, fully connected, with $U$ supply nodes (source bins) and $V$ demand nodes (target bins) with $|U|$ not necessarily equal to $|V|$, edge cost given by

$$c\_{uv} = \begin{cases} 1 &\text{if link is used}\\ 0 &\text{otherwise} \end{cases}$$

and the total demand equal to the total supply.

However, the cost is non-linear so usual min cost flow algorithms do not work here.

3) and I also considered the Split Deliveries Vehicle Routing problem with vehicles (source bins), vehicle capacity (size of source bins) customer demand as the target bins, and a space where all inter customer location distances are 1.

All of these are NP-Hard problems.

My questions:

What is the complexity of this problem? Can it be solved in polynomial time? Is there any research literature covering this problem?

# Answer
> 1 votes
The problem is NP-hard, by reduction from the partition problem.

Here is the reduction. Consider an instance of the partition problem, namely, integer $x\_1,\dots,x\_n$. Create $n$ source bins and 2 target bins, with $x\_i$ items in the $i$th source bin. Set the capacity on the target bins to $(x\_1+\dots+x\_n)/2$. Then there is a solution to your movement problem that uses exactly $n$ moves, if and only if there is a solution to the partition problem.

We can also show your problem is strongly NP-hard, by reduction from 3-partition.

As a result, you should not expect to find any efficient algorithm that always gives the optimal answer and scales to large problems. You might try looking for heuristics, approximation algorithms, or algorithms that could be exponential time in the worst case but hopefully are often fast in practice. For instance, you could look into simulated annealing, integer linear programming, and approximation algorithms for bin packing.

---
Tags: graphs, optimization, combinatorics
---


# Question
Title: Reducing closed TSP to open with fixed starting vertex
I have implemented a branch and bound algoritm for finding a Hamiltonian cycle in my software, but I actually need to find a shortest route from fixed vertex through all verticies ending at any of them.

As far as I understood, I can reduce closed-cycle TSP to open-cycle with fixed starting point by adding dummy vertex. But I can't find or figure out the weights of the edges of this vertex.

How can I do this?

# Answer
> 2 votes
Add two dummy vertices, $d\_1,d\_2$. Add edges of weight 0 from all other vertices to $d\_1$. Add an edge of weight 0 from $d\_1$ to $d\_2$. Add an edge of weight 0 from $d\_2$ to your fixed starting vertex. (If you need a complete graph, each missing edge can be replaced by an edge with weight $+\infty$ or some very large positive weight.) Then any Hamiltonian cycle in the resulting graph will correspond to a Hamiltonian path in the graph that starts at your fixed vertex.

---
Tags: traveling-salesman
---


# Question
Title: Is every reduction function $f \in O(n)$?
I have no detailed questions actually. My question is about a (maybe possible) generalization for reductions.

We defined reduction as following (If I translate a term false please correct me.):

$ L\_1, L\_2 \in \\{0,1\\}^\* $ two languages.

One may reduce the language $L\_1$ to $L\_2$, if there is a total function:

$f: \\{0,1\\}^\* \rightarrow \\{0,1\\}^\* $ with the following properties:

1. $ \forall w\in \\{0,1\\}^\* :w\in L\_1 \Leftrightarrow f(w) \in L\_2 $
2. The function is via a Turing Machine $M\_f$ computable.

My question is the following:

If one may can reduce a language to another, then one may can construct a function from a language to another. It means intuitively for me that the reduction function has to go over $|L\_1| = n$ operations. Which means that the reduction function is computable in $O(n)$. But I am not sure about any generalization. I mean does it imply that:

$f$ is a reduction function $\Rightarrow f\in O(n)$

# Answer
> 2 votes
I'm not sure exactly what you mean. In essentially all interesting cases, $L\_1$ is infinite, so you can't say that $|L\_1|=n$. Second, the function $f$ is a function from strings to strings, so it doesn't make sense to ask if it's $O(n)$ because $O(\cdot)$ is a class of functions from numbers to numbers.

However, you're most probably asking if all reductions are in $\mathrm{TIME}\[O(n)\]$, i.e., if they can all be computed in linear time. They can't.

By the time hierarchy theorem, for any $r\>s$, there are languages in $\mathrm{TIME}\[O(n^r)\]$ that are provably not in $\mathrm{TIME}\[O(n^s)\]$. So, consider any problem $X$ that is **P**-complete under polynomial-time reductions. We must have $X\in\mathrm{TIME}\[O(n^s)\]$ for some $s$. By the time hierarchy theorem, there is some langauge $Y\in\mathrm{TIME}\[O(n^{s+1})\]\setminus\mathrm{TIME}\[O(n^s)\]$. Since $X$ is **P**-complete and $Y\in{}$**P**, there must be some polynomial-time reduction $Y\to X$. However, this reduction cannot run in linear time. If the reduction did run in linear time, there would have to be some $k$ such that it transforms every length-$n$ instance of $Y$ into an instance of $X$ with length at most $kn$ (a function running in linear time can only produce linearly much output). But, then, we would be able to decide $Y$ via the reduction in time $$O(n) + O((kn)^s) = O(n) +O(n^s) =O(n^s)\\,,$$ contradicting our choice of $Y\notin\mathrm{TIME}\[O(n^s)\]$.

Note that, in general, if we're talking about computability rather than complexity, we only care that the reduction is computable – we usually don't care about its time or space complexity at all. However, in other contexts, we do care about linear-time reductions, for example in proving problems hard under the exponential time hypothesis.

# Answer
> 0 votes
$O(n)$ does not appear anywhere in the defintion. Thus the functions are not required to be computable in this time.

I am not sure what you mean by $|L\_1| = n$ -- the language will in general be of infinite cardinality.

There are, however, restricted kinds of reductions that additionaly require the reduction function to be of a certain runtime. For example, say you have two languages of quadratic time complexity. Then a reduction of exponential complexity would be of little interest, because it could itself compute things more complex than the languages.

So when you look at languages from a time complexity class $O(g)$, then you normally want the reduction to be in $O(g)$, too. But this must be stated in the defintion.

---
Tags: turing-machines, reductions
---


# Question
Title: Computational complexity of Bell numbers
I've been recently dealing with a problem which, when worst case is considered, results in exploration of $B\_{n}$ options, where $B\_{n}$ is th $n^{th}$ Bell number. I am trying to rigorously prove, that dealing with $B\_{n}$ possible solutions results in exponential (or worse?) computational complexity (in terms of $n$). If possible, I would also like to prove this in the context of NP-hardness.

As I am new to this, any hints would be greatly appreciated.

So to summarize, given an algorithm, prove that it will take exponential (or worse) time in terms of $n$, when $n$ corresponds to $B\_{n}$.

Thank you very much.

# Answer
> 3 votes
Yes, the $n$th Bell number is exponential in $n$. Wikipedia lists the following relation:

$$B\_{n+1} = \sum\_{k=0}^n {n \choose k} B\_k.$$

It follows that

$$B\_{n+1} \ge B\_n + n B\_{n-1} \ge n B\_{n-1},$$

so

$$B\_{n+1} \ge n(n-2)(n-4)\cdots \ge (n/2)^{n/4},$$

which is exponential in $n$.

---

This fact has little or nothing to do with NP-hardness; it is just unconditionally true, regardless of whether P = NP or not.

If you have a problem for which every algorithm takes $\Omega(B\_n)$ time, then the problem is not in P; it requires exponential time. It might or might not be in NP.

If you have a problem where the obvious algorithm takes $\Theta(B\_n)$ time, that proves nothing (maybe there is some other algorithm you haven't thought of yet that is faster).

# Answer
> 2 votes
There is an easy lower bound for $B\_n$.

Let $\[n\] = \\{1,2,\dots,n\\}$. Pick some $k$-element set $S \subseteq \[n\]$. Form the set $X = \\{\\{x\\} \mid x \in S\\}$ of singletons from $S$. There are $k^{n-k}$ ways to add the remaining $n-k$ elements of $\[n\]$ to the sets in $X$, and these form distinct partitions of $\[n\]$. (Not all partitions of $\[n\]$ can be obtained in this way, so this is only a lower bound.)

So $B\_n \> k^{n-k}$. When $n$ is even, a nice value for $k$ is $k = n/2$, and then $B\_n \> (n/2)^{n/2}$. The best bound is when $k = \lceil n/\lg n\rceil$ but it is a bit messier to write out.

---
Tags: complexity-theory, combinatorics
---