title: Algorithm for sorting with constraints

text:
# Question
Title: Algorithm for sorting with constraints
I've got 30 elements which has to be grouped/sorted into 10 ordered 3-tuple. There are several rules and constraints about grouping/sorting. For example: Element $A$ must not be in the same tuple same unit $B$. Element $C$ must not be right in front of element $A$, etc.

I am searching for an approximated algorithm:

1. We don't need to achieve the exact optimum
2. It is OK for some rules not to be satisfied, if it helps to fulfill more rules.

Do you know of any algorithm/proceeding that solve this problem or a similar one? I fear to solve it in an optimal way, you have to try out every possible solution-\> $2 ^ {30}$

**EDIT**: Sorry for the bad explanation. I am trying to make it a bit clearer: I got 30 elements for example: $\\{1,2,3,\ldots,30\\}$. I need to group them into 3-tuples so that i get something like: $(1,2,3)$, $(4,5,6)$,$\ldots$,$(28,29,30)$.

There are several constraints. For example:

* 1 cannot precede 2 in an ordered tuple, so, for instance $(1,2,3)$ is not a valid tuple.
* 5 must be together with 4.

Those constraints can be broken and its possible that there is no solution where all rules can be fulfilled.
An solution is considered as good if the amount of rules broken is "low".

Hope that makes it clearer and thanks for the help so far.

# Answer
> 1 votes
Just to let anyone know, who got a similiar problem. I found genetic algorithm as an solution to it.

1. Create a population by creating multiple individuals. This is done by setting the elements on a random spot in a vector.
2. Generating the fitness of the individuals by checking how many rules are broken. The fitness is reduced by 1 per rule broken.
3. Checking if the solution is acceptable(Either fitness = 0 or termination criteria satisfied)
4. Doing tournament selection with suitable size(i chosed 3) on the population -\> Getting the tournament winner -\> Reproduct it, Mutate it or 1-Point-Crossover 2 of them and add it to the limbo. -\> Repeat 4. till the limbo got population size
5. Goto 3.

Hope you get the idea of it. Thanks for the comments on the original question. If you got any question, feel free to ask.

# Answer
> 2 votes
The question of whether we can solve this problem without violating any rules is a set cover problem.

In particular, the universe is $U=\\{1,2,\dots,30\\}$, and each possible tuple $t\_i$ that follows all the rules corresponds to a set $S\_i \subseteq U$. In this way, we get many sets $S\_1,S\_2,\dots,S\_n$. We want to know whether there is some 10 of these sets whose union is all of $U$. That's the set cover problem. There are well-known hardness results and approximation algorithms for the set cover problem.

---

Now let's introduce the opportunity to violate some of the rules. Associate to each tuple $t\_i$ a cost $c\_i$. If the tuple $t\_i$ follows all the rules, there is no cost for using that tuple: $c\_i=0$. If the tuple $t\_i$ violates some of the rules, we'll set $c\_i$ to denote the cost of those violations (for instance, if each rule that is violated costs \\$1, then $c\_i$ can be set accordingly). In this way we get a collection of sets $S\_1,S\_2,\dots,S\_n$ with associated costs $c\_1,c\_2,\dots,c\_n$ for each of them.

Now our goal is to find some 10 of those sets whose union is $U$, and where the sum of their costs is minimized.

This can be formulated as an integer linear program (ILP). In particular, we'll introduce $n$ integer variables $x\_i$; the intended meaning is that $x\_i=1$ means that $S\_i$ is one of the 10 sets that were selected, and $x\_i=0$ means $S\_i$ was not selected. Now we want to minimize

$$\sum\_i c\_i x\_i,$$

subject to the constraints

$$\sum\_{j \in S\_i} x\_i \ge 1 \text{ for each $j=1,2,\dots,30$}$$

(where the sum is over all $i$ such that $j \in S\_i$) and $0 \le x\_i \le 1$. Now you could throw any ILP solver at this problem and see what solution it turns up.

---
Tags: algorithms, sorting, randomized-algorithms, greedy-algorithms
---


title: Modified Pumping Lemma

text:
# Question
Title: Modified Pumping Lemma
How could we prove the following modified Pumping Lemma:Let the language L has an infinite number of words, then there are words $x,y,z \epsilon \Sigma ^{\*}$, so that $|xz|\leq |\Sigma\_{k}|$, and each word $xy^{(i)}z, i\geq0 $ is in L. Could you give me a hint how to begin?

# Answer
If we compare your version to the "standard" pumping lemma what do we see? that the only difference is that the standard lemma says

$$ |xy| \le p$$

while your lemma requires $$ |xz| \le p$$ where $p$ is the pumping length. You call it $|\Sigma\_k|$ but it's basically the same.

So, how do you prove the (standard) pumping lemma? The starting point is that if you process a string of length \> $|\Sigma\_k|$, then you must "hit" the same state twice. Then, $x$ is the prefix (the part of the string consumed until the first time you hit that state), $y$ is the middle part, consumed between the two times you hit that state, and $z$ is the leftovers, the part consumed after we hit that state twice.

Now to your question. Does it matter if $|xy|\le |\Sigma\_k|$ or $|xz| \le |\Sigma\_k|$?

**No.** In both cases we must hit a same state twice (this principle is called pigeonhole principle: we visit more states than the total number of states, so one we must visit one state twice).

From here, you should be able to complete the proof yourself.
> 2 votes

---
Tags: regular-languages
---


# Question
Title: Given the same set of nodes, why is it (generally) easier to find a Euler cycle than a Hamilton cycle?
To find a Hamilton cycle is a NPC problem, but Euler is not. Considering one can always transform the vertex as edge or vice versa conceptually. Then the vertex can be used to describe the information which originally edge does.

What properties make the Euler graph more easily to be resolved?

For example, in genome assembly problem, one can either consider a Kmer as vertex or edge(de bruijn graph), it's just two perspectives to look at the same thing. I think their should be additional or missing information between two kind of explanation.

# Answer
Suppose you are trying to find a Hamiltonian cycle on a graph.

You can solve this efficiently in the manner you describe (i.e. converting vertices into edges and then solving for an Euler path) if and only if the graph is a line graph.

There are a number of characterisations of line graphs.

For example, a graph is a line graph if and only if it does not contain any of these 9 graphs below as a subgraph:

An alternative characterisation is that a graph is a line graph if and only if you can partition the graph into cliques such that every vertex belongs to exactly two cliques.

This characterisation is perhaps more useful as you can apply Euler's proof to these cliques.
> 2 votes

# Answer
Euler proved the that a connected graph has a closed path traversing every edge if every vertex is of even degree, and he proved that a connected digraph has a closed path traversing every edge if every vertex has in-degree equalling out-degree. He gave an explicit construction in both cases. The construction can be easily systematized. Others have sped the algorithm up.
> 0 votes

---
Tags: graphs
---


title: IDDFS explained

text:
# Question
Title: IDDFS explained
I am trying to understand how IDDFS works by reading a wikipedia article on it. (If someone has a better literature on the subject, don't hesitate to post). Pseudocode is as follows:

```
IDDFS(root, goal)
{
  depth = 0
  for(i=1, i<10, i++)
  {
    DFS(limit=i)
  }
}

```

First of all, what is 10 here? Is it an arbitray number we choose? What is the connection between depth and "10"?

In the graph given as an example in that wikipedia article, in step 2 vistied nodes are:
2: A, B, D, F, C, G, E, F

Why is node F visited twice? Doesn't a DFS keep track of already visited nodes?

I am totally confused on this issue and any help is greatly appreciated.

# Answer
10 is indeed an arbitrary constant, which you would choose appropriate to your application. In fact, you might not choose it: in a chess program, for example, you'd be likely to decide how much time you want to give to the current position and then just search deeper and deeper until you've used up that time.

As is hinted below the diagram in the Wikipedia page, iterative deepening doesn't generally keep track of which nodes have been visited. You tend to use it for huge trees that aren't actually held in memory – going back to the chess example, you have a typical branching factor of 30-40 and you might want to search interesting lines down to depth 15-20. There's no way you can keep all of that in memory so, no, you can't remember which nodes have been visited. In DFS, you need to keep track of visited nodes so you don't end up in infinite loops when the graph contains cycles; with iterative deepening, the depth cut-off already avoids infinite loops. You trade the time wasted going round loops for the space saved by not storing the visited nodes. (Actually, in our running chess example, you'd typically have a hash table of positions that have already been seen. If the hash table already contains a sufficiently good evaluation of the current node, you use that, rather than exploring the tree more.)
> 3 votes

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


# Question
Title: Looking for a contex-free grammar for the following language
I want to derive a context free grammar for the following language on alphabet $\Sigma=\\{a,b\\}$:

$\qquad\displaystyle \\{ xax'yby'z \mid x,y,z\in\Sigma ^\*, |x|=|x'|, |y|=|y'|, |z|=|x|+|y|\\}$

I am convinced that this language is context-free because this is part of my proof to a theorem given in textbook, but haven't yet seen a context-free grammar for it.

# Answer
Hint: you want to measure size of $x$ and $y$, and still have the sum of the two in the end. so when you read them, you will need twice their size: one for $x'$, and one for $z$. Start with designing a PDA, it seems easier than a grammar. Then you can use a PDA-to-grammar translation to get the wanted grammar.
> 1 votes

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


title: Help reducing 3-SAT to 3-COLORING

text:
# Question
Title: Help reducing 3-SAT to 3-COLORING
I am working on showing that 3-colorability is NP-complete. I read a few articles and walkthroughs on this but none are really clicking. I get to this part

> "Then for every variable xi that appears in the instance of Satisfiability, we connect a vertex xi to a vertex xi, and we connect both xi and xi to red. This is illustrated below for a case where there are (only) 3 variables."

I think what they mean is something like this:

```
x1----x1*     x2----x2*      x3----x3*
 \   /         \   /          \   /
  \ /           \ /            \ /
   R             R              R

```

But my question is, what exactly is this step doing?

With a little bit more thought, is this step just showing that given xi to be one color, then xi\* has to be another, but also cannot be R, as they are both connected to it?

# Answer
I believe the goal of this construction is to try to assign true or false to each variable. The color assigned to x will determine whether it's true or false, and there's an edge from x to ¬x to ensure that each variable and its negation get different values. The edge from each variable to R ensures that there are only two possible colors that can be assigned to x, one of which means true and one of which meand false.

Hope this helps!
> 8 votes

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


# Question
Title: Fast hashing: combination of different techniques to identify changes in a file?
I want to create a fast way to detect whether a file might or might not be the same. For almost 100% sureness I would use an existing hash algorithm, e.g. SHA256. However, the files are expected to be huge video files with several GB, so calculating the SHA256 hash could take some time, especially over the network.

Therefore I want to combine different other techniques:

