title: How can Subset Sum be in CoNP?

text:
# Question
Title: How can Subset Sum be in CoNP?
On Wikipedia it is Written: NP and co-NP are also thought to be unequal.\[1\] If so, then no NP-complete problem can be in co-NP and no co-NP-complete problem can be in NP.\[2\]

So Subset Sum is NP-complete (given integers find a Subset that sums to 0).

CoNp is, the set of decision problems for which a "no" answer has a deterministic polynomial-time verifier.

What does No mean here in the subset sum Example? I can trivally Test if there is a subset that Doesnt sum to Zero.

# Answer
> 5 votes
A $\mathrm{No}$ answer means that there is no solution, not that there is a non-solution.

So for Subset-Sum this means there is no subset of the input integers that sum to zero, or to put it another way, every possible (non-trivial) subset has a non-zero sum. Not that there is a subset which doesn't sum to zero.

---
Tags: complexity-theory
---


title: Variation of omega definition

text:
# Question
Title: Variation of omega definition
The same question has been asked here

> Some authors define $\Omega$ in a slightly different way: let’s use $ \overset{\infty}{\Omega}$ (read “omega infinity”) for this alternative definition. We say that $f(n) = \overset{\infty}{\Omega}(g(n))$ if there exists a positive constant $c$ such that $f(n) \geq c\cdot g(n) \geq 0$ for infinitely many integers $n$, whereas the usual $\Omega$ requires that this holds for all integers greater than a certain $n\_0$.
>
> Show that for any two functions $f(n)$ and $g(n)$ that are asymptotically nonnegative, either $f(n) = O(g(n))$ or $f(n)= \overset{\infty}{\Omega}(g(n))$ or both, whereas this is not true if we use $\Omega$ in place of $\overset{\infty}{\Omega}$

The solution given in the link hints that we can negate the definition of $ \overset{\infty}{\Omega}$ which gives us the definition of big O.

But negation of the definition of $ {\Omega}$ also gives us the same result, doesn't it?

I cannot wrap my head on how the condition of infinitely many integers makes difference rather than saying for all n greater than certain $n\_0$.

Please help me understand this.

# Answer
When you negate $\Omega$ you get $\stackrel{\infty}{O}$, the analog of $\stackrel{\infty}{\Omega}$. I suggest writing the definition of $\Omega$ as a first-order formula and then negating it.

To see the difference between $\Omega$ and $\stackrel\infty\Omega$, consider the functions $f(n) = n$ and $$g(n) = \begin{cases} 1 & \text{$n$ even,} \\ n^2 & \text{$n$ odd.} \end{cases}$$ You can check that $f(n) \neq O(g(n))$ and $f(n) \neq \Omega(g(n))$, whereas $f(n) = \stackrel\infty O(g(n))$ and $f(n) = \stackrel\infty\Omega(g(n))$.
> 2 votes

---
Tags: asymptotics, landau-notation
---


# Question
Title: Can a machine choose whether or not to accept a state in a FSM
We were given a question in class with this FSM and had a debate over what the regex would be and the corresponding accepted strings. Does this FSM make sense as on state 1 there seems to be a choice between going to state 3 or looping on state 1 with the input of b.

!\[enter image description here\]\[2\]

Please forgive the bad drawing as we were given the question on paper.

# Answer
> 2 votes
The diagram appears to be of a Nondeterministic finite automaton, or NFA. A NFA is a model of a theoretical machine that accepts a given string if *any* path through the NFA for that string can end up at an accepting node.

So the simple answer to the question in the title is "yes, if you're talking about NFAs". (As opposed to Deterministic finite automata, or DFAs, which must have a unique outgoing edge for each character at a given node)

One traditional way to write a program to check if a string is accepted by an NFA is to keep track of all the states that the machine *could* be in after seeing a particular character, and then at the end declare that the string is accepted if one of the states we could be in now is an accepting state.

For example, consider the input string `abbbbb`.

At the start, the machine can only be in state $S\_0$, so the set of states it can be in is $\\{S\_0\\}$.

After `a`, the machine can now only be in $S\_1$, so $\\{S\_1\\}$.

After `ab`, the machine could be in $S\_1$ or it could be in $S\_3$, so $\\{S\_1, S\_3\\}$.

After `abb`, the machine's set of possible states is $\\{S\_1, S\_2, S\_3\\}$.

After `abbb`, the machine's set of possible states is $\\{S\_1, S\_2, S\_3\\}$.

After `abbbb`, the machine's set of possible states is $\\{S\_1, S\_2, S\_3\\}$. You should see a pattern by now.

And in fact, at the end of the whole input string `abbbbb`, the machine's set of possible states is $\\{S\_1, S\_2, S\_3\\}$, and that contains an accepting state ($S\_3$), so the string is accepted.

The regular expression should now be easily readable from the machine: `ab*(a|b)`

---
Tags: regular-expressions
---


title: Determining width of paths

text:
# Question
Title: Determining width of paths
I have an image, like the one below that has different paths. I want to be able to detect the thin parts of these paths and highlight them. What is the best way to go about this?

# Answer
Just an idea that might work. Let original image be $I\_0$. Erode just enough to remove the thin lines, then dilate back to obtain $I\_1$. Afterwards, obtain the difference of the $I\_0$ and $I\_1$.
> 6 votes

# Answer
I got a bit confused on your question. Are you looking for the paths that are thin? or are you trying to make the paths thin?

* Maybe this paper about Stroke Width Transform can help you.
* I would also like to suggest doing edge detection first. Then you compute the distance from one edge to another, both on X and Y directions, and then saving the smallest distance in each pixel of the path. To highlight the paths you will look for the smallest values saved on each pixel of the paths.

I hope this helps.
> 1 votes

---
Tags: image-processing
---


title: CTL* query evaluation order

text:
# Question
Title: CTL* query evaluation order
I'm currently trying to evaluate a CTL\* expression and am not sure how to stepwisely evaluate the queries. For example I have **EFG p**. This means something like 'there is a path where eventually there exists a state s where from there on, globally p holds true'.

Globally means that for all successors of a state on all paths starting at this state a certain property holds true.

Applied to the example above, this would mean when evaluating EFGp on a model with init-state s0, that there exists a path from s0 to a state s' where from there on all succeeding paths have the property p. But wouldn't this imply that this is equivalent to **EFAG p**?

Is it in general possible to evaluate such queries stepwise (operator by operator) or do I have to consider all operators at once?

best regards

# Answer
Your interpretation of the $G$ modality is incorrect; it does not inherently talk about all paths. In particular, the example you give specifies that there is a path such that from some point on, all states *on that path* satisfy $p$.

As you suspect, for CTL\* it is in general not possible to use a simple bottom-up evaluation, as you would for CTL, the reason being the LTL-like nested temporal operators.
> 4 votes

---
Tags: logic, model-checking, computation-tree-logic, temporal-logic
---


# Question
Title: There are pretty much no algorithms in P
(Almost) every algorithm runs in exponential time, or merely in 'pseudo-polynomial' time.

Given a list of integers, does it contain the number 2?

$\mathcal{O}(N)$, where $N$ is the size of input, right?

Wrong. Express $N$ as $2^b$, and it's $\mathcal{O}(2^b)$ and it becomes exponential runtime.

So every problem (basically) is as hard as the allegedly 'extremely difficult' factorization problem and subset sum problem.

Why do computer scientists make believe problems like the factorization problem and subset sum problem are any harder for a computer to solve than one of the first algorithms you write in your intro to CS class?

# Answer
> 15 votes
Actually you're wrong. In the example you give, you take a list of integers, but even with binary representation for the numbers in the list, the input length is still linear in the number of elements of that list, so the algorithm is polynomial ( not pseudo ). **Complexity is always measured in respect to the *total* input length**, not some arbitrary number ( b ) you choose that's correlated to the input.

Pseudo-polynomial only works for problems where your input basically consists of numbers, or lists of numbers, and that it becomes difficult only when the numbers are very large. But many problems aren't in this configuration, think of graphs for example.

Response to the other answer : Sure, it may be in O(N) for a bounded element size, but N isn't the length of the input, the length of the input is the sum of the logarithms of every element, and the dynamic programming algorithm is not polynomial in the logarithm of the elements. It's not taking a lot of small elements that makes it hard, it's taking many very big elements. Also, you could try being less arrogant when asking questions or responding : when you are wrong it just comes off as stupid and pretentious.

# Answer
> 10 votes
The premise of your question is mistaken.

The complexity is expressed as a function of the length $n$ of the input. "Does the input contain a specific, fixed bit pattern" (e.g., does it contain the number 2) can be done with a linear scan of the input: it is a linear time algorithm. The fact that you can write $n=2^b$ is irrelevant: we measure complexity with respect to $n$, not respect to $b$.

# Answer
> 2 votes
Perhaps there are some misunderstanding regarding how one arrive at the time complexity and whether or not a problem is in P. However, you are on the right path. Allow me to paraphrase the original problem:

> Given a list of $N$ integers, does the list contain the number 2?

Now, suppose each integer is represented using $b$ bits. In other words, each of these N integers are $\< 2^b$. Hence, the input size is $Nb$ ($N$ integers, each uses $b$ bits).

To perform a linear search on this list, we simply look at these $Nb$ bits and split them into groups of $b$ bits (we end up with $N$ groups). We then compare each of the $b$ bits with the binary representation of 2 prepended with $b-2$ 0 bits. We know that we can perform each of these comparison in $O(b)$ time (by iterating through the bits). We perform $N$ such comparisons. Hence, the overall runtime is then $O(Nb)$, which is linear with respect to the input size (which is $Nb$).

---
Tags: algorithms, complexity-theory, np
---


title: Address Word Structure

text:
# Question
Title: Address Word Structure
In Vol. 1 Issue 1, Jan. 1958 of the magazine *Communications of the ACM*, Dr. Saul Gorn discusses the advantages of the computer architecture of Edvac to that of Eniac.

He states that the Edvac had a **three-plus-one address word structure**, and that the tendencies of his time period were to use **one-address hardware** and **three-plus-zero address pseudo-codes**. He then goes on to say that for the future he imagines using variable instruction-word-length machines.

My questions: What is a **three-plus-one address word structure**? What is a **one-address hardware** and **three-plus-zero address pseudo code**? What do these terms mean exactly? I understand what a word is, but not to an extent that would allow me to understand these terms contextually.

Link to this issue of CACM: here. I believe an ACM membership is required to access the magazine. This question refers to Dr. Saul Gorn's Letter to the Editor.

# Answer
> 5 votes
The EDVAC employed a 44 bit word with a 4 bit op code and 4 10 bit address fields.

While the use of the fields varied a lot, the ADD instruction was typical. The memory location in field 1 was added to the memory location in field 2 and the result placed into the memory location in field 3. Execution of code then continued at the location addressed by field 4.

Thus we can summarize C = A + B; GOTO D

As for simulation with pseudo codes, we can deduce that for the Accumulator + One address machines popular at the time, the C = A + B would be simulated with three instructions and the GOTO part would be omitted. Thus three-plus-zero. It might look something like (stylized not actual code):

```
; ADD A,B,C
LD Acc, A
ADD Acc, B
ST Acc, C

```

For more on EDVAC please see:

https://babel.hathitrust.org/cgi/pt?id=mdp.39015002095639;view=1up;seq=87

---
Tags: computer-architecture
---


# Question
Title: Stroke Width Transform: Gradient Direction Computation
I've been trying to implement this paper from Boris Epshtein, Eyal Ofek, and Yonatan Wexler, the pioneers of Stroke Width Transform .

