# Question
Title: Find which vertices to delete from graph to get smallest largest component
Given a graph $G = (V, E)$, find $k$ vertices $\\{v^\*\_1,\dots,v^\*\_k\\}$, which removal would result in a graph with smallest largest component.

I assume for large $n = |V|$ and large $k$ the problem is difficult (NP-hard), but I am interested in small values of $k$ ($k \in \\{1, 2, 3, 4\\}$).

For $k = 1$, I think it is possible to find best vertex $\\{v^\*\_1\\}$ to remove by performing single depth-first-search of the graph (i.e., checking articulation points).

For $k = 2$, it would be possible to find best vertices $\\{v^\*\_1, v^\*\_2\\}$ by performing $n$ depth-first searches (each of them for graph $G\_i = G / \\{v\_i\\}$). A similar approach could be applied in the case $k \> 2$.

I wonder if there is any better solution than that.

(Related: counting the minimum number of vertices without necessarily enumerating them)

# Answer
The problem you are describing is known as Component Order Connectivity in the field of *vulnerability measures of graphs*. The decision version of the problem is as follows:

> **Component Order Connectivity**:
>
> *Input:* Graph $G = (V,E)$, integers $k$ and $\ell$
>
> *Question:* Does there exist a set of vertices $X \subseteq V$ of size at most $k$ such that the size of the largest component of $G - X$ is at most $\ell$?

The problem is obviously NP-complete since it generalizes vertex cover; the case when $\ell=1$ is vertex cover. Hence the problem cannot be fixed parameter tractable when parameterized by $\ell$ (unless $FPT = W\[1\]$). The problem is also known to be $W\[1\]$-hard when parameterized by $k$. Hence, we have to resort to algorithms with an exponential running time in $k+\ell$.

Very interesting question. For input $G,k,\ell$, a brute force approach would be:

```
branching(G,k,l):
    Find a connected set of vertices D of G of size l+1
    if no such D exists:
            return True // no component of size > l
    for v in D:
        if branching(G-v,k-1,l):
            return True
    return False

```

The algorithm runs in time $(\ell + 1)^k \cdot n^2$.

Observe that any yes instance $G,k,\ell$ of the problem has treewidth, and indeed pathwidth at most $k+\ell$. This can be observed by seeing that taking a deletion set $X$ of size at most $k$ yields a graph $G-X$ where every connected component has size at most $\ell$. Hence, a valid path decomposition is simply to construct one bag for each of the components in $G-X$ and then add all of $X$ to every bag. It follows that any yes instance has $|E(G)| \leq n(k+\ell)$.

A related problem has been studied in the past under the name Graph Integrity, or Vertex Integrity to distinguish the vertex deletion version and the edge deletion version:

> **Vertex Integrity**:
>
> *Input:* Graph $G = (V,E)$, integer $p$
>
> *Question:* Does there exist a set of vertices $X \subseteq V$ such that $|X| + \max\_{D \in cc(G-X)}|D| \leq p$?

That is, the sum of the deletion set and the size of the maximal component should be minimized. This problem is also NP-hard. See, e.g.,

* Clark, L.H., Entringer, R.C., Fellows, M.R.: Computational complexity of integrity. J. Combin. Math. Combin. Comput 2, 179–191 (1987)
* Fellows, M., Stueckle, S.: The immersion order, forbidden subgraphs and the complexity of network integrity. J. Combin. Math. Combin. Comput 6, 23–32 (1989)
> 10 votes

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


# Question
Title: Is the language $0^n 1^n 0^n$ recursive?
I have to find out whether the language $J\_1=\\{0^n1^n0^n \mid n \in \mathbb{N}\\}$ and $J^{c}\_{1}$ is recursively enumerable.

I already know that $J\_1$ is RE, because I have found Turing machine which accepts $J\_1$. I would also like to prove this for $J^{c}\_{1}$ by using the following theorem: $J\in RE \wedge J^{c} \in RE \Leftrightarrow J \in Rec$.

So I have to prove that $J\_1 \in Rec$. I have already tried but I am stuck. Can anybody please help me?

# Answer
> 3 votes
Explaining intuitively why this language is recursive is easy: it's almost trivial to write a computer program in a high-level programming language (e.g. Java, C) that decides this language. Since TMs can simulate high-level languages, you get the result.

If you need a concrete TM that decides this language, try the following:

First, erase a 0 and go right until you encounter 1. Replace this 1 with some new symbol $X$. Go back left, and repeat the process until you are out of 0s on the left. Then go back right and do the same thing with the $X$s and 0s on the right.

If, at any point, something "unexpected" happens, (e.g. you run out of 1s, or have too many 1s), then reject. Otherwise you will end up with an empty tape, at which point you can accept.

---
Tags: formal-languages, computability
---


title: defining lambda expressions

text:
# Question
Title: defining lambda expressions
I am studying for my exam and I wanted to do some extra excercises, but I have some problems with solving :) Can anyone please help or give me some advice where to start? Thank you!

We can represent every list of lambda expressions **$x\_0, x\_1, ..., x\_k$** with lambda expression **$\[x\_0, x\_1, ..., x\_k\]$** , defined as: **$\[x\_0, x\_1, ... , x\_k\] = \lambda c n. c \\, x\_0 \\, (c \\, x\_1 \\, (... (c \\, x\_k \\, n) ...))$**

Define lambda expression s, satisfying the equation **$s(\[\underline{n\_0}, ..., \underline{n\_k}\]) = \underline{n\_0 + ... + n\_k}$** , where **$\underline{n}$** is a Church numeral, representing natural number **$n$**.

Define lambda expression **$r$** , satisfying the equation **$r(\[x\_0, ..., x\_k\]) = \[x\_k, ..., x\_0\]$** .

Define lambda expression **$h$** and **$t$** , satisfying the equation **$h(\[x\_0, ..., x\_k\]) = x\_0 in t(\[x\_0, x\_1, ..., x\_k\]) = \[x\_1, ..., x\_k\]$** .

# Answer
Hint: This way lists are represented as folds. So if you have a lambda term representing a list, you just supply a folding function and a value to start with and the result will be the folded value.
> 1 votes

---
Tags: data-structures, lambda-calculus
---


# Question
Title: Job scheduling with a bottleneck problem
Given $n$ jobs $J\_1,J\_2,...,J\_n$, each job requires $T\_i \> 0, T\_i \in N$ time to complete.

Each job must be pre-processed and post-processed by a single machine M that can handle only *1 job at a time* and both phases require 1 unit of time. After being pre-processed, job $J\_i$ is sent to a machine with unlimited power (that can handle in parallel an unlimited number of jobs) and it will be ready in time $T\_i$, then it must be sent (**immediately**) to machine M again for post-processing.

The associated decision problem is:

*Input:* the processing times $T\_i \>0, T\_i \in \mathbb{N}$ of $N$ jobs, an integer $K\geq 2N$
*Question:* can we process all the jobs in time $\leq K$ using the above "bottleneck" model ?

> Has this problem a name?
> What is its complexity? (is it in $\sf{P}$ or is it $\sf{NP}$-complete?)

**UPDATE 29 March:**
As correctly noticed by M.Cafaro in his answer, the problem is similar to the *Unconstrained Minimum Finish Time Problem (UMFT)* (see Chapter 17 of Handbook of Scheduling Algorithms) which is $\sf{NP}$-hard (proved in W. Kern and W. Nawijn, "Scheduling multi-operation jobs with time lags on a single machine", University of Twente, 1993). As I can see, there are some differences because in my model:

* the pre/post processing time is constant (1 unit of time)
* as soon as the job is completed it must immediately be post-processed (the UMFT model allows delays)

I didn't found the Kern & Nawijn proof online, so I still don't know if the above restrictions change the difficulty of the problem.

Finally you can think the whole process like a single *cook robot* with a big oven; the robot can prepare different types of foods one at a time (all require the same time of preparation), put them in the oven, and as soon as they are cooked it must remove them from the oven and add some cold ingredients ... the "*cook robot problem*" :-)

# Answer
> 5 votes
The question is proven NP-hard in "Minimizing Makespan in a Two-Machine Flow Shop with Delays and Unit-Time Operations is NP-Hard" by W. Yu, H. Hoogeveen, and J.K. Lenstra (2004). This is proven in section 9 of the paper:

> Theorem 24. *The problem of minimizing the makespan on a single machine with two unit time operations per job with arbitrary intermediate delays is strongly NP-hard.*

The exact model studied here is that job $i$ consists of two operations that take unit time separated by some delay time $T\_i$. The problem is strongly NP-complete both when the exact value of the delay $T\_i$ is specified for each job, and when some minimum delay time is specified for each job.

# Answer
> 5 votes
This looks like the so called *master-slave scheduling model* introduced by Sahni. In particular, your problem falls under the Single-Master Master-Slave Systems. You can distinguish several cases:

1. If you do not add any additional constraint on the order of job execution (as in your case), the problem is called *unconstrained minimum finish time problem* (UMFT) and has been shown to be NP-hard;
2. Same Pre- and Postprocessing Orders: it is possible to design an $O(n \log n)$ algorithm to construct an *order preserving minimum finish time* (OPMFT) schedule;

Therefore, in case 1 your problem is $NP$-hard, while it is in $P$ in case 2.

Additional related problems are:

3. Reverse Order Postprocessing: For any given preprocessing permutation, $σ$ , it is possible to construct a reverse-order schedule, referred to as *canonical reverse order schedule* (CROS). Given a preprocessing permutation $σ$ , the corresponding CROS is unique. It is easy to establish that every *minimum finish-time reverse order* (ROMFT) schedule is a CROS.
4. no-wait-in-process constraint:

a) \[MFTNW\] Minimize finish time subject to the no-wait-in-process constraint; b) \[OP-MFTNW\] This is the order-preserving version of MFTNW. That is, minimize finish time subject to the no-wait-in-process and order-preserving constraints; c) \[RO-MFTNW\] Minimize finish time subject to the no-wait-in-process and reverse-order constraints.

Problems $a$ and $b$ are NP-hard, while $c$ admits a polynomial time solution.

Additional details in Handbook of Scheduling, chapter 17.

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


# Question
Title: Why don't we emphasize "length of input string" when considering time complexity of sorting algorithms?
The knapsack problem is $O(c\\,n)$ where $c$ is the capacity of knapsack and $n$ is the number of items. Yet it's exponential because the size of the input is $\log(c)$.

However, why don't we emphasize length of input in other algorithms? To name one example, what would be the **input size $n$** and **worst case time complexity $T$** of the following input when using insertion sort:

`111111111,101,11,10,1,0`

Answer A: $n=6$, $T=O(n^2)$
Answer B: n = space(all\_digits)+space(delimiters\_between\_numerics)

If B is correct, what is the time complexity $T$?

# Answer
First, note that the input length of a Knapsack instance is $\Theta(n \cdot \log \max \\{c,w\_1,\dots,w\_n\\})$. Assuming the instance is "pruned", namely that all weights are at most $c$, this is $\Theta(n\log c)$.

In order to answer such questions, you need to fix

* the machine model,
* the cost model,
* the set of valid inputs and
* the algorithm.

You don't give the first three.

So your question is not well defined. In order store this particular set of numbers on a Turing machine tape, six symbols are indeed sufficient (one per number), and then the algorithm would run in time $O(1)$ on its only input. In order to get a general algorithm, however, you need to "properly" encode the numbers, namely B is the correct answer. I'll assume the latter.

