# Question
Title: how can i say a given problem is in co-NP using it's definition?
I seem to be having trouble understanding the connection between the formal definition of co-NP and how problems are concluded to be in it. co-NP is defined to be the class containing the languages that are complements to languages in NP (I'm using this definition).

So, given this problem: "given a finite set of integers, is there a non-empty subset that sums to zero?" is in NP. How do i conclude that this problem: "given a finite set of integers, does every non-empty subset have a non-zero sum?" is in the class co-NP?

In other words, **how do i know that the second problems corresponding language L2 is the complement to the first problems corresponding language L1?**

Perhaps i'm missing something fundamental?!

Edit: It seems I was not clear enough so hear is a clarification: My question was **why** does the complement language L2 represent the second problem if it contains many seemingly random strings?

**In other words, how are these seemingly random strings instances of the second problem?**

# Answer
Following the brief discussion in the comments, let me write an answer summarizing it.

When defining decision problems (e.g., based on $\\{ 0, 1 \\}^\ast$ strings), we usually make the assumption that *every word in $\\{0,1\\}^\ast$ is a valid problem instance*. Perhaps your source of confusion is that, usually, this is not made as explicit or given as much importance as it should or, rather, it is only too late (i.e., when discussing complementary problems such as those in $\textbf{coNP}$) that one realizes what the assumption actually entails. Under such an assumption it is obvious why $\textbf{coNP}$ is simply the complements of the problems in $\textbf{NP}$; in fact, without the assumption, such a definition would not make that much sense (since $\textbf{coNP}$ problems would contain invalid problem instances).

In the comments, I have also mentioned the notion of promise problems. This is an alternative way of defining decision problems without needing the aforementioned assumption. Basically, when the input string is not an encoding of a problem instance, the behavior of an algorithm solving the problem is left unspecified. The result is the $\\{0,1\\}^\ast$ string space being partitioned in three parts: valid "yes" instances, valid "no" instances, and invalid instances. Note that for poly-time algorithms this notion is equivalent to the former one since recognizing a valid instance (for reasonable problems) can always be done efficiently.
> 1 votes

# Answer
NP and co-NP are about decision problems : Problems where every instance has an answer “yes” or “no”.

A problem is in NP if every instance with answer “yes” you has a proof that can be checked on polynomial time. A problem is in co-NP if every instance with answer “no” has a proof that can be checked in polynomial time.
> 0 votes

# Answer
Complement of a decision problem is simply defined as “flip yes and no answers”.

Your confusion seems to come from the fact that decision problems and their corresponding languages are not the same things, strictly speaking. In order to talk about decision problems as languages, you need to formalize them as such.

Whether the complement of the language would be equal to the language of the complement problem is totally up to your chosen encoding of the problem instances.
> 0 votes

---
Tags: complexity-theory, formal-languages
---


# Question
Title: Matching schedules between users and providers
I have a problem I've been dealing for the past few days, and I'm pretty stuck.

Each `user` has a schedule for a given week, such as `Mondays 9:00-12:00 and 14:00-18:00, Tuesdays...` and so on. Each `provider` has another schedule for himself.

The problem is: Get the best `k` (different) solutions such that each solution assigns the minimum amount of providers to cover the entire schedule from the user? Where a solution is a set of pairs `(Provider, schedule he will cover)` and two solutions are considered equal if they contain the same `providers` (and different if they are not equal).

Also, take into account that any day could be split in sub-intervals and assigned to different `providers`. An example for a solution for the schedule shown before could be: `{(Provider1, Monday 9:00-12:00), (Provider1, Monday 14:00-16:00), (Provider1, Monday 16:00-18:00)}`

I've been looking into the Interval Partitioning Problem, Bipartite Matching Problem, and Assignment Problem, and none of them seem to adjust to my case.

Any ideas on how I could model this problem?

# Answer
> 2 votes
I think your problem is actually not a scheduling problem but a set cover problem. Just cut the time line in the atomic time parts of providers and assign them indices.

For instance, considring only one day for user from 8h to 14h:

* provider 1: 7h-10h
* provider 2: 6h-9h
* provider 3: 10h-16h

The cut-off is:

1. 6h-7h
2. 7h-9h
3. 9h-10h
4. 10h-16h

and your problem is solving the minimum set cover of {2, 3, 4} with:

* provider 1: {2, 3}
* provider 2: {1, 2}
* provider 3: {3, 4}

with evident solutions providers 1&3 or 2&3.

Nevertheless, this is a NP-problem and you likely have to test most of combinatoric if you really want to get optimal solutions. Sometimes this type of application contain some constraints or patterns that may help you to reduce the problem.

---
Tags: scheduling, bipartite-matching, assignment-problem, intervals
---


# Question
Title: Why does $L\subseteq \textbf{P} \cap \textbf{NP}$ is $\textbf{NP}$-complete imply $\textbf{NP} = \textbf{P}$?
If I show that a language $L$ is contained in $\textbf{P}$ and $\textbf{NP}$ and I know that the language is $\textbf{NP}$-complete, why did I proof that $\textbf{P} = \textbf{NP}$?

# Answer
Because you have then showed that $L$ is an $\textbf{NP}$-complete language which, since $L \in \textbf{P}$, is decidable in poly-time. Since any other language $L' \in \textbf{NP}$ is efficiently reducible to $L$ (because of $\textbf{NP}$-completeness), $L' \in \textbf{P}$ as well. It follows that $\textbf{NP} \subseteq \textbf{P}$ (and the other inclusion is trivial).
> 4 votes

---
Tags: complexity-theory
---


title: What are the implications of P=NP?

text:
# Question
Title: What are the implications of P=NP?
Is there a list of implications of $P=NP$?

Presumably, a proof of $P \ne NP$ will be by contradiction, for which a list of consequences of $P=NP$ would be useful.

# Answer
There wouldn't be a lot of practical implications. In practice, the question is not whether a problem can be solved in polynomial time, the question is whether it can be solved in a reasonable amount of time.

Let's say I can solve the Travelling Salesman problem for n cities in n^12 nanoseconds. So what? N=50 still takes thousands of years.

No fast algorithms for this problem are known. P=NP doesn't magically give us any fast algorithms.

Of course P = NP would affect a huge number of open problems in computer science, where certain problems are obviously in P, and obviously in NP but not known to be NP-complete, and it is unknown where exactly between P and NP they are - all these problems would be known to be in P. (See this question for example: Existence of NP problems with complexity intermediate between P and NP-hard )

And if a guaranteed polynomial time algorithm for checking primality hadn't been known, we would know that one exists (but that knowledge would have been no help whatsoever to find this algorithm).
> 2 votes

# Answer
If P=NP, then all of the NP problems can be solved deterministically in Polynomial time.

This is because the NP problems are all essentially *the same problem*, just stated in different terms.

As far as lists go -- many of the NP-Complete problems are enumerated here: https://en.wikipedia.org/wiki/List\_of\_NP-complete\_problems

Further implications? Our cryptosystems break down, armchair philosophers argue about what it means, the world changes, and somebody gets a Fields medal or Turing award + a big hunk of cash, etc... but that's a tangent.

For example, one of the classic NP problems is clique. If you could solve clique with a polynomial time algorithm, this would prove that P=NP, and then you could also use your method for solving clique to solve all of the other problems on that wiki-list, as an implication.
> 1 votes

# Answer
It also implies that some unsolvable problems may just be very hard. One of which being "which specific genes cause the phenomenon of consciousness" which could yet be solvable.
> -2 votes

---
Tags: complexity-theory, proof-techniques, np, polynomial-time, p-vs-np
---


# Question
Title: Algorithm to separate circles to reduce collision the maximum between them
I'll try to do my best to explain this.

I have X circles (from 2 to 4) which can move around smaller pivot circles. The pivot circles are fixed and cannot be moved once they are in the "field". Pivot circles are never created colliding with other pivot circles. Something like this:

Red are pivot circles (fixed) and orange are the normal circles (displace without exiting the pivot circles).

Now if I put two pivot circles near, the algorithm should do something like this:

This is pretty easy to achieve. Detect colliding circles and displace them the needed amount. Because red circles never collide, the orange circles are never going to break the "do not exit the pivot circle" rule.

The problem comes when 3 or more circles come into play. Because they cannot exit the pivot circle zone, so there should be some vertical/horizontal movement, like this:

I think this is the least colliding I can achieve when 4 pivots are next to the other. I created this manually but I'd like to know if there's already an algorithm to detect this efficiently without making a lot of detections/passes to achieve the least colliding factor, as I don't like everything that I'm thinking on.

The best I can think of is to simply do a loop where I detect all circle collisions, then displace the circles the amount needed for them to avoid the collisions the maximum possible, then repeat the loop, and repeat until I find that the "collision factor" is not reduced anymore for the next X steps. To make the circles go "up" and "down" I can try to create a bit of noise each time, and the algorithm will do the rest to move the circles up and down. Also, instead of noise I can try to detect if they are colliding "horizontally" or "vertically" and add a bit of horizontal/vertical movement when a circle with 2 or more collisions has a perfect horizontal/vertical collision.

I don't like this much actually, so well, here I am hehe.

I can't think of something, but I'm pretty sure that there's something that can be calculated with one step, instead of looping the same step multiple times, but I'm really stuck and nothing comes out of my head.

# Answer
If you want to brute force it, this is a constrained optimization problem where the quantity you're minimizing is the overlap area, the variables are the x and y coordinates of each circle's center, and the constraints are that each center lies within a red circle.

Depending on how you want to count areas inside three or more circles, the formula for the overlap arra can be reasonably simple or a huge mess that gets worse with the number of circles.
> 2 votes

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


# Question
Title: What is the point of traversing a binary tree in preoder, inorder or postorder?
Why would you want to traverse a binary tree in preoder, inorder or postorder? Why not use an order like breadth-first search for all graphs?

# Answer
> 7 votes
Different traversals of a binary tree exist to suffice different data dependencies between the nodes.

Let's have a comparison between different traversals of a tree. Note that aside from in-fix traversal, the tree doesn't have to be binary.

In case of **Postorder**, we process the descendants of a node before the node itself, meaning that we want to send some data from the descendants to the ancestors to be able to process the ancestors. For example if you want efficiently to calculate for each node $n\_i$ the weight of the subtree rooted at $n\_i$, which is the sum of the weights of all descendants of $n\_i$ including $n\_i$.

In case of **Preorder**, you process the predecessors before the descendants. One use case is broadcasting data to all descendants of each node in the tree. For example, if you want count the number of predecessors of each node with some characteristic, you propagate the counter of each node to its children and each child add one if it has the characteristic itself.

In case of **Inorder** you might have a left-right order between the nodes of the tree (Example: binary search tree), and might be interested in visiting the elements according to this order (Printing the keys of a binary search tee in ascending order).

Finally, in case of **BFS**, we consider the tree as levels, level $l\_i$ has all vertices with depth $i-1$, which is at distance $i-1$ from the root of an unweighted tree. BFS has a lot of use-cases. Here we are interested in processing all nodes of each level consequently (starting from the smallest level). Most common use cases are the ones where we want to process the closer vertices to the root before the farther ones for example if we want to assign ids to the vertices so that for two vertices $n\_i, n\_j$ if $i \< j$, $n\_j$ is not closer to the root than $n\_i$.

**Note** that in some cases you might be interested in two consequent traversals for example a post-order to gather data from the whole tree in the root and a following pre-order to broadcast the data to each node in the tree in total linear time in the size of the tree.

**Note** In some cases any of the traversals suffices, if all nodes are independent of each other and you are only interested in visiting all nodes of the tree(For example, to calculate the depth of each node you can use BFS or Preorder with no remarkable differences). However, some times you might still be interested in the order you are visiting the nodes even if there is no data-dependencies between the nodes (For example printing mathematical expression in polish notation vs. infix notation. see link).

**Note** One interesting application is Euler tour technique in parallel computing. By setting the right weights on the right edges you get pre-order, post-order and the depth of the nodes of a tree. see link.

# Answer
> 2 votes
As Narek Bojikian explains, it depends on the use case: often, any traversal order will do, but sometimes, it makes a big difference. He doesn't provide concrete examples, so I will provide one, using the Unix `find` command.

The Unix `find` command lets you traverse a directory tree and execute arbitrary commands for each file it encounters.

Let's create a directory:

```
$ mkdir d

```

Now let's traverse that directory tree (it's empty), no deeper than depth 2, and for each file we encounter, execute `mkdir` to create the subdirectories `a` and `b`:

