# Question
Title: A logic function that is true iff the first operand is less than the second operand
In my computer organization class I have been given a series of problems. One I'm stuck on currently is below:

> Assume that $X$ consists of 4 bits, $x\_3 x\_2 x\_1 x\_0$, and $Y$ consists of 4 bits, $y\_3 y\_2 y\_1 y\_0$. Write logic functions that are true if and only if
>
> (a) $X \< Y$, where $X$ and $Y$ are thought of as unsigned binary numbers.
>
> (b) $X \< Y$, where $X$ and $Y$ are thought of as signed (two’s complement) numbers.
>
> (c) $X = Y$.
>
> (d) Use a hierarchical approach that can be extended to larger numbers of bits. Show how can you extend it to 8-bit comparison (that is, if $X$ and $Y$ are 8-bit numbers, how to implement the above three comparisons).

For all of them I understand the what makes each case true. I'm even aware of the simple method of writing a truth table and listing out the logic functions that make each case true, however that approach would make a table 256 rows tall.

I'm stuck a bit on how to write out the logic. The real confusion actually comes from the TA in the class. He gave an example using 3-bit numbers. I believe he was using the case of $X \< Y$ still. His solution was: $(x\_2 \\;\mathrm{XOR}\\; y\_2)' \cdot (x\_1 \\;\mathrm{XOR}\\; y\_1)' \cdot (x\_0' \cdot y\_0)$

Is this the full answer for the case of 3-bit numbers for part (a)? I understand it this solution, but I feel there is more. For example, $(x\_2 \\;\mathrm{XOR}\\; y\_2)'$ checks if the most significant bits are equal, which gives reason to move onto the next portion of the function, but if $x\_2$ is 0 while $y\_2$ is 1, then that means $x$ is smaller and the function needs to become true, but I don't see how that is a possible outcome with that example solution.

# Answer
I haven't heard back from my professor or my TA yet, nor has anyone posted a solution yet, but I'm been thinking long and hard. It was a bit of a rush when the TA went over his solution, but maybe I wrote down a partial solution. So going off of that idea, I came up with:

```
Problem 4:
a.  x < y iff unsigned:
    x3’ . y3
+   (x3 XOR y3)'  .  x2’ . y2
+   (x3 XOR y3)'  .  (x2 XOR y2)'  .  x1’ . y2
+   (x3 XOR y3)'  .  (x2 XOR y2)'  .  (x1 XOR y2)'  .  x0’ . y0
b. x < y iff signed:
    x3 . y3’
+   (x3 XOR y3)'  .  x2’ . y2
+   (x3 XOR y3)'  .  (x2 XOR y2)'  .  x1’ . y2
+   (x3 XOR y3)'  .  (x2 XOR y2)'  .  (x1 XOR y2)'  .  x0’ . y0
c. x = y iff
    (x3 XOR y3)'  .  (x2 XOR y2)'  .  (x1 XOR y2)'  .  (x0 XOR y0)'
d.
Assume x,y consist of i bits.
a.  xi-1’ . yi-1
+    (xi-1 XOR yi-1)'  .  xi-2’ . yi-2
+    …
+   (xi-1 XOR yi-1)'  .   . . .    .  xi-i’ . yi-i
b.  xi-1 . yi-1’
+    (xi-1 XOR yi-1)"  .  xi-2’ . yi-2
+    …
+    (xi-1 XOR yi-1)'  .   . . .    .  xi-i’ . yi-i

c.  (xi-1 XOR yi-1)'  .   . . .    .  (xi-i XOR yi-i)'

Assume i = 8.
a.  x8-1’ . y8-1
+    (x8-1 XOR y8-1)'  .  x8-2’ . y8-2
+    …
+    (x8-1 XOR y8-1)"  .   . . .    .  (x8-7 XOR y8-7)'  .  x8-8’ . y8-8
b.  x8-1 . y8-1’
+    (x8-1 XOR y8-1)'  .  x8-2’ . y8-2
+    …
+    (x8-1 XOR y8-1)'  .   . . .    .  (x8-7 XOR y8-7)'  .  x8-8’ . y8-8

c.  (x8-1 XOR y8-1)'  .   . . .    .  (x8-7 XOR y8-7)'  .  (x8-8 XOR y8-8)'

```

If you see anything wrong with this solution, let me know.
> 0 votes

---
Tags: logic, boolean-algebra
---


# Question
Title: Help with understanding Simulated Annealing algorithm
I'm trying to wrap my head around it, but no matter what I read, I still can't fully understand it.
I tried to read a little bit about the annealing process in physics, but I have no background whatsoever in physics, let alone in thermodynamics, so I couldn't understand what is it exactly, and how it fits into the algorithm.
Here is the algorithm:

In the Hill Climbing algorithm, the reasoning can be easily described: Of all the successors of the current state - choose the highest-valued. But in Simulated Annealing... well, I can see what the algorithm does, I just don't understand the reasoning behind it:
1. It starts a timer.
2. It chooses a random successor.
3. It evaluates how "far away" the randomly chosen successor from current.
4. If the successor is indeed a "progress in the right direction" ($\Delta E \> 0$) then we move ahead towards the direction of successor; otherwise, we move ahead towards the direction of successor with some (odd) probability that depends on the timer(?).

Why is randomly choosing a successor better then the Hill Climbing method?
Can someone please explain the reasoning behind it?
Do I really have to understand the annealing process? If so, can someone please explain it in layman terms?

# Answer
The variable $T$ is not a timer but the *temperature*. It starts very high, making it more likely that transitions are taken, and then slowly cools. It's called annealing due to the metallurgical technique of the same name.

Simulated annealing handles one problematic aspect of the hill climbing algorithm, namely that it can get stuck at a local optimum which is not a global optimum. Instead of getting stuck, simulated annealing offers a way out: if the proposed change only marginally deteriorates the objective function, then with some reasonable probability with make it anyway. This way we can escape local optima.

As the process proceeds, we increase the threshold of making unfavorable changes by decreasing the temperature; when the temperature is zero, simulated annealing is the same as hill climbing (and when the temperature is infinite, it is the same as a random walk). The idea is that at first we need to escape local optima more vigorously, but eventually we settle at a good solution which does not require as much tinkering with (except for hill climbing).

You mention that hill climbing always chooses the best neighbor, but this is only one version of the algorithm, and not necessarily the best one. In other versions we choose an improving neighbor in some other fashion. I don't have much intuition which approach is better, though you are right that choosing the best neighbor sounds like a reasonable heuristic.
> 2 votes

---
Tags: constraint-satisfaction
---


# Question
Title: Why is this sequence not acceptable for this DFA?
Why is the sequence 1100101 not acceptable for this DFA? Is it because once it reaches the final state 'q3' it can't go back to 'q1'?

# Answer
> 2 votes
Upon reading the word 1100101, the DFA reaches the non-accepting state $q\_2$. There's nothing more to it.

A DFA accepts a word $w$ if when starting for the initial state and following the transitions according to $w$, the DFA reaches a state $q$ which is accepting. If it reaches a state which is not accepting, it rejects $w$. This is the definition of acceptance for DFAs.

---
Tags: automata, finite-automata
---


title: Poly-time reduction: D and D Comp

text:
# Question
Title: Poly-time reduction: D and D Comp
Looking at the Independent Set problem and its complement, I want to show that IS is poly-time reducible to its complement, however I am struggling on coming up with the reduction function.

I will define its complement for further clarity, does every subset such that its size is at least $k$ in $V$ contain at least one edge between its vertices? My intuition is below.
$$f(G, k) = (G, i-k),$$ where $i = |V|$?

# Answer
> 1 votes
Independent set and its complement are **NP**-complete and **co-NP**-complete, respectively. If you found a polynomial-time reduction between those two problems, you'd have proven that **NP$\\,=\\,$co-NP**, resolving one of the biggest open problems in theoretical CS.

---
Tags: complexity-theory, np-complete, reductions, decision-problem
---


title: Tallest Person Average Memory Updating?

text:
# Question
Title: Tallest Person Average Memory Updating?
We ran into a problem that was mentioned in an interview 2 days ago. Can you help us with any idea or hint?

A sequence of $n$ people, $\langle\\,p\_1,p\_2,\dotsc p\_n\\,\rangle$ enter a room. We want to find the index, $i$, of the tallest person in the room. We have one variable for saving that index, which is updated when we see a person who is taller than the maximum height so far. We want to calculate the average number of times our variable is updated. For simplicity, assume that $p$ is a permutation of $\\{1, 2, \dotsc, n\\}$

Short answer: it is close to $\ln n$. (i.e: natural logarithm)

How can one solve such a question?