Insertion sort has worst-case complexity $\Theta(n^2)$ in the RAM model with uniform cost model (elementary operations on naturals cost $1$), $n$ being the number of elements. In particular, it is independent of the size of the numbers. Since $n \leq |i|$, $i$ the input, you get an $O(|i|^2)$ time algorithm.

If you apply the logarithmic cost model (elementar operations on naturals have cost depending on their encoding length, cf. elementary school), you get time $\Theta(n^2 \cdot \log E)$ with $E = \log \max\\{e\_1, \dots, e\_n\\}$ the length of the largest input number, because the $\Theta(n^2)$ comparisons on the elements dominate the runtime. With similar reasoning as above, we note that the algorithm has runtime $O(|i|^2)$.

So as you can see, the qualitative result does not change when considering the input length for *this* kind of algorithms, so it is often glossed over. When analysing e.g. radix sort this is no longer valid, and you have to look more closely.
> 8 votes

---
Tags: algorithms, terminology, time-complexity, runtime-analysis
---


# Question
Title: Largest reported speedup for a parallel computation?
A parallel implementation of a computation is usually compared to a sequential version of the same computation. The ratio of the time taken by the sequential version to the time taken by the parallel version is called the *speedup*. So if 8 cores run their smaller parts of the computation in 2 time units, and one core runs the whole computation in 8 time units, then the speedup is 4.

> What is the largest speedup reported for a real computation?

It is possible to reach essentially infinite speedup in a search problem, since one of the parallel pieces of the search space may lead to a fast solution by that parallel instance, while the sequential solution has to work through the entire search space to get to that point. More generally, I want to exclude any problem where one of the parallel processes can reach a shortcut. So I am only interested in computations where the amount of work done by the parallel processes is the same as done by the sequential process. This is common in solving PDEs by grid methods, or in discrete event simulation. So with $n$ processors, one should never get more than $n$ speedup for these kinds of problems.

I would also like to exclude embarrassingly parallel problems like parallel rendering, since there one really has a vast number of independent tiny problems. I am interested in problems where it is not possible to partition the computation into strictly disjoint pieces.

For a large speedup, one has to have many processors. Given the restrictions on scope that I have conveniently labelled as "real computations", this question is then essentially about how efficiently the very large processor arrays that exist have been programmed.

I am aware of reported speedups of ~500 using arrays of GPUs, but surely larger speedups exist.

---

*Edit:* To address some of the comments, I dug up some further motivation, which will hopefully be precise enough for the tastes of those more mathematically inclined. This is quite different in style from the above, so I append it here as a postscript.

For $n$ iid random variables $X\_1, X\_2,\dots, X\_n$ with mean $\mu$, denote their maximum by $X\_{(n)}$ and their sum by $S\_n$. O'Brien has shown that $X\_{(n)}/S\_n \to 0$ almost surely as $n \to \infty$ iff $\mu \< \infty$.

Letting $X\_i$ be the time taken by the $i$-th processor to complete its task, and assuming that there is a timeout/recompute mechanism to ensure that $\mu$ is finite, this hints that the inverse of the speedup should be essentially unbounded. (This is not necessarily the case: the techniques used may not carry over to the inverse, so I have to leave this a bit vague.)

This is a nice theoretical prediction, and the question arises: *is this prediction borne out in practice?* Or do implicit dependencies or diverging behaviours of the different processors (i.e. a breakdown in the iid assumption) tend to curtail this supposedly unbounded increase?

The iid case corresponds to the embarrassingly parallel case. Where the processors have to synchronize, independence breaks down.

My question can therefore also be rephrased as: how badly does non-negligible dependence between parts of a computation as seen in practice affect the large-scale speedups that have been demonstrated? Given that the bounds for expectation of the maximum in the non-independent case are quite weak, some pointers to empirical data would be useful.

# Answer
John Gustafson observed and reported speedups in excess of 1024 on early 80's supercomputers; this led him to the concept of scaled speedup (Gustafson-Barsis law), in contrast to the pessimistic Amdahl-Ware law.

Right now, in the era of multicore parallel supercomputers equipped with hundreds of thousands or millions of cores, performances are more commonly reported in terms of petaflops and efficiency. For instance, the winners of the last Gordon Bell prize at the Supercomputing 2012 conference, established the current world record for an astrophysical N-body simulation of one trillion particles performed on the full K computer, which appears to be number 4 in the June 2013 top 500 list. They reported 4.45 petaflops on 663,552 cores (the K computer was equipped with 82944 8-core processors in November 2012), and an efficiency (the ratio speedup/cores) of 42%. Translated in terms of speedup, that means a speedup of about 278,691.
> 8 votes

---
Tags: reference-request, efficiency, parallel-computing
---


# Question
Title: Can expected "depth" of an element and expected "height" differ significantly?
When analysing treaps (or, equivalently, BSTs or Quicksort), it is not too hard to show that

$\qquad\displaystyle \mathbb{E}\[d(k)\] \in O(\log n)$

where $d(k)$ is the depth of the element with rank $k$ in the set of $n$ keys. Intuitively, this seems to imply that also

$\qquad\displaystyle \mathbb{E}\[h(T)\] \in O(\log n)$

where $h(T)$ is the height of treap $T$, since

$\qquad\displaystyle h(T) = \max\_{k \in \[1..n\]} d(k)$.

Formally, however, there does not seem to be an (immediate) relationship. We even have

$\qquad\displaystyle \mathbb{E}\[h(T)\] \geq \max\_{k \in \[1..n\]} \mathbb{E}\[d(k)\]$

by Jensen's inequality. Now, one can show expected logarithmic height via tail bounds, using more insight into the distribution of $d(k)$.

It is easy to construct examples of distributions that skrew with above intuition, namely extremely asymmetric, heavy-tailed distributions. The question is, can/do such occur in the analysis of algorithms and data structures?

Are there example for data structures $D$ (or algorithms) for which

$\qquad\displaystyle \mathbb{E}\[h(D)\] \in \omega(\max\_{e \in D} \mathbb{E}\[d(e)\])$?

Nota bene:

* Of course, we have to interpret "depth" and "height" liberally if we consider structures that are not trees. Based on the posts Wandering Logic links to, "Expected average search time" (for $1/n \cdot \sum\_{e \in D} \mathbb{E}\[d(e)\]$) and "expected maximum search time" (for $\mathbb{E}\[h(D)\]$) seem to be used.
* A related question on math.SE has yielded an interesting answer that may allow deriving useful bounds on $\mathbb{E}\[h(D)\]$ given suitable bounds on $\mathbb{E}\[d(e)\]$ and $\mathbb{V}\[d(e)\]$.

# Answer
> 3 votes
In chained hash tables with uniform hashing a similar question arises. Given a table with $n$ elements hashed into $m$ buckets, the expected number of elements per bucket is $n/m$, but what is the expected length of the longest chain?

