# Question
Title: Given a pair of coordinates $(x,y)$ in 2D, find the points inside the circle $C((x,y),R)$
Suppose that there are a set of $n$ points $P = \\{(x\_1,y\_1), \dots, (x\_n,y\_n)\\}$ in 2D.

Given two coordinates $(a,b)$ and a number $r \in \mathbb{R}$, is there an algorithm with $O(|Q| + \log n)$ running time that can find the point set $Q \subseteq P$ containing those points of $P$ that are inside the circle with center $(a,b)$ and radius $r$?

(That is, I want to find all points in $P$ with coordinates $(i,j)$ such that $(i-a)^2 + (j-b)^2 \leq r^2$.)

\[I originally asked about a solution with running time $O(\log n)$, but as Pål GD correctly points out, the answer to that question was "not possible".\]

# Answer
Obviously not. You must inspect all the points and, on a classical, deterministic computer, you can't possibly look at $n$ points in only $O(\log n)$ time.

Note that this answer applies equally to the original question (is it possible in $\log n$ time?) and the revised one (is it possible in $|Q|+\log n$ time?). The answer could well be $Q=\emptyset$, but you can't figure that out in time $o(n)$.
> 3 votes

# Answer
You are asking for a sublinear time algorithm which for some inputs must output every element. So the answer is, as David Richerby argues, no.

A better question is probably an output-sensitive version of the problem: Can you solve it in $O(\log n + |S|)$ where $S$ is the solution. That is, logarithmic in the input, and linear in the output.
> 3 votes

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


# Question
Title: Why are NP-complete problems so different in terms of their approximation?
I'd like to begin the question by saying I'm a programmer, and I don't have a lot of background in complexity theory.

One thing that I've noticed is that while many problems are NP-complete, when extended to optimization problems, some are far more difficult to approximate than others.

A good example is TSP. Although all kinds of TSP are NP-complete, the corresponding optimization problems get easier and easier to approximate with successive simplifications. The general case is NPO-complete, the metric case is APX-complete, and the Euclidean case actually has a PTAS.

This seems counter-intuitive to me, and I'm wondering whether there is a reason for this.

# Answer
> 15 votes
One reason that we see different approximation complexities for NP-complete problems is that the necessary conditions for NP-complete constitute a very coarse grained measure of a problem's complexity. You may be familiar with the basic definition of a problem $\Pi$ being NP-complete:

1. $\Pi$ is in NP, and
2. For every other problem $\Xi$ in NP, we can turn an instance $x$ of $\Xi$ into an instance $y$ of $\Pi$ in polynomial time such that $y$ is a yes-instance of $\Pi$ if and only if $x$ is a yes-instance of $\Xi$.

Consider condition 2: all that is required is that we can take $x$ and turn it into some $y$ that preserves the "single-bit" yes/no answer. There's no conditions about, for example, the relative size of the witnesses to the yes or no (that is, the size of the solution in the optimization context). So the only measure that's used is the total size of the input which only gives a very weak condition on the size of the solution. So it's pretty "easy" to turn a $\Xi$ into a $\Pi$.

