# Question
Title: Given a mechanical assembly as a graph, how to find an upper bound on number of assembly paths
The rules are that you can only build from an existing part, so in the example below, B is the only option for the first move = A.

A mechanical assembly might be represented as follows:

```
  E
  |
  C
  |
A-B
  |
  D
  |
  F

```

Where the valid assembly paths when starting from A are:

```
A, B, C, E, D, F
A, B, C, D, E, F
A, B, C, D, F, E
A, B, D, F, C, E
A, B, D, C, F, E
A, B, D, C, E, F

```

This is a fairly simple example, but providing an upper bound for an arbitrary assembly is difficult since it's related to the "connectivity" of the parts.

n! would be an absolute upper bound I guess, but I'm hopping to find something a little better.

I've also looked at representing the graph with the parts (A, B, C, etc) as the edges and doing Kirchhoff's theorem, but that doesn't work for sparsely connected graphs like the example above.

Any information about the problem would help. I'm not sure if there's a formal description of this type of problem or not.

# Answer
Your question is quite open-ended, in that you have not specified how accurate the **upper bound** should be, nor how **efficient** the algorithm should be. There is certainly a trade-off between the run-time and the accuracy.

---

Ways to get an exact answer:

* Naive brute force - I guess you know what this means (very slow)
* Observe that it is easy to calculate the number of ways of the graph is a tree (start from the leaves, and when they join up, just count number of ways of joining the two branches

ie. #ways = #ways(branch A) * #ways(branch B) * {#nodes(branch A) + #nodes(branch B)} Choose #nodes(branch A)

Thus iterate over all possible trees, and sum up the number of ways of assembling the tree.

This method is faster than a naive brute force, but it is still brute forcing on all the trees

---

For an upper bound:

* $n!$ - very quick but not accurate
* Using the same observation as before (easy to calculate number of ways for a tree), you can use the quick method for all subtrees/leaves off the main component. Then join it all up.

For example, suppose the main component connected to the root has $a\_0$ nodes, then you have two subtrees hanging off that main component with $a\_1$ and $a\_2$ nodes, each with $b\_1$ and $b\_2$ ways of assembling them respectively.

Then, letting $b\_0$ = $a\_0!$ (an upper bound on the main component), an upper bound on the whole graph is $b\_0b\_1b\_2\frac{(a\_0a\_1a\_2)!}{a\_0!a\_1!a\_2!}$.

This method is very quick, but although it is a much better upper bound than $n!$, it can still be very far off the exact answer.
* A refinement to either of the above methods can be made, by considering the earliest that a particular node can appear in the sequence. Basically, it is a way of counting such that, for example, since you know $B$ can never be the 1st in the sequence, and $C$ is 3rd or later, etc., you can count in such a way to avoid that possibility.

For example, in the above example, first consider that there are 2 ways of ordering $E$, $F$, in places 4-6, call this sequence $s\_1$. Then there are 2 ways of ordering $C$, $D$ in places 3-6 (sequence $s\_2$). So you can now merge the two sequences. Because the intersection of their possible places is 4-6, you know that in place 4-6, there is one element from $s\_2$ and two elements from $s\_1$. Thus, the number of ways of merging them is $\frac{3!}{2!1!}=3$, thus the merger of the two sequences results in a sequence with $2\times 2 \times 3=12$ ways, in a possible range of places ranked 3-6. After merging with a subsequence consisting of $B$ and a subsequence consisting of just $A$, you have an upper bound of $12$ ways of assembling it.
* Further refinement may also be made by considering the latest a node can appear (eg. $C$ and $D$ cannot be in place 6. Thus, when merging sequences $s\_1$ and $s\_2$, an even better upper bound is $2\times 2 \times \frac{2!}{1!1!}=8$ ways.

---

There may be other ways I cannot think of. But each refinement will add complexity, and running time to your algorithm.

I am unsure if there exists an efficient algorithm for finding the exact answer (in $P$ time).
> 1 votes

---
Tags: algorithms, graphs
---


title: Big O: Nested For Loop With Dependence

text:
# Question
Title: Big O: Nested For Loop With Dependence
I was given a homework assignment with Big O. I'm stuck with nested for loops that are dependent on the previous loop. Here is a changed up version of my homework question, since I really do want to understand it:

```
sum = 0;
for (i = 0; i < n; i++
    for (j = 0; j < i; j++)
        sum++;

```

The part that's throwing me off is the `j < i` part. It seems like it would execute almost like a factorial, but with addition. Any hints would be really appreciated.

# Answer
> 12 votes
So let me clarify a few things, you are interested in the big-O notation - this means **upper bound**. In other words, it is okay to count more steps than you actually do. In particular, you can modify the algorithm to

```
 ...
    for (j = 0; j < n; j++)
 ...

```

So you have two nested loops, each loop runs $n$ times, which gives you an *upper bound* of $O(n^2)$

Of course, you would like to have a good estimate for the upper bound. So for completion, we want to determine a lower bound. This means its okay to count less steps. So consider the modification

```
for (i = n/2; i < n; i++)
    for (j = 0; j < n/2; j++)
        sum++;

```

Here, we perform only a some of the loop-iterations. Again we have two nested loops, but this time we have $n/2$ iterations per loop, which shows that we have at least $n^2/4$ additions. In this case we denote this asymptotic lower bound by $\Omega(n^2)$. Since the lower and upper bound coincide, we can even say that $n^2$ is a tight asymptotic bound, and we write $\Theta(n^2)$.

If you want to know more, read here.

# Answer
> 8 votes
```
sum = 0;
for (i = 0; i < n; i++)
    for (j = 0; j < i; j++)
        sum++;

```

Let's trace this out:

* When i=0, the inner loop will not run at all (`0<0 == false`).
* When i=1, the inner loop will run once (for j==0).
* When i=2, the inner loop will run twice. (for j==0 and j==1).

This algorithm will thus increment `sum` the following number of times:

$$\sum\_{x=1}^n x-1 = 0+1+2+3+4... + n-1 = \dfrac{n(n-1)}{2}$$

We can see by inspection that the sum is a "triangular number". Distributing $n$ into the rest of the numerator, we arrive at $\dfrac{n^2-n}{2}$, of which the fastest-growing term is $n^2$ hence the Bachman-Landau Big-Theta complexity is $\theta(n^2) \equiv O(n^2) \ and\ \Omega(n^2)$.

# Answer
> 3 votes
let's see if I can explain this...

So if the inner loop was j

Now, for the first iteration you do n-(n-1) times through the inner loop. on the second time you do n-(n-2) times through the inner loop. On the Nth time you do n-(n-n) times through, which is n times.

if you average the number of times you go through the inner loop it would n/2 times.

So you could say this is O(n\*n/2) = O(n^2/2) = O(n^2)

Does that make sense?

---
Tags: algorithms, algorithm-analysis, runtime-analysis, landau-notation
---


# Question
Title: Given a fast and a slow computer, at what sizes does the fast computer running a slow algorithm beat the slow computer running a fast algorithm?
The source of this question comes from an undergraduate course I am taking, which covers an introduction to the analysis of algorithms. This is not for homework, but rather a question asked in CLRS.

You have a slow machine running at $x$ MIPS, and a fast machine running at $y$ MIPS. You also have two algorithms of the same class, but different running time complexities: one "slow" algorithm runs at $T(n) = c\_1n^2$ whereas a "fast" algorithm runs at $T(n) = c\_2n \log n$.

You execute the slow algorithm on the fast machine, and the fast algorithm on the slow machine. What is the largest value of n such that the fast machine running the slow algorithm beats the slow machine running the fast algorithm?

**My solution so far:**

Find the set of all $n$ such that $$\frac{c\_2n\log n}{x} \> \frac{c\_1n^2}{y}$$ where $n$ is a natural number.

This is my work thus far:

$$\\{n : \frac{c\_2 n \log\_2 n}{x} \> \frac{c\_1 n^2}{y}, n \in \mathbb{N}\\} = \\{n : n \< \frac{c\_2 y}{c\_1 x} \log\_2 n, n \in \mathbb{N}\\}$$

The only solution that comes to mind now is to plug-n-chug all values of $n$ until I find the first n where

$$n \< \frac{c\_2y}{c\_1x}\log(n)$$

no longer holds.

# Answer
> 2 votes
Consider your last inequality:

$\qquad \displaystyle n \< \frac{c\_2y}{c\_1x}\log(n)$

Now, $C\log n$ with $C = \frac{c\_2y}{c\_1x}$ is a concave function. Therefore, there are at most two intersections, and only one of them is interesting for you; that is, solve

$\qquad \displaystyle n = C\log(n)$

and find out which algorithm is faster in which interval by simply calculating the respective function values at some point in the respective interval.

It is true that solving this equality explicitly is hard/impossible. For some fixed $C$, computer algebra gives you an expression in a well-known function; interesting (real) intersection turns out to be at

$\qquad \displaystyle n = e^{-W\_{-1}(-\frac{\ln 2}{C})}$

if $C \geq e \ln 2$, with $W\_k$ the analytic continuation of the product log function. This function does not have a nice closed form, but it can be evaluated numerically for given $C$; for instance, you get $\approx 116,74$ for $C=17$.

---
Tags: algorithms, algorithm-analysis, runtime-analysis, mathematical-analysis
---


# Question
Title: Anonymization of dataset preserving unique identities
The $k$-anonymization paradigm (and its refinements) means to create datasets where every tuple is identical with $k-1$ others.

However I'm in a situation where people are in the dataset many times. And I want to follow their progress through the health care system, so I need to know who is who. If I give each person a unique ID, which is necessary in this situation, a linking attack from within the table is possible!

Does anyone know of any relevant theory or have attempted to deal with similar problems?

I'm inclined to think it is impossible to give any good guarantee of anonymity in this situation.

This will possibly be used for my MSc thesis topic.

# Answer
> 2 votes
The point of k-anonymity is that you can't uniquely identify your patients. So I will rephrase your question:

> Given two anonymized tuples $x$ and $y$, can we tell if they are anonymizations of the same person?

Let's suppose for purposes of contradiction that we could. Then this means there is a "meta-tuple" which uniquely identifies a patient. But this violates anonymity (unless $k=1$). So it is impossible.

---
Tags: algorithms, security, databases
---


# Question
Title: Why do the swap step in Prim's algorithm for minimum spanning trees?
I was watching the video lecture from MIT on Prim's algorithm for minimum spanning trees. Why do we need to do the swap step for proving the theorem that if we choose a set of vertices in minimum spanning tree of $G(V,E)$and let us call that $A$ such $A\subset B$, the edge with the least weight connecting $A$ to $V-A$ will always be in the minimum spanning tree ? The professor has done the swap step at point 59:07 seconds in the video.

# Answer
> 3 votes
Charles Leiserson is presenting a proof to what is known as the **blue rule** in Tarjan's "Data Structures and Network Analysis" book.

The proof goes by contradiction, that is you assume that the edge $(u,v)$ is not in the MST $T$. Don't be confused by the board, it has to be $(u,v)\not \in T$. Let $(a,b)$ the edge that we swap with $(u,v)$. Bot edges are cut edges between $A$ and $A\setminus V$. The tree $T'$ after the swap has weight $$w(T')=w(T)+w((u,v))-w((a,b)).$$ As a consequence $w(T')\<w(T)$, which is a contradiction and therefor the assumption $(u,v)\not\in T$ was wrong.

Notice that this proof uses the assumption that all edge weights are distinct, however it is easy to modify it for general edge weights.

---
Tags: algorithms, graphs, algorithm-analysis, greedy-algorithms, spanning-trees
---


# Question
Title: What approaches are most useful when proving uncomputability of a given function?
I'd like to understand what approaches should one adopt when deciding/proving that a given function *F* is uncomputable, by any Turing Machine (TM). The ones I've tried so far are as follows:

* Reduction, from a known uncomputable function (such as $UC(\alpha)$, the uncomputable function as proved by Cantor's diagonalization argument in Chapter 1 of the book "Computational Complexity" by Sanjeev Arora and Boaz Barak, or $HALT(\alpha, x)$, which is nothing but the function in the Halting problem), to *F*. If such a reduction is possible, it can be argued that *F* is uncomputable as otherwise, the problems that are proved to be uncomputable would become be computable as well.
* Proof by contradiction, in which one shows that if there is a TM *M* that computes *F*, it would lead to some sort of inconsistency in either the *M*'s output, or the functions evaluated value.

I've applied (or rather, tried to apply) both the above techniques to some reductions, two of which I now state here (for illustrating the limitations of my approach):

> 1. If whenever a TM *M* accepts a string *w* $\in$ ${\\{0,1\\}}^\*$, it also accepts $w^R$, the TM *M* is said to possess property *R*. ($w^R$ is the string obtained by reversing $w$ i.e. $(110)^R$ is $011$). Let $R: {\\{0,1\\}}^\* \rightarrow \\{0,1\\}$ be defined as follows: $R(\alpha) = 1$ if $M\_\alpha$ possesses property $R$, and $R(\alpha) = 0$ otherwise. Prove that $R$ is uncomputable.
> 2. Let $B: {\\{0,1\\}}^\*$ x $ {\\{0,1\\}}^\* \rightarrow \\{0,1\\}$ be defined as follows: $B(\alpha,x) = 1$ if $M\_\alpha$ writes a non-blank symbol on its output tape while computing input $x$, $B(\alpha,x) = 0$ otherwise. Prove that function $B$ is uncomputable.

For problem 1, I tried reducing the uncomputable function $UC$ to $R$, but the reason I couldn't quite complete the reduction is because $R$ is a property of the Turing Machine, not dependent on any input instance, where $UC$ depends on the output of a specific instance $M\_\alpha(\alpha)$. Also, for both $R(\alpha)$ = 0 and $R(\alpha)$ = 1, it is possible that $M\_\alpha$ can go on indefinitely for some inputs!

For problem 2, I tried reducing the function $HALT$ to $B$ (thus attempting to make a TM that computes $HALT(\alpha,x)$ by using the output of a TM $M\_\beta$ that computes $B$). But here as in problem 1, *it is possible* that for both outputs of $M\_\beta(\alpha,x)$, the TM $M\_\alpha$ may not halt at all on input $x$!

So, I'm stumped here - I understand intuitively why these functions should be uncomputable (No TM should be able to predict whether another TM would halt/output anything on any possible input), I'm not quite able to derive a concrete proof! So, I really want to understand what approaches am I missing here, or are there holes in the current approaches that I've tried so far!

Note: For self-containment, I'm stating what are the functions UC and HALT here as well:

$UC: {\\{0,1\\}}^\* \rightarrow \\{0,1\\}$:

$UC(\alpha) = 0$, when the Turing Machine represented by $\alpha$, $M\_\alpha(\alpha)$ = 1

$UC(\alpha) = 1$, otherwise.

$HALT: {\\{0,1\\}}^\*$ x $ {\\{0,1\\}}^\* \rightarrow \\{0,1\\}$:

$HALT(\alpha, x) = 1$, when the Turing Machine represented by $\alpha$, $M\_\alpha(\alpha)$ halts on input $x$.

$HALT(\alpha, x) = 0$, otherwise.

# Answer
There are unfortunately as many techniques to prove functions uncomputable as there are to prove things in general, so there's no comprehensive doctrine for how you should approach this.

Note that the proof by reduction is just a special case of a proof by contradiction; assuming that the function *is* computable leads to a proof that some other problem is computable, which is a contradiction if there's already a proof that the other problem is *not* computable.

Your first problem can immediately be shown to be uncomputable due to Rice's Theorem. Briefly, Rice's Theorem states that for any non-trivial semantic property of TMs, detecting whether a given TM has the property is undecidable. *Semantic* means the property depends only on the language accepted by the TM (all TM's accepting the same language have the property, or all do not have the property, regardless of the specific implementation). *Non-trivial* simply means that there do exist languages that have the property, and languages that don't. So one way to solve this problem is to simply recognise that "for all strings w accepted by M, the reverse of w is also accepted by M" is a non-trivial semantic property and invoke Rice's Theorem. That may not be the most satisfying way to solve your problem if you're doing this to learn though (although the proof of Rice's Theorem is quite accessible; it's essentially a very generalised reduction from the Halting Problem).

For your reduction proofs, remember that you can "cheat". You are **assuming** the existence of a solver (call it **P**) for the problem you're trying to prove undecidable, and show that if you had that you could solve the Halting Problem. This means your reduction can presume that **P** "just works" by black-box magic, regardless of whether it seems possible. In particular, you do not need to care that the machines you construct to feed to **P** halt or do anything at all useful; only that they cause **P** to accept/reject in a way that can be used to solve the Halting Problem (or some other undecidable problem, but I found the Halting Problem to be very productive when I was doing these sorts of exercises at uni).

For example, one of my most enjoyable exercises in my undergraduate Theory of Computation course was proving that it as undecidable to detect whether a TM ever attempted to move the tape head left from the left-most cell of the tape (in the model we were using this would cause the tape head to simply remain in the left-most cell). I did this by showing that for an arbitrary TM **M** you could construct a machine that was in fact guaranteed *not* to halt on any input, but would attempt to move left from the left-most cell if-and-only-if **M** halted on the same input.

So what you need to do to prove $R$ uncomputable by reduction is find some undecidable problem **P**, such that you can transform an arbitrary instance of **P**'s input into a TM that has the property *R* if-and-only-if the original input to **P** should be accepted (or rejected; the negative works too).

Similarly for problem 2, the obvious (to me) thing to do is to take an arbitrary TM **M**, and transform it into a machine **M'** that halts exactly when **M** writes something on the output tape, and is guaranteed not to halt if **M** never writes something on the output tape. Don't get hung up on whether **M** or **M'** halts; you're not planning to run either of them, only to run your hypothesized solver for problem 2 with **M'** as input.

---
> 7 votes

# Answer
Perhaps another way to prove **Q1** is the following:

1) we can automatically build the transition table of a $TM\_{(m,x)}$ that on every input $w$ simply adds the fixed string $\\#m\\#x$ at its end, and bring the head to the intial tape position (the final tape content of $TM\_{(m,x)}(w)$ is $w\\#m\\#x$);

2) we can explicitly build a $TM\_{sim}(w\\#m\\#x)$ that simulate $TM\_m$ on input $x$ and if it halts output $w^R$

Now, suppose that there is a Turing machine $TM\_R(\alpha)$ that decide if $TM\_\alpha(w)=w^R$ for all $w$.

Given $m$ and $x$, we can find the $\alpha$ that correspond to the TM with a transition table that is the *concatenation* of the transition table of $TM\_{(m,x)}$ and the transition table of $TM\_{sim}$

But by construction: $TM\_R(\alpha) = 1$ if and only if $TM\_\alpha(w) = w^R$ for all w, if and only if $TM\_{sim}(w TM\_{(m,x)})=w^R$ for all w, if and only if $TM\_m(x)$ halts; i.e. we would be able to solve $HALT(m,x)$.
> 1 votes

# Answer
Here's the general approach I used, which I'm hoping would be useful for similar types of problems on deciding uncomputability of functions using TMs. There are 2 types of such functions (as far as I've faced!):

1. Functions which decide properties of the *language accepted by the Turing Machine supplied as input*, e.g. Problem 1 in my question, and doesn't depend on the behaviour of that TM on any specific input instance.
2. Functions which take a tuple $\<\alpha, x\>$, whose output depends on the behaviour of $M\_\alpha$ on input $x$.

For Type 1 problems (given a function $F(\alpha)$ which predicts some property of $M\_\alpha$), use the following mechanism:

> 1. Assume $M\_\beta(\alpha)$ to be the TM that computes $F(\alpha)$.
> 2. Construct a TM $M\_\gamma(w)$, which would accept only a select set of inputs $w \in \\{0,1\\}^\*$, such that $F(\gamma) = 1$ iff $M\_\alpha(x)$ returns 1, *for any input $x$*.
> 3. Evaluate $M\_\beta(\gamma)$. If $M\_\beta(\gamma) = 1$, it implies $M\_\alpha(x) = 1$, otherwise $M\_\beta(\gamma) = 0 \Rightarrow \> M(\beta)$ can predict if $M\_\alpha(x)$ would be accepted or not. That is clearly not possible, hence $M\_\beta$ cannot exist.

**Note**: The real trick in Type 1 problems is to design the behaviour of the TM $M\_\gamma$, such that it

1. Rejects most inputs (so as to simplify the construction), and
2. Accepts only particular input cases so as to cause $M\_\beta(\gamma)$ to be true, only when the output of $M\_\alpha$ is true. (For problem 1, I made $M\_\gamma$ reject all inputs other than 01 and 10. For 01, it returned 1, while for 10, it simulated the behaviour of $M\_\alpha(x)$, and returned whatever that returned.)

For Type 2 problems, where the output of $F(\alpha, x)$ depends on the output/operation of a TM $M\_\alpha$ on a specific input $x$, use the following approach:

> 1. Assume $M\_\beta(\alpha, x)$ to be the TM that computes $F(\alpha, x)$.
> 2. Construct a TM $S$ which on input $\<\alpha, x\>$, does the following:
>     1. Construct a TM $M\_\gamma(w)$ such that $M\_\beta(\gamma, w) = 1$ iff $M\_\alpha(w)$ returns 1.
>     2. Run $M\_\beta$ on \<$\gamma, x$\>, and return its output.

Thus, it can be seen that the TM $S$ accepts only when $M\_\alpha$ accepts, which is not possible!

**Note:**, For problem 2, I made $M\_\gamma$ to be a 2 Tape TM that on input $w$, simulates $M\_\alpha$ on $w$ using the first tape, and write a non-blank symbol on its second tape if $M\_\alpha$ accepts!
> 0 votes

# Answer
I think problem 2 is decidable.
We shall prove that $B$ is computable by describing a 2-tape $TM M$ that decides it:
$M$ will simulate $M\_\alpha$ on $x$ and will keep on its 2nd tape the configurations (= state, head position and symbols currently on tape) $M\_\alpha$ has been in. Each time $M\_\alpha$ "moves", $M$ will check if this configuration has been visited.
$M$ will also write on it's 2nd tape the states in which $M\_\alpha$ last visited a new blank cell (one that has NEVER been visited before) to the right and to the left of the input (2 different lists).
We will name this $LBSL$ (Last Blank State Left \[of original input\]) and $LBSR$. Additionally, each time $M\_\alpha$ visits a non blank cell \[= the original input\] $M$ will delete $LBSL,LBSR$.
If $M\_\alpha$ writes a symbol on the tape, $M$ will accept.
If $M\_\alpha$ accepts or rejects, $M$ will reject.
If $M\_\alpha$ revisits a configuration $M$ will reject.
If $M\_\alpha$ visits a blank cell to the right of the input, which it never visited before, and the state of $M\_\alpha \in$ $LBSR$, $M$ will reject. Same for left of input and $LBSL$.
We will prove that $M$ rejects the input $\iff$ $M\_\alpha$ will never write anything on $x$:
$\implies$ Let us assume $M$ has rejected some input.
1.If this was because $M\_\alpha$ halted, obviously $M\_\alpha$ wouldn't have written anything.
2.If $M\_\alpha$ revisited a configuration: $M\_\alpha$ is deterministic and thus will repeat the steps between the first and 2nd visit, and will keep doing this forever.
Now for the messy part:
3. If $M\_\alpha$ visited a new cell, in the same state, without going through the input in between then it has only read blank chars between this two configurations. Thus $M\_\alpha$ will repeat the same steps, because it will again read only blanks. Notice that the new blank cell is further away from the input. This means it will once again visit a new blank cell in the same state and will never write anything.
For the other part of the iff, we need to show that either 2 or 3 will happen on any machine that never writes anything for input x and never halts.
Notice that after visting a new blank cell $M\_\alpha$ will either:
$I$ visit a new blank space some time in the future, and because the number of states is finite this will in some point result in situation 3.
$II$ $M$ will use bounded space from now on (because $I$ does not happen), and thus will repeat a configuration, resulting in situation 2.

I admit this is a messy construction & proof, and it is possible I have missed something on the way.

EDIT: I forgot to mention why M (the decider) halts on every input, but this should be obvious. Also, I know I did not answer your question. I think Ben did an excellent job at that. I just felt that the decider for B should be mentioned (assuming I did not miss anything). Maybe I should have opened a new question for that? I'm not sure.
> 0 votes

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


# Question
Title: Looking for a simple example of Transition Semantics
I want to define a semantics of a DSL through transition semantics. For my DSL I defined the syntax and implemented a code generator. Although I can provide a demo by giving examples, I want to write the semantics of my DSL to provide a formal specification of it.

However I don't know how to do it!. Can someone provide me with an example?

# Answer
What do you mean by "transitional semantics"? If you mean structural operational semantics using transition systems, then maybe a good place to start is a good text on the semantics of programming languages, Examples:

I recommend ignoring denotational semantics for your task.

Since the semantics of programming languages is really well-understood, most of the work in formalising DSLs usually comes from the domain-specific part of the language.
> 5 votes

---
Tags: formal-languages, semantics
---


# Question
Title: Heuristically determine a value f such that a probability d/f approaches 1/2
We have a set X of N elements. We want to get a new set X' having a size M \< N.

```
Choose a first element x from X and put it in X'
for each element x in (X - X')
  Let x' the element from X' which is the closest to x (that is x' = argmin distance(x, x') for all x' in X')
  d = distance(x, x')
  if ( uniform_random([0,1]) < d / f )
     add x to X'

```

How can I choose the value f such that the size of the set X' at the end will be for instance the half of the size of X (that is, M approximates or equals N/2). I suppose that I should choose f such that the probability d / f equals 1/2 (or approximates 1/2 for most values of d), but how to do that ?

Additional details (that are not necesarily usefull for this question): the elements are actually vectors, and the distance between two vectors is the euclidean distance.

Note that d is not a constant (while f is a constant that I want to fix). d depends on the distance between each element x and its closest element x', so d is not always the same.

Suppose that the order in which we test the elements x is always random. For any set X, if we choose the value of f relatively small then we will get a relatively hight number of elements in the final set X', if we choose the value of f relatively big we will get a relatively small number of elements in the final set X'. If I experimentally vary the value of f many times I can always (for any set X) find a value of f for which the final number of elements in X' approaches N/2. So experimentally I can find a good value for f if I test many times which different values of f, but I want to determine it heuristically (not by testing many times and varying f).

**EDIT:** By the way, the only one method which seems to give an acceptable results is: let mean\_d the mean distance of each x to its nearest x'. We put f = 2mean\_d, thus the probability d/f = d/(2mean\_d) usually approximate 1/2 if the most of distances d are not far from mean\_d. We also put f = (2mean\_d)+d' where d' depends on how many distances are higher than mean\_d, or f = (2mean\_d)-d' where d' depends on how many distances are less than mean\_d. Does this make sense ? Do you think it can be improved ?

# Answer
OK, another answer :)

Size of the set X' clearly depends on the distribution of points, choice of starting points, and random chance.

If the points are always chosen from the same distribution, I'd try drawing |X'| as a function of f and |X|. To do that, I'd just do some monte-carlo simulations.

Also notice that f is a linear function of mean distance between points.
> 1 votes

# Answer
This isn't an answer, but just a thought about your setup.

The outcome seems to depend on the choice of the initial element. For example, if one point was really far out, and all the other points clustered together. If we start with the far point, then the initial `d` is huge. Thus we can only ever add new points to `X'` if `f` is also huge. But if `f` is huge, then we can never add any subsequent points, since `d` will henceforth be small.

Perhaps you could describe the larger goal of this algorithm before jumping at a specific implementation?

---

Another example: Suppose `X` is the set consisting of the vertices of the standard simplex in *n*-dimensional Euclidean space, i.e. all vertex pairs have distance 1. Surely `f = 2` would be a good solution. Now add to `X` one really far away point. By the above logic, `f = 2` is still a good choice if we start with any of the original points, but if we start with the far point, it won't work. So no choice of `f` works uniformly for *all* choices of initial point.
> 0 votes

# Answer
The value of f depends on the set X aty hand, and the order in which You test the elements.

For example, if the elements are points on a line, then testing the elements in order will give You more elements in the final set than testing them in a random order.

In short, it is not possible to choose f that works for any set X.
> 0 votes

---
Tags: probability-theory, mathematical-analysis, heuristics, statistics
---


# Question
Title: Finding the Shortest path in undirected weighted graph
Is there an algorithm for finding the shortest path in an undirected weighted graph?

# Answer
## All-Pairs-Shortest Path

Given a graph $G = (V, E)$ find the shortest path between *any* two nodes $u,v \in V$. It can be solved by Floyd-Warshall's Algorithm in time $O(|V|^3).$ Many believe the APSP problem requires $\Omega(n^3)$ time, but it remains open if there exists algorithms taking $O(n^{3 - \delta} \cdot \text{poly}(\log M))$, where $\delta \> 0$ and edge weights are in the range $\[-M, M\]$.

The reasoning for this is upon close examination we see that the APSP problem can be solved by matrix multiplication. If we replace the operators to $\\{\text{min}, +\\}$ instead of $\\{ +, \cdot \\}$ we may use the framework for matrix multiplication to compute the solution. What is interesting is if there exists sub-cubic algorithms for the APSP problem, then there exists sub-cubic algorithms for many related graph and matrix problems \[1\].

---

\[1\] Subcubic Equivalences Between Path, Matrix, and Triangle Problems
> 3 votes

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


# Question
Title: Decidable restrictions of the Post Correspondence Problem
The Post Correspondence Problem (PCP) is undecidable.

The *bounded version of the PCP* is $\mathrm{NP}$-complete and the *marked version of the PCP* (the words of one of the two lists are required to differ in the first letter) is in $\mathrm{PSPACE}$ \[1\].

1. Are these restricted versions used to prove some complexity results of other problems (through reduction)?
2. Are there other restricted versions of the PCP that make it decidable (and in particular $\mathrm{PSPACE}$-complete)?

\[1\] "Marked PCP is decidable" by V. Halava, M. Hirvensalo, R. De Wolf (1999)

# Answer
> 4 votes
there is more than one way to "bound" PCP (maybe verging on many!) and there seems to be diverse research into many variants. limiting the number of concatenated blocks or total length of concatenated strings to a parameter specified on the input (specified in binary) appears to be NExpSpace complete but have not seen this written up in a paper. see Bounded Post Correspondence Problem NP-Complete Proof, tcs.se. if you limit the same "concatenation length" parameter to a polynomial of the input size its apparently PSpace complete. again havent seen that written up anywhere despite some search.

there is also somewhat related research into resolving special cases of the PCP (somewhat reminiscent of Busy Beaver research), see eg PCP solver by Zhao or \[8\]. note that theres also a remarkable/pioneering case of applying DNA computing for a somewhat-probabilistic approach.\[3\] also there seems to be more research by Halava\[4\],\[7\] into other decidable variants. \[5,6\] are further misc results.

\[1\] Tackling Posts correspondence problem by Zhao (v2?)

\[2\] A polynomial reduction from any NP-complete problem to bounded PCP, cs.se

\[3\] Using DNA to solve the Bounded Post Correspondence Problem by Kari et al

\[4\] On Post Correspondence Problem for Letter Monotonic Languages by Halava et al

\[5\] The Post correspondence problem over a unary alphabet by Rudnicki

\[6\] Post Correspondence Problem with Partially Commutative Alphabets Barbara Klunder, Wojciech Rytter

\[7\] Some New Results on Post Correspondence Problem and Its Modifications by Halava, Harju

\[8\] Creating Difficult Instances of the Post Correspondence Problem by Lorentz

# Answer
> 11 votes
Ehrenfeucht, Karhumäki and Rozenberg have shown that binary PCP (where the domain is binary) is decidable. Halava and Holub later showed that it's actually in P.

---
Tags: complexity-theory, computability, reference-request
---


title: How to reduce MaxUNSAT to MaxSAT?

text:
# Question
Title: How to reduce MaxUNSAT to MaxSAT?
Is it possible to reduce MaxUNSAT to MaxSAT in a polynomial way ?

When considering the MaxSAT problem, one often considers also the `MinUNSAT` problem, which is almost the same. And for a propositional formula `f` in CNF it holds:

```
|f| = MaxSAT(f) + MinUNSAT(f)

```

where `|f|` is the number of clauses of f.

When considering `MaxUNSAT` and the corresponding `MinSAT` problem, the same relationship holds:

```
|f| = MaxUNSAT(f) + MinSAT(f)

```

Now, I was wondering if there is also a relationship between those two pairs, e.g. to reduce `MaxSAT` to `MaxUNSAT` or `MinSAT` (or the other way round) ?

Unfortunately, I could not figure out one by myself. And maybe there is none ?

**Update 1:** Inspired by Yuval Filmus's answer, I will give a reduction for my question.

**Reduction from MaxUNSAT to its corresponding decision problem:**

Let $\phi = {C\_1, ..., C\_m}$ a set of clauses over the variables $x\_1, ..., x\_n$, then it holds: $$MaxUNSAT(\phi) = BinarySearch(0, |\phi|, MaxUNSAT(\phi, k) )$$ with

> `BinarySearch(start, end,` **CompareProcedure**( )`):`
>
> `Searches for the element` **e** `between` **start** `and` **end** `so that` **CompareProcedure**(**e**)=**true** `and` **CompareProcedures**(**e**+**1**)=**false**

and

$$MaxUNSAT(\phi, k) := \exists v\in\\{0, 1\\}^n:\sum\_{i=1}^m 1 - I\_v(C\_i) \geq k$$ where $I\_v$ is the interpretation of a propositional formula under assignment $v$.

**Reduction from decision problem $MaxUNSAT(\phi, k)$ to SAT:**

One can reduce the devision problem $MaxUNSAT(\phi, k)$ to the SAT problem by adding blocking variables to each clause and adding a cardinality constraint as propositional formula to limit the number of used clauses with help of the blocking variables.

I can describe this in more detail, if needed.

**Conculsion:**

One can reduce the MaxUNSAT problem to the SAT problem and then solve the SAT problem with the MaxSAT problem. This is a reduction that works in polynomial time.

# Answer
Both MaxSAT and MaxUNSAT are NP-complete, and so can be reduced to one another. MaxSAT is NP-hard by (trivial) reduction from SAT. To see that MaxUNSAT is NP-hard, we follow Creignou \[1\] and reduce from MaxCUT. Given an instance $G=(V,E)$ of MaxCUT, consider the instance $$ \bigwedge\_{(x,y) \in E} (x \lor \lnot y) \land (\lnot x \lor y). $$ Each cut corresponds to a $0/1$ assignment to the vertices. If an edge $(x,y)$ is separated by a cut, then one of the two corresponding clauses will be unsatisfied, and otherwise none will be unsatisfied.

\[1\] Creignou, A dichotomy theorem for maximum generalized satisfiability problems, JCSS 51, 511-522 (1995).
> 3 votes

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


# Question
Title: Compression of sequence with Direct Access
I have a sequence of $n$ integers in a small range $\[0, k)$ and all the integers have the same frequency $f$ (so the size of the sequence is $n = f * k$). What I'm trying to do now is to compress this sequence while providing random access (what is the $i$-th integer). I'm more interested in achieving high compression at the expense of higher random access times.

I haven't tried with Huffman coding since it assigns codes based on frequencies (and all my frequencies are the same). Perhaps I'm missing some simple encoding for this particular case.

Any help or pointers would be appreciated.

Thanks in advance.

# Answer
You can use the so-called "binomial encoding", described in one of my answers on math.stackexchange. You have to consider, though, whether it will be worthwhile. The naive encoding takes $n \log\_2 k$ bits, and the best encoding saves about $O(\log n)$ bits (the best encoding uses $\log\_2 \frac{n!}{f!^k}$ bits). Plug in your actual numbers to see what kind of saving you can expect.

Edit: I can't find my supposed post on math.stackexchange, so here is a summary of binomial coding (or rather multinomial coding), as it applies in this case. For a vector $x$ of length $k$, define $$ w(x) = \frac{(\sum\_i x\_i)!}{\prod\_i x\_i!}. $$ Note that for $x \neq 0$, $$ w(x) = \sum\_{i\colon x\_i \> 0} w(x-e\_i), $$ where $e\_i$ is the $i$th basis vector. For example, if $k = 2$ and $x\_1,x\_2\>0$ then $$ w(x\_1,x\_2) = w(x\_1-1,x\_2) + w(x\_1,x\_2-1). $$ This is just Pascal's identity $$ \binom{x\_1+x\_2}{x\_1} = \binom{x\_1+x\_2}{x\_1-1} + \binom{x\_1+x\_2}{x\_1}. $$

For every vector $x$ and every $i$ such that $x\_i \> 0$, define $$ w(x,i) = \sum\_{j \< i\colon x\_j \> 0} w(x-e\_j). $$ Given a sequence $\sigma$ of letters in $\\{1,\ldots,k\\}$, let $H(\sigma)$ be its histogram, a vector of length $k$. For a non-empty word $\sigma \neq \epsilon$, let $\sigma\_1$ be the first symbol, and $\sigma\_{\>1}$ be the rest, so that $\sigma = \sigma\_1 \sigma\_{\>1}$. We are now ready to define the encoding: $$ C(\sigma) = \begin{cases} w(H(\sigma),\sigma\_1) + C(\sigma\_{\>1}) & \sigma \neq \epsilon \\ 0 & \sigma = \epsilon. \end{cases} $$ $C(\sigma)$ is an integer between $0$ and $\frac{n!}{f!^k}-1$.

Here is an example, with $k=f=2$. Let us encode $\sigma = 0101$: $$ \begin{align\*} C(0101) &= w((2,2),0) + w((1,2),1) + w((1,1),0) + w((0,1),1) \\ &= 0 + w(0,2) + 0 + 0 = 1. \end{align\*} $$ You can check that the inverse images of $0,1,2,3,4,5$ are $$ 0011,0101,0110,1001,1010,1100. $$ These are just all the solution in increasing lexicography order.

How do we decode? By reversing the encoding procedure. We know the initial histogram $H\_1$. Given an input $c\_1$, we find the unique symbol $\sigma\_1$ such that $w(H\_1,\sigma\_1) \leq c\_1 \< w(H\_1,\sigma\_1+1)$. We then put $H\_2 = H\_1 - e\_{\sigma\_1}$, $c\_2 = c\_1 - w(H\_1,\sigma\_1)$, and continue. To test your understanding, try to decode $0101$ back from its encoding $1$.
> 1 votes

---
Tags: algorithms, data-compression
---


# Question
Title: Get specified bit in addition of two large binary numbers
I am performing an addition operation on two large binary numbers that have an equal number of bits. Both numbers are stored in an array of length $N$, which is rather large.

At first I tried running a loop over them and keeping track of carry bits. This wasted time, because the aim is to get the bit at a specific position in this sum.

So I modified my approach in following way. Starting from the specified index, I am looping until I find a 0 bit in same position on both numbers; I add only those parts to each other and return the bit at the specified position.

This seems okay, but is this the best I can do? Recall that I want to get the value of one specific bit of the sum, given by its position.

# Answer
Your method will indeed work, but for two $n$-bit numbers it will still take $O(n)$ time. There is a much faster way to solve your problem, with running time $\Theta(\log n)$, known as **carry-lookahead addition**. The downside is that in my experience teaching this technique, people have a hard time wrapping their heads around it. You can find online sources, here and here, and some algorithm or computer organization texts cover it. It's a really interesting algorithm, well worth taking the time to figure it out.
> 3 votes

# Answer
Let $x$ and $y$ denote the two numbers and $x\_i$ and $y\_i$ the i-th bits in their respective binary representations. You want to determine the $i$-th bit in the binary representation of $x+y$. You are not interested in anything else. If so, proceed as follows.

1. Compute $z = x\_i \oplus y\_i$.
2. Examine in succession $(x\_{i-1},y\_{i-1}), (x\_{i-2}, y\_{i-2}), \ldots$ until you find a pair that is $(0,0)$ or $(1,1)$. If you reach $(x\_0, y\_0)$ and all pairs have been either $(0,1)$ or $(1,0)$, stop. The answer is $z$.
3. If you find a pair $(x\_j, y\_j) = (0,0)$, stop. The answer is $z$. If instead $(x\_j, y\_j) = (1,1)$, stop. The answer is $1-z$ or the bit complement of $z$.
> 3 votes

# Answer
It depends on what language you're using to do this. For instance, if this were C, I wouldn't use arrays. I would use Bitfields. Then I'd have access to Bitfield operations. Simple arithmetic is then done by using a combination of AND, OR, XOR and so on.

As far as I know, your Bitfield length will still be limited to your processor's and/or compiler's capacity, without additional libraries.

Also, this question should have been posted in Stack Overflow.
> 0 votes

# Answer
Each specific bit in the sum of two $n$-bit numbers $A=a\_{n}a\_{n-1}...a\_{1}$ and $B=b\_{n}b\_{n-1}...b\_{1}$ is given by the sum of the corresponding bits in the addends, plus a possible carry of $1$, modulo $2$. The carry is $1$ if the less-significant neighbor bits are $11$, or if they are $01$ or $10$ and subjected to a carry themselves. $$ \begin{eqnarray} (A+B)\_{k}&=&(A\_{k} \oplus B\_{k}) \oplus \text{carry}\_{k}(A,B) \\ \text{carry}\_{k+1}(A,B)&=&(A\_{k}\wedge B\_{k})\vee((A\_{k}\oplus B\_{k})\wedge\text{carry}\_{k}) \\ \text{carry}\_{1}(A,B)&=&0 \end{eqnarray} $$ (Here $\oplus$ means addition modulo $2$.) If the numbers are random, you can expect this to take $O(1)$ time, whereas calculating the sum is certainly $\Theta(n)$. (As a practical matter, though, integer addition is so highly optimized that you will need $n$ to be very large before realizing any speed gain.)
> 0 votes

---
Tags: arrays, integers, binary-arithmetic
---


title: Unification vs. SAT solver

text:
# Question
Title: Unification vs. SAT solver
I read on Wikipedia that unification is a process of solving the satisfability problem.

At the same time, I know that such solvers are called "SAT solvers" or "SMT solvers". So, are they different names for the same thing?

If you say that they are different, please point out a flaw in my treatment.

# Answer
SAT solvers solve the Boolean Satisfiability Problem. This is "the problem of determining if the variables of a given Boolean formula can be assigned in such a way as to make the formula evaluate to TRUE."

An example is find an assignment of truth values to variables $a,b,c$ such that $(a \lor b \lor c)\land (\lnot a \lor \lnot b \lor c)\land (a \lor \lnot b \lor \lnot c)\land (\lnot a \lor b \lor \lnot c)$ is true. A SAT solver could return a solution such as $a=true$, $b=true$, $c=true$.

SMT solvers solve a more general problem, namely Satisfiability Modulo Theories. This is "a decision problem for logical formulas with respect to combinations of background theories expressed in classical first-order logic with equality". These theories could include "the theory of real numbers, the theory of integers, and the theories of various data structures such as lists, arrays, bit vectors and so on."

An example, given typed variables $x:int$ and $y:int$ and $f:int\to int$, asks whether the following is $f(x+2) \neq f(y-1) \land x=(y- 4)$ satisfiable. An SMT solver would answer yes, with solution $x=-2$, $y=2$, $f(0)=1$ and $f(1)=3$.

Unification is a specific technique that takes two terms and finds a substitution that would make the terms equal. For example, given terms $book(x,\text{"Fishing"},2010)$ and $book(\text{D.~Smith},y,2010)$, unification would produce substitution $\\{x\mapsto\text{D. Smith},y\mapsto\text{"Fishing"}\\}$. Unification is likely used inside SMT solvers.
> 14 votes

---
Tags: terminology, sat-solvers, unification
---


# Question
Title: Converting a context free grammar to a PDA -- is my solution correct?
I'm reviewing for my midterm and wanted to post this to see if anyone can spot any errors. Im supposed to make a PDA that recognizes this CFG:

$\qquad\begin{align} S &\to R1R1R1 \\ R &\to 0R \mid 1R \mid \varepsilon \end{align}$

Here is my solution; I'm aware that I forgot to draw the second circle around my accepting state.

# Answer
Doesn't that language simply recognize any string in $\\{0,1\\}^\*$ that has at least three $1$s in it?

If so, you just need a regular finite deterministic automaton with that can count up to three in order to recognize it.

---

This is because I'm not on the mood to do a direct translation of that grammar, if that is what you really wanted to check :P
> 8 votes

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


# Question
Title: Finding the number of leaves in a imbalanced recursion tree
I'm going through the MIT Online Course Videos on Intro. to Algorithms at here at around 38:00.

So we have a recursion formula

$\qquad T(n) = T(n/10) + T(9n/10) + O(n)$

If we build a recursion tree it looks like

```
                   T(n)                     -- Level 1       = c*n
             /               \
       T(n/10)             T(9n/10)         -- Level 2       = c*n
        /   \             /         \
 T(n/100)  T(9n/100) T(9n/100)  T(81n/100)  -- Level 3       = c*n

   /                                  \                      <= c*n
    .                                .
    .                                .
 0(1)                                 0(1)

```

where $c$ is a constant larger than $0$.

Shortest path from the root to the leaf is $\log\_{10}(n)$.

Longest path from the root to the leaf is $\log\_{10/9}(n)$

Therefore, the cost could be calculated as Cost = Cost of each level * number of levels.

With the shortest path cost, we get a lower bound of $cn\log\_{10}(n)$, and with the longest path cost an upper bound of $cn\log\_{10/9}(n)$.

And now I have to add the costs of leaf nodes, which leads to my problem. In the video it says the total number of leaves is in $\Theta(n)$. I have trouble figuring out how he got to $\Theta(n)$.

The video further says $T(n)$ is bounded by

$\qquad cn\log\_{10}(n) + O(n) \leq T(n) \leq cn\log\_{10/9}(n) + O(n)$

Wouldn't it make more sense to say it's

$\qquad cn\log\_{10}(n) + O(n^{\log\_{10}(2)}) \leq T(n) \leq cn\log\_{10/9}(n) + O(n^{\log\_{10/9}(2)})$

where $\Theta(n^{log\_{10}(2)})$ represents the leaves on the left and $\Theta(n^{\log\_{10/9}(2)})$ represents the leaves on the right.

Or is there a way to simplify these terms to $\Theta(n)$?

# Answer
> 0 votes
1. Why is thetotal number of leaves in $\Theta(n)$? Because each level in recursion tree corresponds to a splitting of an array's range. When we have one element we can't split it any more so we stop. That's $\Theta(1)$ per leaf. How many 1-element areas are there in an $n$ element array? The answer is $n$.
2. He is summing up all levels. But levels are not all populated. Some paths down are short, some long. The more to the left in the tree, the shorter is the path. So going down the right "spine" of the tree, how many levels are there? $\log\_{10/9}(n)$. What each level sums up to? Initially, $cn$ (where $c$ is a constant, $n$ is number of elements in the array) - while the levels are totally populated - i.e. all nodes represent splits - i.e. no one-element ranges are reached yet. Then, we start missing some leaves, so instead of "equal" , we can write $\leq cn$. So the total sum is *less* than $cn\log\_{10/9}(n)$.

Or, let's go down the left spine and sum all levels up. There will be some uncounted tree to the right and down. So the total is *greater* than this summation, which equals $cn\log\_{10}(n)$. He uses "or-equal" just because he's a mathematician who doesn't like to be wrong in some corner cases. :)

This is all pretty straight-forward and intuitive.

---
Tags: algorithm-analysis, asymptotics, recurrence-relation
---


# Question
Title: Is there a simple way of calculating perceptron weights based on a classification graph?
I am studying for an AI exam and I'm looking for a better way of solving the following problem:

> Graph shows a classification problem in the unit square $\[0,1\]^2$, where Class A is denoted by the grey area in the figure (not including the points on the dotted lines), and Class B occurs otherwise.

To solve this problem, there is a need of constructing 2 perceptrons: both perceptrons output 1 if the input lies in the grey area, and at least one of the perceptrons outputs 0 otherwise.

There are 3 ways of finding appropriate weights for inputs and biases that I know of:

1. Trial and error
2. Perceptron learning algorithm (involving random weights, learning rate, multiple epochs)
3. Geometrical way of finding the vectors of weights (involving finding an orthogonal line to boundary function)

All of them are quite time consuming when you do it with just pen and paper.

Is there a simple way of calculating/finding perceptron weights based on a classification graph?

# Answer
think that you may be somewhat misinterpreting the point of the question. the intent of the exam question seems to be, "what good perceptron weights would result for this classification problem". the reason for this is that one cannot go through all the steps of a long-running algorithm during an exam or even homework.

so going back to perceptron theory \[which is several decades old\] the point is that its a classifier based on *linearly separable functions*, ie *linear inequalities*. for the 2d case this results in simple algebraic geometry. in other words the perceptron can implement some number of linear inequalities to attempt to create the classification. here it is given as $n=2$. so the question probably intended is, "what are two linear inequalities that a good perceptron algorithm would converge to for this problem".

so it seems to reduce to find the coefficients of:

$y \< m\_1 x + b\_2$

$y \> m\_2 x + b\_2$

so then use basic geometric algebra to determine the coefficients $m\_1, m\_2, b\_1, b\_2$ that work for the above diagram. based on the diagram there is not a perfect solution, but a "good" one. (also note that the equations only need to work within $\[0,1\]^2$.)

intuitively, its also somewhat implied from this analysis why perceptrons are so limited. because its easy even in 2d to draw classification problems for which there is no linearly separable solution (concave shapes, shapes with holes in them, etcetera— some hint of this is seen in noting the above shape is *slightly* concave). this observation, fleshed out in a more sophisticated/formal/mathematical/rigorous way in \[1\], caused a lot of controversy at the time & was an important debate in the history of AI, and even apparently discouraged some scientists from investigating more sophisticated simulated neural network models for some time, although Minsky emphatically denied that was his intent and said his work was misinterpreted.

\[1\] Perceptrons, by Minsky & Papert
> 2 votes

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


# Question
Title: Difference between multimethods and overloading
## Context

I've been programming in java for a few years now. And atm i'm learning something totally different: Clojure. There the expression problem can be solved by using multimethods whereas in java you will need something like the visitor pattern or something alike.

## The question

I've been reading about multimethods and got quite confused with the actual difference with method overloading.

The only difference I spotted so far that a multimethod doesn't depend on the runtime type of the object on which the method is called.

# Answer
Overloading is when two or more methods have the same name but different signature (different argument types, different number of arguments). Overloading is resolved statically, depending only on the static types of the arguments. (The interaction of overloading and overriding, in Java, for example, makes the story a little more complicated). Overloading resolves statically to a particular method signature. Then at runtime, dynamic dispatch will select the most appropriate method with that signature.

Multimethods are a collection of methods that have the same name, the same number of arguments, and *overlapping* type signatures. Whenever a call is made to a multimethod (using the name of the multimethod), all of the methods in the collection is considered as a possible candidate for dispatch. The precise candidate is chosen depending on the runtime types of the arguments – the most specific method is selected. The actual runtime types of all arguments are used to determine which one to run, which differs from traditional single dispatch in Java, where only the first argument (the target) of the method is used to determine which method body is run.
> 14 votes

# Answer
As far a as my understanding goes:

Multimethods are a generalization of method polymorphism.

A multimethod consists of 2 parts

1. A name
2. A `dispatch method`: which will produce a `dispatch value`

Based on this dispatch value, the appropriate method will be chosen. Overloading is a special case of multimethods where the dispatch method will return the static type as a dispatch value

In general, the dispatch method can be anything. It can return other values than the type.
> 2 votes

---
Tags: programming-languages, semantics, functional-programming, object-oriented
---


# Question
Title: Size of Maximum Matching in Bipartite Graph
Am I correct in my observation that the cardinality of the maximum matching $M$ of a bipartite graph $G(U, V, E)$ is always equal to $\min(|U|, |V|)$?

# Answer
Given a bipartite graph $G = (U,V,E)$ and a maximum matching $M$ of $G$, via Konig's Theorem we see that $|M| = |C|$ where $C$ is a minimum vertex cover for $G$. Your statement is merely an upper bound on the size of the possible matching, not a strict equality.

The image on the wikipedia page provides a nice counterexample to your claim. We see that $|M| = 6$, while $\min(|U|,|V|) = 7$.

However, in the case of a complete bipartite graph $K\_{n,m}$ your statement holds.
> 13 votes

# Answer
No. For example, consider the case where the two sides are disconnected $|E| = 0$ or the case where a large group of nodes are all connected to the same single node:

$U = u\_1, u\_2, ..., u\_n$

$V = v\_1, v\_2, ... , v\_n$

$E = u\_1v\_1, u\_2v\_1, ... u\_nv\_1,$ $ v\_1u\_1, v\_2u\_1, ... v\_nu\_1$
> 9 votes

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


# Question
Title: Double-nested loop with bitwise operation
I have this little exercise:

```
for ( i = 0; i < 2 * n; i += 2 )
  for ( j = 1; j <= n; j <<= 1 )
    if ( j & i )
      foo ();

```

(`j <<= 1` means `j = (j << 1)`, where `<<` is the bitwise left shift operator. `&` is the bitwise and operator.)

I am supposed to determine how many times will the *foo* function be called for some *n*. The result should be both an exact number (or the most accurate approximation possible) and asymptotic (like O(n)).

# Answer
> 4 votes
The number of `foo()` calls is the number of 1 bits in all numbers from 0 to $n$ (or all even numbers between $0$ and $2n$ - same thing). Asymptotically, it's $O(n \log n)$, because the number of 1 bits is around $\log\_2(n)/2$.

I don't have an exact function. It won't be a smooth function - for example, $f(1023)-f(1022)=10$, but $f(1024)-f(1023)=1.$

---
Tags: time-complexity, imperative-programming, binary-arithmetic
---


title: Simple Task-Assignment Problem

text:
# Question
Title: Simple Task-Assignment Problem
I have this simple 'assignment' problem:

We have a set of agents $A = \\{a\_1, a\_2, \dotso, a\_n\\}$ and set of tasks $T= \\{t\_1, t\_2, \dotso, t\_m\\}$. Note that $m$ is not necessarily equal to $n$. Unlike the general assignment formulation in Wikipedia, a task $t\_c$ can only be assigned to an agent based on the task's preferred agents $ta\_c \subseteq A$. For example, if we have $ta\_1= \\{a\_1, a\_3\\}$, that means that task $t\_1$ can only be assigned to either agents $a\_1$ or $a\_3$. Now, each agent $t\_d$ has a quota $q\_d$ where $q\_d$ is positive integer. This means that $a\_d$ must be assigned with $q\_d$ number of tasks.

**The Problem**

Given above and a set of quota $\\{q\_1, q\_2, \dotso, q\_n\\}$, is there an assignment of tasks to agents such that all agents meet their respective quota $q$. Note that it is not necessarily that all tasks be assigned to an agent.

**Possible Solution**

I have tried reformulating this problem in terms of a bipartite graph $G(A, T, E = \cup ta\_c)$ and expressed as a form of matching problem where given a matching $M$, a vertex agent $a\_d\in A$ is matched up to $q\_d$ times or is incident to $q\_d$ edges in $M$ but the vertices in $T$ is incident to only one edge in $M$. Not really like the usual matching problem which requires that the edges in $M$ are pairwise non-adjacent.

However, it was suggested by someone (from cstheory, he knows who he is) that I could actually work this out as a maximum matching problem, by replicating an agent $a\_d$ into $q\_d$ vertices and 'conceptually' treat them as different vertices as input to the matching algorithm. The set of edges $E$ is also modified accordingly. Call the modified graph as $G'$

It is possible to have more than 1 maximum matchings from graph $G'$. Now, if I understand this correctly, I still have to check each of the resulting maximum matchings and see that at least one of them satisfies the $qouta$ constraint of each $agent$ to actually provide the solution to the problem.

Now, I want to prove that not finding one maximum matching $M$ $\in$ set of all maximum matchings of the graph $G'$ that satisfies the $qouta$ constraint of the problem guarantees that there really exists no solution to the problem instance, otherwise a solution exist which is $M$.

**I want to show that this algorithm always give correct result.**

**Question**

Can you share to me some intuition on how I might go to show this?

# Answer
As I stated on the CSTheory post, this is solved via maximum matching. The following should give enough intuition to show that each agent $a\_i$ has a $q\_i$-matching iff a transformed graph $G'$ has a matching. First, construct the graph $G$. Now, for each agent $a\_i$ and quota $q\_i$, make a new graph $G'$ that has $q\_i$ copies of $a\_i$. That is to say, if agent $a\_i$ has quota $q\_i = 3$, make 2 new nodes $a\_i', a\_i''$ that have the same tasks as $a\_0$.

Here is an illustration to help. Supposed we have the complete bipartite graph $K\_{2,3}$ where agent $q\_1 = 2, q\_2 = 1$.

Original graph $G$, and modified graph $G'$:

We see that agent $a\_1$ has two copies in the new graph $G'$, while agent $a\_2$ maintains just his lone copy. Solving for the maximum matching in $G'$ and then merging all copies of an agent to the original and you will have your best possible assignment. Since the edges are unweighted, one possible solution is (and merged solution):
> 3 votes

---
Tags: algorithms, graphs, proof-techniques, assignment-problem
---


# Question
Title: When are Dynamic and Lexical Scoping equivalent?
I am designing a small DSL and I know that implementing dynamic scoping (with a simple global stack) is easier then using full lexical scoping (each function needs its own scope/closure). What kind of features can be added that do not care how scope is implemented and what features would require a particular kind of scope implementation?

For example, if I have a very simple language that does not allow nested functions or function arguments I feel that both implementation choices are likely equivalent. On the other end of the spectrum, if I wanted to support returning inner functions then I'm pretty sure we would need to allow functions to save their own closures. However, I am not really sure what would happen in the middle if say, I alowed nested functions while not allowing them to be returned or if I allowed functions to be passed as arguments to other functions.

# Answer
> 7 votes
If you allow one function to call another, then you have enough power to distinguish a lexically defined variable from a dynamically defined one.

```
def scope {
  var x = 10
  def f() {
    return g()
  }
}
def g() {
  return x;
}
scope.f()

```

If `x` is dynamically scoped, the code returns `10`. If it is lexically defined, the result is an error.

Thus if you want a language where dynamic and lexical scoping behave the same, it will be a rather weak language.

---
Tags: programming-languages, semantics
---


# Question
Title: Büchi automaton with modified acceptance condition
Consider a Büchi automaton $\mathcal{A}$ with the modified acceptance condition, that an $\omega$-word $\mathcal{w}$ is accepted by $\mathcal{A}$ iff every run $\rho$ of $\mathcal{A}$ on $\mathcal{w}$ is accepting (rather than at least one run being accepting). I need to show that this automaton also accepts only $\omega$-regular languages. How do I go about doing that?

# Answer
Let $S$ and $F$ be the set of all states and all accepting states of $\mathcal{A}$, respectively. For $t \in S \setminus F$, let $\mathcal{A}$ be the automaton obtained by making $t$ the only accepting state. For $t \in S \setminus F$, let $\mathcal{B}\_t$ be the automaton obtained by removing all states in $F$, and making $t$ the starting state. We think of $\mathcal{A}\_t$ as an NFA, and of $\mathcal{B}\_t$ as a Büchi automaton. The following language is $\omega$-regular: $$ L = \overline{\sum\_{t \in S \setminus F} L(\mathcal{A}\_t) L(\mathcal{B}\_t)}. $$ An $\omega$-word $w$ is *not* in $L$ if and only if on some run of $\mathcal{A}$, no accepting state appears infinitely often. Therefore an $\omega$-word $w$ is in $L$ if and only if on all runs of $\mathcal{A}$, some accepting state appears infinitely often.
> 2 votes

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


# Question
Title: Phrase generators for use with testing grammars that don't use a seed
In helping someone understand phrase generators for use with testing grammars, think compiler test cases, I noted that I have never found a phrase generator that is knowledgeable of the grammar, and is deterministic. The phrase generators I am talking about rely on the grammar of the language as input so that the user does not have to recreate the rules for the grammar into a format acceptable for the tool. The tool must accept a BNF grammar; I don't mind if the grammar has to be factored some for the tool before input. Tools that rely on a seed or generate a random seed are what I want to avoid.

I am aware that one can use PROLOG to generate a parser and then run a query that outputs a set of results that are phrases used for testing. I also know that it is not uncommon for these result sets to have 10\**15 answers for basic cases of a grammar like C++.

Does anyone know of such tools? They can be commercial or open-source as I don't plan on using it, I have my own, I just want to verify my knowledge.

EDIT

The tool must encompass sematic knowledge of the compiler. In other words the phrases must be able to be compiled by a compiler, not just pass the syntactic rules.

EDIT

I agree that the comments and answers regarding deterministic are correct and I my use of the word here is not correct.

What I am looking for is a tool that not only takes in a BNF grammar and can use it "as is" which would mean for a grammar like C++ a basic result sets with 10\**30 items. That is not an accurate number but a realistic one based on a phrase generator I have that can report the number of results before generating the results. Since that size of a result set is impractical, I have given the tool the ability to enhance the grammar with constraints, thinking tree pruning. This allows one to generate phrases for one particular branch of the grammar, and also prune and limit the sub-braches and number of recursion over those branches. Even with the constraints each result item is a valid C++ file for use as input to a C++ compiler.

I have a proof of concept of this already, but the difference between a proof of concept and useful tool is a lot of work. So while a seed can be reused and create deterministic results, it does not allow the user to determine the conditions.

# Answer
> 4 votes
The tools you refer to are probably already deterministic. Tools that accept a seed *probably* only employ a pseudorandom generator which is keyed from the seed and nothing else. Therefore, given the seed, everything is completely deterministic. If the seeding process is reasonable, then a seed like $0$ or $1$ should work. For definiteness, I suggest you take your favorite "random" tool and use a fixed seed, say $1$. Now it's completely deterministic.

One reason you'd want a deterministic tool is *reproducibility*. You want to be able to reproduce phrases on demand. If the tool is random, that's impossible. However, if all the "randomness" is encapsulated in a user-entered seed, the output is reproducible; all you have to do is remember the seed used.

I cannot think of any other reason you'd want your tool to be deterministic, but if there is one, please let us know so that we can understand your question better.

---
Tags: reference-request, formal-grammars, context-free, parsing, software-testing
---


# Question
Title: Upper-bounding the number of comparisons for Sorting to $\Theta(n)$ using a physically big number like Number of Particles in the Universe
I recently read an article Scott Aaronson - Big Numbers . That has made me think about the effective upper-bound for sorting.

According to the article, some of the big numbers like the number of particles in the universe and age of universe in milliseconds are less than $10^{100}$.

In any realistic computational device, the data to be sorted will have to be lesser than these numbers. (As otherwise, it would be impossible to store the numbers physically).

$\log\_2(10^{100}) \approx 333$

Hence, if we take a number $C \> 333$, we can show that number of steps required for sorting an input of size $n$ will always be lesser than $Cn$

This makes sorting an $O(n)$ time operation using algorithms like QuickSort or HeapSort.

Is there a point I've wrongly considered while making this assumption?

**Should we consider physical constraints while analyzing algorithms? If not, why?**

# Answer
The reasoning is not wrong as such, but applying such constraints tends to make asymptotic analysis meaningless; for example we could simply choose $C' = 10^{100}$, and as all inputs are smaller than this, every algorithm is $O(1)$.

Despite the ability to limit the analysis physically and end up with trivial observations, asymptotic analysis (without imposing those limits) does give practical information about algorithms. When we run them, we can certainly notice the difference between, say, Merge Sort and Bubble Sort - even when we have physically very small instances (even less than 1000).

So by speaking about algorithms in this more general (though not necessarily physically accurate) way, we get genuine information about how we can expect algorithms to perform based on how big the input is. More importantly it allows us to compare them.

From a different perspective, if we accept that all possible instances are smaller than some (really really big) constant, then all algorithms take constant time, what we then need to consider is what that constant is - if it amounts to longer than a few years, we haven't learnt anything useful to humans who only live a few years. If we lived longer than the life of the universe, then perhaps we wouldn't care about anything smaller than the size of the universe.
> 5 votes

---
Tags: algorithm-analysis, sorting
---


title: Euler cycles in biconnected components

text:
# Question
Title: Euler cycles in biconnected components
If a graph has a Euler cycle, do the biconnected components have Euler cycles as well?

# Answer
Yes. If you start with a Euler cycle for the graph and restrict to a biconnected component, then what you have is still a cycle on the biconnected component (basically, if the euler cycle leaves vertex v in the biconnected component, then you know it must return to the biconnected component through v, otherwise we could enlarge our biconnected component - contradicting its maximality).
> 9 votes

---
Tags: graphs, eulerian-paths
---


# Question
Title: Can two neighbors in a graph be at the same depth in a DFS tree?
In an undirected graph, can two nodes at an identical distance n from the root of a DFS tree be neighbors in the original graph? I'm thinking no, but I'm not sure (because of back edges)

# Answer
> 3 votes
I think you are correct:

All neighbors of a node will be of rank one less (the node we got here from) or one more (or two more, etc) because we will rank them before we back out of the node.

# Answer
> 3 votes
The wikipedia article states that "it can be shown that if the graph is undirected then all of its edges are tree edges or back edges."

If you find out how this can be shown, you should be quite close to your solution.

# Answer
> -1 votes
Your question does not stipulate how the DFS tree is generated. Naive implementations simply list nodes in the order they are visited, but most practical implementations rebuild the output tree as the search progresses and the ranks of the nodes are adjusted.

Consider three nodes, A B C, connected to each other. A naive DFS will visit A B C, with ranks of 0 1 2, and the tree will have a back edge from C to A. A more useful implementation will backtrack from C to B to A, and then from A will travel to C again and assign it a rank of 1, then decline to travel to B at rank 2 because B is already rank 1, this tree will have both B and C at rank 1 below A, with a cross edge between B and C.

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


title: Unique path in a directed graph

text:
# Question
Title: Unique path in a directed graph
I'm designing an algorithm for a class that will determine if a directed graph is unique with respect to a vertex $v$ such that for any $u \ne v$ there is at most one path from $v$ to $u$. I've started by using BFS (breadth-first search) to find the shortest path from v to another vertex u, and then running BFS again to see if an alternate path can be found from v to u. I think this is too time consuming however. Does anyone have any hints as to how the solution can be found with a shorter execution time?

# Answer
> 9 votes
Use BFS to work backwards from v, flagging each vertex as 'visited' as you go. If you ever hit a vertex you've previously visited, your graph doesn't have the uniqueness property. Otherwise, it does.

# Answer
> 4 votes
Look at the Max Flow Min Cut algorithm.

# Answer
> 2 votes
It's a simple modification of any graph traversal: if you find an edge to a previously marked node, then you have multiple paths.

---
Tags: graphs, shortest-path, graph-traversal
---


# Question
Title: Some questions on parallel computing and the class NC
I have a number of related questions about these two topics.

First, most complexity texts only gloss over the class $\mathbb{NC}$. Is there a good resource that covers the research more in depth? For example, something that discusses all of my questions below. Also, I'm assuming that $\mathbb{NC}$ still sees a fair amount of research due to its link to parallelization, but I could be wrong. The section in the complexity zoo isn't much help.

Second, computation over a semigroup is in $\mathbb{NC}^1$ if we assume the semigroup operation takes constant time. But what if the operation does not take constant time, as is the case for unbounded integers? Are there any known $\mathbb{NC}^i$-complete problems?

Third, since $\mathbb{L} \subseteq \mathbb{NC}^2$, is there an algorithm to convert any logspace algorithm into a parallel version?

Fourth, it sounds like most people assume that $\mathbb{NC} \ne \mathbb{P}$ in the same way that $\mathbb{P} \ne \mathbb{NP}$. What is the intuition behind this?

Fifth, every text I've read mentions the class $\mathbb{RNC}$ but gives no examples of problems it contains. Are there any?

Finally, this answer mentions problems in $\mathbb{P}$ with sublinear parallel execution time. What are some examples of these problems? Are there other complexity classes that contain parallel algorithms that are not known to be in $\mathbb{NC}$?

# Answer
> Third, since $\sf{L} \subseteq \sf{NC}^2$, is there an algorithm to convert any logspace algorithm into a parallel version?

It can be shown (Arora and Barak textbook) given a $t(n)$-time TM $M$, that an oblivious TM $M'$ (i.e. a TM whose head movement is independent of its input $x$) can construct a circuit $C\_n$ to compute $M(x)$ where $|x| = n$.

The proof sketch is along the lines of having $M'$ simulate $M$ and defining "snapshots" of its state (i.e. head positions, symbols at heads) at each time-step $t\_i$ (think of a computational log). Each step $t\_i$ can be computed from $x$ and the state $t\_{i-1}$. Because each snapshot involves only a constant-sized string, and there exist only a constant amount of strings of that size, the snapshot at $t\_i$ can be computed by a constant-sized circuit.

If you compose the constant-sized circuits for each $t\_i$ we have a circuit that computes $M(x)$. Using this fact, along with the restriction that the language of $M$ is in $\sf{L}$ we see that our circuit $C\_n$ is by definition *logspace-uniform*, where uniformity just means that our circuits in our circuit family $\\{C\_n\\}$ computing $M(x)$ all have the same algorithm. Not a custom-made algorithm for each circuit operating on input size $n$.

Again, from the definition of uniformity we see that circuits deciding any language in $\sf{L}$ must have a function $\text{size}(n)$ computable in $O(\log n).$ The circuit family $\sf{AC}^1$ has at most $O(\log n)$ depth.

Finally it can be shown that $\sf{AC}^1 \subseteq \sf{NC}^2$ giving the relation in question.

> Fourth, it sounds like most people assume that $\sf{NC} \neq \sf{P}$ in the same way that $\sf{P} \neq \sf{NP}$. What is the intuition behind this?

Before we go further, let us define what $\sf{P}$-completeness means.

A language $L$ is $\sf{P}$-complete if $L \in \sf{P}$ and every language in $\sf{P}$ is logspace reducible to it. Additionally, if $L$ is $\sf{P}$-complete then the following are true

1. $L \in \sf{NC} \iff \sf{P} = \sf{NC}$
2. $L \in \sf{L} \iff \sf{P} = \sf{L}$

Now we consider $\sf{NC}$ to be the class of languages efficiently decided by a parallel computer (our circuit). There are some problems in $\sf{P}$ that seem to resist any attempt at parallelization (i.e. Linear Programming, and Circuit Value Problem). That is to say, certain problems require computation to be done in a step-wise fashion.

For example, the Circuit Value Problem is defined as:

> Given a circuit $C$, input $x$, and a gate $g \in C$, what is the output of $g$ on $C(x)$?

We do not know how to compute this any better than computing all the gates $g'$ that come before $g$. Given *some* of them may be computed in parallel, for example if they all occur at some time-step $t\_i$, but we dont know how compute the output of gates at timestep $t\_i$ and time-step $t\_{i+1}$ for the obvious difficulty that gates at $t\_{i+1}$ require the output of gates at $t\_i$!

This is the intuition behind $\sf{NC} \neq \sf{P}$.

---

Limits to Parallel Computation is a book about $\sf{P}$-Completeness in similar vein of Garey & Johnson's $\sf{NP}$-Completeness book.
> 9 votes

# Answer
> Fifth, every text I've read mentions the class RNC but gives no examples of problems it contains. Are there any?

The paper "Matching is as Easy as Matrix Inversion" by Mulmuley, Vazirani, and Vazirani has several examples of problems in class $\mathbb{RNC}^2$. The main one is finding a maximal matching, then they reduce other problems to this one.
> 3 votes

---
Tags: complexity-theory, reference-request, parallel-computing, complexity-classes
---


# Question
Title: Best-Case Running Time For Binary Search Tree Insertion
The notion of best-case running time is kind of ambiguous for me. According to wikipedia, the definition of best case running time is:

> The term best-case performance is used in computer science to describe the way of an algorithm behaves under optimal conditions. For example, the best case for a simple linear search on a list occurs when the desired element is the first element of the list.

According to this definition, the best case running time for BST insertion should be $O(1)$ \[consider that we are inserting to the root node\]. But different resources says different things, some claim that it is $O(\log n)$ \[perfect balanced tree\] and some others claim that it is $O(1)$ which one should I believe?

# Answer
Both! That is, if you are lenient with what "best-case" means. The best-case is the input for respectively run¹ of an algorithm which minimises runtime (for a given size). I guess that some of your sources refer to (asymptotically) optimal BST implementations, either them or you mixing up the notions.

These are the facts:

* For any (reasonable) binary search tree implementation, the *best-case* insertion time is certainly $O(1)$ (for all sizes): all nodes are in the root's right subtree, the one to be inserted belong in the left.
* An *optimal* binary search tree implemenentation has *worst-case* insertion time in $\Theta(\log n)$; it is height-balanced (examples include AVL- and Red-Black-trees).

---

1. That's equivalent for deterministic algorithms; for nondeterministic ones you consider runs.
> 3 votes

---
Tags: terminology, data-structures, runtime-analysis, binary-trees
---


# Question
Title: How to prove that the pre-order tree traversal algorithm terminates?
I see **structural induction** the usual way for proving an algorithm's **termination** property, but it's not that easy to prove by means of induction on a **tree** algorithm. Now I am struggling on proving that the pre-order tree traversal algorithm is terminable:

```
preorder(node)
  if node == null then return
  visit(node)
  preorder(node.left)
  preorder(node.right)

```

How should I prove?

# Answer
> 1 votes
Hint (by Raphael): How do you prove that the recursive factorial function terminates?

Answer (by Kejia): The recursive factorial function's universe is non-negative integers, which is countable and so well-found, and so it is very easy to prove with mathematical induction.

By analogy, we can find a mapping from trees to a well-founded universe so that a similar proof works.

> Our mapping is to the size of the subtree. At each recursive call, the size of a subproblem (i.e. a subtree) is strictly decreasing and always non-negative. Therefore, we can proceed by induction.
> Suppose (induction hypothesis) that the function on a tree of size of at most k terminates. Now consider an input tree with k+1 nodes...

---
Tags: algorithms, data-structures, algorithm-analysis, correctness-proof, induction
---


title: definition of formula validity

text:
# Question
Title: definition of formula validity
I read in some sources that valid formulas are tautologies (valid under every evaluation). In the others, I read that these are formulas that have conclusions true when premises are true. Are these just equivalent definitions because ⊨ P → Q is equivalent to P ⊨ Q?

# Answer
> 3 votes
Yes. These definitions are equivalent, noting that not all valid formula have the form $P\to Q$, though any formula $Q$ is equivalent to $\top\to Q$.

---
Tags: terminology, logic, logical-validity
---


# Question
Title: How many possible assignments does  a CNF sentence have?
I'm having some trouble understanding the following:

When we look at satisfiability problems in conjunctive normal form, an underconstrained problem is one with relatively few clauses constraining the variables. For eg. here is a randomly generated 3-CNF sentence with five symbols and five clauses. (Each clause contains 3 randomly selected distinct symbols, each of which is negated with 50% probability.)

```
(¬D ∨ ¬B ∨ C) ∧ (B ∨ ¬A ∨ ¬C) ∧ (¬C ∨ ¬B ∨ E) ∧ (E ∨ ¬D ∨ B) ∧ (B ∨ E ∨ ¬C)

```

16 of the 32 possible assignments are models of this sentence, so, on an average, it would take just 2 random guesses to find the model.

I don't understand the last line- saying that there are 32 possible assignments. How is it 32? And how are only 16 of them models of the sentence? Thanks.

# Answer
There are 5 (Boolean) variables in the formula. Each of these could be either *true* or *false*. This means that there are $2^5=32$ ways of assigning values to these variables.

Of the 32 possibilities, only 16 of them make the formula true – this would have to be checked by hand (or machine).
> 10 votes

---
Tags: logic, combinatorics, satisfiability
---


# Question
Title: What could you learn from studying player movement and behaviour on online FPS games?
Just thinking of Counter Strike as a canonical example, if you have a coordinate representation of the map and for every player you have a complete history of everything you might need for every moment of time, say every 10 miliseconds or something and you just recorded where the players went around the map, and what they did. So maybe, for example, at each time `t` you had `v(t)` a vector function whose components are (`location(t)`, `velocity(t)`, `rotationVector(t)`, `rotationVelocity(t)`, `isFiring(t)`, `ammoCount(t)`, `health(t)`, `isEnemyVisible(t)`, `isTeamMateVisible(t)`) or whatever other measurements you think would be useful for the state space.

If you collected a bunch of data like this what sort of hypotheses or models would you consider testing? Would it be possible to construct a probabilistic model to classify histories and possibly predict outcomes of player-enemy encounters? Could you train AI bots on this data?

# Answer
> 3 votes
File each given vector function with the win/loss of the game and the team each vector was on. Applications of this data: To gauge map balance and provide the least advantage to any one particular team.

Determine how particular elements of the map effect balance.

Make bots more effective by determining common strategies employed against bots, and the manner in which players address situations (going with the counter strike example: We're down players lets group up on the objective).

It would be interesting to see which would provide better balance or more effective bots, conventional testing or this in-depth vector analysis.

# Answer
> 1 votes
Probably if you apply machine learning methods to the basic movements/fire actions of a specific player you can develop an AI bot that plays well against that player.

But adding more high level actions like targets, waypoints, coordinated team actions, terrain features, and so on, you'll probably end up with models that has already been developed for *REAL war scenarios* :-(

See for example Google results for "combat models soldier behaviour" or "combat XXI simulation model"

---
Tags: machine-learning, computer-games
---


# Question
Title: Subtracting lower-order term to prove subtitution method works
Substation method fails to prove that $T(n)=\Theta(n^2) $ for the recursion $T(n)=4T(n/2) + n^2$, since you end up with $T(n) \< cn^2 \leq cn^2 + n^2$.

I don't understand how to subtract off lower-order term to prove that substitution works.

Came up with: $T(n) \leq cn^2 - bn^2$

Assume it holds for $T(n/2) \leq c(n/2)^2 - b(n/2)^2$

$T(n) \leq 4(c(n/2)^2 - b(n/2)^2) + n^2 = cn^2- bn^2 + n^2 $

However, there is no way to solve $cn^2- bn^2 + n^2 \leq cn^2 - bn^2 $ for $b$

# Answer
If you're using the same book I have (Introduction to Algorithms 3rd edition), then you mis-wrote the question. The relation in question should be: $T(n)=4T(n/2) + n.$

That said, substitution here won't work, as you know. Assuming $T(n) \le cn^2,$ you get:

$T(n)\le4T(n/2) + n$

$T(n)\le4(c\frac{n^2}{4}) + n$

$T(n)\le cn^2 + n$

Which doesn't imply $T(n) \< cn^2.$ Instead, you can make the assumption: $T(n) \le cn^2 - bn.$

$T(n)\le4T(n/2) + n$

$T(n)\le4(c\frac{n^2}{4}-b\frac{n}{2}) + n$

$T(n)\le cn^2 + n(-2b + 1)$

Letting $b=1,$ you get an equation consistent with the initial asumption. Namely:

$T(n)\le cn^2 - n$

As a side note, the relation you initially wrote, $T(n)=4T(n/2) + n^2,$ can be solved using case 2 of Master's Theorem, and has an answer of $\Theta(n^2lg(n))$
> 5 votes

---
Tags: asymptotics, recurrence-relation, landau-notation
---


# Question
Title: Collisions of prefixes of MD5 hashes in some fixed interval
I was wondering, if there is an MD5 hash collision in the UNSIGNED MEDIUMINT Range (0 - 16777215). Sadly, I'm unable to run a script to check this myself, due to Memory (RAM) limitations. The answer is probably no; the next step would be - how many characters are even needed, until the first collision is found?

An MD5 hash has 32 Characters. If you only would use, lets say, the first nine characters from all MD5 hashes in the MEDIUMINT range, would they still all be unique?

The reason behind this: I'm trying to find a simple way to basically use an MD5 hash for every number in the MEDIUMINT range, to create a short, unique string, preferably not longer than 9 letters -- as abstraction to the actual number (so instead of an `1`, you get something like `c4ca4238a`)

Are the first nine characters of all MD5 hashes in the UNSIGNED MEDIUMINT (whitout 0) range unique?

# Answer
Just to complete Yuval's answer, there are plenty of collisions if you pick the first 9 digits of the MD5.

For example:

```
md5('40236')  = f46657d67 3d95ccf8d12b1075ab7c653
md5('400704') = f46657d67 e7a3de02f64013bfcbd932c

```

Let $m = 2^{36}$ (nine hex digits), $n = 2^{24}$ (three bytes for an UNSIGNED MEDIUMINT); assuming that MD5 is a good hash :), the probability $P(n)$ of a collision is:

$1 - m! / (( m - n )! * m^n) \approx 1 - e^{-n^2/2m} = 1 - \frac{1}{e^{2048}}$

And you'll find a collision on the first 9 digits with high probability ($P(n) \approx 0.99$) every $n = 2^{20}$ strings picked (*whatever they are*). See Birthday problem on Wikipedia.

So even if you use the binary encoding (three bytes) you obviously get plenty collisions:

Starting from 000000, the first is:

```
md5( 0x013701 ) = 8015b8be cf7b0a7e744cd54ac76a302f
md5( 0x0725c6 ) = 8015b8be cf8140319e919766901824bf

```

Note that 0x0725c6 is a 19 bit number.
> 5 votes

# Answer
Every number in the range $0$ to $2^{24}-1$ can be represented by:

* $8$ digits
* $6$ lower-case letters
* $5$ symbols, each of which is either a digit or a lower-case letter
* $4$ symbols, each of which is either a digit, a lower-case letter, an upper-case letter, a comma, or a period

There's no need to bother with MD5.
> 4 votes

---
Tags: cryptography, hash
---


# Question
Title: If the “is P equals to NP?” is a NP-COMPLETE, what does it tell us?. Some conclusions?
If there is someone can prove that the problem "is P equals to NP?" is a NP-COMPLETE problem, what we can conclude from this?

# Answer
"$\mathsf{P}$ vs. $\mathsf{NP}$" is not a computational problem that depends on an input, we don't have any input on which the computation will depends on, therefore the complexity does not make much sense. The complexity of a computational problem is defined w.r.t. an input that varies (e.g. we will need more time to solve the problem for larger inputs).

For any problem that does not depend on a varying input there *exists* a trivial algorithm that solves the problem in unit time: either the algorithm that always outputs YES solves the problem or the algorithm that always outputs NO solves it. We may not know which one, but what we know or don't know is irrelevant, what is important is the existence of an algorithm running in constant time solving the problem. In short, any computational problem with no varying input is computationally trivial.

We can think of this question as an instance of a computational problem like "given a first order formula $\varphi$ in the language of arithmetic, is $\varphi$ true?". However it does not make sense to say a problem instance is $\mathsf{NP\text{-}complete}$, complexity theory concepts like $\mathsf{NP\text{-}complete}$ness are defined for languages which are sets of instances. A language containing a single instance is trivial from computational perspective.
> 4 votes

# Answer
While Kaveh's answer is perfectly satisfactory and complete, I can direct you to the following survey article: On P vs NP and Geometric Complexity Theory by K.D. Mulmuley, in which he gives an overview of the "flip theorem" which seems to be a rigorous formulation of the idea "what does P vs NP have to say about it's own provability?".

Informally the theorem states (as far as I understand) that if certain well-believed conjectures in complexity theory are true, then P$\neq$NP only if there is a certain procedure to construct "obstructions" to circuits of size polynomial in $n$ that claim solve the SAT problems of a certain size $n$. Here an obstruction for a given circuit $C$ is essentially an input $S$ such that $C$ gives the *wrong* answer for input $S$. The theorem further states that these obstructions are "small" in the sense that they can be coded in logarithmic number of bits in $n$, which make it easy to find such obstructions in P time.

The theorem is stated and proven in this article by the same author.
> 2 votes

---
Tags: complexity-theory, p-vs-np
---


title: Turing complete and computational power

text:
# Question
Title: Turing complete and computational power
In a lecture a professor mentioned that modern computers don't have as much computational power as a Turing machine because they don't have infinite memory, and since no computer can have infinite memory the Turing machine is therefore unattainable and simply represents the upper limit of computing. Is there a measure, or definition of what problems (or class of problems) lie beyond the reach of our computing power because of this?

# Answer
If we think of the universe as finite, then anything that needs more memory than that finite amount is beyond our computational ability.

However this is not a good model for studying computability, the Turing machine model works much better in reality and that is the reason we use it for studying computation on real computers. A Turing machine doesn't really need an infinite amount of memory, it only needs an *unbounded* amount of memory. For example, we can provide additional memory to a computer over time (as the computer needs more and more memory) and then we have something similar to a Turing machine. If we assume that we have unbounded amount of time and memory for finishing our computation then the Turing machine captures this concept of computability in principle quite nicely.

Check the Wikipedia article about Turing machines, there is a section that discusses the relevance of the model.

If you are interested in *feasible* computability, then complexity theory (where we consider various amount of resources like time and space for performing a computational task) is closer to the what we can really do in practice than computability theory. Many experts state that the feasible computations fall in the complexity class $\mathsf{P}$ (and more recently in probabilistic and quantum versions of $\mathsf{P}$, i.e. $\mathsf{BPP}$ and $\mathsf{BQP}$).
> 12 votes

# Answer
You might consider Linear Bounded Automaton and corresponding languages are the context-sensitive languages. See Chomsky Hierarchy to know which languages are beyond the reach of such automata.

btw, in some sense, some "unreachable" problems now become within reach, because of the restricted computing power!

For instance, Halting Problem for Turing Machines is undecidable, but it is decidable for Linear Bounded Automata.
> 5 votes

# Answer
The theory of computation is an abstraction of the real world. In many ways, the abstraction isn't a great fit for the real world. For one, we can't make computers with unbounded memory; so we can't even make machines to recognize arbitrary regular languages - or even arbitrary finite languages!

This turns out not to be too big of a problem, though; in the real world, we can't even construct inputs of any arbitrary size, and even if we could, we wouldn't be around long enough to see the answer.

In a strict sense, then, no: the class of physically realizable computers is strictly less powerful than the class of Turing machines. It's strictly less powerful than the class of finite automata, as well.
> 4 votes

---
Tags: computability
---


# Question
Title: How to prove that BFS directed-graph traversal algorithm terminates?
How to prove that BFS directed-graph traversal algorithm terminates? (I copy the pseudocode from here) Input: A graph G and a root v of G.

```
  procedure BFS(G,v):
      create a queue Q
      enqueue v onto Q
      mark v
      while Q is not empty:
          t ← Q.dequeue()
          if t is what we are looking for:
              return t
          for all edges e in G.incidentEdges(t) do
             o ← G.opposite(t,e)
             if o is not marked:
                  mark o
                  enqueue o onto Q

```

# Answer
The only potentially non-terminating construct used here is the while loop. So you need to prove that `Q` eventually becomes empty.

`Q` contains vertices from the graph. The only operations that add elements to `Q` are the `enqueue` operations. Each adds a single vertex. So proving the termination of the algorithm is equivalent to proving that only a finite number of enqueue operations are performed.

The first call to `enqueue` at the beginning of the program adds one vertex and marks it. The second call to `enqueue` adds a vertex that was not marked yet, and the vertex is marked at the same time.

Since a vertex is never unmarked, the set of marked vertices can only grow.

The set of marked vertices is included in the set of all vertices. Note that the graph is be assumed to be finite (in an infinite graph, the search might not terminate). Hence there are at most $|G|$ `mark` operations where $|G|$ is the number of vertices in the graph. Since each `enqueue` operation has a corresponding `mark`, there are at most $|G|$ `enqueue` operations. Therefore there are at most $|G|$ `dequeue` operations. Since there is one `dequeue` operation at each loop iteration, there are at most $|G|$ iterations of the `while` loop, a finite number.
> 2 votes

---
Tags: algorithms, algorithm-analysis, correctness-proof
---


# Question
Title: Prove that the complement of  $\{0^n1^n \mid n \geq{} 0\}$ is not regular using closure properties
I want to prove that the complement of $\\{0^n1^n \mid n \geq{} 0\\}$ is not regular using closure properties.

I understand pumping lemma can be used to prove that $\\{0^n1^n \mid n \geq{} 0\\}$ is not a regular language. I also understand regular languages are closed under complement operation. However, does that also imply that a non-regular language's complement is also non-regular?

# Answer
Yes. Since the complement of a regular language is also a regular language, then it follows that the complement of a non-regular language must also be non-regular. Strictly speaking, this works since the complement is its own inverse.
> 9 votes

---
Tags: formal-languages, regular-languages, closure-properties
---


# Question
Title: Rigorous proof against pseudorandom generator
I am trying to teach myself the principles of cryptograhpy, and want to solve the following question:

> Let G be the algorithm that takes an input x = (x1, . . . , xn) from {0, 1} n (so each xi ∈ {0, 1}) and outputs the string G(x1, . . . , xn) = (x1, . . . , xn, x1 ⊕ x2) in {0, 1} n+1. Rigorously prove that G is not a pseudorandom generator.

So, we would want to prove that either **expansion** doesn't hold (for all n, l(n) \> n), which, in this case, would mean that for each x, the corresponding G \> x, or **pseudorandomness** doesn't hold ( For efficient algorithm D, there is a negligible function 'n' such that:

> Pr\[D(r) = 1\]-Pr\[D(G(s)) = 1\] $\leq$ $\epsilon$(n),
>
> where 'r' is uniform on {0,1}$^{l(n)}$ and 's' is uniform on {0,1}$^n$

), which, in this case, means that we need to prove that there does not exist a function n such that the difference of the probabilities of the function D(r) and D(G(s)) is very small.

Now, I understand these concepts, but I am having trouble approaching this problem practically... what would be the best way to start?

# Answer
Your definition of pseudorandomness is misleading. A better definition would start with a function with "expansion", and then state then it is indistinguishable from random. In your case, the function is "expanding" since it takes $n$ bits and outputs $n+1$ bits. However, the $n+1$ bits it produces don't look random. Can you tell why?
> 5 votes

# Answer
An equivalent requirement for the pseudo-randomness property is to pass the *next-bit test* (as proven by Yao, see https://en.wikipedia.org/wiki/Next-bit\_test).

This "test" means that if you are given output bits $x\_1,...,x\_n$ of the generator, you will not be able to guess the next bit $x\_{n+1}$ (except with a negligible advantage over 1/2, which is the probability to guess an unknown bit.)

Clearly, the generator you suggest doesn't pass the next-bit test and is not a pseudo-random generator.
> 4 votes

---
Tags: correctness-proof, pseudo-random-generators
---