# Answer
> 4 votes
Let $T(n)$ denote the total number of updates to the variable when $n$ people have entered the room. For example, with $n=3$ there will be $3!=6$ possible orders where the heights are $1, 2, 3$. Notice that once the height 3 person enters, no further updates will occur, so let's group the six possible arrangements by when the height 3 person enters: $$\begin{array}{ccc} \mathbf{3}21 & \mathbf{3}12 \\ 1\mathbf{3}2 & 2\mathbf{3}1 \\ 12\mathbf{3} & 21\mathbf{3} \\ \end{array}$$ For each of these arrangements, let's count the number of updates we have to make *before* we see the tallest person. In the two arrangements where the height-3 person arrives first, there are 0 earlier updates. In the second row above, there will be 1 update we have to make before the tallest person arrives and in the third row there will be either 1 or two updates before the tallest person arrives: arrangement $12\mathbf{3}$ will require 2 updates (one for the height-1 person and another for the height-2 person and the arrangement $21\mathbf{3}$ will require 1 update, for the height-2 person. In this $n=3$ case, then, we'll have $0+2+3$ total prior updates (0 in row 1, 2 in row 2, and 3 in row 3). To this add the $3!=6$ updates for the tallest person, giving us a total $T(3)=5+6=11$.

Now let's look at the general case for $n$ people. As we did above, let's group the $n!$ possible arrangements by when the height-$n$ person arrived. Denote this tallest person by $X$ and the rest of the people by dots. As we did above, we'll defer counting the last update until later.

We'll have these possibilities, each of which can happen in $(n-1)!$ ways: $$\begin{array}{cc} \text{arrival of }X & \text{arrangement}\\ 1 & X\circ\dotsc\circ \\ 2 & \circ X\circ\dotsc\circ \\ 3 & \circ\circ X\circ\dotsc\circ\\ \dotsm & \dotsm \\ n & \circ\dotsc\circ X \end{array}$$

For each row above we'll count the total updates before the tallest person arrives: Obviously if the tallest person arrives first, we'll have no prior updates, so the first row above will give a total count of 0. Each of the following rows will look like this: $$ \underbrace{\circ\dotsc\circ}\_k\ X\ \underbrace{\circ\dotsc\circ}\_{n-1-k} $$ The first set of $k$ dots can be filled with the heights $\\{1, 2, \dotsc, n-1\\}$ and there are $\binom{n-1}{k}$ ways to choose these sets, each of which will contribute $T(k)$ updates. The last set of $n-1-k$ dots can be filled with the remaining numbers in $(n-1-k)!$ ways. Thus each row in the table will contribute $$ \binom{n-1}{k}T(k)(n-1-k)! $$ to the total of prior updates. Adding these and including the $n!$ updates for the tallest person we have the recurrence relation $$\begin{align} T(n) &= n! + \sum\_{k=1}^{n-1}\binom{n-1}{k}T(k)(n-1-k)!\\ &= n!+ \sum\_{k=1}^{n-1}\frac{(n-1)!}{k!(n-1-k)!}T(k)(n-1-k)!\\ &= n!+ \sum\_{k=1}^{n-1}\frac{(n-1)!}{k!}T(k)\\ &= n!+ (n-1)!\sum\_{k=1}^{n-1}\frac{T(k)}{k!}\\ \end{align}$$ Divide both sides by $n!$ to get $$ \frac{T(n)}{n!} = 1 + \frac{1}{n}\sum\_{k=1}^{n-1}\frac{T(k)}{k!} $$ and remember that the average number of updates, $U(n)=T(n)/n!$ which gives us. $$ U(n) = 1 + \frac{1}{n}\sum\_{k=1}^{n-1}U(k) $$ Now we'll find a simple closed form for this: $$\begin{align} U(n) &= 1+\frac{1}{n}\sum\_{k=1}^{n-1}U(k)\\ &= 1+\frac{1}{n}\left(\sum\_{k=1}^{n-2}U(k)\right)+\frac{1}{n}U(n-1) &\text{pulling out the last term}\\ &= 1+\frac{n-1}{n}\left(\frac{1}{n-1}\sum\_{k=1}^{n-2}U(k)\right)+\frac{1}{n}U(n-1)\\ &= 1+\frac{n-1}{n}(U(n-1)-1)+\frac{1}{n}U(n-1) & \text{definition of }U(n-1)\\ &= U(n-1)\left(\frac{n-1}{n}+\frac{1}{n}\right)+\left(1-\frac{n-1}{n}\right)\\ &= U(n-1) + \frac{1}{n} \end{align}$$ Whaddya know? With $U(0)=0$ we just have $$ U(n) = 1 + \frac{1}{2}+\frac{1}{3}+\dotsm+\frac{1}{n} = H(n) $$ the $n$-th *harmonic number*, as it's known and it's also known that $H(n)$ is asymptotic to $\ln n$.

---
Tags: algorithms, algorithm-analysis, data-structures, runtime-analysis, discrete-mathematics
---


# Question
Title: In which pipeline stage are exceptions detected?
Do you immediatly handle an exception when it occurs (for example an overflow exception in the EX stage) or do you wait until the final pipeline stage and then check whether any interrupts had occured?

# Answer
> 5 votes
Both.

I'll assume you are talking about pipelined machine organizations with

1. out-of-order *completion* (different instructions take different amounts of time to produce their results)
2. precise interrupts (instructions appear to produce their effects in-order).

An exception might be detected in the instruction fetch stage (if, for example, there is a page fault when trying to access the instruction memory), in the execution stage (like in your example of an overflow) or, for memory instructions, for a page fault when trying to access the data memory.

One important question is what to do with the other instructions in the pipeline. Instructions that were fetched before the excepting instruction should appear to commit their changes before the interrupt, and instructions that were fetched after the excepting instruction should get cancelled somehow before they commit any changes at all.

Typically you deal with this by having some form of commit stage (called the "write-back" stage in the 5-stage pipeline that is often used in computer organization courses.) Instructions commit in order, even if they "complete" their execution out-of-order. At the time the excepting instruction arrives at the commit stage all the previous in-order instructions will have committed, but their will be some number of instructions that were fetched after the excepting instruction still in the pipeline. Those following instructions need to be cancelled, and this is often done by keeping a cancelled bit with each instruction as it flows down the pipeline. The commit stage just doesn't write-back the results of any cancelled instructions.

The other question that needs to be answered is when do you redirect the fetch unit to the exception handler. It would be simplest to signal the fetch unit only from the commit stage, but for longer pipelines that can cause an extremely long bubble between the exception being detected and the exception handler starting to fetch. In that case you might redirect the fetch unit when you detect the exception. The Pentium 4 did it this way, for example.

---
Tags: computer-architecture
---


# Question
Title: What can I deduce if an NP-complete problem is reducible to its complement?
Let's say I have a decision problem $D$ and its complement $D'$. I know D is poly-time reducible to $D'$ (its complement). Furthermore, I know $D$ is NP-complete. What is the strongest statement I could possibly make about this kind of relationship?

# Answer
> 2 votes
If an NP-complete problem is reducible to its complement then NP=coNP (why?). Conversely, if NP=coNP then every NP-complete problem is reducible to its complement (why?).

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


# Question
Title: Maximum Enclosing Circle of a Given Radius
I try to find an approach to the following problem:

> Given the set of point $S$ and radius $r$, find the center point of circle, such that the circle contains the maximum number of points from the set. The running time should be $O(n^2)$.

At first it seemed to be something similar to smallest enclosing circle problem, that easily can be solved in $O(n^2)$. The idea was to set an arbitrary center and encircle all point of $S$. Next, step by step, replace the circle to touch the left/rightmost points and shrink the circle to the given radius, obviously, this is not going to work.

# Answer
> 7 votes
I don't know how to solve this problem in $O(n^2)$ time, but an $O(n^2\log n)$ algorithm does exist.

Let $C(s\_i)$ be the circle whose center is $s\_i$, the $i$-th point, with radius $r$. It's not hard to find that the point set $P = \\{p\_0, p\_1, \ldots, p\_m\\}$ can be enclosed by a circle with radius $r$ iff the intersection $I(P)$ of $C(p\_0), C(p\_1), \ldots, C(p\_m)$ is not empty. Moreover, if $I(P)$ is not empty, there must be some points in $I(P)$ lay on some $\textbf{bd}C(p\_i)$ (the boundary of $C(p\_i)$). So for each $C(s\_i)$ and each point $p$ on its bondary, we try to find how many circles contain $p$. The max count among all $p$ will be the answer to this problem.

Let's examine points in $\textbf{bd}C(s\_i)$. There is an one-to-one mapping between the points on $\textbf{bd}C(s\_i)$ and the real number in $\[0, 2\pi)$. For each circle $C(s\_j)$, the intersection between $C(s\_j)$ and $\textbf{bd}C(s\_i)$ can be represented by an interval $\[begin\_j, end\_j\]$. So for all circles other than $C(s\_i)$, there are at most $n-1$ intervals (some circles may not intersect with $C(s\_i)$). The max count can be found easily by sorting all $2(n-1)$ end points of interval, scanning them in order and counting the current overlapping number. For each $C(s\_i)$, this step can be done in $O(n\log n)$ time, and there are $n$ such circles, so the time complexity of this algorithm is $O(n^2\log n)$.

# Answer
> 2 votes
I think the difficult questions is knowing whether the circle you've selected is actually "maximal" within the set. The only way I can think to determine this is to try all the possible combinations of the points, and test the size of the circle which encloses them.

You can reduce the search space though by first dividing the point space into a grid of square cells with width 2r. Then locate the cell with the greatest density. Since you've already located one circle of X points you can conclude that if a circle exists with more points, then it must have at least X points in it. And use this as a starting off point for testing the different combinations of the points.

If you are only looking for a set of points which is likely to be maximal, then you might be able to further reduce the number of combinations you need to test by selecting those points which fall within a neighborhood of cells where the density of the neighborhood is greater than X.

Having said this, both "reductions" can can fail, and at the worst case you will be computing circles for all possible combinations of points.

# Answer
> 1 votes
In Chazelle, B.; Lee, D. T. 's paper Computing 36, 1-16(1986), theorem 3 in page 15, it states that the maximum enclosing circle finding algorithm takes $O(n^2)$ time cost.

I think the key is still the $O(n^2)$ intersection graph construction algorithm it mentions early, (or see Edelsbrunner, H. (1987), Algorithms in Combinatorial Geometry, chapter 7). Afterwards the maximun enclosing circle finding should be straightforward.

Apparently, this problem is equivalent to find the point covered by maximum number of given circles and it is easily to know only those mostly $2n^2$ points intersected by given n circles need to be considered as candidates. (This also leads a $O(n^2log(n))$ algorithm directly )

However, by utilizing the above mentioned $O(n^2)$ construction algorithm, it leads an $O(n^2)$ algorithm for this problem, too. Because the intersection graph constructed with vertices as intersection points and edges as arcs is an Euler planar graph. So one can just travel all the arcs through an Euler cycle and an order of arcs indexed by the indexes of circles it belongs to and information of whether any arc is a "leaving away arc" (curved backwards) or "entering into arc" (curved forwards) for the met-during-travling vertice which this arc is incident on will be recorded.

By Jordan's theorem an intersection vertice is enclosed by a circle only if it meets a "leaving away arc" belonging to that circle first or has an incident arc belonging to that circle. So after the whole travel, the maximum enclosing circle can be easily found. It is simliar to the case of deciding the covering times for points with ordered intervals along a straight line, (or i.e. the 1D version of this enclosing problem), except the order has already been given by the travel. While by Euler's formular $V + E - F = 2$ for a planar graph, the total number of arcs is linear with the number of vertices, and since one does not need to record related information again when traveling back to vertices already visited, by handshaking lemma, the total time cost will be $O(n^2)$.

---
Tags: algorithms, computational-geometry
---


# Question
Title: I think I have a regular expression for a non-regular language
Let $W = \\{a^n b^m \mid n\ge m+5,m\le 5\\}$, where $\Sigma=\\{a, b\\}$.

I have proved that this language is irregular through pumping Lemma. But through regular expression it is proving that the language is regular. Can anyone please tell me that what should I consider it as. And does that happens?

# Answer
> 3 votes
$W\_1 = \\{a^5 . a^\*\\}$ is a regular language.

$W\_2 = \\{a^m b^m \mid m\le 5\\}$ is a regular (finite) language.

Thus $W = W\_1.W\_2$ is a regular language.

Something is wrong in your proof.

# Answer
> 1 votes
The key result of finite automata is that deterministic finite automata, nondeterministic finite automata and regular expressions all define exactly the same set of langauges: the regular languages.

So there must be a mistake somewhere. In this case, your pumping lemma proof is wrong because the language is regular. Hint: to accept, you only need to consider whether the number of $a$s is 0, 1, ..., 9, or "10 or more" and whether the number of $b$s is 0, 1, ..., or 5.

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


title: Is this grammar LR(1)?

text:
# Question
Title: Is this grammar LR(1)?
A bit confused about whether this grammar is ambiguous or not

```
C' -> C
C -> d C u C
C -> d C
C -> ε

```

I tried building the DFA for this but I get this in one of the states:

```
C -> d C DOT u C, $
    C -> d C DOT, $

```

Isn't this a shift-reduce conflict, so surely it means the grammar is not LR(1)? Or does it reduce regardless since $ and u are both in the follow set of C? Is this not a reduce-reduce conflict since it goes to C regardless?

# Answer
> 1 votes
This grammar (which isn't ambiguous) isn't LR(k) due to the right-recursion, thus it isn't LR(1).

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


# Question
Title: Distribution of Ones in a Psuedorandom Sequence
Let S be a string in the set (0,1) produced by taking the AND of the output of two maximal length linear feedback shift registers of large period (say 128 bits). It's easy to see from the truth table of the AND gate that you will end up with a string consisting of (approximately) 75% zeroes and 25% ones with the ones being psuedorandomly distributed , so to speak, in a string of zeroes. My question is given any number of observed output bits in the sequence , is it possible to predict WHEN the AND gate will output a one ?

# Answer
Yup, it's possible. This generator is easily broken, as each output bit has degree only two. There's an efficient algorithm that, given the first $n$ bits of output from the generator, will let you predict all the future outputs from the generator with 100% accuracy.

Let $x\_1,\dots,x\_{128}$ denote the initial state of the first LFSR and $x\_{129},\dots,x\_{256}$ denote the initial state of the second LFSR. Then every bit produced by your generator can be expressed as a multivariate polynomial over $x\_1,\dots,x\_{256}$. The degree of this polynomial is two: each monomial is of the form $x\_i x\_j$ or $x\_i$. Here were are working in the finite field $GF(2)$, i.e., working modulo two. In this field, the AND of $x\_i$ and $x\_j$ is the term $x\_i x\_j$ (the product). It follows that the output of the generator is a polynomial of degree two. (Why? Because at any given time, the output from the first LFSR is a linear function of the initial state, i.e., a polynomial $p\_1(x\_1,\dots,x\_{128})$ of degree one; and similarly the output from the second LFSR is a linear function, i.e., a polynomial $p\_2(x\_{129},\dots,x\_{256})$ of degree one. Now the output of the generator is the AND of these two, i.e., it is the product $p\_1(x\_1,\dots,x\_{128}) p\_2(x\_{129},\dots,x\_{256})$, which is a polynomial of degree two.)

So, if you're given $n$ bits of output from this generator, you receive $n$ quadratic equations in the 256 unknowns $x\_1,\dots,x\_{256}$. If $n$ is large enough, there are standard techniques for solving this system of equations, which gives you $x\_1,\dots,x\_{256}$. At that point you know the initial state of both LFSRs, so you can predict the future output of the generator for all time -- and the scheme is broken.

How do you solve the system of linear equations? One simple approach is linearization: if $n \> 256^2/2$, then you can replace each monomial $x\_i x\_j$ by a new unknown $y\_{i,j}$; then you get a new system of $n$ linear equations in roughly $C(256,2)$ unknowns, which can be efficiently solved using Gaussian elimination. If $n$ is smaller than that but still significantly larger than 256, you can use relinearization, which is efficient as long as $n$ is large enough. (You can also try SAT solvers, Groebner basis algorithms, or other methods, though these are not polynomial-time in general.) For more details on relinearization, see https://crypto.stackexchange.com/a/3736/351.

To avoid this problem, I suggest using a cryptographic-strength pseudorandom generator -- also known in the cryptographic literature as a "stream cipher". For instance, you could use AES in CTR mode (counter mode). This will provide very strong resistance against prediction of future outputs, as long as the AES key is chosen at random and is hard to guess.

By the way, the Cryptography Stack Exchange site has many experts who are knowledgeable about this sort of topic, so you might be interested in checking out the material that's available over there.
> 3 votes

---
Tags: combinatorics, probability-theory, pseudo-random-generators
---


# Question
Title: Suggestions for Short Examples Contrasting Functional Programming Languages
A fellow student and I are writing a paper on functional programming for a programming languages course, part of which will be comparing and contrasting Lisp (Scheme), ML (SML), and Haskell. We'll be coding the same algorithm in each language and we're at a bit of a loss for exactly *what* to code. We would be grateful for some suggestions for algorithms that fit the bill (described below). We'll work out the code---we're just looking for suggestions. But if there's a particular tricky point or useful idiom we'd welcome a heads-up.

We envision the code being about a page. In particular, the professor wants something more substantial than a line or two. To the degree possible, we'd like to use this to contrast the styles of the three languages and at the same time showcase the benefits of functional programming. I considered quicksort, but the standard Haskell code is just a line or two.

I would have tagged this with "homework" and "soft question" (as well as "ML" and "Haskell"), but those tags don't seem to exist. Also, I wasn't sure whether Computer Science or Stack Overflow was the right place for this, but decided on Computer Science because we're not really looking for worked-out code or solutions to a particular coding problem. Instead we're looking to demonstrate the benefits of the functional programming paradigm and three important branches thereof.

# Answer
> 1 votes
* Project Euler has nice problems for showcasing the core of a programming language.
* An important part of a programming language are user defined (container) data structures. Bread and butter containers include random access arrays, bidirectional lists, hash tables, and search trees. You may take the implementations from standard libraries of the languages to get interesting real world programs for you comparisons.
* A strong point of functional programming languages is that they allow modular reuse of standard algorithms. The C++ stl header algorithm provides a nice collection of those reusable standard algorithms.

---
Tags: functional-programming, lisp
---


# Question
Title: Algorithm to compute a recursive function on a given set
I am working on a property of a given set of natural numbers and it seems difficult to compute. There is a function 'fun' which takes two inputs, one is the cardinal value and another is the set. If the set is empty then fun should return 0 because fun depends on the product of the set and fun on all subsets of the complement set.

For clarification here is an example:

S is a set given S={1,2,3,4}. The function fun(2,S) is defined as

```
fun(2,S)=prod({1,2})*[fun(1,{3}) + fun(1,{4}) + fun(2,{3,4})] +
         prod({1,3})*[fun(1,{2}) + fun(1,{4}) + fun(2,{2,4})] +
         prod({1,4})*[fun(1,{3}) + fun(1,{2}) + fun(2,{2,3})] +
         prod({2,3})*[fun(1,{4}) + fun(1,{1}) + fun(2,{1,4})] +
         prod({2,4})*[fun(1,{1}) + fun(1,{3}) + fun(2,{3,1})] +
         prod({3,4})*[fun(1,{1}) + fun(1,{2}) + fun(2,{1,2})]

```

prod is defined as the product of all elements in a set, for example

```
prod({1,2})=2;
prod({3,2})=6;

```

I am trying to write the pseudo code for this problem using recursive method but it's not working. The base case is the cardinal value should be more than zero that means there should be at least one element in the set other wise prod will be zero and fun will return zero.

Pseudo code:

```
fun(i,S)
if |S|=1 && i!=0
   return prod(S)
else if i==0
   return 0
else
  prod(subset s', s' is a subset of S and |s'|=i)*(sum over fun((for i=1 to m),{S-s'}), m=|S-s'|) //I don't know how to write code for this part and need help.
end if
end fun

prod(s)
if |s|=0
  return 1
else
  n=|s|
end if
temp=1
for i=1 to n
    temp *=s(i) //s(1) is the 1st element of set s
end for
return temp
end prod

```

**Update**:I tried to form a mathematical expression of the function fun $fun(m,s)=\sum\_{\sigma\_{p}\subset s;|\sigma\_p|=m}\left \[\prod\_{i}i\in \sigma\_p \sum\_{j=1}^{|s-\sigma\_p|}\sum\_{\gamma\_p\subset (s-\sigma\_p);|\gamma\_p|=j}fun(j,\gamma\_p)\right \]$

Where $|s|\geq 1$ and $m\geq 1$

$fun(m,s)=0$ if $s$ is a null set.

# Answer
You haven't told us what the function *is*, so we can't give you an algorithm.

However, here's what I can say. There are two general techniques that are often applicable to this setting:

1. Use dynamic programming (or memoization). This will avoid you having to evaluate `fun(k,S)` more than once for any pair `(k,S)`.
2. Look for mathematical identities that give you different ways to express your function. Sometimes you can find different ways to express your function (e.g., by factoring out common terms or somesuch); if so, look for these, and see if any of them leads to a more efficient algorithm than the others.
> 1 votes

---
Tags: algorithms, computability, recurrence-relation, dynamic-programming, recursion
---


# Question
Title: Is there an implicit condition OPT<P(|input|) in approximation schemes?
Sorry if my question is banal. Consider an approximation scheme such as `FPTAS` that guarantees to find a `soln>(1-eps)OPT` for maximization. Now consider if `OPT=exp(|input|)` so It easily can be seen that `soln` is `exp(|input|)` So its run-time will be exponential too(just a print of result is exponential). So can we say the condition `OPT<P(|input|)` is a necessary condition for any problem that we want to find an approximation scheme algorithm for that?

# Answer
FPTAS is commonly used for optimization problems whose associated decision problem is in NP. For those problems, it is guaranteed that the optimal solution has polynomial size (that's part of the definition of NP), so this issue does not arise.
> 1 votes

---
Tags: approximation
---


# Question
Title: What's the difference between physically based rendering and global illumination?
I know that Physically based rendering means we try to simulate how light actually works in real world and global illumination is bouncing back of light when it strikes a surface. But what's actual difference between them and how are they related?

# Answer
The two terms are, in a sense, orthogonal.

*Global illumination* refers to any process which simulates indirect lighting. Indirect lighting occurs when light bounces off surfaces or through media. The opposite of global illumination is *local illumination*, where only illumination directly from light sources is taken into account.

*Physically-based rendering* is a loosely-defined term, but the general idea is to model lighting, surfaces, and media in a way that is physically plausible. This includes, for example, ensuring conservation of energy, so that the solution to the light transport equations don't blow up.

Generally speaking, PBR can be thought of as a type of GI, but this isn't always the case; it's possible to use physically-based rendering without trying to solve the whole rendering equation. Moreover, PBR doesn't always try to model light exactly; quantum mechanical phenomena such as coherence and polarisation aren't commonly modelled (or are only coarsely modelled) in typical rendering methods.
> 1 votes

---
Tags: algorithms
---


# Question
Title: Matching a set of paths to an incrementally generated graph
I am working on an approximate matching problem, where I have a set of paths in an unknown graph (A) and a partial graph (B), where B is generated incrementally during the matching process (and can be potentially infinite).

The problem is to match the maximum number of edges in the paths to the smallest graph B. The matching should be such that the order in which the edges appear in the paths is preserved in the graph, and each path is matched to a distinct path in the graph. This distinctness requirement comes from the fact that each path in graph A must have a corresponding path in graph B but might not generated yet.

The graph nodes are immaterial and the edges have non-unique labels upon which matching is performed. Also, the paths to be matched can have arbitrary edges added/deleted while matching is to the graph B. If the solution does not meet a threshold (X% of edges matched), we can query an oracle, that generates a slightly bigger (i.e., more complete) graph but the goal is to minimize the queries as the graph can potentially be infinite.

Example:

```
Paths:
-A-> -B-> -C->
-A-> -D->

Graph:
-A-> -X-> -B-> -C->

Result:
Matched: A-A, B-B, C-C
Unmatched: D

Query Oracle (A-D?) gives resulting graph.
-A-> -X-> -B-> -C->
 |-D->

Result:
Matched: A-A, B-B, C-C, D-D

```

I tried to lookup standard solutions from assignment and graph isomorphism but didn’t find anything similar. So, here is a solution I came up with:

1. I am using a branch and bound algorithm to match every edge in the paths to every edge in the graph (M X N table). For each possible assignment, I am keeping track of which other assignments are possible containing with the particular assignment
2. The bounding condition (& feasibility) is defined by the same ordering of the edges in the graph as it is in the paths. Also, two paths cannot be mapped such that they violate each others ordering.
3. If we are not happy with this solution, we can query the oracle, get a bigger graph and repeat 1 & 2. Otherwise, the technique outputs the possible edge mappings.

My question is that I am not sure if my solution still falls under branch & bound algorithms, as it no longer follows the standard branch & bound tree structure. Also, it would be great if anyone can point out optimizations or a better way to do this.

Note: At every iteration, N changes and the table grows horizontally. The biggest inefficiency is in step #2, which needs to be recomputed at every stage for safety (e.g., a loop being added in the graph invalidates previous solutions).

# Answer
I'll outline a solution to your problem. There are two key insights: (1) each path can be analyzed independently of all the others; (2) the best match can be computed using dynamic programming. I'll start with a simpler version of your problem and build up to a solution for the full problem.

## Finding the best match for a single path

Suppose we have a single path (from graph A) and we want to find its best match in graph B. This can be solved with dynamic programming.

Let $P$ denote the path from graph A, and $P\_k$ denote the prefix of the graph containing its first $k$ edges. If $v$ is a vertex in $B$ and $k$ is a natural number, define $f(k,v)$ to be the number of edges present in the optimal match of $P\_k$ inside graph B, such that the match ends at vertex $v$. Then $f(k,v)$ follow the following recursive relation:

$$f(k+1,w) = \max(\max \\{f(j,v) : v \to^\* w,j \le k \\}, 1 + \max \\{ f(j,v) : v \to^\* v' \to w, j \le k\\})$$

where the former max is taken over all $v$ such that $w$ is reachable from $v$ in B, and latter max is taken over all $v,v'$ such that $v'$ is reachable from $v$ in B and there is an edge from $v'$ to $w$ in B whose label is the same as the label on the $k$th edge of $P$. Also, we have the base case $f(0,v) = 0$ for all $v$. Finally, notice that the number of edges matched in the optimal match for $P$ is given by $\max\\{f(k,v) : v \in V\\}$.

This recursive relation immediately gives us a dynamic programming algorithm to compute the number of edges matched in the optimal match for $P$. You can also augment the algorithm to retrieve the match itself, if desired.

The running time is polynomial. Suppose the path has length $\ell$ and graph B has $n$ vertices and $m$ edges. Then there are $O(\ell n)$ subproblems, and each subproblem takes $O(m \el)$ time to solve (on average), so the running time is $O(nm \ell^2)$. \[It might be possible to further improve the running time by decomposing B into strongly connected components and only computing $f(k,v)$ values for one vertex $v$ in each strongly connected component, but I haven't tried to optimize this algorithm.\]

Note that this gives the exact optimum, not an approximation. It's not a heuristic -- it always gives the optimal solution.

If you don't find the dynamic programming algorithm intuitive, here is another perspective. You can think of this from an automata theory perspective. Suppose the path has edge labels $e\_1,\dots,e\_{\ell}$. Let $M$ be the automaton that accepts every subsequence of regexp $\Sigma^\* e\_1 \Sigma^\* e\_2 \Sigma^\* \cdots \Sigma^\* e\_{\ell} \Sigma^\*$ (this is a regular language, so it has a NFA, call it $M$). Form the parallel composition of $M$ and B, using the product construction; call it $M'$. Now look for the longest path in $M'$. This is exactly the optimal match you are looking for.

## Finding the best match for a collection of paths

Now suppose we have multiple paths and want to match them all to B. Well, it turns out that the optimal way to match a collection of paths is to consider each path separately, finding the optimal match for that path in isolation (independent of all the other pairs), and then combine these matches.

So if we have $q$ paths, we can just invoke the algorithm above $q$ times, once for each path. The running time will be $O(nm \ell^2 q)$.

## Dealing with changes to B

In your problem, each time you find the best matches for a collection of paths, you then update B to get a new graph. This can be easily handled by simply running the algorithm from scratch again on the new graph. In each round, you run the $O(nm \ell^2 q)$-time algorithm from above on the current graph B. Then, you use whatever technique you have in mind for growing the graph B, and start over again. This doesn't let you re-use work from previous rounds, but it's a very simple technique, and it computes the optimal solution.
> 1 votes

---
Tags: graphs, graph-traversal, assignment-problem, branch-and-bound
---


# Question
Title: How to make a "Secure by Design" client-server communication?
Is there a way to have a secure by design client-server communication in a sense that the server can check if the client is not a modified version?

What I'd like to do is give the user access to both the client's and the server's source code, but keep him from communicating with a modified version.

As a practical example, let's suppose a multiplayer race game. Is there a way to give the user access to the source (and to compiling it and playing it on the server if he wants) but keeping him from, let's say, altering the speed of his car to 2x normal speed and using this new version to play?

As I understand, the compiled program could generate some hash and send it together for the server to verify. But then there also comes stuff like being able to get this code and making another version send it, etc.

If this is a known problem, please also provide further information about it. (Any recommendations on books or papers related to that are also welcome)

# Answer
The short answer is: No, you can't verify what code is running on the client. As a result, you should never trust what is running on the client.

You could use all sorts of hashes, but nothing prevents a malicious client from lying to you about its hash and telling you what you want to hear. Asking the client to hash itself and tell you its hash would be like having airport security ask passengers "Are you a terrorist?" and then believing them when they say "No".

In principle this problem could be solved with trusted hardware on the client, such as a a TPM. Currently, a TPM is about the only way to check that the client is running unmodified code. However, in practice using TPMs for this has major issues that typically render it not deployable in practice for the purpose you have in mind.

Therefore, in practice the answer is basically "no, there's no way to check". See https://security.stackexchange.com/q/72091/971 for an explanation why there is no way to do this without trusted hardware (like a TPM). As a result, the standard mantra is "you can't trust the client". See e.g., https://security.stackexchange.com/q/40378/971 for some discussion of alternative architectures don't rely on trusting the client.

For a partial explanation why TPM-based solutions are not really deployable in practice, see https://security.stackexchange.com/q/2459/971.

If you want to explore the TPM approach, see https://security.stackexchange.com/q/5570/971 and https://security.stackexchange.com/q/4008/971. However, I don't recommend it as a promising avenue. In the future, Intel will be releasing SGX technology, which might be a better way to achieve this -- but it has not yet been released, so it will be quite some time before you can count on all your clients to run on hardware that supports SGX.
> 2 votes

---
Tags: distributed-systems, security
---


# Question
Title: Proof of Circuit-Sat to Nand-Sat polynomial time many–one reducibility
Given a gate called **Nand** with the following truth table:

```
 A | B | A Nand B
------------------
 0 | 0 |    1
 0 | 1 |    1
 1 | 0 |    1
 1 | 1 |    0

```

We can define a circuit satisfiability problem where only Nand gates are allowed:

> $\mathrm{Nand\text{-}Sat}$:
>
> *Input*: A Boolean circuit $C$ with $m$ inputs $(P\_{1},P\_{2}\ldots,P\_{m})$ such that all gates are Nand gates.
>
> *Question*: Is there a Boolean assignment to the inputs of $C$ such that the output of $C$ is $1$?

I would like to show that $\mathrm{Circuit\text{-}Sat} \leq\_{P} \mathrm{Nand\text{-}Sat}$. Where $\mathrm{Circuit\text{-}Sat}$ is the normal circuit satisfiability problem:

> $\mathrm{Circuit\text{-}Sat}$:
>
> *Input*: A Boolean circuit $C$ with $m$ inputs $(P\_{1},P\_{2}\ldots,P\_{m})$.
>
> *Question*: Is there a Boolean assignment to the inputs of $C$ such that the output of $C$ is $1$?

My question is do I have to create a function that translate AND,OR,NOT gates into Nand gates?

# Answer
> 0 votes
not A = A nand A
A Or B = (A nand A) nand (B nand B)
A and A = (A nand B) nand (A nand B)

---
Tags: complexity-theory, reductions, satisfiability, circuits
---


# Question
Title: 6-coloring of a tree in a distributed manner
I have some difficulties in understanding distributed algorithm for tree 6 - coloring in $O(\log^\*n)$ time.

The full description can be found in following paper: Parallel Symmetry-Breaking in Sparse Graphs. Goldberg, Plotkin, Shannon.

In short, the idea is ...

Starting from the valid coloring given by the processor ID's, the procedure iteratively reduces the number of bits in the color descriptions by recoloring each nonroot node $v$ with the color obtained by concatenating the index of a bit in which $C\_v$ differs from $C\_{parent}(v)$ and the value of this bit. The root $r$ concatenates $0$ and $C\_r\[0\]$ to form its new color.

**The algorithm terminates after $O(\log^\*n)$ iterations.**

I don' have the intuitive understanding why it's actually terminates in $O(\log^\*n)$ iterations. As it's mentioned in the paper on the final iteration there is the smallest index where two bit string differs is at most 3. So 0th bit and 1th bit could be the same and $2^2=4$, so this two bit will give us 4 colors + another 2 colors for different 3th bit, and in total 8 colors and not 6 like in the paper, and why we cannot proceed further with 2 bits, it's still possible to find different bits and separate them.

I would appreciate a little bit deeper analysis of the algorithm than in the paper.

# Answer
> 1 votes
In the paper, the authors mention that after $\log^\* n$ iterations, the number of bits used to encode any of the color labels is at most 3. That means that there are at most eight colors. If we have six or fewer colors, we're done, and otherwise we go through the loop once more.

Let's say that we do one last loop iteration. The root gets the color label 0 or 1. Every other node gets a label equal to the first bit position where that node's old label disagrees with its parent's label, plus one extra bit. Since on entry to this iteration all colors are three bits long in the worst case, there are three possible positions where the bits could disagree. Therefore, each new color is formed from a combination of one of three choices and a bit (one of two choices), so at exit of this loop iteration there are only six possible color labels, so we have a six-coloring. The total number of loop iterations is then $\log^\* n + 1 = O(\log^\* n)$

Hope this helps!

# Answer
> 0 votes
Distributed Algorithm for tree 6 - coloring in O(log\* (n)) time is very good algorithm.

Let me explain what is "log\* n"

log\* (n)- "log Star n" as known as **"Iterated logarithm"**

In simple word you can assume log\* (n)= log(log(log(.....(log\* (n))))

log\* (n) is very powerful.

**Example:**

1) Log\* (n)=5 where n= Number of atom in universe

now your question:

**Why it terminate after log\*n time?**

In each round size of the ID reduced by log factor hence the number of color is also reducing: to index bit where two label of size n bit differ + 1 more appending bit.

**Why only 6 colors, why not More or Less?**

Why not 4 colors: {0,1,2,3} - as two bits are required to address index where they differ, plus adding the “difference-bit“ gives more than two bits.

Why not 7 colors: {0,1,2,3,4,5,6} - as 7=111 (in Binary) can be described with 3 bits, and to address index (0,1,2) requires two bits, plus one “difference-bit“ gives three again.

Why 6 Colors?- colors 110 (for color “6“) and 111 (for color “7“) are not needed, as we can do another round! (IDs of three bits can only differ at positions 00 (for “0“), 01 (for “1“), 10 (for “2“).

you can **reduce 6-color to 3-color**, which is given in above link of your comment.

---
Tags: algorithms, runtime-analysis, distributed-systems, colorings
---


# Question
Title: Does NP-completeness require to find the solution?
In the paper "Computing Equilibria:A Computational Complexity Perspective" by Tim Roughgarden, they consider the problem:

**Problem 2.1** (Clique). Given a graph $G = (V, E)$ and an integer $k$:

1. if there is a set $K ⊆ V$ with $|K| = k$ and with $(i, j) ∈ E$ for every distinct $i, j ∈ K$, then output such a set;
2. otherwise, indicate that $G$ has no $k$-clique.

Then they claim that Problem 2.1 is NP-complete in the Theorem 2.7.

My question is about the part (1). I always thought NP-completeness is for yes/no problems and thus they didn't require that the the solution be output if the decision is an yes?

So is this definition of NP-complete problem 2.1 right? Or should part (1) be rephrased as "if there is a set $K \subseteq V$ with $|K| = k$ and with $(i, j) \in E$ for every distinct $i, j \in K$, then output yes;

The Problem 2.1 is a half decision problem and half feasibility problem, what are such problems called?

P.S the paper can be found at http://theory.stanford.edu/~tim/papers/et.pdf

I went through Optimization version of decision problems and still not sure where Problem 2.1 belongs to.

# Answer
> 7 votes
You are right that NP-completeness applies only to decision problems. What they mean by "Problem 2.1 is NP-complete" can be either

> The decision problem corresponding to Problem 2.1 is NP-complete

or

> The decision problem corresponding to Problem 2.1 is NP-complete, and the search problem is in FNP

Here the *search problem* is finding a clique of size $k$ if one exists. We think of the search problem as a two-place predicate $f(\langle G,k \rangle,K)$ which is true if $G$ is a graph and $K$ is a $k$-clique of $G$. This search problem is in FNP if the predicate $f$ is in P. (Usually FNP is defined for functions, i.e. for relations which are functions, but you can also define it for general relations.)

---
Tags: complexity-theory, decision-problem, np, search-problem
---


title: Proof of Karp-Lipton theorem

text:
# Question
Title: Proof of Karp-Lipton theorem
I am trying to understand the proof of the Karp-Lipton theorem as stated in the book "Computational Complexity: A modern approach" (2009).

In particular, this book states the following:

> *Karp-Lipton theorem*
>
> If **NP** $\subseteq$ **$P\_{\backslash poly}$**, then **PH** $= \Sigma^p\_2$.
>
> *Proof:* By Theorem 5.4, to show **PH** $= \Sigma^p\_2$, it suffices to show that $\Pi^p\_2\subseteq \Sigma^p\_2$ and in particular it suffices to show that $\Sigma^p\_2$ contains the $\Pi^p\_2$-complete language $\Pi\_2$SAT.

Theorem 5.4 states that

> for every $i \geq 1$, if $\Sigma\_i^p = \Pi\_i^p$ then **PH** = $\Sigma\_i^p$. That is, the hierarchy collapses to the ith level.

I am failing to understand how $\Pi^p\_2\subseteq \Sigma^p\_2$ implies $\Sigma\_2^p = \Pi\_2^p$.

As a more general question: does this hold for every $i$, i.e. does $\Pi^p\_i\subseteq \Sigma^p\_i$ imply $\Sigma\_i^p = \Pi\_i^p$ for all $i \geq 1$?

# Answer
Recall that $L \in \Sigma\_i^p$ iff $\bar{L} \in \Pi\_i^p$. Suppose now that $\Sigma\_i^p \subseteq \Pi\_i^p$, and let $L \in \Pi\_i^p$. Then $\bar{L} \in \Sigma\_i^p$ and so $\bar{L} \in \Pi\_i^p$ by assumption, implying that $L \in \Sigma\_i^p$. In other words, $\Pi\_i^p \subseteq \Sigma\_i^p$, and so $\Sigma\_i^p = \Pi\_i^p$.

Here's why $L \in \Sigma\_i^p$ iff $\bar{L} \in \Pi\_i^p$. For concreteness, we take $i = 3$. By definition, $L \in \Sigma\_3^p$ if for some P-time predicate $T$, $$ x \in L \Leftrightarrow \exists |y| \< |x|^{O(1)} \forall |z| \< |x|^{O(1)} \exists |w| \< |x|^{O(1)} T(x,y,z,w). $$ Similarly $\bar{L} \in \Pi\_3^p$ if for some P-time predicate $S$, $$ x \in \bar{L} \Leftrightarrow \forall |y| \< |x|^{O(1)} \exists |z| \< |x|^{O(1)} \forall |w| \< |x|^{O(1)} S(x,y,z,w). $$ However, these two statements are equivalent, as a simple invocation of de Morgan's laws shows, together with the fact that P is closed under complementation (take $S = \lnot T$).
> 8 votes

---
Tags: complexity-theory, complexity-classes
---


# Question
Title: Kernel Perceptron vs Polynomial Perceptron
I was looking at Support Vector machines (SVM) kernels. Looking at Polynomial Kernel and Kernel Perceptron I was curious how they differ?

**Work Done**

Polynomial Kernel:

$d\_{k+1}(x)=d\_{k}(\bar{x})+\rho k(\bar{x}\_{k}, \bar{x})\\; \mbox{if}\\; \bar{x}\_k\epsilon\\,C\_1$

$d\_{k+1}(x)=d\_{k}(\bar{x})-\rho k(\bar{x}\_{k}, \bar{x})\\; \mbox{if}\\; \bar{x}\_k\epsilon\\,C\_2$

where $k(\bar{x}\_{k}, \bar{x}) = (\bar{x}\cdot \bar{x}\_{k}+1)^{q}$

Kernel Perceptron:

This is given by

$g(x)=\sum\_{j=1}^{N}a\_{j} K(\bar{x},\bar{x}\_j)$

So as per my understanding a bias constant is added in former case when compared to later. So how does that impact and what difference does it make? Or am I missing something?

Any insights are appreciated.

# Answer
> 1 votes
A SVM with a polynomial kernel is a SVM classifier.

A kernel perceptron is a perceptron classifier, or in other words, a neural net.

A SVM is quite different from a neural net. So, that's one way that they differ.

However, Wikipedia says that SVMs are in some respects a generalization of a kernel perceptron, generalized with regularization. Regularization is basically a form of Occam's razor: it says that, all else being equal, simpler models are preferred over more complex models. Regularization helps avoid overfitting and thus is very useful in practice.

(Related: See also Support Vector Machines as Neural Nets? -- a SVM with a linear kernel is similar to a single-layer perceptron classifier, in case that's what you were thinking of.)

---
Tags: machine-learning, pattern-recognition, kernel-functions, svm
---


# Question
Title: Bellman-Ford Termination when there is no change on vertex weights?
We know the bellman-ford algorithms check all edges in each step, and for each edge if,

> d(v)\>d(u)+w(u,v)

then d(v) being updated such that w(u,v) is the weight of edge (u, v) and d(u) is the length of best finding path for vertex `u`. if in one step we have no update for vertexes, the algorithms terminate. with supposing this algorithms, for finding all shortest path from vertex `s` in graph G with `n` vertex after `k<n` iterate is finished, can we conclude:

1) number of edges in all shortest paths from `s` is at most `k-1`

2) weight of all shortest paths from `s` is at most `k-1`

I Think Neither the number of edges nor their total weight is limited by k-1 with the defining problem, but my TA says (1) is True. How can describe these conditions?

# Answer
Part (1) is indeed true. The idea is that in $k$ steps the algorithm is only considering paths of length $k$. Indeed, you can prove by induction on $k$ that the path realizing the value of $d(v)$ after $k$ steps is at most $k$ edges long.

If the algorithm terminates after $k$ steps, then the results of the first $k-1$ steps are already optimal, hence (1).

Part (2) is indeed false, and I'm sure you can give a counterexample on your own.

---

The simultaneous version of the Bellman–Ford algorithm, referred to in part (1), has the following pseudo-code (where $d(x,y)$ is the weight of the edge connecting $x$ and $y$):

```
A[0,x,y] = ∞ for all x,y
t ← 0
do
  for all x,y:
    A[t+1,x,y] = min(A[t,x,y], { A[t,x,z] + d(z,y) : all z ≠ x,y })
  t ← t+1
while A[t,x,y] ≠ A[t-1,x,y] for some x,y
return A[t,x,y]

```

Take as an example the (undirected) graph $x - y - z - w$ (with unit weights). Here is a trace of the algorithm:

$$ \begin{array}{c|cccccc} t & A\[t,x,y\] & A\[t,x,z\] & A\[t,x,w\] & A\[t,y,z\] & A\[t,y,w\] & A\[t,z,w\] \\\hline 0 & \infty & \infty & \infty & \infty & \infty & \infty \\ 1 & 1 & \infty & \infty & 1 & \infty & 1 \\ 2 & 1 & 2 & \infty & 1 & 2 & 1 \\ 3 & 1 & 2 & 3 & 1 & 2 & 1 \\ 4 & 1 & 2 & 3 & 1 & 2 & 1 \end{array} $$
> 3 votes

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


# Question
Title: Infinite sequence of regular languages over fixed finite alphabet
Construct an infinite sequence of regular languages $L\_1, L\_2 , \ldots$, over the same fixed finite alphabet, such that for every $i ≥ 1$, $L\_i ⊇ L\_{i+1}$ and $|L\_i \setminus L\_{i+1} | = ∞$.

# Answer
You can start with a problem that seems intuitively easier, and then use closure properties of regular sets. Here is an example.

Take any infinite sequence of infinite and disjoint regular sets $R\_i, i=1,2, \ldots$. Start with $L\_1=\Sigma^\*$, and build the sequence $L\_{i+1}=L\_i\setminus R\_i$.

For example, with $\Sigma=\\{0,1\\}$ you can take $R\_i=0^i1^\*$

**Added after comments to the initial question: analysis and synthesis**

Since you want some form of reasonning to find a solution. Here is a possible analysis of the problem, from which one then get in reverse the construction technique suggested.

Assume that the sequence $L\_1,L\_2,\ldots$ satisfies the given considitons for an answer. Then consider the sequence $R\_1, R\_2,\ldots$ defined by $R\_i=L\_i\setminus L\_{i+1}$. The conditions on the $L\_i$ sequence imply that each $R\_i$ is an infinite set, and it is regular since regular set are closed under set difference. They are also all disjoint, since by construction, no $R\_i$ can contains elements from $R\_j$ for any $j\leq i$ (out of two such sets, there is always one with a smaller index).

They are also all contained in $L\_1$ by construction.

Given that any solution has these properties, you may wonder whether these are sufficient to obtain the desired decreasing sequence you wanted. This may be useful since defining an infinite sequence of disjoint infinite regular sets $R\_i$ is rather easy.

Using closure properties of regular sets, it is easily proved that indeed such a construction, as given at the beginning of my answer, will work to answer the question, provided that each $R\_i$ is included in $L\_1$.

But choosing $L\_1=\Sigma^\*$ I make certain that that is the case.
> 2 votes

# Answer
Hint: One option is to take $L\_1 = 0^\*$, $L\_2 = (00)^\*$, and so on. There are many others.
> 1 votes

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


# Question
Title: Is there any other way of getting a function from this piece of code?
I have this pseudocode

```
function mysterious(N):
    count = 0
    for i = 0 to N:
        if (i mod 3 == 0):
            count = count + i
    return count

```

The problem ask for the expression that returns this function using N or in terms of N

The best I have done is $\sum\limits\_{i=0}^n i \bmod 3$

Is there any better way to express the function of this code? I know the code returns the sum of the numbers divisible by 3

# Answer
> 1 votes
Hint: Use the formula $$ \sum\_{i=1}^k i = \frac{k(k+1)}{2}. $$ You can consider first the case that $N$ is a multiple of $3$.

Further hint: Use the formula $$ \sum\_{i=1}^k 3i = 3\frac{k(k+1)}{2}. $$ When $N$ is a multiple of $3$, a good choice of $k$ is $N/3$. More generally, you should choose $k = \lfloor N/3 \rfloor$.

# Answer
> 2 votes
Isn't it simply the sum of all the multiples of 3 in the range `(0,N)`

It is the sum `3 + 6 + 9 + 12 + ... + int(N/3)`. You can work around from here, following @Yuval answer.

---
Tags: algorithms, algorithm-analysis
---


# Question
Title: What is the relationship between Turing Machines with a finite tape and Finite State Automata?
I seem to recall from an undergraduate class that for a Turing Machine with a finite tape there will always exist a corresponding Finite State Automata, but I've been unable to find this confirmed anywhere on the internet. Is this actually the case or am I misremembering?

# Answer
> 15 votes
It depends what you mean by "finite tape". If you bound the length of the tape by some function of the input, then no - you can recognize non-regular languages. For example, consider LBAs.

But if you mean a *bounded* tape, where the tape has $k$ cells for some fixed $k$, then yes - you indeed get a model which is equivalent to DFAs.

To prove this, consider what information you need to determined the future of a run of a TM: you need the contents of the tape, the location of the head, and the state. If the tape has a constant number of cells, and the alphabet is fixed, then you have a constant number of configurations, which you can encode as states of a finite automaton.

---
Tags: turing-machines, finite-automata
---


title: How do you search a graph?

text:
# Question
Title: How do you search a graph?
An interview question I was asked. I was first asked how to traverse a graph and next I was asked how to search one. Got the first one but not the second.

What is the modern standard way to search a graph (assume undirected) given no other context? I've a notion that it might have something to do with Dijkstra's algorithm but IDK what. It makes sense that one way is to simply traverse the graph until you find the item you are looking for but it sure doesn't seem optimal.

# Answer
Interviewer was probably fishing for words like: preorder, inorder, postorder traversal and depth-first versus breadth-first. I am thinking of traversal as simply having an iterator over the graph that returns some vertices and edges in some particular order. As Richerby says, you could fill books with all the various ways that this could happen.

As for searching graphs, if they didn't mean traversal; then they probably meant searching for subsets efficiently: If a graph is known to have implicit structure (ie: find all edges in: 192.168.4.0/24 -\> 10.0.3.2/24 by hour, etc), then various kinds of searches over src/dst/time are often possible. Facebook/Twitter, etc are utterly gigantic graphs of "at time T, A says X to B".
> 0 votes

---
Tags: algorithms, graphs, graph-traversal
---


# Question
Title: Algorithm to extract the subgraph of all nodes with degree at least four
I have an undirected graph represented by a list of nodes and a list of edges. What I need to produce from this is a list of nodes and edges representing a new graph containing only the nodes which have degree of at least 4. I think I've developed an algorithm. It uses an object called Node, which can store an integer for the degree of the node and a list of that node's neighboring nodes.

1. For each node in the graph create a Node object in $O(|V|)$ time and store in a list.
2. Traverse the list of edges in $O(|E|)$ time. While doing so update my list of nodes with their appropriate degree and neighbors.
3. Search the list in $O(|V|)$ time and find the node with smallest degree. If \>4, return. If \<4, visit the node's neighbors, reduce their degrees by one, and remove this node from their list of neighbors. Then remove this node from the graph, in worst case $O(|V|)$ time.
4. Repeat step 3. At worst $O(|V|)$ times.

If anyone is wondering, I'm doing this for a Civilization-esque game I'm making. I want to be able to separate cities that are part of major trade routes from minor ones.

Now, I think this algorithm is correct, but I'm not happy with its running time. If I'm not mistaken, it's $O(|V|^2)$, correct? Is there a way to make this more efficient?

# Answer
The object you are trying to find is known in graph theory as the *4-core*. Batagelj and Zaveršnik give a simple linear time algorithm for finding the $k$-core for any given $k$.
> 3 votes

---
Tags: algorithms, graphs
---


# Question
Title: Understanding terms related to 2SAT algorithm
Recently I am learning about solution of the 2-satiability problem using strongly connected components. There is a theorem related to this problem given below:

Let $F = Q\_lx\_1 Q\_2x\_2\ldots Q\_nx\_n C$ be a quantified Boolean formula with no free variables, where each $Q\_i$ is either universal or existential, and $C$ is in conjunctive normal form. That is, $C$ is a conjunction of clauses, each clause is a disjunction of literals, and each literal is either a variable, $x\_i$, or the negation of a variable, $x\_i$ ($1 \leq i \leq n$).

> **Theorem 2:** The formula $F$ is true if and only if none of the following three conditions holds:
>
> 3(i) An existential vertex $u$ is in the same strong component as its complement $u’$.
>
> 3(ii) A universal vertex $u\_i$ is in the same strong component as an existential vertex $u\_j$ such that $j \< i$ (i.e., $x\_i$ is not quantified within the scope of $Q\_i$).
>
> 3(iii) There is a path from a universal vertex $u$ to another universal vertex $v$. (This condition includes the case that $v = u$.)

In the proof they use this definition: We call a vertex universal if the corresponding variable is universally quantified and existential otherwise.

But I am not familiar with the terms *universal vertex* and *existential vertex*. Can any one please explain these terms to me?

# Answer
> 3 votes
The terms *universal vertex* and *existential vertex* are not universal, but rather specific to this specific theorem. The context is a graph on the set of literals (variables and their complements). Presumably for every clause $\ell\_1 \lor \ell\_2$ in $C$, there is an arrow from $\bar{\ell}\_1$ to $\ell\_2$.

A vertex is called *universal* if its corresponding variable is universally quantified, that is, quantified as $\forall x\_i$. In other words, if $Q\_i x\_i = \forall x\_i$ then the vertices $x\_i$ and $\bar{x}\_i$ are universal.

Similarly, a vertex is called *existential* if its corresponding variable is existentially quantified, that is, quantified as $\exists x\_i$.

---
Tags: algorithms, graphs, satisfiability
---


# Question
Title: Unprovable Post correspondence problem instance
Since there is no algorithm for the post correspondence problem, there exists an instance of this problem such that we can neither prove that the instance is positive nor prove that the instance is negative, i.e. an unprovable instance of this problem. Otherwise, for each instance, a proof that the instance is positive or a proof that the instance is negative exists and we could just use an algorithm which enumerates all the possible proofs until it finds such a proof, it always terminates and it correctly answers yes/no according to the proof found.

For finding such an instance, I pick a random instance, I try with a semi-decision procedure and, after some time, if this doesn't work, I try to prove that the instance is negative. Since this heuristic has always finished, I have not find such an instance until now, but it should be possible.

This is not specific to the Post correspondence problem, an unprovable instance should exist for all undecidable problems.

# Answer
> 0 votes
I find an answer here :

https://math.stackexchange.com/questions/1214823/have-we-found-a-turing-machine-for-which-halting-non-halting-is-unprovable

Since we can encode turing machine in PCP, we can construct an instance such that we can neither prove that the instance is positive nor prove that the instance is negative.

# Answer
> 9 votes
The argument you outline doesn't actually work. In fact, for any specific PCP instance, there is an algorithm which produces the right answer; it is either "output 'yes'" or "output 'no'". It is only when you require the algorithm to work for all the infinitely many instances that undecidability enters the picture (since an algorithm needs to be finite, you cannot just cobble together all the individual solutions).

Now it is true that given any particular PCP instance, you could just enumerate the potential solutions. The problem with this is that while for solvable instances, you will eventually find the solution, for (non-trivial) unsolvable ones, you will never get an answer. That is, what you have here is a *semi*-decision procedure.

---
Tags: computability, undecidability
---


# Question
Title: Constructing solution to 3SAT formulas using oracle queries
I'm interested in 3SAT and querying an oracle. Suppose we had an oracle that can decide, on an input boolean formula $\phi$, whether there exists any assignment to the variables that makes the formula true. Note: this does not say what the assignment to the variables is, just that there exists one.

My main question is: can we get the actual solution of the formula in polynomial time, using the oracle?

My first thought was that no, it is impossible because the oracle cannot help you with an assignment (i.e., if I gave an assignment to the variables, the oracle's answer does not change). However, just because this technique does not work does not mean that no techniques will.

I then thought to give an assignment to the first variable $x\_1$, and then use that to work on the next variables; however, I don't know how to progress from there without trying all possible combinations (i.e., running in time $O(2^n)$).

# Answer
> 4 votes
You have the right idea. Suppose you have a SAT oracle and an instance $I$ of 3SAT (or whatever SAT-ish class you like) containing $n$ variables, $x\_1, x\_2, \dotsc x\_n$. You could then do this:

```
send I to the oracle
if the oracle answers "not satisfiable"
   quit
else
   j = 1
   I_0 = I
   repeat
      transform I_{j-1} to I_j by substituting x_j = 1
      send I_j to the oracle
      if the answer is "satisfiable"
         save x_j = 1
      else
         save x_j = 0
         transform I_{j-1} to I_j by substituting x_j = 0
      j = j + 1
  until j = n

```

When the algorithm terminates, you'll have saved a satisfying collection of values for all the variables. This will be linear in $n$ (times the steps necessary to do the substitutions, which will be polynomial in the length of $I$).

---
Tags: complexity-theory, satisfiability, oracle-machines
---


# Question
Title: Enumerating all n-tuples over a finite domain
I would like to create an algorithm which takes in an integer n and returns an array whose entries give all n-tuples of nonnegative integers each of which is at most n, so like

* `A[n][0] = [0,0,0,...,0]`,
* `A[n][1] = [1,0,0,...,0]`, ...,
* `A[n][n^(n+1)]=[n,n,n,...,n]`,

that kind of thing.

If n is small, I can manually create n-many for loops to do this, but in general I would like to allow n to be large. Is there an easy workaround? Any help would be appreciated.

# Answer
Use recursion. Something like this:

```
def f(l, k):
    if l==0:
        yield []
    else:
        for i in range(k):
            for L in f(l-1, k):
                yield [i]+L

```

Here `f(l, k)` produces all lists of length `l` all of whose entries are in the range `0..k-1`. The idea is that if you have all lists of length `l-1` (the output of `f(l-1, k)`) you can use that to generate all lists of length `l`, by using a for-loop.

If you're not familiar with that Python syntax, try this variant:

```
def f(l, k):
    if l==0:
        return [[]]
    t = []
    for i in range(k):
        for L in f(l-1, k):
            t.append([i]+L)
    return t

```

Note that `[i]` is a list containing a single element, `i`, and `+` is the list concatenation operator, so `[i] + L` is a list obtained by prepending the element `i` to the front of list `L`.
> 3 votes

---
Tags: algorithms, enumeration
---


# Question
Title: How to design a finite state machine to detect 0110 in the input?
My task is to design a FSM whose output goes high for a single cycle whenever the pattern 0110 is detected on its input. The patterns may overlap, so an input 0110110 of would cause the output to go high twice- once for the first pattern (0110110), and once for the second pattern (0110110). a is used for the input and f is used for the output.

I am assuming I will need five state bubbles like this.

Is this correct or am I missing some cases based on the pattern going high twice if the pattern overlaps?

# Answer
> 3 votes
It looks like you're missing the overlap case, if I understand your diagram correctly. This does the trick:

```
A    // goto B if read 0 else stay
B    // goto C if read 1 else stay
C    // goto D if read 1 else goto B
D    // goto E if read 0 else goto A
E    // emit rising edge, goto B

```

assuming that you have a falling edge after every read.

# Answer
> 1 votes
This problem is just an instance of the substring searching problem, for the specific substring $0110$. There are several algorithms that solve it.

Given that the search is to be done in real-time, I guess the best algorithm is the Knuth-Morris-Pratt algorithm. For any string to be searched, the KMP algorithm will compute the table for a DFA that recognizes all occurences of that string in any string given as input.

Note however that the finite state device to be constructed is not really a DFA, but a deterministic finite state transducer (also known as Generalized sequential machines - GSM), as it has an output for each transition, which is either *low* or *high*. The words *low* and *high* may be taken as symbol of an output alphabet, even if they have physical meaning in the context of the question.

I leave it as an exercise to apply the KMP algorithm to the specific example of the question, since the question is actually asking how to design the finite state transducer, and is not asking to actually do it.

---
Tags: finite-automata, strings, substrings, digital-circuits
---


# Question
Title: RSA Decryption from Simple Public Key Values
I'm a little stuck trying to figure out how to decrypt some messages and could use some hints as to what I may be doing wrong.

I was given a series of integer values that make up my cipher text. Here are just a few of them:

6584 15650 16198 11003

I was given the following public key b = 3001 n = 18209

So to encrypt a message M, you would use the formula:

C = M^3001 mod 18209

I understand to encrypt, I need to find a 'd' value that satisfies:

bd = 1 mod 18209

3001d = 1 mod 18209

Any hints on a technique or algorithm to help me find a suitable value for 'd'?

# Answer
> 3 votes
If you want to decode a message encoded with RSA, you need to get the private key. The "simplest" method is to find the primes $p,q$ with $n=p\cdot q$.

In your case, $n=18209$ is the product of the primes $131$ and $139$. Now, you can follow the value of Euler's phi function for $n$, which is $\varphi(18209)=130\cdot138=17940$.

The private key $d$ suffices the following equation

$b\cdot d\equiv 1\mod\varphi(n)$.

To get $d$ with this property, you can use the extended euclidean algorithm for $b$ and $\varphi(n)$, which produces $x$ and $y$ with

$1=x\cdot b+y\cdot\varphi(n)$

Now, the value $x$ is your private key $d$. In your case, I get $d=4621$. To finally decode the message $m$, you have to compute

$m^d\mod n$

---
Tags: cryptography, encryption
---


# Question
Title: Is there a term for "delegate" function in CS?
*This question is all about terminology (names).*

When you consider "list", this term is well defined in CS -- despite the fact programming languages use and misuse this term (for example C# `List` is not a list).

I am looking for term in Computer Science domain that C++ defines as pointer to a function, C# as delegate, Swift as closure. Consider a function `A` that takes another function `B` as a parameter -- is there established term for `B`? Functor?

# Answer
> 3 votes
I cannot know all the parochial terminologies and concepts used by the great variety of the many - sometimes disputable - language designs available in computer science. Some design choices may be motivated by issues that are only remotely connected with science. But there is also some more or less established terminology.

When a function `A` takes a function `B` as parameter, that is simply called a **functional parameter**.

A function can be seen as composed of a control part (the code or instructions) and of an environment of entities used by the control. This environment comprises usually two kinds of program entities:

* local entities that are normally intended to be used during the lifetime of a call to the function, that have distict instances for distinct calls, and are visible only to other entities created (declared) in the body of the function. They come into existence at each function call, usually only for the duration of that call
* global entities that are defined (declared) in some (usually) enclosing structure (function, method, class instance ...) containing the function declaration, hence also visible and usable by the function. They are the same for each call of the function value created by the same declaration instance.

The function code together with its associated global environment is called a **closure**. The term is about 50 years old. But a closure is essentially a functional value.

Often the conceptual closure structure can be ignored as everything works naturally as one would hope, since a function declared in some environment usually ceases to be accessible, thus to be used, when this environment is exited. Hence it will no longer need what it was using there. It is however possible that a functional value $\gamma$ leaves the environment where its has been declared, and has to survive the disappearance of this environment where it uses some global entities. This happens mostly when another function returns $\gamma$ as a functional result.

If function `G` and variable `X` are declared in function `F`, then `G` can use `X` as a global. It may happen that the functional value $\gamma$ of `G` is returned by a call to `F`. This is no problem because that functional value $\gamma$ can be stored in a functional variable (some would probably say pointer) and just used from there. The difficulty comes from the fact that when this functional value $\gamma$ is called, it may use the variable `X` of the call to `F` that created $\gamma$, and terminated returning it. So special steps must be taken to preserve `X` for the closure, even after the call to `F` has terminated, and the corresponding environment should be no longer otherwise needed.

Actually, this occurs often in object oriented programming, for essentially the same reason. Object orientation can be implemented in a language that does not have it precisely by declaring an object constructor function with local variables (the state variables of the object constructed) that return tuples of functional values (the methods of the object class) accessing these variables. Thus the closure concept is just a very intentional and frequent occurrence in OO programming. Every method is essentially a closure on the environment implementing the state of an object. At each call to the constructor, a new tuple of closures is created for the new object, corresponding to function code that does not change, but which is closed on a new environment, the local environment of the constructor call that creates the object.

As said above, a closure is just a pair composed of a function and its globals. It is not mutable: the pair is essentially fixed when the function is created. However, the adress of such a pair is just a **pointer to a closure**, and can be stored in a variable. It can be dereferenced and called (no big mystery). But I do not know whether that is what C++ calls a pointer to a function, though I would hope it is.

You may note that creation of a closure has nothing to do with caller or callee. It has to do with the function that declares the closure, and with the function that returns it out of the environment where its globals are defined.

I am not experienced with C# delegates (so double check me), but they seem just to be functional types, that can have functions, closures, or methods as instances. This typing ensures that instances are not misused, as might happen with untyped pointers to functions. It is not clear to me whether C# allows changing the closure associated with a delegate instance, i.e. whether delegate instances are to be considered functional variables or functional constants. From what I read, it seems to be the former, hence the comparison with function pointer. Why that is necessary to pass functions or methods as parameter is apparently due to specific features of C#. Other languages do not need anything special for that: they just declare the parameter like any other, but with a functional type (i.e. a signature).

I suggest you read the wikipedia articles on closure and possibly scoping (though I have not read them in enough detail to vouch for their accuracy).

---
Tags: terminology, programming-languages
---


# Question
Title: If A is mapping reducible to B then the complement of A is mapping reducible to the complement of B
I'm studying for my final in theory of computation, and I'm struggling with the proper way of answering whether this statement is true of false.

By the definition of $\leq\_m$ we can construct the following statement,

$w \in A \iff f(w) \in B \rightarrow w \notin A \iff f(w) \notin B$

This is where I'm stuck, I want to say that since we have such computable function $f$ then it'll only give us the mapping from A to B if there is one, otherwise it wont.

I don't know how to phrase this correctly, or if I'm even on the right track.

# Answer
> 18 votes
As Dave said, it follows from a simple logical equivalence: $p \leftrightarrow q$ is the same as $\lnot p \leftrightarrow \lnot q$. Now put $p= w\in A$ and $q = f(w) \in B$.

$A \leq\_m B$ means there is a total computable $f$ s.t. for all $w$,

> $w \in A \leftrightarrow f(w) \in B$.

By the argument above, this is the same as

> $w \notin A \leftrightarrow f(w) \notin B$.

Or equivalently

> $w \in \bar{A} \leftrightarrow f(w) \in \bar{B}$.

And therefore, the same $f$ shows that $\bar{A} \leq\_m \bar{B}$.

# Answer
> -1 votes
$A \leq\_m B$ does not implie $w \in A \leftrightarrow f(w) \in B$ only the other way is true if $w \in A \leftrightarrow f(w) \in B$ then $A \leq\_m B$ but not reciprocaly

---
Tags: complexity-theory, computability, reductions
---


# Question
Title: Can the Bell-LaPadula model emulate the Chinese Wall model?
I have been reading on security policies and the question wether Bell-LaPadula can be used to implement Chinese Wall. Does anyone know more about it?

# Answer
> 3 votes
first the Bell-LaPadula Model cannot capture changes over time. second, more serious problem arises when one considers that subjects in the Chinese Wall model may choose which CDs(company dataset) to access; in other words, initially a subject is free to access all objects. the Bell-LaPadula Model cannot emulate the Chinese Wall model.

# Answer
> 2 votes
Ravi S. Sandhu has given a part of a positive answer in his 1992 paper entitled Lattice-Based Enforcement of Chinese Walls (preprint). The idea is to build a lattice from the $n$ Conflict Of Interest (COI) classes defined in the Chinese Wall: elements are tuples of the form $\[l\_1, \ldots, l\_n\]$ where $l\_i$ is either $\bot$ when no document from class $i$ has been accessed yet or a document's identifier from the class $i$.

To capture the dynamic character of the Chinese Wall policy model, the users' labels have to be updated when he/she reads a document pertaining to a COI class. In this sense, the translation is closer to high-water mark than to *pure* Bell-LaPadula.

---
Tags: information-theory, security, access-control
---


# Question
Title: If $B$, $\overline{B}\neq \varnothing$ , then for every recursive set $A$, $A \leq_m B$
How to prove if $B$, $\overline{B}\neq \varnothing$ , then for every recursive set $A$, $A \leq\_m B$ ?

it means every recursive set is mapping reducible to set $B\neq \aleph$. I really have no idea to prove this.

**UPDATE**

$A,B$ are sets, $A \leq\_m B$ if there is a computable function $f$ such that

$A = \\{ x \in N | f(x) \in B\\}$

Since we have $A \leq\_m B$ and $A$ is recursive, it means checking membership (characteristic function) in $A$ is recursive, so it means checking $f(x) \in B$ is recursive, right?

I guess it means $B$ must be recursive too and it means every recursive set is mapping reducible in to every other recursive set. Am I right?

# Answer
> 1 votes
This should be a comment on the original post by @Drupalist and on Ds D's answer, but it's too long. It's not enough to say that $A\le\_M B$ requires $B$ be recursive or that one of $B, \overline B$ be r.e.

Let $A$ be recursive and $B=\\{(\langle\\,M\\,\rangle,\langle\\,N\\,\rangle)\mid M,N\text{ are TMs and }L(M)=L(N)\\}$. This language (sometimes called $\text{EQ}\_{\text{TM}}$) is known to be neither r.e nor co-r.e. However, let

```
      M(x) =                    N(x) =
         return accept             if x = 0
                                      return reject
                                   else
                                      return accept

```

We have $(\langle\\,M\\,\rangle,\langle\\,M\\,\rangle)\in B$ and $(\langle\\,M\\,\rangle,\langle\\,N\\,\rangle)\in \overline{B}$. Then if $A$ is recursive, there is a decider TM, $D$, for A and if we define $f$ by

```
      f(x) =
         run D on x
         if D(x) = accept
            return (<M>, <M>)
         else
            return (<M>, <N>)

```

Then $f$ is Turing-computable and $x\in A\Longleftrightarrow f(x)\in B$, which is the definition of $A\le\_M B$. So we can have such a reduction in every case where it's possible to find (not necessarily by a TM) two instances $y\in B$ and $n\in\overline{B}$.

Note that I'm not claiming that this technique will work for *all* possible $B$ nor am I claiming that this technique is the only possible one. All I've shown is that the problem isn't as simple as it seems at first glance.

# Answer
> 0 votes
As I know the definition you gave is definition of many one reduction.

If at least one of $ B$ and $B^c$ be r.e. (we can assume that B is r.e.) then we have a Turing machine $T\_B$ which accept $B$ (I mean $\forall x \in B $ Turing Machine $T\_B$ answer YES and halt) and another Turing machine $T\_A$ that decides $A$. The computable function $f$ which we need is a function that for all input $x \in A$ which $T\_A$ answers YES, $T\_B$ on input $f(x)$ answer YES. it's possible to make such function so $A \leq\_m B$.

If both of $B$ and $B^c$ be not r.e. then there is no Turing machine that accepts them or computes them. since we can construct a TM for all functions it's not possible to have many one reduction between $A$ and $B$.

---
Tags: computability, reductions
---


# Question
Title: Reduction from Vertex Cover to Polygon Cover
**Polygon Cover**:

**Input**: A set of points $P$, a set of polygons $S$ in a 2D plane, and a positive integer $k \in \mathbb{N}$.

**Output**: True if and only if there exists a subset in $S$ of at most $k$ (not necessarily convex) polygons such that every point in $P$ lie inside some polygon in the subset.

I am trying to give a polynomial reduction from Vertex Cover to Polygon Cover. However, I am struggling slightly. My idea is that to construct the set of points $P$, I figured that I should map each $uv \in E$ with ($u \< v$) to a point $(u, v)$. For the set of polygons $S$, I was thinking to define some type of non-convex polygon in order to cover the rows and columns.

# Answer
Let $(G,k)$ be an instance of Dominating Set where $G$ is drawn on the plane with any drawing. Construct for each vertex $v$ a polygon $S\_v$ which covers all of $N\[v\]$ and no other vertices, where $N\[v\]$ is the set containing $v$ and all its neighbors. Let $S = \bigcup\_{v \in V(G)} S\_v$ and the points $P$ be the points where the vertices are drawn. The instance for Polygon Cover is $P, S, k$. This reduction is a Karp-reduction from Dominating Set which is NP-complete, and hence Polygon Cover is NP-complete as well.

To formally prove that the above reduction works, you need to prove that selecting a set of $k$ polygons $S' \subseteq S$ which covers all the points corresponds to picking a set of vertices whose neighborhoods contain all the vertices of the graph.

If you want to prove it for convex polygons, you can use the fact that Dominating Set is NP-complete on planar graphs and that planar graphs are equivalent to kissing graphs.
> 1 votes

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


# Question
Title: Application of set theory subjects as ordinals, forcing, generic filters in software engineering
I am going to teach a course in set theory for software engineering students. I am going to talk in this course about: ordinal numbers, partial orders, well ordering, generic filters and maybe some cardinal invariants (such as $\mathfrak b$, $\mathfrak d$). I might also give a gentel introduction to forcing theory.

I was asked by the head of the department, to add to this course some application of this theory to software engineering.

Since my main area is math and not computer science, I don't have an idea for such an application.

Any ideas for such an application? If there is I would be greatfull if you could give me a detailed source.

Thank you!

# Answer
> 5 votes
The areas of set theory you refer to are generally rather abstract and don't seem to have a lot of applications. Also, the concept of "application" is different in math than in CS. Anyway, though applied CS is so vast now that even very abstract concepts can find applications somewhere. Here is one possible link.

This paper Tree Automata Make Ordinal Theory Easy (Cachat) shows that tree automata can be used as representing ordinal sets with infinite trees. Then, once connected to automata, there are many practical applications of automata. (There are possibly other connections with Buchi automata.)

> We give a new simple proof of the decidability of the First Order Theory of ($\omega^{\omega^i}, +)$ and the Monadic Second Order Theory of $(\omega^i, \<),$ improving the complexity in both cases. Our algorithm is based on tree automata and a new representation of (sets of) ordinals by (infinite) trees.

Another idea, this blog quotes a reference that ordinal theory is used in High Frequency Trading (HFT) algorithms but there seem to be few other independent references to this on the internet. This could be explained in that HFT field is very secretive with its technology, or possibly that it's erroneous, but the claim has been repeated widely.

# Answer
> 4 votes
Generally speaking, if you want to present some applications of the theory, it's more effective to start with applications first and teach the theory that's needed for that application, rather than select a collection of theory and then search around for some application of it.

So, one way to approach your question is to ask *why* the department wants software engineers to know set theory. How will set theory help software engineers? Then once you know the answer to that question, you could devise a curriculum based upon the elements of set theory that will be relevant to software engineers. Most likely the set of topics that should be taught to software engineers is quite different from the set of topics that we would teach to mathematicians.

If you've followed this approach to course design, you should able to answer very clearly what the applications are and why you are teaching them this material. This approach can also potentially lead to better student engagement, depending on student's motivations. However, this approach likely requires re-thinking the entire course and starting over from scratch on the syllabus and topics you plan to teach, which might or might not be attractive in this case.

---
Tags: discrete-mathematics, type-theory, sets, software-engineering, applied-theory
---


# Question
Title: Converting regular (Type-3) grammar to a deterministic finite state automaton
I would like to create a deterministic finite state automaton (DFA) M=(Q, Σ, δ, q0, F) that is accepting the language generated by the following regular grammar (RG) G=(N, Σ, P, S). In short I want to **convert RG to DFA**.

```
G = ({S,A,B},{a,b},P,S)
P = {
S -> aA | bB,
A -> aS | a,
B -> bS | b
}

```

I have found these rules that convert RG to a finite automaton (which might not be deterministic if I think correctly).

```
1. δ(B, a) = C if B → aC ∈ P
2. δ(B, a) = K if B → a ∈ P
   K ∈ F
3. δ(K, *) = emptySet
   i.e. q0 ∈ F, if S → ε ∈ P
   I dont understand rule 3

```

Now I am using these rules on G this way.

```
A -> aS
becomes
δ(A, a)=S
according to
1st rule

A -> aS
becomes
δ(A, a)=K
according to
2nd rule

```

Now I already have

```
δ(A, a)=S
δ(A, a)=K

```

which means the automaton is not deterministic because

```
δ(A, a)={S,K}

```

Am I doing something wrong?

# Answer
> 2 votes
As Rick Decker said, the algorithm doesnt guarantee that the conversion from G will yieald a DFA. Therefore I should convert to a NFA and than to the DFA. The howto is here.

# Answer
> 1 votes
The way I interpret your rules (other than 1 and 2) is:

There is a state K, not corresponding to a non-terminal of the grammar, such that K ∈ F.

Then rule 3 means that there is no transition from state K, so that any further input when you are in state 3 results in rejection of the input string. The star `*` means any input, and the empty set says that any input will get you in no state, hence failure unless you have no input left.

The initial state `q0` is `S`, and it belongs also to the set F of final states iff `S → ε ∈ P`

Thus the set F of final states contains either only the state K or the two states S and K.

But as you remark, this gives you in general a NFA, a non-deterministic finite automaton.

To transform it into DFA, you need to apply the so-called **powerset construction**, that you will find in any textbook on finite automata, and in many other places, including wikipedia.

---
Tags: automata, formal-grammars, finite-automata
---


title: NP HARD Problem Longest Path in Graph

text:
# Question
Title: NP HARD Problem Longest Path in Graph
I got stuck with this problem since the whole day.

When we are finding the longest path in a graph we first do topological sorting and then check the path of adjacent vertices and keep upgrading selecting the maximum of the edge weight or the alternate path from the other vertex.

So, we are able to solve this problem because of topological sorting which can be done only for acyclic graphs. Thus this type of question can be solved only for acyclic graph.

Now, if I present another case. What if all the edge have the same weight and we don't look in the cycle of the graph. Is this solvable. Everytime I think about this I don't see any use of topological sorting if we can choose any source considering we have to choose the maximum number of nodes(longest path).

Is this also NP Hard or can we solve this?

# Answer
If I understand your problem correctly, it is NP-hard (and so NP-complete) since you can reduce Hamiltonian Path to it. Given an undirected graph, make it into a directed graph by splitting each undirected edge into two directed edges going in both directions, and ask whether there is a path of length $n-1$.
> 1 votes

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


# Question
Title: Bulk-loading R-tree with data with extent
When bulk-loading R-tree with points one can simply sort the elements by some coordinate and split to equal-sized chunks. But if the elements have some extent, sorting them by their coordinate value (whether minimum, average or maximum) can still lead to large overlap if there are some large elements involved.

(Update) I am already building the tree top-down. It was the obvious option, especially since I *don't* have 100% utilization requirement. The leaves are compressed, so they won't end up page-aligned on disk anyway. My concern is really splitting the individual elements in a better way than simply sorting by coordinate, because the elements have very different extents (from couple of metres to several kilometres, so three orders of magnitude) and also different sizes (in bytes). It is even worth unbalancing the tree a bit, because the high-level nodes easily fit in memory, so they are not critical. The decompression and parsing the leaf data is.

Is there some technique for splitting so that overlap is minimized?

# Answer
Yes, there is. It's called OMT, for Overlap Minimizing Top-down, and the first description of the algorithm can be found here: http://ftp.informatik.rwth-aachen.de/Publications/CEUR-WS/Vol-74/files/FORUM\_18.pdf
> 1 votes

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


# Question
Title: CFGs: detecting infinitely many derivations of a single string
Some particularly degenerate CFGs can produce a single string in infinitely many ways: for a dumb example, $S \to SS \mid \epsilon$ can produce the empty string as $S \to \epsilon$ or $S \to SS \to S \to \epsilon$, etc.

I'm writing a general CFG parser which can produce all the different parses for a given string, but obviously it chokes on examples like the above. I'd like to be able to detect when there may be infinitely many parses for a string, rather than just looping forever. Can I, and, if so, how?

My intuition is that a grammar has this property if and only if there is some non-useless nonterminal A (ie, A is used in the production of some string in the language of the CFG) which can produce itself via some chain of productions such that all of the other symbols produced by following that chain are nullable nonterminals of A itself. But I don't know if this is correct, and I'm not sure how to detect it.

(A nonterminal B is nullable if $B \to^\* \epsilon$, ie, some series of productions replaces the symbol with the empty string.)

# Answer
If a nonterminal can derive itself ($A \to A$) then you can have an infinite number of derivations deriving whatever else that nonterminal can derive. There is no need for it or any other nonterminal to derive $\epsilon$ (unless you are only concerned with an infinite number of parses for the empty string.)

In other words,

$$A \to A \mid a$$

can produce infinitely many parses for the string $a$. By contrast,

$$A \to A A \mid a$$

can only produce exponentially many parses for the string $a^n$.

As far as I know, the existence of a useful nonterminal which can (possibly indirectly) derive itself is necessary and sufficient for the existence of an infinite number of possible parses.

It's easy to detect whether a nonterminal can derive itself. First, use the standard algorithm to find all nullable nonterminals. Then define the relation $$ R = \\{ (A, B) \mid A \to \omega B \chi \wedge \omega \to \epsilon \wedge \chi \to \epsilon \\}$$ which you can do in linear time by scanning all the productions keeping track of nullability.

Then construct $R^+$. If it contains $(A, A)$ for any nonterminal, you have a possibly indirect self-derivation.
> 2 votes

---
Tags: context-free, parsers
---