We can see the difference in various NP-complete problems by looking at the complexity of the some simple algorithms. $k$-Coloring has a brute force $O(k^{n})$ (where $n$ is the input size). For $k$-Dominating Set, a brute force approach take $O(n^{k})$. These are, in essence the best exact algorithms we have. $k$-Vertex Cover however has a very simple $O(2^{k}n^{c})$ algorithm (pick an edge, branch on which endpoint to include, mark all covered, keep going until you have no edges unmarked or you hit your budget of $k$ and bactrack). Under polynomial-time many-one reductions (Karp reductions, i.e. what we're doing in condition 2 above), these problems are equivalent.

When we start to approach complexity with even slightly more delicate tools (approximation complexity, parameterized complexity, any others I can't think of), the reductions we use become more strict, or rather, more sensitive to the structure of the solution, and the differences start to appear; $k$-Vertex Cover (as Yuval mentioned) has a simple 2-approximation (but doesn't have an FPTAS unless some complexity classes collapse), $k$-Dominating Set has a $(1+\log n)$-approximation algorithm (but no $(c\log n)$-approximation for some $c\>0$), and approximation doesn't really make sense at all for the straight forward version of $k$-Coloring.

# Answer
> 14 votes
One way to consider the difference between decision version and optimization version is by considering different optimization versions of the same decision version. Take for example the MAX-CLIQUE problem, which is very hard to approximate in terms of the usual parameter – the size of the clique. If we change the optimization parameter to the *logarithm* of the size of the clique, we obtain a problem with an $O(\log n)$ approximation algorithm. If we change the optimization parameter to $1/2 + k/n$, where $k$ is the size of the clique, then we can get an $O(1)$ approximation algorithm.

These examples are not completely made up. The problems of MAX-INDEPENDENT-SET (equivalent to MAX-CLIQUE) and MIN-VERTEX-COVER are closely related – the complement of an independent set is a vertex cover. But while the former is hard to approximate, the latter has a simple 2-approximation.

Reductions showing the NP-hardness of a given problem can sometimes be used to also show hardness of approximation, but this is not always the case – it depends on the reduction. For example, the reduction from MAX-INDEPENDENT-SET to MIN-VERTEX-COVER does not imply hardness of approximation of the latter problem, which is much easier to approximate than the former.

Summarizing, NP-hardness is just one aspect of a problem. Hardness of approximation is a different aspect, and it strongly depends on the notion of approximation.

# Answer
> 6 votes
As an intuitive approach, consider that instantiations of NP-complete problems are not always as hard as the general case. Binary satisifiability (SAT) is NP-complete, but it's trivial to find the solution to A v B v C v D v ... The complexity algorithms just bound the worst-case, not the average case, or even the 90% case.

The easiest way to reduce a NP-complete problem to something simpler is to simply exclude the hard parts. It's cheating, yes. But often the remaining parts are still useful for solving real world problems. In some cases, the line between "easy" and "hard is easy to draw. As you pointed out for TSP, there is a strong reduction in difficulty as you constrain the problem around "normal" directions one might think of. For other problems, it is harder to find real-life useful ways to segregate the easy and hard parts.

To totally leave the realm of CS and mathematics, consider an old car. Your friend wants to drive it. If you have to tell him, "hey, the car works perfect. Just don't take it above 95mph. There's a nasty wobble that'll knock you off the road," it's probably not a big deal. Your friend probably only wanted to take it around town anyway. However, if you have to tell him, "you have to feather the clutch just right to go from 1st to 2nd, or the engine will stall," it might be harder for your friend to use the car around town without some minor training.

Likewise, if an NP-complete problem happens to only get difficult in exotic cases, it reduces complexity rather quickly when you look at subdomains. However, if it gets difficult in commonly occuring cases, there aren't so many useful subdomains which avoid the hard part.

---
Tags: complexity-theory, optimization, np, approximation
---


title: $k$-gifts problem

text:
# Question
Title: $k$-gifts problem
Consider the following problem:

> Suppose you have $k$ nephews and $d$ dollars in your pocket all of which you need to spend. Given a set of $n$ toys with different prices, find whether there exists $k$ gifts with total cost exactly $d$.

If $k=2$, is it possible to have an algorithm that runs in $o(n^2)$? If not, how to prove this?

Consider the case $k = 2$ and the prices are all nonnegative integers. In this case, we should have an $O(nd)$ algorithm by iterating through the toys and remembering the prices we have already seen.

Is it possible to remember which numbers seen from a sequence of length $n$ of integers between $1$ and $d$ in less than $\Omega(nd)$ time? It seems like one could use binary representation of numbers to remember in $n\log d$ time.

# Answer
**Get the naive approach out of the way:** We have a set of $n$ candidate toys, out of which we need to select $k$ such that the total cost is equal to $d$. Lets consider the *most naive* approach to check if $k$ such toys: exhaustively consider all $\binom{n}{k}$ possible combinations of toys and for each such $k$-set check whether the total price is equal to $d$. But, $$ \binom{n}{k} \le n^{k} $$ while for a given $k$-set, the total price is checked in $O(k)$. Hence, the total running time for this naive procedure is $$ O(k n^{k}). $$ For $k=2$, this is clearly an $O(n^{2})$ algorithm, but *not* $o(n^{2})$.

**Second approach.** A second, relatively straightforward approach is to classify items in $d$ bins according to their price (like a histogram, but well.. not exactly). Why is this useful? If our final pair contains an item of cost $i$ (*i.e.*, from bin $i$) then the second item must be from bin $d-i$.

Consider $d$ bins labeled $1, \dots, d$ with the $i$th bin corresponding to price $i$. This can be implemented as array with $d$ entries; access of entry $i$ costs $O(1)$. We scan the toys in $O(n)$ and place each toy in the suitable bin according to its price. In fact, we do not need to store all items. All we want is to store one item per bin (if one exists). As a special case, if $d$ is even, then in bin $d/2$ we store up to two items because two items of price $d/2$ can give total price $d$, but this does not affect the total complexity.

We scan the toys, and if a toy has price $i$ we access bin $i$ in $O(1)$, check if it is empty. If not, we can discard the item (because we already have an item of price $i$). If the bin is empty, we put that item in bin $i$. (As already mentioned, special care is taken for bin $d/2$ when $d$ is even.) This procedure is completed in $O(n)$.

Now, if we choose an item/toy from bin $i$, $1\le i \< d$, then the second toy can only be in bin $d-i$. We can scan the bins as follows: check if bins $d-1$ and $1$ are empty. If both are *not* empty, then return the items stored in the two bins. If either or both are empty, continue by checking bins $2$ and $d-2$. This procedure can be completed in $O(d)$, and hence the entire procedure is completed in time $O(n+d)$. If $d = o(n^{2})$, then this algorithm satisfies our requirements. If not, we would have see how to improve it.

**Third approach**: A third approach is to sort the $n$ items according to their price from lowest to highest price. This takes $O(n \log n)$. Once we have the sorted array of items, we can start scanning from the first and last position (keeping two pointers, call them *left* and *right*). If the total price is greater than $d$, then we have to reduce it, so we move the *right* pointer one position to the left. If the price is less than $d$, we move the *left* pointer one position to the right. See where this is going? This procedure is dominated by the original sorting and is done in $O(n\log n) = o(n^{2})$. (*edit* I guess if $d$ is a free parameters of the problem, then possibly we need an additional $O(\log d)$ factor when we do the sorting... and if $d$ is too large, then this can still lead to problems.)
> 2 votes

# Answer
Here's a hint for $k=2$. Let $P = \\{p\_i : i\in \[n\]\\}$ be the set of prices. In any solution $\\{p\_i,p\_j\\}$ with $p\_i \le p\_j$, you have $p\_i \le d/2$ and $p\_j\ge d/2$. Split $P$ into $A = \\{ a\in P : a\le d/2\\}$ and $B = \\{b \in P : b \> d/2\\}$. If $A$ and $B$ are sorted, you can find if there is an $a\in A$ and $b\in B$ with $a + b = d$ in $O(n)$ time.
> 2 votes

---
Tags: algorithms, assignment-problem
---


# Question
Title: Algorithm to decide the Kleene Star of a Language A
> Assume $f$ decides a language $A$ in $O(g(n))$ time, where $n$ is the length of the input string. How to write a recursive algorithm to decide $A^\*$ (recursive)?
>
> Moreover, can an $O(n^2g(n))$ time algorithm be written to decide $A^\*$ (dynamic programming)?

Yes, the dynamic programming portion is a hw assignment. CLRS book recommends using recursion first, then evolving to memoization, then the bottom-up approach. I can't even see how to write a recursive algorithm to solve this.

# Answer
First, solve the problem recursively:

```
def D(w)
  if w = emptystring, return true.
  for i = 1 to n
      Let wp be the postfix of w of length i, let w2 be w with wp removed.
      if f(wp) then
          if D(w2) then
              return true
          endif
      endif
  endfor

  return false
end

```

Now, if we just run $D(w)$ on all prefixes of $w$, remembering the result, then the time complexity is $O(n^2 g(n))$.
> 1 votes

---
Tags: algorithms, formal-languages, dynamic-programming, recursion
---


# Question
Title: How to bridge theory and implementation for while loops?
I'm working on my own little programming language for educational purposes, and I've run into a little bit of a problem. There are a few different solutions for it, but all of them seem inelegant - and from what I understand, unnecessary. But reading through the books I have and google searches, I can't find the elegant solution.

So, the problem is that I'm building off basic lambda calculus as I understand it. I have defined true/false as abstraction terms. I can combine these with functions to do if/then/else sort of behavior. The problem comes with loops. I can define a basic while loop via recursion, but in practice, that causes a stack overflow. As I understand it, the usual solution would be to perform Tail Call Optimization, but I don't see how I can - conditionals are defined in-language. Because of that, the compiler doesn't *know* that the body of the while loop is in tail position.

The dragon book focuses on implementing the loop assuming there is labels and gotos. I could certainly do that. It looks as though other languages that don't build in looping constructs at least build in conditionals and then do TCO. And I could certainly do that too. But my understanding is that as long as I can apply abstractions and perform reductions, then loops (and everything else) should be able to be built from those basic blocks.

So what am I missing? Or is this one of those cases where "you can model anything once you have X and Y" isn't the same as "you can model anything once you have X and Y on a real computer" and built-ins are necessary for practical purposes?

# Answer
> 5 votes
So I managed to solve this issue today. The code for my while loop:

```
while (condition: ~>bool) (body: ~>void) => void {
    if condition {
        body;
        while condition body;
    };
}

```

When I go to build this into CIL (a stack based runtime, important for the psuedocode, not important for the answer) it looks like:

```
ldarg 0
<build closure from { body; while condition body; }>
call if

```

The important thing I was missing is that in the `while` code, the ***conditional*** was the thing in tail position. From the compiler's perspective, the block and the while function are two separate functions, with two separate "tails". Each of those are easily evaluated for tail position, making the optimization viable despite the lack of built-in conditionals.

# Answer
> 5 votes
I think you're missing the notion of continuation. Although your compiler may not rely on that notion, as a compiler designer with a functional language as source or intermediate (or target) language, it's important to understand that notion and keep this in mind.

The continuation of a piece of code describes what the code exits to. In imperative terms, it embodies not only the location to which the code jumps or falls through, but also the program state (stack and heap) at that point. In lambda calculus terms, the continuation of a subterm is the context in which it is evaluated.

When you translate imperative code into a functional language, one of the difficulties is coping with code that can exit in several different ways. For example, code can return or raise an exception. Or, the body of a loop can either go on to checking the condition again or exit the loop altogether (`break` construct). There are two main ways to cope with this:

* Multiplexing: make the code return a sum type for all the possible exits. In the case of a loop body, that would be `Continue | Break`.
* Continuation-passing style: translate code to a function that takes an extra parameter which is the function to execute next. This extra parameter is the function's continuation. Code which can exit in different ways receive one such parameter for each of the ways.

Continuation-passing style is how data structures get embedded into the pure lambda calculus. For example, when you represent true as $\lambda x,y. x$ and false as $\lambda x,y. y$, the arguments $x$ and $y$ are the two possible continuations, and the boolean is an “if” statement that selects either one or the other continuation.

In continuation-passing style,

```
while (condition) body

```

gets translated to

```
let rec f (continuation) =
  if (condition, body (f (continuation)), continuation)

```

In the translation of a program in a typical imperative language in continuation-passing style, the continuation is always the last thing that a piece of code executes. For example, the continuation of `body` above is executed after all the code of `body`, so tail call optimization results in freeing all the local variables of `body` just before executing the continuation.

Some languages offer first-class continuations with a construct like call-with-current-continuation. Call/cc is not in general amenable to tail call optimization — it can in fact be a rather expensive operation since it can lead to duplicating the whole program state.

---
Tags: programming-languages, loops, language-design
---


title: NP != P Proof Requirments

text:
# Question
Title: NP != P Proof Requirments
I have been examining the NP = P problem and I am wondering, why is proving or disproving NP = P hard? For example, why wouldn't a proof such as the following be adequate? Suppose a million doors were in front of me and I had to discover which door had a red ball behind it. In order to verify the solution, one would have to simply open the hypothesized door. But in order to solve, one must check at least one door to solve the problem. However, statistically speaking, that's like guessing an integer zero to an equation. Therefore, it must take more time to solve, then to check statically speaking, proving P != NP. Although one could argue that they could guess the door, the same goes for any solution to an equation. My question is what is wrong with a proof like the one above?

# Answer
> 9 votes
The problem is that it's an analogy, not a proof.

1. It can't be a proof because it claims to come to a conclusion about Turing machines without using any property of Turing machines.
2. $\mathrm{P} \overset{?}{=} \mathrm{NP}$ isn't a question of statistics or probabilities.
3. You're making the assumption that it's harder to compute a solution than to check one, from which you conclude that it's harder to compute a solution than check one: this is circular.
4. The problem you consider is clearly in $\mathrm{P}$: just check every door and see what's behind it. So you couldn't possibly use that problem to distinguish $\mathrm{P}$ from $\mathrm{NP}$. The best you could hope for is distinguishing constant time (check a solution) from linear time (generate one) in some kind of random-access model of computation.

There's lots of information about why the $\mathrm{P}/\mathrm{NP}$ problem is hard in our reference question.

---
Tags: np-complete
---


# Question
Title: Enumerate all combinations of operations that fit memory and time criteria
I have the following problem:

$x$ is the number of operations **I have to** perform.

$O=\\{o\_1,o\_2,\ldots o\_n\\}$ is the set of possible operations.

I know beforehand the cost in terms of time and memory of every operation $o\_i \in O$.

I have a limited amount of memory and computation time, $M$ and $T$ respectively.

What is the most efficient way to generate the list of *computable* combinations? *i.e.* I need to generate a set of *computables* $C=\\{c\_1,c\_2,\ldots c\_m\\}$ such as:

* $\forall c\_i \in C, c\_i$ is a combination (with possible repetition) of $O$ and $|c|=x$
* $\forall c\_i \in C$ the memory and time consumption should be less than $M$ and $T$ respectively.

I think this is an *operations research* problem, but I can be wrong. If so, what branch of *operations research*? If not, then what is the most suitable approach?

# Answer
You can use uniform-cost search in the space of possible combinations of operations. Each node will be an ordered list of operations performed. Terminate the search when the maximum memory or time allotment is reached.
> 2 votes

# Answer
There are exponentially many possible sequences of operations ($n^x$, in the worst case). Therefore, in general, there is no efficient algorithm to compute the list of all sequences of operations. The problem can be solved in a feasible amount of time only if $x$ is small. If $x$ is very small, just enumerate all sequences of length $x$. As a special case, if the first $j$ in the sequence have a total time usage greater than $T$, you can ignore all sequences starting with that prefix. As Raphael says, a branch & bound algorithm may be efficient, if many sequences break the resource criteria. For that purpose, you'd want to sort the list to start with expensive operations.
> 2 votes

---
Tags: algorithms, enumeration
---


title: Big O notation and functions

text:
# Question
Title: Big O notation and functions
$$ f\_1(n) = n^2 $$ $$ f\_2(n) = n^2 + 1000n $$

Are the following statements true or false? $$ f\_1(n) = O (f\_2(n)), $$ $$ f\_2(n) = O (f\_1(n)), $$ Based on what I know about big O notation, I think the first statement is true and the second false, however my answer sheet says they're both true. Is that correct?

# Answer
> 1 votes
You have to think carefully the definition of the $O$-notation:

$f(n) = O(g(n))$ if and only if there exists a constant $c\>0$ and $N \in \mathbb{N}$ such that $$ f(n) \le c\cdot g(n), \quad \forall n \ge N. $$ Note that you need **two** things: the constant $c$ and $N$. The definition does *not* require that the inequality $f(n) \le c\cdot g(n)$ holds for all $n$. It requires that it holds for *sufficiently large $n$*.

In your example, it is easy to see that $f\_{1}(n) = O(f\_{2}(n))$, because $f\_{1}(n) \le 1\cdot f\_{2}(n)$, and that *happens* to hold for all $n$.

What about the second relation? Can you find appropriate $c\>0$ and $N$? (The statement is indeed correct, but you should be able to justify it by finding a good pair of $c$ and $N$.)

**Additional remark:** when $f(n)$ is a polynomial of $n$, like for example $f(n)=n^{2}+1000n$, then the complexity is determined/dominated by the highest degree term. In this example, the highest degree term is $n^{2}$, and hence $f(n) = O(n^{2})$. But again, more general observation originates from the fact that we are able to find appropriate $c\>0$ and $N$ and apply the definition.

---
Tags: asymptotics
---


title: Graph cycles on 40 vertices

text:
# Question
Title: Graph cycles on 40 vertices
I'm trying to create an algorithm in polynomial time, that detects wether or not a graph is in a language.

The language specifies that a graph is only part of this language if it has a **cycle on 40 vertices.** (The cycle doesn't need to be induced.)

Now, I'm considering the fact that there could be a huge number of vertices within this graph. For example, we could have 100000 vertices, and there could be a cycle of 300, but this would not be in the language. If this graph had a cycle of 300 **AND** a cycle of 40, then it is.

I'm thinking that depth-first search would be the proper way to approach this question. Then, using this, we'd possibly have check every vertex within the graph?

This is just a guess at the moment though, and help/thoughts would be greatly appreciated.

# Answer
> 3 votes
When you say "cycle", do you mean a simple cycle of length 40 (so no vertex is allowed to be repeated), or would you allow an arbitrary walk of length 40 that ends where it starts (i.e., vertices are allowed to be repeated in the cycle)? The answer to your question depends on what you mean by cycle, so I'll answer both cases.

## Simple cycles

The problem of testing whether a graph contains a simple cycle of length $k$ is hard.

No efficient algorithm is known; all known algorithms have running time that is exponential in $k$; and if $k$ is part of the input, the problem is NP-hard. See here and here. In your case, $k=40$. The best algorithms that I know of have either a $O(k!)$ factor or a $O(n^{k/2})$ factor in the running time, so they will be totally infeasible: $O(n^{20})$ is not feasible for any non-trivial value of $n$, and $k! \approx 2^{159} \approx 10^{48}$, which is also infeasibly large. (See Louis's answer for pointers to an algorithm of the former type.)

## If you allow repeated vertices

If you allow the cycle to contain repeated vertices, then the problem becomes much easier, and there is a polynomial-time solution.

Hint: Consider the adjacency matrix of the graph, $M$. Look at $M^2$. Can you find any relationship between the $i,j$ entry of $M^2$ and paths of some length? Can you generalize?

(Since this looks like a natural exercise problem, I am just giving you a hint, and letting you take it from here.)

# Answer
> 2 votes
It's worth noting that, as D.W. hints at, the running time of the best algorithms for even cycles has a form like $O(k!V^2)$ which is a lot better than $O(V^k)$ for small $k$. A relevant references is Finding even cycles even faster by Yuster and Zwick.

# Answer
> 1 votes
Since 40 is a constant, there is a very simple polynomial time algorithm that just goes over all possible cycles of length 40, and for each of them, tests whether it is in the graph. There are $O(n^{40})$ cycles, and testing whether each of them is in the graph takes $O(1)$ (or slightly more, depending on your machine model), for a total running time $O(n^{40})$. Although this algorithm is quite slow, it still counts as polynomial time. This shows one discrepancy between the concept of polynomial time and our intuitive notion of efficient computation, a notion that the concept was originally trying to model.

---
Tags: algorithms, graphs, polynomial-time, search-problem
---


title: Array search NP completeness

text:
# Question
Title: Array search NP completeness
Given an unsorted array of size n, it's obvious that finding whether an element exists in the array takes O(n) time.

If we let h = log n then it takes O(2^h) time.

Notice that if the array is sorted, a binary search actually takes O(h) time (which is polynomial) but the binary search cannot apply to an unsorted array.

Is it possible to prove that the problem to find an element in an array (yes or no) is NP complete in terms of h. What problem should I reduce from and how to reduce?

A more formal definition of the problem is given below.

We have an oracle, which is a binary tree of height h with each node having random values. I.E. a tree that DOES NOT have the property that all values in the left subtree of a node must be smaller than the value in the node or all values in the right subtree of a node must be greater than the value in the node. However all nodes in the oracle tree are guaranteed to have value between 0 and 2^h-1.

> The input is a number to be searched. The input is guaranteed to have value between 0 and 2^h-1. (The input has h bits)

(Let's say we are searching through the same array every time and hence we have the same oracle every time so the tree itself is not a part of input.)

> The output is YES or NO, indicating whether the input is in a node of the tree or not.

Question: whether this problem is NP complete or not in terms of h. This problem is NP because if a path to the YES node in the tree is given it can be verified in O(h) time.

Assuming NP != P, since the problem is in NP it must be either NP-complete or P (Apparently there is something called NP-intermediate (credited to Nicholas) so that's another possibility as well). If it is NP-complete, what problem can be used to reduce to this problem?

Note that if the oracle tree has the property that left subtree of a node is less than the node and right subtree of a node is greater than the node then the problem is in P and NOT in NP complete because binary search can be applied.

Intuitively, this problem can be viewed as a non-deterministic turing machine and every single possible path needs to be considered but this intuition cannot be used to "prove" the problem is NP complete. I want to know if we can reduce any known NP-complete problem to it.

Reference: (Original Post) https://stackoverflow.com/questions/28847966/array-search-np-complete

# Answer
> 5 votes
If you want to prove that a problem is **NP**-complete, you don't get to make up your own definition of **NP**. **NP** is the class of problems that can be solved by a nondeterministic Turing machine in time bounded by some polynomial function of the length of the input.

Specifically, you don't get to use oracles, you don't get to use some other measure of the size of the input (e.g., the logarithm of its length) and you don't get to make random access to the contents array: you have to walk the head of the Turing machine there, one cell at a time.

Your problem is, as you say in your first sentence, clearly in **P**. It is, therefore, very unlikely to be **NP**-complete, since that can only happen if **P**=**NP**.

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


# Question
Title: Given the "programs as proofs" isomorphism, how do we know that the program isn't lying?
I've been studying constructive type theory (CTT) and one of the things that I'm not clear on is the proof part: Proving the correctness of a program in a form of a proof that's nothing but the program itself (Curry-Howard Correspondence)

Most examples that I've seen in books (e.g., Type Theory and Functional Programming - Thomson and TaPL) show the "proofs" on $\lambda$-abstractions and applications on terms (i.e., literally $a, b, e...$). The proofs seem to mostly rely on the type signatures of the functions, under the *assumption* that the function does what it claims. Not much is discussed about the "how" of the function's correctness.

For example, when writing a real program (e.g., in Haskell and other \[pure\] functional languages), the *function* under consideration could do any arbitrary computation and return a term of the correct *type* for the proof to go through (statically speaking). So how do we know that the program is computationally doing the "right" thing (dynamically speaking) and not just faking it to get past a proofing system?

From what I understand, here's how things should go (and probably are, but I'm not sure if I'm right), crudely speaking:

1. Given a program's specification in something like predicate logic we "convert" it into an equivalent "typed representation"
2. Using backward inference we substitute the "functions" with their appropriate values, which themselves could be other functions (i.e., we replace the functions with their *computation rules*, but I'm thinking more on the lines of replacing the function with its *body*, from a programming point of view, for the sake of argument. Assuming that they're "returning" the correct type this seems like a believable substitution)
3. We continue doing #2 above till we hit primitive operations (again, crudely speaking) which we can trivially prove (or if not, maybe the proof is "simple" enough).
4. Once we've hit all the "axioms" (or trivial proofs) along all the branches of backward inferences, we stop.
5. QED

Two questions:

* Is my understanding/intuition of "how" the proof of correctness works in CTT works correct? It looks like it won't be possible for the program to "cheat" this or can it?
* And secondly, is this what proof assistants like Coq help you prove/analyze (at a high level)?

# Answer
> Proving the correctness of a program in a form of a proof that's nothing but the program itself

This is not quite how the Curry-Howard-Correspondence works.

First one has to show that the language of choice actually corresponds to some consistent logic. Different languages correspond to different logics, and many languages correspond to inconsistent logics which are not good for proving things. Haskell doesn't correspond to a consistent logic, because in Haskell, we can write nonterminating programs which would correspond to infinite proofs. But infinite proofs are invalid, so not every Haskell program corresponds to a valid proof.

Now what does it mean that **a language corresponds to a logic**? It means that:

* a **type** in the language corresponds to a **formula** in the logic
* a **program** in the language corresponds to a description of a **proof** in the logic
* a **well-typed program** in the language corresponds to a description of a **valid proof** in the logic.
* a **program of a specific type** in the language corresponds to a **proof of a specific formula** in the logic
* a **value** in the language correspond to **truth** in the logic
* **evaluation** of programs to values corresponds to **soundness** of the proving rules
* **reification** of values to programs corresponds to **completeness** of the proving rules
* ...

No need to understand all aspects of the correspondence at once, but it is good to keep in mind that the correspondence relates not just programs and proofs, but many (all?) aspects of the languages and the logic. For the question here, only the first four aspects are relevant.

A minor issue is that only well-typed programs correspond to valid proofs. That's why type signatures of functions are so relevant to the Curry-Howard-Correspondence.

**The key issue is that a well-typed program doesn't correspond to a valid proof of its own correctness, but to a valid proof of whatever formula corresponds to the program's type.**

For example, let us consider the following two programs (using Haskell syntax, but assuming a version of Haskell that corresponds to a consistent logic):

```
f :: a -> a -> a
f x y = x

g :: a -> a -> a
g x y = y

```

The functions `f` and `g` are **well-typed programs of the same type**, so they correspond to **valid proofs of the same formula**. The formula is "forall propositions p, p implies that p implies p".

But clearly, `f` and `g` are **different programs**. And of course, they correspond to **different proofs** of the same formula. The program `f` corresponds to the proof "We know that p implies p, so also p implies (whatever implies p)". And the program `g` corresponds to the proof "We know that p implies p, so also whatever implies (p implies p)."

Usually, with programming languages, we care about the difference between programs like `f` and `g`, and with logics, we don't care about the difference between the two proofs that correspond to `f` and `g`. But when thinking about the Curry-Howard-Correspondence, it is important not to forget that there can be multiple different valid proofs of the same formula.

> So how do we know that the program is computationally doing the "right" thing (dynamically speaking) and not just faking it to get past a proofing system?

We don't. We only know that the program proves **the formula we have encoded in the program's type**. So how can we use the Curry-Howard-Correspondence to prove a program correct? We have to encode a statement about program correctness into the type of the program. This requires a very expressive type system, of course, which is exactly what the languages inside tools like Coq or Agda provide.
> 9 votes

# Answer
In some sense it doesn't matter what the function does, as long as it takes the correct types and produces something of the correct type. The trick is that when you start talking about the Curry-Howard correspondence, the types are much more precise and specified that what we'd normally deal with day-to-day.

Moreover the Curry-Howard correspondence says that we can take a proof (in a variety of different logics) and produce a program by a "simple" substitution, and we can take a program (in something essentially lambda-calculus-esque) and produce a proof about the types.

So it doesn't quite say that it proves what the program does, it just proves a statement about the types. So a function that takes a natural number and produces a natural number is a proof that given a natural number, we can produce a natural number. It gives us nothing in particular (without extra work) about what number it actually produces.

When you start using more precise types, then things start to get interesting, and you get something like the process you outline, and give or take particulars, how things like Coq work.

To give an example from Coq, we can define a function:

```
Definition zero (n : nat) : nat := 0.

```

So all we get is zero, but if we look at the type of `zero`, we get `nat -> nat`. Not particularly interesting (but correct, which is what the type checker gives us).

We can however prove something about it:

```
Lemma zero_always : forall n, zero n = 0.
Proof.
  intros. destruct n. reflexivity. reflexivity.
Qed.

```

This is Coq's syntax for proving things, which gets translated into a program:

```
zero_always =
fun n : nat =>
match n as n0 return (zero n0 = 0) with
| 0 => eq_refl
| S _ => eq_refl
end

```

So the proof is a function that destructs the `nat` type, and applies some other thing which says that things that look identical are the same. Now the type of `zero_always` is

```
forall n : nat, zero n = 0

```

Which is a function from `nat`s (which we will give the label `n`) to things of type `zero n = 0`. So you can see that the types we need to say something useful about a program are a bit unusual compared to the run of the mill datatypes (but not really different in this context).

Going back a step, the `eq_refl` is actually a constructor of a type `eq`. `eq` has only the one contructor which is `eq_refl : x = x` where `x : A`, `A: Type` and hence `eq : A -> Prop`. Unravelling that, equality is a function that takes a single element of some type (for every type `A`) and produces a `Prop` (which is a proposition type, really just a `Type` but Coq uses it for convenience for other reasons) that says that element is equal to itself. So our `zero_always` proof applies a function that just applies another function, and because the very carefully chosen types match, we're happy (as long as we trust the type checker ;) ).
> 5 votes

---
Tags: type-theory, correctness-proof, intuition, proof-assistants, curry-howard
---


# Question
Title: What does the language {a, b, c}* exactly mean? How will the automaton for this look like?
What does the language {a, b, c}\* exactly mean?

# Answer
Any finite words composed of the characters $a,b$ & $c$ and the empty word are part of the language $\\{a,b,c\\}^\*$. The automaton has one state which is the starting and ending state. That state has 3 recursive edges which are reading $a$,$b$ and $c$.
> 1 votes

# Answer
It means this Language can 'generate' any string using the alphabets $a, b, c$, including the empty string $\epsilon$

There is no bound on the length of the string generated.

Here's a NFA that accepts such a language:
> 0 votes

---
Tags: formal-languages, automata, formal-grammars
---


# Question
Title: How can I build a DFA for ${a^m b a^n | m+n \equiv 1 mod 3}$?
I have a language $\\{a^m b a^n | m+n \equiv 1 mod 3\\}$

* $m+n$ can be 1, 4, 7, 10, 13, 16, 19, 22, ...
* $m+n$ is the number of all $a$'s in the word

How can I build a DFA for this language?

# Answer
Consider six nodes $v\_0,v\_1,v\_2$ and $v\_0', v\_1', v\_2'$, where $v\_0$ is the initial state. The automaton is in state $v\_i$ if we have already outputted $x \equiv i \mod 3$ times the character 'a' *before* we outputted a 'b'. Between $v\_0$ and $v\_1$, between $v\_1$ and $v\_2$ and between $v\_2$ and $v\_0$, we add a transition with output 'a'.

The same is done for the nodes $v\_0'$, $v\_1'$, and $v\_2'$, i.e., we are in state $v\_i'$ iff the total number (including the part before and the part after the 'b') of outputted 'a' equals $x \equiv i \mod 3$. Correspondingly, we connect $v\_0'$ and $v\_1'$, $v\_1'$ and $v\_2'$, and $v\_2'$ and $v\_0$ with transitions outputting 'a'.

Now we connect each $v\_i$ with the corresponding $v\_i'$ by a transition with output 'b' (since the output of a 'b' doesn't change the number of 'a' in the string). By assigning $v\_1'$ to be the final state, we are done.
> 2 votes

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


# Question
Title: Updating connections weights in neural networks
I am learning about neural networks and have a couple of things I don't understand.

Firstly, in competitive learning I understand that only the neuron with the strongest output is reinforced. That is done in a manners imilar to:

```
Δwi*j = I(j)*h(i)

```

Where w\* indicates the 'winning' neuron, j indicates the input we are considering, I(j) is the value of such input and h(i) is the sum of all weighted inputs. This is repeated for each connection leading to the winning neuron.

My question is... Why? Why not simply, for example, increase the connection by an arbitrary amount? Or by another function? I have done quite some research, but still can't make sense of this.

Thanks!

# Answer
> 1 votes
You actually can increase it by an arbitrary amount. The reason you are increasing it by the sum of all weighted inputs is so that the number you increment by is actually related to the neural network and the input. At least in that case, what you are incrementing by something that is related to what's going on. Otherwise, the behavior may be more random.

There are several functions you could choose to increment by instead. You could also choose to create new neurons (mitosis) where a neuron exceeds an arbitrary threshold. The method you're following is just another method that is being tested in trying to properly represent neural networks.

---
Tags: artificial-intelligence, neural-networks
---


# Question
Title: Can you determine rotation/camera calibration from series of images separated by pure rotation
I have a series of about 50 images, each separated by a small rotation and taken from the same camera. The images are feature-dense, and I can calculate a homography from image-to-image easily.

My question is, is there any way to determine the rotation matrix and/or intrinsic camera calibration parameters given just these images?

# Answer
> 2 votes
If the images are related by pure rotation, then the homography would give you the rotation matrix. If the rotation is in-plane, then you would not be able to compute the intrinsics.

---
Tags: image-processing, computer-vision
---


# Question
Title: Reccurence of recursive function with unequal sizes of subproblems
Given pseudocode:

```
X is an array

function FUN(X)
    l = length(X)
    if l <= 1 then
        PRINT("Hello")
        return
    end if
    p = l / 3
    FUN(X[1...p])
    FUN(X[(l-p+1)...l])
end function

```

I now want to get the reccurence of this pseudocode. At the moment I have $$T(n) = 2 \cdot T(\frac{n}{b})\cdot O(1)$$

but the problem is that I don't know how to handle the fact that the first recursive call has a subproblem size of $\frac{1}{3}$ and the second has a subproblem size of $\frac{2}{3}$. What is $\frac{n}{b}$ then?

# Answer
> 3 votes
Your timing function is $T(n)=2T(n/3)+1$, namely two recursive calls to one-third size problems plus a constant amount of time for the if test and the assignments. If you know the Master Theorem, the answer is immediate, namely $T(n)=\Theta(n^{\log\_32})$. If you don't know the MT, it's not too difficult to see the answer by expansion:

$$\begin{align} T(n) &= 2T\left(\frac{n}{3}\right)+1\\ &= 2\left(2T(\frac{n}{3^2})+1\right)+1=2^2\ T\left(\frac{n}{3^2}\right)+2+1\\ &=2^3\ T\left(\frac{n}{3^3}\right)+4+2+1 &\text{and, in general, we have}\\ &\dotsc\\ &=2^k\ T\left(\frac{n}{3^k}\right)+\left(2^{k-1}+\dotsm +4+2+1\right) \end{align}$$ Now let $n=3^k$ and the result follows with a little algebra.

# Answer
> 1 votes
The size of the problems aren't $\frac{1}{3}$ & $\frac{2}{3}$. The size of the two subproblems are $\frac{1}{3}$each, so $b=3$.

I have overlooked that the second recursive call only takes the latter $\frac{1}{3}$ of the problem instead of the latter $\frac{2}{3}$.

---
Tags: runtime-analysis, recursion, master-theorem
---


# Question
Title: How can I quickly guess if L is context-free or det. context-free?
I have a language, for example

* $\\{a^m b^n c^n \mid m, n \in \mathbb{N}, m = 2n\\}$
* $\\{a^l b^m \mid l, m \in \mathbb{N}, l=4^m\\}$

How can I see **at a glance** whether the language is deterministic context-free, context-free or not context-free? I'm not willing to try to prove the language to be context-free. I just want a heuristic -- a quick test I can apply by inspection, without use of a computer, that will often be correct.

# Answer
> 2 votes
This answer was first written before the OP edited the question to specify that he wanted "*a quick test I can apply by inspection, without use of a computer, that will often be correct.*"

Of course, I do not think anyone has such a test. To begin with, we should first define a meta-language defining sets of strings to which such a test could be applied. How general should this language be, as we can even define metalanguages that can describe only context-free sets. But that is no help, since the difficulty remains in the translation between metalanguages. In other words, this is simply an ill defined question as asked.

And even if we were to agree on the language, as something that looks more or less like the examples, we just do not have such tests. Actually the question was raised before, as a suggestion for research, but I do not recall there was any follow-up.

This discussion is mostly intended for the determination of CF-ness. Raphael rightly commented that if the language is known to be CF, even assuming that a CF grammar is known for it, it remains undecidable to determine whether it is deterministic CF. However, the OP is not asking for a decision procedure, but only a test which works most of the time. So assuming there is a proper definition of what most of the time means, such a test could still exist, though I do not know of any. To take an example in a somewhat different family of problems, there are primality tests that are fast and known to work most of the time, with a probability of error that can be chosen arbitrarily low (with increased cost).

Before I knew the OP wanted "a quick test", I thought he was only asking for the heuristics we use to get a feeling that some language is more likely to be this or that. I tried to give some hints on how I do it. There is nothing more to my answer. It is based on a few patterns that we see often enough, though the devil in the details may sometimes change the answer.

**Here is what I first answered**

Since your question is whether we can see things at a glance, the answer is that for many exercises, we can ... though we may occasionally make mistakes.

Very often the stack is used simply as a counter, which is only a small part of the CF power.

This is typically the case of the following example: $\\{a^l b^m \mid l, m \in \mathbb{N}, l=4m\\}$, you have to check that 2 subparts of the string have the same length $m$, up to a multiplicative rational constant (4 in this case). That is easily done with a pushdown stack, by pushing $m$ times in the stack the first time, and then popping $m$ times, checking that there is enough and not too much to pop. When you push, or pop, you can do it for several symbols to account for the constant.

However, this allows you to synchronize the sizes of two parts of the input string, but not more. Once the information is popped, it is lost and there is no way you can check a third part for the same size. This is the case of your first example, where you would have to check for $2n$ and twice for $n$, which makes three times, one too many.

The second example can be discounted as non CF for another reason. The pumping lemma, without going into details, does tell you that an infinite CF language has strings that can increase in size by constant increments. That is, there is some number $n$ such that you can find an infinite sequence of strings that increase in length by exactly $n$.

For a language of the form $\\{a^l b^m \mid l, m \in \mathbb{N}, l=4^m\\}$, when you increase $m$ by 1, the number of $a$ increases by $4^{m+1}-4^m=3\times 4^m$. That is incompatible with the presence of a linearly increasing sequence. Exponentials usually do that.

This is an example of using the pumping lemma without even bothering to try pumping anything. Geological considerations tell you the well will be dry.

Hence I conclude that none of your examples is CF,

But that is not always a full proof (though the pumping lemma use could be considered one). Mostly first evaluation at a glance, heuristics. One might combine exponentials so that things work.

As for deterministic, it is another kind of game. Basically, you try to see whether you have to guess sometning in order to do your counting right, so that it succeeds.

In the first example I gave, you obviously do not need any guess. It is deterministic CF.

But if you consider the language $\\{a^n b^{2n}c \mid n\in \mathbb{N}\\} \cup\\{a^n b^{4n}d \mid n\in \mathbb{N}\\}$ it is non deterministic because you have to guess the last symbol of the string before you decide to count with the constant 2 or with the constant 4.

*Thanks to Hendrik Jan for pointing out my misreading of one example.*

---
Tags: formal-languages, context-free, nondeterminism
---


title: What's the complexity of the Bombe?

text:
# Question
Title: What's the complexity of the Bombe?
Now my knowledge of this comes through watching The Imitation Game, a glance of a wiki article, and a couple of computerphile videos, so forgive me if it's obvious.

While watching the Imitation Game, I couldn't help but think that the Bombe that was being developed was just doing a naive search through all possible combinations, so there would be some days where you'd run through all 159 quintillion odd settings before you got to the right one. So why was it so good?

I understand that quite a few setting could be discounted, as the enigma machines couldn't map a letter to itself, but surely that's still quite a lot of settings to search through. And while it'll be faster than doing it by hand, it's still quite a lot.

So naturally, I'm guessing that one of my assumptions is wrong, and Turing and co. are in fact, smart cookies. What sort of algorithm are they using to break the cypher, or how are they filtering the possible iterations down?

# Answer
No, the Bombe was not doing brute-force search over all possible internal settings of the Enigma machine. Read the Wikipedia article on the Bombe, which has a detailed explanation of the techniques used by the Bombe: https://en.wikipedia.org/wiki/Bombe.
> 1 votes

---
Tags: complexity-theory, cryptography
---


title: Definition of co-RE class

text:
# Question
Title: Definition of co-RE class
I know that the definition of RE class is: $\ RE = \left \\{ L \subseteq \Sigma ^{\*} | \text{Exists M which accepts L} \right \\}$

Can someone explain in the same notation the definition of co-RE.

# Answer
> 4 votes
The definition of coRE is $$ coRE = \\{L\subseteq\Sigma^\*|\text{Exists $M$ which accepts $\Sigma^\* \setminus L$}\\}. $$

---
Tags: terminology, computability
---


title: Is the Wall-Follower Algorithm in P?

text:
# Question
Title: Is the Wall-Follower Algorithm in P?
Is the wall-follower algorithm a poly-time algorithm (for Perfect Mazes)?

In particular, are there poly time algorithms for solving the Perfect Maze problems?

A perfect maze has the following properties:

* no inaccessible areas and is simply connected.
* no closed loops
* one and only one path from any point to any other point.
* the maze has exactly one solution.

# Answer
> 2 votes
Yes, there is a polynomial-time algorithm for solving perfect mazes: depth-first search solves them, and runs in polynomial time. Actually, depth-first search is more general, as it can handle loops and other structures, too.

Breadth-first search also works, and will give you the fastest way out of the maze, but is only implementable on a computer given the full description of the maze. In contrast, depth-first search can be implemented by a human with a piece of chalk and a ball of string -- the piece of chalk allows you to mark rooms as visited, and the ball of string lets you simulate the stack.

# Answer
> 2 votes
Wall-following is exactly depth-first search with a specific order on the children of each vertex. So, as D.W. points out, it's a polynomial-time algorithm.

---
Tags: algorithm-analysis, runtime-analysis
---


# Question
Title: Prove that Language is not Regular using closure(s)
I'm having a really tough time trying to comprehend proofs via closure and pumping lemma. None of the examples I can find are similar to the one's im looking to prove. Can anyone explain if I'm totally missing the mark here or is this valid?

Question: Prove that $$ L = \\{0^x 1^y 2^{x+y} \mid x \ge 0 \text{ and } y \ge1\\}\qquad\text{is not Regular.} $$

Must use Closure(s).
Your "destination" should be $$ \\{ a^z b^z \mid z \ge 1\\}, \qquad\text{ which we know is not Regular.} $$

Start with $L$

(show a sequence of operations and results)

End with $\\{a^z b^z\\}$ which is not regular

Answer:

If $L$ is regular then $L'$ must be regular $$ L' = \\{(0^x)' (1^y)' (2^{x+y})' \mid x \ge 0, y \ge1 \\} $$ Let $E$ be an element of $L'$ where $E = \\{a^z b^z \mid z\ge 1\\}$. Since we know $\\{a^z b^z \mid z\ge 1\\}$ is not regular from using pumping lemma, etc. $L$ is not regular

# Answer
What is your " ' " operator? Could it perhaps be the homomorphism $0\rightarrow a, 1\rightarrow a, 2\rightarrow b$? If not, consider this as a hint, since regular languages are closed under homomorphisms.
> 2 votes

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


# Question
Title: Finding all circuits that contain a given edge
Given a *directed graph* $G = (V, E)$ and an edge $e \in E$, I'm trying to come up with an algorithm to construct the minimum induced subgraph $H$ of $G$ with the property that every circuit in $G$ that traverses $e$ is in also in $H$.

As an example, suppose graph $G$ has vertices $V = \\{1,2,3,4\\}$ and edges $\\{(1,2), (2,1), (2,3), (3,2), (3,1), (2,4), (4,3)\\}$, and $e = (4, 3)$. The subgraph $H$ that the algorithm should output consists of the two circuits $2,4,3,2$ and $2,4,3,1,2$.

Of course, this problem can be solved by enumerating all circuits of $G$, but I'm hoping that someone here can come up with something better (that is, with strongly polynomial complexity, in the size of the graph) than that.

**EDIT:** I just found this post that solves the problem for *undirected* graphs, but it doesn't provide any directions for *directed* graphs. I don't see a straightforward generalisation to *directed* graphs from that post.

# Answer
It should be NP-complete to compute, given an arc $e = uv$ of a directed graph $D = (V,A)$ whether there is a cycle containing some vertex $w$ using the arc $e$. The instance to this problem is $(D,e,w)$.

By reducing from back-and-forth (two-disjoint paths from $a$ to $b$ and from $b$ to $a$), given an instance $(D',a,b)$ of back-and-forth, construct the instance $D$ where you make two copies of $a$, $a\_1$ and $a\_2$ and an arc going from $a\_1$ to $a\_2$. The constructed instance is $(D,(a\_1a\_2),b)$.

Now, suppose there are two-disjoint paths from $a$ to $b$ and back, then there is a cycle from $a\_2$ to $b$ and from $b$ to $a\_1$, hence $b$ is on a cycle containing the arc $a\_1a\_2$. For the reverse direction suppose that $b$ is on a cycle traversing the arc $a\_1a\_2$. Then, in the original graph, there is a path from $a$ to $b$ and one from $b$ to $a$. qed
> 1 votes

---
Tags: algorithms, graphs, search-algorithms
---


# Question
Title: Why can't we solve the Halting Problem by using Artificial Intelligence?
Yesterday I was reading about Computability and they mention the Halting Problem. It got stuck in mind all day until I remember that some weeks ago, when learning Java, the IDE (Netbeans) show me a warning saying that my code was going to result in an infinite loop.

My question is, why can't this problem, be solved by using an "Intelligent" program to determine if another program will halt or end in an infinite loop? This hypothetical program could look for repetitive structures, conditions, etc and even predict under which circumstances (possible inputs) will halt, loop infinitely or end. Maybe like looking for the "acceptable range", like the domain of a mathematical function.

# Answer
> 18 votes
The halting problem is not a statement about intelligence (human or artificial) it is a statement about the limits of mathematics. It is an historically important example of an undecidable problem.

An artificial (or human) intelligence can certainly look for and find many sorts of different infinite loops in real programs. And the halting problem doesn't say that such a thing is impossible or even very hard.

What the halting problem says is that given any program $I$ ("I" for "intelligent"), (say a really complicated AI program written in Netbeans) that looks for infinite loops we can produce a program that $I$ can't analyze. The way we do this is a clever technique called *diagonalization*, which is described in the question @Raphael linked: How to show that a function is not computable?, and also in Why, really, is the Halting Problem so important?

The halting problem is similar to the Liar's Paradox in that it demonstrates the limits of mathematical and logical definitions of "truth", and "provability". The Liar's Paradox is: suppose I say "this statement is a lie." Is that statement true or false? If it is true then it must be a lie, so must be false. If it is false, then it is not a lie, so must be true. Writing a complicated artificial intelligence (or relying on a really smart person) won't make the question about whether I lied or not any more meaningful.

---
Tags: computability, artificial-intelligence, halting-problem
---


# Question
Title: Finding a Hoare logic correctness proof for a Repeat-Until loop
How can we prove a program in repeat until using Hoare Logic?

I've found a rule like this:

```
{P} S {R}, {R ^ ~B -> P}, {R ^ B -> Q}

```

for

```
{P}
repeat
  S
until B
{Q}

```

But I still can't find any explanatiom how I can use this rule

For example in this question:

```
{x > 0 ^ y > 0}
     z:=0; u:=x;
     REPEAT
        z:=z+y;
        u:=u-1;
     UNTIL u=0;
{z = x * y}

```

How I can use the rule to prove this program?

UPDATE I've tried to find invariant loop:

```
R : Z = X*Y + (Y - Y*U)

```

But I still confuse what is P?

# Answer
Note that the loop is not the outermost construct in your program; that is a sequential composition. In order to apply this rule, you first need to take care of the initial assignments. In this case that is straightforward: you get that the formula $x\>0\wedge y\>0\wedge z=0\wedge u=x$ holds after $z:=0; \ u:=x$.

For the loop rule, you need three formulas: a precondition $P$, a postcondition $Q$, and an invariant $R$, satisfying the premises of the rule. The precondition $P$ also needs to follow from the formula we obtained above. The postcondition $Q\equiv z=x\*y$ is already given in your initial triple. What is left to do is therefore to find $P$ and $R$ such that

* $(x\>0\wedge y\>0\wedge z=0\wedge u=x)\to P$,
* $\\{P\\}\ z:=z+y;\ x:=x-1\ \\{R\\}$,
* $(R\wedge u\neq 0)\to P$,
* $(R\wedge u=0)\to z=x\*y$.

A special case which may be worth trying here is to assume that the third condition holds with equality, i.e. $P\equiv (R\wedge u\neq 0)$. This reduces the problem to finding $R$ such that

* $(x\>0\wedge y\>0\wedge z=0\wedge u=x)\to (R\wedge u\neq 0)$,
* $\\{R\wedge u\neq 0\\}\ z:=z+y;\ x:=x-1\ \\{R\\}$,
* $(R\wedge u=0)\to z=x\*y$,

which is essentially an application of the usual while rule. As for how to find $R$, that is in general a very tricky problem. You seem to be looking in the right direction, but you invariant still needs some work (checking which of the conditions it fails, and how, may help with that).
> 4 votes

---
Tags: logic, loops, hoare-logic, software-verification
---


# Question
Title: Prove that regular expression is unambiguous
I've got following definition:

Function $f$ is a *valid mapping* of word $w$ to regular expression $R$, if any of following conditions is true:

1. $R = w$ and $f$ is the identity or $R = \epsilon$ and $w = \epsilon$;
2. $R = R\_1 + R\_2$ and $f$ is a valid mapping of $w$ to $R\_1$ or $f$ is valid mapping of $w$ to $R\_2$;
3. $R = R\_1R\_2$, and $w$ can be written as $w\_1w\_2$ such that $f$ limited to $w\_1$ is a valid mapping of $w\_1$ to $R\_1$, and $f$ limited to $w\_2$ is a valid mapping of $w\_2$ to $R\_2$; or
4. $R = S^\*$ and $w$ can be written $w = w\_1w\_2\dots w\_k$ for some $k \geq 0$ and, for all $1\leq i\leq k$, $f$ limited to $w\_i$ is a valid mapping of $w\_i$ to $S$.

A regular expression $R$ is *deterministic* (unambiguous) if, for every $w\in L(R)$, there exists exactly one valid mapping from $w$ to $R$.

I need to prove that the regular expression $R = 0^\*(11^\*000^\*)^\*11^\*01(1+0)^\*$ is deterministic. I think that first I should prove that there exists a valid mapping for every word $w$ to $R$ and then assume that there's a different mappings and lead to a contradiction. But I've got problems with details (especially with the second part of the proof).

# Answer
This answer has 3 parts:

* I first answer the question as asked, sketching the beginning of a proof concerning the example given. A full proof is too long and tedious to be given here.
* Then I give a general procedure to solve the problem and decide whether a regular expression is deterministic/unambiguous.
* Finally I discuss some difficulties and problems with the statement of the question.

## A direct answer to the question

What you may first prove, though it should be obvious, is that for any regular expression $R$, there is a valid mapping of any word $w\in L(R)$ to $R$.

Then you consider the regular expression $R = 0^\*(11^\*000^\*)^\*11^\*01(1+0)^\*$ to be analyzed, and you procede to decompose it structurally, showing that at every step, there is only one way to decompose a string $w\in

For example, you show that there is only one way to decompose a string $w\in L(R)$ as $w=uv$ with $u\in L(0^\*)$ and $v\in L((11^\*000^\*)^\*11^\*01(1+0)^\*)$. The reason is that $u$ contains only $0$, and $v$ begings necessarily with a $1$. So the string $w$ must be cut just before the first one. Then there is only one way to get a valid mapping for the whole expression, from valid mapping of the two subexpressions. If the subexpressions are themselves proved detrministic, i.e. with only one valid mapping fo any string in their language, then the whole expression must be deterministic.

Hence you now have to prove only that, $0^\*$ and $(11^\*000^\*)^\*11^\*01(1+0)^\*$ are deterministic, since their concatenation has a unique decomposition.

So you go on decomposing the expression into subexpression, such that you have a unique way of matching them with a string of the language.

The next step is to show there is only one way to decompose a string $w$ in $L((11^\*000^\*)^\*11^\*01(1+0)^\*)$, as $w=u01v$, with $u\in L((11^\*000^\*)^\*11^\*)$ and $v\in L((1+0)^\*)$

And so on ... For each subexpression, you must perform the analysis according to the type of the subexpression, following the definition given for each of the four types in the definition of valid mapping.

In the case of $R=S+T$, where $S$ and $T$ are subexpressions of $R$, you only have to prove that $L(S)\cap L(T)=\emptyset$.

This gives you the general idea of a proof on a given example, such as the one above.

However, such a proof is very tedious and prone to errors.

So you would be better off designing an algorithm that will decide mechanically whether a regular expression is ambiguous or not. The problem is decidable, and not so hard. I follows the same lines I sketched: recursive decomposition of the regular expression, which things to be checked depending on the operator (concatenation, union, Kleene star).

## A procedure to decide ambiguousness of a regular expression.

To decide ambiguousness of a regular expression, one must recursively decompose the expression into 1 or 2 subexpressions dominated by an operator, down to the leaf level.

Given a regular expression $R$,

1. If $R=w\in \Sigma+$, then $R$ is unambiguous;
2. If $R=R\_1+R\_2$, then $R$ is unambiguous iff both $R\_1$ and $R\_2$ are unambiguous, and $R\_1\cap R\_2=\emptyset$. If the intersection is not empty, any valid mapping from string to $R\_1$ could instead map validly to $R\_2$; hence there would be two valid mappings. Also, if there were two distinct valid mappings to one daughter, say $R\_1$, then by application of rule 2 of the definition, there would be two valid mappings to $R$.
3. If $R=R\_1 R\_2$, then $R$ is unambiguous iff both $R\_1$ and $R\_2$ are unambiguous, and there is only one way to decompose any string $w\in L(R)$ into 2 substrings as $w=w\_1 w\_2$ such that $w\_1\in L(R\_1)$ and $w\_2\in L(R\_2)$. $R\_1$ and $R\_2$ must be both unambiguous because, as before, if one were ambiguous, say $R\_1$ for a string $w\_1$, if would be possible to build two valid mappings for $R$, which would thus be ambiguous.

But how does one check that string $w\in L(R)$ can be decomposed in only one way into two substrings $w=w\_1 w\_2$ with $w\_i\in L(R\_i)\text{ for }i=1,2$? This can be checked by attempting to simulate 2 simultaneous generations of a string in $L(R)$, such that 2 distinct prefix of the substring will be associated to $R\_1$.

Let $A\_1$ and $A\_2$ be two FA recognizing $L(R\_1)$ and $L(R\_2)$, having (to simplify) one start state and one accepting state. A FA for $L(R)$ can be obtained by linking then with an empty transition from the accept state of $A\_1$ to the start state of $A\_2$.

Then one can build a new FA $A^2$ by doint a cross product of the state set of $A$ with itself to simulate 2 computations at the same time. Both computations must be synchronized so that they scan the input together, though not necessarily following the same computational paths for each simulated automaton. Both computations must at some point cross the linking transition. This is memorized in the final state so that the double computation ends in acceptance iff the both reach the final state of $A\_2$, but after crossing the linking transition at different points in the input.

This automaton $A^2$ recognizes the language $\\{w\in L(R)\mid w=uv=u'v' \wedge u\neq u' \wedge u,u'\in L(R\_1) \wedge v,v'\in L(R\_2)$

Hence, strings in $L(R)$ can be decomposed unambiguously in two strings belonging respectively to $L(R\_1)$ and $L(R\_2)$ iff $L(A^2)=\emptyset$.
4. If $R=S\*$, then $R$ is unambiguous iff $S$ is unambiguous, and there is only one way to decompose any string $w\in L(R)$ into a concatenaton of substrings in $L(S)$.

The technique is similar to the one used for concatenation. You take a FA $A\_S$ recognizing $L(S)$, with a single accept state, and you connect the accept state to the start state with an empty "looping" transition, to get a FA $A$ for $L(R)$. Then, you buils a FA $A^2$ that simulates two computations of $A$ and accepts only when they both accept, but with the constraint that they must have crossed the looping transition at least once while being at different points of the input (or possibly a different number of times).

Again, strings in $L(R)$ can be decomposed unambiguously in a sequence of strings in $L(S)$ iff $L(A^2)=\emptyset$.

## Caveats

Some care must be taken with the empty word $\epsilon$. It is not clear that the problem is always well defined in this respect. The empty word $\epsilon$ may be used in regular expressions but will have no apparent counterpart in strings of the language. They can be ignored, But then, what of a Kleene star $R=S^\*$ when $\epsilon\in L(S)$. Should it be considered always ambiguous.

Another point is that the concept of valid mapping is really a mapping of occurrences of words to occurrences of regular expressions, i.e., to the syntactic instances, rather than to regular expressions as abstract concepts.

For example, consider the string $w=011001$ and the regular expression $R=(01)^\*100(111)^\*1$. There is a valid mapping $f$ of $w$ to $R$. However it associates the first instance of $01$ with $(01)^\*$, and the second instance of $01$ with $0(111)^\*1$.

What is worse, even considering occurences, $f$ is not a mapping since it associates the first instance of $01$ with both $(01)^\*$ and the regular expression $01$ to which the Kleene star is applied. Hence $f$, as it is defined, cannot be considered a mapping.

Actually, it seems that **$f$ should be defined as a mapping of $R$ and each subexpression occurrence in $R$ to substrings of $w$**.

But up to that rephrasing of the problem, everything holds.
> 5 votes

---
Tags: formal-languages, proof-techniques, regular-expressions, ambiguity
---


# Question
Title: Count pairs of nodes in a tree that are connected by a path whose labels have gcd 1
Given an un-rooted tree with N nodes, numbered from 1 to N. Each edge of the tree has a positive integer, associated with it. We need to calculate the number of unordered pairs (S, T) of tree's nodes such that the greatest common divisor of all the integers associated with the edges of the path between S and T is equal to one. Of course, we consider only the pairs where S isn't equal to T.

But main problem is N (Number of nodes in tree is 100000) So is their any better solution than O(N^2) as I currently have O(N^2) approach to do this problem using LCA between 2 nodes of tree.

So given a tree with N nodes and N-1 edges can we have a better algorithm ?

# Answer
> 1 votes
If there are a lot of large numbers on the edges I do not know, but if the number of different prime factors on the edges is limited there seems to be an efficient algorithm.

The approach is as in Longest path in an undirected tree with only one traversal.

Make the tree rooted, so you can work bottom up. In each node $v$ keep for each possible number $d$ the number of successor nodes in the tree that have a path up to $v$ with gcd $d$. If we move up in the tree we extend the paths of the children (taking into account the values on the edges) to the parent, *and* count the paths that connect two successors that run via the parent (if the ggd's are $1$).

Each node is visited only once, but there is quite some work between edges at each node.

Example.

At node $g$ we store $1$ incoming path with gcd $3\cdot 5$, and $1$ incoming path with gcd $3\cdot 7$: $\[3\cdot 5\to 1, 3\cdot 7 \to 1\]$. At node $h$ we store: $\[5\to 1, 5^2\to 1, 7 \to 1\]$. At node $i$ we store: $\[3\cdot 7\to 1, 5\to 1, 5\cdot 7 \to 1\]$.

With this information we obtain zero paths via $g$ with gcd $1$, two paths via $h$ with gcd $1$, and one path via $i$ with gcd $1$.

We now move the path info upwards. One new path from $g$ to $j$ with gcd $3^2\cdot 7$, and we add the info from $g$ after performing the gcd with the last edge: $\[3\to 1, 3\cdot 7 \to 1, 3^2\cdot 7\to 1\]$. One new path from $h$ to $j$ with gcd $2\cdot 5$, and we add the info from $h$ after performing the gcd with the last edge: $\[5\to 2, 1 \to 1, 2\cdot 5\to 1\]$. One new path from $i$ to $j$ with gcd $3^2\cdot 5$, and we add the info from $h$ after performing the gcd with the last edge: $\[3\to 1, 5 \to 2, 3^2\cdot 5\to 1\]$.

Altogether we store at $j$: $\[3\to 2, 3\cdot 7 \to 1, 3^2\cdot 7\to 1,5\to 4, 1 \to 1, 2\cdot 5\to 1, 3^2\cdot 5\to 1$. This info is bounded by the possible divisors of the edge labels.

We finally compute the \`via' count at $j$ by considering the lists at pairs of children. Quite some work. All paths from $g$ and from $h$ have gcd $1$, so we count $3\cdot 4 = 12$. I count $6$ between $h$ and $i$, and $3$ between $g$ and $i$.

---
Tags: algorithms, trees, counting
---


# Question
Title: When is the big-O relation preserved under exponentiation?
Suppose that $f, g$ are functions from the positive integers to the positive reals. Under what circumstances will $\log f(n)=O(\log g(n))$ imply $f(n)=O(g(n))$?

---

It's easy to see that this isn't always true: If $f(n)=3^n$ and $g(n)=2^n$ then we know that $3^n\notin O(2^n)$, but taking logs gives $\log3^n = n\log 3$ and $\log 2^n=n\log 2$ and it's obvious that $n\log 3=O(n\log 2)$.

The reason is also clear: If there exists a $c\>0$ such that $\log f(n)\le c\\,\log g(n)$ then all we can say is that $f(n)\le (g(n))^c$, which won't necessarily allow one to conclude $f(n)=O(g(n))$. When, though, can we correctly make the inference?

# Answer
It is at least sufficient to have $\log f(n) \in o(\log g(n))$. This gives us that for sufficiently large $N$, we have $\log f(n) \leq \log g(n)$ for all $n \> N$.

Hence immediately we have that for $c=1, n \> N$, $f(n) \leq c\cdot g(n)$ and ergo $f(n) \in O(g(n))$.

This also suggests the condition that if we have that $\log f(n) \leq c\cdot \log (g(n))$ where $c \leq 1$ for sufficiently large $n$, then we also get $f(n) \in O(g(n))$.
> 1 votes

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


# Question
Title: Solution to the following recurrence relation and initial condition?
With the initial condition being $a\_0$ = 3, and the relation being $a\_n = 2a\_{n - 1}$, what would the solution be? Any help would be greatly appreciated.

# Answer
> 2 votes
Try to calculate $a\_1$. You'll see that $a\_1=2\times3$. Then $a\_2=2a\_1=2\times2\times3=2^2\times3$.

Conjecture that $a\_n=3.2^n$ for all $n\ge 0$.

Prove by induction.

---
Tags: recurrence-relation
---


# Question
Title: How to create an LR($k$) grammar for a given language?
How can I construct an LR($k$) grammar (which $k$ is not really of interest for now) for a given language, say:

$$L=\left\\{w \in \\{a, b\\}^\star \ | \ \exists u \in \\{a, b\\}, v \in \\{a, b\\}^\star: w = vu \wedge |w|\_u \operatorname{mod} 2 = 0\right\\}$$

($|w|\_u$ denotes the number of $u$'s in $w$).

Please note that I don't want a right or left linear grammar although I KNOW that the language is regular. I am interested in the process of creating an LR($k$) grammar for an arbitrary, in general more complex language. (Feel free to ignore this example.)

# Answer
You question is very strangely stated. The answer is however very trivial. Your language $L$ is a regular language, hence recognizable by a DFA. It does not even need a pushdown stack. Hence it has to be LR(k). Indeed, the lookahead is necessary only to make the recognition deterministic, but in this case, it is deterministic to start with if you use the DFA (this is a bit tautological, since building the LR parser involve in general building a DFA, if my memory does not fail me)

You can get the LR grammar (if one dares calling it that, trivial as it is) just by taking the right-linear grammar corresponding to the transitions of the DFA.

BTW, **it is not easy to decide whether a given grammar is LR(k) for some unknown k, it is undecidable**. But it is decidable when k is given, you just try to build the tables.

To answer your question about a procedure to build a LR(k) grammar for a given CF language, the answer is "*sorry: not in this universe*".

The reason is that it is undecidable whether a given CF language is deterministic or not. Since any deterministic CF language has a LR(k) grammar, if a procedure existed to produce a LR(k) grammar for a language, when possible, that would be a procedure to decide whether the language is deterministic. Since no such procedure can exist, we have no systematic way of obtaining an LR(k) grammar for the language.
> 1 votes

---
Tags: formal-grammars, parsers, lr-k
---


# Question
Title: Can a Language be determined by its kleene closure?
Lets assume that we have access to a oracle (machine that determines without details) for $L^\*$, can we calculate $L$ from this machine? The cost of operation is measured by number of queries from oracle.

Can any property of $L$ like being prefix free or regular help?

What if the language be finite and instead of $L^\*$ we have an oracle access to $L^k$ for a known $k$?

# Answer
Consider $L\_1 = \\{a\\}$ and $L\_2 = \\{a, aa\\}$. In this case $L\_1^\* = L\_2^\*$. Thus a language is not uniquely determined from its Kleene closure.

Moreover you cannot determine a lot of information about a language from simply querying an oracle. Even if you had access to an oracle for $L$ itself rather than $L^\*$, you would not learn much.

That is because you can only ever do a finite number of queries to the oracle. So for a finite number of strings, you know if they are in the language. It could be that every string, which you did not query, is in the language, which would make $L$ regular. Or it could be that none of the strings, which you did not query are in the language, which would also make $L$ regular. It is also possible to simply pick any arbitrary regular language $L'$ and assume that the rest of the strings are in $L$ if they are in $L'$ and vice versa. In that case $L$ would also be regular, because adding or removing a finite number of strings from a regular language would also produce a regular language.

The parts of $L$ which you did not yet query the oracle about could also have a non-regular structure, it could even be non-computable.

There are properties about $L$ which could help. For example if a property about $L$ was stated in such a way, that there would only be a finite number of languages satisfying the property, the problem would get a lot simpler.

For certain properties about $L$, it would even be possible to identify an $L$ from an infinite set of candidates, however such an algorithm would not necessarily terminate, if given an input not satisfying the property.

For example if it is required that $L$ consists of exactly one string, there are infinitely many candidate languages, but knowing the alphabet, it is possible to search for this string and find it in finite time. If this algorithm was executed on $Ø$ (which does not satisfy the property), the algorithm would never terminate.
> 10 votes

# Answer
Being prefix free would certainly help, but this is not the more general situation where the solution is easy.

A language $X$ is a (*length variable*) *code* if $X^\*$ is a free monoid. This means that if $x\_1, ..., x\_n$ and $y\_1, ..., y\_m$ are elements of $X$ such that $x\_1 \dotsm x\_n = y\_1 \dotsm y\_m$, then $n = m$ and $x\_1 = y\_1$, $\ldots$, $x\_n = y\_n$. This is the case in particular if $X$ is a *prefix code*, which means that if $x, xu \in X$, then $u = 1$ (the empty word). This is also the case for the dual notion of a *suffix code*. However, there exist codes which are neither prefix nor suffix, like $\\{aa, ba, baa\\}$ (Exercise !)

Now, if $X$ is a code, then $X = X^+X^+ \setminus X^+$ where $X^+ = X^\* \setminus 1$. Consequently, when $X$ is a code, it is very easy to compute $X$ from $X^\*$ and the solution is unique. In particular, if $X^\*$ is regular, so is $X$.
> 4 votes

---
Tags: formal-languages, automata
---


# Question
Title: The equivalence relations cover problem (in graph theory)
An equivalence relation on a finite vertex set can be represented by an undirected graph that is a disjoint union of cliques. The vertex set represents the elements and an edge represents that two elements are equivalent.

If I have a graph $G$ and graphs $G\_1,\dots,G\_k$, we say that $G$ is covered by $G\_1,\dots,G\_k$ if the set of edges of $G$ is equal to the union of the sets of edges of $G\_1,\dots,G\_k$. The edge sets of $G\_1,\dots,G\_k$ do not need to be disjoint. Note that any undirected graph $G$ can be covered by a finite number of equivalence relations (i.e., disjoint union of cliques graphs).

I have several questions:

* What can be said about the minimal number of equivalence relations required to cover a graph $G$?
* How can we compute this minimal number?
* How can we compute an explicit minimum cover of $G$, i.e., a set of equivalence relations whose size is minimal and which cover $G$?
* Does this problem has any applications apart from partition logic (the dual of the logic of subsets)?
* Does this problem has a well established name?

---

Given the various misunderstandings indicated by the comments, here are some pictures to illustrate these concepts. If you have an idea for an easier to understand terminology (instead of "cover", "equivalence relation", "disjoint union of cliques" and "not necessarily disjoint" union of edge sets), feel free to let me know.

Here is a picture of a graph and one equivalence relation covering it:

Here is a picture of a graph and two equivalence relations covering it:
It should be pretty obvious that at least two equivalence relations are required.

Here is a picture of a graph and three equivalence relations covering it:
It's less obvious that at least three equivalence relations are required. Lemma 1.9 from Dual of the Logic of Subsets can be used to show that this is true. The generalization of this lemma to nand operations with more than two inputs was the motivation for this question.

# Answer
The problem is known as the *equivalence covering problem* in graph theory. It is upper bounded by the *clique covering number* (the minimum collection of cliques such that each edge of the graph is in *at least* one clique). There are many similar problems and definitions; one has to be very careful here. These two numbers are denoted by $\text{eq}(G)$ and $\text{cc}(G)$, respectively.

There are special graph classes where the exact value or a good upper bound for either number is known. In general, to the best of my knowledge, the best bounds are given by Alon \[1\]:

$$\log\_2 n - \log\_2 d \leq \text{eq}(G) \leq \text{cc}(G) \leq 2e^2 (\Delta+1)^2 \ln n,$$

where $\Delta$ is the maximum degree of $G$. By the way, a covering with $\lceil n^2/4 \rceil$ triangles and edges is always possible (cf. Mantel's theorem), and this is easy to find algorithmically as well.

Not surprisingly, computing either number is $\sf NP$-complete. Even for split graphs, computing $\text{eq}(G)$ is $\sf NP$-hard (but can be approximated within an additive constant 1) as shown in \[2\]. It is also hard to compute for graphs in which no two triangles have a vertex in common \[3\].

---

\[1\] Alon, Noga. "Covering graphs by the minimum number of equivalence relations." Combinatorica 6.3 (1986): 201-206.

\[2\] Blokhuis, Aart, and Ton Kloks. "On the equivalence covering number of splitgraphs." Information processing letters 54.5 (1995): 301-304.

\[3\] Kučera, Luděk, Jaroslav Nešetřil, and Aleš Pultr. "Complexity of dimension three and some related edge-covering characteristics of graphs." Theoretical Computer Science 11.1 (1980): 93-106.
> 5 votes

# Answer
Although I don't know the name for such problem, I can show this problem is NP-hard.

For a triangle free graph, all equivalence classes must be a matching. The minimum number of equivalence classes that covers the graph equals the chromatic index of the graph.

According to this article, finding the chromatic index for a triangle free graph is NP-complete.
> 6 votes

---
Tags: algorithms, graphs, clique
---


# Question
Title: Does complement distribute over concatenation?
**Prove or disprove**

$\exists L\_{1},L\_{2}\subseteq\Sigma^{\*}:\quad L\_{1}\ne L\_{2}\wedge\overline{L\_{1}\cdot L\_{2}}=\overline{L\_{1}}\cdot\overline{L\_{2}} $

Where $\cdot$ means concatenation, and over line is complement. Also, Let $\Sigma=\\{a,b\\}$.

# Answer
It is possible. **Hint**: Let $L\_1=a^\*, L\_2=\Sigma^\*$. Fill in the details.
> 5 votes

# Answer
A good starting point is to try to find languages and apply them to your formula, in attempt to satisfy it.

Try first very simple languages, such as $\emptyset$, $\Sigma^\*$, or $\\{a\\}$. If they don't work out, try more complex ones that fix the 'flaws' the simple languages had.

If it feels impossible to find languages that satisfy the formula, it might just be impossible.
> 1 votes

---
Tags: formal-languages
---


# Question
Title: Is radix sort really O(n) for sorting 32 bit integers?
I was trying to analyze radix sort in terms of time and space. Assume that we are given $n$ 32-bit integers which we would want to sort by looking at the least significant digits first.

$k$ is the total amount of bits that you will be working with at every step. So at first you look at the first $k$ bits, and sort the elements with counting sort. Then you look at the next $k$ bits etc.

In total we would have to run counting sort $\frac{32}{k}$ times. In the counting sort phase we will both have to scan the input array and also the bucket array, where the input array is of size $n$ and the bucket array is of size $2^k$. In other words the running time is going to be $ \Theta (\frac{32}{k}(n+2^k))$. As for space, we will need an extra temporary array of size $n$ during the counting sort phase, and also an array for the bucket, so in total the space will be $\Theta (2n + 2^k)$

So we have:

**Time: $ \Theta (\frac{32}{k}(n+2^k))$**

**Space: $\Theta (2n + 2^k)$**

Am I the only one who can't see why this is $O(n)$?

# Answer
> 14 votes
You can choose $k = 1$ and then the time is $\Theta(32(n+2)) = \Theta(n)$ and the space is $\Theta(2n + 2) = \Theta(n)$. In general, if you replace 32 by any *fixed* number, the complexities will be $\Theta(n)$. If, however, you try to use radix sort with integers of non-constant width $m$, the complexities will be as stated (with $32$ replaced by $m$), or even worse, since you are assuming that operations on these integers take constant time, which might not be the case for integers of arbitrary size (depending on your computation model).

---
Tags: algorithms, algorithm-analysis, radix-sort
---


# Question
Title: Why Shannon's Entropy is said to be a measure of information?
I got a bit of how Shannon explained to find the number of bits required to represent a message and Shannon's Entropy.But it's natural to know that to code alphabet letters you need `5` bits of information starting from `0000` to `11001`.

Is that because at his time no one knew how to represent bits in information that Shannon came with looking at the unpredictability of the message to determine the number of bits needed to represent a message?

It's really getting confusing why would one need to consider terms like entropy,probability etc as said in Coding Theory to get the number of bits to represent a message when we already know that to represent 32 letters we need `5` bits.

Is there really any other reason behind why did Shannon came with these terms in the field of communication other than finding the number of bits required to represent a message?

# Answer
> 5 votes
Yes, of course. Shannon's work was on the transmission of information over discrete, noisy channels. It centred on the trade-off between bandwidth and signal-to-noise ratio, and, grossly over-simplifying it, in particular what the maximum transmission rates could be with and without the presence of noise induced error and how to construct suitable codes. This involves coding theory1 and probability theory, which is where some of things that have you confused come from.

It is also incorrect that you *need* 5 bits to encode letters. If we have a known frequency distribution of the letters, we can encode the more frequent ones with fewer bits, and less frequent ones with more, which will give much shorter messages that the simple 5-bits-for-everything coding. For example, the entropy given by the usual distribution of English is 4.219 bits per symbol, so we can encode common symbols like 'e' with perhaps 1 bit, and uncommon symbols like 'q' with 5 or 6 bits, an on average we use less than 5 bits per symbol. If we use more cunning coding schemes, for example ones that take into account digram and trigram frequencies, we can get this average down to a little over 2 bits per symbol by using short codes for common two and three symbol groups.

Also, notably, your title is backwards, Shannon's Entropy is a measure of information, not the other way around. It is not the only one possible, however Shannon argues that it is the most natural and intuitive.

The full extent of Shannon's (seminal) work on information theory is too large to encompass in this format, but there is plenty of further reading. The wikipedia entry on information theory is reasonably approachable, and the page on coding theory also adds something. For the real stuff of course, you can just read the paper in which Shannon invented information theory essentially out of whole cloth; "A Mathematical Theory of Communication"2.

*Footnotes*

1. This is not not suggest that Shannon was applying coding theory, he was inventing new ideas that would become large parts of coding theory.
2. Claude E. Shannon, "A Mathematical Theory of Communication", *The Bell System Technical Journal*, **27**:379-423,623-656, 1948.

# Answer
> 1 votes
There's a flaw in your premise. Information isn't said to be a measure of Shannon's entropy (you've got it backwards). Rather, Shannon's entropy is a measure of information. See https://en.wikipedia.org/wiki/Entropy\_%28information\_theory%29.

---
Tags: terminology, information-theory, entropy
---


# Question
Title: Disabeling interrupts to solve critical section issue on multiprocessor system
Assume I have a multicore system and a critical section.

I understand how disableling interrupts on a single core systems solves the critical section problem.

So assume I could disable interrupts on all cores atomically (Why is that not possible?). Why would that solve the problem?

As I understand, there would still be n processes running at the same time that may interfere with each other. They just wont be stopped until interrupts are enabled again.

Can somebody explain why that would (according to my professor) work?

# Answer
We are generally concerned about controlling concurrent access to kernel data structures. User-level processes don't have access to kernel data structures, so they can't do any harm from user space. The only risks are (1) if a user process does a syscall or causes a context switch to kernel mode, (2) if an interrupt arrives. (1) could be guarded by explicitly checking for a lock, or by other methods. (2) could be guarded by disabling interrupts, if you had a way to disable them on all cores.
> 1 votes

---
Tags: parallel-computing, mutual-exclusion, deadlocks
---


# Question
Title: Is a "tree" with $0$ vertices, $0$ edges or $1$ vertex, $0$ edges considered a valid tree?
For the following $2$ cases:

(1) $V = \emptyset, E = \emptyset $ (i.e. nothing at all)

(2) $V = \\{v\_0\\}, E = \emptyset $ (i.e. only 1 root node $v\_0$)

Are they considered a valid tree? It seems like different literature have different definitions.

I recall that I have read a data structures and algorithms book that defines "A tree is a set of nodes that either: is empty or has a designated node, called the root ...". According to this definition, (1) and (2) are both valid trees. I don't have the book on hand, but I am sure if you search the quoted sentence above in Google, you can get lots of results, as quite a lot of lecture notes follow this definition.

However, another definition of trees often met is defined in terms of graphs:

A tree is "a connected graph without a cycle".

Using this definition, my question is transformed to another question: "Is an empty graph a connected graph?" But the answer to the latter question is debatable according to here:

Is the empty graph connected?

My question is, which one is the more accepted definition?

# Answer
> 5 votes
Here are a few properties of trees which can be relevant:

1. A tree on $n$ vertices has $n-1$ edges. Works for (2) but not for (1).
2. A graph has no cycles iff it is a disjoint union of trees. Works for both (1) and (2), unless you require the decomposition into trees to be unique, in which case it works for (2) but not for (1).
3. A tree is either a single vertex or a bunch of disjoint trees connected to a common vertex. Works for (2) but not for (1).

These examples suggest that the commonsense definition of tree should include (2) but not (1). Indeed, oftentimes it seems that the graph on no vertices is a pointless concept; see the classical discussion of Harary and Read, who present arguments for both sides of the issue.

Practically speaking, you should probably assume that (1) is not a legal graph, unless it makes sense in your application, and then you should explicitly mention the fact.

---
Tags: graphs, terminology, trees
---


# Question
Title: Shortest possible comparison sequence to determine order of elements
Supposed you have $\langle a\_1,a\_2,a\_3,a\_4,a\_5\rangle$ = $\langle 6,16,13,9,6\rangle$, how would you find a shortest possible sequence of comparisons that determines the order of elements?

# Answer
## It is necessary and sufficient to do $n-1$ comparisons.

You just order indices according to the order of corresponding values, noting equalities.

If you choose increasing order, that gives for the example: 1 = 5 \< 4 \< 3 \< 2

Then you chose the sequence of comparisons tests that tests precisely these equalities or inequalities. And that sequence is precisely exactly what you need to make a decision regarding the order. It uses $n-1$ comparisons (i.e., $n-1$ comparisons are sufficient), but it can be proved that less would not be enough (so that $n-1$ comparisons are necessary). Hence the sequence of tests is optimal, i.e. shortest.

The proof that $n-1$ comparisons are necessary can be done by induction on $n$.

It is clearly true for $n=1$ and for $n=2$. In the latter case, the only way to order the two elements is to compare them.

Now we only need the following lemma.

*Lemma*: If $n$ elements can always be ordered with $m$ comparisons, then $n-1$ elements can always be ordered with $m-1$ comparisons.

If we consider $n-1$ elements, there is an integer $a$ that is greater than all of them. Then consider the problem of ordering all the same elements with $a$ included. This can be done with $m$ comparisons by hypothesis. At least one of these comparisons must be with $a$, since otherwise we could get the same order with $a$ as greatest element, even if we had chosen $a$ smallest. The value of $a$ has to be tested at least once.

But this comparison is irrelevant for ordering the initial $n-1$ elements, since it involves only one of them, So the proper ordering of these $n-1$ elements can be achieved with at most $m-1$ tests.

Using this lemma, we prove that if $n$ elements can be ordered with less than $n-1$ comparisons, then $2$ elements can be ordered without any comparison, which is false. Hence $n-1$ comparisons are necessary.
> 1 votes

---
Tags: algorithms, sorting
---


# Question
Title: What data size is sent to and read from physical RAM?
When you have a cache mis, you need to fetch a block from RAM. If said block is 64 bytes big, do you need to have buses that are 512 bits (= 64 bytes) wide to transfer data from the RAM to the cache? And when writing to RAM do you write to the whole 64 byte block?

# Answer
There is no requirement that a transfer between memory and cache use one line per bit. In fact, DDR3 DRAM uses a burst length of eight, meaning that eight bits are transferred per line in four cycles at double data rate. (DDR3 supports burst chop of only four transfers, but this has the same timing constraints for a read following a read and a write following a write. Burst chop can reduce energy use and other DRAM ranks can use the memory channel during the inactive time.) By requiring burst transfers, memory chips can be made more cheaply while still providing high bandwidth.

The write interface to DRAM is likewise constrained. In addition, the modified nature of portions of cache smaller than a cache block is usually not tracked, so the cache would not know that it actually only needs to writeback part of the cache block. (Such constraints are not inherent in memory systems. Caches could track validity or cleanness at any granularity, at the cost of addition storage and complexity. Interfaces could be defined to support arbitrary sized transfers, including the use of mask bits to tell the memory chips to ignore specific data, but the complexity is generally not considered worthwhile.)

One advantage of a narrower interface is that synchronization of all the lines is easier, making it easier to produce an interface with a fast clock providing higher bandwidth with the same number of lines.

Note also that more than one memory channel can be implemented in a CPU. It is also possible to gang two or more memory channels together to form a single interface.
> 4 votes

---
Tags: computer-architecture
---