Having a simple image with random texts, that underwent gray scaling. Then I have produced two edge maps using two different algorithms for output comparison (for later) , Sobel and Canny (I'm also planning on Prewwit or other edge detection algorithms). I also have gradient maps x and y, using sobel.

on the segment of computing the gradient direction, given the equation:

theta = arctan( Gy / Gx )

where:

* theta = is the resulting angle
* Gx = is the X gradient component
* Gy = is the Y gradient component
(both Gx and Gy are from the gradient maps)

I got a bit confused. If the value of Gx is 0 (zero), and we all know dividing by zero is undefined (some say it's infinity), so are we going to make theta infinity or just 0 (zero)?

# Answer
If $Gx = 0$ and $Gy \> 0$, then we use $Gy / 0 = + \infty$. Note that $\arctan +\infty = 1$.

If $Gx = 0$ and $Gy \< 0$, then we use $Gy / 0 = -\infty$. Note that $\arctan -\infty = -1$.
> 2 votes

---
Tags: algorithms, image-processing, mathematical-programming, research
---


title: Comparing complexities with 2 variables

text:
# Question
Title: Comparing complexities with 2 variables
Suppose I have 2 possible algorithms: one runs in O(m+n) and the other runs in O(mn). Suppose also that the task is performed on a connected graph with m edges and n vertices. No other information is given about the graph. How do I know which algorithm is faster?

EDIT: I don't think my question is a duplicate of the question quicksort refers to since that question asks for a definition and I'm asking for a calculation. I did search for a solution before I posted but couldn't find any sufficient solution to my question.

# Answer
Since big O is only an upper bound, you cannot really tell which algorithm is faster. Let us therefore assume that the running times of the two algorithms are actually $\Theta(n+m)$ and $\Theta(nm)$. Since your graphs are all connected, you have $n-1 \leq m \leq \binom{n}{2}$, and so the first algorithm runs in time $\Theta(m)$ and the second in time $\Omega(m^{1.5})$. This shows that as $m\to\infty$ (equivalently, as $n\to\infty$), the first algorithm is asymptotically faster.
> 2 votes

# Answer
The function O() represent the number of steps to complete a task for a specific algorithm. O(m+n) will be always faster than O(m\*n).

\[edit\] sorry O() is not a function is a notation for classifying algorithm give an estimation (upper bound) of the number of steps for complete a task. If I have to choose between two algorithms for a specific task, one classifies O(m+n) and second classify O(mn), without any other information, I'll choose that classify O(m+n) because it's done with fewer steps.
> -2 votes

---
Tags: complexity-theory, graphs
---


title: Kleene star Empty language

text:
# Question
Title: Kleene star Empty language
I had a test a couple of days ago and one of the question had 2 statements :

1. $L^+ = L^\ast$
2. $L$ contains $\varepsilon$

I had to say does 1 imply 2, does 2 imply 1 or do they both imply each other.

I answered that only 2 implies 1 but the answer is that they both imply each other.

But I don't understand, if $L = \emptyset$ (Empty Language), then $L^\ast = \\{\varepsilon\\}$ and $L^+ = \\{ \varepsilon \\}$, they are equal and $L$ doesn't contain $\varepsilon$.

Am I wrong?

# Answer
> 4 votes
You're wrong about $L^+$:

$L = \emptyset \rightarrow L^+ = \emptyset$, but $L = \emptyset \rightarrow L^\* = \\{\epsilon\\}$

---
Tags: formal-languages, kleene-star
---


title: Maximize points of K dance moves

text:
# Question
Title: Maximize points of K dance moves
In this problem, I want to maximize the number of points of K dance moves. There are N possible dance moves.

Each of the dance moves have a point value associated with it which can be positive or negative.

There are also points from transitioning from one dance move to another. We're given an $N\times N$ matrix that has the points gained from transitioning from one dance move to another.

The brute force solution is easy which is simply try every dance move for the 1st move, then the 2nd move, then the 3rd ... which is $O(N^K)$.

My interviewer says there's a $O(NK^2)$ or $O(KN^2)$ solution (don't quite remember if it's one or the other).

How do I get that solution or what's the best solution to this problem?

Thanks!

# Answer
> 2 votes
We can model the transition of one move to another using the following discrete dynamics:

\begin{align} m\_{n+1} &= u\_{n} \end{align}

where $m\_{n}$ is the $n^{th}$ move you performed and $u\_{n}$ is the $n^{th}$ choice of the next move you will make. Note that both $m\_n$ and $u\_n$ are members of the move set, $\mathcal{M}$. The cost function you wish to maximize might then be of the form:

\begin{align} V &= P\_{M}(m\_{K+1}) + \sum\_{j=1}^{K} P\_{M}(m\_j) + P\_{T}(m\_j,u\_j) \end{align}

where $P\_{M}(\cdot)$ gives you points for your current move and $P\_{T}(\cdot, \cdot)$ gives you points from the transition from $m\_j$ to $u\_j$. Given this formulation, you can then recursively find an optimal policy, $\mu^{\*}\_{j}(m)$, that will generate optimal sequences given some move at step $n$ of the sequence. This can be found via:

\begin{align} V^{\*}\_{K+1}(m) &= P\_{M}(m) \\; \forall m \in \mathcal{M} \\ V^{\*}\_{j}(m) &= \max\_{u \in \mathcal{M}} P\_{M}(m) + P\_{T}(m,u) + V^{\*}\_{j+1}(u) \\; \forall m \in \mathcal{M}, \forall j \in \lbrace 1, 2, \cdots, K\rbrace \\ \mu^{\*}\_{j}(m) &= \arg\max\_{u \in \mathcal{M}} P\_{M}(m) + P\_{T}(m,u) + V^{\*}\_{j+1}(u) \\; \forall m \in \mathcal{M}, \forall j \in \lbrace 1, 2, \cdots, K\rbrace \\ \end{align}

Once you have found the optimal policy $\mu^{\*}\_{j}(m)$, you can obtain an optimal dance move sequence from some dummy starting move using the following:

\begin{align} m\_{n+1} &= \mu^{\*}\_{n}(m\_{n}) \end{align}

In this case, $\lbrace m\_2, m\_3, \cdots, m\_{K+1}\rbrace$ would be your optimal set of $K$ moves. Now as we can tell from the recursive algorithm, we would essentially have three nested loops to obtain the optimal policy. These nested loops together are $O(KN^2)$ because we loop through all $m$ and $u$ (both of size $\left| \mathcal{M}\right| = N$) at a given step for $K$ steps. Generating the optimal sequence is then just $K$ steps, but the recursive algorithm is the dominant part of the algorithm computationally.

**Simplified Explanation**

So in the explanation above, we defined the dynamics to obtain the next move $m\_{n+1}$ based on information we know, like the current move $m\_n$ and the choice of what move to make next, $u\_n$. We also defined a cost function to maximize, $V$.

To solve this problem using Dynamic Programming, we treat the cost function as a reward for a discrete trajectory and try to find optimal sub-trajectories, starting from the end of the sequence. The logic behind this is we can incrementally solve the optimal trajectory by using previously found optimal sub-trajectories.

We can define the final cost trajectory term as:

\begin{align} V^{\*}\_{K+1}(m\_{K+1}) &= P\_{M}(m\_{K+1}) \end{align}

where $m\_{K+1}$ is within the set of moves, $\mathcal{M}$. We can define this term because it is independent of the decision variable, $u$, which is what we are trying to find an optimal algorithmic strategy to choose. Now the recursive relationship for the next piece of the cost trajectory is:

\begin{align} V\_{K}(m\_K, u) &= P\_{M}(m\_K) + P\_{T}(m\_K, u) + V^{\*}\_{K+1}(m\_{K+1}) \end{align}

where $u$ can be any move within $\mathcal{M}$. Note how this equation depends on the value for $m\_{K+1}$. This dependence is where you incorporate your knowledge of the dynamics. We know based on the discrete dynamics that this cost term can be redefined as:

\begin{align} V\_{K}(m\_K, u) &= P\_{M}(m\_K) + P\_{T}(m\_K, u) + V^{\*}\_{K+1}(u) \end{align}

Our goal now is to find the optimal value of $V\_{K}(m\_K)$, for each value of $m\_K$ within $\mathcal{M}$, with respect to $u$. This is simply written as:

\begin{align} V^{\*}\_{K}(m\_K) &= \min\_{u \in \mathcal{M}} V\_{K}(m\_K, u) \end{align}

Note that we also define the optimal value of $u$ for a given step $j$ and a given state $m$ as the optimal policy $\mu^{\*}\_j(m)$. We can use the above findings to thus define a recursive formulation to find the optimal cost:

\begin{align} V^{\*}\_{K+1}(m) &= P\_{M}(m) \\; \forall m \in \mathcal{M} \\ V^{\*}\_{j}(m) &= \max\_{u \in \mathcal{M}} P\_{M}(m) + P\_{T}(m,u) + V^{\*}\_{j+1}(u) \\; \forall m \in \mathcal{M}, \forall j \in \lbrace 1, 2, \cdots, K\rbrace \\ \mu^{\*}\_{j}(m) &= \arg\max\_{u \in \mathcal{M}} P\_{M}(m) + P\_{T}(m,u) + V^{\*}\_{j+1}(u) \\; \forall m \in \mathcal{M}, \forall j \in \lbrace 1, 2, \cdots, K\rbrace \\ \end{align}

Note that $j$ should start at $K$ and be decremented down to $1$. Implementing this algorithm becomes a series of nested loops. This can be shown in pseudo-code to be the following:

```
for m in {Set of Moves}
  V_opt(K+1,m) = P_m(m)
end

for j going from K to 1, increment -1
  for m in {Set of Moves}
    // initialize V_opt(j,m)
    V_opt(j,m) = -Infinity

    for u in {Set of Moves}
      points = P_m(m) + P_t(m,u) + V_opt(j+1,u)
      if( V_opt(j,m) < points )
        V_opt(j,m) = points
        policy_opt(j,m) = u
      end
    end // end for loop u
  end // end for loop m
end // end for loop j

```

After finding the optimal policy $\mu^{\*}\_j(m)$ (`policy_opt(j,m)` in code), you can generate the optimal moves using the dynamics as noted previously. As you can see looking at the pseudo-code, the algorithm uses 3 nested loops, two of size $N$ and one of size $K$. This makes the problem dominated by a computational complexity of $O(KN^2)$.

---
Tags: dynamic-programming
---


# Question
Title: Why do all recent SAT solvers work on CNF instead of circuit SAT?
After the release of the AIGER library to handle and-inverter graphs sometime in 2006 (I think), some circuit SAT solvers were released in 2006-2008, and in a few SAT Races/Competitions there were AIG tracks. However since then it seems the focus has been entirely on either SMT or improving clausal SAT solvers.

Intuitively to me concentrating on circuit SAT seems to make a lot of sense: Many if not most problems are more naturally expressed as circuit SAT than CNF; circuits provide structural information that cannot be reverse engineered from CNF, but circuits can always be transformed into CNF; and at least the industrially significant field of logic synthesis seems to be a particularly good fit for AIGs.

So, what happened? Did it turn out that the extra structural information does not help solvers? Was AIG-based SAT solving a failed experiment?

# Answer
there are a lot of different angles on your question. generally agreed with your premise that looking at "structural information" in a SAT formulation ought to be an excellent research area.

* SAT encoded in CNF has been a standard for decades. it was solidified in the early-to-mid 1990s with the DIMACS format/ competitions.
* what technically is "structural information"? it may be hard to formally nail that concept down and avoid near-tautological circles. there is not really any difference between a SAT CNF encoding and and other encodings that preserve a network structure. this is embodied in the "clause/ variable graph" concepts which very many SAT solvers tend to utilize. in other words, in some rough sense, *every significant SAT solver uses "structural information"*.
* yes, newer directions in research have focused on ASP and SMT solving which nearly actually embody the "structural information" you inquire about.
* Tseytin transformation easily converts a circuit into SAT in P time/ space for input into a standard SAT solver. it is presumably widely used in many contexts esp EE circuit contexts.
* there is some rather isolated research generally along the lines you mention but unfortunately (again along with your premise) it never seemed to develop much into a research trend. dont think that is due to lack of potential but more human factors. two favorite papers\[1\]\[2\], another is to look at particular instances from areas such as "industrial instances" or "electrical engineering" instances of which there is some specialized research.
* CS purists sometimes tend to want to avoid psychology/ sociology considerations in all the mathematical abstractions, but reasonably its still a factor in computer *science*. you ask about research trends, which are based on human psychological factors. its possible there is some streetlight effect going on here aka "low hanging fruit". one might say/ consider that even now a few decades old, SAT algorithmic research is somewhat in its infancy, such that big questions like P vs NP seem nowhere in sight, and maybe existing research while still substantial is still just "scratching the surface".

\[1\] Decomposing satisfiability problems or Using graphs to get a better insight into satisfiability problems, Herwig 2006 (83pp)

\[2\] The constrainedness knife edge Walsh 1998
> 6 votes

---
Tags: satisfiability, circuits, sat-solvers
---


title: Failure of the Pumping Lemma

text:
# Question
Title: Failure of the Pumping Lemma
On the Wikipedia page for the Pumping Lemma for Context-Free Languages, a language, $$ \\{b^j c^k d^l | j, k, l \in N\\} \cup \\{a^i b^j c^k d^l | i \> 0, j = k = l\\} $$ is introduced. The pumping lemma proof for this supposedly fails because, given a string without *a*'s, you can pump the *b*'s and, given a string with *a*'s, you can pump the *a*'s. In either case, all of the possible cuttings are pumpable according to the constraints of the language.

For example, given the string $$ a^k b^k c^k d^k $$ you can split *vwx* over *|a|* and pump, leaving *|b|* = *|c|* = *|d|*.

Why can the string $$ a b^k c^k d^k $$ not be used?

This seems to meet all the constraints of the pumping lemma, and you cannot split *vwx* across *|a|*. If *v* = *a* then *x* must contain at least one *b*. The string cannot be pumped for any *i* \> 2 as the *|b|* will exceed the length of *|c|* **and** *|b|* will exceed the length of *|d|*.

Is there some reason that *|a|* \> 1 or *|a|* = *k*?

# Answer
The condition of the Pumping lemma is fulfilled for words of the form $ab^kc^kd^k$.

Pick $v=a$, $u=x = \varepsilon$, and $w$, $y$ arbitrary.
> 2 votes

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


# Question
Title: Looking for an algorithm to find a shortest path in a special graph
I have the following problem: given a directed unweighted graph and a set of source vertices, it's needed to find the shortest path to the specified vertex. The mentioned graph has two special extensions:

1. A graph's edge can be active or inactive depending on edges placed in the path before. In other words, the edge $E$ can be placed in the path at position $i$ only when $ f( E, path\[1..i-1\] )$ is true. The $f$ function in not specified explicitly; each path has a corresponding set of named properties and each graph edge has a function which modifies property values if the edge is involved (placed in the path). The edge $T$ is active (i.e. can be inserted in the path) if $g(T, set\ of\ properties)$ is true. A property may have a boolean or enum value, but it is desirable for me to allow properties to have integer and string values too.
2. Two adjacent edges in a path are not required to be linked. I.e. $path\[j\].end$ is not necessary equal to $path\[j+1\].start$. For example, we want to add the edge $B$ to the path and it has a property requirement which can only be satisfied if the edge $A$ is placed in the path before the $B$. In this case a $path\[j\]$ edge equals to the $A$ and $path\[j+1\]$ edge corresponds to the $B$. Still, $path\[j+1\].start$ should be equal to at least one of $path\[1..j+1\].end$ vertices.

The graph examples I've seen are sparse and pretty small (several dozen vertices). However some paths may contain up to several thousands of edges to satisfy the complex transition rules.

My current solution to this problem is based on the BFS algorithm. First, I construct a new graph where each vertex represents a vertex in the source graph plus the current path and it's property values. This is similar to how a game like Chess can be represented as a graph: a set of vertices each describing a current state of the game and a set of edges which describe the possible actions. Then, I simply use the BFS to find the shortest path. This approach has several drawbacks:

1. For each combination of property values a new vertex should be created. If property has an integer value, the number of vertices is going to be really large.
2. Because of the extension number two, the vertex can have a large number of edges connected. We need to represent an each edge which can be visited from this state, and when path is long the number of edges becomes big too.
3. If I need to find a path to several vertices, it's necessary to start a search several times and combine received paths. In some cases it is possible to make a shorter path if the algorithm will be aware that I actually need to reach several vertices, not the single one only.

My questions are:

1. Are there an existing name for such graphs? I've learned about dynamic graphs and they don't fully correspond to my description because they don't usually have a state (a state is the main feature of my graph).
2. Are there any better (faster, with less computational complexity, more functional) algorithms to find the shortest path in such graphs? To be more specific, are there an algorithm which solves at least some of the issues mentioned before?
3. If such algorithms exist, are there any libraries that implement it?

P.S. $f$, $g$ functions are simple logical predicates or integer arithmetic expressions. For example, to require some edge to repeat 100 times in the path I may set transition function for this edge as $i\_{new} = i\_{old} + 1$ and place another edge after it with $g$ equal to $i \> 100$. SMT solver may be a helpful tool for this task, but I don't know how to encode the problem itself in a solver format. Also I'm not sure that applying SMT is the best approach.

# Answer
The "state" of a traversal (after visiting $k$ edges) is the set of $k$ edges that you've traversed so far, in the order they were traversed. You can now use any method for exploring this state space: e.g., BFS; or A\*, if you have a suitable heuristic.

In other words, we define a new graph $G'$ where each vertex of $G'$ is a possible state of a traversal (after visiting some number of edges), and where there is an edge $u \to v$ if starting from state $u$ it is possible to add one edge to the end to reach state $v$. Then you do BFS in $G'$. You don't need to build up $G'$ explicitly before doing BFS; the graph can be represented implicitly (where each time you reach a state $u$, you can compute all possible next-states reachable from $u$ in a single step).

If BFS takes too much memory, you can use techniques from explicit-state model checking. This will reduce the space consumption but not the memory usage.

None of this avoids the fact that, for arbitrary functions $f,g$, the running time of these algorithms might all be exponential in the worst case, because you might need to explore an exponentially-sized state space. I suspect the only hope to do better is to take advantage of knowledge of some particular structure in $f,g$.
> 2 votes

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


# Question
Title: Can one truly build a schedule from graph coloring?
I know that with graph coloring we can build a simple schedule with maybe 9 students and 9 lectures (i.e. these notes) and determine the minimum number of meeting times, but is this feasible in a real world scenario? Say I have 30 professors and 200 students, can we determine a minimum number of meeting times with a graph this size? And does the graph tell us *when* they need to meet? Pointing to any available examples would be greatly appreciated.

In addition, could the graph take into account some lectures twice as long as other lectures?

# Answer
> 3 votes
> \[...\] is this feasible in a real world scenario?

I'm not sure. But note that determining the chromatic number of a graph and determining the minimum number of timeslots needed to schedule lectures with a given pattern of conflicts are exactly the same problem. So, if the scheduling problem can't be feasibly solved by colouring, it can't be feasibly solved any other way, either.

> Say I have 30 professors and 200 students, can we determine a minimum number of meeting times with a graph this size?

Note that the size of the graph depends only on the number of classes. The only effect that the number of students has is that having more students means there are more likely to be conflicts between more classes.

> And does the graph tell us when they need to meet?

No. It will just tell you "Here are sets $S\_1, \dots, S\_k$ that partition the classes." All the classes in one set should be scheduled at the same time; different sets need to be at different times. The graph doesn't care whether you study algorithms at 10am and Java at 11am, or algorithms at 11 and Java at 10, or algorithms at 3am and Java at 3pm. All it knows is that, if at least one person is studying algorithms and Java, those two classes have to be at different times.

> In addition, could the graph take into account some lectures twice as long as other lectures?

Not directly. But you could pretend that your two-hour electronics lab is really two one-hour labs called electronics1 and electronics2 which, of course, can't be at the same time, because students take both courses. And, because the graph doesn't care what time the classes are at, you can schedule electronics2 to be in the slot immediately after electronics1.

# Answer
> 2 votes
Whether or not you can solve an instance of an NP-hard problem (like graph coloring) depends crucially on the structure of the input. Even the size of the instance is not that important: even small instances can be very hard to solve, while some huge instances are solved in an instant. In other words, remember that NP-hardness is about worst case intractability.

You might be interested in checking out the recent book, *A Guide to Graph Colouring* by Lewis (Springer, 2016). It showcases real-world examples and applications of graph coloring from different domains (including scheduling problems).

---
Tags: graphs, colorings
---


# Question
Title: Proof Idea: How to prove the intersection of regular language and CFL is a CFL?
I know that the intersection of a regular language and a context free language is a context free language. I've seen this fact proven on here and other websites. However, after spending hours reading through proofs, I don't really understand the general idea of the proof itself. I'm not looking for a formal proof, but I am more concerned with understanding the high level idea. This is my basic idea for a proof, but there are some issues:

Given a regular language $R$ and a context free language $L$, the intersection of $R$ and $L$ is a context free language $L\_1$. We know that there exists a DFA $D$ that recognizes $R$, as $R$ is a regular language. We also know that there exists a PDA $P$ that recognizes $L$, as $L$ is a context free language. Since it is a fact that $D$ can be converted into a PDA $P\_1$, we know that $R$ is also a context free language. Next, we create a PDA with states as pairs of states from $P$ and $P\_1$.

This is where I am getting stuck. How are the transitions modified to simulate both PDAs? And what happens to the stack?

# Answer
> 0 votes
1. Look at the product construction for DFAs, it will give you a hint of what the state space of a PDA accepting the intersection will look like.
2. You can convert $D$ to a PDA, but you have more information than that. It doesn't need to touch the stack at all, since it can be accepted by a DFA.

These should get you close to the answer.

# Answer
> 0 votes
Don't convert $D$ to a PDA.

Instead, you can construct a PDA that accepts $R \cap L$ by using the product construction on $D$ and $P$ -- check your favorite textbook on automata theory; it should be covered there. Basically, you take $P$, and then modify its control state using the product construction. See Intersection of context free with regular languages for more details.

---

You don't want to convert $D$ to a PDA, because that would require you to take a product construction of two PDAs, and there's no good way to do that (the intersection of two context-free languages is not context-free in general).

---
Tags: regular-languages, context-free, proof-techniques
---


# Question
Title: Is the runtime complexity of sorting $O(n\log n)$ or $O(n\log^2 n)$?
Suppose we want to sort an array that contains $n$ different integers in the range $\[1,2n\]$. It is known that this requires $\Theta(n\log n)$ comparisons. But comparing integers which might be as large as $n$ might requires time $\Theta(\log n)$ since we have to compare them bitwise. So, apparently the runtime complexity of sorting is $\Theta(n\log^2 n)$. Is this correct? If so, why is it taught that the complexity of sorting is $\Theta(n\log n)$? Is there a better algorithm for sorting which runs in time $\Theta(n\log n)$?

EDIT: I understand that the question depends on the computational model. In fact, I just found an interesting unanswered question that specifically asks about the runtime complexity of sorting on a Turing machine. Originally, I had in mind a realistic computer, only with unlimited memory. In such a computer, we can represent arbitrarily large integers (as sequences of bytes). We are given an array that contains $n$ different integers, each of which is between $1$ and $2n$. We measure the clock-time it takes to sort this array, as a function of $n$. What function will we see?

# Answer
> 6 votes
Algorithms are usually analyzed using the random access machine model. In this model, arithmetic operations on machine words take time $O(1)$. A machine word contains $O(\log n)$ bits, where $n$ is some natural parameter, say the length of the input (in machine words!).

Given this definition, comparison-based sorting algorithms run in time $O(n\log n)$ as long as the arguments fit in a constant number of machine words.

Sorting algorithms probably take more than $n\log^2 n$ time on a Turing machine, since Turing machines have no random access. Turing machines are not so interesting, however, for analyzing the running time of algorithms, except for special circumstances such as proving results on the Turing machine model itself.

In your particular case, you can actually sort the array in $O(n)$ using counting sort. The $\Omega(n\log n)$ lower bound only holds for some models such as the comparison model.

# Answer
> 3 votes
The correct statement is that any comparison-based sorting algorithm will require $\Theta(n\log n)$ *comparisons* in the worst case. How long each comparison will take depends on what you're sorting and what model of computation you're using.

---
Tags: runtime-analysis, sorting
---


# Question
Title: Number of n-node binary trees containing an m-node binary subtree
In a paper I see the following lemma about unlabeled binary trees:

> If $s\_1$ and $s\_2$ are both m-node binary trees, then the number of n-node binary trees containing $s\_1$ as a subtree is the same as the number of n-node binary trees containing $s\_2$.

It goes on to use this to show that if you want to compute the number of n-node binary trees that have m-node as a subtree, it doesn't matter what m-node tree you use.

I feel like I'm either misinterpreting this or missing something obvious. But isn't the following setup a contradiction to this lemma:

Nodes 2a and 6a produce the same tree, so tree 1 is only the subtree of 5 4-node trees while tree 2 is a subtree of 6 4-node trees.

# Answer
You haven't defined what a subtree is, so let's assume that $S$ is a subtree of $T$ if there is a node $x \in T$ whose subtree is isomorphic to $S$ (the notion of isomorphism depends on the definition of subtree).

Now suppose $S\_1,S\_2$ are two trees on $m$ of vertices. For any tree $T$, mark all the nodes whose subtrees contain $m$ vertices. Define $\pi(T)$ by replacing all such nodes whose subtree is isomorphic to $S\_1$ by a subtree isomorphic to $S\_2$, and vice versa. For any $n$, this is an involution on the set of trees on $n$ vertices which satisfies the following property: $T$ contains $S\_1$ iff $\pi(T)$ contains $S\_2$. This shows that the number of trees of size $n$ containing $S\_1$ is the same as the number of trees of size $n$ containing $S\_2$.
> 0 votes

---
Tags: binary-trees
---


title: Does a computer do only two things?

text:
# Question
Title: Does a computer do only two things?
According to the book, Introduction to Computation And Programming Using Python by John V Guttag, a computer does only two things:

* Store data
* Manipulate data

But is this all? I mean, without I/O, can a computer be considered useful?

# Answer
I think the author is over simplifying to make a point. Obviously a computer needs to take input and produce an output to have any value. But usually, when you press a key on your keyboard, it is altering data in a reserved memory location and that's how the computer even knows you pressed something, because it sees that data changed. That's what a "memory mapped I/O" is--specific places in memory that the computer looks for input changes. So depending on how you look at it, input and output is still just storing and manipulating data. But if you attach a motor to it, then your computer can do just about anything.
> 1 votes

# Answer
The statement is obviously false: my computer can make sounds and it's hard to see that that as either storing or manipulating data. I suggest you just ignore it and move on, since producing this kind of list does nothing to help your understanding of computers, programming or anything else.
> 7 votes

# Answer
The problem with such a statement is that you need to understand them in a very specific context and at a specific level of abstraction only. For example I could say an electronic computer just move electrons around, which is correct if the context and the abstraction level is just electrons but it is not useful outside of that context.
> 2 votes

# Answer
This is what is called a truism. It's true, but not really useful.

For example: You mention I/O. Consider showing a picture on the screen. At some level, the computer manipulates the data into a series of pixel values and then stores those values in a memory buffer that just happens to be the video buffer of the graphics card. The graphics card hardware just takes that data and manipulates it into an HDMI data stream for the monitor and shazzam... a picture on the screen.

The same can be said for any I/O or any other operation. Just moving (storing if you frame your perspective "correctly") data around while manipulating it to the desired form.

True Yes. Useful, only on the most abstract level. Perhaps as a conceptual starting point in the introduction of a book.
> 1 votes

---
Tags: computer-architecture, computation-models
---


# Question
Title: NFA models with characters on nodes, not edges
I am attempting to understand the inner workings of the open source string matching library Hyperscan.

It takes a multiple-engine approach to the problem of generating string matches, and I'm still in the early stages of following through the debugging output to see how it does what it does.

However, one design decision already visible at this point puzzles me: when constructing an NFA, it doesn't use the traditional model of a directed graph with edges labeled with characters, and nodes labeled with whether or not they accept. Instead, it seems to use a model (\*) of a directed graph with unlabeled edges and nodes labeled with a set of characters that can reach this node, along with designated special nodes for accepting strings. (specifically, it has a special `NODE_ACCEPT` node and a special `NODE_ACCEPT_EOD` node; nodes that mean "accept and ignore remaining input" have edges to `NODE_ACCEPT` and nodes that mean "accept if at end of input" have edges to `NODE_ACCEPT_EOD`)

I think this model is equivalent to the standard NFA model, but I can't find any references to this NFA model anywhere; I wonder if it goes by a standard name that I just don't know, and therefore can't search for. (My attempts just get buried in page after page of explanations of the standard NFA model)

So, has anyone seen an NFA model like this before? Are there any references I can look at to find out why one might prefer a model like this?

(On the off chance that anyone has already written up something on how the compiler and the various string matching engines embedded inside the Hyperscan library work, I'd also love any pointers to that. I primarily want to learn about state-of-the-art string-matching techniques, not about how to reverse-engineer C++.)

(\*) I'm simplifying slightly here and ignoring bits of node and edge labels that seem unused at the initial stages.

# Answer
Hyperscan chief architect here.

The buzzword you are looking for is a Glushkov NFA, as opposed to a Thompson NFA.

The 'traditional model' you refer to is a Thompson NFA but is by no means the only choice. Both have their strengths and weaknesses, but we found the Glushkov NFA quite economical and it maps very nicely to a bitwise implementation (the "LimEx" NFA is a concrete NFA implementation, as opposed to the NFAGraph, which is an abstract representation). The joy of the Glushkov NFA is that the calculation of "reach" (which states are reached on which characters) and "succ" (which states can succeed other states) are completely independent and can be combined with a simple AND operation.

Gonzalo Navarro has a number of very nice papers and an excellent book on this subject. In terms of underlying approaches (if no the specific algorithms) we are entirely indebted to him.

Feel free to contact the Hyperscan list or alias if you want more information. We have been very lax in terms of writing up our approach.
> 5 votes

# Answer
You should look in the finite-automata literature for the terms 'Moore Machine' and 'Mealy Machine'. Comparing the two definitions will be instructive.
> 1 votes

---
Tags: algorithms, finite-automata, string-matching
---


# Question
Title: What is the name for polynomially solvable optimisation problems?
An optimisation problem that allows to solve a NPC decision problem through a polynomial reduction is called NP-hard. For these optimisation problems no polynomial algorithm is known.

Symmetrically, is there a standard name for all those optimisation problems for which a polynomial algorithm is known?

# Answer
> 3 votes
An optimization problem is an example of a function problem: i.e., one where the task is to map some input to some output. The class of function problems solvable in polynomial time is **FP**. See, for example, the Complexity Zoo.

(Note that there is a class **OptP** but that's not the polynomial-time optimization problems. Perhaps confusingly, it's the optimization analogue of **NP**: it's the class of functions that can be defined by taking the maximum out the outputs given by accepting paths of a nondeterministic polynomial-time Turing machine.)

# Answer
> 1 votes
The book Complexity and Approximation by Ausiello et al. uses the name **PO** for the class of optimization problems that can be solved optimally in polynomial time.

---
Tags: terminology, optimization, polynomial-time
---


# Question
Title: How to prove that Inner product of two $n$ dimensional vectors requires at least $n$ many multiplications?
**Input :** Two matrices $A$ and $B$ of size $n$ X $n$.

**Compute :** Matrix product $A$ X $B$.

Some of the known results about matrix multiplication are given below.

Brute Force : $O(n^3)$.

Nader H. Bshouty : at least $2.5$ $n^2 -$$o( n^2 )$ \[over binary field\] multiplications. A lower bound for matrix multiplication

A paper by Yijie Han : Matrix Multiplication Algorithm by Yijie Han

After reading the paper above I come to know that lower bound for matrix multiplication reduces to the problem of finding inner product of two vectors. I know how to compute a inner product of two vector in a brute force way. So my question is

**Question** : How to prove that Inner product of two $n$ dimensional vectors requires at least $n$ many multiplications ?.

# Answer
Here is a proof in the real case. For general fields, this only gives a lower bound of $\lceil n/2 \rceil$, though the correct lower bound should indeed be $n$. For more, take a look at the monograph *Algebraic complexity theory* by Bürgisser, Clausen and Shokrollahi.

## Model

It will be easier to give a lower bound on computing the inner product of a vector with itself; this is a potentially easier task. Consider an arithmetic "straight-line" program for computing the squared norm $\sum\_{i=1}^n x\_i^2$. Such a program consists of the following operations: addition, subtraction, multiplication, division, all of which of the form $a \gets b \circ c$. We are also allowed to "load" input variables and arbitrary field constants. The final answer must be found in some variable. Since we don't care about space, we can assume that every operation assigns its output to a new variable.

For simplicity we will not allow division in what follows, though divisions can always be eliminated (this is a famous result of Strassen), without too much trouble.

Here is an example of such a program:

> $t\_1 \gets x\_1 \cdot x\_1$
>
> $t\_2 \gets x\_2 \cdot x\_2$
>
> ...
>
> $t\_n \gets x\_n \cdot x\_n$
>
> $s\_2 \gets t\_1 + t\_2$
>
> $s\_3 \gets s\_2 + t\_3$
>
> ...
>
> $s\_n \gets s\_{n-1} + t\_n$

The variable $s\_n$ contains the inner product.

## Normal form (1)

The first step is coming up with a program in normal form. Let $t$ be a variable occurring in the program. The value of $t$ is always a fixed polynomial in the inputs (if we allowed divisions, it could be a more general power series). We write $t$ as a sum $t = t^{(0)} + t^{(1)} + t^{(2)} + t'$, where

* $t^{(0)}$ is a constant.
* $t^{(1)} = \sum\_i c\_i x\_i$.
* $t^{(2)} = \sum\_{i \leq j} d\_{ij} x\_i x\_j$.
* $t'$ consists of all monomials of degree larger than 2.

We will convert an arbitrary program into one which computes only the parts $t^{(0)},t^{(1)},t^{(2)}$, and furthermore contains no more "essential" multiplications than the original program; a multiplication is not essential if one of the operands is a constant. Since the output variable $o$ satisfies $o = o^{(2)}$, the new program also computes the squared norm.

The base cases are when $t$ is constant or an input variable. In both cases no computation is needed, since each part is either zero, a constant, or an input variable.

We replace the operation $a \gets b + c$ with the sequence $a^{(0)} \gets b^{(0)} + c^{(0)}$, $a^{(1)} \gets b^{(1)} + c^{(1)}$, $a^{(2)} \gets b^{(2)} + c^{(2)}$. Subtraction is similar.

The most interesting operation is $a \gets b \cdot c$, which we replace by the sequence

> $a^{(0)} \gets b^{(0)} \cdot c^{(0)}$
>
> $a^{(1')} \gets b^{(0)} \cdot c^{(1)}$
>
> $a^{(1'')} \gets b^{(1)} \cdot c^{(0)}$
>
> $a^{(1)} \gets a^{(1')} + a^{(1'')}$
>
> $a^{(2')} \gets b^{(0)} \cdot c^{(2)}$
>
> $a^{(2'')} \gets b^{(1)} \cdot c^{(1)}$
>
> $a^{(2''')} \gets b^{(2)} \cdot c^{(0)}$
>
> $a^{(2'''')} \gets a^{(2')} + a^{(2'')}$
>
> $a^{(2)} \gets a^{(2''')} + a^{(2'''')}$

The only essential multiplication is involved in computing $a^{(2'')}$.

It is routine to check that the new program indeed computes $t^{(0)},t^{(1)},t^{(2)}$ correctly for all $t$ occurring in the original program.

## Normal form (2)

Consider the new program. It is not hard to prove by induction that for each original variable $t$,

* $t^{(0}$ is a constant.
* $t^{(1)}$ is a linear combination of inputs, i.e. of the form $\sum\_i c\_i x\_i$.
* $t^{(2)}$ is a linear combination of the results of essential multiplications (multiplications of the form $s^{(1)} \cdot r^{(1)}$).

In particular, if there are $m$ multiplications in the original program then there are $m$ essential multiplications in the new program, and so it is semantically equivalent to the following program:

* Compute $2m$ linear combinations $\ell\_1,\ldots,\ell\_{2m}$ of the inputs.
* Compute $m$ essential multiplications $p\_i \gets \ell\_{i\_1} \cdot \ell\_{i\_2}$, for $1 \leq i \leq m$.
* Output a linear combination $\sum\_{i=1}^m c\_i p\_i$.

In fact, without loss of generality we can assume that $c\_i = 1$.

## Rank lower bound

Given a program computing the inner product $\sum\_{i=1}^n x\_i y\_i$ using $m$ multiplications, we have shown how to obtain a representation $$ \sum\_{i=1}^n x\_i^2 = \sum\_{j=1}^m \ell\_j r\_j, $$ where $\ell\_j,r\_j$ are linear combinations of the $x\_i$. Replace $\ell\_j,r\_j$ with coefficient vectors of length $n$, say column vectors. The representation then implies the matrix identity $$ I\_n + S = \sum\_{j=1}^m \ell\_j r\_j^T, $$ where $S$ is a skew-symmetric matrix (we get $S$ since $x\_ix\_j$ can be represented in two ways for $i \neq j$). *If we are working over the reals*, then all eigenvalues of $S$ are either zero or pure imaginary, and so $I\_n + S$ has full rank. The right-hand side implies that the rank is at most $m$, and we conclude that $m \geq n$.

When working over the complex numbers, we can have shortcuts such as $$ (x\_1 + ix\_2)(x\_1 - ix\_2) = x\_1^2 + x\_2^2. $$ The same method still shows that $n/2$ multiplications are needed, and indeed the optimal number of multiplications to compute the squared norm is $\lceil n/2 \rceil$.
> 5 votes

---
Tags: algorithms, algorithm-analysis, lower-bounds
---


# Question
Title: Sum of k smallest values of affine functions
Assume we have a fixed number of $n$ one-dimensional affine functions of the form $f\_i(x) = a\_i x + b\_i$ for $i \in N = \\{1,\ldots,n\\}$.

Consider some fixed value $k \in \\{0,\ldots,n\\}$. Let $S\_k : \mathbb{R} \mapsto 2^N$ (power set) denote a function mapping some value $x \in \mathbb{R}$ to the set of indices of the $k$ smallest functions at $x$, so for all $x \in \mathbb{R}$, it holds that $|S\_k(x)| = k$ and $f\_i(x) \leq f\_j(x)$ if $i \in S\_k(x)$ and $j \notin S\_k(x)$.

The question is: If we hold $f\_1,\dots,f\_n,k$ fixed and allow $x$ to vary, **how many different sets can $S\_k$ map to? In other words, which cardinality can the image of $S\_k$ have?**

For $k=0$ or $k=n$, there is only one possible set for all $x$ (either $\emptyset$ or $N$). Similarly, for $k=1$ or $k=n-1$, there are $n$ different sets each (since this is equal to the maximum or minimum element, which can change $n$ times while x increases).

But is there a general formula for arbitrary values of $k$? It seems that the maximum is attained at $k = \frac{n}{2}$.

Note that an upper bound is given by $O(n^2)$ since this is the maximum number of intersection points of the involved functions, which, thus, bounds the number of orderings. However, I think this bound is too rough. In computational experiments I have never seen a value of $2n$ or more.

# Answer
> 2 votes
I recently found out that my problem is known as the *k-th level problem*, which itself is equivalent to the *k-set problem* in the dual plane. Since almost 50 years, it is an open problem how many sets there are exactly. At present, the best upper bound is given by $O(n k ^{1/3})$: https://en.wikipedia.org/wiki/K-set\_(geometry)

---
Tags: combinatorics
---


# Question
Title: Regular expression for a language which doesn't look regular
I'm trying to find a regular expression for the following language:

$$L=\\{x0y : \text{$x$ contains same number of 0's as $y$ contains 1's}\\}. $$

# Answer
The trick is to write $L$ as a different language. Let's consider the following similar language $$ L' = \\{ xy \in \\{0,1\\}^\* : \\#\_0(x) = \\#\_1(y) \\}, $$ where $\\#\_0(x)$ is the number of 0's in $x$.

I claim that $L' = (0+1)^\*$. Indeed, let $w = w\_1\ldots w\_n$ be some arbitrary word, and define $\delta\_w(i) = \\#\_0(w\_1\ldots w\_i) - \\#\_1(w\_{i+1}\ldots w\_n)$. The following properties are not hard to check:

1. $\delta\_w(0) \leq 0$.
2. $\delta\_w(n) \geq 0$.
3. $\delta\_w(i+1) = \delta\_w(i) + 1$ for $0 \leq i \leq n-1$.

This shows that $\delta\_w(i) = 0$ for some $0 \leq i \leq n$, and so $w \in L'$.

Your case is very similar - I'll leave you to figure out the details.
> 1 votes

---
Tags: regular-languages, regular-expressions
---


# Question
Title: Express boolean logic operations in zero-one integer linear programming (ILP)
I have an integer linear program (ILP) with some variables $x\_i$ that are intended to represent boolean values. The $x\_i$'s are constrained to be integers and to hold either 0 or 1 ($0 \le x\_i \le 1$).

I want to express boolean operations on these 0/1-valued variables, using linear constraints. How can I do this?

More specifically, I want to set $y\_1 = x\_1 \land x\_2$ (boolean AND), $y\_2 = x\_1 \lor x\_2$ (boolean OR), and $y\_3 = \neg x\_1$ (boolean NOT). I am using the obvious interpretation of 0/1 as Boolean values: 0 = false, 1 = true. How do I write ILP constraints to ensure that the $y\_i$'s are related to the $x\_i$'s as desired?

(This could be viewed as asking for a reduction from CircuitSAT to ILP, or asking for a way to express SAT as an ILP, but here I want to see an explicit way to encode the logical operations shown above.)

# Answer
**Logical AND:** Use the linear constraints $y\_1 \ge x\_1 + x\_2 - 1$, $y\_1 \le x\_1$, $y\_1 \le x\_2$, $0 \le y\_1 \le 1$, where $y\_1$ is constrained to be an integer. This enforces the desired relationship. See also https://or.stackexchange.com/q/37/2415.

**Logical OR:** Use the linear constraints $y\_2 \le x\_1 + x\_2$, $y\_2 \ge x\_1$, $y\_2 \ge x\_2$, $0 \le y\_2 \le 1$, where $y\_2$ is constrained to be an integer.

**Logical NOT:** Use $y\_3 = 1-x\_1$.

**Logical implication:** To express $y\_4 = (x\_1 \Rightarrow x\_2)$ (i.e., $y\_4 = \neg x\_1 \lor x\_2$), we can adapt the construction for logical OR. In particular, use the linear constraints $y\_4 \le 1-x\_1 + x\_2$, $y\_4 \ge 1-x\_1$, $y\_4 \ge x\_2$, $0 \le y\_4 \le 1$, where $y\_4$ is constrained to be an integer.

**Forced logical implication:** To express that $x\_1 \Rightarrow x\_2$ must hold, simply use the linear constraint $x\_1 \le x\_2$ (assuming that $x\_1$ and $x\_2$ are already constrained to boolean values).

**XOR:** To express $y\_5 = x\_1 \oplus x\_2$ (the exclusive-or of $x\_1$ and $x\_2$), use linear inequalities $y\_5 \le x\_1 + x\_2$, $y\_5 \ge x\_1-x\_2$, $y\_5 \ge x\_2-x\_1$, $y\_5 \le 2-x\_1-x\_2$, $0 \le y\_5 \le 1$, where $y\_5$ is constrained to be an integer.

Another helpful technique for handling complex boolean formulas is to convert them to CNF, then apply the rules above for converting AND, OR, and NOT.

---

And, as a bonus, one more technique that often helps when formulating problems that contain a mixture of zero-one (boolean) variables and integer variables:

**Cast to boolean (version 1):** Suppose you have an integer variable $x$, and you want to define $y$ so that $y=1$ if $x \ne 0$ and $y=0$ if $x=0$. If you additionally know that $0 \le x \le U$, then you can use the linear inequalities $0 \le y \le 1$, $y \le x$, $x \le Uy$; however, this only works if you know an upper and lower bound on $x$.

Alternatively, if you know that $|x| \le U$ (that is, $-U \le x \le U$) for some constant $U$, then you can use the method described here. This is only applicable if you know an upper bound on $|x|$.

**Cast to boolean (version 2):** Let's consider the same goal, but now we don't know an upper bound on $x$. However, assume we do know that $x \ge 0$. Here's how you might be able to express that constraint in a linear system. First, introduce a new integer variable $t$. Add inequalities $0 \le y \le 1$, $y \le x$, $t=x-y$. Then, choose the objective function so that you minimize $t$. This only works if you didn't already have an objective function. If you have $n$ non-negative integer variables $x\_1,\dots,x\_n$ and you want to cast all of them to booleans, so that $y\_i=1$ if $x\_i\ge 1$ and $y\_i=0$ if $x\_i=0$, then you can introduce $n$ variables $t\_1,\dots,t\_n$ with inequalities $0 \le y\_i \le 1$, $y\_i \le x\_i$, $t\_i=x\_i-y\_i$ and define the objective function to minimize $t\_1+\dots + t\_n$. Again, this only works nothing else needs to define an objective function (if, apart from the casts to boolean, you were planning to just check the feasibility of the resulting ILP, not try to minimize/maximize some function of the variables).

---

For some excellent practice problems and worked examples, I recommend Formulating Integer Linear Programs: A Rogues' Gallery.
> 98 votes

# Answer
The logical AND relation can be modeled in *one* range constraint instead of *three* constraints (as in the other solution). So instead of the three constraints $$y\_1\geq x\_1+x\_2−1,\qquad y\_1\leq x\_1,\qquad y\_1\leq x\_2\\,,$$ it can be written using the single range constraint $$0 \leq x\_1 + x\_2-2y\_1 \leq 1\\,.$$ Similarly, for logical OR: $$0 \leq 2y\_1 - x\_1 - x\_2 ≤ 1\\,.$$

For NOT, no such improvement is available, because NOT is restricted to one argument.

In general for $y=x\_1 \land x\_2 \land \dots \land x\_n$ ($n$-way AND) the constraint will be: $$0 \leq \sum x\_i -ny \leq n-1\\,.$$ Similarly for OR: $$0 \leq ny -\sum x\_i \leq n-1\\,.$$
> 22 votes

# Answer
I found shorter solution for XOR y=x1⊕x2 (x and y are binary 0, 1)

just one line: x1 + x2 - 2\*z = y (z is any integer)
> 3 votes

---
Tags: linear-programming, integer-programming
---


# Question
Title: Draw DFA that accepts concatenated binary string with condition
Let $\Sigma = \\{0,1\\}$, with $w \in \Sigma^\* $ and $value(w)$ the not negative integer value of $w$. $w$ is seen as binary string, with its first index being the least significant bit:

$$value(w\_1 w\_2 ... w\_n) = \Sigma\_{i=i}^n 2^{i-1} w\_i$$

The languages is defined as: $$L = \\{a\_1b\_1a\_2b\_2 ... a\_nb\_n \ \in \ \Sigma^\* \ \vert \ value(a\_1a\_2 ... a\_n) = 3 \ \cdot \ value(b\_1b\_2 ... b\_n)\\}$$

The task is to draw the accepting DFA. I frankly have no idea on how to approach this question. Can someone give me a hint, not the full answer please?

# Answer
Hint: $3\operatorname{value}(u)=\operatorname{value}(u)+\operatorname{value}(0u)$. Then you're just doing a simple addition with carry.

---

By the way, there's a much stronger result: For any first order formula $\varphi(x\_1,\dots,x\_n)$ of the Presburger arithmetic, there is an automaton $A$ over $\\{0,1\\}^n$ so that $A$ accepts $u$ iff $\varphi(\operatorname{value}\_1(u),\dots,\operatorname{value}\_n(u))$ is true (where $\operatorname{value}\_i(u)$ is the same value that you defined except that since each "letter" of $\\{0,1\\}^n$ contains several digits, it only looks at the $i^{th}$).

Your question is a special case of this where the formula is $\varphi(a,b)= \`\`a=3b"$. (Kind of: if $L$ is what you get for this formula, then you'd need to take $f(L)$ where $f$ is the morphism defined by $(b\_1,b\_2)\mapsto b\_1b\_2$).
> 1 votes

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


# Question
Title: Where does the heuristic come from in the A-star algorithm and how do we know it has the right properties?
I am trying to understand some notes regarding the A-star algorithm. The example used is to show how the algorithm can be used as a (more efficient) alternative to Dijkstra's algorithm for finding shortest path. I am reading about A\* search starting page 71 of the UK GCE Computing textbook, Rouse to find shortest path. I have also read the Wikipedia entry - but to no avail. Two things do not makes sense to me.

(i) Where do the heuristic values for shortest distance come from? There is mention of "straight roads" but I don't understand this. I know "heuristic" is "informed guess" but why not values 1237, 978, 516, ... etc. or any other arbitrary, descending values for the heuristic distance "still to go" ?

(ii) What is the significance and meaning of "the heuristic must never make an over-estimate"? How do we know that, and why is it important? Surely all the intermediate distances before the completion of the A\* algorithm are "over-estimates".

Regards,

Clive

# Answer
> (i) Where do the heuristic values for shortest distance come from? There is mention of "straight roads" but I don't understand this. I know "heuristic" is "informed guess" but why not values 1237, 978, 516, ... etc. or any other arbitrary, descending values for the heuristic distance "still to go" ?

When you decide to use A\* to solve a problem, you need to design an appropriate heuristic. Designing a heuristic is a creative act, so one can't really give advice on how to do it. Ideally, though, the heuristic should give a good estimate of the true cost.

The purpose of the heuristic is to guide the search and a search that receives accurate guidance will terminate faster than one that receives poor guidance. There is, however, a trade-off. If your heuristic is perfect, then it will guide the search so well that the optimal route is the first one it examines. But, of course, if you could compute this perfect heuristic, you wouldn't need to be using search in the first place! Having a better heuristic means you spend less time searching, but you need to balance that against the fact that you'll probably spend more time computing this better heuristic.

> (ii) What is the significance and meaning of "the heuristic must never make an over-estimate"? How do we know that, and why is it important?

You know it because you figured it out and you designed the heuristic to achieve that. The classic example is using straight-line distance as a heuristic for navigation. You know that the straight-line distance is the shortest possible distance between two points, so it cannot overestimate the distance you'd have to travel on the road network.

I wrote an answer a while ago about why it's important that you don't overestimate. Essentially, if you say "every route via X is long", the algorithm will first look at routes via other places, and potentially find one. When it finds an answer, it will stop. But it never considered routes via X so, if it turns out that the shortest route was via X, you missed it because your heuristic overestimated.

> Surely all the intermediate distances before the completion of the A\* algorithm are "over-estimates".

No. A\*'s use of the heuristic means that, any time you expand a node in the search, you've found the shortest possible path to that node. So, every time you expand a node, you've found the optimal path to that node, plus an underestimating heuristic to the goal: all your intermediate states that get expanded are underestimates. There might be over-estimates in the frontier (i.e., suboptimal routes to intermediate goals) but they'll never get expanded.
> 6 votes

# Answer
One additional remark relating to point (i) of David's answer. Often, it does indeed make sense to come up with a heuristic *manually*, using and exploiting your domain knowledge about your specific search problem.

There are, however, also ways of deriving heuristics *automatically*, something that is routinely done in automated planning. These automatic approaches typically assume that the graph you want to search is given by a compact, structured model, where each node can be seen as an assignment of values to a set of state variables, and where the transitions are encoded by preconditions and effects on those state variables. Then, a very general idea of deriving heuristics automatically is to look at a simplified version of the model (and at the corresponding graph), to determine shortest goal distances in that simplified model, and to use those shortest goal distances as heuristic values when searching in the original graph.

For instance, one specific class of such heuristics are *abstraction heuristics*: many concrete nodes are represented by the same abstract node, so you get a smaller graph; whenever there is an edge in the original concrete graph, there must be a corresponding edge in the abstract graph; and start and goal nodes should be preserved. This guarantees that for every start-goal path in the original graph, there is also a corresponding start-goal path in the abstract graph that is at most as long as the original one. This then implies that the abstraction heuristic will never make an over-estimate.

Besides abstraction heuristics, there are also other classes of automatically derived heuristics in planning, like delete-relaxation heuristics, landmark heuristics, potential heuristics, etc.
> 2 votes

---
Tags: algorithms, search-algorithms, shortest-path
---


# Question
Title: right and left derivatives of a cfg from parse tree?
i just want to double check with what i concluded from this parse trees.

> ```
>        A
>       / \
>      /   \
>     B      C
>    / \    / \
>   0   D  D   E
>          |   |
>          0   1
>
> ```

from the above tree i get right derivation to be

> A -\> C
>
> C -\> D|E
>
> E -\> 1
>
> D -\> 0

and the left derivation as

> A -\> B
>
> B -\> 0|D
>
> D -\> 0

i just want someone to proof check for me. and tell me if am wrong somewhere. Thanks!

# Answer
> 2 votes
What you wrote are not derivations, they are grammars.

The leftmost derivation in your case is $A \to BC \to 0DC \to 0DDE \to 0D0E \to 0D01$. I'll leave you to figure out the rightmost derivation.

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


title: Color Filler Algorithm

text:
# Question
Title: Color Filler Algorithm
Is there an algorithm that fills the area outside the edges?

e.g.:
From this
to this

# Answer
Assuming for simplicity that the edges don't touch the image boundary (you can always guarantee that by adding a pixel-wide "frame"), you can simply run flood fill from an arbitrary point on the image boundary.
> 2 votes

---
Tags: algorithms, image-processing
---


# Question
Title: Embedding SATISFIABILITY into 3-DIMENSIONAL MATCHING
> Using the fact that the satisfiability problem is NP Complete, demonstrate that the 3-Dimensional Matching problem is NP Complete.

I am currently in need of clarification of the proof of the above statement as given in the Combinatorial Optimization text by Papadimitriou and Steiglitz. I am a graduate student in mathematics currently finishing my dissertation, and one of my chapters includes a citation and quote of this result, and a clear understanding of it has so far escaped me. In order to minimize the inevitable wall of text, I will summarize the proof as briefly as possible.

The authors reduce SATISFIABILITY to instances of 3-DIMENSIONAL MATCHING as follows: given a Boolean formula $F$ with clauses $C\_1, \ldots, C\_m$ over literals $x\_1, \ldots, x\_n,$ the sets $$U=\\{x\_i^j, \bar{x}\_i^j\\},i \in \[n\], j \in \[m\],$$

$$V=\\{a\_i^j\\}\cup\\{v\_j\\}\cup\\{c\_i^j\\}, $$ and $$W=\\{b\_i^j\\}\cup\\{w\_j\\}\cup\\{d\_i^j\\}, i \in \[n-1\], j \in \[m\]$$ are constructed, with $i \in \[n\]$ for the $a$ and $b$ elements and $i \in \[n-1\]$ for the $c$ and $d$ elements and $j \in \[m\]$ as before. I noted that $|U|=|W|=|V|=2mn$ to verify identical cardinality of these three sets.

The triplet set $$T=\\{(x\_i^j, a\_i^j, b\_i^j)\\} \cup \\{(\bar{x}\_i^j, a\_i^{j+1}, b\_i^j)\\} \cup \\{(\lambda\_j, v\_j, w\_j)\\} \cup \\{(\lambda\_k, c\_i^j, d\_i^j)\\}$$ is then constructed, where $i \in \[n\], j \in \[m\]$ in the first three sets of this union and $i \in \[n-1\], j \in \[m\], k \in \[m\]$ in the fourth set in this union. It is stated that $\lambda\_j$ in the third set in this union are literals in $C\_j;$ the $\lambda\_k$ in the fourth set in this union are simply identified as literals.

First, we assume that a subset $S \subset T$ exists such that each element of $U,$ $V,$ and $W$ appears in exactly one triplet in $S.$ Because of the definition of $T$ and these constraints on $S,$ we know that at least $mn$ triplets of the first two sets listed in the representation for $T$ appear in $S$; because no pair in $S$ can match elementwise, it follows that exactly $mn$ elements are chosen from these "a,b" triplets, since for each $i,$ exactly one of $x\_i^j$ or $\bar{x}\_i^j$ are present in triplets of $S$ for all $j$ (supposing not, the construction of $T$ forces a match in the $a$ position or the $b$ position). The proof declares $x\_i$ to be false if $x\_i$ is chosen, and if $\bar{x}\_i$ is instead chosen then $x\_i$ is true (so that $\bar{x}\_i$ is false).

The proof goes on to explain that the third and fourth set in the union definition of $T$ must therefore comprise the remaining $mn$ elements to be selected for $S.$ Since all $m$ elements of the third set comprise exactly one literal $\lambda\_j$ in each clause $C\_j,$ and since the first $mn$ choices from the first two sets in the union for $T$ were all assumed false, then, since $\lambda\_j$ cannot match the $x\_i^j$ or $\bar{x}\_i^j$ as selected for the $a,b$ triplets in the position $i$ to which $\lambda\_j$ corresponds, then $\lambda\_j$ must be a true literal in the clause $j.$ Since such a selection exists for all $m$ clauses, the third set of $T$ (which, again, must be included in $S$) represents a truth setting that satisfies $F.$ The fourth set is labeled as a "garbage set" that picks up the rest of the literals.

The other direction, assuming that a given $F$ is satisfiable, is easy: make the same construction as above and simply select the $\lambda\_j$ to correspond to the truth setting that satisfies $F,$ set the $a, b$ triplets opposite these settings in these positions, and you've constructed a $T$ that has a perfect matching subset $S$ following the above rubric. This direction is direct and is not the point of concern, nor is there any concern with showing the problem is in NP.

What my advisor finds troublesome is the first direction. His challenge is that if we happen to construct a $T$ that does not have a perfect matching subset $S$ as given above, he cannot see how we can conclude that $F$ is not satisfiable; the third subset in the union for $T$ may just happen to be a truth setting that doesn't work for $F,$ and we do not know from this fact whether or not some other formulation of $T$ exists *with* a "truth setting" subset that actually satisfies $F.$ I am not aware how to answer his challenge to this proof; I have attempted to explain that the rubric for proving NP-Completeness allows us to *assume* that the $T$ we constructed *has* a perfect matching subset $S,$ but he continues to answer that if we did not have such a subset for the $T$ we constructed, we would not know for sure whether $F$ is unsatisfiable or not. In short, he believes that a "no" answer for 3-Dimensional-Matching *must* imply a "no" answer for the transferred satisfiability problem. Is that something that must be demonstrated in proofs of NP-Completeness?

The other question I had is one of my own. For our selection of the first $mn$ elements for the matching subset $S,$ the proof explains that, for each $i,$ we *freely* select exactly one of $x\_i$ or $\bar{x}\_i$ for every $j,$ but not both, and furthermore we can *freely* declare these $n$ selections all false. I do not see how we are "free" to make such selections - for example, if $F$ happens to be, in every clause, *exactly what we selected* for these first $mn$ "false" elements, then the $m$ elements from the third set of $T$ that are supposed to be the truth setting variables cannot possibly correspond to the literals in any of the $m$ clauses, but we can construct $S$ nonetheless. I suppose I am getting confused with what the author of this proof meant by "choosing" exactly one of $x\_i$ or $\bar{x}\_i$ for every $j,$ but I can't identify the point where my understanding breaks down.

Any help clarifying these questions would be deeply appreciated!

# Answer
To answer your following question:

> In short, he believes that a "no" answer for 3-Dimensional-Matching must imply a "no" answer for the transferred satisfiability problem. Is that something that must be demonstrated in proofs of NP-Completeness?

Yes, this must definitely hold for your construction. Note however, that it is already proven in the following paragraph (assuming the proof is correct, I did not verify that)

> The other direction, assuming that a given $F$ is satisfiable, is easy: make the same construction as above and simply select the $λ\_j$ to correspond to the truth setting that satisfies $F$, set the $a,b$ triplets opposite these settings in these positions, and you've constructed a $T$ that has a perfect matching subset $S$ following the above rubric. This direction is direct and is not the point of concern, nor is there any concern with showing the problem is in NP.

Here it is shown that if $F$ is satisfiable, $T$ has a correct matching subset. By contraposition, if $T$ does NOT have such a subset, $F$ cannot be satisfiable.

EDIT: Let me try to answer your second question as well:

> I suppose I am getting confused with what the author of this proof meant by "choosing" exactly one of $x\_i$ or $\bar{x}\_i$ for every $j$, but I can't identify the point where my understanding breaks down.

This direction of the proof shows how, given a matching in $T$, you can construct a satisfying solution in $F$ (thus showing it is satisfiable).

You do indeed not randomly (or, indeed, freely) choose such an $x\_i$. Instead, (I do not know if the book shows this clearer then your summary) you demonstrate that a matching S **must** have a certain format (i.e. it contains exactly one of the sets $\\{x\_i^j,a\_i^j,b\_i^j\\}$ or $\\{\bar{x}\_i^j,a\_i^j,b\_i^j\\}$). Having this knowledge, we now construct the solution for $F$ by saying we **choose** $x\_i := false$ if $\\{x\_i^j,a\_i^j,b\_i^j\\} \in S$ and $x\_i:=true$ otherwise (note that this is indeed a choice we make, it just happens to be a clever one). Then, you can show this is a satisfying solution: If it were not, there would be a clause $C\_j$ for which all literals are set to $false$. But then there is no way to cover $v\_j$ by our matching $S$ ($v\_j$ needs to be covered by set $\\{\lambda\_j,v\_j,w\_j\\}$, but all $\lambda\_j$ are already matched in $S$), which is a contradiction.

EDIT: It appears the construction of $T$ is not clear, let me try give an example of (what I believe) the construction should look like. Suppose $F = (x\_1 \vee x\_2 \vee x\_3) \wedge (x\_1 \vee \bar{x}\_2 \vee \bar{x}\_3)$ , so $n = 3$ and $m=2$. Construct variables

* $U = \\{x\_1^1, \bar{x}\_1^1, x\_1^2, \bar{x}\_1^2, x\_2^1, \bar{x}\_2^1, x\_2^2, \bar{x}\_2^2,x\_3^1, \bar{x}\_3^1, x\_3^2, \bar{x}\_3^2\\}$
* $V = \\{a\_1^1, a\_1^2, a\_2^1,a\_2^2, a\_3^1,a\_3^2\\} \cup \\{v\_1, v\_2\\} \cup \\{c\_1^1, c\_2^1,c\_1^2, c\_2^2\\}$
* $W = \\{b\_1^1, b\_1^2, b\_2^1,b\_2^2, b\_3^1,b\_3^2\\} \cup \\{w\_1, w\_2\\} \cup \\{d\_1^1, d\_2^1,d\_1^2, d\_2^2\\}$

Then add all following triples to $T$:

* $\\{x\_i^j, a\_i^j, b\_i^j\\}$ for all $i \in \[3\]$ and $j \in 2$ (this adds six triplets)
* $\\{\bar{x}\_i^j, a\_i^j, b\_i^j\\}$ for all $i \in \[3\]$ and $j \in 2$ (this adds six more triplets)
* For **each** literal $\lambda \in C\_j$ add $\\{\lambda^j, v\_j,w\_j\\}$, in our example: $\\{x\_1^1,v\_1,w\_1\\},\\{x\_2^1,v\_1,w\_1\\},\\{x\_3^1,v\_1,w\_1\\},\\{x\_1^2,v\_2,w\_2\\},\\{\bar{x}\_2^2,v\_1,w\_1\\},\\{\bar{x}\_3^2,v\_1,w\_1\\}$ Note that I assume nothing about the satisfiability of $F$ (or of the satisfying assignment that $F$ does/does not have).
* For **each** possible $x \in U$ and all $i \in \[n-1\],j\in \[m\]$ the triples $\\{x,c\_i^j,d\_i^j\\}$.
> 3 votes

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


# Question
Title: Finding the nodes that have degree at least 3 in an undirected graph
I want to come up with a good algorithm that takes as input an undirected graph $G$ and checks which vertices to include in an output graph $G'$, such that each vertex in $G'$ has degree at least 3.

I've thought about traversing the graph once to eliminate any vertex with degree less than 3 since none of these can be included in the output. Then, I could have a set $S$ that initially contains some arbitrary vertex that hasn't been eliminated; the rest of the vertices are kept in the set $T$.

If I keep with this idea, I'm not sure how to start moving in vertices from $T$ to $S$ and at which point to delete them. I also wonder if there's a way to use BFS to scan and see if each vertex has degree at least three in the output tree of the BFS procedure. Any pointers/ideas would be appreciated; thanks!

# Answer
> 2 votes
This problem is known as a maximum $k$- core (in your case $k = 3$) and can be solved in polytime. The idea is the one you mentioned : simply delete vertex with degree less than 3 until you don't have such vertices.

More accurate description of the algorithm:

Store your graph as adjacency list. Whenever you find a vertex with degree less than $k$ mark it as deleted and then remove it from neighbors list of its neighbors. In the end you can shift indices if you really need them to be in consecutive order.

# Answer
> 1 votes
As mentioned in Eugene's answer, you are looking for a 3-core of the graph $G=(V,E)$. If the graph is sufficiently small, you can find any $k$-core in linear time using a bounded-height priority queue. This kind of priority queue is typically implemented as an array of buckets, where any given bucket at index $i$ holds all of the items that have priority $i$. Thus, if you consider the items to be the vertices of $G$ and their priorities to be their respective degrees, then this data structure allows you to keep track of the vertices of $G$ sorted by degree.

The algorithm to find a $k$-core is as follows:

1. Initialize the bounded-height priority queue. This data structure supports insertions in $O(1)$ time. Therefore, if you haven't precalculated the degrees of the vertices of $G$, this step takes $O(|V|+|E|)$ time.
2. Find the vertex $v$ of minimum priority (that is, of minimum degree). This operation takes $O(1)$ time.
3. Remove $v$ and subtract $1$ from the degrees of all the neighbours of $v$. When the degree of a vertex is modified, the vertex must be reallocated within the queue; nonetheless, this operation takes $O(1)$ time because the bounded-height priority queue is an array-based data structure that is indexed by degree.
4. Go to step 2 until there is no vertex $v$ such that $d(v)\lt k$, where $d(v)$ is the degree of $v$.

Observe that the above greedy algorithm takes linear time overall because processing each vertex takes time proportional to its degree and the sum of all vertex degrees is linear in $|E|$.

---
Tags: algorithms, graphs, algorithm-analysis, search-algorithms
---


# Question
Title: Can a finite state transducer emit $\epsilon$?
Can a deterministic finite state transducer output ϵ (epsilon) ?

> A Deterministic Finite-state Transducer (DFT) is a device much like a DFA, except that its purpose is not to accept strings or languages but to transform input strings into output strings. Informally, it starts in a designated initial state & moves from state to state , depending on the input , just as DFA does. On each step, however it emits a string of the symbols of the alphabet (zero or one or more than one symbols)depending on the current state & the input symbol. The state diagram of a DFT looks like that of a DFA, except that the label on an arrow looks like a/w, which means “if the input symbol is a, follow this arrow and emit output w”.

# Answer
The quote says that the machine emits "zero or one or more than one symbols". Emitting zero symbols is emitting $\varepsilon$.
> 1 votes

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


# Question
Title: Theoretical worst case running time of finding a path through a maze?
Given a randomly generated maze of dimensions n x n, with the entrance point always being the top left corner (0,0) and the exit point always being the bottom right corner (n,n) what is the theoretical worst-case running time of finding a path through this maze?

* The maze has a density of d (for example, if d = 0.5, then half of the maze is filled with obstacle/wall cells)
* The path finding algorithm uses a stack to keep track of the path and for back tracking when necessary
* The algorithm uses a search order of down, right, up, left

# Answer
> -1 votes
If you are only interested by the worst-case scenario, you need to consider an algorithm always picking the worst possible move at any point in time. The answer is intrinsic to both the method used to find the path through the maze and the maze topology. In fact, two randomly generated mazes might be very different from each other, one could have a path from start to end with no dead end while the other might have a lot of path intersection and dead ends. In the latter, a naive algorithm might perform worse if hitting a dead end mean searching backward to the last intersection before to attempt another path. Again, the answer is intrinsic to the algorithm used to traverse the maze and the maze topology.

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


# Question
Title: Gate/transistor number and program length measures of computational complexity?
Are there scaling concepts regarding the number of components needed and minimum program length needed to solve a problem of some complexity?

For example, problems are characterized by O(.) measures of time and space complexity. Space complexity tells me the amount of memory needed but not the number of computational components needed. We assume a Turing machine and count the number of steps performed. But in practice, the number of instructions available, and the level of parallelism have some non-linear relationship with the amount of time needed to solve a problem. Amdahl's law deals with speeding up one part of the problem. On a more general level, there could be at least an empirical or conjectural observation of how physical hardware like NAND gates or transistors scale with problem size or speed.

Thinking in terms of program size, there is Kolmogorov complexity defined as the shortest program that will generate a sequence or other data object. But what about the min. program that will solve a problem? Has anyone defined or used Kolmogorov-like complexity to characterize a problem rather than information content?

# Answer
Two well-known books in this research area are:

> Jeffrey D. Ullman, *Computational Aspects of VLSI*, Computer Science Press, 1984

and

> F. Tom Leighton, *Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes*, Morgan Kaufmann, 1991.

The connection between space and time complexity is due to the finite speed of communicating across distance. Thus, a lot of the interesting results are about how various communication networks can (or cannot) be embedded in 3-dimensional space.
> 3 votes

---
Tags: complexity-theory, parallel-computing, kolmogorov-complexity, empirical-research
---


# Question
Title: Product construction for given two finite automata
I need to construct a finite automata which accept a language $L = L\_1 \cap L\_2$, where $L\_1$ and $L\_2$ are given below.

$L\_1 = \\{ w \mid w $ is divisible by 2 }

$L\_1 = \\{ w \mid w $ is divisible by 3 }

I know how to design a finite automata for a single number but how do I combine the automatons which check divisibility by 2 and 3? I am able to combine the initial states of the two automatons by using ϵ transitions from a new state but how can I combine the final states of the two automatons? Input is in the set of decimal numbers
Σ = {0,1,2,3,4,5,6,7,8,9}

# Answer
> 3 votes
Here is a product construction for finite automata. I am considering you have two finite automata $M\_1$ and $M\_2$.

Let $M\_1$ = $(Q\_1,\Sigma ,\delta\_1,q\_{01},F\_1)$ and $M\_2$ = $(Q\_2,\Sigma ,\delta\_2,q\_{02},F\_2)$ be two finite automata with the same input alphabet. Let us define $M$ such that

> $$L(M) = L(M\_1) \cap L(M\_2) $$

Finite automata for $L(M)$ is defined as $M$ = $(Q,\Sigma ,\delta,q\_0,F)$ , where $Q$ is a finite set of states, $\Sigma$ is a input alphabet, $q\_0$ is a start state, $\delta$ is a transition function and $F$ is final state of a finite automata $M$.

> * $Q$ = $Q\_1$ X $Q\_2$ (Cartesian product),
> * $\delta((q\_1,q\_2),a) = (\delta\_1(q\_1,a),\delta\_2(q\_2,a))$,
> * $q\_0 = (q\_{01},q\_{02})$,
> * $(q\_{1},q\_{2}) \in F $ iff $q\_1 \in F\_1 $ and $q\_2 \in F\_2$.

Each state in $Q$ is a pair consisting of a state from $Q\_1$ and a state from $Q\_2$.

**Reference** : the Product Construction for Automata by Laura Kovács.

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


# Question
Title: Algorithm to find liars and truthtellers
This is the exercise 2.18 from Introduction to Bioalgoritms of Neil Jones. It says:

> We have a mix of 100 participants: some are honest while others are not. The honest ones always tell the truth, but the deceitful ones sometimes tell the truth and sometimes lie. You can ask any participant the following question about any other participant: “Participant Y, is Participant X honest?” Participant Y will answer with either “yes”or “no.” Design an algorithm that, with no more than 198 questions, would allow you to ﬁgure out which of the 100 participants are honest. It is known that there are more honest than dishonest participants.

# Answer
The problem cannot be solved at all. It is possible that they are all honest, and therefore always say that everyone else is honest. Or they could all be liars, and in order not to be found out, the also all say that everyone else is honest. If everyone says that everyone is honest, you know they are all honest or all liars, but you don't know which one.

There was an attempt at some help which went badly wrong: "There are more honest than dishonest professors". Since we don't know whether there are any professors among the participants, this hint is useless. Had we been told "there are more honest than dishonest professors among the participants", that would have meant there is at least one honest participant, making the scenario of all dishonest participants impossible. The poster might have meant "there are more honest than dishonest participants", which would have been a stronger hint.
> -1 votes

# Answer
Just Pick a single man and ask the rest of the 99 person a single question I.e., raise your hands it this person is a truthteller. If he he is a truthteller then the majority answer will be in his favour as the majority are truth tellers. But if by any chance the majority says he is a liar then remove him and start with another person. Try at last you find ha truthful person. As majority is of truth tellers the maximum question you need to ask to find a single true person is 48( do the math). once you have found the truth ask him about each person seperatly so the maximum question you will need to ask from that person will be 99. 99+48=147 you found who is truthful and who is a liar in just 147 questions
> -1 votes

---
Tags: algorithms
---


title: n! mod p Fast Factorial

text:
# Question
Title: n! mod p Fast Factorial
I need to find **N! (mod 232-5)** such that **0 ≤ N ≤ 264** for **i** cases, **0 ≤ i ≤ 1000** in 1 sec.

Credits: https://dmoj.ca/problem/factorial2

I am aware that I only have to handle **0 ≤ N ≤ 2 ≤ 232-6** because once **N ≥ 232-5**, **N!≡0 (mod 232-5)** . A naive solution would take **O((232-6)\*1000)**. I have also tried using Wilson’s Theorem and a naive solution, which would run in approximately **O(4000000000\*1000)** time (Calculated from the highest point when **O(N)** intersects with **O(232-5-N)log(N))**).

I cannot find a solution to this problem with a fast enough run time. Any help would be appreciated.

# Answer
First use Yuval's advice: With p = 2^32 - 5, remove all N ≥ p (the result is 0), then sort the rest, so now you have up to 1,000 numbers in sorted order from 0 to p-1. This is trivial to do by multiplying up to almost 2^32 numbers modulo p and recording results at the right moment; that's not *much* above a second worth of work but more than a second.

Let's say you have r processors, and you want to use them simultaneously. The largest number is t \< p. You make each processor responsible for multiplying s = ceil (t / r) numbers. For example if r = 8 and t = 2^32 - 6, then s = 2^29. Processor 0 multiplies numbers from 1 to s, processor 1 multiplies numbers from s+1 to 2s and so on. Let's say one of your N's is 3s + 15900: Processor 3 multiplies 3s+1 to 4s. At some point you record the product of numbers 3s+1 to 3s+15,900. And when all the processors are done, you multiply with the final results of processors 0, 1 and 2.

You may have vector units being able to do for example 4 operations in parallel. In that case, you would multiply r by 4, and have 8 processors calculating 4 results simultaneously.

Say you have calculated x (x+1) modulo p, the product of two numbers. How can you get (x+2)(x+3) modulo p, the next product? (x+2)(x+3)-x(x+1) = 4x + 6, so the product modulo p changes by (4x + 6) modulo p. Let d(x) = (4x + 6) modulo p. As you increase x by 2, d(x) changes by 8 (modulo p), so the products x(x+1) modulo p, (x+2)(x+3) modulo p, (x+4)(x+5) modulo p etc. can be calculated very quickly. I think that should be enough to get you below one second.

Some additions: One, **if p** = $2^{32}-5$ **is not prime**, **that makes the problem just faster to solve**. If all prime factors are ≤ $p^{1/2}$ then the problem is trivial because N! = 0 (modulo p) if N ≥ $2^{17}$ (must be careful in case p is the square of a prime). Otherwise let p = a·q, where a ≥ 2 and q is a prime q ≥ $p^{1/2}$, then we can calculate N! modulo p easily from N! modulo a and N! modulo q. Since $a ≤ 2^{16}$ and N! modulo a = 0 if N ≥ a, calculating N! modulo a is trivial (only 65535 products needed). b would be at most half as large as p, making the problem at least twice as fast to solve. After applying this, we can assume p is prime.

Two, **Wilson's Theorem lets you cut the time in half**. We now assume p is prime (having cut down the time earlier if the original p wasn't). Wilson's Theorem says (p-1)! = -1 (modulo p). Now say we want to calculate (p-k)! modulo p. We have obviously (p-k)! · ((p-k+1)·(p-k+2)· ... · (p-1)) = (p-1)!. This product is equal to (p-k)! · (-(k-1))·(-(k-2))· ... · (-1)) = (p-k)! · (k-1)! · (-1)^(k-1). The result modulo p is -1, so (p-k)!·(k-1)! = (-1)^k modulo p. So if p/2 ≤ N \< p, then we let k = p - N, calculate (k-1)! modulo p, and solve N! · (k-1)! = (-1)^k modulo p. The problem is now mostly reduced to the problem of calculating N! modulo p for about 1,000 values 0 ≤ N ≤ p/2 ≤ $2^{31}$.

Three, **Yuval's idea** using a table with pre-calculated values N! modulo p will work if the task is to solve the problem for fixed p and different sets of 1,000 values N. If there are 1,000 values N you need **1,000k precalculated values to save a factor k**. It doesn't work if p is variable. And if it is possible to use multiple processors or vector units to do k calculations in parallel, then a factor k in time can be saved. Without these savings, it's 2 billion products modulo p in 1 second.

One idea is factoring N! into a product of powers primes. There are less than 100 million primes \< $2^{31}$. However, since we have 1,000 values $N \< 2^{31}$, I think many primes will have to be multiplied multiple times. Doing this in one second is tough.
> 1 votes

---
Tags: mathematical-programming
---


# Question
Title: Show that every definite language is accepted by a finite automaton
A language $L$ is definite if there is some $k\> 0$ such that for any string $w$, whether $w \in L$ depends on the last $k$ symbols of $w$. How can I prove that every definite language is accepted by a finite automaton?

# Answer
This is true as a consequence of the Myhill Nerode theorem. For any fixed $k\gt 0$, the number of possible combinations of the last $k$ symbols of any string $w\in L$ is $|\Sigma|^k$, where $\Sigma$ is the alphabet.

Any two strings that have the last $k$ symbols identical will always be both accepted or both rejected by $L$, for any string appended to them, i.e., no string in $\Sigma^\*$ will distinguish such strings. Thus, such strings lie in the same equivalence class of $L$.

Strings with differences in their last $k$ symbols will either lie in different equivalence classes or will cause the classes demarcated in the previous step to collapse together into a single class.

Thus, the equivalence classes of $L$ are determined by the last $k$ symbols of $L$.

As the possible combinations of the last $k$ symbols is finite, the number of equivalence classes is finite. Thus, by the Myhill Nerode theorem, the language $L$ is regular. Hence, there exists a DFA that accepts $L$.
> 2 votes

# Answer
**Hint 1:**

> $L=L\_1\sqcup L\_2$ where $L\_1=\\{u \in L : |u|\<k\\}$ and $L\_2=\\{u \in L : |u|\ge k\\}$.

-

> What properties would you like to have on $L\_1$ and $L\_2$ to prove that $L$ is regular?

**Hint 2:**

> What property does $L\_1$ have that makes it regular?

-

> How many elements are there in $L\_1$?

**Hint 3:**

> If $u\in L\_2$, then $u$ can be written $u=vw$ with $|w| = k$.

-

> And then $\Sigma^\*w\subseteq L\_2$.

-

> Take $L\_3=L\_2\cap \Sigma^k$.

-

> Express $L\_2$ in terms of $L\_3$.

-

> $L\_2=\Sigma^\*L\_3$

**Hint 4:**

> What property does $L\_3$ have that makes it regular?

-

> How many elements are there in $L\_3$?
> 1 votes

---
Tags: finite-automata
---