```
$ find d -maxdepth 2 -exec mkdir \{}/a \{}/b \;

```

This should just create the directories `d/a` and `d/b`, right?

Let's see. Without arguments, `find` just prints the names of the files it encounters:

```
$ find d
d
d/a
d/a/a
d/a/a/a
d/a/a/b
d/a/b
d/a/b/a
d/a/b/b
d/b
d/b/a
d/b/a/a
d/b/a/b
d/b/b
d/b/b/a
d/b/b/b

```

We got a lot more than just `d/a` and `d/b`. Why?

As you can see from this listing, `find` traverses the directory tree using *depth-first search*: it prints `d/a/a` before `d/b`.

More specifically, it uses *preorder* traversal: it prints `d` before `d/a`.

It turns out that in cases where we care about the order of processing, this is the most commonly wanted order. For instance, if we just want a listing of filenames, this produces them in lexicographical order, which is usually what we want.

The preorder traversal explains why the first `find` command created so many directories: it executes the `mkdir` command for a directory before traversing its contents, which by then include the newly created subdirectories `a` and `b`.

So this is a nice way to create a directory of arbitrary depth (specified by the `-maxdepth` argument).

What if we want to traverse a directory tree and only create `a` and `b` subdirectories in each *pre-existing* directory?

The answer: that's exactly what *postorder* traversal will produce:

```
find d -depth -exec mkdir \{}/a \{}/b \;

```

The `-depth` option means: use postorder traversal instead of the default preorder traversal. (It should have been called `-postorder`.) This command would have created just `d/a` and `d/b`.

But OK, we've created this whole directory tree. Let's remove it. We can do this easily, by calling `rmdir` on each directory in it.

First try:

```
$ find d -exec rmdir \{} \;
rmdir: failed to remove 'd': Directory not empty
rmdir: failed to remove 'd/a': Directory not empty
rmdir: failed to remove 'd/a/a': Directory not empty
find: ‘d/a/a/a’: No such file or directory
find: ‘d/a/a/b’: No such file or directory
rmdir: failed to remove 'd/a/b': Directory not empty
find: ‘d/a/b/a’: No such file or directory
find: ‘d/a/b/b’: No such file or directory
rmdir: failed to remove 'd/b': Directory not empty
rmdir: failed to remove 'd/b/a': Directory not empty
find: ‘d/b/a/a’: No such file or directory
find: ‘d/b/a/b’: No such file or directory
rmdir: failed to remove 'd/b/b': Directory not empty
find: ‘d/b/b/a’: No such file or directory
find: ‘d/b/b/b’: No such file or directory

```

Clearly, that doesn't work: we're traversing in preorder again, so we're calling `rmdir` on a directory before trying to visit its subdirectories. Once again, the resolution is to visit in postorder instead:

```
$ find d -depth -exec rmdir \{} \;
$ find d
find: ‘d’: No such file or directory

```

That's better. The whole tree has been removed.

So having the choice between preorder and postorder directory tree traversal is clearly useful. That's why `find` gives us both.

What if we want to use breadth-first traversal instead? Too bad, `find` doesn't have an option for that. Why not?

One reason: I've been using Unix and Linux for 36 years now; I use `find` almost daily and `find -depth` fairly often, but I can't recall an occasion when I wanted to traverse a directory tree breadth-first. It just isn't a common need.

The second reason: breadth-first traversal consumes much more memory.

For depth-first search, memory consumption is $O(\log n)$: all you need to keep in memory is the stack of nodes leading up to the current node.

For breadth-first traversal, it is $O(n)$: you need to keep the whole queue of unvisited nodes in memory, which at some point includes all nodes of a given depth.

For instance, on one of my Linux systems, the root directory contains 1448354 files, its highest directory depth is 25, and the highest number of files and directories at the same depth is 325680 (for depth 7). So a `find /` on that Linux system will maintain a stack with a maximum size of 25, while a breadth-first traversal of `/` will maintain a queue with a maximum size of about 325680. Why spend all that memory? We can obtain the same result in a memory-efficient way by running a series of consecutive `find` commands:

```
find / -maxdepth 1 [...]
find / -mindepth 2 -maxdepth 2 [...]
find / -mindepth 3 -maxdepth 3 [...]
[...]

```

There is just no need for `find -breadthfirst`.

You may always run into a graph traversal use case that really requires breadth-first and nothing else. Those cases are rare, and if your graphs can be large, make sure you have the memory to spare.

---
Tags: algorithms, graphs, trees, binary-trees
---


# Question
Title: What are different ways to provide a semantics to a language?
Suppose you have 1. a grammar for terms of a language; 2. type-assignment rules, 3. a set of reduction rules. You want to prove that your language is adequate for mathematical reasoning. If I understand correctly, the right way to do it is to develop a semantics for it, and then prove certain desirable properties such as soundness and consistency.

I've seen different approaches to this. Usually, a model in set theory is involved. But I believe that is not the only way to do it. Wouldn't, for example, an interpreter for that language on the untyped λ-calculus count as a semantics? So, my question is: what are the different ways to provide a semantics to language?

# Answer
There are many possible approaches. Here's a few "classic" styles.

* Operational semantics (e.g. small step / reduction, or big step)
* Denotational semantics (e.g. domain-theoretic, or category-theoretic)
* Axiomatic semantics (e.g. hoare logic)

You can also define the semantics of a language through a translation to another language (already having its semantics). CPS transforms could also be mentioned here.

Also note that many languages admit several distinct semantics. Lazy & eager semantics of functional programs are possible, for instance. Prolog also has many different semantics (I recall someone stating "there's no such a thing as THE semantics of Prolog").