* file size: if the file size has changed, the content has changed (sure)
* head / tail hash
* random hash

The latter 2 are part of my question:

My guess would be that in the header there are things like:

* frame rates (e.g. Videos)
* resolution (e.g. Videos, Images)
* (file) length (e.g. in frames, pixels etc.)
* last change date (e.g. Word documents, not specifically Videos)

Why I consider checking the tail is:

* MP3 has the tag information there
* EXIF adds custom data at the end if I'm right

Random hashes would select e.g. 126 regions at random positions in the file with a specific length, e.g. 64 kB and create a hash for them. Of course I remember the offsets for later comparison. All in all I would use (1+126+1)\*64 kB of data for my hash, so I need to read only 8 MB instead of several GB to get the hash.

Maybe it's more a Math question now, but: **how likely is it to detect a change using the combination of file size, head, tail and random data to generate this quick hash sum?**

I assume that the files are always legal files. There's no benefit in manipulating single bytes. The user would use a normal video editing tool to change the files.

**UPDATE**: I unaccepted this answer which came from Crypto.StackExchange. I agree that my proposal is not cryptographic and not intended to be secure. I also agree that CRCing a file is fast, but in my case I really need a hash - I'll explain why:

* My application is expected to save bookmarks in videos. My database is expected to save the video hash and the bookmarks.
* Users sometimes move or rename files. My program will notice that a file does no longer exist, but will not delete the bookmarks from the database. Instead, when the same video is (accidentally) played again, I want to recognize that it's (probably) the same file.
* Users are expected to save files on network drives (NAS) and stream videos. Those are dumb storages. I cannot install a server component. And they might be quite slow, so I really don't want the full hash. Calculating a full hash on a 3 GB file takes at least 5 minutes @ 10 MB/s, no matter how fast the hashing algorithm is.
* If the user has edited the file, I somehow hope that the hash won't match any more, because otherwise I would display wrong bookmarks.

I'd be ok with a **~80% chance** of having the correct bookmarks. How many hash pieces should I put together and where in the file would that be?

# Answer
> 8 votes
There are two sides to your coin:

1. if you want to do it secure, you will need to use a cryptographically secure hash like SHA256 (crypto-hashes are meant to be fast, but tend to be a bit slow due to security constraints),
2. things like CRCs are definitely quicker, but will never be able to offer the same kind of security (especially when we’re talking about .

### Option 1: CRCs — Doing it quickly at the price of security:

If you're just after the detection of changes, go for a checksum instead of a hash. That's what checksums were made for: quickly detecting changes in a file or data-stream. But keep in mind that *CRC was designed to prevent transmission errors, not malicious action!*

Practically, CRC32 is the most obvious candidate (but even an additive CRC8 would do the job if you only want to detect if something has changed and don't expect anything else than that from the CRC.)

### Option 2: Beyond CRCs — Doing it rather quickly while enhancing change-detection:

Other valid options (looking at@poncho's comment) are indeed to simply check the *last-mod* timestamp.

Or, you combine both (to prevent bottlenecks), using something like this pseudo-code shows:

```
if(LastMod != knownLastMod) { CreateNewCRCandCompare(FileName, knownCRC) };

```

But does this offer any real security? No. Same goes for your…

> Why I consider checking the tail is:
> \- MP3 has the tag information there
> \- EXIF adds custom data at the end if I'm right

Again, it depends on how much security you expect. You have to realize that an adversary will surely manipulate the file to keep (or copy-and-paste) any old ID3 and EXIF data… as anyone (with appropriate RW file-access rights) can modify that. Same goes for the Last-Modification timestamp, frame rates, resolution, last change date, and even the (file) length. Depending on that “additional” and “modifiable” data — which can be modified and removed by anyone with enough file-access rights — would introduce a security flaw.

But you do expect security, don't you? After all, that's the reason why you're thinking about all this in the first place. Well, then there is not way around using crypto-secure hashes…

### Option 3: Cryptographically Secure Hashes — Doing it securely at the price of speed:

If you expect real security, you will have to rely on hashing; to be more precise: cryptographically secure hashing (using a hash which is not known to produce collisions). It takes time (a few microsecs per MB) but it's worth it.

### My 2 (personal) cents:

Try to live with the fact that hashing costs time and hash the whole files with a *cryptographically secure* hash. Because, when stuff starts hitting the fan… you're better off being slow, instead of being sorry.

**EDIT based on your EDIT…**

If cryptographic security isn’t your main focus, you could look at MD5 or SHA1. Both MD5 and SHA1 are “cryptographically broken” because collisions have been detected… yet for the change-detection purposes you describe (especially after your EDIT), the likely-ness of hitting such a collision should be minimal enough.

Looking at everything again (including your EDIT), I personally would most probably use MD5, because it offers a usable collision resistance (for change-detection purposes) while still being fast enough to completely hash multi-gigabyte files.

If that still doesn’t satisfy you in a “speed” sense or if your hardware resources are really *that* limited, you have to try to balance collision-resistance/change-detection with speed. Meaning…

Take the individual timestamp, the individual filename, and hash the header (length depends on media type and used file format) as well as a good chunk from the middle and a good chunk of the tail (= file end). Combine those 5 and you should be able to roughly filter out most

> I'd be ok with a ~80% chance of having the correct bookmarks. How many hash pieces should I put together and where in the file would that be?

That’s more of a personal opinion, as it depends on a whole truckload of details (media type, file format, available resources, expected change-detection ratio, file similarity, etc.) so will have to balance that out yourself depending on your personal expectations, your implementations, and local results due to hardware and/or software bottlenecks.

Let me try to provide you with some guidance nevertheless:

If hashing the complete file isn’t an option for whatever reasons, I would – at least – take: the header (and maybe a few KBs more), a good chunk from the middle (at least the size of the “header & co.” part), and a good chunk from the file end (again, at least the size of the “header & co.” part).

The more resources you can invest (or are willing to invest), the more chunks you can take and/or the bigger those chunks can be. If you think your resources/feel/whatever still offers room for more, increase the *size* of the chunks you hash and/or increase the *number* of chunks you hash.

Increasing the number of chunks is easy: as all you need to do is to take care of an equal distribution (by dividing the filesize accordingly, resulting in same-size chunks you extract from equally-spaced parts over the whole file-length).

And if you’re asking yourself “Why equally distributed and not random chunk-positions?”, let me simply note that picking random chunk positions might practically render your change-detection efforts void since it incorporates the risk of skipping some important parts media where you would normally detect the chances you are aiming to detect. Choosing an equal distribution is – simply said – more neutral.

# Answer
> 5 votes
## Shortcuts

If you have multiple files and you want to detect changes to files, use file size and last modification timestamp.

It is possible that operating system you use provides facilities to detect file changes, for example Linux allows to get notification of changes to directories.

## Full file processing

If you need to read actual contents of files to check if files have changed, go with actual cryptographic hash. CRC has significant potential of giving a false negative. SHA-256 can be quite good, but actually, SHA-512 is faster on many modern platforms.

If you have many CPU cores, it could be useful to calculate different hashes for different parts of the file or use hash tree to parallelize the processing.

The reason for suggesting proper hash is that once you go to actual file data, the cryptographic processing will not be too much, instead there will be a lot of other slower things, typically e.g. disk I/O or sending and receiving network packets.

Note: For (at least) small files it is also possible to store entire file contents, and do comparison of the contents instead of hash.

Note 2: If you are very tight on storage, CRC or truncated cryptographic hash could be good choice. CRC32 takes 4 bytes per file, and SHA-256 is 32 bytes. Small tags 4 bytes are not able to protect against malicious attempts to hide edits.

## Partial file processing

In most cases I would recommend using just the full file processing.

> Maybe it's more a Math question now, but: how likely is it to detect a change using the combination of file size, head, tail and random data to generate this quick hash sum?

For picture files it is common to make small edits, like remove red eye, add mustache or horns, etc. These edits in JPG format would occasionally not affect file size (with editing program which is able to make changes to JPG with recompressing only altered areas) or one of other attributes you mention.

File modification time would usually be affected though.

Considering video files: many video formats generate constant bit rate. For constant bit rate file, if some frames in the middle are altered, it'll also not appear in file size, head or tail. Removing or adding frames will almost always result in difference in size.

So I see it entirely possible that field get changes without it getting detected.

It is very hard to estimate probability edits are detected with this scheme, but there are common usage scenarios for videos and images which **are not** properly detected.

---
Tags: hash, performance
---


# Question
Title: Problems that are NP but polynomial on graphs of bounded treewidth
I *heard* here that the Hamiltonian cycle problem is polynomial on graphs of bounded treewidth.

I am interested in examples/references to different problems which is essentially hard but having polynomial complexity on graphs of bounded treewidth.

# Answer
> 8 votes
There are probably thousands of examples; there's a short list at ISGCI; the Wikipedia article has plenty of links. Search for "bounded treewidth" and "parameterized complexity treewidth" for many, many more.

Essentially, the problems become easy on graphs of bounded treewidth because:

1. Although it's NP-complete to determine if a graph has treewidth at most $k$ \[1\], there is, for every $k$ a linear-time algorithm to compute a tree decomposition of any graph that does actually have treewidth $k$ \[2\].
2. Once you have the tree decomposition, you can solve many problems by dynamic programming.

A simple example, which doesn't even use dynamic programming, is the Clique problem. Any clique of a graph must be contained completely in some node of the tree decomposition. That means that a graph of treewidth $k$ can have no clique of size greater than $k+1$ and, to find a clique of size at most $k+1$, you just have to see if each node of the decomposition contains the clique you're looking for. That can be done in linear time if $k$ is a fixed constant, since you're just checking for cliques in $O(n)$ graphs that each have at most $k+1$ vertices.

For a more complicated example, suppose you want to know if a graph $G$ of treewidth 4 is 3-colourable. First, compute the tree decomposition. Each vertex of the tree corresponds to a subgraph of at most 5 vertices of $G$. For each leaf of the tree, compute by brute force all 3-colourings of the corresponding subgraphs. This is in polynomial time because there are at most $n$ leaves, each corresponds to a subgraph with at most 5 vertices and there are at most $3^5=243$ 3-colourings of any such subgraph. Now, for each vertex $v$ of the tree that's adjacent to a leaf, enumerate all the 3-colourings that are compatible with possible colourings of the leaves adjacent to $v$. (That is, the 3-colourings of the subgraph corresponding to $v$ that can be extended to a 3-colouring of the graph corresponding to $v$ and all its adjacent leaves.) At this point, you can forget about the colourings of the leaves, since everything you need to know about them is now encoded in the distance-1 vertices. Now, iterate up the tree. You can imagine doing something similar for Hamiltonian path, constructing a path through the whole tree by joining up paths in the subtrees; that's more complicated.

---

\[1\] Arnborg, Corneil, and Proskurowski, "Complexity of finding embeddings in a k-tree"., SIAM Journal on Matrix Analysis and Applications 8(2): 277–284, 1987. DOI.

\[2\] Bodlaender, "A linear time algorithm for finding tree-decompositions of small treewidth", SIAM Journal on Computing 25 (6): 1305–1317, 1996. DOI.

# Answer
> 5 votes
Typically, for many "local problems" such as $\mathsf{Vertex Cover}$ or $\mathsf{IndependentSet}$ (meaning a solution can be verified by checking the neighborhood of each vertex), standard dynamic programming methods run in $c^{\textbf{tw}}|V|^{O(1)}$ time, where $\textbf{tw}$ is the treewidth of the input graph, and $c$ is some (small) constant. For many of these problems, we have matching upper and lower bounds for the running time of the optimal solution, assuming the so-called Strong Exponential Time Hypothesis (SETH).

In some sense, problems with some "global constraint" (like connectivity) appear harder. For such problems, the typical DP algorithm has to consider all the ways in which the solution can traverse the corresponding separator of the tree decomposition, that is $\Omega(s^s)$, where $s$ is the size of the separator. For more, you could look at the FOCS'11 paper of Cygan et al., arXiv version here. They consider Monte Carlo algorithms for problems with global constraints. There is subsequent work in this direction that investigates the "need" for randomness.

You could also have a look at Chapter 5 of Fomin, Fedor V., and Dieter Kratsch. Exact exponential algorithms. Springer, 2010.

# Answer
> 4 votes
Perhaps you could start with:

H. Bodlaender and A. Koster, Combinatorial Optimization on Graphs of Bounded Treewidth, The Computer Journal 51 (3), 255-269, 2008.

Found that reference under "Resources" from here.

# Answer
> 1 votes
Here is a recent study of this phenomenon of treewidth limiting the complexity of the problem and moving it into P from the point-of-view of SAT instance (hardness). This might underlie a larger framework to help understand the simplification across other NP-complete problems (via reductions to SAT).

Strong Backdoors to Bounded Treewidth SAT Gaspers/Szeider 2012

> Decomposability can be considered in terms of the treewidth of a graph that is associated with the given CNF formula, for instance by considering clauses and variables as vertices of the graph, and making a variable adjacent with all the clauses it appears in. On the other hand, a strong backdoor set of a CNF formula is a set of variables such that each possible partial assignment to this set moves the formula into a fixed class for which (#)SAT can be solved in polynomial time. In this paper we combine the two above approaches. In particular, we study the algorithmic question of finding a small strong backdoor set into the class W\_t of CNF formulas whose associated graphs have treewidth at most t.

---
Tags: complexity-theory, graphs, reference-request, np, polynomial-time
---


title: Is this NP-hard? I cannot prove it.

text:
# Question
Title: Is this NP-hard? I cannot prove it.
I have a problem and I guess it NP-hard, but I cannot prove it.

Here is a layer graph, where layer 0 is the hignest layer and layer L the lowest.

there are some directed edge between layers, where an edge (A, B) indicates that node A can \[cover\] node B. And when A can cover B, every node on any path from A to B can cover B, B can cover itself.

Finally here comes a set of node S. I need to choose another set of node ANS, and ensure that for each node q in S, there exists a node p in ANS and p covers q.

For every node there is a cost, and I need to make the total cost of set ANS minimal.

Is this a NP-hard problem? I think so but I cannot prove it.

Could you help me?

Thank you very much.

# Answer
> 6 votes
Yes this problem is definitely NP hard. I am posting this answer since you require proof.

If you follow this link http://en.wikipedia.org/wiki/Set\_cover\_problem, it says that the optimization version of minimal set cover problem is NP-Hard.

**The problem in the link:**

> Given a set of elements {1,2,...,m} (called the universe) and a set S of n sets whose union equals the universe, the set cover problem is to identify the smallest subset of S whose union equals the universe. For example, consider the universe U = {1, 2, 3, 4, 5} and the set of sets S = {{1, 2, 3}, {2, 4}, {3, 4}, {4, 5}}. Clearly the union of S is U. However, we can cover all of the elements with the following, smaller number of sets: {{1, 2, 3}, {4, 5}}

You can relate this to your problem as follows:

S is the set of nodes that cover at least one node in your input set. This can be found by conducting a DFS on the nodes of input set with the direction of edges reversed.

Now the problem described in the link is a special case of your problem, where the cost of each node is equal and you just want to minimize the number of nodes (sets).

Hence your problem is even more difficult to solve in the general case and hence it is NP Hard.

---
Tags: graphs, np
---


# Question
Title: Does types being terms imply your dependend theory is considered polymorphic?
In the introduction of the book by B.Jacobs, "Categorical Logic and Type Theory" (it's online here), he classifies type systems into three general flavours: Simply typed ones, depended typed (term depended types) and polymorphic types (type depended types). He says also there are also mix types.

Now if you start out with a dependently types theory and introduce transitive universes, hence forcing types on the level of terms, are you automatically speaking of a polymorphic type system then?

# Answer
These three “flavors” are usually presented as the lambda cube. They aren't really flavors but properties that can be combined independently, so there are not $3$ but $2^3 = 8$ flavors. In fact you could go as high as $4$ properties yielding $16$ flavors:

* terms depending on terms, i.e. functional languages (e.g. $f : x \mapsto x+2$);
* terms depending on types, i.e. polymorphism (e.g. $\mathrm{head} : \[X\] \rightarrow X$);
* types depending on types, i.e. type operators (e.g. $\mathrm{list} : X \mapsto \[X\]$);
* types depending on terms, i.e. dependent types (e.g. $\mathrm{array(int)} : n \mapsto \mathrm{int}^n$).

Theories without lambda abstraction tend to be less interesting and do a bad job of encoding most programming languages, so they're generally left out.

If you introduce transitive universes, then having types depending on terms automatically gives you types depending on higher-order terms, i.e. types. The Barendregt cube tends to collapse when terms and types are collapsed. However this doesn't necessarily give you all the polymorphism you want. The Barendregt cube is a classification; it doesn't reflect all the properties of the language. In particular, polymorphism can be more or less explicit, requiring you to thread type arguments down to every function, or not.

I think the right way to put it is that you're automatically speaking of a type system that can encode a polymorphic type system, but not necessarily give it to you the way you want.
> 3 votes

---
Tags: type-theory, dependent-types
---


# Question
Title: When describing a CS paper, can it be assumed that the meaning of "tick" is known?
I thinkt this question fits better here than on english.stackexchange.

When describing a figure in a computer science paper, is it safe to use "tick" meaning "tick mark"?

Examples:
`... (see the thick line right of tick "17")` meaning `tick mark "17"`
or `... increase at tick "1e+02"` `... increase at tick mark "1e+02"`.

# Answer
Yes, if by tick you mean

.

No, if you mean

.
> 8 votes

# Answer
I've never heard those marks on the axes referred to as "ticks", though Wikipedia agrees with your usage. Since Dave Clarke also didn't realise that's what you're talking about, I suspect that at least a sizeable minority of people aren't familiar with the term.

Why do you need to talk about the marks on the axes at all? Instead of saying "increase at tick mark '1e+02'" just say "increase at $x=100$" or whatever the variable is on that axis. (Also, it's silly to use the notation "1e+02" for such a simple concept as 100.) Your writing will be easier to understand if you talk about the data, rather than talking about the precise details of how you chose to represent it.
> 10 votes

---
Tags: terminology
---


# Question
Title: Non-termination of types in Martin-Löf's Type:Type?
In the pre-history of dependent type theory, Per Martin Löf introduced a calculus that is in some sense the simplest dependent type theory and the most general form of impredicative polymorphism. It is often referred to as ***Type:Type*** because the kind ***Type*** is itself of type ***Type***. Unfortunately, it is inconsistent as a logic. This was discovered by Girard in his famous dissertation \[1\], who managed to express the Burali-Forti paradox in ***Type:Type***. Various people have analysed, generalised and simplified Girard's analysis, see e.g. \[2, 3\]. This analysis seems to involve showing that non-terminating terms can be typed.

I have a question about non-termination: do we get non-normalisation ***at the level of types***? By that I mean, is there a type $T$ such that the reduction relation $\rightarrow$ used, explicitly or implicitly, to define equality of types, gives rise to an infinite reduction sequence $$ T \rightarrow T' \rightarrow T'' \rightarrow \cdots? $$

\[1\] J.-Y.. Girard, Une extension de l'interpretation fonctionelle de Gödel a l'analyse.

\[2\] T. Coquand, A New Paradox in Type Theory.

\[3\] A. J. C. Hurkens, A Simplification of Girard's Paradox.

# Answer
Short answer: yes.

Long answer: For $\mathrm{Type}:\mathrm{Type}$, non-termination at the type level is trivial. You can take a constant $X:\mathrm{False}\rightarrow \mathrm{Type}$. Then if you take the inconsistent term $\bot : \mathrm{False}$ you have $$ X\ \bot : \mathrm{Type}$$ Which is non-terminating at the type level. You might complain that this has a *head normal form*, which isn't what usually leads to inconsistency in type theory. In this case you can remember that $$ \mathrm{False}\equiv \forall X.\ X$$ and so $$ \bot\ \mathrm{Type}:\mathrm{Type}$$

Which has no head-normal form. In general, in this system the types and terms are so intertwined that the non-termination always seeps at the type level.

However, there is another system, called $U^-$, also described by Girard in his thesis, which was discovered to be inconsistent by Coquand (A New Paradox in Type Theory). *This* system is terminating at the type level, as it only has $\mathrm{system}\ F$ types at the *kind* level, and we know that terms are normalizing in that system (also a result of Girard!).

This means that non-termination at the type level is **not necessary** for having an inconsistent pure type system (a fact that I found out somewhat painfully after having proven an open question while depending on this fact).
> 6 votes

---
Tags: type-theory, functional-programming, dependent-types, curry-howard
---


# Question
Title: Master theorem for $T(n) = 2T(n/2) + n^{2}\log n$
Would I use the third case of the Master Theorem for the recurrence equation $T(n) = 2T(n/2) + n^{2}\log n$?

The condition given for the third case by Wikipedia is $f(n) = \Theta(n^c)$ when $c \> \log\_{b}a$.

# Answer
Yes and no. The form of the Master Theorem given on Wikipedia is a bit more restrictive than a fuller version of the theorem, essentially limiting itself to the cases where $f(n)$ is a polynomial.

In this case, where $f(n) \notin \Theta(n^{c})$ for any $c$ (though we do have $f(n) \in \Omega(n^{2})$ and $f(n) \in O(n^{2+\varepsilon})$ for any $\varepsilon \> 0$), the condition given on Wikipedia is insufficient.

A more useful (but slightly mathematically harder to work with, sometimes) formulation can be found in Cormen et al.'s "Introduction to Algorithms", or in this convenient worksheet from MIT.

The third case in this version is now

> If $$ f(n) \in \Omega(n^{\log\_{b}(a)+\varepsilon}) \text{ with } \varepsilon \> 0 $$ where $f(n)$ also has to satisfy a "regularity condition": $$ a f(\frac{n}{b}) \leq cf(n) \text{ for some } c\>1 \text{ and } n \text{ large enough} $$ then $$ T(n) \in \Theta(f(n)) $$

For the recurrence $T(n) = 2T(\frac{n}{2})+n^{2}\log n$, we have $\log\_{b}a = 1$, so we can pick any $\varepsilon \in (0,1\]$ (say for the sake of argument we pick $\varepsilon = 1$) and we have $f(n) \in \Omega(n^{1+\varepsilon}) = \Omega(n^{2})$.

Thus we can conclude $T(n) \in \Theta(n^{2}\log n)$.

In this case we don't need to worry too much about the regularity condition as $n^{2}\log n$ is well behaved - the condition is there to stop tricky things like the ones mentioned in the Wikipedia article, such as $f(n)=n\cdot(2-\cos n)$.
> 3 votes

---
Tags: recurrence-relation, master-theorem
---


title: all pairs shortest path using Dijkstra

text:
# Question
Title: all pairs shortest path using Dijkstra
So, I have a list of cities (A, B, C, etc) with weighted edges (two-way, undirected) between them with a list of cities that already have a store.

My task is to place a one new store at either A, B, C, etc so that I minimize the travel distance from any city to a store.

So my head is thinking

1. Perform Dijkstra's on every non-city vertex
2. Find the max distance among that node -\> all other nodes.
3. Store that distance associated with the store it originated from.

The problem I encountered was

The easiest example of A, B, and C cities with a store already existing at A, has roads of AB = 1, BC = 2.

Placing a store at B, would make C have to travel 2 units to the nearest store (at B). While placing a store at C, would make B have to travel 1 unit (since it can backtrack to A where a store is at).

This "backtracking" to other nodes is causing my mix-ups. Since I'm only iterating from the point of view of either City B or C. B's point of view thinks the max distance to a store is 2, while C does as well. (Even though C should find the max value of 1 unit).

# Answer
Hint: If you have all-pairs shortest-paths information, and if you are considering placing a store at city X, can you compute the max distance from any city to a store? You could now enumerate all possibilities for city X. What's the running time of this algorithm?

---

An alternative approach:

Hint: If you add a new source vertex and add edges from it to `_______`, and then use Dijkstra's algorithm to compute single-source shortest-paths starting from that source, does that give you any useful information that will help you? (You'll have to fill in the blank somehow.)
> 1 votes

---
Tags: algorithms
---


# Question
Title: Information capacity of Ternary-based system over Binary-based
Some researchers are trying to get a memory cell capable of having 3 states instead of 2.

1) How many memory cells, in principle and as a rough estimate, does a typical 1 megabyte memory chip has? is it 8\*1024 cells?

2) If you have N memory cells, each has x logical levels, what is the number of possible representations that we can get out of it? is it x^N representations?

Let's take Binary system as an example. Say we have 8\*1024 memory cells. We can store only one of the possible 2^N representations in each cell, so at the end the number of stored bits is just N=8\*1024. Now, for Ternary system, the gain is log2(3) ~ 1.58 times so we can store ~ 1.58 * 8 * 1024 "bits" or 8\*1024 "trits".

Correct? EDIT: sorry I meant 8\*1024\*1024.

# Answer
## Binary (two states)

1 Megabyte = 1,048,576 bytes = 8,388,608 bits = 8,388,608 cells. See https://en.wikipedia.org/wiki/Megabyte and https://en.wikipedia.org/wiki/Byte. 1 byte = 8 bits.

There are $2^{8,388,608}$ different possible values that can be stored in this much memory.

## Ternary (three states)

Now a cell can have 3 possible values. If we have 8,388,608 cells, each of which can have 3 possible values, then the entire memory can hold $3^{8,388,608}$ possible values. This is the equivalent of $\lg 3^{8,388,608} = 8,388,608 \times \lg 3 \approx 8,388,608 \times 1.58 \approx 13,295,629$ bits. This corresponds to $13,295,629/8 = 1,661,953$ bytes.

Therefore, this many ternary cells can store the same amount of data as 1,661,953 of ordinary binary cells (as 1,661,953 MB of memory).
> 1 votes

---
Tags: information-theory
---


# Question
Title: What do functions look like, if I stated out with the categoical model of my type theory?
I see how objects in a category stand for types, but where do I find the terms and more specifically the rules which tell me which of them are allowed? When I e.g. consider a Cartesian closed category as model of a type theory, how are term constructors represented?

I guess this is the same as asking how do I know or specify appropriately what the homsets of this category are, which I assume are in bijection with the lambda terms. The Curry–Howard–Lambek correspondence as presented at the end of the Wikipedia page Curry–Howard–Lambek correspondence presents all terms conventionally as in a type theory, but if I start out with a category, the model, then I must have specified them in a more algebraic sense.

And once given, does the model also represent $\beta$ and $\eta$ conversion? I actually read on the (quite too high level for me) nLab that morphisms relate to substitutions. Then I guess the lambda terms are somehow elements of the objects.

# Answer
> 8 votes
Your intuition is correct: terms are "somehow" elements of the objects. The only thing left is to figure out what elements in a category are. They cannot be literally elements because objects need not be sets (and more generally there may be no way to even "convert" an object to a set with a functor).

If I say "consider a mass point $p$ moving in $\mathbb{R}^3$" then you will immediately understand that $p$ is not actually an element of $\mathbb{R}^3$ but a *map* $\mathbb{R} \to \mathbb{R}^3$, i.e., the point is *parameterized* by time (which we take to be a real number). It is a general phenomenon that "entities" can be parameterized, and so they can be thought of as either *variable elements* or *maps*. For instance "temperature" may be thought of as a scalar field mapping the points of Earth's surface to real numbers, or it can be thought of as a real number which varies with position on the Earth.

In any case, this leads to the idea that the elements of an object $A$ in a category are simply all morphisms $B \to A$. When $B$ is the terminal object, we get the *global* (non-parameterized) elements, but in general we allow elements to be parameterized by any object, and so we call them *generalized elements*. One way to understand the Yoneda lemma is that an object in a category consists of its generalized elements.

You asked how to pass from a category to its internal type theory. Let me answer the opposite question first. Given a type theory, we can think of terms in context as the generalized elements of a type, while the closed terms are the global elements. But since generalized elements are the same thing as morphisms this tells us how to build a category out of a type theory: the morphisms are just terms in a context, quotiented by whatever equations the theory proves.

To go in the opposite direction, suppose we have a category $\mathcal{C}$ and we want to make a type theory out of it. As you said, we take the types to be the objects of $\mathcal{C}$. According to our view that "generalized elements are morphisms", the morphisms $f : A \to B$ ought to correspond to terms of type $B$ in context $A$. But we cannot just write $x : A \vdash f : B$ because there is no $x$ on the right-hand side. It would make more sense for $f$ to have the type $A \to B$, which is precisely what we do. For each morphism $f : A \to B$ we introduce a constant of type $A \to B$, which we also write as $f$. Then the correspondence is recovered: given $x : A$ there is a term $f\\, x : B$.

If our type theory does not have arrow types then we have to do things a bit differently. For each morphisms $f : A \to B$ in $\mathcal{C}$ we add a unary term constructor $f$ and the typing rule $$\frac{\Gamma \vdash e : A}{\Gamma \vdash f\\,e : B}.$$ Note that $f\\,e$ is just a syntactic form, namely application of the unary term constructor $f$ to the term $e$. It would make no sense to apply the morphims $f$ to the term $e$! A type theory consists not only of types and terms, but also of equations. Our category gives us some equations, too: if the morphism $h : A \to C$ is the composition of $f : A \to B$ and $g : B \to C$, then we get the equation $$x : A \vdash h \\, x =\_C g (f \\, x).$$ There are some further equations. For instance, if $A$ and $B$ are objects and $C$ is their product, then we need to relate the type $C$ with the product type $A \times B$. That is, in the category there are projections $\pi\_1 : C \to A$ and $\pi\_2 : C \to B$ and a pairing operation $\langle{-}, {-}\rangle$, while in type theory there are projections $\mathtt{fst} : A \times B \to A$ and $\mathtt{snd} : A \times B \to B$ and pairing $({-},{-})$ (where $A \times B$ is the formal product type). We need equations which relate these, but let me skip the technicalities.

The $\beta$ and $\eta$ reduction rules are validated by a cartesian closed category. The rules about product and function types correspond to various parts of the adjunction between cartesian products and exponentials.

In conclusion, it may seem strange that we take *all* morphisms in a category and make them into unary constructors of the corresponding type theory. If the category is very big that gives us a very large type theory which is not syntactic in any sense of the word syntactic. Just *free your mind and the rest will follow*.

---
Tags: lambda-calculus, type-theory, category-theory
---


# Question
Title: How to prove the NP-completeness of the ``Exact-3D-Matching`` problem by reducing the ``3-Partition`` problem to it?
**Background:** The `Exact-3D-Matching` problem is defined as follows (The definition is from Jeff's lecture note: Lecture 29: NP-Hard Problems. You can also refer to 3-dimensional matching):

> *Exact-3D-Matching:* Given a set $S$ and a collection of three-element subsets of $S$, called *triples*, is there a sub-collection of disjoint triples that exactly cover $S$?

The `3-Partition` problem is defined as (It is also from Lecture 29: NP-Hard Problems. You can also refer to 3-partition problem.):

> Given a set $S$ of $3n$ integers, can it be partitioned into $n$ disjoint three-element subsets, such that every subsets has exactly the same sum?

It is known that the `3-Partition` problem can be proved to be NP-complete by reducing the NP-complete `Exact-3D-Matching` problem to it. And the NP-completeness of the `Exact-3D-Matching` problem is proved by reducing the `3SAT` problem to it (both are given in the book Computers and Intractability: A Guide to the Theory of NP-Completeness).

**Problem:** My problem is:

> How to prove the NP-completeness of the `Exact-3D-Matching` problem by reducing the `3-Partition` problem to it?

I have found neither papers nor lecture notes on it.

# Answer
> 1 votes
I think this reduction should work:

Given a 3-PARTITION instance: $n$ integers $a\_1,\ldots,a\_{3n}$ and a target sum $B$; mark each integer with an unique identifier $\hat{a\_i}$; then build a collection of 3-elements subsets $C\_j = \\{ \hat{a}\_{i\_1}, \hat{a}\_{i\_2}, \hat{a}\_{i\_3} \\}$ such that $a\_{i\_1}+ a\_{i\_2}+ a\_{i\_3} = B$ and $i\_1 \neq i\_2 \neq i\_3$ (the collection has $O(n^3)$ elements).

The original 3-PARTITION problem has a solution if and only if there exist an EXACT-3D-MATCHING $C\_{j\_1}, \ldots, C\_{j\_n}$ that covers $S = \hat{a}\_{1}, \ldots, \hat{a}\_{3n}$.

For example given $A = \\{5,4,3,3,3,2,2,1,1\\}, B = 8$ we build: $S = \\{5a,4a,3a,3b,3c,2a,2b,1a,1b\\}$ and the collection of 3-elements subsets:

```
C1  = { 5a, 2a, 1a }
C2  = { 5a, 2a, 1b }
C3  = { 5a, 2b, 1a }
C4  = { 5a, 2b, 1b }
C5  = { 4a, 3a, 1a }
C6  = { 4a, 3a, 1b }
C7  = { 4a, 3b, 1a }
C8  = { 4a, 3b, 1b }
C9  = { 4a, 3c, 1a }
C10 = { 4a, 3c, 1b }
C11 = { 4a, 2a, 2b }
C12 = { 3a, 3b, 2a }
C13 = { 3a, 3b, 2b }
C14 = { 3a, 3c, 2a }
C15 = { 3a, 3c, 2b }
C16 = { 3b, 3c, 2a }
C17 = { 3b, 3c, 2b }

```

An Exact-3D-MATCHING is given by:

```
C1  = { 5a, 2a, 1a }
C6  = { 4a, 3a, 1b }
C16 = { 3b, 3c, 2b }

```

that also uniquely identifies a valid solution for the original 3-PARTITION problem.

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


# Question
Title: Selection Sort runtime in terms of Big O
I'm trying to understand why the sorting algorithm Selection Sort has asymptotic runtime in $O(n^2)$.

Looking at the math, the runtime is

$\qquad T(n) = (n-1) + (n-2) + \dots + 2 + 1$.

And this is stated to be equal to

$\qquad O(n^2)$.

However I just don't understand the intuition. I have tried several practical experiments for n=10 up to n=5000, and all point to that the time complexity of e.g. 5000 can never be greater T(5000) = 12.497.500 -- not T(5000) = 5000^2 = 25.000.000.

Now, I know that 5000 is not the same as infinity, but I just don't understand the intuition behind

$\qquad (n-1) + (n-2) + \dots + 2 + 1 = O(n^2)$.

Does someone have a great pedagogical explanation that my dim-witted mind can understand?

# Answer
> 5 votes
Remember what $O(n^2)$ means: it means that there is a constant $c$ such that, for large enough $n$, the number of steps is at most $cn^2$. The constant doesn't have to be $1$; in this case, it looks like the constant is about $\tfrac12$.

Why is $(n-1) + (n-2) + \dots + 2+1$ equal to $O(n^2)$? Because you're adding up $n-1$ numbers and the average of those numbers is half-way between the first one and the last one, i.e., $\tfrac12(1 + (n-1))$. So the total is $$(n-1)\times \tfrac12(1 + (n-1)) = \tfrac12(n^2-n).$$Plug in $n=5000$ and you get... \*drumroll\*... $12497500$.

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


# Question
Title: Multi-dimensional Neural Network for fingerprint matching
I want to use “Fingerprint matching using multi-dimensional ANN” by Rajesh Kumar and B.R. Deva Vikram \[content link\] for fingerprint identification. But I have a serious problem understanding what is a Multidimensional Artificial Neural Network.

I searched for keywords MDANN and Multidimensional ANN but I can't find anything. I also can't be sure what Kumar meant about a MDANN in his article. So far, the closest thing I can relate with Kumar's MDANN is Convolution Nets but I don't believe this is what he meant. Can anybody help me about understanding this type of ANN?

# Answer
Based on my skim of the paper, I suspect that this is just a standard neural network (in which the entire image is fed into the neural network as an input, one input line per pixel in the image), and they have invented a fancy-sounding name for a standard use of neural networks. You could of course contact the authors to ask them this question, but that's what it looks like to me.

To replicate their work, I suggest you read Section 5.1 very carefully and use the descriptions there to replicate their work.
> 1 votes

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


# Question
Title: Viterbi algorithm recursive justification
I have a question regarding recursion in Viterbi algorithm.

Define $\pi(k; u; v)$ which is the maximum probability for any sequence of length $k$, ending in the tag bigram $(u; v)$.

The base case if obvious $\pi(0,\*,\*)=1$

The general case.

$\pi(k,u,v) = max\_{w \in K\_{k-2} } \pi(k-1,w,u) \cdot q(v|w,u) \cdot e(x\_k|v)$

The author justifies the recursion as folllows:

> How can we justify this recurrence? Recall that $\pi(k, u, v)$ is the highest probability for any sequence $y\_{−1}...y\_k$ ending in the bigram $(u, v)$. Any such sequence must have $y\_{k−2} = w$ for some state $w$. The highest probability for any sequence of length $k − 1$ ending in the bigram $(w, u)$ is $\pi(k − 1, w, u)$, hence the highest probability for any sequence of length $k$ ending in the trigram $(w, u, v)$ must be $\pi(k − 1,w, u) \cdot q(v|w, u) \cdot e(x\_k |v)$

I do not understand why it's actually true, I think it's possible to reach $\pi(n,u, v)$ from any $(n-1,w, u)$ not actually the maximum one $\pi(n-1,w, u)$ just because $q(v|w, u) \cdot e(x\_k |v)$ might have a higher influence on the resulting $(n,u, v)$ than any $\pi(n-1,w, u)$.

I would appreciate if anyone could explain me why it's true.

# Answer
> 1 votes
The maximum is over the entire expression $\pi(k-1,w,u) \cdot q(v|w,u) \cdot e(x\_k|v)$, for exactly the same reason that is worrying you. Moreover, under your original interpretation, there is no reason to keep $\pi(k-1,w,u)$ for the non-optimal $w$. We are forced to store $\pi(k-1,w,u)$ for all $w$ exactly for the reason you mention.

---
Tags: algorithms, dynamic-programming, recursion, correctness-proof, hidden-markov-models
---


# Question
Title: Approximation algorithms for NP-complete problems
Given two NP NP-hard functional problems, A and B, one can find a reduction of A to B. Is it possible to find a reduction that would honour approximations? That is, if you have an approximation algorithm for B that yield approximate solutions within accuracy $\delta$, is it possible to reduce A to B in such a way that one would be able to derive an approximate solution of A within accuracy $\epsilon = \epsilon(\delta)$?

# Answer
It depends on the problems. Some NP-complete problems are in APX (can be approximated to some constant amount) and some are not. This shows that you cannot in general assume the existence of a transformation such as the one you mention; this is spelled out here.

A concept somewhat similar to what you mention is *APX-hardness*. First, some definitions. APX, as mentioned, is the class of problems approximable to some constant in polytime. PTAS is the class of problems which can be approximated arbitrarily well in polytime. A problem is APX-hard if there is a "PTAS reduction" (approximation-preserving reduction) from every problem in APX to that problem. One problem which is APX-hard is MAX-SAT.

A related definition is MaxSNP. This is a class of graph problems with the following property: there is a PTAS reduction from every problem in APX to some problem in MaxSNP.
> 6 votes

---
Tags: complexity-theory, reductions, approximation-algorithms
---


# Question
Title: How to make a Neural network understand that multiple inputs are related to the same entity?
Neural networks can have multiple inputs. But some times two or more of these inputs can often be related to a single entity.

E.g : Height and weight of a person to predict the probability of disease or price and Volume of a stock to predict it's value.

How can we make a neural network understand that two inputs are related to the same entity? Is there any efficient (or inefficient) way of '*tagging*' them together?

# Answer
It is not necessary to indicate this to the neural network (and not possible). This is not part of how neural networks are typically used -- or part of how other machine learning algorithms are used, either.

I confess I'm not clear on why you think it would make a difference, but it doesn't matter: there's no way (that I know of) to do that, and it's not something people normally do.
> 1 votes

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


# Question
Title: Find a diffrent minimal spanning tree for a graph
For my homework I have a problem that I can't solve and it makes me wonder about 2 different MST:

> Let $G=(V,E)$ be a graph that has a minimum spanning tree $T$.
>
> I want to find another minimum spanning tree $T'$ that has at least 1 different edge $e'$ such that the weight of $e'$ is differ from any weight of edges in $T$.

If $T'$ doesn't exist I can claim that every 2 different MST must have the same weight for each edge.

My intuition says that this claim is wrong but on the other hand I can't find example of $T'$ to contradict this claim.

# Answer
> 1 votes
You cannot find such a MST. Every two minimal spanning trees must have the same multiset of edge-weights. Actually you can find the proof in the link that Raphael added:

Do the minimum spanning trees of a weighted graph have the same number of edges with a given weight?

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


# Question
Title: Question about the undecidability of $A_{TM}$
You probably know this one (or at least a version of it).
Let $P$ be a program code, and $w$ be an input string.
Define $A\_{TM}=\left\\{(P,w)| P(w)=1\right\\}$.
Meaning: $A\_{TM}$ is the set of all ordered pairs $(P,w)$ s.t. $P$ accepts $w$.
$A\_{TM}$ is undecidable.

I just read the proof for it, that made me wonder about something.
The brief of the proof (by contradiction) looks something like this:
Suppose there exist $D\_{A\_{TM}}$ - a computer program that answers 'yes' if $(P,w)\in A\_{TM}$, and 'no' if $(P,w)\notin A\_{TM}$.
Let us consider the following program:

$Q(w):$
1. run $D\_{A\_{TM}}$ on $(w,w)$
2. if $D\_{A\_{TM}}$ returned 'yes', then return 'no'. if $D\_{A\_{TM}}$ returned 'no', return 'yes'.

Now running $Q(w);$ with the input $Q$, contradicts the existence of such $D\_{A\_{TM}}$

This is a brief, since I assume most of you already know this problem (and its proof).

Now what makes me wonder is this: when I looked at $A\_{TM}$, and needed to determine if it's decidable or not, the first thing that came to my mind when I tried to imagine a machine that accepts $A\_{TM}$, is how can machine like that handle inputs $(P,w)$ s.t. $P$ doesn't halt on $w$? How can it 'predicts', beforehand, that $P(w)$ goes to an infinite loop, without actually running $P$ on $w$?
That intuition, as it turns out, wasn't wrong.
The thing is: How come the proof, as clever as it is, has nothing to do with that fact?
You'd expect it to lean - and even in the slightest way - on that leverage, but instead, the proof looks like something that was taken from the realm of paradoxes.

Basically, what I'm asking is: why does this proof work?

# Answer
If you know what the program is doing, you can predict its outcome even without running it. For example, consider the following program.

```
INPUT: a polynomial P with integer coefficients
n = 0
while P(n) is different from zero:
  n = n + 1

```

This program halts if the input polynomial $P(x)$ has a non-negative integer root. It turns out that this problem is decidable - there is a clever shortcut that determines the outcome of the program. How can we rule out the existence of such shortcuts in general? The proof you describe is one clever way of doing that.
> 1 votes

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


# Question
Title: Redundant States During Removal of Null-Moves (Regular Expression to DFA)
I've had this little doubt bothering me since four semesters now, so I've come here to resolve it. Theoretical CS was probably not the right place to ask.

Coming to the question, my old coursebook (*Theory of Computer Science - Automata, Languages and Computation (Eastern Economy Edition)* by KLP Mishra) details the conversion of the regular expression -:

$(0 + 1)^\* (00 + 11)(0+1)^\*$

to a finite automaton. The book details the process as follows:

I am able to grasp the process uptil step (d). I do not understand how (e) was obtained, and there is no explanation given. I tried to convert (d) to (e) by removing null-moves, but I am not able to get (e) - I obtain a bunch of redundant states (extra initial and final states).

It is not possible to use the DFA minimization procedure to obtain (e) after the null-moves are deleted, simply because this isn't a DFA yet - it's still an NFA. Note that I've not shown the NFA to DFA conversion procedure, which was on the next page. Could someone point me in the right direction?

There are no steps given to obtain (e) from (d). That's what's confusing - I know I have to remove the null-moves but not how to get the neat and 'minimized' transition system given by (e).

# Answer
> 2 votes
*\[answer by UncleDolan originally embedded in the question post\]*

I believe I just solved the problem on trying it again. The strategy was to remove the nulls in the right sequence, not follow a random sequence of null-deletion. Following that, I had to remove **unreachable** and **redundant** states.

First, I state the algorithm used to remove null-moves as given in my coursebook.

For two vertices A and B with a null link from A to B,

1. **Duplicate** all the edges which are going outside from B, from A.
2. If A is an **initial state**, make B an initial state.
3. If B is a **final state**, make A a final state.
4. Remove the null link.

Now I'll go step-wise through the solution. I generated the images using Graphviz on Ubuntu.

1. First, I removed the null link between q5 and q1. q0-q5 and q2-q6 are risky at this time because I would be inadvertently duplicating the null links from q5-q1 and q6-qf.
2. Second, I removed the null link between q6 and qf. qf now becomes unreachable.
3. Third, I removed the null link between q2 and q6. q6 evidently becomes redundant.
4. Fourth, I removed the last null link between q0 and q5. q0 becomes redundant as we now have two initial states, both having (almost) the same moves.
5. I remove q0, q1 and qf for being either unreachable or redundant. The end result looks very close to (e) in the question.
6. I find that q2 could do q6's job without making any changes to the language. q6 is redundant as well. This is the final result.

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


# Question
Title: Can anyone provide me answer/guide on how to design a turing machine for this case?
I tried, but I could not design a turing machine for the following problem:

Turing machine that takes as input a tape containing a series of n 1s, where n \>= 0, terminated by an = sign. The Turing machine head is initially positioned on the leftmost 1. The end state should be a tape containing the input, followed by the reverse of the sequence of 0s and 1s that represents n in binary.

# Answer
One approach you could take would be to effectively reduce this to a machine that adds one to a binary number that is written left to right rather than right to left. Once you figure out that logic you'd just need to mark the end of the input and write a zero after that. Then for each 1 in the input, mark it and add one to the binary number found after the input.
> 1 votes

---
Tags: turing-machines
---


# Question
Title: how to solve NFA acceptance problem in polynomial time
I need to show that the language Anfa = {(A,w)| A is an nondeterministic finite automata that accepts w} can be decided in polynomial time. My problem is every solution that I think of requires exponential time.

I would appreciate any help, Thanks in advance..

# Answer
Hint (expanding on David Richerby's hint): As the NFA reads $w$, keep track of the set of states it could be in at any given time.
> 1 votes

---
Tags: time-complexity, finite-automata, nondeterminism, polynomial-time
---


# Question
Title: Environment detection - How to detect "city" versus "landscape" background environment in computer vision?
I'm searching for computer vision or machine learning algorithms/methods that are used to classify or differentiate two outdoor environments. Given an image with vehicles, I need to be able to detect whether the vehicles are in a natural open landscape (desert, in particular), or whether they're in the city.

I've searched but can't seem to find relevant work on this. Perhaps because I'm new at computer vision, I'm using the wrong search terms.

Any ideas? Is there any work (or related) available in this direction?

# Answer
Think of what different features the desert has compared to an urban environment. The desert is probably restricted the a limited set of colors/hues. It is limited to mostly smooth textures. It lacks "man-made" geometries such as straight lines from building edges etc.

So you should be able to differentiate between desert and urban environment by looking at the color components (both the number of colors and the variation), textures and the amount of prominent straight lines/edges in the environment.

By googling "image processing classify outdoor environment" I found the paper Automatic Classification of Outdoor Images by Region Matching which can be a good starting point for reading up on environment classification. They seem to base the classification mostly on color and texture features.

These are just general ideas but hopefully they can help you get started. Good luck.
> 3 votes

# Answer
Perhaps these can be helpful (see also their references):

Aditya Vailaya , Anil Jain , Hong Jiang Zhang, On Image Classification: City Images vs Landscapes (1998)

and the more recent:

Li Fei-fei, Pietro Perona, A Bayesian Hierarchical Model for Learning Natural Scene Categories (2005)
> 1 votes

# Answer
I would suggest you to use a training classifier. You train the system by feeding in what you want and then you can do template matching or histogram matching to get good results.
> 1 votes

# Answer
There are many possible different approaches, each one based on a different classification technique. The following list of commonly adopted techniques, is a starting point to get you started studying the underlying relevant theory:

Principal Component Analysis;

Neural networks (probabilistic, fuzzy logic based, back propagation based, self-organizing maps);

Support vector Machines;

Nonnegative Matrix Factorization;

Wavelets;

Fisher Discriminant Analysis.
> 0 votes

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


title: VC dimension and optimal mistake bound

text:
# Question
Title: VC dimension and optimal mistake bound
I have a question regarding optimal mistake bound for learning algorithm

There is a famous fact that $VC(C) \leq Opt(C)$,

where $C$ - set of learning concepts,

VC(C) \- VC dimension of C,

$Opt(C)$ - the smallest mistake bound (of the best learning algorithm) on the hardest learning concept $c \in C$ .

I don't understand why $VC(C) \leq Opt(C)$, in my opinion the notion of best algorithm $A$ is so vague that you cannot for sure say that $VC(C)$ is not more than $Opt(C)$

For example, $VC(line\ on\ the\ plane)$=3 , it means that $Opt(C) \geq 3$ in words it means for the hardest concept $c \in C$ (represented as a line on the plane) the number of mistakes of the best learning algorithm is more than 3.

Why the above fact is so strong?

# Answer
So this result pertains to the online mistake bound framework. I found a proof here in Shai Shalev-Shwartz's lecture notes. I'll give a rough sketch of it here for the sake of keeping things self contained.

One way to think of online learning is a game between the learner and an adversarial environment. The environment produces an example $x\_t$ at time $t$. The learner then outputs a label $\hat{y}\_t \in \\{-1,1\\}$. Finally the environment outputs the true label of $y\_t$ and the learner suffers a mistake if $\hat{y}\_t \neq y\_t$.

The thing to note for the above bound is that it doesn't matter if the environment switches the true hypothesis mid-game, provided the new hypothesis is consistent with all previous labelings. This is because it would be the same as selecting the new hypothesis in the first place.

Assume the learner is trying to learn some some finite hypothesis class $C$ over an instance space $\mathcal{X}$ with $\text{VCdim}(C) = d$. Let $X = \\{x\_1, \cdots, x\_d\\} \subseteq \mathcal{X}$ be a shattered set. At any time $1 \le t \le d$ the environment reveals $x\_t$ and the learner outputs $\hat{y}\_t$. The environment then selects a new hypothesis $c \in C$ such that $c(x\_t) = -\hat{y}\_t$ and $c(x\_i) = y\_i$ for $1 \le i \le t$. There will always exist such a hypothesis $c \in C$ since $X$ is shattered by $C$. So the learner makes at least $d$ mistakes. Since this argument was independent of the learning algorithm it follows that $$ \begin{align\*} \text{VCdim}(C) &\le \text{Opt}(C). \end{align\*} $$
> 3 votes

---
Tags: machine-learning, vc-dimension
---


# Question
Title: What is the job of Syntax Analyzer in a compiler?
What exactly is the job of a syntax analyzer? Suppose I have a mathematical expression. Is it true that the order of execution of the operations is found with the help of syntax analyzer?

Any example on exact jobs of Syntax Analyzer?

# Answer
> 7 votes
The syntax analyser has two main purposes.

* It checks if the program to be compiled is syntactically correct.
* It converts the program, which is given as a string of characters,
into an abstract syntax tree, which is a representation of the
program that is much easier to use for the code generator.

The second part is not really necessary as one could, in principle, generate code directly from the input string, but that would be painful, both in terms of speed of compilation, and complexity of the code generator.

# Answer
> 0 votes
The syntax analyser checks for the grammers or checks for the meaningfulness of your operation.. As you mentioned about mathematical expression, First it creates `PARSE TREE` of your expression.

Consider following example,

```
Answer=token1+token2;

```

So it will create parse tree of this expression as

```
                    =
                   / \
                  /   \
               Answer  +
                      / \
                     /   \
                  token1 token2

```

So here priority of operator also matters, so if you want to have a deeper knowledge, click here

---
Tags: compilers
---


# Question
Title: Dijkstra algorithm: equal number of shortest paths
If I had a Dijkstra graph with the number shortest paths from Node A to O being 1, would it be correct to say: **the equal number of shortest paths from A to O is 1 and not 0**, because that node is included as an 'equal shortest path'? I am really confused.

Here is an image to illustrate my question:

# Answer
Depends on how you define "equal number of shortest paths".

If we change the graph so that Q -\> O is 3, then we have two shortest paths from A to O, one via P and one via Q, both of distance 4.

Then there are 2 shortest paths with equal distances. This is what you mean by "equal number of shortest paths", correct?

Then, the question is, when there is just 1 shortest path as in the original graph, should we say "there is 1 shortest path with equal distance", or is it more correct to say "there is 0 shortest path with equal distance"?

Both are correct depending on how the question is phrased.

1. How many shortest paths are there in total that have equal distances?
2. How many additional paths are there that have distances equal to the given shortest path?

This is simply a wording problem and not so much a Technical Computer Science Shortest Path Algorithm problem.
> 2 votes

# Answer
There will be atleast one shortest path from source to destination. There can be multiple shortest paths from source to destination but Dijkstra will choose only one based on the nearest neighbors.

This will give you a good idea on how Dijkstra works.
> 1 votes

# Answer
As wookie said,You are right in your essence rather wrong in how you are presenting it.,

It would be more correct if you say "\**There is 1 shortest path from source to destination or There are 2 shortest path from source to destination* \*,rather than saying " *the equal number of shortest paths is 1"*

And therefore if you have more than one shortest path it *implicitly* means that the shortest paths are having equal *distances*.
> 1 votes

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


# Question
Title: In type systems, is there a name for SQL's way of cutting and combining record types into new types?
I'd like to have this feature in my application programming language (which these days, is Scala), but when I went to learn more about it on the internets, I realized I don't know the name of it. I'm talking about the ability to do this (in Scala-ish pseudocode):

```
// Define some types that correspond to table rows in relational DB
class User
   val id: Int
   val name: String
   val email: String
   val created: DateTime

class Comment
   val id: Int
   val text: String
   val userId: Int
   val created: DateTime

// Call a select/join query function
val list = select c.id, c.text, u.name
           from comments c join user u on c.userId = u.id ...

```

And then `list` gets a type of something like `List[R]` where `R` is an unnamed record type with properties `id`, `text`, `name`, or maybe `c.id`,`c.text`,`u.name`.

Some languages, like Scala, support you writing that select function so it returns a tuple type `(Int, String, String)`, but not a type with *named* fields.

Is there a name for that?

# Answer
I think what you are looking for is *type inference* for *record types*. Let me give you a bit of an overview on each of those; but those keywords should help you find a lot more on those topics.

---

*Type inference* means that you don't need to declare the type of everything. Instead, the compiler figures out the types where it can, from context. For instance if you write a function

```
function f(x,y):
    return (x+y)/2

```

the compiler can figure out that `f` is a function that accepts two `int`s and returns an `int`. (How? It knows that `2` is an `int`, and that both operands to the `/` operator must have the same type. Therefore, the type of `(x+y)` must be `int`. That in turn means that both `x` and `y` must have type `int`. And so on.)

You want type inference, so you don't need to explicitly declare the type of the result of the `select` and `join` operations.

---

A *record type* is basically just a fancy name for a struct.

A record is an object that has a list of fields; each field has a name and a type. For instance, to invent some example syntax: `{height: 69, weight: 152, name: "Bob"}` might be a record with three fields; if `r` is a variable holding this record, then you might be able to use syntax like `r.height` to access the `height` field.

You might notice that a record is a lot like a tuple, except that the elements of a tuple do not have names (you just access the first element, second element, third element, etc. of a tuple), whereas the elements of a record do have names. The ability to provide names is convenient.

Others have suggested you want *anonymous record types*, meaning you don't have to explicitly declare the record type. That might be relevant, too.

---

With those concepts, here's what I think you want from a language. First, I think you want your language to support records. Second, assuming you want a statically typed language, it sounds like you want your language to support type inference, so that the compiler can infer the types of records where possible. (In a dynamically typed language, you might not need the type inference part.) Third, you want your language to provide `select` and `join` operations that operate on records and return records, and (assuming you want a statically typed language) you want the type inference operation to be able to infer the types on their result based on the types of what they're operating on.

There are some questions you'll need to decide. Will `select` and `join` be built into the language? Or do you want to enable them to be implemented as libraries or user-defined functions?

You'll also need to make some decisions about your type system. Do you want to alow subtyping on records? Do you want to allow functions in your language to be polymorphic over records? For instance, consider the following function:

```
function g(r):
    return (r.weight + 10) / r.height

```

Do you want your type inference routine to infer that `g` is polymorphic in the sense that it can accept any record containing `width` and `height` fields that are both `int`s? Do you want to allow first-class field names? For instance, consider the following function:

```
function extract(r,f):
    return r.f

r = {height: 69, weight: 152, name: "Bob"}
extract(r, #weight)

```

In other words, do you want to be able to pass the name of a field as a first-class value?

---

There's lots of work on type systems for this sort of stuff, in the programming languages community -- and especially in functional languages. I believe that F# and ML support sophisticated record types. Here are two samples:

For experience about how to integrate SQL-like database queries directly into the programming language, take a look at LINQ, which provides support for SQL queries directly in .NET / C#. There are both academic papers on LINQ and lots of documentation for developers. It looks very close to what you are looking for.
> 5 votes

---
Tags: type-theory, type-checking, notation
---


# Question
Title: upper bound for the size of a universal Turing machine
Let $\phi$ be a the function computed by a universal Turing machine: $\phi\_y(x)$ is the encoding of the output of the machine for the program whose Gödel encoding is $y$ with input encoding $x$.

I am looking for an upper bound on the length of the shortest program that computes $\phi$.

# Answer
> 1 votes
The precise answer depends on the model of computation and on the specifics of the encodings for $x$ and $y$ -- so if you want an answer, you'll need to specify those.

In general, once you specify those, the way we get an upper bound is by writing an interpreter that interprets the Turing machine $y$ on input $x$; then we look at the length of that interpreter. So, that should tell you how to get an upper bound for yourself.

In any case, the upper bound will always be some constant, i.e., $O(1)$ (for trivial reasons).

---
Tags: computability
---


# Question
Title: Is there an efficient way to cluster a graph according to Jaccard similarity?
Is there an efficient way to cluster nodes in a graph using Jaccard similarity such that each cluster has at least k nodes?

Jaccard similarity between nodes i and j: Let S be the set of neighbours of i and T be the set of neighbours of j. Then, the similarity between i and j is given by $\frac{|(S \cap T)|}{|(S \cup T)|}$.

# Answer
> 1 votes
Any hierarchical clustering algorithm should meet your needs. There are many efficient methods for hierarchical clustering; you can use any of them for your application.

With agglomerative (bottom-up) clustering, you simply keep merging clusters until all clusters have at least $k$ nodes.

With top-down clustering, you keep splitting clusters, except that if the algorithm tells you to split some cluster in a way that would leave one of its subclusters with fewer than $k$ nodes, you cancel the split and mark that cluster as finalized.

In general, hierarchical clustering gives you a tree. You can pick any consistent cut through the tree that leaves all clusters of size $\ge k$. So, it is easy to adapt any hierarchical clustering algorithm to satisfy your requirement that all clusters have at least $k$ nodes. Many of the hierarchical clustering methods let you use any pairwise distance function, so you can use them with your Jaccard similarity metric.

---
Tags: graphs, data-mining, cluster
---


# Question
Title: No number is equal to Zero, is this statement true or false?
While reading an article on logic, there is a sentence "No number is equal to zero" and we have to assign truth values to this sentence. I hope this is true and the article says it as false.

Can someone explain me why it is false? Or the author of the article is wrong?

# Answer
> 6 votes
It is false if and only if there is a number that is equal to zero.

"There is a number that is equal to zero" is true if and only if zero is a number. Without any context (there might e.g. be some very strange definitions given earlier in the exercise), we cannot say whether zero is considered a number in this case. If there is no other context given in the exercise, it should be clear that zero is a number.

For example, the domain of discourse might be only positive integers\*, when zero is not a number, but then it would be very weird to use the word "zero" in the sentence in the first place.

\*The set of natural numbers has two contradicting definitions, $\mathbb{N}=\\{0,1,2,\dots\\}$ (non-negative integers) and $\mathbb{N}=\\{1,2,\dots\\}$ (positive integers). This might be the source of confusion in your case.

# Answer
> 3 votes
What I gathered, form a cursory reading of the paper is that the old man described the algebraic properties of the rational numbers, by actually describing what a ring is, as the corresponding wikipedia article is explicitly referenced in the text (though the word ring is not given). Hence, he must have specified that the addition has a special element called zero wich is an additive identity.

Hence any model that fits the description given by the old man, i.e. that is actually a ring, must have an element called zero with the required properties. This is certainly true of the rationals, and it must be true of what you (as the character of the story) call the integers since you have no disagreement with the old man.

And, as stated in the article, it will actually be true of any model meeting the description of the old man. So, for any model you care to call "numbers", the statement "*(5) No number is equal to zero*" is clearly false.

However, I am bothered by statements (1), (3), and (4) that refer to the number 2, as the axioms for a ring do not define what 2 might be. It is not supposed to have been defined in the discussion, and it is therefore difficult to assign any meaning to a statement using it. They should have at least agreed that 2 is a notation for the result of "1+1".

# Answer
> 1 votes
In the part of the article you're referring to, "number" means either "integer" or "rational" (specifically, the conceit is that you're talking to an old man and the old man thinks you're talking about the rationals, while you think you're talking about the integers). There is an integer equal to zero and a rational equal to zero so, in either case, the sentence is true: the number equal to zero is zero itself.

# Answer
> 1 votes
Your confusion comes from trying to describe a mathematical statement in English -- but not very precisely. English often isn't very precise. Here it isn't clear exactly what the intended translation of the English into mathematics is. Let me outline a few possible translations:

* $\forall x \in \mathbb{Z} . x \ne 0$. This proposition is false. $\mathbb{Z}$ (the set of all integers) does include $0$.
* $\forall x \in \mathbb{N} . x \ne 0$. This proposition is false, using the usual definition of $\mathbb{N}$ as the set of all natural numbers (i.e., all non-negative integers, i.e., $\mathbb{N}=\\{0,1,2,3,\dots\\}$).
* $\forall x \in \mathbb{Q} . x \ne 0$. This proposition is false. $\mathbb{Q}$ (the set of all rationals) does include $0$.
* $\forall x \in \\{1,2\\} . x \ne 0$. This proposition is true, since the set $\\{1,2\\}$ does not include an element $0$.
* $\forall x . x \ne 0$. The truth value of this proposition is indeterminate, without knowing the universe over which $x$ is quantified. If we are letting $x$ range over all of $\mathbb{Z}$, this is true. If we are letting $x$ range over $\\{1,2\\}$, this is false.

---

From a practical perspective, I think we could say the following: in this particular example, I think nothing very interesting is happening. It's just a case of being imprecise with notation. So, from a practical perspective: take this as a lesson to try to be explicit about what you are quantifying over, to ensure there is no possibility of confusion.

---

From a theoretical perspective, here is what is going on. That article is talking about propositional logic. Propositional logic is, in some sense, a framework for reasoning about what is true *regardless of what universe you are quantifying over*. In other words, in some sense propositional logic wants to help us reason about propositions where we don't need to specify the set that $x$ ranges over, because the proposition will be true either way. This is where models come in. A model is basically a set that all quantified variables range over (it also specifies, for each predicate, which elements of that set make the predicate true). Now we can have a propositional formula that is true for all models; false for all models; or true for some models and false for others.

For more, see https://en.wikipedia.org/wiki/Interpretation\_%28logic%29 and textbook introductions to propositional logic and first-order logic.

---
Tags: logic, first-order-logic
---


# Question
Title: The theoretical upper bounds for duplicate detection in a set of objects?
I recently had a lengthy exchange with someone about the most efficient way to remove duplicates from a collection. The debate was mostly centered around the specific behavior of C# collections, such as HashSet(T) and HashTable(T).

I think we agreed on the fundamentals, but where we couldn’t come to an agreement was what the constraints are with very large sets.

He told me to investigate the theoretical (ie absolute) bounds for duplicate detection in a set of objects… But I don’t really know what that means. I don’t think there’s an absolute bounds if you can break up the problem sufficiently.

There may be a point at which you can no longer use a HashSet / HashTable in .NET because I know that if you are using the framework au-naturale you are constrained by the number of unique values an Int32 can express and the amount of memory you have available.

But the issue of storage and memory issue comes much sooner than the number of unique values, which is typically what the theoretical is concerned with... For example if the data type is integers for the initial set you're removing duplicates from, you run out of memory before the numeric range of the integer type becomes a problem:

* If I am storing integers, I know that there are 2^32 possible integer values.
* To store an integer, I need 32 bits of space, so the total memory required to store all distinct integers is 2^32\*4 bytes, which is 17.18 gigabytes.
* The amount of memory that can be addressed in a 32 bit architecture is 2^32 bytes or approximately 4.295 gigabytes

Even if I’m not using a hashset, I can see that in order to store that many values, I would need at least four times the amount of memory addressable by the architecture for the initial collection. And that's not even factoring in the duplicates we're seeking to remove.

I would also need memory proportional to the size of the initial set for the hash set implementation and hash set value storage… So the use of a hashset quickly becomes unfeasible when you exceed millions of unique values.

I’ve already asserted to him that if you had a large digit such as a long, and you had billions of values, you would not use a hashset. Hypothetically I might store the data in distributed nodes that are pre-sorted by the unique field, or implement a distributed mapreduce sort implementation, followed by a mapreduce duplicate value removal algorithm.

He didn’t acknowledge the feasibility of the sort/remove duplicates approach though… And was quite insistent that there is an upper bound for duplicate detection.

Could anyone tell me what the ‘absolute’ bounds for duplicate detection for a set of objects is? Or what he was was referring to by it?

# Answer
> 1 votes
I think you're asking about the "Element Distinctness Problem."

Assuming you're talking about time complexity (number of comparison operations) rather than space complexity, "lower bound" instead of "upper bound," and that you can't hash elements of your multiset (which gives you $O(n)$ expected time), then the best you can do is $\Theta(n \log n)$.

---
Tags: hash-tables, performance
---


# Question
Title: Are there any problems in complexity class EXP that are not in NP?
I cannot conceive of any problem that can be solved in exponential time, but cannot be checked in polynomial time.

# Answer
> 12 votes
First of all, we don't know whether $NP=EXP$ or not. So the initial answer is "it is an open question".

However, we strongly believe (and there are supporting evidence) that $NP\neq EXP$. In fact, we believe that $NP\neq PSPACE$ and that $PSPACE\neq EXP$ (that is, there is a strict containment $NP\subsetneq PSPACE \subsetneq EXP$).

Since you are looking into problems that cannot (to our knowlendge) be verified in polynomial time, you can start with any PSPACE complete problem. For example, TQBF, or $ALL\_{NFA}$. If you want EXP-complete problems, there are examples here.

---
Tags: complexity-classes
---


# Question
Title: Find a hole while travelling along an infinite wall
There is an infinite wall with a hole somewhere, you are placed on that wall at an unknown position. Let the distance between your initial position & the hole be $x$. Find the average distance traveled in terms of $x$ until you find the hole. What's the complexity of this problem in terms of $x$ and how does an algorithm look like that solves it?

# Answer
If you can go only left or right, than you can do the following strategy:

```
DIRECTION = Right
For i = 0 to infinity do:
    Go 2^i steps to DIRECTION.
    Go back to the initial place.
    CHANGE_DIRECTION
    STOP if you found the hole

```

If the distance between the start place and the hole is n, you will find the hole within O(n) steps. You can easily calculate the exact average number of steps given this algorithm.
> 1 votes

---
Tags: algorithms, time-complexity
---


# Question
Title: Decidability of $\lbrace \langle D \rangle \mid \text{$D$ accepts $a^kb^k$ for some $k > 0$}\rbrace$
I'm trying to understand decidable languages. In particular, I would like to show that $$B = \lbrace \langle D \rangle \mid \exists k \geq 0 \\,.\\,\text{DFA $D$ accepts $a^k b^k$}\rangle.$$ I don't quite understand the process of proving these. I know that $a^kb^k$ is not regular, so then no DFA accepts it. I also know that $A\_{DFA}$ (acceptance DFA) is decidable, I also know several other decidable languages like $E\_{DFA}$ and $EQ\_{DFA}$. How can I use these to prove that $B$ is decidable?

If no DFA accepts $a^kb^k$, doesn't that mean that $A\_{DFA}$ will reject? So if $A\_{DFA}$ rejects then shouldn't the decider for $B$ accept?

# Answer
Hint: Let $s\_0$ be the starting state, $F$ the set of accepting states, and $q$ the transition function. The mapping $k \mapsto q(s\_0,a^k)$ is eventually periodic and can be determined explicitly. The predicate $(s,k) \mapsto q(s,b^k) \in F$ is eventually periodic and can be determined explicitly. So the predicate $k \mapsto q(q(s\_0,a^k),b^k) \in F$ is eventually periodic and can be determined explicitly.

Similarly, you can check whether a DFA accepts some word of the form $a^k b^k c^k$. The fact that the languages $\\{ a^k b^k \mid k \in \mathbb{N} \\}$ and $\\{ a^k b^k c^k \mid k \in \mathbb{N} \\}$ are not regular doesn't play any role here.
> 6 votes

# Answer
Hint. The language $\\{a^k b^k \mid k \in \mathbb{N}\\}$ is context-free. So, can you construct a context-free grammar or pushdown automaton for it? What do you know about the closure properties of context-free languages and regular langauges? If you take the `_____` of a regular language and a context-free language, what do you get? Do you know how to test whether a context-free language is `_____`? How does that help? (You fill in the blanks; to avoid giving too much away, I've left some blanks for you to fill in.)
> 3 votes

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


title: Naive Bayes Intuition

text:
# Question
Title: Naive Bayes Intuition
I have some difficulties in understanding the intuition behind Naive Bayes Classification.

In general, I do understand every argument of the definition, however I don't understand why it's correct and why any other argument is incorrect.

Start from the beginning:

**Goal:** $v\_{MAP} = argmax\_{v\_i} p(v\_i|a\_1...a\_n)$

the goal is simply to find the maximum aposteriori of the value of the target function given the set of features Note, here we don't mention the hypothesis, because we are not interested in hypothesis.

After developing the formula with Bayes formula, we get

$argmax\_{v\_i} p(v\_i)p(a\_1...a\_n|v\_i)$

Now, the trick goes $p(a\_1...a\_n|v\_i)=\prod\_{j} p(a\_j|v\_i)$

The question is why in the very begging, having the formula of

$v\_{MAP} = argmax\_{v\_i} p(v\_i|a\_1...a\_n)$

I cannot apply the trick $p(v\_i|a\_1...a\_n)=\prod\_{j} p(v\_i|a\_j)$

It's just a reverse direction, in addition we don't have to calculate the prior probability of $p(v\_i)$, so for me it looks like the better way to go.

What's wrong with my reasoning.

# Answer
Because in general $p(v\_i \mid a\_1 \dots a\_n) \ne \prod\_j p(v\_i | a\_j)$. There is no reason to expect that equation to hold with equality. You can't just write down an equation and hope that it is true; you have to be able to justify it from the axioms of probability, and you can't justify the equation you want to hold.

Remember that $p(A \mid B)$ is not the same as $p(B \mid A)$. The two probabilities can be very different. Be careful not to confuse them, or you will definitely get very mixed up.

In general, if $A,B,C$ are events, then $p(A \mid B,C)$ is not necessarily equal to $p(A \mid B) \times p(A \mid C)$. It is easy to come up with a counter-example. For instance, suppose I toss a fair die, and define the following events: $A$ = "the die came up 5", $B$ = "the die is showing an odd number", $C$ = "the die is showing a prime number". Then $p(A \mid B,C) = 1/2$, $p(A \mid B) = 1/3$, $p(A \mid C) = 1/3$, and $1/2 \ne 1/3 \times 1/3$.

The reason why you *can* write $p(a\_1 \dots a\_n \mid v\_i) = \prod\_j p(a\_j \mid v\_i)$ is because $a\_1,a\_2,\dots,a\_n$ conditionally independent on $v\_i$: once $v\_i$ is fixed, then $a\_1,a\_2,\dots,a\_n$ become independent. In general, if $A,B$ are conditionally independent on $C$, then $p(A,B \mid C) = p(A \mid C) \times p(B \mid C)$ -- this is in fact the definition of conditional independence. That's why $p(a\_1 \dots a\_n \mid v\_i) = \prod\_j p(a\_j \mid v\_i)$ is justified. (However, no such justification is available for $p(v\_i \mid a\_1 \dots a\_n) \ne \prod\_j p(v\_i | a\_j)$.)

If you are not familiar with the concepts of independence and conditional independence, I suggest reviewing a standard probability textbook, where you can find more on that subject to help you practice and become proficient with those concepts.
> 2 votes

---
Tags: machine-learning, probability-theory
---


# Question
Title: What is this hash of array data structure called?
I've created a data structure that is a hash of arrays with a special property: the hash keeps track of the combined order in which items are appended to its arrays.

For example (pseudocode):

```
h = HashOfArray()

h["a"].append(1) // accessing an unset key returns an empty array
h["b"].append(2)
h["a"].append(3)
h["b"].append(4)

h["a"]
>>> [1, 3]

h["b"]
>>> [2, 4]

h.items()
>>> [1, 2, 3, 4]

```

I'm struggling with coming up with a good name for this data structure. Does it have a commonly used name? I've called it `HashOfArray` but that fails to convey its main property: that it maintains the combined append order of the arrays.

Example implementation in Ruby: https://gist.github.com/kajic/7981533

# Answer
> 1 votes
No, this data structure does not have a commonly-used name. It so similar to a hash table that it is very unlikely to have been the subject of a peer-reviewed publication.

# Answer
> 0 votes
I am not familiar with a name that will describe your entire data structure, but to simplify it you can name it: `HashQueue` as your arrays are Queue.

---
Tags: data-structures, arrays, hash-tables
---