I found a Stackoverflow question about chained hash tables. The answer by btilly argues that for fixed ratio $n/m$ the expected worst case longest chain is $\Theta(\log n/ \log\log n)$. (Since $n/m$ is fixed, $m$ doesn't need to come into the answer.)

And the answer by templatetypedef references the following paper for a more detailed analysis:
Gaston H. Gonnet: Expected Length of the Longest Probe Sequence in Hash Code Searching.
J. ACM\_ 28(2):289-304, 1981.
\[Free techreport version at University of Waterloo\]

Slightly more generally I found a math.stackexchange question about the balls and bins problem. The answer by Yuval Filmus cites the following paper, which gives even tighter bounds: Martin Raab; Angelika Steger: Balls into Bins - A Simple and Tight Analysis. *2nd Intl Wkshp on Randomization and Approximation Techniques in Computer Science*, pp. 159-170, 1998.

Finally, there is apparently a branch of statistics called extreme value theory culminating in the Fisher-Tippett-Gnedenko theorem, which, I think, gives expected maxima for a huge variety of distributions.

---
Tags: algorithms, data-structures, algorithm-analysis, probability-theory, average-case
---


# Question
Title: Use complementary slackness to prove the LP formulation of max-flow only need polynomial number of path constraints
This is a homework problem for a class that ended 2 years ago, I'm learning it by myself.

Consider a directed graph $D=(V,A)$, $s,t\in V$. $A=\\{a\_1,\ldots,a\_n\\}$. Let $P=\\{p\_1,\ldots,p\_m\\}$ be the set of all simple paths from $s$ to $t$, There is a capacity function $c:A\to \mathbb{R}^+$. First we are asked to express max s-t flow as a linear program letting each path $p\_j$ in $P$ associated with the variable $x\_j$, there could be a exponential number of variables.

The formulation, $$ \begin{align} \text{Maximize:} & \sum\_{j}x\_j\\ \text{subject to:} & \sum\_{a\_i \in p\_j}{x\_j} \leq c(a\_i) &\text{ for } 1 \le i \le n, \\ & x\_j\geq 0 &\text{ for } 1 \leq j \leq m\\ \end{align} $$

The dual is therefore: $$ \begin{align} \text{Minimize:} & \sum\_{i} c(a\_i) y\_i\\ \text{subject to:} & \sum\_{a\_i\in p\_j} y\_i \geq 1 &\text{ for } 1 \le j \le m, \\ & y\_i\geq 0 &\text{ for } 1 \leq i \leq n\\ \end{align} $$

Assuming we have an optimal solution for the dual, the problem ask us to use complementary slackness to show there exist a formulation of the primal with only a polynomial number of paths, which also obtain an optimal solution. How is this done?

# Answer
One way which comes to mind is to use the fact that if $\sum\_{a\_i \in p\_j} y\_i \> 1$ for some $j \in \[m\]$ then $x\_j = 0$ and so the path $p\_j$ is irrelevant. However, consider a graph with exponentially many paths in which the source has capacity 1 and all other vertices have capacity 2. The optimal solution is 1 and it is obtained by $y\_s = 1$ and $y\_v = 0$ for all $v \neq s$, and so all the inequalities considered above are tight. (For a "generic" graph, however, we can expect the optimal solution to be obtained at a vertex, and so have at most $n$ tight constraints.)

Another way is to notice that if the primal has an optimal solution then it has one which is a vertex, and so has at least $m$ tight inequalities. At least $m-n$ of them are of the type $x\_j \geq 0$, and so there is an optimal solution using at most $n$ paths. However this is not helpful in the context of the exercise.
> 3 votes

---
Tags: linear-programming
---


# Question
Title: Efficiently map different codes to rotation-different codes
Let $\mathbb{F}^n\_2$ denote the set of $n$-bit 0-1 strings. How to construct an efficiently computable function $f:\mathbb{F}^n\_2\to \mathbb{F}^m\_2 (m\>n)$ satisfying that $\forall u\neq v$,$f(u)\neq f(v)$ and $f(u)$ is not a circular rotation of $f(v)$?

$m$ is expected to be as small as possible.

Thank you very much for your kindness.

# Answer
Here's a more efficient way of doing it. Let's map all the strings of length $n$ into strings of length $n+O(\sqrt{n} \log n)$ with no consecutive string of $0$'s of length more than $\sqrt{n}$. We then add a string $1 0^{a}1$ at the end, where $a \geq \sqrt{n} + 1$. Our mapping isn't always going to give us the same length string, so $a$ can vary.

How do we do this encoding? We need a way of encoding long string of 0's. Let's do that by taking a string of $0$'s of length at least $t$ and mapping it to a string of zeros of length $t$ followed by a number telling us how many zeros were in it.

$$ \begin{array}{lcl} 0^{\sqrt{n}} & \rightarrow & 0^{\sqrt{n}}10\ldots000 \\ 0^{\sqrt{n}+1} & \rightarrow & 0^{\sqrt{n}}10\ldots001 \\ 0^{\sqrt{n}+2} & \rightarrow & 0^{\sqrt{n}}10\ldots010 \\ 0^{\sqrt{n} +3} & \rightarrow & 0^{\sqrt{n}}10\ldots011 \\ 0^{\sqrt{n} +4} & \rightarrow & 0^{\sqrt{n}}10\ldots100 \\ \vdots &\rightarrow & \vdots \end{array} $$ Because we will never have a string of more than $n$ 0's, we can use the first $\lceil\log n \rceil$ bits after the string $0^{\sqrt{n}} 1$ to encode the length of the string of 0's. Thus, the most we can increase the length of our code by is a factor of $1 + \frac{\log n+2}{\sqrt{n}}$. After this expansion of the code, we need to add at least $\sqrt{n} + 1$ consecutive 0's. This lets us take $m = n + \sqrt{n}(\log n + 3)$.

I think you can probably get $m \approx n + \log n\\,$ by using the ideas behind arithmetic codes, but I don't have time to work the details out right now. If somebody else wants to work them out and post an answer, please feel free to do so.
> 6 votes

# Answer
Here is a trivial solution. Take $m = 2n+3$, and map $u$ to $u10^{n+1}1$. Each $f(u)$ has only one rotation containing the substring $10^{n+1}1$, so $f(u)$ is a rotation of $f(v)$ iff $u=v$. You can probably make do with a much smaller $m$, but I leave that to you.
> 1 votes

---
Tags: coding-theory
---


title: Regarding to the speed of supercomputer

text:
# Question
Title: Regarding to the speed of supercomputer
There seems to be a sense of competition in creating the fastest computer in the world, and I feel like technically you just have to continue increasing the core number to gain more flops, which is exactly what some countries are doing, so how would you really bench mark the technological level of a supercomputer

for example

United States currently have two supercomputer on the top list with similar performance, however one has significantly less core than the other

Titan has 560000 cores 17590 Rmax Tflops with 8000 kW of power

Sequoia has 1570000 cores 17173 Rmax Tflops with 7800 kW of power

Does this mean that Titan is a much superior supercomputer than Sequoia as it only uses 1/3 of cores to reach a similar performance, and if it does, this will also imply that judging supercomputer by flops is completely meaningless?

Is there something I am missing here? Such as the increasing complexity of software as the amount of core gets larger and the synchronization of overhead to assign task to each core gets more sophisticated?

Any info would be much appreciated

# Answer
> 5 votes
The only thing you are missing is the importance of the interconnect between cores/processors/racks and the design of the memory system for each processor.

I assume you are referring to the most recent top-500 supercomputer list. That list is sorted by **Rmax**, not Rpeak.

Rpeak is a measure of the theoretical maximum number of floating point operations that the system can perform. For Rpeak you are correct: just add more cores (or more vector units per core) and the Rpeak number will go up.

**Rmax** is (arguably) a little bit more meaningful. It is the maximal rate at which the system can run the Linpack benchmark. The Linpack benchmark requires the system to solve a huge, dense, system of linear equations using LU factorization with partial pivoting in double precision.

For solving a dense system of linear equations you need to carefully partition the problem among the cores, and there needs to be an efficient way for the cores to communicate results back and forth. So a big part of designing a computer that will get onto the Top500 list is careful design of the interconnect and the software used to send messages between processors.

On the top500 list they tell you what interconnect each system is using. Note that you don't find a system with Ethernet until you get to number 49. The first 48 all have infiniband, cray gemini or custom interconnects.

There is also a green500 list that measures the MFLOPS/Watt of systems while solving the Linpack benchmark. The difference between the top system and the 500th system on that list (from last November) is a factor of 75x.

Most people agree that there is a lot more that you want from a supercomputer in addition to being able to efficiently solve massive dense systems of linear equations. Jack Dongara (who originated the Linpack benchmark) has recently released a paper proposing a new benchmark that measures the speed at which a system can solve a sparse linear system. http://www.netlib.org/utk/people/JackDongarra/PAPERS/HPCG-Benchmark-utk.pdf.

# Answer
> 0 votes
not necessarily. since SC are built not for records, but for real work, it's important how they execute real programs. some cpus has more raw power, but harder to program (read: they can be used only for subset of useful programs), other are opposite

the great example is your won computer - it has 2-8 cores in the cpu, and up to 2000 cores in the video card. but video card can't efficiently run the code that runs in the cpu. it only does very limited tasks but does it extremely well

---
Tags: performance
---


title: How a TM can represent any algorithm?

text:
# Question
Title: How a TM can represent any algorithm?
As I remember:

* A decision problem is a problem that has the answer yes or no.
* An algorithm (in the context of automata theory) answers yes or no; it halts on all inputs, accepted or not.
* A TM represents an algorithm. The TM accepts an input string and executes with that input. If the machine ends up in an accept state, the answer is yes, otherwise no.

How does a yes/no problem relate to general algorithms we are doing that have more than yes/no problems? Or is that every problem can be thought as a yes/no problem, i.e. is this a function f produce 5 (or whatever input) with input 2 (or whatever output)?

# Answer
Don't forget that the final content of the tape can be treated like the output of the algorithm that the TM computes; in other words, a TM is able to compute a function: there is no "reject state" but only an "accept state" and the function result is the content of the tape at the end of the computation.

But if you want to learn more on the relation between decision problems and function problems , (quickly) read the Decision Problem - Equivalence with functions problems entry on Wikipedia, and then search some lectures online on the subject.
> 6 votes

# Answer
you can just convert you general algorithm into one comparing correct answer with the additional input
> 0 votes

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


# Question
Title: Upper bound on the number of edges relative to the height of a DFS tree
Let $T$ be a depth-first search tree of a connected undirected graph $G$ and $h$ be the height of $T$. How do you show that $G$ has no more than $h \times |V|$ edges where $|V|$ is the number of vertices in $G$?

# Answer
After running a DFS, all the edges in $G$ can be classified as tree edges or back edges. Each back edge connects a vertex on the tree to one of it's ancestors. For each vertex it can point to at most $h-1$ ancestors, thus you can have at most $(h-1)|V|$ back edges. There are $|V|-1$ tree edges. You can have at most $h|V|-1$ edges.
> 4 votes

---
Tags: graphs, spanning-trees
---


# Question
Title: Heap - Give an $O(n \lg k)$ time algorithm to merge $k$ sorted lists into one sorted list
Most probably, this question is asked before. It's from CLRS (2nd Ed) problem 6.5-8 --

> Give an $O(n \lg k)$ time algorithm to merge $k$ sorted lists into one sorted list, where $n$ is the total number of elements in all the input lists. (Hint: Use a min-heap for $k$-way merging.)

As there are $k$ sorted lists and total of $n$ values, let us assume each list contains $\frac{n}{k}$ numbers, moreover each of the lists are sorted in strictly ascending order, and the results will also be stored in the ascending order.

My pseudo-code looks like this --

```
    list[k]   ; k sorted lists
    heap[k]   ; an auxiliary array to hold the min-heap
    result[n] ; array to store the sorted list
    for i := 1 to k                 ; O(k)
    do
        heap[i] := GET-MIN(list[i]) ; pick the first element
                                    ; and keeps track of the current index - O(1)
    done
    BUILD-MIN-HEAP(heap) ; build the min-heap - O(k)
    for i := 1 to n
    do
        array[i] := EXTRACT-MIN(heap)   ; store the min - O(logk)
        nextMin := GET-MIN(list[1])     ; get the next element from the list 1 - O(1)
        ; find the minimum value from the top of k lists - O(k)
        for j := 2 to k
        do
            if GET-MIN(list[j]) < nextMin
                nextMin := GET-MIN(list[j])
        done
        ; insert the next minimum into the heap - O(logk)
        MIN-HEAP-INSERT(heap, nextMin)
    done

```

My overall complexity becomes $O(k) + O(k) + O(n(k + 2 \lg k)) \approx O(nk+n \lg k) \approx O(nk)$. I could not find any way to avoid the $O(k)$ loop inside the $O(n)$ loop to find the next minimum element from k lists. Is there any other way around? How to get an $O(n \lg k)$ algorithm?

# Answer
> 15 votes
The purpose of the heap is to give you the minimum, so I'm not sure what the purpose of this for-loop is - `for j := 2 to k`.

My take on the pseudo-code:

```
lists[k][?]      // input lists
c = 0            // index in result
result[n]        // output
heap[k]          // stores index and applicable list and uses list value for comparison
                 // if i is the index and k is the list
                 //   it has functions - insert(i, k) and deleteMin() which returns i,k
                 // the reason we use the index and the list, rather than just the value
                 //   is so that we can get the successor of any value

// populate the initial heap
for i = 1:k                   // runs O(k) times
  heap.insert(0, k)           // O(log k)

// keep doing this - delete the minimum, insert the next value from that list into the heap
while !heap.empty()           // runs O(n) times
  i,k = heap.deleteMin();     // O(log k)
  result[c++] = lists[k][i]
  i++
  if (i < lists[k].length)    // insert only if not end-of-list
    heap.insert(i, k)         // O(log k)

```

The total time complexity is thus $O(k * \log k + n * 2 \log k) = O(n \log k)$

You can also, instead of `deleteMin` and `insert`, have a `getMin` ($O(1)$) and an `incrementIndex` ($O(\log k)$), which will reduce the constant factor, but not the complexity.

**Example:**
(using value rather than index and list index and heap represented as a sorted array for clarity)

```
Input: [1, 10, 15], [4, 5, 6], [7, 8, 9]

Initial heap: [1, 4, 7]

Delete 1, insert 10
Result: [1]
Heap: [4, 7, 10]

Delete 4, insert 5
Result: [1, 4]
Heap: [5, 7, 10]

Delete 5, insert 6
Result: [1, 4, 5]
Heap: [6, 7, 10]

Delete 6, insert nothing
Result: [1, 4, 5, 6]
Heap: [7, 10]

Delete 7, insert 8
Result: [1, 4, 5, 6, 7]
Heap: [8, 10]

Delete 8, insert 9
Result: [1, 4, 5, 6, 7, 8]
Heap: [9, 10]

Delete 9, insert nothing
Result: [1, 4, 5, 6, 7, 8, 9]
Heap: [10]

Delete 10, insert 15
Result: [1, 4, 5, 6, 7, 8, 9, 10]
Heap: [15]

Delete 15, insert nothing
Result: [1, 4, 5, 6, 7, 8, 9, 10, 15]
Heap: []

Done

```

# Answer
> 13 votes
First of all, I think that your assumption of all lists having $n/k$ entries is not valid if the running time of the algorithm depends on the length of the *longest* list.

As for your problem, the following algorithm should do the trick:

1. Put the first elements of the lists in a min-heap $H$ of size $k$. Remember for each element the list $l\_m$ it belongs to. ($O(k\lg k)$)
2. For $i$ from $1$ to $n$ do:
    * Extract the minimum $m$ from $H$ and store it in $result\[i\]$ ($O(\lg k)$)
    * Insert the direct successor of $m$ in $l\_m$ (if any) into $H$ ($O(\lg k)$ )

The running time is obviosuly in $O(k\lg k + n \lg k)=O(n\lg k)$ and the algorithm correctly sorts $result$.

*Proof* (or at least, an idea for a proof). Consider the following loop invariant: The $i$-th element to insert into $result$ is always the minimum of the min-heap $H$ in step $i$ and therefore, $result\[1..i\]$ is correctly sorted after the $i$-th iteration.

This is true before the first iteration: First, we show that the first element to insert into $result$ is in $H$: Assume towards a contradiction that the first element to insert into $result$ (that is, the overall smallest element, call it $r\_1$) were not a first element. Then, in the list $l$ that contains $r\_1$, the first element $l\[1\]$ must be distinct from $r\_1$ (as by assumption, $r\_1$ is *not* a first element). As our lists are all sorted, we have even $l\[1\] \< r\_1$, but this is a contradiction, as we chose $r\_1$ to be the *overall* smallest element. Obviously, the minimum of all first elements is the one to insert into $result$.

The invariant holds after an iteration: We proceed in the same way. Assume the $i$-th element to insert (call it $r\_i$) were not in $H$. By construction, $H$ holds at most one element from each list, and once it contains an element $m$ from a list $l$, all of its predecessors in $l$ were already extracted from $H$ and (by hypothesis) correctly inserted into $result$. Therefore, $r\_i$ is assumed to be a successor of some element $m$ in the list $l$. But this is, as above, a contradiction, as $l$ is sorted, and therefore, the invariant holds.

On termination, we thus have $result\[1..n\]$ correctly sorted.

---
Tags: algorithms, algorithm-analysis, heaps, priority-queues
---


title: Bloom Filter for 208 million URLs

text:
# Question
Title: Bloom Filter for 208 million URLs
I need to create a bloom filter of 208 million URLs. What would be a good choice of bit vector size and number of hash functions? I tried a bit vector of size 1 GB and 4 hash functions, but it resulted in too many false positives while reading.

I have a huge web corpus containing web content of billions of URLs. I need to process the web content of URLs satisfying certain criteria: the URL should have appeared in web search results in the past 7 days at least 5 times. This is represented by a list of 208 million URLs. Joining the list directly with the web corpus is not feasible because of volume. So I am considering creation of a bloom filter out of the list and then using the bloom filter to prune out unnecessary URLs from the web corpus.

# Answer
Using the formula from wikipedia for Bloom filter false positives, your proposal would have a false positive probability of about 0.00726%. This assumes, among other things, that good hash functions are used. The formula is:

$(1 - (1 - \[1/m\])^{kn})^k$

where $m$ is the number of bits in the filter, $k$ is the number of hash functions and $n$ is the number of entries in the filter.

Because items cannot be removed from a typical Bloom filter, if generation of the filter is too expensive, you might consider a counting Bloom filter to allow deletions.

(Although I have not read of it being used and do not know if it would be effective, one might use ORed signatures in each field instead of a set bit, where each signature has half or fewer of the bits set. A possible match is found when ((entry\_signature ^ test\_signature) & test\_signature) == 0 for each entry selected by a hash function. If every signature has the same number of set bits, this would be like nesting a Bloom filter with a size equal to the signature size and the number of hash functions equal to the number of set bits.)
> 6 votes

# Answer
I recommend you to try Siphash, what is 64-bit, cryptographically strong and extremely fast. It's keyed so you can use as many Siphash'es as you need, each providing 64 bits of variability
> 0 votes

---
Tags: data-structures, probabilistic-algorithms, searching, big-data, bloom-filters
---


title: Are HTML and CSS regular languages?

text:
# Question
Title: Are HTML and CSS regular languages?
I have a question whether or not CSS and HTML are regular languages.

I believe CSS is a regular language, since it should be possible to create a regular expression to match the structure of CSS.

However, I believe that HTML is **not** a regular language since you have nested attributes that could be defined recursively.

# Answer
Providing a regular expression or DFA for a language and proceeding to demonstrate that it is correct for the language in question generally constitutes a pretty convincing argument for the regularity of the language. To prove a language is non-regular, you have a few options: the pumping lemma for regular languages is a classic standby, but the Myhill-Nerode theorem is pretty nifty, too (especially since you can use it to prove regularity as well as non-regularity).

Your first job should be to define what constitute valid strings in the languages $HTML$ and $CSS$. Note that most browsers will take anything you call $HTML$ and display something without error; in that sense, anything is valid $HTML$, and the language $\Sigma^\*$ is trivially regular. However, I think it's safe to assume that you have something a bit more strict in mind: $HTML$ consists only of those strings that conform to some standard, which probably calls for matched tags. In this case, you should be able to prove that $HTML$ isn't regular, since you can consider the following kinds of strings (whitespace is added only for clarity and could be removed in the real string):

```
<html>
   <body>
      <table>
         <tr>
            <td>
               <table>
                  ...
               </table>
            </td>
         </tr>
      </table>
   </body>
</html>

```

This language, `<html><body>` $($ `<table><tr><td>` $)^n($ `</td></tr></table>` $)^n$\`\</body\>\</html\>\`, should be enough to get to a proof of non-regularity, provided you accept the above as valid $HTML$, and would say that a missing \`\</table\>\` tag would make the resulting string invalid $HTML$, even though browsers would try to render it anyway.

For $CSS$, first figure out what strings you think are valid, then try to come up with a regular expression or DFA for the set of all $CSS$ strings, or figure out how to define a subset of $CSS$ that requires non-local checks and unbounded memory (counting, matching, nesting, etc.) If you can define such a subset (like we did for $HTML$ above), then you're good to go.
> 11 votes

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


title: Speeding up a program solving Icosoku

text:
# Question
Title: Speeding up a program solving Icosoku
I bought a great puzzle called Icosoku. Wikipedia describes it as: "The puzzle frame is a blue plastic icosahedron, and the pieces are 20 white equilateral-triangular snap-in tiles with black dots and 12 yellow pins for the corners. The pins are printed with the numbers from 1 to 12, and the triangular tiles have up to three dots in each of their corners. The object of the game is, for any arrangement of the pins, to choose the positions and orientations of the triangles so that the total number of dots on the five joining corners of each pin equals the number of the pin."

I created a computer program which solves this puzzle by randomly choosing any two triangular tiles and then exchanging them (giving each tile a random orientation) if and only if the total discrepency (which can be measured in various ways) between each number on the pins and the total number of dots on the five joining corners of each pin decreases. But I have found that it takes hundreds or even thousands of iterations to finally get a solution for most initial configurations. I would like my program to take less time. Any suggestions?

# Answer
I suggest you to look at other (completely different) approaches, too:

1. write a program that given an Icosoku configuration outputs a SAT instance that can be solved using a SAT solver;
2. (re)write your program using a constraint programming language (for example STP) or write a program that given an Icosoku configuration outputs an intermediate source code for the constraint solver;
3. (re)write your solver using a SAT library (for example Choco for Java).

... perhaps you'll find them interesting (and faster) :-)
> 3 votes

# Answer
Another technique that may be suitable for your problem is backtracking. It is often used for solving puzzles such as 8 queens problem, sudoku, etc.
> 2 votes

# Answer
The Rubik cube is a different beast, but the techniques to study it might come handy. A look at the mathematics (group theory) behind its solution is Joyner's "Mathematics of the Rubik's Cube", the site http://permutationpuzzles.org with its links might also be of help.
> 1 votes

# Answer
Heuristics may help. Probably you can arrange the nodes in groups of three for example one node may be conformed by the numbers 12,10,5 which sums 27, sort all of them like this (example) 12,10,5=27 12,7,5=24 10,9,4=23... and so on.

In the other hand arrange the sum of the dots from the triangles... 3,3,3=9 first in list 3,3,2=8 (i don't know if this configuration of dots exists (doesn't matter) ... 0,0,0 at the and

1.- then you go recursive putting first, the higher triangle in the higher node. 2.- if doesn't help rotate in the same node 3.- if doesn't help, permute triangle with the next higher node, (which may have the next higher triangle).
> 0 votes

---
Tags: efficiency, computer-games
---


title: Equivalence of regular expressions

text:
# Question
Title: Equivalence of regular expressions
Is it possible, in general, to determine whether two regular expressions admit the same set of strings?

Also, in particular, is it possible to determine whether a given regular expression admits the same set of strings as the regular expression ".\*" (i.e., accepts anything).

# Answer
This seems like a dupe, but I couldn't find one in a cursory search. Given that, we can solve your problem as follows:

1. Generate NFAs $N\_1$ and $N\_2$ for the regular expressions $r\_1$ and $r\_2$;
2. Generate DFAs $M\_1$ and $M\_2$ for the NFAs $N\_1$ and $N\_2$;
3. Generate DFAs $D\_1$ and $D\_2$ such that $L(D\_1) = L(M\_1) \setminus L(M\_2)$ and $L(D\_2) = L(M\_2) \setminus L(M\_1)$;
4. Determine whether $L(D\_1) = L(D\_2) = \emptyset$; if so, $L(r\_1) = L(r\_2)$; else, $L(r\_1) \neq L(r\_2)$.

You can do (1) by using Kleene's theorem demonstrating that regular expressions and finite automata have the same expressive power. To each of the operations union, concatenation, and Kleene closure, there corresponds an automaton-based construction which accepts what the regular expression generates. By recursivly applying these constructions to subexpressions you can build an NFA to accept the language generated by a regular expression.

To do (2), you typically will want to use the powerset construction (sometimes called the subset construction). This involves constructing a DFA whose set of states equals the set of subsets of stats from the NFA. Transitions now connect subsets of states which are reachable from each other. The resulting DFA may have up to $2^{|Q|}$ states, where $Q$ is the set of states in your NFA.

To do (3), you can use the Cartesian product machine construction to generate machines with up to $|Q\_1| \times |Q\_2|$ states. Every state in your product machine will correspond to a pair of states from the operand machines. You must choose the set of accepting states to effect the correct operation; in our case, set difference.

To do (4), you can try all strings of length up to and including $|Q|$. If the machine accepts anything, it must accept some string of such a length. If you check all the strings and nothing's accepted, you know that $L(M) = \emptyset$. If that's the case, by construction, then the one language is a subset of the other. If both languages are subsets of each other, the languages are equal, by definition of set equality.
> 12 votes

---
Tags: regular-expressions
---


title: Complexity of a particular algorithm

text:
# Question
Title: Complexity of a particular algorithm
I am a bit confused about calculating complexities.

Above is a C++ program converting a char array into an int, incrementing the value, parsing it back to char array.

```
#include <iostream>

int main() {
    char number[] = {'4', '3', '1'};
    int num = 0;
    //char to int conversion
    for (int i = 0; i < (int)sizeof(number); i++) {
        num += number[i] - '0';
        num*=10;
    }
    num/=10;

    //incrementation
    num++;

    //int to char conversion
    for (int i = (int)sizeof(number) -1; i >= 0; i--) {
        number[i] = '0' + num % 10;
        num/=10;
    }

    //printing the result
    std::cout << number << endl;
    return 0;
}

```

Now let's say array size(3) is n. In that case I would say that the complexity is O(n+n) which is O(2n). However I've heard that O(2n) is actually O(n) for some reason but I could not find any actual source about it. What is the time complexity of this program?

# Answer
The way $O(f(n))$ is defined, $O(k \times f(n))$ = $O(f(n))$ for positive constants $k$. Therefore, $O(2n)$ = $O(n)$. The reason this works is that $f(n) = O(g(n))$ if and only if there exists some constant $c$ such that for all $n \geq n\_0$ it holds that $f(n) \leq c \times g(n)$. We can therefore demonstrate that $k \times f(n) = O(f(n))$ since $k \times f(n) \leq c \times f(n)$ precisely for $c \geq k$.
> 4 votes

---
Tags: algorithms, algorithm-analysis, asymptotics, runtime-analysis
---


# Question
Title: Number of permutation cycles in matrix transposition
I am trying to solve a problem on Sphere Online Judge (SPOJ) link to which is: http://www.spoj.com/problems/TRANSP/

The matrix can be thought of as a permutation and its transposition as another permutation. I need to convert the first one into another. I have found a relation between the Cycles in the Permutation and the number of swaps required as:

Minimum Swaps = Total Elements in Permutation - Number of Cycles

However, I don't know how to calculate the matrix of size $2^a 2^b$ where $a+b \leq 500000$.

# Answer
Let's take a simple example: $$ \begin{pmatrix} a & b & c \\ d & e & f \\ g & h & i \end{pmatrix}' = \begin{pmatrix} a & d & g \\ b & e & h \\ c & f & i \end{pmatrix}.$$ So we need to exchange $(b,d),(f,h),(c,g)$, i.e. the answer is 3. Now try to generalize this to $A \times B$ matrices. Obtain a formula, substitute $A = 2^a$ and $B = 2^b$, and find a way to efficiently compute the result modulo a small prime $p$.

When $A = 2^a$ and $B = 2^b$, things look nicer. The permutation taking a position in the original matrix to the corresponding position in the transposed matrix corresponds to left shift by an amount $a$. Suppose $g = \mathrm{gcd}(a,b)$ and $a' = a/g,b' = b/g$. We can now think of the operation as a left shift by the amount $a'$ of a string of length $a'+b'$ over an alphabet of size $G = 2^g$. The number of orbits is then the number of necklaces of length $a'+b'$, which has an explicit formula. (The shift amount doesn't matter since $a'$ is invertible modulo $a' + b'$ due to $(a',b')=1$.)
> 3 votes

---
Tags: algorithms, matrices, permutations
---


# Question
Title: Combination with a minimum number of elements in a fixed length subset
I have been searching for long but unable to find a solution for this. My question is "Suppose you have n street lights(cannot be moved) and if you get any m from them then it should have atleast k working.Now in how many ways can this be done"

This seems to be a combination problem, but the problem here is "m" must be sequential.

Eg: 1 2 3 4 5 6 7 (Street lamps) Let m=3 Then the valid sets are,
1 2 3
2 3 4
3 4 5
4 5 6
5 6 7

Whereas, 1 2 4 and so are invalid selections.

So every set must have atleast 2 working lights. I have figured how to find the minimum lamps required to satisfy the condition but how can I find the number of ways in it can be done ?

There should certainly some formula to do this but I am unable to find it.. :(

Eg: Let n=7,m=4,k=3. The minimum number of lights that must be working to satisfy the condition that "atleast 3 of any 4 lights must be working" is 5. It is if 23467 are working. But there are more ways in which it can be satisfied like if 23467,13457... We have 4 such combinations in all for the taken values of n,m,k. I want to know how can we generalize this?

Can be represented like this : n =\> 1111111
1 Indicates light working and 0 indicated not working.
0111110
0111011
1011101
1011110

Hope the question is clear.

# Answer
For each particular $m,k$ you can get a recurrence formula and solve it. Perhaps this way you can obtain a general formula. Here is how to find the recurrence formula:

1. The language of all valid sequence is regular. Construct a DFA (deterministic finite automaton) that accepts the language. (An optimization: construct a "partial" DFA in which sometimes there is no outgoing edge labeled $0$.)
2. Suppose the transition matrix is $A$, the initial state is $s$, and the accepting states are $F$. Then the number of sequences of length $n$ is $\alpha\_n = 1\_F A^n 1\_s$.
3. Compute the Jordan normal form of $A$, decompose $1\_F,1\_s$ according to the Jordan basis, and so obtain a formula for $\alpha\_n$.

Instead of using DFAs, you can use generating functions, which really amounts to the same.

Here is a very simple example: $m = 2$ and $k = 1$. The regular language here is all words not containing $00$, that is $1^\*(10)^\*1^\*$. The minimal partial DFA has two states $s\_0,s\_1$ which correspond to the two possible "histories" (we can assume that the part of the sequence before it actually starts consists entirely of 1s) - in general there will be $2^{m-1}$ states (if $k \< m-1$ then actually less, since some of them would be invalid). The transitions are: On $0$, transition from $s\_1$ to $s\_0$; On $1$, transition from $s\_0,s\_1$ to $s\_1$. The starting state is $s\_1$. All states are accepting (this will always be the case with a minimal partial DFA). The transition matrix is $$ A = \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}. $$ Therefore $$ \alpha\_n = \begin{pmatrix} 1 & 1 \end{pmatrix} \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}^n \begin{pmatrix} 0 \\ 1 \end{pmatrix}. $$ The matrix $A$ has two eigenvalues $(1 \pm \sqrt{5})/2$, and furthermore $$ A = \begin{pmatrix} 1 & 1 \\ \frac{1-\sqrt{5}}{2} & \frac{1+\sqrt{5}}{2} \end{pmatrix} \begin{pmatrix} \frac{1-\sqrt{5}}{2} & 0 \\ 0 & \frac{1+\sqrt{5}}{2} \end{pmatrix} \begin{pmatrix} \frac{1}{2} + \frac{\sqrt{5}}{10} & -\frac{\sqrt{5}}{5} \\ \frac{1}{2} - \frac{\sqrt{5}}{10} & \frac{\sqrt{5}}{5} \end{pmatrix}. $$ Thus $$ \begin{align\*} \alpha\_n &= \begin{pmatrix} \frac{3-\sqrt{5}}{2} & \frac{3+\sqrt{5}}{2} \end{pmatrix} \begin{pmatrix} \frac{1-\sqrt{5}}{2} & 0 \\ 0 & \frac{1+\sqrt{5}}{2} \end{pmatrix}^n \begin{pmatrix} -\frac{\sqrt{5}}{5} \\ \frac{\sqrt{5}}{5} \end{pmatrix} \\ &= \frac{5-3\sqrt{5}}{10} \left( \frac{1-\sqrt{5}}{2} \right)^n + \frac{5+3\sqrt{5}}{10} \left( \frac{1+\sqrt{5}}{2} \right)^n. \end{align\*} $$ The first few numbers (starting with $\alpha\_0$) are $1,2,3,5,8,13,\ldots$, and we recognize the Fibonacci sequence: $\alpha\_n = F\_{n+2}$.

---

An alternative to following these steps is noticing that $\alpha\_n$ is always defined by a recurrence relation of length at most $2^{m-1}$. So for general $m,k$, all you have to do is calculate enough of the sequence $\alpha\_n$ to determine the coefficients: you need to calculate $\alpha\_0,\ldots,\alpha\_{2^m-1}$, which will give you $2^{m-1}$ equations.

Here is how to do it for $(m,k) = (2,1)$: $\alpha = 1,2,3,5$. If $\alpha\_n = c\_1 \alpha\_{n-1} + c\_2 \alpha\_{n-2}$ then $3 = 2c\_1 + c\_2$ and $5 = 3c\_1 + 2c\_2$. We deduce that $c\_1 = c\_2 = 1$ and so the recurrence is $\alpha\_n = \alpha\_{n-1} + \alpha\_{n-2}$.

Having recovered the recurrence relation, we solve it as usual. It will usually be the case that all roots of the characteristic polynomial are distinct, and that the asymptotics of the sequence are given by the largest root (though in principle it depends on the actual sequence).
> 2 votes

---
Tags: algorithms, logic, combinatorics
---


# Question
Title: Properties of polynomial time many-one reductions
I'm working on old multiple choice exams and would like to know if the following statements are true or false:

a) $L\_1 \le\_p L\_2 \le\_p L\_3 \Rightarrow L\_1 \le\_p L\_3$

b) If $L \in \mathsf{NP}$ and $U \le\_p L$ holds for all languages $U \in \mathsf{PSPACE}$ then $\mathsf{NP} = \mathsf{PSPACE}$

c) $L \in P \Leftrightarrow L \le\_p \\{a\\}^\*$

Statement a) was part of the lecture, Statesments b) and c): I don't know.

# Answer
> 2 votes
Article (a) is badly written. Writing $L\_1\le\_p L\_2\le\_p L\_3$ already implies, in a way, that we have transitivity. How do you think could a reduction function for $L\_1\le\_p L\_3$ look like, if we know reduction functions for $L\_1\le\_p L\_2$ and $L\_2\le\_p L\_3$?

As for (b): If $U\le\_p L$ for every language $U\in PSPACE$, then in particular this is true for some PSPACE complete language. For example, TQBF. Do you see what to do from here? (comment if not)

For (c): Also badly written, since the alphabet isn't stated, and it may affect the answer. Assuming the alphabet is not $\\{a\\}$, but something bigger (e.g. $\\{a,b\\}$), then the answer is yes: first, obviously if $L\le\_p \\{a\\}^\*$ then $L\in P$ (do you see why this is obvious?)

Conversely, if $L\in P$ then you can solve $L$ "within" a polynomial-time reduction. That is, given an input for $L$, a reduction can decide whether it is in $L$, and use the result to decide what to output.

Now, if the alphabet has other letters than $a$, then $a^\*\neq \Sigma^\*$, and the reduction can output something that is either in $\\{a\\}^\*$ or not in $\\{a\\}^\*$, depending on the input.

If, however, the alphabet is $\\{a\\}$, then there is no such reduction unless $L=\\{a\\}^\*$.

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


title: PCP deterministic emulation

text:
# Question
Title: PCP deterministic emulation
Suppose that $S \in PCP(r(n),q(n))$, colclude that $S \in NTIME(2^r \cdot poly) \cap DTIME(2^{2^r q+r} \cdot poly)$

The idea of a nondeterminstic simulation of the $V$ on input $x$ is simple, guess a proof, check every string $y$ of the length $2^r$, and this simulation should take nondeterministic time $2^r \cdot poly$ because $V$ works in time $poly$ and there are $2^r$ string to check.

In case of deterministic simulation the same intuition is applied, the maximum length of the proof is $2^r \cdot q$ with non-adaptive queries, hence $2^{2^rq}$ number of proofs should be checked by deterministic emulation, therefore the total time is $2^{2^r \cdot q} \cdot poly$, not exactly what's required.

The problem is to show that $S \in NTIME(2^r \cdot poly) \cap DTIME(2^{2^r q+r} \cdot poly)$

# Answer
> 4 votes
Checking each of the possible proofs takes time $O(2^r\cdot poly)$, so checking $2^{2^rq}$ of them would take how much?

---
Tags: complexity-theory
---


# Question
Title: Quantum computers, parallel computing and exponential time
I've read that quantum computers can solve 'certain problems' exponentially better than classical computers. As I think I understand it, it's NOT the same to say that quantum computers take any problems that are EXPTIME-complete, 2-EXPTIME,... and convert them to linear time or constant-time.

I would like to know something more about this matter:

* Why can/can't a quantum computer solve exponential problems in sub-exponential time?
* Is it at least theoretically possible to imagine a computer (quantum or otherwise) able to solve EXPTIME-complete problems in constant time? Or does this lead to a contradiction?

**EDIT** a third related item:

* Can quantum computers do parallel computing?

Now that the subject came up from comments, the idea about parallel computing, that's the usual/pop vision about quantum computers, like if quantum computers were able to compute "all posibilities at once" of any given problem (I think if that were the case, wouldn't be necesary to call great Peter Shor to invent a factoring algorithm!). Then "why" question about quantum computers can/cannot do parallel computing is half a computer science and a physics question.

Here a source of confusion: http://physics.about.com/od/physicsqtot/g/quantumparallel.htm

# Answer
*Why can't a quantum computer solve exponential problems in sub-exponential time?* Factoring is believed (by some) to take classical time $2^{n^\epsilon}$ for some $\epsilon \> 0$, while Shor's algorithm takes time $O(n^3)$. Does that count?

*Is it at least theoretically possible to imagine a computer able to solve EXPTIME-complete problems in constant time?* Sure, consider a Turing machine with oracle access to all EXPTIME problems (i.e. the oracle accepts the code of an EXPTIME machine and an input, and returns the output). This doesn't lead to any contradictions. Is this realizable in practice? Probably not.

*Can quantum computers do parallel computing?* It is known that BQP$\subseteq$PP$\subseteq$EXPTIME, and most people expect these inclusions to be proper. Under this conjecture, there are problems solvable in classical exponential time but not quantum polynomial time. In particular, EXPTIME-complete problems shouldn't be in BQP.
> 6 votes

# Answer
It's certainly possible to imagine computers able to solve certain problems (EXPTIME-complete or otherwise) in constant time. Such computers are called "oracle machines," and they are an important tool in the study of complexity theory. However, it's not necessarily possible to construct these machines.
> 3 votes

---
Tags: complexity-theory, time-complexity, quantum-computing
---


# Question
Title: Analysis of algorithms, 'big O' question
The main question is, how exactly is the big O analysis calculated on routines? Is there a specific formula that relates what each function in a program does to a big O calculation?

Also, what about more complex iterations, such as colour conversions etc?

I would like to point out that this is not a homework question, rather, it is a question from my own research/programming learning curve. I have code that I am working on, but would like to know how this analysis is carried out.

# Answer
There is no specific formula for calculating it as jmite already mentioned. You have to realize that $\mathcal{O}$ notation serves to merely estimate the number of cycles a certain process takes to execute. It's not an exact representation or quantity.

For instance, lets say you had the following function:

```
int add(int a, int b)
{
  return a+b;
}

```

This function would be $O(1)$ because it is a linear operation. There are no loops, tree or list traversals (if you've gotten up to those topics already), etc. It's a simple single instruction function.

Now if I modified that function to say the following

```
int redundantAdd(int a, int b)
{
  int c = a+b;
  c += 0;
  b+= c;
  return c;
}

```

you'll notice that I now have 3 more instructions than the previous snippet. However, it is still $O(1)$. Again, we are just trying to give a general idea of the amount of time spent on a process, not an exact number.

Now suppose I created another function, like the one below.

```
int summation(int array[])
{
  int sum = 0;
  for(int i = 0; i < (sizeof array)/(sizeof array[0]); ++i)
  {
    sum += array[i];
  }
}

```

This block of code is now $O(\text{length of array})$ (we say $O(n)$ if the array length is $n$), since we are generally executing $n$ number of tasks. We do not take into consideration the initialization of sum at the beginning. It's usually insignificant unless $n$ is small.

Now suppose I modified that code to add all the elements in a matrix

```
    int summation(int matrix[][], int width, int height)
    {
      int sum = 0;
      for(int i = 0; i < width; ++i)
      {
        for(int j = 0; j < height; ++j)
         {
            sum += matrix[i][j];
         }
      }
    }

```

This time we have $O(n^2)$ if if the width == height = n , we essentially iterate through the loop $n^2$ times. Again, we're only estimating here, so we don't care if they're different, it just makes for easy representation. I won't bother you with logarithmic big-O notation yet as you need to drill down on the key purpose of the notation first. Doing so will only confuse you.
> 2 votes

# Answer
There is no such formula. If there were, it would solve the halting problem, because we could take an algorithm (Turing machine), find its big-$\Theta$ complexity, then return true or false depending on if it was $\Theta (\infty)$.

For Big-O (upper bounds), there's technically a formula, since all functions are in $O(\infty)$. However, there's no way to find a tight upper bound, nor to test if an algorithm has a bound tighter than $O(\infty)$.

That said, there are certainly tools and heuristics for determining these things, as well as limited models of computation for which the problem is decidable.

For example, if you can express your routine using recursion, often you can find a recurrence relation for the running time, which you can solve to find the Big-O time. However, none of these techniques will work all the time.
> 3 votes

---
Tags: algorithms, algorithm-analysis, proof-techniques, runtime-analysis
---


# Question
Title: Significance of parameters in Tiny Mersenne Twister algorithm
I am trying to implement and optimize the Tiny Mersenne Twister (TinyMT) algorithm as required by an API I am developing with my team at work. The algorithm utilizes a C structure with 32-bit unsigned integers "mat1", "mat2", "tmat", and an array called "status" which is four 32-bit unsigned integers wide.

I am relatively new to the subject of random number generation; however, I have been able to teach myself a lot about the subject over the past couple of weeks. I know what the purpose of a seed is, different methods such as linear congruent, LSFR, GFSR, etc. So I've been doing my "homework" and researching the topic to the best of my ability (contrary to what the guys at Stack Overflow think). Unfortunately, the Mersenne Twister in general is extremely poorly documented and very few documents exist to explain the code and math side-by-side. The TinyMT's documentation is even worse, it's virtually non-existent! So developing accurate Doxygen comments for this part of the API is going to be tricky.

With that said, hopefully somebody more qualified than I can help me out here. What is the significance of the aforementioned parameters? What do they do, what do they mean, what do they stand for, etc? My guess would be as follows:

* mat1 - Matrix 1
* mat2 - Matrix 2
* tmat - Tempering Matrix
* status - 127 bit wide "seed" (where the last bit goes, I'm not sure)

Given that the user provides values for "mat1", "mat2", and "tmat," are there any precautions they need to take before supplying values for them? Again, this is for an API and its documentation, so I would like to be able to give the customers a good idea of what they need to use the RNG and hopefully make the lives of other fellow programmers easier. Thanks!

# Answer
> 4 votes
You can generate parameters for the PRNG using the provided program *tinymt32dc*. You should generate these parameters once and for all for each application. Each time you call the PRNG, you use the same parameters but a different seed. The reason that you don't want to vary the parameters is that generating them is (apparently) time consuming, while initializing the PRNG from just the seed is designed to be quick.

There might be some constraints on these parameters, but since you're not the designer of TinyMT, you're not aware of them. Instead, you should just use the provided program that generates legal parameters.

---
Tags: linear-algebra, randomized-algorithms, matrices
---


# Question
Title: Can a Turing machine decide if a LOOP program stops for the integer input 0
This is a question I found in a practice exam while I am preparing for my mid term exam.

The answer needs justification, either a pseudo code or a logical explanation why not.

What puzzled me about that question is that we already know that all LOOP programs terminate at some point, the question seems odd to me.

Any references about LOOP and/or WHILE programs are welcome. Our professor didn't give much.

# Answer
> 2 votes
If all LOOP programs terminate that there is a Turing machine that decides whether a LOOP program stops on input 0: it just always accepts. For WHILE programs the picture is rather different - I'll let you find out yourself. (Perhaps your professor really meant WHILE programs.)

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


# Question
Title: How hard is finding restricted assignment of 3-SAT satisfying $7/8$ of the clauses?
The PCP theorem implies (with other results) that there is no polynomial time algorithm for MAX 3SAT to find an assignment satisfying $7/8+ \epsilon$ clauses of a satisfiable 3SAT formula unless $P = NP$.

There is a trivial polynomial time algorithm that satisfies $7/8$ of the clauses. How hard is it to find an assignment that satsfies at least $7/8$ of the clauses but no more than $7/8 +\epsilon $ for some $\epsilon \gt 0$? Is this task still $NP$-hard?

# Answer
The PCP theorem states that for every $\delta \> 0$, it is NP-hard to decide whether a 3CNF is satisfiable or at most $(7/8+\delta)$-satisfiable. Take such a formula $\varphi$ and add to it lots of copies of $(a \lor b \lor c) \land \cdots \land (\lnot a \lor \lnot b \lor \lnot c)$, where $a,b,c$ are new variables (by $\cdots$ I mean eight clauses, exactly seven of which are always satisfied). Suppose these clauses take up $(1-\epsilon)$ of the new 3CNF. This replaces the original $1$ vs. $7/8 + \delta$ to $\epsilon + (1-\epsilon)7/8$ vs. $(7/8+\delta)\epsilon + (1-\epsilon)7/8$, that is $7/8 + \epsilon/8$ vs. $7/8 + \delta\epsilon$. That's not exactly what you wanted since $\delta \neq 0$, but it's pretty close.
> 2 votes

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


title: How does a race condition work?

text:
# Question
Title: How does a race condition work?
When two threads try to access the same resources at exactly the same time how does the computer decide which one gets the resource, or is it just decided at random?

# Answer
On a single-processor system, it is impossible for two threads to access the same location simultaneously. Rather, if the threads access the same data outside of a critical section, it's possible for their execution to become interleaved, in which case the access order is undefined. Execution is concurrent and you might call the result "random", in that nothing obvious affects the choice of one thread's code over another's. Of course, the scheduler is making the choice somehow, but it's fairly opaque in terms of ordering for access to thread-shared memory.

In multiprocessor/multicore/distributed applications, the notion of ordering is a little hazier. We can define the happens-before partial relation based on causation of signals and use this to define time stamps that can be used for coordinating events across sites. Unrelated events are called concurrent, and any processes which care about the order of concurrent events need to agree amongst themselves. Consistency is a well-studied problem in shared-memory distributed systems. If sites request access to shared memory over some medium (bus, interconnect, etc.) then the medium access protocol will, in an opaque fashion, determine which thread gets access first. Like scheduling, the result here may appear "random", since different decisions can be made on different executions.
> 5 votes

# Answer
a "race condition" is actually a more technical/specialized term than the sense you are using in a generic way, it does not really simply mean that two threads are accessing the same resource at the same time. it is in general used to refer to subtle programming defects where the results of parallel thread processing can unintentionally vary based on thread execution order, when the intention is that there is not a variation. in other words imagine two threads A, B that do some same "operation". and the results of that "operation" are "different" when thread A runs before thread B versus when thread B runs before thread A.

in a multithreaded system one cannot assume a particular thread execution order unless it is fixed by thread ordering mechanisms (eg say a multithreading synchronization system like a semaphore etcetera).

the general study of how threads are scheduled is in scheduling theory. the basic strategies are known as scheduling disciplines. eg a simple strategy is FIFO or "first come first served".
> 1 votes

---
Tags: terminology, concurrency
---


title: r-regular graph and hamiltonian path

text:
# Question
Title: r-regular graph and hamiltonian path
I am having some issues proving a problem I am working on. I have been sketching out examples but the proof is not jumping out at me.

Question: Let $G = (V,E)$ be an undirected $r$-regular graph (that is each vertex has a degree of $r$) for some $0 \< r \< n$, where $|V| = n \> 1$. Prove that either $G$ or its complement $G^\*$ has a hamiltonian path.

Now the reason it's asking for $G$ or $G^\*$ is because if it's not a connected undirected graph then taking the complement will make it connected.

So lets assume that it's a connected $r$-regular graph. We start at a vertex $v$. From this vertex we can visit up to $r$ adjacent vertices. So we visit one of them, say $u$, and from there we have $r-1$ vertices to choose from because we do not want to go back to vertex $v$.

Now I am trying to formulate a proof by going from vertex to vertex until all vertices are visited exactly once (hamiltonian path). But I do not see how to formulate the proof. Somehow each new vertex I visit will always have an uninformed neighbour until I reach the final vertex on the path.

Am I on the right track?

# Answer
You are underselling the "G or G\*" part. This suggests a proof of the form:

* "assume G isn't Hamiltonian ... prove G\* must be". So try that route.

To give a further hint, I remind you of the Dirac theorem:

* If a connected graph G has n \>= 3 vertices and the degree of each vertex is at least n/2, then G has a Hamiltonian cycle (if it has a cycle, obviously it also has a path, you just remove an edge from the cycle).
* Additionally, an n-vertex r-regular graph with r \>= n/2 must be connected (assume it is not connected - what is the minimum number of vertices each connected component must have? Can there be more than 1 such component?)

I think these should give you the idea how to prove it for n \>= 3.

Then it just remains to prove it for n = 2, which is trivial (the only reason it isn't included in above theorem is that it only has a path, not a cycle).

Note: because I am not sure a complement is even defined on a non-simple graph, I am assuming G is simple. But if it wasn't, the statement-to-prove couldn't be true, even if you defined a complement in any way that makes sense - what would be the complement of this graph, and how could either have a Hamiltonian path:
> 4 votes

---
Tags: graphs, proof-techniques
---


# Question
Title: Is oracle computer capable of doing infinite loops?
Solve this problem: "build an infinite binary oscilator"

With a Turing Machine we can solve it

```
a=False
While True:
   a=not a
   print a,

```

then output will be

```
True False True False True False ...

```

(for ever)

I think an oracle can't do it, because its definition, it could solve in "one operation", but here there's not halting as a request of the problem statement. Is it true?

**EDIT**: Oracle definition from wikipedia

".. an *oracle machine* is an abstract machine used to study decision problems. It can be visualized as a Turing machine with a black box, called an *oracle*, which is able to decide certain decision problems in a single operation. The problem can be of any complexity class. Even undecidable problems, like the halting problem, can be used."

So what if that TM ask its black box oracle to create an infinite binary oscilation?

```
   1- oracle black box can't do infinite loops
   2-TM can't ask that problem to oracle
   3- Does it return a string with a source code as answer? weird
   4-or other options...

```

# Answer
I'm with Yuval Filmus on this. *Oracle* seems to be the wrong characterization. An oracle is normally thought of as something that can decide a problem asymptotically faster than a Turing machine (or at all, for undecidable problems).

What you're describing sounds, perhaps, more like *hypercomputation*. Consider, for instance, a *Zeno machine*. It could output "True" after 1 minute, "False" after an additional 30 seconds, "True" 15 seconds later, and so on, completing the task you set out for it in two minutes.
> 2 votes

# Answer
A simple model that is close to what you need is a TM with an oracle that receives its (finite) input on a *semi-infinite query tape* and puts the answer on an *semi-infinite oracle result tape* (accessible by the TM control: after the oracle produces its (possibly infinite) result, the TM head on the oracle result tape is moved on the leftmost cell).

An oracle "Doing an infinite loop" is equivalent to an oracle that writes an infinite sequence of 0-1 on the oracle result tape.
> 1 votes

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


title: Team construction in tri-partite graph

text:
# Question
Title: Team construction in tri-partite graph
The government wants to create a team with one *alchemist*, one *builder*, and one *computer-scientist*.

In order to have good cooperation, it is important that the 3 team-members like each other.

Therefore, the government gathers $k$ candidates of each profession, and creates their "liking" graph. This is a tri-partite graph, where there is an edge between $a$ and $b$ iff $a$ likes $b$.

(Note that the "like" relation is symmetric but not transitive, i.e.: if $a$ likes $b$ then $b$ likes $a$, but if $a$ likes $b$ and $b$ likes $c$, then not necessarily $a$ likes $c$).

Is this always possible to create a team? Of course not. For example, it is possible that no alchemist likes any builder.

However, suppose the "liking" graph has the following property: *in each group of 3 alchemists and 3 builders, there is at least a single alchemist-builder pair that like each other; ditto for alchemists-computerists and builders-computerists*.

Given this property, is this always possible to create a team where all 3 members like each other? If so, what is the minimum number of candidates of each type ($k$) that the government will have to gather?

I would like to both find k and prove that it is the minimum.

A possibly related sub-question is: in a group of $k$ alchemists and $k$ builders, what is the minimum number of pairs that like each other? For $k=3$, by the assumption of the question, that number is 1. What about $k\>3$?

A third question is: what is the name of this kind of problems?

# Answer
The summary so far (as CW).

Yuval Filmus rephrased the question in more conventional terms, as

> What is the minimal $k$ such that for every red/blue-coloring of the edges of $K\_{k,k,k}$ (the complete 3-partite graph with $k$ vertices in each partition) there is either a red triangle or a blue $K\_{3,3}$?

Erel proved that the lower bound on $k$ is at least 5, and then using a SAT formulation that $k \ge 8$.

frafl showed that the upper bound on $k$ is at most 15. Aravind sketched a nice argument for a better upper bound.

Here is a more detailed form of Aravind's argument.

If a vertex $u$ in partition $A$ is red-connected to 3 vertices $S$ in partition $B$ and 3 vertices $T$ in partition $C$, then there is either a red triangle involving $u$ and one vertex from each of $S$ and $T$, or otherwise $S\cup T$ induces a blue $K\_{3,3}$. So no vertex can have more than 2 red-connected neighbours in both of its neighbour partitions.

Hence every vertex has at least $k-2$ blue-connected neighbours in at least one of its neighbour partitions. Let $S$ be the vertices in $A$ which have at least $k-2$ blue-connected neighbours in $B$, and $T$ be those vertices in $A$ which have at least $k-2$ blue-connected neighbours in $C$; note that $A = S\cup T$. If $S\cap T$ is non-empty, then switching colours yields a contradiction since $k\ge 5$. So assume $S$ and $T$ are disjoint. In fact, each vertex in $S$ must be blue-connected to at most 2 vertices in $C$ (so red-connected to at least $k-2$ vertices in $C$), and each vertex in $T$ must be blue-connected to at most 2 vertices in $B$ (and red-connected to at least $k-2$ vertices in $C$).

Now $k \ge 6$ so without loss of generality suppose that $S$ contains a subset $S'$ with at least 3 vertices. They are each blue-connected to at least $k-2$ vertices in $B$, so these neighbourhoods must have a common intersection $U$ with at least $k-6$ vertices. If $k\ge 9$, then $U$ contains at least 3 vertices, so $S'\cup U$ induces a blue $K\_{3,3}$.

This shows that $k\ge 9$ is enough to always meet the conditions, and 9 is therefore an upper bound on the desired quantity.

What remains is to either demonstrate a counterexample with $k=8$ (which would show that the desired quantity is 9), or to show that $k=8$ is always enough to guarantee a red triangle or a blue $K\_{3,3}$ (which would show it is 8).
> 3 votes

# Answer
An upper bound on the first question is $k\leq 15$: Take a set of $5$ $a$s $A=\\{a\_1,\dots,a\_5\\}$, $5$ $b$s $B\_1=\\{b\_1,\dots,b\_5\\}$ and $5$ $c$s $C\_1=\\{c\_1,\dots,c\_5\\}$. We know that at most 2 of the $a$s don't have a neighbor among the $B$s, otherwise we found a complement of a $K\_{3,3}$, which is forbidden. The same holds for $a$s and $c$s. Thus there must be one $a\_1'$ that has a neighbor among both sets. We call these neighbors $b\_1'$ and $c\_1'$ respectively.

We now fix the set $A$ and consider $10$ additional pairs of sets of $b$s and $c$s $(B\_i,C\_i)\_{i\in\\{2,\dots,11\\}}$ with $$B\_i=\\{b\_{i+4}\\}\cup(B\_{i-1}\setminus \\{b\_{i-1}'\\})$$ and $$C\_i=\\{c\_{i+4}\\}\cup(C\_{i-1}\setminus \\{c\_{i-1}'\\})$$ and choose $b\_i'$ and $c\_i'$ such that they're both neighbors of the same $a\_i' \in A$ (which all exist by the observation above).

Now at least $3$ pairs of sets agree on the same $a$ by the pigeonhole principle, i.e. there is an $a\_l\in A$ and pairwise different $m\_1,m\_2,m\_3 \in \\{1,\dots,11\\}$ such that $a\_l = a\_{m\_1}' = a\_{m\_2}' = a\_{m\_3}'$. Now $b\_{m\_p}'$ and $c\_{m\_p}'$ are neighbors of $a\_l$ for $p\in\\{1,\dots,3\\}$. Thus for some $p,p'\in \\{1,2,3\\}$ the set $\\{a\_l,b\_{m\_p}',c\_{m\_{p'}}'\\}$ induces a triangle of friends.
> 4 votes

# Answer
Following András Salamon's comment, I decided to pose my question as a SAT problem. I created a Javascript application that takes as input the number of candidates per profession ($k$), and generates a CNF formula that defines a graph with k candidates per profession, that contains an edge between each two triples, but does NOT contain a triangle of candidates.

If that formula is satisfied, it means that $k$ is too small to guarantee that there is always a feasible team. If that formula is not satistied, it means that $k$ is large enough since there is always a feasible team.

I created MiniSAT input files for $k=3..8$. For $k\<=7$, MiniSAT returned in less than a second, saying that it is satisfiable (i.e. k is too small). Here is the assignment MiniSAT found for $k=7$. This means that 8 is a lower bound on the number of required candidates (better than the lower bound of 7 that I found in the previous answer).

For $k=8$, I started MiniSAT several minutes ago, and it is still running. The input file contains 192 variables and 9920 clauses. I don't know how much time it will take it to finish.

Based on the slowness of computation (and assuming I don't have a bug in the implementation), I conjecture that 8 or at most 9 candidates are enough. But I still wait to see what MiniSAT says.

Here is the current output:

```
============================[ Problem Statistics ]=============================
|                                                                             |
|  Number of variables:           192                                         |
|  Number of clauses:            9920                                         |
|  Parse time:                   0.01 s                                       |
|  Simplification time:          0.03 s                                       |
|                                                                             |
============================[ Search Statistics ]==============================
| Conflicts |          ORIGINAL         |          LEARNT          | Progress |
|           |    Vars  Clauses Literals |    Limit  Clauses Lit/Cl |          |
===============================================================================
|       100 |     192     9920    86208 |     3637      100     16 |  0.003 % |
|       250 |     192     9920    86208 |     4001      250     22 |  0.003 % |
|       475 |     192     9920    86208 |     4401      475     25 |  0.003 % |
|       812 |     192     9920    86208 |     4841      812     29 |  0.003 % |
|      1318 |     192     9920    86208 |     5325     1318     31 |  0.003 % |
|      2077 |     192     9920    86208 |     5857     2077     32 |  0.003 % |
|      3216 |     192     9920    86208 |     6443     3216     35 |  0.003 % |
|      4924 |     192     9920    86208 |     7088     4924     34 |  0.003 % |
|      7486 |     192     9920    86208 |     7796     3907     35 |  0.003 % |
|     11330 |     192     9920    86208 |     8576     7751     36 |  0.003 % |
|     17096 |     192     9920    86208 |     9434     4866     39 |  0.003 % |
|     25745 |     192     9920    86208 |    10377     8762     36 |  0.003 % |
|     38719 |     192     9920    86208 |    11415     6081     39 |  0.003 % |
|     58180 |     192     9920    86208 |    12557     8338     35 |  0.003 % |
|     87372 |     192     9920    86208 |    13812    12272     37 |  0.003 % |
|    131161 |     192     9920    86208 |    15194     7495     36 |  0.003 % |
|    196845 |     192     9920    86208 |    16713    12107     38 |  0.003 % |
|    295371 |     192     9920    86208 |    18384     9989     32 |  0.003 % |
|    443160 |     192     9920    86208 |    20223    10152     40 |  0.003 % |
|    664843 |     192     9920    86208 |    22245    18854     37 |  0.003 % |
|    997368 |     192     9920    86208 |    24470    15595     40 |  0.003 % |
|   1496156 |     192     9920    86208 |    26917    15102     34 |  0.003 % |
|   2244338 |     192     9920    86208 |    29608    19091     42 |  0.003 % |
|   3366612 |     192     9920    86208 |    32569    16905     35 |  0.003 % |
|   5050023 |     192     9920    86208 |    35826    21640     37 |  0.003 % |
|   7575139 |     192     9920    86208 |    39409    34856     39 |  0.003 % |
|  11362814 |     192     9920    86208 |    43350    20735     38 |  0.003 % |
|  17044326 |     192     9920    86208 |    47685    35456     42 |  0.003 % |
|  25566595 |     192     9920    86208 |    52453    43639     34 |  0.003 % |
|  38349998 |     192     9920    86208 |    57699    48290     42 |  0.003 % |
|  57525103 |     192     9920    86208 |    63469    22810     40 |  0.003 % |
|  86287761 |     192     9920    86208 |    69816    55424     36 |  0.003 % |
| 129431749 |     192     9920    86208 |    76797    69548     43 |  0.003 % |

```

After additional 4 hours, still no result:

```
| 194147731 |     192     9920    86208 |    84477    67509     38 |  0.003 % |
| 291221704 |     192     9920    86208 |    92925    61375     34 |  0.003 % |

```
> 4 votes

# Answer
Upper bound of 9:

I am using the characterization of Yuval Filmus.

Suppose that a vertex in A has at least 3 red neighbors in both B and C. Then either there is a red edge across the two neighbor-sets, which results in a red triangle or there is a blue $K\_{3,3}$.

So if k\>=6, we obtain that there are three vertices in A each of which have at most 2 red neighbors in B (w.l.o.g- in B). Thus, these 3 vertices must have at least k-6 blue neighbors in common. If $k \geq 9$, we get a blue $K\_{3,3}$.
> 3 votes

# Answer
As a lower bound, here is a proof that 5 candidates of each profession are not enough. Suppose there are $n=5$ candidates numbered $i=0..4$, with the following relations:

* Alchemist $i$ likes Builder $i$
* Builder $i$ likes Computerist $i$
* Computerist $i$ likes Alchemist $(i+1)\ mod\ n$.

By the pigeonhole principle, in every group of 3 alchemists and 3 builders there is at least 1 pair that like each other (ditto for the other professions). However, the entire graph is a single circle of length 15, and there is no circle of length 3.

The construction can be extended for $n=6$, by adding the following large circle:

* $A\[i\]$ likes $B\[(i+1)\ mod\ n\]$
* $B\[i\]$ likes $C\[(i+1)\ mod\ n\]$
* $C\[i\]$ likes $A\[(i+2)\ mod\ n\]$

Unfortunately, the construction doesn't work for $n\>6$. There is still a wide gap between this lower bound and frafl's upper bound of 15.
> 2 votes

---
Tags: graphs, combinatorics
---


title: Visualizing a Non Deterministic Decider

text:
# Question
Title: Visualizing a Non Deterministic Decider
I know that we can visualize a Non deterministic TM as a TM which splits into multiple copies of itself whenever it sees a non deterministic path (Yes, I also know that this is just a visualization and is usually used by beginners like me for understanding non determistisism).

Further, I also know that a Decider is a TM that halts on all possible inputs.

Now, my question is how can I visualize a Non determistic Decider? Does a non-determistic decider mean a TM where

1. All the copies must halt, (OR)
2. At-least one copy halts.

Kindly explain in detail why so. Thanks.

# Answer
> 5 votes
For a nondeterministic decider the answer is *At-least one "copy" halts on a "yes"/"no" state*; copy-paste from another answer:

1. for a Nondeterministic Turing machine (NDTM) processing an input $x$ there can be infinite computations (paths); some of them will halt on the accept state $q\_Y$, some will halt on the reject state $q\_N$, some will run forever;
2. a string $x$ is *accepted* by a Nondeterministic Turing machine if **at least one** of its computations halts on the accepting state $q\_Y$;
3. we say that "$M$ accepts $x$ in $m$ steps" if $M$ accepts $x$ and $m$ is the length of the shortest accepting computation on input $x$;
4. a language $L\_M$ recognized by a NDTM $M$ is the set of $x$ accepted by $M$ (this is independent of whether $N$ is a decider or not);
5. the *definition* of time complexity for a Nondeterministic Turing Machine $M$ is slightly different from the definition of time complexity for a Deterministic Turing Machine:

$T\_M(n) = max ( \\{1\\} \cup \\{ m \\; : \\; $ there is an $x \in L\_M$ such that $|x|=n$ and $M$ accepts $x$ in $m$ steps $\\})$
6. we say $M$ is a **decider** if $T\_M(n)$ is computable.

See Garey&Johnson, "Computers and Intractability"

# Answer
> 4 votes
My textbook (Sipser, 3rd edition, 2012, p. 180) explicitly states that "we call a nondeterministic Turing machine a decider if all branches halt on all inputs". So if there are strings on which the NDTM doesn't halt, or if there is even a single computation path on which the NDTM does not halt, it is *not* a decider. According to this definition, the correct answer would be *All the copies must halt*

This is in contrast to what Vor answered, but I'm not allowed to comment on his answer. Also, I don't see how Vor answers the question; it only states when a TM recognizes a language or accepts its input. The question was about a TM being a decider, which requires a slightly different behavior.

---
Tags: turing-machines, undecidability, nondeterminism
---


# Question
Title: circle packing algorithm used by Percolator
I was admiring this rendition of the Mona Lisa from quasimondo's Flickr account. He says:

> Combining circle packing with data visualization. The pie charts show the distribution of the dominant colors under the circle area.
>
> The circle packing technique used here is a combination of an image segmentation with a distance transform and the first one who came up with it is John Balestrieri: www.flickr.com/photos/tinrocket/

I have traced it to an app called Percolator

How are such circle packings calculated? How are the pie charts calculated from the image?

# Answer
Since I created this I probably can explain it best ;-):

* the first step is to calculate an image segmentation which will combine small areas of similar colors into bigger chunks. The tolerance values of that segmentation will influence how big the biggest circles can become (higher tolerance =\> bigger areas =\> bigger circles)
* You proceed by processing each of the found areas individually: calculate an euclidean distance map for the area. This map will tell for every pixel the distance to the nearest edge. Find the maximum value in that map. This is the pixel that has the furthest distance from an edge. Conveniently that distance will be the radius of the biggest circle that you can fit into that area. Add that circle (center position + radius) to a list. Now you subtract that circle from the area - subtract in this case means that if the original area is all white pixels surrounded by a black border you simply draw a black circle over it. Recalculate the distance map for the remaining white area pixels repeat the above process until there are no more distances bigger than some chosen threshold (the smallest radius you want to display).
* the last part is to calculate the pie charts for all the circles you have collected. In order to do that you accumulate all the pixel colors of the original image that are lying under a circle and calculate a color quantization for them. In the Mona Lisa example all the colors are reduced to the 7 most representative. In order to calculate the pie ratios you simply count for each of the 7 representative colors how many of the original colors are their nearest neighbors. The only thing left to do is to draw a pie chart using the ratios and colors at the stored circle position.
> 12 votes

---
Tags: algorithms, computational-geometry, discrete-mathematics, image-processing
---


# Question
Title: Example of a false proposition when assuming Type : Type
In Type Theory if one allows Type to be a member of itself, it makes the theory inconsistent. I understand it by analogy to Russel's paradox in Set Theory, but would prefer to see it done in Type Theory. Is there a short example of the equivalent in Type Theory?

# Answer
The relevant literature is the following:

Thierry Coquand *A new paradox in type theory* (link). He describes his paradox in a system that is somewhat weaker than

```
Type : Type

```

But that can be easily transported to the above. The main idea is taking Reynolds proof that there are no models of system F in set theory. That proceeds by building an initial algebra of the form:

$$ A\simeq (A \rightarrow \mathrm{2}) \rightarrow \mathrm{2}$$

Where $\mathrm{2}$ is a set with 2 elements, and deriving a contradiction by a cardinality argument. Coquand shows

1. You can carry out this reasoning in the above type theory
2. There *is* a model of system F in that theory. This yields a contradiction.

The second article is from Antonius Hurkens, and is titled *A simplification of Girard's paradox* (link). The proof involves a construction of the "type of all well-founded types". I must admit that the general idea seems clear, but the details are quite devilish.

I'm afraid there is no simple, easy to understand contradiction in $\mathrm{Type} : \mathrm{Type}$. However the proof-terms obtained from the contradiction are relatively tractable: only a few lines are sufficient to define them.

Alexandre Miquel, in his thesis dissertation, showed that one could construct a model of naive set theory in these inconsistent type systems by using a pointed graph interpretation of sets. He can then simply apply Russel's paradox directly. Unfortunately the model construction takes a bit of work, and the dissertation is in French.
> 10 votes

---
Tags: type-theory
---


title: Complexity of taking mod

text:
# Question
Title: Complexity of taking mod
This seems like a question that should have an easy answer, but I don't have a definitive one:

> If I have two $n$ bit numbers $a, p$, what is the complexity of computing $a\bmod p$ ?

Merely dividing $a$ by $p$ would take time $O(M(n))$ where $M(n)$ is the complexity of multiplication. But can $\bmod$ be performed slightly faster ?

# Answer
Shoup (Section 3.3.5, Theorem 3.3, p. 62) gives a bound for computing the residue $r$ in time $O(n\log q)$ where $a = q\cdot p +r$ and $\log a = n$.

I guess that if $p$ and $a$ are both roughly $n$ bit numbers, then $q$ (and hence $\log q$) should be rather small, giving $O(n)$.

If $a$ is an $n$-bit number, and $p$ is relatively small, then the multiplication approach should be faster.
> 12 votes

---
Tags: algorithms, number-theory
---