Further, concurrent languages like CCS or $\pi$-calculus have a LTS semantics. Game semantics is also used sometimes (but I don't know much about it).

I'm pretty sure there are many other kinds of semantics. I'd be surprised if in the future someone does not invent a new kind of semantics.
> 5 votes

---
Tags: lambda-calculus, type-theory, functional-programming
---


# Question
Title: Randomized communication complexity of indexing
The function $\mathrm{INDEX}:\\{0,1\\}^n\times\\{1,\dots,n\\}\to \\{0,1\\}$ is defined as

$$\mathrm{INDEX}(x,i)=x\_i,$$ where $x=x\_1\dots x\_n$. I am looking for the randomized communication complexity of $\mathrm{INDEX}$ for an arbitrary number of rounds.

Somehow, I do not manage to find it in the literature.

The deterministic communication complexity is known to be $\Theta(\log n)$, while its one-way randomized communication complexity is $\Theta(n)$.

I guess the randomized communication complexity is still $\Theta(\log n)$, I was not able to find a lower bound.

Since this function its well-studied, it should be stated somewhere.

Thanks for your help.

# Answer
> 1 votes
It is known that the randomized communication complexity of inner product on $m$ bits is $\Omega(m)$. You can compute inner product using a protocol for the indexing function on $\\{0,1\\}^{2^m} \times \[2^m\]$ as follows: denoting Alice's input by $x \in \\{0,1\\}^m$ and Bob's by $y \in \\{0,1\\}^m$, Alice computes a new vector $X$ by $X\_y = \mathsf{IP}(x,y)$, and the parties run the indexing protocol on the inputs $X$ and $y$. This gives an $\Omega(m) = \Omega(\log n)$ lower bound for indexing.

---
Tags: reference-request, communication-protocols, communication-complexity, randomized
---


# Question
Title: MST: Is there such an example of a graph with unique mst and not unique light edge?
The problem is the following:

Give an example of a graph that has a unique minimum spanning tree but for every cut of the graph, there is not a unique light edge crossing the cut.

I am trying to find such a graph, but I have not find any example. Is it possible to have such a graph? If not, why?

# Answer
No.

Here is a proof. Suppose $G$ is a weighted undirected graph such that for every cut of the graph, there is not a unique lightest edge crossing the cut.

Let $M$ be a (or "the" in case it is unique) minimum spanning tree of $G$. Let $v$ be a leaf node of $M$. Consider the cut $\\{\\{v\\},V\setminus \\{v\\}\\}$ of $G$. Since $M$ is spanning, it contains an edge $m$ that crosses the cut. There are at least two edges of the minimum weight that cross the cut. Suppose one of them is $c\_1\not=m$. Let graph $M'$ be the same as $M$ but with $m$ replaced by $c\_1$. It is a routine to show that $M'$ is also an MST. So we know $G$ has two different $MST$s, $M$ and $M'$.

---

This negative conclusion can be seen as an corollary of the characterization theorem of the uniqueness of MST as stated in this answer. Here is the relevant part of that theorem.

(**Uniqueness of MST by cut**) Let $G$ be a weighted undirected graph. $G$ has a unique MST if and only if every edge is either the unique edge of minimum weight crossing some cut or never an edge of minimum weight to cross any cut.

Now let us assume $G$ is a graph of at least 2 nodes such that for every cut of the graph, there is not a unique light edge crossing the cut. Let $C$ be a cut of $G$. Let $e$ be the edge of minimum weight in the cut-set of $C$. Because $e$ is not the unique edge of minimum weight to cross any cut, we see that $G$ cannot have a unique MST.

---
> 2 votes

# Answer
If there is not a unique light edge crossing any cut, it means that every node has at least 2 edges of minimum weight. If you use Prim's algorithm to build your MST which is:

```
Grow the tree, adding nodes one by one.
On each step, select the minimum weight
edge leading to a new node.

```

You realise that whatever is the starting node, you have at least 2 choices. If the MST was unique, there would be leaf nodes having only one possible edge. Therefore there are several possible MST.
> 2 votes

# Answer
I found this answer in a book:

> Consider a graph with 3 vertices a,b,c and weights w(a,b) = w(a,c) = 1 and w(b,c) = 2. The graph has a unique minimal spanning tree (containing edges (a,b) and (a,c)), however cut ({a}, {b,c}) doesn’t have a unique light edge crossing the cut.

I hope it helps!
> 2 votes

---
Tags: graphs, minimum-spanning-tree, prims-algorithm
---


# Question
Title: How does IEEE 754 decimal encoding work?
This may be a silly question, but if a computer works in binary how can you encript numbers using decimal?

# Answer
> 1 votes
Fair question. First of all, it's worth noting that the IEEE decimal formats are fairly modern and not used particularly often—they're meant for the rare use cases where things need to round in a specific way, mostly in finances.

But, there are various ways to encode a truly decimal number (i.e. a number stored as a series of base-10 digits) in binary. The simplest is called BCD (Binary Coded Decimal), which uses four bits to represent each digit. Many early computers used this system because humans are used to decimal and found it more intuitive.

BCD is kind of wasteful, because four bits can represent any number from 0 to 15, and a single digit only need to represent a number from 0 to 9. So IEEE uses slightly different packings, called Binary Integer Decimal and Densely Packed Decimal. They're somewhat more complicated, but the idea is the same: you have a one-to-one mapping between decimal digits and binary bits, wasting as few bits as possible.

---
Tags: floating-point
---


# Question
Title: Solve PARTITION-INTO-THREE-SETS in pseudo-polynomial time
Let **PARTITION-INTO-THREE-SETS** be defined as following:

**Input**: Positive integers $a\_1, ..., a\_n$

**Problem**: Are there three pairwise disjoint sets $I, J, K \subseteq \\{1, ..., n\\}$ with $I \cup J \cup K = \\{1, ..., n\\}$, so that $\sum\_{i \in I}{a\_i} = \sum\_{j \in J}{a\_j} = \sum\_{k \in K}{a\_k}$?

It's easy to show, that PARTITION-INTO-THREE-SETS is NP-complete by doing a polynomial-time reduction PARTITION $\le$ PARTITION-INTO-THREE-SETS.

As PARTITION can be solved in pseudo-polynomial time with dynamic programming, there should be a way to solve PARTITION-INTO-THREE-SETS in pseudo-polynomial time. Is there any solution to adapt the pseudo-polynomial algorithm for this problem?

# Answer
Yes, there is a pseudo-polynomial algorithm for this problem.

---

Here is a wrong algorithm. Can you spot the biggest error?

Let $K=\sum\_{i=1}^n{a\_i}$. If $K$ is not divisible by 3, return none.

Run the pseudo-polynomial algorithm with $\lfloor K/2\rfloor$ replaced by $K/3$ everywhere. Adapting the algorithm so that it tracks the set of numbers whose sum is a given number. If that run of that algorithm return false, return none. If yes, remove the set of numbers from $a\_1, a\_2, \cdots, a\_n$, we reduce the problem to find a subset of the remaining numbers whose sum is $K/3$, or half of the sum of remaining numbers, which is, of course, the partition problem again and which can be solved in pseudo-polynomial time.

---

Let us see how to construct a correct algorithm.

In the pseudo-polynomial algorithm for partition into two disjoint subsets, the goal is to compute function $p$ such that $p(i, j)$ is True if a subset of $\\{x\_1, \cdots, x\_j \\}$ sums to $i$ and False otherwise.

Now for partition into three disjoint subsets we have two variable parts, the first subset and the second subset (the third subset is the remaining integers), our goal is to compute function $q$ such that $q(h,i,j)$ is True if there are two disjoint subsets of $\\{x\_1, \cdots, x\_j \\}$ such that one of them has sum $h$ and the other has sum $i$, where $0\le h\le K/3, 0\le i\le K/3$. We have the following recurrence relation, ignoring a few corner cases because of the out-of-bound situations that are easy to figure out.

$q(h, i, j)$ is True if either of the following is true.

* $q(h, i, j − 1)$
* $q(h, i − x\_j, j − 1)$
* $q(h-x\_j, i, j − 1)$

$q(h, i, j)$ is False otherwise.

I will leave the rest for readers to figure out.

---

**Exercise 1.** Write the correct algorithm roughly or fully in pseudocode or in your favorite programming language. Adapt it so that it will track the subsets in order to return the wanted three disjoint subsets.

**Exercise 2.** Show the time-complexity of the correct algorithm is $O(nK^2)$.

**Exercise 3.** Generalize to PARTITION-INTO-M-SETS for any given integer $M\ge2$.
> 2 votes

---
Tags: complexity-theory, np-complete, dynamic-programming, partitions, pseudo-polynomial
---


title: multithreading - duration of jobs

text:
# Question
Title: multithreading - duration of jobs
" How long will it take for 2 jobs to complete if they're running in parallel, knowing that both have a total of 20 minutes of CPU usage time and 50% IO"

I calculated the CPU usage: `1-0.5²=75%`. To my understanding, if they're running sequentially, time needed to completion is 80 minutes (each job needs 40 minutes to complete) therefore time needed to complete both jobs in parallel is `75% * 80 = 60` minutes.

However here is the correct answer:

" CPU utilization is 75%. Thus each one gets 0.375 CPU minute per real time minute. To accumulate 20 minutes of CPU time, a job must run 20/0.375=53.33 minutes. Thus, in parallel, time to completion for both jobs is 53.33 minutes".

I don't get where the 0.375 came from ?

What are CPU minutes ?

Help is appreciated

# Answer
> I don't get where the 0.375 came from ?

If the CPU utilization is 75%, and it's shared equally between two process, each of them gets 37.5%.

> What are CPU minutes?

A CPU-minute is the amount of work done by one CPU in one minute.
> 1 votes

---
Tags: operating-systems, cpu, process-scheduling, threads, multi-tasking
---


# Question
Title: Why is there no one to many Multithreading Model?
I am studying various multi-threading models. Here the user threads are mapped to Kernel Threads. They are -

```
Many to one model.
Many to many model.
one to one model.`

```

What kept me wondering was why there is no one to many model ?

# Answer
Actually, there is such a model, though it is typically not thought of as one of the "multi-threading models."

One to many would mean one thread distributed across many processors. At first that should look silly. After all, you only have one thread. What are the other processors to do? However, superscalar architectures are designed to do roughly this sort of operation. In superscalar architectures, instructions are decomposed and the CPU identifies the best ways to do these decomposed pieces in parallel, utilizing as much of the hardware as possible. As a trivial example, they might do a floating point operation and an integer operation at the same time. Or they might take both branches of a conditional jump at the same time, only settling on one branch later when data becomes available.

This isn't quite a "multi-threading" model, because there's no crisp clean boundary between CPUs. In superscalar architectures, the hardware utilization is much more fluid. But it does accomplish something which is very similar in nature: it executes many instructions from one thread in parallel.
> 1 votes

---
Tags: operating-systems, threads
---


# Question
Title: Rational agent question from Russell and Norvig
Question from *Artificial Intelligenge: A Modern Approach* by Russell and Norvig (Exercise 2.1).

> Suppose that the performance measure is concerned with just the first $T$ time steps of the environment and ignores everything thereafter. Show that a rational agent's action may depend not just on the state of the environment but also on the time step it has reached.

This question is extremely confusing to me. My initial thought is that this is obvious. A rational agent wants to maximize its performance, and the first $T$ time steps are a factor in the performance measure. So for instance, if the environment is in state $A$ at time step 1, the performance measure can be different than being in state $A$ at step 2 since the state of the environment in step 1 is relevant to the performance measure in the latter case. Thus as the performance measures can be different, the rational agent may make different actions.

Perhaps that is the answer, but I am still confused on why it matters that the performance measure is concerned with only a finite sequence of initial time steps. My interpretation of the question seems to make that irrelevant. Only the fact that the performance measure has some historical factor is of any concern.

Can anyone help clarify what is happening in this question?

# Answer
> 2 votes
This question is obvious as you told and its purpose is to ensure that the reader has understood a part of the chapter. You are right that the actions that the agent does will differ in the time period T. They will also differ after this period, because the agent's actions will have no value.

One example may be for a car agent that has to cover as much distance as possible and has limited fuel. If only the distance reached during the first hour counts, the car could take it in full throttle(exhausting the fuel very fast). However if there was no time limit the car agent should choose the optimal speed that maximizes the distance covered per fuel unit spent.

# Answer
> 0 votes
My first thought regarding this question was that a rational agent could be involved in some sort of time-limited event or activity, such as a sports game. In such a scenario, the agent would be required to play against an opponent and accumulate more points than the opponent within a predetermined amount of time. So, the duration of the game would be the T time steps that the performance measure is concerned with. In a game of soccer, for example, goals may be scored outside the game’s duration, but obviously, they do not matter. The agent’s style of play or tactics may change during the game depending on the score relative to the remaining time. If the agent has a comfortable point lead over its opponent with little time remaining in the game, it may choose to simply play defensively for the remainder. On the other hand, if the agent has a lower score than its opponent and there is a considerable amount of time remaining, it may choose to play more offensively in order to gain points.

Another situation in which a rational agent’s actions may depend on the time step is has reached could be taking a long exam in some given amount of time. If the agent has 60 minutes to complete 30 exam problems and has 20 problems finished after 45 minutes, it may start skipping the problems that it finds to be more difficult or time consuming and focusing on the easier or shorter ones in order to maximize the amount of problems it can answer, instead of just completing them in the order they are given and possibly not having time to answer some of the easy questions

# Answer
> 0 votes
The role of the problem generator is to gather information about the environment by suggesting actions to the performance element that temporarily violate rationality. Since the problem generator can suggest arbitrary actions for the sake of exploration, the performance measure is not the only input considered when the agent selects an action, and so the the action may depend on the time even though the performance measure does not. Note that we should not assume that we may evaluate the performance measure on or before epoch T (imo).

Intuitively, suppose we have been without water for 2 days and there is a small but insufficient drizzle of water on a rock nearby. We are in the vicinity of 2 hills. Across each hill, there may be a well or a lake. There may also be a water source upstream from the rock-drizzle, but the origin of the rock-drizzle may be underground. Collaboratively, we may choose to investigate each hill or the rock-drizzle, or continue taking turns licking the rock. Independently, we may also restrain or kill each other to increase our licking time. There's a lot of creativity involved here, so feel free to make up your own situation involving necessary resources. A funny bit is to make up a situation like this where the objective is a luxury (imagine we are at the mall..... :)

---
Tags: artificial-intelligence
---


# Question
Title: Finding a subset in bipartite graph violating Hall's condition
We are given a bipartite graph of $n \leq 200$ vertices in both the first and the second partite set. Let $U$ be some set of vertices in the first set, and $V$ those vertices from the second that are conected to some of the vertices from $U$. If for every choice of $U$ we have $|U| \leq |V|$ (Hall's condition) then there exists a perfect matching (Hall's theorem).

But in our graph we know there is no such matching. That means there exists some set of vertices $U$ violating Hall's condition, and I'd like to find it with complexity around $O(n^3)$ - hints instead of full solutions are most welcome.

What I already tried was finding the maximum matching first, and then searching for our subset, but I couldn't figure out how to do this. Also, I thought of ways of reducing this problem to some max-flow (as you do with the maximum matching) but it also seemed to me like a dead end.

# Answer
Let $G=(X,Y,E)$ be a bipartite graph with $|X|=|Y|=n$ having a maximum matching $M$. Consider the directed graph $G'$ on the vertex set $X \cup Y$ which includes the edges of $G$ oriented from $X$ to $Y$ and the edges of $M$ oriented from $Y$ to $X$. Let $U \subseteq X$ be the set of vertices of $X$ unmatched in $M$, and let $S$ be the set of vertices reachable from $U$ in $G'$. Then $|N(S \cap X)| = |S \cap X| - (n-|M|)$.

For the proof, let us first notice that $|N(S \cap X)| \geq |S \cap X| - (n-|M|)$, since otherwise each matching would have to miss more than $n-|M|$ vertices of $S \cap X$. It remains to show that $|N(S \cap X)| \leq |S \cap X| - (n-|M|)$. The idea is to show that $|X \setminus S| + |S \cap Y| \leq |M|$. Given this, note that by definition $N(S \cap X) = S \cap Y$, and so $$ |N(S \cap X)| = |S \cap Y| \leq |M| - |X \setminus S| = |M| - (n-|S \cap X|) = |S \cap X| - (n-|M|). $$

To finish the proof, we show that $|X \setminus S| + |S \cap Y| \leq |M|$. We do this by showing that each vertex in both of these sets belongs to $M$. For each $(x,y) \in M$, if $y \in S$ then $x \in S$, showing that at most one vertex is counted in $|X \setminus S| + |S \cap Y|$ for each edge in the matching, proving the inequality. It is clear that each vertex in $X \setminus S$ belongs to $M$, since by definition unmatched vertices belong to $S$. The crux of the proof is showing that each vertex in $S \cap Y$ belongs to $M$. Indeed, if some $y \in S \cap Y$ didn't belong to $M$, then the path proving that $y \in S$ is an augmenting path for the matching: if we remove all edges going from $Y$ to $X$ on the path and replace them by all edges going from $X$ to $Y$ on the path then we obtain a matching with one more edge than before. Since we assumed that $M$ is a maximum matching, this is impossible, completing the proof.
> 7 votes

# Answer
Here is an alternative answer. I will be happy to know if it is correct.

Let the bipartite graph be $(X+ Y, E)$. Consider the integer linear program:

\begin{align} \text{maximize} && \sum\_{i\in X} x\_i - \sum\_{j\in Y} y\_j \\ \text{subject to} && x\_i - y\_j \leq 0 && \forall (i,j)\in E \\ && x\_i\in\\{0,1\\} && \forall i\in X \\ && y\_j\in\\{0,1\\} && \forall j\in Y \end{align} In this program, there is a variable $x\_i$ for each node $i$ in $X$, and a variable $y\_j$ for each node $j$ in $Y$. Let $S$ be the subset of $X$ defined by $\\{i\in X: x\_i=1\\}$, and $T$ the subset of $Y$ defined by $\\{j\in Y: y\_j=1\\}$.

The constraints $x\_i - y\_j \leq 0$ ensure that, if some vertex $i$ is in $S$, then all its neighbors are in $T$, so $T\supseteq N(S)$. The objective is to maximize the difference $|S|-|T|$. If the objective is positive, then $|S|\>|T| \geq |N(S)|$, so $S$ is the Hall violator that we are looking for; otherwise, there is no Hall violator.

In general, integer linear programs are hard to solve. But in this case, the matrix of constraints is Totally unimodular. It satisfies the Hoffman-Gale conditions:

* Every entry in the matrix is one of $+1, 0, -1$;
* Every row in the matrix contains at most two nonzero entries.
* In every row, there are no two nonzero entries with the same sign: every row contains exactly one $+1$ and one $-1$ and the rest are zeros.

Therefore, the LP relaxation of this ILP has an integral solution. So we can solve this LP in polynomial time and use the solution to construct the Hall-violator $S$.

Is this algorithm correct?
> 0 votes

---
Tags: graphs, network-flow, bipartite-matching
---


# Question
Title: Detailed step of Dijkstra's algorithm performance analysis
Reading the book of Dasgupta-Papadimitriou-Vazirani.pdf about the performance of Dijkstra's algorithm on Page 118, we are given:

> ### 4.4.3 Running time
>
> At the level of abstraction of Figure 4.8, Dijkstra's algorithm is structurally identical to breadth-first search. However, it is slower because the priority queue primitives are computationally more demanding than the constant-time `eject`'s and `inject`'s of BFS. Since `makequeue`takes at most as long as $|V|$ `insert` operations, we get a total of $|V|$ `deletemin` and $|V| + |E|$ `insert`/`decreasekey` operations. The time needed for these varies by implementation; for instance, a binary heap gives an overall running time of $O((|V|+|E|)\log |V|)$.

I understand that it has $|V|$ `insert` and `deletemin` operations but can someone please explain why we have $|V|+|E|$ `insert`/`decreasekey` operations? First of of all, why does one algorithm have TWO kinds of insert operations? If they are the same kind, then where can we learn more about what `decreasekey` actually does? The Wikipedia page doesn't seem to cover it much either (unless I missed or misunderstood it).

# Answer
> 0 votes
> Since makequeue takes at most as long as $|V|$ `insert` operations, we get a total of $|V|$ `deletemin` and $|V | + |E|$ `insert/decreasekey` operations.
> First of of all, why one algorithm has TWO kinds of insert operations, if they are the same kind, then where can we learn more about what `decreasekey` actually does?

No, there is only one kind of `insert` operation. We got

* $|V|$ `deletemin` operations.
* a total of at most $|V|+|E|$ operations, where each operation is either an `insert` operation or a `decreasekey` operation. We count these two kinds of operations together because it takes the same asymptotic time to do either one of them, $O(\log |V|)$. More specifically. we have
    + |V| `insert` operations during `makequeue`.
    + at most |E| `decreasekey` operations as each edge may or may not lead to a `decreasekey` operation.

# Answer
> 0 votes
In worst case the number of delete operations are bounded by O(V) and now for each delete operation you perform on each vertex you may have to perform in worst case O(V-1) decrease-key operation as it may be adjacent to V-1 vertex considering a complete graph. Now total number of decrease key operations are bounded by O(E).

vertex 1 ---\> v-1 decrease key (1 vertex removed from heap,added to visited)

vertex 2 ---\> v-2 decrease key (2 vertex removed from heap,added to visited)

vertex 3 ---\> v-3 decrease key

vertex 4 ---\> v-4 decrease key

.

.

.

vertex |V| ---\> 1 decrease key

total decrease key operations = $1+2+.....+(V-1) = O(V^2) = O(E)$

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


# Question
Title: What is wrong with this reduction from vertex cover to binary programming?
I am trying to polynomial-time reduce the decision version of vertex cover to the decision version of binary programming. Here are the problem statements.

**Vertex Cover Decision Problem**

Instance: A graph $G=(V,E)$ and an integer $k$.

Question: Does $G$ have a vertex cover of size at most $k$?

**Binary Programming Decision Problem**

Instance: An integer $m \times n$ matrix $A$, an integer $m$-vector $b$, and an integer $l$.

Question: Is there a a 0-1 $n$-vector $x$ with at most $l$ 1's such that $Ax \geq b$? Here $||x||\_1= \sum\_{i=1}^{n}x\_i$.

I found a supposed transformation here that makes $A$ an $|E| \times |V|$ matrix, where $a\_{e,v}=1$ if edge $e$ is incident on vertex $v$ and $0$ otherwise. It also sets $b$ to an all 1's vector and $l=k$.

This transformation works in one direction: if you have a vertex cover you can build $x$ by letting $x\_v=1$ if vertex $v$ is included in the vertex cover and $0$ otherwise. However, in the other direction I can easily create an example where $Ax \geq b$ but the 1's in $x$ do not create a vertex cover in the induced graph. Can anyone provide a hint as to how to correct this?

# Answer
Your example does not hold since the first entry of $Ax$, 0 is smaller than 1, the first entry of $b$.

$$ \begin{array}{c c c} &Ax & &b\\ & \begin{bmatrix}0 \\1 \\2 \\1 \\1\end{bmatrix} & \not\ge\ & \begin{bmatrix}1 \\1 \\1 \\1 \\1 \\\end{bmatrix} \end{array} $$

Please note the condition $Ax\ge b$ means every entry in $Ax$ is no less than the corresponding entry in $b$. In term of the corresponding problem, the vertex cover problem, it means every edge is incident to at least 1 vertex. It is not about the $L\_1$ norm; otherwise, it should be written as, for example, $||Ax||\_1\ge ||b||\_1$.

Yes, we want to minimize the number of 1's in $x$, which is the same as minimizing $||x||\_1$. However, the condition $Ax\ge b$ is a requirement on $x$. The requirements on the variable that are usually read as "subject to ..." and the objective function could be seen as irrelevant or independent to each other.
> 1 votes

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


# Question
Title: Grover's Algorithm result when the desired element is not present
What does Grover's algorithm output when the desired element is absent from the database? Since there will be no phase inversion, how exactly will the probabilities work?

# Answer
> 4 votes
When it is absent, it will just output one arbitrary state.

As it is not the desired element, you may repeat the search algorithm again (even in the case it was present, you could have measured another computational basis – the algorithm uses probability after all so that's why it may be necessary to repeat) and you will finally conclude that it is not present.

The inversion about average operator changes the amplitudes of the states $\alpha\_i$ to $$ - \alpha\_i + 2 \langle\alpha\rangle\\,, $$ where the last term is the average of the amplitudes. You see in the case of no marking, it has no effect, so all computational bases will have the same probability of being measured.

You can check the explanation in Nielsen and Chuang's book.

---
Tags: search-algorithms, quantum-computing
---


title: Finding a subset with few neighbors

text:
# Question
Title: Finding a subset with few neighbors
Given a bipartite graph $G(X+Y,E)$, how can I find a non-empty subset $Y'\subseteq Y$, such that $|N(Y')| \leq |Y'|$ (where $N$ is the set of neighbors)?

If $|Y|\geq |X|$ then the problem is easy - $Y'=Y$ satisfies the requirements. The interesting case is $|Y| \< |X|$. In this case a solution might not exist, for example here:

$$ x\_1 - y\_1 \\ x\_2 - y\_1 $$

the only subset of $Y$ that satisfies the requirement is $\emptyset$. Is there an efficient algorithm for deciding whether a solution exists, and if so, find one?

A possible first step is to find a maximum matching in the graph. If its size is less than $|Y|$, then by Hall's theorem there exists a $Y'\subseteq Y$ with $|N(Y')|\< |Y'|$, and it can be found efficiently, so we are done.

But if the size of the matching is $|Y|$, then... I am stuck.

RELATED PROBLEMS:

1. Finding a subset in bipartite graph violating Hall's condition: there, the problem is to find a subset with $|N(Y')|\< |Y'|$; here, the problem is to find a non-empty subset with $|N(Y')|\leq |Y'|$.
2. In bipartite expansion, the goal is to find a subset $Y'$ containing a fraction $\beta$ of the vertices of $Y$ which minimizes the size of $N(Y')$. The problem is hard to approximate. However, our problem is possibly easier, since we only require $Y'$ to be non-empty, and only require $|N(Y')|$ to be at most $|Y'|$ \- we do not try to minimize it.
3. In union minimization, we are given a set-system and an integer $k$, and the goal is to find $k$ sets such that their union is minimized. We can view the set-system as a bipartite graph with sets on one side and elements on the other side; then, the goal is to find a $Y'$ of size $k$, such that $|N(Y')|$ is minimized. This is hard to approximate, but again our problem is potentially easier since it does not insist on $k$ and does not require minimization.

So, can the problem be solved in polynomial time?

# Answer
I have an idea and will be happy to know if it is correct, or can be corrected.

Consider the integer linear program:

\begin{align} \text{maximize} && \sum\_{j\in Y} y\_j - \sum\_{i\in X} x\_i \\ \text{subject to} && y\_j - x\_i \leq 0 && \forall (i,j)\in E \\ && 0\leq x\_i \leq 1,~~ 0\leq y\_j \leq 1 && \forall i\in X, j\in Y \\ && x\_i\in \mathbb{Z},~~ y\_j\in\mathbb{Z} && \forall i\in X, j\in Y \end{align} In this program, there is a variable $x\_i$ for each node $i$ in $X$, and a variable $y\_j$ for each node $j$ in $Y$. Let $X'$ be the subset of $X$ defined by $\\{i\in X: x\_i=1\\}$, and $Y'$ the subset of $Y$ defined by $\\{j\in Y: y\_j=1\\}$.

The constraints $y\_j - x\_i \leq 0$ ensure that, if some vertex $j$ is in $Y'$, then all its neighbors are in $X'$, so $X'\supseteq N(Y')$. The objective is to maximize the difference $|Y'|-|X'|$. If the optimal solution is at least 0, then $|Y'|\geq |X'| \geq |N(Y')|$, so $Y'$ is the required set. On the other hand, if the optimal solution is negative, there is no such set.

In general, integer linear programs are hard to solve. But in this case, the matrix of constraints is Totally unimodular. It satisfies the Hoffman-Gale conditions: every entry in the matrix is one of $+1, 0, -1$; every row in the matrix contains at most two nonzero entries; and if there are two nonzero entries, they have opposite signs. Therefore, we can solve the LP without the integrality constraints, and we are guaranteed to get an integral solution which gives us $Y'$.

The only problem is that the above LP does not guarantee that $Y'$ is non-empty. Adding a constraint such as $\sum\_{j\in Y} y\_j\geq 1$ would invalidate the argument of total-unimodularity. A possible solution is to solve $|Y|$ different linear programs: for each vertex $j\in Y$, solve the LP with the constraint $0\leq y\_j \leq 1$ replaced with the constraint $y\_j = 1$. If for some $j\in Y$ the objective is at least 0, we have found a non-empty $Y'$ as required. Otherwise, such $Y'$ does not exist.
> 2 votes

---
Tags: algorithms, graphs, bipartite-matching
---


# Question
Title: DFA - unsigned int with digits in non-decreasing order
I was hoping someone could help me in understanding how to achieve a DFA here. The question is how I would create a DFA that accepts unsigned decimal integers whose digits are in non-decreasing order, such as 1234, 1589? The numbers can't start with 0.

# Answer
> 1 votes
Think about how you'd determine yourself whether a number's digits are non-decreasing: you'd look at each digit in turn and remember each digit just long enough to check that the next digit is at least as big. You'll be happy as long as it always is at least as big, and sad if you find one that's smaller.1 So do the same with a DFA, using the currrent state to encode anything you need to remember.

---

1. OK, maybe you're not *that* emotionally invested in this problem...

---
Tags: finite-automata
---


# Question
Title: Can the test set of attributes be a subset of the training set's attributes?
I'm currently writing an application for a trick-based card game, where agents are assigned points based on the accuracy of their predictions of how many hands they're going to win. The number of tricks predicted will display a level of confidence to the other agents as well as also potentially allowing the agent to choose the Trump suit.

I've compiled a set of attributes (such as cards in hand, score sum total in hand) that will be useful in the prediction, but it would be ideal if I could include previous predictions in the training set.

My question is can my test data \[attributes\] be a subset of the training data \[attributes ∩ predictions\] both of which are predicting the number of hands that the agent will win?

# Answer
Well, if the test data would be the same from training data, your machine learning algorithm may overfit. Because you test your model with your training data it may perform very well, as it may see the pattern even in noise. And then it won't generalize on new data.

You should separate the test data (with which you see the accuracy) to the training data.
> 1 votes

---
Tags: machine-learning
---


title: Numbering of vertices in RAM model

text:
# Question
Title: Numbering of vertices in RAM model
I have read few research papers in which given a graph $G$ where $V$ denotes its vertex set and $E$ denotes its edge set. Model of computation is word RAM. "Without loss of generality assume that vertices are numbered from $1$ to $n$"

Question : How to justify the above mentioned assumption? I am not getting why this assumption is valid?

# Answer
> 2 votes
Typically, graph problems don't depend on the "names" of the vertices. Finding a route from Paris to Berlin doesn't get any easier or harder if you rename the cities Sirap and Nilreb, or 6 and 32, or anything else. Indeed, in many cases, the vertices of the graph don't even have explicit names: they're just a set. Since changing the names of the vertices makes no difference, an algorithm doesn't become less powerful by assuming that the names are $1, \dots, n$, where $n$ is the total number of vertices. That is, there is no loss of generality in doing this.

$1, \dots, n$ is a useful choice of names because computers are good at dealing with numbers and because, typically, the vertices will be stored in some kind of array anyway (an array of adjacency lists or just an adjacency matrix). It makes sense to name the vertex after the array cell it occupies, so that the algorithm never has to worry about the distinction between "vertex $x$" and "the place where vertex $x$ is stored".

---
Tags: computation-models
---


# Question
Title: Understanding connection between minimum spanning tree, shortest path, breadth first and depth first traversal
In CLRS, in the later part of breadth first search topic, for unweighted graphs, it says:

> At the beginning of this section, we claimed that breadth-first search finds the distance to each reachable vertex in a graph $G=(V,E)$ from a given source vertex $s \in V$ . Define the **shortest-path distance** $\delta(s,v)$ from $s$ to $v$ as the minimum number of edges in any path from vertex $s$ to vertex $v$; if there is no path from $s$ to $v$, then $\delta(s,v)=\infty$. We call a path of length $\delta(s,v)$ from $s$ to $v$ a shortest path from $s$ to $v$.

So for many months, I was content with the fact that for unweighted path, BFS gives shortest path. But today I came across problem asking whether breadth first search gives minimum spanning tree for unweighted graph. I was like, BFS gives shortest path not the minimum spanning tree. And to my surprise I was wrong. Somehow, stupidly, I assumed what CLRS stated was the only connection among minimum spanning tree, shortest path, depth first search and breadth first search, because I was subconsciously thinking that its not given in CLRS (in any of four sections), then it should not be the case. I did not give any extra thought for evaluating any possible connection. But now I want to know what all are the connection.

I have done quick google and found many links, some of which are:, , .

My conclusion is:

> For unweighted graph,
>
> 1. Breadth first search gives both minimum spanning tree and shortest path tree.
> 2. Depth first search gives only minimum spanning tree but not the shortest path tree.

Now I have further small doubts:

> 3. I know for weighted graph MST and SPT are not same. But are they same for unweighted graph? Somehow I feel no, as otherwise point 2 will be wrong, and DFS would have given both MST and SPT for unweighted graph. However I am not able to come up with the unweighted graph for which MST and SPT are different.
> 4. MSTs given by BFS and DFS on given unweighted graph may be different, its just that the number of edges contained in them will be the same.

Which of above points are correct and which are wrong?

# Answer
In fact, a MST is a subset of the edges building a tree (thus without cycle) using the minimum edge weights. It has exactly N-1 edges for a N nodes graph.

It may exist several different MST for the same graph. For an unweighted graph, which is in other way a graph with weight 1 on every edges, the total weight of any spanning tree is N-1. Thus any spanning tree is a MST.

When you use BFS or DFS to explore a graph, you build an exploration tree, which is the shortest path tree for BFS. And if the graph is unweighted, you can say this tree is a MST, yes so **1.** and **2.** are true.

**3.** is true, MST and SPT are different. Just make BFS and DFS on a 3-clique (3 nodes connected to each other) to have an example.

**4.** is true but remember that "minimum" adds no information to any spanning tree of an unweighted graph. And also that a N nodes tree has exactly N-1 egdes.
> 0 votes

# Answer
Just putting Vince's answer in more structured manner:

* (Q4) SPT and MST, both being trees, they have same number of edges for unweighted graph, i.e. $n-1$
* (Q1,2) Thus, as long as we have a tree connecting all vertices and thus having n-1 edges, we are ending up with MST, whatever the procedure is followed.
* (Q3) In unweighted graph, SPT will be a MST (as both have same total weight, and total weight is the only constraint put by MST), but reverse is not true (as SPT requires distance from source vertex to every other vertex to be minimum, which is not considered by MST), which can be seen from 3-clique:

* (Q1,2) As can be seen from above, BFS gives SPT which also happen to be MST. But DFS gives MST which may not be a SPT.
> 0 votes

---
Tags: graphs, shortest-path, minimum-spanning-tree
---


# Question
Title: Is there a relation between the size of the domain/range of a function and its computability?
This was a question given in a course, without answer. The referenced literature (just a few books) do not cover it, unfortunately.

I think there is no relation with the range as the range of the Halting problem is {0,1} and the range of the successor function is infinite. But I feel like I'm missing some subtleties here.

# Answer
(**Note:** As mentioned by Apass.Jack in the comments, there are apparently two different usages of the terms "domain" and "range". In this answer, I adopt the usages which I am more familiar with. That is, given a function $f\colon X \to Y$ (i.e., $f \subseteq X \times Y$), $X$ is the *domain of $f$* in the sense that $f(x)$ is defined for all $x \in X$; similarly, the *range* (or *codomain*) $Y$ is a set such that $f(x) \in Y$ for all $x \in X$. Additionally, every function is total; partial functions are explicitly denoted as such.)

---

Let $f\colon X \to Y$ be a function. The question is: What can we say about the computability of $f$ (strictly) based on $|X|$ and $|Y|$? The following is more or less a structured breakdown of what I have written in the comments:

## Domain

* Case 1: $|X|$ is finite. Then the values $f(x)$ of $x \in X$ may be hardcoded (e.g., as a lookup table) in an algorithm to compute $f$.
* Case 2: $|X|$ is infinite. There are plenty of both computable and uncomputable functions in this case.

## Range

If $Y$ is such that the image $\text{im}(f) = \\{ f(x) \mid x \in X \\}$ of $f$ is a *proper* subset of $Y$, then there is not much that can be said about $f$ (e.g., $Y$ could be an infinite set but $f = \\{ \\}$ the empty function; see Case 1 below). Thus, let us assume $\text{im}(f) = Y$ holds.

* Case 1: $|Y| = 0$. Then $f$ must be the empty function $\\{ \\}$, which indicates $|X| = 0$; see "Domain", Case 1.
* Case 2: $|Y| = 1$. $f$ is computable by an algorithm which ignores its input and outputs the only possible value for $f$.
* Case 3: $|Y| \ge 2$ but $|Y|$ finite. An example of an uncomputable $f$ is, for instance, the membership relation for the halting problem (as mentioned in the question) or any non-recursive (i.e., undecidable) language; similarly, a computable $f$ would be the membership relation for a recursive (i.e., decidable) language.
* Case 4: $|Y|$ infinite. As in case 3, there are both computable and uncomputable choices for $f$. For example, $X = Y$ and $f = \text{Id}\_X$ is trivially computable. An uncomputable example for $f$ (off the top of my head) would be the busy beaver function.

It is possible to extend these results if further assumptions are made about $X$, $Y$, and $f$. In the general case, however, this is as much (and it is not much, I know) we can say about the computability of $f$.

---

If we are dealing with a partial function $f \subseteq X \times Y$ instead, note there is always a (maximal) $X' \subseteq X$ such that $f \subseteq X' \times Y$ is a (total) function $X' \to Y$. As pointed out by chi in the comments, it might be tempting to say we may simply generalize the above discussion by considering the total restriction of $f$ instead. This does not work, however, since, for example, the partial function $f \subseteq \mathbb{N}\_0 \times \\{ 1 \\}$ with $f(x) = 1$ if and only if TM number $x$ does not halt is not computable, despite its image having a single element (cnf. "Range", Case 2). Nevertheless, note this is the only case in which the generalization fails.
> 3 votes

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


title: Number of min-cuts of a graph

text:
# Question
Title: Number of min-cuts of a graph
It can be shown that every graph G has at most $\binom{n}{2}$ min-cuts. It follows from Karger’s algorithm Analysis.

Is there a different combinatorial proof of this fact? Was this known before Karger’s paper?

# Answer
> 1 votes
An earlier proof that associates to an arbitrary graph G a certain "structural graph" was shown by Dinitz, Karzanov and Lomonosov in 1976 \[1\].

---

\[1\] Dinitz, E. A., Karzanov, A. V., & Lomonosov, M. V. (1976). On the structure of the system of minimum edge cuts in a graph. *Issledovaniya po Diskretnoi Optimizatsii*, 290-306.

---
Tags: graphs, algorithm-analysis
---


# Question
Title: Constructing PDA to accept language $\{a^ib^j \mid 0 \leq j \leq 2i\}$
How can I construct a PDA which accepts the language $\\{a^ib^j \mid 0 \leq j \leq 2i\\}$?

# Answer
> 1 votes
The description of the PDA is easy:

> Read the input string. if read $b$ and the stack is empty, reject the string. If see $a$, push two $a$ to the stack. If read $b$, pop a value from the stack. Finally, if read the end of the string, it will be accepted.

---
Tags: pushdown-automata
---


# Question
Title: Rice's theorem applicable to the following language?
Let $L= \\{\langle M \rangle \mid M \text{ halts on } \langle M \rangle \\} $ be a language where $\langle M \rangle$ is the Code of the TM $M$. $L$ is undecidable.

I've heard that I can't use Rice's theorem to proof its undecidability.

But why? I can construct a set $S = \\{f\_M \mid f\_M(\langle M \rangle)\in \\{0,1\\}\\}$.

It's clear that $S$ is not empty and $S$ contains not every TM.

# Answer
Because there may be multiple $M$'s corresponding to the same $f\_M$. That is to say, you cannot deduce $\langle M\rangle$ from $f\_M$, so you cannot describe $S$ in this way.
> 0 votes

---
Tags: complexity-theory, turing-machines, computability, undecidability, rice-theorem
---


# Question
Title: How is Johnson's shortest path weighting function $\hat{w}(u, v) = w(u, v) + h(u) - h(v)$ proven by the triangular inequility?
Recap to the Johnson's shortest path algorithm:

By the procedure extending the original graph $G^\prime = (V^\prime, E^\prime), V^\prime = V\ \cup \\{s\\}, E^\prime = E\ \cup \\{(s, v)\ |\ \forall v \in V\\}$, and then extend the original weighting function $\forall x \in V,\ w(s, x) = 0.$

Finally define the **reweighted** function $\hat{w}(u, v) = w(u, v) + h(u) - h(v)$ where $\forall x \in V,\ h(x) = d(s, x)$ , where $d(s, x)$ is the shortest path from $s$ to $x$.

Problem:

Assume that there is no negative cycle in the graph. The textbook Introduction to Algorithms says that $w(u, v) + h(u) - h(v)$ is always **nonnegative** proven by using the **triangular inequality theorem** to get $w(u, v) + h(u) \ge h(v)$.

This makes me so confused, because **I think that there could exist negative weights in the graph and hence triangular inequality can't be applied.** (Am I misunderstanding triangular inequality? Or something are skipped I cannot tell?).

Where did I misunderstand about this algorithm? Thanks!

# Answer
> 2 votes
You're right that you can't (necessarily) apply the triangle inequality to the edges of the original graph, but that's not what's being discussed here.

We know $h(u)$ is, by definition, the shortest path to $u$. Thus we immediately know that $w(u,v) + h(u) \geq h(v)$ because, if it wasn't true, $h(v)$ would not be the shortest path to $v$. The author is calling this the "triangle inequality" of the reweighted graph.

---
Tags: shortest-path, weighted-graphs
---


# Question
Title: Quicksort Partitioning: Hoare vs. Lomuto
There are two quicksort partition methods mentioned in Cormen:

(the argument `A` is the array, and `[p, r]` is the range, inclusive, to perform the partition on. The returned value is the index to the pivot after the partition.)

```
Hoare-Partition(A, p, r)
x = A[p]
i = p - 1
j = r + 1
while true
    repeat
        j = j - 1
    until A[j] <= x
    repeat
        i = i + 1
    until A[i] >= x
    if i < j
        swap( A[i], A[j] )
    else
        return j

```

and:

```
Lomuto-Partition(A, p, r)
x = A[r]
i = p - 1
for j = p to r - 1
    if A[j] <= x
        i = i + 1
        swap( A[i], A[j] )
swap( A[i + 1], A[r] )
return i + 1

```

Disregarding the method of choosing the pivot, in what situations is one preferable to the other? I know for instance that Lomuto preforms relatively poorly when there is a high percentage of duplicate values ( i.e. where say more than 2/3rds the array is the same value ), whereas Hoare performs just fine in that situation.

What other special cases make one partition method significant better than the other?

# Answer
> 124 votes
# Pedagogical Dimension

Due to its simplicity Lomuto's partitioning method might be easier to implement. There is a nice anecdote in Jon Bentley's *Programming Pearl* on Sorting:

> “Most discussions of Quicksort use a partitioning scheme based on two approaching indices \[...\] \[i.e. Hoare's\]. Although the basic idea of that scheme is straightforward, I have always found the details tricky - I once spent the better part of two days chasing down a bug hiding in a short partitioning loop. A reader of a preliminary draft complained that the standard two-index method is in fact simpler than Lomuto's and sketched some code to make his point; I stopped looking after I found two bugs.”

# Performance Dimension

For practical use, ease of implementation might be sacrificed for the sake of efficiency. On a theoretical basis, we can determine the number of element comparisons and swaps to compare performance. Additionally, actual running time will be influenced by other factors, such as caching performance and branch mispredictions.

As shown below, the algorithms behave very similar on random permutations **except for the number of swaps**. There Lomuto needs *thrice* as many as Hoare!

## Number of Comparisons

Both methods can be implemented using $n-1$ comparisons to partition an array of length $n$. This is essentially optimal, since we need to compare every element to the pivot for deciding where to put it.

## Number of Swaps

The number of swaps is random for both algorithms, depending on the elements in the array. If we assume *random permutations*, i.e. all elements are distinct and every permutation of the elements is equally likely, we can analyze the *expected* number of swaps.

As only relative order counts, we assume that the elements are the numbers $1,\ldots,n$. That makes the discussion below easier since the rank of an element and its value coincide.

### Lomuto's Method

The index variable $j$ scans the whole array and whenever we find an element $A\[j\]$ smaller than pivot $x$, we do a swap. Among the elements $1,\ldots,n$, exactly $x-1$ ones are smaller than $x$, so we get $x-1$ swaps if the pivot is $x$.

The overall expectation then results by averaging over all pivots. Each value in $\\{1,\ldots,n\\}$ is equally likely to become pivot (namely with prob. $\frac1n$), so we have

$$ \frac1n \sum\_{x=1}^n (x-1) = \frac n2 - \frac12\\;. $$

swaps on average to partition an array of length $n$ with Lomuto's method.

### Hoare's Method

Here, the analysis is slightly more tricky: Even fixing pivot $x$, the number of swaps remains random.

More precisely: The indices $i$ and $j$ run towards each other until they cross, which *always* happens at $x$ (by correctness of Hoare's partitioning algorithm!). This effectively divides the array into two parts: A left part which is scanned by $i$ and a right part scanned by $j$.

Now, a swap is done exactly for every *pair* of “misplaced” elements, i.e. a large element (larger than $x$, thus belonging in the right partition) which is currently located in the left part and a small element located in the right part. Note that this pair forming always works out, i.e. there the number of small elements initially in the right part equals the number of large elements in the left part.

One can show that the number of these pairs is hypergeometrically $\mathrm{Hyp}(n-1,n-x,x-1)$ distributed: For the $n-x$ large elements we randomly draw their positions in the array and have $x-1$ positions in the left part. Accordingly, the expected number of pairs is $(n-x)(x-1)/(n-1)$ given that the pivot is $x$.

Finally, we average again over all pivot values to obtain the overall expected number of swaps for Hoare's partitioning:

$$ \frac1n \sum\_{x=1}^n \frac{(n-x)(x-1)}{n-1} = \frac n6 - \frac13\\;. $$

(A more detailed description can be found in my master's thesis, page 29.)

## Memory Access Pattern

Both algorithms use two pointers into the array that scan it *sequentially*. Therefore both behave almost optimal w.r.t. caching.

## Equal Elements and Already Sorted Lists

As already mentioned by Wandering Logic, the performance of the algorithms differs more drastically for lists that are not random permutations.

On an array that is already sorted, Hoare's method *never* swaps, as there are no misplaced pairs (see above), whereas Lomuto's method still does its roughly $n/2$ swaps!

The presence of equal elements requires special care in Quicksort. (I stepped into this trap myself; see my master's thesis, page 36, for a “Tale on Premature Optimization”) Consider as extreme example an array which filled with $0$s. On such an array, Hoare's method performs a swap for *every* pair of elements - which is the worst case for Hoare's partitioning - but $i$ and $j$ always meet in the middle of the array. Thus, we have optimal partitioning and the total running time remains in $\mathcal O(n\log n)$.

Lomuto's method behaves much more stupidly on the all $0$ array: The comparison `A[j] <= x` will always be true, so we do a swap for *every single element*! But even worse: After the loop, we always have $i=n$, so we observe the worst case partitioning, making the overall performance degrade to $\Theta(n^2)$!

# Conclusion

Lomuto's method is simple and easier to implement, but should not be used for implementing a library sorting method.

---

## Clarification

In this answer, I explained why a *good implementation* of the “crossing-pointer scheme” from Hoare's partitioning method is superior to the simpler scheme of Lomuto's method, and I stand by everything I said on that topic.
Alas, this is strictly speaking *not* what the OP was asking!

The pseudocode for `Hoare-Partition` as given above does *not* have the desirable properties I lengthily praised, since it fails to exclude the pivot element from the partitioning range. As a consequence, the pivot is “lost” in the swapping and cannot be put into its final position after partitioning, and hence be excluded it from recursive calls. (That means the recursive calls do no longer fulfill the same randomness assumptions and the whole analysis seems to break down! Robert Sedgewick's PhD dissertation discusses this issue in detail.)

For pseudocode of the desirable implementation analyzed above, see my master's thesis, Algorithm 1.(That code is due to Robert Sedgewick).

# Answer
> 8 votes
Some comments added to the excellent Sebastian answer.

I'm going to talk about the partition rearrangements algorithm in general and not about its particular use for *Quicksort*.

## Stability

Lomuto's algorithm is *semistable*: the relative order of the elements not satisfying the *predicate* is preserved. Hoare's algorithm is unstable.

## Element Access Pattern

Lomuto's algorithm can be used with singly linked list or similar forward-only data structures. Hoare's algorithm needs *bidirectionality*.

## Number of Comparisons

Lomuto's algorithm can be implemented performing $n-1$ applications of the *predicate* to partition a sequence of length $n$. (Hoare's too).

But in order to do this we have to sacrifice 2 properties:

1. The sequence to be partitioned must not be empty.
2. The algorithm is unable to return the partition point.

If we need any of these 2 properties, we will have no choice but to implement the algorithm by making $n$ comparisons.

---
Tags: algorithms, sorting, quicksort
---


# Question
Title: Where are C++ templates inside of the lambda cube?
C++ templates have type variables and can express lambdas, so they must have System F embedded. But is that exactly where they are located in the lambda cube? Can C++ templates produce new types or express dependent types?

(I originally posted this to Stack Overflow, but they referred me over to here.)

# Answer
> But is that exactly where they are located in the lambda cube?

The lambda cube is not a giant spectrum on which all programming languages can be classified. It is precisely eight languages, which combine a lambda calculus (values abstracted over values) with all possible combinations of three features:

* Values abstracted over types (parametric polymorphism)
* Types abstracted over types (kinds / type constructors)
* Types abstracted over values (dependent types)

So, the C++ template language isn't anywhere on the lambda cube, since it isn't any of those 8 languages.

The second thing to keep in mind is that we can't mix up C++ features and C++ template features. Just because C++ has lambdas, this doesn't (necessarily) mean that its template language has them.

It *is* possible to ask, which of the three lambda-cube features does C++ have? It would seem that it features the full power of the lambda cube, but I'm not enough of a C++ expert to know for sure.
> 11 votes

---
Tags: programming-languages, type-theory, dependent-types, c++, calculus-of-constructions
---


# Question
Title: Algorithm to find the two closest elements in a BST
For example, consider an AVL tree:

Performing the two\_close(T) should give back (13, 12), as they are the closest elements together. Said another way, you can take any two **other** elements in the tree, and their absolute difference will always be greater or equal to that of the result:

$|c\_1-c\_2|\leq |o\_1-o\_2|$, where $c\_i$ are the two closest elements, and $o\_i$ are any other two elements in the three.

I'm trying to think of an algorithm for this that can be done is O(log n). I can modify the nodes to store additional information, but not sure what I could use.

Specifically the algorithm, I am not sure about. Visually its evident, but algorithm wise I would like a hint.

# Answer
In most common models of computation, it cannot be ensured to find the two closest elements in a binary search tree (BST) in $O(\log n)$ time or, in fact, in $o(n)$ time. Here $n$ is the number of elements in BST and $o(n)$ is the little $o$-notation.

The idea is simple. There must be enough running time for an algorithm to access at least about half of the elements.

Here is an detailed explanation. It is not rigorous; to make it rigorous we will need an explicit adversary argument as well as a more detailed formal specification of the model of computation.

---

Let us fix some model of computation $M$ in which at most $c$ elements can be accessed in a unit time of computation for some constant $c$. In fact, $c$ is usually 1 or 2.

For the sake of contradiction, suppose algorithm $Alg$ can find the two closest elements in a BST of $n$ element in $o(n)$ time. So for constant $\dfrac1{3c}$, there exists a constant $n\_0\>0$ such that $A$ can find the two closest element in no more than $\dfrac1{3c}n$ time for all $n\>n\_0$.

Now let $n\_1\>\max(n\_0, 6)$. Let $Alg$ runs on a BST with $n\_1$ nodes for some time that is no more than $\dfrac1{3c}n\_1$. Then $A$ has accessed at most $\dfrac{1}{3c}n\_1\cdot c=\dfrac {n\_1}3$ elements. Let $a\_1, a\_2, \cdots, a\_{n\_1}$ be the elements in the BST in nondecreasing order. There must be at least 2 adjacent elements in that nondecreasing list of all elements none of which have been accessed by the algorithm. Those two elements mights be closer to each other than any pair of elements among the elements that have been accessed by $Alg$. That means, $Alg$ may not have found the two closest elements. This is a contradiction.

---

**Exercise.** Find the two closest elements in a binary search tree with left-child pointers, right-child pointers and parent pointers in $O(1)$ working space.
> 1 votes

---
Tags: algorithms, complexity-theory, trees, binary-trees
---


# Question
Title: Why Cook-Levin thorem's proof can mean SAT's NP-Hardness
I'm studying about Cook-Levin theorem but there is a problem I faced. Cook-Levin theorem shows that any NPTM can be encoded as a boolean formula. About given language $A$, instance $w$, and NPTM $M$ that decides $A$, I understand that when a boolean formula $φ$ is true when $M$ accepts $w$ and false when $M$ rejects $w$, decision problem $w∈A?$ will be the same problem as $φ=true?$. But I am confused that can we actually certificate existence of reduction from any other NP problem to SAT, with Cook-Levin theorem. I can't make actual Karp reduction to SAT that doesn't picky about where the reduction comes from, so I can't tell that SAT is in NP-Hard. Please help me to understand why conversion to boolean formula can mean SAT's NP-Hardness...

# Answer
Any language $L$ in NP is decided by some nondeterministic Turing machine $M$. By Cook–Levin, the problem "Does $M$ accept input $x$?" can be decided by constructing a Boolean formula $\varphi\_{M,x}$ that is satisfiable if, and only if, $M$ accepts $x$. Hence $L$ reduces to SAT, so SAT is NP-hard.
> 3 votes

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


title: Whether TM accepts epsilon?

text:
# Question
Title: Whether TM accepts epsilon?
$L = \\{ \langle M \rangle \mid \epsilon \in L(M) \\}$, where $M$ is any Turing machine.

Why is the above problem undecidable? Can't we just check whether the initial state is a final state and say the TM accepts $\epsilon$ if the initial state is the final state else it doesn't? We can also just check if the TM goes to an accepting state on the blank symbol.

# Answer
> 4 votes
First, a note on notation: $L(M)$ is a language which is a set. Languages don't accept or reject, Turing machines do. You can either say "$\epsilon \in L(M)$" or "$M$ accepts $\epsilon$".

There are many Turing machines in this language that don't meet your description. For example, imagine a machine that upon reading a blank goes and writes, say, 111 and then accepts. The initial state does not need to have a transition to an accept state on a blank symbol in order to belong in this language.

Here's another perspective on why this language is undecidable using Kleene’s Recursion Theorem. Imagine that there is some decider $D$ that, given the description of a TM $\langle M \rangle$, $D$ accepts if $M$ accepts $\epsilon$ and rejects otherwise. Now create a Turing machine with the following behavior:

```
Get my own description <M> and then run D on <M>.
If D accepts <M>:
   If input is empty, reject. Otherwise accept.
Else:
   If input is empty, accept. Otherwise reject.

```

The existence of this decider allows us to create the above Turing machine which is a contradiction. Essentially, if the decider says the Turing machine is supposed to accept the empty string, it then goes and rejects and if it's supposed to reject, it then goes and accepts. This idea of being able to use self-reference and ask "What am I about to do?" and then doing the opposite shows that no single machine can predict behavior of all others.

# Answer
> 2 votes
Consider a TM $M$ that, on input $\epsilon$, computes $3654^{256}$, divides it by two, and then accepts.

Then $\langle M \rangle \in L$, even if $M$ does *not* get to the accepting state on blank. Before reaching the accept state it does a lot of computation, traversing many states and writing a lot of data on the tape.

# Answer
> 0 votes
As this question is related to recursively enumerable set, we can use Rice's theorem.

Rice's theorem 1. Any **non trivial property** of Recursively enumerable set is undecidable. Note the word non trivial, so if you can give two sets suppose yes instance and no instance with respect to Recursively enumerable set of TM , then the problem is undecidable. Here yes instance : L = {epsilon} No instance : L = {00,01,10,...} Here instance means property which is asked in your question. Here as we have shown it is a non trivial property. This problem is undecidable.

# Answer
> -1 votes
$M$ may be doing computations regardless of the input, rather then checking then first checking it and secondly compute things accordingly

# Answer
> -1 votes
Consider a turing machine, Take just blank on the input tape, Turing machine could have moves just on blank and could loop infinitely without it being decidable whether it accepted epsilon or not

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


# Question
Title: Bounds on "well dispersed" sparse matrices
Suppose we have an $n\times n$ zero/one matrix $M$, with $k$ ones. Let us say that the *extent* of $M$ is the maximum of $i+j$ over all ones at positions $(i,j)$ of the matrix, and the *quality* $q(M)$ is the minimum of the extent of $PMQ$ taken over all permutation matrices $P$ and $Q$. Let $f(n,k)$ be the maximum of $q(M)$ over all matrices $M$ with $k$ ones. What bounds can we give on $f(n,k)$?

Specifically, I am interested in finding whether there are any matrices $M$ with $k=O(n)$, such that $q(M)\ge (1+\epsilon)n$ for some $\epsilon\>0$, i.e. $f(n,k)\ge (1+\epsilon)n$.

> Is it possible to achieve $f(n,k)\ge (1+\epsilon)n$ for $k=O(n)$?

Less formally, we have a grid that we can fill with a small number of dots, and the adversary is allowed to permute rows and columns in order to prevent the bottom corner from being filled. For example, I can have a matrix like

\begin{matrix} \bullet&\cdot&\cdot&\cdot&\bullet\\ \cdot&\bullet&\cdot&\cdot&\bullet\\ \cdot&\cdot&\bullet&\cdot&\bullet\\ \cdot&\cdot&\cdot&\bullet&\bullet\\ \bullet&\bullet&\bullet&\bullet&\cdot\\ \end{matrix}

and the adversary can permute this to \begin{matrix} \cdot&\bullet&\bullet&\bullet&\bullet\\ \bullet&\cdot&\cdot&\cdot&\bullet\\ \bullet&\cdot&\cdot&\bullet&\cdot\\ \bullet&\cdot&\bullet&\cdot&\cdot\\ \bullet&\bullet&\cdot&\cdot&\cdot\\ \end{matrix} so this matrix gets a quality of $6$. We want to distribute the dots so the quality is as large as possible.

Here are some observations:

* $f(n,k)\le 2n$ trivially
* $f(n,k)=2n$ only for $k=n^2$. This is because if $M$ has less than $n^2$ ones, then there is a spot containing a zero, which can be moved to the corner by a permutation.
* $f(n,n)=n+1$. The identity matrix has $n$ ones, and all permutations of the identity matrix are permutation matrices. The best the adversary can do on a permutation matrix is put all the ones on the antidiagonal, which has $i+j=n+1$ for each of its ones.
* $f(n,n+m^2-m)\ge n+m$: Similar to the above, where we use a $m\times m$ block of ones followed by ones on the diagonal. Permutations cannot break up the block, so the best option for the adversary is to put it on the antidiagonal, where it will extend out beyond the antidiagonal by $m$, like so: \begin{matrix} \cdot&\cdot&\cdot&\cdot&\bullet\\ \cdot&\cdot&\cdot&\bullet&\cdot\\ \bullet&\bullet&\bullet&\cdot&\cdot\\ \bullet&\bullet&\bullet&\cdot&\cdot\\ \bullet&\bullet&\bullet&\cdot&\cdot\\ \end{matrix}

# Answer
The answer to the main question is yes, and the key to the construction is the notion of an expander graph.

> A (bipartite $d$-left-regular) *expander graph* between vertices $\mathcal{I}$ and $\mathcal{O}$ (the bipartition), where $|\mathcal{I}|=|\mathcal{O}|=n$, with expansion factor $c\>0$, is a graph which is $d$-left-regular, meaning that each $x\in \mathcal{I}$ has degree $d$, such that for all subsets $A\subseteq I$ such that $|A|\le n/2$, the set $B\subseteq\mathcal{O}$ of neighbors of elements of $A$ has $|B|\ge (1+c)|A|$.

There are many proofs of existence of expander graphs like this by the probabilistic method and some deterministic methods as well; for the present purpose we only need that expander graphs as defined above exist for some constant $c\>0$ independent of $n$.

Given such a graph, we can construct a $n\times n$ matrix from the adjacency matrix of the graph, with $\mathcal{I}$ for the rows and $\mathcal{O}$ for the columns. This matrix has exactly $k=dn=O(n)$ ones, because of the $d$ left regular property, and the expander property is unaffected by any permutations performed by the adversary.

Now for $\alpha\>0$, let $A$ be the last $\alpha n$ elements of $\mathcal{I}$ and let $C$ be the last $\alpha n$ elements of $\mathcal{O}$, after the adversary has chosen an ordering of the rows and columns. If there is no one in this square in the matrix, then there must correspondingly be no edge between $A$ and $C$, and hence the neighbors $B$ of elements of $A$ must satisfy $B\subseteq C^c$, so by the expander graph property this implies $$(1+c)|A|=(1+c)\alpha n\le |B|\le |C^c|=(1-\alpha)n\implies \alpha\le\frac{1}{2+c}.$$

Thus any empty bottom right square must be smaller than $n/(2+c)\times n/(2+c)$, so in the language of the OP, $$f(n,k)\ge 2n\left(1-\frac{1}{2+c}\right)=(1+\epsilon)n$$ where $\epsilon=\dfrac{c}{2+c}\>0$.
> 1 votes

---
Tags: graphs, optimization, asymptotics, combinatorics
---


# Question
Title: Confusion in CLRS's version of Prim's algorithm
The algorithm is as follows:

```
MST-PRIM(G,w,r)
1   for each u ∈ G.V   //initialization
2      u.key = ∞
3      u.π = NIL
4   r.key = 0
5   Q = G.V          //end initialization
6   while Q ≠ ∅
7      u = EXTRACT-MIN(Q)
8      for each v ∈ G.Adj[u]
9         if v ∈ Q and w(u,v) < v.key
10           v.π = u
11           v.key = w(u,v)

```
* All vertices that are not in the tree reside in a min-priority queue `Q` based on a `key` attribute.
* `v.key` is the minimum weight of any edge connecting `v` to a vertex in the tree
* `v.π` points to the parent of `v` in the tree
* `G` is a graph, `w` is a weight function, `r` is a root

The example given is as follows:

I am confused, why in step (c), edge $(b,c)$ is added instead of edge $(a,h)$. Below the diagram, there is a note saying:

> In second step, the algorithm has a choice of adding either edge $(b,c)$ or edge $(a,h)$ to the tree since both are light edges crossing the cut.

However still I think that according to the line 8 in algorithm, all adjacent vertices of $a$ not in the tree must be added first to the tree. Thus $h$ should also get added immediately after $b$, before $c$. The line 8 says `for **each v** ∈ G.Adj[u]`(i.e. for each adjacent vertex $v$ of $u$), why only adjacent node $b$ of $a$ is considered, but not $h$ (which is also adjacent to $a$).

If what author says should occur, then there should be something like `break` construct on line 12 inside the `if` construct's body, which will result in exiting `for` loop and hence grabbing next `u = EXTRACT-MIN(Q)`.

Am I correct? or I must be missing something very stupid. What's that?

# Answer
> 3 votes
> ***Question 1:*** However still I think that according to the line 8 in algorithm, all adjacent vertices of $a$ not in the tree must be added first to the tree. Thus $h$ should also get added immediately after $b$, before $c$.

You are confusing the resulting MST tree (denoted $T$) with the intermediate priority queue $Q$.

* All the vertices are already in $Q$ at the end of initialization (Lines 1 ~ 5). However, $T = \emptyset$ at this time point.
* A vertex $u$ is extracted from $Q$ and becomes a member of tree $T$ at line 7.
* In the loop starting from Line 8, vertice $v$ satisfying the requirements of Line 9 are *not* inserted into the tree $T$; instead their keys in the priority queue $Q$ are changed (in fact, decreased).

> ***Question 2:*** "My point is when the line 8 says "for each adjacent vertex $v$ of $u$", why only adjacent node $b$ of $a$ is considered, but not $h$ (which is also adjacent to $a$)."

Yes, $h$ is also considered, but in the way different from what you describe. In the iteration for $a$, both $b$ and $h$ are considered (satisfying Line 8 and Line 9): their `keys` are updated (i.e., decreased) in the priority queue $Q$ (Line 11) and their parents are updated accordingly (Line 10). (Note that these updates are not finalized and may be updated again during the algorithm.)

The key point is: neither $b$ nor $h$ has been added into the resulting MST tree $T$. Vertex $b$ will be extracted from $Q$ and added into $T$ in the *next* iteration at Line 7 (shown in step (b)).

Also note that the figure in CLRS only shows the changes on $T$; it does not show the states of $Q$.

# Answer
> 0 votes
I've done some simulation, implementing Prim's algorithm exactly as you reported from CLRS. As the book says, you have a set $A$ ***implicitly*** maintained by the algorithm, defined as

$$ A = \\{(v, v.\pi) : V-\\{r\\} - Q \\} $$

This is built incrementally, and when the priority Q is empty then it is complete. Here is the output of my simulation with the same instance of the book, starting from node 'a': gray circles represent nodes already included in the MST (actually, I included also the starting node), while bold lines represents eligible edges for the solution. White circles are nodes in the queue. As long as PQ is consumed, adjustment are done. Note that you aren't building the MST when you update the $\pi$ attribute if nodes are still in the queue (see $A$ definition).

The total cost of the MST is $37$, as you can see this graph has more than one MST.

# Answer
> 0 votes
As both of vertices are present in Q with same key value 8, So you can either choose (b,h) or (b,c). Resultant MST will be same in both cases.

# Answer
> 0 votes
In simple words, the line $7$ which is extracting a vertex $v$ tells the next vertex to be added in the tree. $h$ vertex is extracted after $g$. Although the parent of $h$ would be written $a$ (i.e, $h.\pi = a$) during first iteration but it eventually be overwritten when $g$ would aspect it forwardly (i.e, $h.\pi = g$). Also, note that $... if \ v \in Q...$ in the $9$ the line is another interesting thing; it ensures to follow *cut property*.

---
Tags: graphs, greedy-algorithms, prims-algorithm
---


# Question
Title: Interpretation of Turing's statement on universal computers
I'm currently reading a book about artificial intelligence and i frequently come across the concept of universal computers, as it is essential to understand the book i would like to know the meaning of author's statement referring to Turning's paper of 1936:

> If a type of computer can perform a certain bare minimum set of operations, then it's universal in the sense that given enough resources, it can do anything that any other computer can do.

Maybe the above statement is on its own very clear, but i have difficulties to understand. I'm afraid i interpret the concept in a wrong way.

Consider a simple calculator we were using in school, how can we provide it with **enough resources** so it can do anything that any graphical calculator nowadays can do? We if add components to the existing computer then it wouldn't be the same computer as it used to be. So my conclusion is the term **enough resources** doesn't mean any physical alterations.

# Answer
> 1 votes
To understand what Turing means here, you first need to understand what Turing means when he uses the word "computer". He is not talking about any particular machine, but about someone or something that 'computes', where 'computing' means to transform inputs into outputs according to some specification or function.

The key difference between the everyday using of 'computer' and Turing's is the following: a 'computer' such as a pocket calculator or mobile phone consists of not only a 'computer' a la Turing, but also has an *interface* to this computer. Roughly, we can see this interface as a component that translates device input (touch screens, keys, etc.) to strings of 0's and 1's and translates this binary code back to device output (e.g. screen displays). This means that all the 'computer' has to do is compute on strings of 0's and 1's and leaves how to get input or present the output to the interface.

---

Now for the actual statement. What Turing says is the following:

1. If a computer can perform a certain (relatively simple) set of operations, we call it *universal*.
2. An universal computer can do anything another computer can do, given enough resources.

Part 1 should be clear. The 'resources' in part 2 is not very clear, but we can think a bit about what it means. Since a computer is something that only works with transforming binary code, the 'resources' of a computer are 'whatever is needed to perform this transformation on binary code'. What exactly are resources then depends on the type of computer: a mobile phone will need battery power to perform computations, while an engineer might be able to perform the same computations with a piece of paper and a good cup of coffee. Both of them will also need *time* to perform the computation.

---

We can now take a look at your calculator example. First of all, Turing's statement is only applicable if the simple calculators operations make it a universal computer. While a calculator is likely not universal, let's assume that it is for the moment. Then the computer 'inside' the pocket calculator can do everything the computer 'inside' the graphical calculator can do, even though the graphical calculator can display things the pocket calculator cannot.

What you should realize is that the difference in displays is a difference in interfaces of devices, not of their computers. The pocket calculator may not be able to show you a function plot on the display, but the display can certainly show the coordinates of all points on the plot.

---
Tags: turing-machines, history
---


# Question
Title: How to show that this decision problem is in co-NP?
Given a set of strictly positive numbers $a\_1, ..., a\_n$, the problem is to determine if $\lfloor n/2 \rfloor$ different indexes $i\_1, ..., i\_{\lfloor n/2 \rfloor}$ exist so that $$\frac{a\_{i\_j}}{a\_{i\_{j-1}}} = \frac{a\_{i\_{j+1}}}{a\_{i\_j}}$$ for $2 \leq j \leq \lfloor n/2 \rfloor$.

How to show that this problem is in co-NP ?

# Answer
P is a subset both of NP and of co-NP. Do you think the problem is in P?

(O(n^3) solution is trivial if poster states the problem correctly. As it is, $i\_1 = i\_2 = i\_3 ... = 1$ is a solution.)

You need n/2 different indices $i\_j$ such that $a\_{i\_2} / a\_{i\_1} = a\_{i\_3} / a\_{i\_2}$, $a\_{i\_3} / a\_{i\_2} = a\_{i\_4} / a\_{i\_3}$, etc.

There are $n^2 - n$ ways to choose $i\_1$ and $i\_2$. Once you chose these, let $d = a\_{i\_2} / a\_{i\_1}$. Then we must have $a\_{i\_3}$ = $a\_{i\_2} \cdot d$, $a\_{i\_4}$ = $a\_{i\_2} \cdot d^2$, $a\_{i\_5}$ = $a\_{i\_2} \cdot d^3$ etc. So all you have to do is check whether there are enough $a\_i$ with these values and take their indices.

You can do this faster, but all I cared about was whether it's polynomial time.
> 0 votes

---
Tags: complexity-theory, np, co-np
---