# Question
Title: Is the set of TMs that accept exactly two strings (each) semi-(decidable)?
I have found this problem-

> let A be the set of encoding of all those Turing machines that accept exactly two strings and let A' be the complement of A. Comment on whether A and A' are recursive , recursively enumerable or not recursively enumerable.

I am clueless at "exactly 2 strings". I have tried many books but I can't solve it. Please help.(Any hint is acceptable)

# Answer
This is a trivial application of Rice's theorem.

Define:

$$S\_A = \\{ L \in RE \mid |L|=2\\}$$

It is a non-trivial subset of $RE$ (for instance, it contains $\\{0,1\\}$ and it doesn't contain $\\{\varepsilon\\}$). Then By Rice's Theorem

$$ A = \\{ \langle M \rangle \mid L(M) \in S\_A\\}$$ is undecidable. Note that $A$ is exactly the language stated in the question.

There is also an extended version of Rice's theorem that will show that $A$ is not even $RE$.
> 2 votes

---
Tags: computability, undecidability, semi-decidability
---


# Question
Title: Recovering the transition function of a Turing machine with a known number of states
Suppose we have a Turing Machine and know how many states it has as well as bound on its running time, but do not initially know its transition function. Is it possible to determine its transition function (up to a relabeling of its states and disregard for inaccessible states) by noting its behavior on only finitely many strings? (By behavior I mean a record of its computation histories leaving out the information of which state it is in at any particular step.)

On the one hand, there are only finitely many Turing machines with a set number of states, so we could definitely run them on all of the finitely many given strings to determine if a given transition function is *not* a candidate. However, I realize that Rice's Theorem might prevent us from determining the behavior on all inputs given only its behavior on inputs up to a given length. Even if it is not possible for Turing machines to recover its transition function, is it possible for simpler computation models like DFA's and PDA's? Thanks for your help.

# Answer
> 1 votes
Yes, this is possible. This is not really a question about Turing machines so much as a question about learning DFAs given membership queries (you provide an input to the DFA and learn whether it accepts or not, and in the case of a finite-state transducer, the output it produces). Therefore, decidability doesn't really enter into it.

If you know the number of states in the FSM of the Turing machine, yes, observing its behavior on finitely many strings is enough. You can use Biermann's algorithm to infer a FSM that is consistent with the observed behavior.

You can think of Biermann's algorithm as basically just using SAT, where for each string $u$, you have a variable $s\_u$ to represent the state the FSM is in after reading string $u$. If the FSM has $n$ states, then each $s\_u$ must be one of $n$ possible values. You can use the outputs to deduce some relationships on these variables: e.g., the FSM's behavior on input sequence $u$ differs from its behavior on input sequence $v$, then we obtain the constraint $s\_u \ne s\_v$. Also, you get some additional relationships due to the fact that this is a FSM: $s\_u = s\_v \implies s\_{uw} = s\_{vw}$ for all $u,v,w$.

Biermann's algorithm yields an (exponential-time) algorithm for finding a FSM that is consistent with all of the observations, if one exists. Learning a FSM given just membership queries is NP-hard, so you can't expect a more efficient solution in this model.

Biermann's algorithm only promises to give you a FSM that is consistent with all of the observations. How do we know whether this will match the FSM of the Turing machine? In general, we don't, but in this case we can use our knowledge of the number of states of the FSM to solve this. In particular, suppose we know there are $n$ states in the FSA of the Turing machine (after it has been minimized). We apply Biermann's algorithm to check whether there exists a FSM that's consistent with all the observations and uses $n$ states, and use Biermann's algorithm to check whether there exists a FSM that's consistent with all the observations and uses $n-1$ states. If the answers are yes and no, respectively, we are done. If the answers are yes and yes, then we generate more observations until we're done (this can be done systematically in a way that will terminate, by using knowledge of the candidate FSM with $n-1$ states).

I am assuming by "observe its behavior" you mean "observe each step of the execution of the Turing machine on some input". This lets you treat the FSM as a finite-state transducer and observe the output of the FSM for any desired sequence of inputs, by providing an appropriate input to the Turing machine.

If you don't know the number of states in the FSM, it's easy to prove that you can never know when you have the full thing (this is an easy adversary argument).

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


# Question
Title: Is every file an integer amount of bytes?
I'm not sure whether I'm asking on the right site, since all the other questions seem to be a lot more abstract and theoretical. If I should remove the question, please tell me.

Are all files on my computer an integer amount of bytes? That is, does every file on my computer consist of an amount of bits divisible by 8? Or are there files that are, for example, 300 bits (37 and a half byte), or 301 bits (37.625 bytes)?

Follow-up question: does this mean that every file can be 'read' using a program that reads ASCII encoded files? (Of course the output would be nonsense, but the program shouldn't notice any difficulties, right?)

# Answer
> 5 votes
Yes, every file has an integer amount of bytes. In fact, most file systems deal with blocks or clusters of bytes. If cluster size is 64KB a file may claim to take up 250KB, but it will actually take 4 clusters or 256KB. This reduces the problem of fragmentaton (now fragments can only get so small, and there can only be so many of them) and the problem of addressing (how big do addresses need to be to access any byte in your 500GB drive? Now the addresses can be shorter by 16 bits).

---
Tags: filesystems
---


# Question
Title: Underlying language to specify various types of logic
There exist several different types of logic -- 1st order, 2nd and higher order with many different sets of inference rules possible.

What I'm having trouble understanding is what's the "underlying logic" we use to talk about the various different types of logic. For instance, if we were limited to thinking in terms of $i$th order logic, then we couldn't talk about $\>i$th order logics but we can. Does this mean that the logic we think in terms of is more powerful than any $n$th order logic?

Sorry this is so vague but I'm having a hard time formulating my question exactly.

Edit: Turing machines cannot even decide all statements in first-order logic -- so does this imply some sort of relation between first-order logic and any other logic that we can think of (as humans are no more powerful than TMs)?

# Answer
> 4 votes
One answer is that we use English, but that's not what you're looking for.

To make the question more precise, let us ask what sort of formalism is useful for describing logics. This is still quite broad, because a logic has several parts: syntax, rules of inference, semantics, etc.

Syntax is pretty well understood and we know that the syntax of a language can be described in terms of formal grammar. That is a well developed theory. In any case, concrete syntax is rather boring from the point of view of logic.

It is far more interesting to ask what we need to specify the inference rules for a logic. Because a general logic can be just about any formal system, let us consider only traditional logics: classical first-order, intuitionistic first-order, second order, higher-order, simple type theory, dependent type theory and so on. One answer is that we should use a **logical framework** (LF). It is a variant of type theory designed in such a way that when we specify a logic in it we have:

> *A statement in the logic is provable if, and only if, the corresponding type in the logical framework is inhabited.*

This is desirable because it says that the logical framework is neither too weak nor too powerful.

In terms of logical strength LF is very weak: it is a dependent type theory with first-order kinds and $\Pi$'s. Speaking vaguely and in terms of logical connectives, this is a bit like using as our meta-theory a logic which has only $\forall$ and $\Rightarrow$ (and no equality).

There are implementations of logical frameworks, for instance Twelf. Of course, the point of such a tool is not just description of logics, but also the study of their meta-theoretic properties. Among the Twelf case studies you can find formalization in LF of cut elimination, the double negation translation, classical modal logic S5, and a bunch of more programming-language oriented examples.

One may also ask what formalism is necessary to specify semantics of a logic. The semantics of traditional classical first-order logic goes under the name of *Tarski model theory* and uses set theory, although it is well known that a much weaker system suffices (a fragment of Peano arithmetic). Other kinds of logic require different approaches, but in general it is the case that the meta-theory needed for the description of semantics is much less complicated than the semantics itself. For instance, the models of intuitionistic higher-order logic are elementary toposes. The axioms for an elementary topos are essentially algebraic, i.e., we can express all the axioms of an elementary topos with equations (we do not even need *any* logical connectives, just equations), see Section II.2 of Lambek and Scott's "Introduction to Higher-Order Categorical Logic".

# Answer
> 2 votes
As you may know, "interesting" classes of language often correspond to "interesting" classes of automata and also "interesting" algebras. For example, regular languages correspond to NFAs/DFAs, and Kleene algebras.

It's the same with logic. Interesting logics often corresponding to interesting category structures, interesting programming languages, and so on. So, for example, intuitionistic logic corresponds to Cartesian-closed categories and also to the simply-typed lambda calculus. Modal logic systems also have graph theoretic interpretations, with different axiom systems corresponding to different classes of graph.

In a sense, this is what you'd hope, right? It's gotten to the point where we expect "interesting" objects in one subfield to be isomorphic to "interesting" objects in another subfield. So it's difficult to say that there is a language "underlying" them.

The world seems to have converged on Gentzen notation (e.g. sequent calculus) to describe logical deduction systems, so that could be considered an "underlying language".

However, any sane logic needs to obey at least the following rules:

* If A is a judgement, then A entails A (i.e. deduction is reflexive).
* If A, B, and C are judgements, and A entails B and B entails C, then A entails C (i.e. deduction is transitive).

Add an associative law, and it follows that any reasonable deduction system forms a mathematical category. So category theory could be considered an "underlying language", too.

In the specific case of first-order classical logic, it has a well-understood game theoretic equivalent.

---
Tags: logic, higher-order-logic
---


# Question
Title: Proof of Minsky Papert Symmetrization technique
I frequently hear about the Minsky-Papert Symmetrization technique in many papers with a reference to the book of Minsky. I could not locate the book online. Could someone supply me a proof of the symmetrization technique?

For instance, it is used in Lemma $5$ in this paper http://www.csee.usf.edu/~tripathi/Publication/polynomial-degree-conference.pdf

# Answer
> 3 votes
Over $0/1$ inputs we have $$ \begin{align\*} (y\_1+\cdots+y\_N)^0 &= 1 \\ (y\_1+\cdots+y\_N)^1 &= \sum\_i y\_i \\ (y\_1+\cdots+y\_N)^2 &= \sum\_i y\_i+2\sum\_{i\<j} y\_iy\_j \\ (y\_1+\cdots+y\_N)^3 &= \sum\_i y\_i+6\sum\_{i\<j} y\_iy\_j + 6\sum\_{i\<j\<k} y\_iy\_jy\_k \end{align\*} $$ And so on. It follows that for $0/1$ inputs, $p\_{sym}$ can be written as a linear combination of $(y\_1+\cdots+y\_n)^0,\ldots,(y\_1+\cdots+y\_n)^d$, where $d$ is its degree. This linear combination can also be viewed as a polynomial $\tilde{p}$ in $y\_1+\cdots+y\_n$, which is equal to $p\_{sym}$ for $0/1$ inputs.

---
Tags: polynomials
---


# Question
Title: Where can I find a study on the amount of different word frequencies in a corpus?
I need to know how many different values the frequency of a certain word in a corpus can there be for a natural language processing problem. Is there any study or site that has such estimation?

# Answer
> 1 votes
What you're asking directly refers to Information Retrieval. Information Retrieval directly creates models for such things as frequency of words in a corpus and so on.

In a corpus, different indicators are estimated in order to create a score. Two indicators are predominant in those models :

* **Inverse document frequency (idf)**

This model aims at attenuating words that appear too often and considered irrelevant to judge the score of a word.

$ idf\_{t} = log\frac{N}{df\_{t}}$ where $N$ stands for the total of document in a collection and $df\_{t}$ the number of documents in a collector that contain the term $t$

* **Term frequency (tf)**

This is the most basic way to modelize word frequency in a corpus. It can be computed by saying that:

$tf\_{t,d} = \frac{t\_{occ}}{N}$ where $t\_{occ}$ is the occurence of the term divided by the number of words in the document.

More information on this subject can be found here :

Scoring, term weighting and the vector space model

---
Tags: natural-language-processing
---


# Question
Title: As a wannabe computer "scientist" I have problems differentiating theory and practice
Specifically I'm studying towards a research degree in HCI (human computer interaction). I have problems however differentiating theory and practice, or science and engineering. I know science is about advancing human knowledge. Providing evidence about something specific in a field. But it's also about theory right? I guess there's different ways to do science; you can prove something with numbers and results, but you can also do science simply by creating a new method or theory about how something should work right? Engineering on the other hand is more about putting into practice the theory, right?

I'd like to have some guidance, perhaps with examples, to what differentiates theory and practice, science and engineering. Also books/articles to read on the subject would be greatly appreciated.

PS: In HCI it's hard to do research with experiments - it's very subject and not quantifiable as other fields of computer science. Perhaps this is why my confusion is greater than one would expect.

# Answer
> 4 votes
There is no universal objective answer to the question of how to tell what counts as theory and what counts as practice, or what counts as science vs engineering; the precise dividing line between theory and practice, or science and engineering, is subjective and a matter of opinion. Those terms are not precisely defined -- they are fuzzy, subjective terms. Different people use them differently.

For instance, sometimes people might use science to mean "understanding fundamental questions, identifying and testing laws of nature and hypotheses" and engineering to mean "building useful systems and solving practical problems", but even there the line is fuzzy. Other times people use the term "science" to mean "what I do" or "the kind of work I respect" or "the really challenging stuff" and "engineering" to mean "what those other researchers do" or "the kind of work that I consider trivial/uninteresting/not deep". You'll probably encounter many other variations on these kinds of meanings.

P.S. You are wrong that it's hard to do research with experiments in HCI. Indeed, every human subjects study is itself an experiment, so experiments are very commonly used in HCI. Perhaps you are thinking that it is challenging to find universal laws of nature in HCI (analogous to Newton's First Law, say, but for people), as people are complex. That is true, but it doesn't mean no such laws exist or that such research is impossible. Consider Fitt's Law, for instance.

---
Tags: software-engineering, research, hci
---


# Question
Title: Given family of grammars, determine if LR(k)
Parsing family of grammars, determine if LR(k)

I have the exact same problem, but my reputation is not enough to comment on that thread, plus the OP hasn't been online in 2 years so I can't ask him personally. So I apologize, but I do have to ask for your help!

Would it be enough to show that the formula works for n = 2, n = 3 (by drawing the automata) and deduct that it must work for any n?

As for the second question, could I follow the same strategy?

Thank you for you time.

# Answer
> 1 votes
No, of course not. If you want to prove that some formula is true for all $n$, it is in general not enough to show that it is true for $n=2$ and $n=3$. That's just wishful thinking.

Consider, for instance, the claim that $n^2+n+41$ is prime for all $n$. You can check it for $n=2$ (sure enough, $2^2+2+41=47$ is prime) and $n=3$ (yup, $3^2+3+41=53$ is prime), and it'll be true for both $n=2$ and $n=3$, but that doesn't mean it's true for all $n$. In fact, it's not true for all $n$: at $n=41$, the corresponding value is not prime (it is divisible by 41).

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


# Question
Title: Decide $\{a^nb^n\mid n>0\}$ in log space
Given $S = \\{a^n b^n \mid n \> 0\\}$, show $S$ is deterministically decidable in log space.

Hint: to count up to $n$ you need $\log n$ bits.

This comes from some lecture notes at https://www.cise.ufl.edu/research/OptimaNetSci/slides/ThangSept20.pdf

but they did not show how to prove it. Any ideas? (Was posted in wrong section before)

# Answer
> 4 votes
The hint that you have pretty much solves the problem. Essentially you need two counters; one for `a` and one for `b`.

1. If the first occurrence is not an `a`, you reject.
2. Start counting `a`s. You will encounter `n` of those, until the end of input, or you find a different character. When you stop reading `a`s, at that point you have `n` in binary. Essentially, every time you read an `a`, you simply perform addition in the counter that is used for counting `a`s.
3. If you have reached the end of input, or if the next character is not b, you reject.
4. Start counting `b`s in the same manner as you were counting `a`s until you reach the end of input or encounter a different character. You will read at most `n` `b`s, by checking every time that you read a `b` if you have read less than `n` characters. This is again straightforward because the two counters for `a` and `b` are in binary. If you read a different character you reject. If you reach the end of input after `n` `b`s, then you accept; otherwise reject (there is another character coming up - might even be a `b`).

Thus, we need O(log(n)) space.

---
Tags: complexity-theory, decision-problem, space-complexity
---


# Question
Title: Prove or disprove: L^2 context free implies L is context free
Clearly we have to disprove this. But I am finding it hard to prove it. I was trying in following way: Considering any non context free language L. I was trying to prove that L^2 is context free which will contradict given statement. But I don't know to how to prove it. Because by pumping lemma we can show only that language is not CFL but converse is not true. Can you please help me. Or is there any other way to prove it. Thanks

# Answer
> 1 votes
Ran's hint, with a bit of work, can indeed be used to show that the concatenation of an undecidable language with itself can be decidable. Here's a cute, simple, "almost-proof" of the fact that the concatenation of a non-CFL with itself can be a CFL:

1. The language $L=\\{0^p\mid p \text{ is an odd prime}\\}$ is not a CFL. This is a standard result, shown in some (but not all) theory texts.
2. *Goldbach's conjecture*: Any even number greater than 4 is the sum of two odd primes. This is unproven, but has been shown to be true for all even numbers less than $4\times 10^{18}$ and is regarded by many number theorists as likely true in general.

So, **if** Goldbach's conjecture is true, then $L^2=\\{0^{2n}\mid n\ge 3\\}$ which is clearly a CFL (being regular), even though $L$ isn't. Bada-bing.

# Answer
> 2 votes
**Hint.** Let $U\subseteq\mathbb{N}$ be any undecidable set and let $I = \\{2u+1\mid u\in U\\} \cup \\{0, 2, 4, \dots\\}$. Let $L = \\{a^i\mid i\in I\\}$. Now prove that $L^2$ is context-free but $L$ is not.

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


title: Bitwise operations on memory addresses

text:
# Question
Title: Bitwise operations on memory addresses
I have to solve a question saying

> The value of ab if ab & 0x3f equals 0x27.

Consider a, b as hex digits. Then `b&f` means `b&1111` \- the book explains that `b&1111` should yield `0111` i.e. `7` =\> a should be 7. The book says `a&0011`should yield `a = 2` but doesn't provide an explanation.

Please help me understand why `a&0011 = 2` implies `a = 2`.

# Answer
As you already noticed, you have to solve two equations, the first one is $N \\& 1111\_b = 0111\_b$ the other $M \\& 0011\_b = 0010\_b$.

To solve these equations notice that every bit in these equations acts independently of the other bits. For example let $N1,N2,N3,N4$ the bits of $N$, i.e.,

```
 N1 N2 N3 N4
+ 1  1  1  1
------------
  0  1  1  1

```

Since $N4 \\& 1 = 1$ the value of $N4$ has to be $1$. Now continue with the other bits. If you have problems inverting the and look at the truth table. Note that the inversion is not always unique: If you ask for $0 \\& X = 0$ then $X$ can be either $1$ or $0$.
> 1 votes

---
Tags: arithmetic
---


title: Prove NP Complete

text:
# Question
Title: Prove NP Complete
There are n numbers and we have to split the numbers into 2 sets such that difference of the sum of numbers of both sets is less than 100. Is this problem NP complete?

Solution: I can prove that it belongs to NP but I am not able to find a reduction from another NP complete problem to this problem. I have tried reducing Subset Partition problem to this problem but no luck.

Please suggest any alternate solutions or how to reduce from Subset Partition to this problem.

# Answer
Hint: Multiply all the numbers in the set by a factor of 100. What happens? What if you multiply them by a factor of 1000?

This should be enough to help you find the reduction you want.
> 0 votes

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


# Question
Title: Eliminating Null Productions from Context Free Grammar
Here is a problem I am trying to solve:

```
S -> 0A0 | 1B1 | BB
A -> C
B -> S | A
C -> S | e

```

I know that C is nullable (since it produces an epsilon) and A is nullable (since it produces C, which is nullable). My question is if B is nullable too since it produces A which produces C which are both nullable?

# Answer
Yes, absolutely. We have the derivation $B \to A \to C \to \epsilon$, so $B$ is nullable.
> 1 votes

---
Tags: context-free, formal-grammars
---


# Question
Title: Probability of probing $t$ locations in a Cuckoo hash is $O(\frac{1}{2^{t/2}})$ locations in the worst case
I was told this question may be better received here.

> Prove that the probability that an insertion into a cuckoo hash table probes $t$ array locations is $O(\frac{1}{2^{t/2}})$. Keep in mind that there are two tables, each with size $s \ge 2n$, where $n$ is the number of elements in the set.

I'm trying to use induction, but I don't know if this is the best method to go about proving this.

The worst case to probe $1$ array location would be when all $n$ element are stored in the first table, and we get probability $\frac{n}{2n} = \frac{1}{2} = O(\frac{1}{\sqrt{2}})$ for insertion.

The worst case to probe $2$ array locations would be when all $n$ elements are stored in the first table, we hit the first table, and we succeed in the second table. This has the same probability as it does to probe $1$ array location.

However, I don't know how to continue the analysis. For example, what's the worst case probability to probe $4$ array locations? The question statement implies that the worst case is $O(\frac{1}4)$, but how do we achieve this result? If the first and second tables each have $\frac{1}4$ of their array locations occupied, then the worst case to probe $4$ elements would be hitting in the first table, hitting in the second table, hitting in the first table again, then finally inserting into the second table $\Rightarrow \frac{1}4\cdot\frac{1}4\cdot\frac{1}{4}\cdot\frac{3}4 = \frac{3}{256} \not = \frac{1}4$.

Does anyone have a clearer way of thinking about this problem?

# Answer
Basically, you just write down everything that is necessary to have $t$ evictions and then use the universality of your hash functions to bound the probability.

Assume you want to insert $x$ and your hash functions are $f,g$. Then if you have $t$ probes if $f(x)$ is occupied that is $$ \begin{align} \mathbb{P}\[t=1\]& =\sum\_{y \neq x} \mathbb{P}\[f(x)=f(y)\]\\ &\le n \cdot 1/s \le 1/2. \end{align}$$ since your hash function are $(1,k)$-universal (I assume).

Now for $t=2$, the place of $f(x)$ have to be occupied by some element $y$ (that is $f(x)=f(y)$), and the alternative for $y$ is blocked by some other element $z$ (that is $g(y)=g(z)$). Summing up over all possible values for $y$ and $z$ gives $$ \begin{align} \mathbb{P}\[t=2\]& =\sum\_{y,z \neq x} \mathbb{P}\[f(x)=f(y) \text { and } g(y)=g(z) \]\]\\ &\le n^2 \cdot 1/s^2 \le 1/4. \end{align}$$

The summands of the sum are bounded by $1/s^2$ due to the universality of the hash functions, and you have less than $n^2$ summands.

I think from here you can continue by yourself.
> 2 votes

---
Tags: algorithms, algorithm-analysis, data-structures, hash-tables
---


# Question
Title: Why is the orthogonal line segment intersection algorithm $O(n\log n+R)$ instead of $O(n\log n + Rn)$?
In the same lecture notes without providing many details it says that the complexity of the algorithm which uses a balanced search tree is $O(n\log n+R)$ where $R$ is the total amount of intersections.

However I don't understand why this is the case.

Suppose that the sweep line is travelling from top to bottom. Whenever we encounter a vertical line segment, we pick its $x$ coordinate and add it to a search tree. Assuming that we are using a balanced search tree like AVL, this operation will take $O(\log n)$ time. Now when we reach an end point of a vertical line segment, we remove its $x$ coordinate from the search tree, which is going to take $O(\log n)$ time as well.

Whenever we encounter a horizontal line segment defined by points $A$ and $B$, we have to do a range search on our search tree and use the range defined by these two points, that is $(A.x, B.x)$

Now how is this range search going to happen? We use $A.x$ and travel to the left most point in the search tree, and do the same for $B.x$, we can do this in $O(2\log n)$.

All the points in our tree between these two end points are going to be the intersecting the horizontal segment, which is going to be let's say $R$ in total, so $O(2\log n+R)$ in total.

We do this $n$ times (the amount of horizontal segments) so we get a complexity of $O(2n\log n+nR)$.

# Answer
It's a bit hard to get through your text since a lot of information is missing. However I assume that you have the following misunderstanding.

Let me ignore the constants in the big-O for this argument since this is irrelevant. For every horizontal segment $h$ you perform an action that takes $O\log n + R\_h$ time, where $R\_h$ are the intersections you output. Then the overall running time is $$\sum\_h \log n + R\_h = n\log n +R.$$

Simply speaking, you only output every crossing once. So the overall time for the output is $O(R)$.
> 3 votes

---
Tags: algorithms, algorithm-analysis, computational-geometry, search-trees
---


# Question
Title: Partition partition with constraint of equal size
I see the problem here which is the well know partition problem but with constraint that the size of both sets must be equal.

I look at the answer and I don't understand that why Colin said add max(S)⋅length(S), and run the algorithm as normal would make the size of both sets equal. I think for long time.

And i think that his claim for send s∈S to 1+s⋅length(S) is wrong?

Example:

Initial set: 1 2 3 9

1+s⋅length(S)= 1+s(4)=5 9 13 37

After running the traditional Boolean algorithm, what I got is one set of 5 9 13, another set of 37?

Can anyone explain to me? Especially the max(S)⋅length(S) one.

# Answer
The idea of Colin's algorithm is to try to force a multiset that has partitions where the cardinality of the subset is different, to have only partitions where the resulting subsets have the same size. So that the problem can only be solved if we can divide the multiset into two subsets with the same cardinality

For instance, think in the multiset

{1,1,1,2,2,3}.

This set has more than one way of partitioning it:

We can partition it into {3,1,1} and {2,2,1}

Or we can partition it into {1,1,1,2} and {3,2}

In the variant they talk about, only the first way to partition this multiset is valid.

So, what he does is adding to each number the following quantity:

Number + (number with highest value * cardinality of the set we want to divide)

In our example this results in:

{19,19,19,20,20,21}

And we can only partition this multiset of numbers only if we can partition it into two subsets with the same cardinality, in this case:

{19,20,20} and {19,19,21}

Why does it work?

It works because you add to each number the same quantity, so in a partition where the two subsets have the same cardinality, we add the number the same number of times to each subset, in a partition with subsets of different cardinality, we add the number to each subset a number of times that is not equal, so the subsets can't have the same sum.

For instance

We keep with the previous example

1 + 18 + 2 + 18 + 2 + 18

and

1 + 18 + 1 +18 + 3 +18

This partition has the same sum because we add the number eighteen three times to each subset.

But

1 + 18 + 1 +18 + 1 +18 + 2 + 18

and

3 + 18 + 2 +18

don't give the same result because we add eighteen to the first subset four times and only two to the other subset, as the two had the same sum before the transformation, by adding a number to each subset a number of times that is not equal, the two don't have the same sum anymore

Hope this is helpful
> 1 votes

---
Tags: algorithms, partition-problem, pseudo-polynomial
---


title: Minimize sum of squared error

text:
# Question
Title: Minimize sum of squared error
I have an array of real numbers, I want to partition them into k sets. In each set, I calculate the sum of squared error. Then, I add up all the sum of squared error for all the set. I want to minimize this number. For example:

1 3 5 9

if k=2, I would partition them into (1 3 5) and (9), the sum of squared error of (1 3 5) is (3-1)^2+(3-3)^2+(5-3)^2=8 and the sum of squared error of (9) is 0. So the total sum of squared error is 8. I think 8 is the minimum sum of squared error in this case.

I want to use the traditional prim's method to solve this problem. i.e. to use connect n-k edges, then stop. But the problem is whenever I add 1 more integers to the subset, the mean changes. So, it seems that I cannot use Prim's method...Anyone give me some insight on this? Thanks!

# Answer
You are looking for an optimal 1-dimensional k-means algorithm. The k-means objective function for partitioning the data $x\_1, \ldots, x\_n$ into $k$ sets $S = \\{S\_1, \ldots, S\_k\\}$.

$$ \sum\limits\_{i=1}^k \sum\limits\_{x \in S\_i}\lVert x - \mu\_i \rVert^2 $$

where $\mu\_i$ is the mean of $S\_i$ \[1\].

You can apply a dynamic programming algorithm to the problem \[2\].

1. Let the data $x\_1, \ldots, x\_n$ be sorted in non-decreasing order.
2. Fill a $(n + 1) \times (k + 1)$ array, $D$, with the minimum sum of squared errors, for the first $i$ entries, using $m$ clusters. This can be calculated as

$$ D\[i,m\] := \min\limits\_{m \le j \le i} \left\\{ D\[j-1,m-1\] + d(x\_j, \ldots, x\_i) \right\\} $$

where $d(x\_j, \ldots, x\_i)$ is the sum of squared errors from their mean. For $1 \le i \le n$ and $1 \le m \le k$, and the base cases are $d\[i,m\] = 0$ if $i=0$ or $m=0$.

Thus, the entry $D\[n,k\]$ contains the optimal sum of squared errors for the original problem, now all that is left to do is to extract the answer.

Note that $d(x\_j, \ldots, x\_i)$ can be computed iteratively to speed up the algorithm, as

$$\begin{align\*} d(x\_j, \ldots, x\_i) &= d(x\_j, \ldots, x\_{i-1}) + \frac{i-1}{i} (x\_i - \mu\_{i-1})^2 \\ \mu\_i &= \frac{x\_i + (i - 1) \mu\_{i-1}}{i}\end{align\*} $$

Thus, $D$ can be computed in $O\left(n^2k\right)$ time, since there are $nk$ entries, and each takes $O(n)$ time to compute.
3. Now, we fill a $n \times k$ array, $B$, whose entries, $B\[i,m\]$, contain the index of the smallest (first) element in the cluster that contains entry $i$, which can be calculated as

$$ B\[i,m\] := \arg\min\limits\_{m \le j \le i} \left\\{ D\[j-1,m-1\] + d(x\_j, \ldots, x\_i) \right\\} $$

for $1 \le i \le n$ and $1 \le m \le k$. This takes $O\left(n^2k\right)$ time.

Thus, we can backtrack from $B\[n,k\]$ to find the clustering. The clusters are defined recursively as

$$\begin{align\*} S\_k &= \\{B\[n,k\], \ldots, x\_n\\} \\ S\_i &= \\{B\[x\_j,k\], \ldots, x\_j \mid x\_{j+1} := \min S\_{i+1}\\} \end{align\*}$$

The backtracking takes $O(k)$ time.

The algorithm runs in $O\left(n^2k\right)$ time, and requires $O(nk)$ space.

\[1\] http://en.wikipedia.org/wiki/K-means\_clustering

\[2\] http://journal.r-project.org/archive/2011-2/RJournal\_2011-2\_Wang+Song.pdf
> 3 votes

---
Tags: algorithms, optimization, sets, partitions, real-numbers
---


# Question
Title: Show that the following family of hash functions is $2$-wise independent but not $3$-wise independent
I've really been thinking about and working on this problem for a while, and I would appreciate if someone could offer any help towards the solution.

> Consider the following family of hash functions that map $w$-bit numbers to $l$-bit numbers (i.e. the range is $\\{0,...,m-1\\}$ where $m=2^l$):
>
> $\mathcal{H} = \\{h\_{A,b}|A\in \\{0,1\\}^{l\times w}, b \in \\{0,1\\}^{l\times 1}\\}$, where $h\_{A,b}(x) = Ax+b\mod 2$
>
> Show that $\mathcal{H}$ is $2$-wise independent but not $3$-wise independent ($\mathcal{H}$ is $k$-wise independent if for any $k$ inputs $x\_1,...,x\_k$ and hash values $v\_1,...,v\_k$, $\Pr\limits\_{h\in\mathcal{H}} \left( \bigwedge\limits\_{1\le i\le k} h(x\_i)=v\_i \right)=m^{-k} $).

I'm first trying to show that $\mathcal{H}$ is $2$-wise independent. So consider any two inputs $x\_1, x\_2$ and hash values $v\_1,v\_2$. Then it's required that $\Pr \left( h(x\_1)=v\_1 \wedge h(x\_2)=v\_2 \right)=\frac{1}{m^2}$.

$$\Pr \left( h(x\_1)=v\_1 \wedge h(x\_2)=v\_2\right)$$

$$\Rightarrow \Pr\left( Ax\_1+b = v\_1 \mod 2\wedge Ax\_2+b=v\_2 \mod 2\right)$$

What about this equation shows that the probability is $\frac{1}{m^2}$? If we were trying to show $3$-wise independence, we would have:

$$\Pr\left( Ax\_1+b = v\_1 \mod 2 \wedge Ax\_2+b=v\_2 \mod 2 \wedge Ax\_3+b=v\_3 \mod 2\right)$$

Why is this *not* $\frac{1}{m^3}$?

I just don't know how to evaluate an expression like $\Pr\left( Ax\_1+b = v\_1 \mod 2 \wedge Ax\_2+b=v\_2 \mod 2 \wedge Ax\_3+b=v\_3 \mod 2\right)$. I've tried searching online for similar problems, but none seem to help with solving this one specifically.

# Answer
**Hint for showing 2-wise independence:** Given $x\_1,x\_2$ and $v\_1,v\_2$, write the desired equations in a different way: $$ b = v\_1 - Ax\_1, \\ A(x\_2-x\_1) = v\_2 - v\_1. $$

**Regarding 3-wise independence:** I could be missing something, but it seems that the family *is* 3-wise independent.

**Hint for refuting 4-wise independence:** Take $x\_3 = x\_1 + x\_2$ and $x\_4 = 0$.
> 1 votes

---
Tags: data-structures, probability-theory, hash, hash-tables
---


# Question
Title: Find a subgraph whose edge weights sum to at least the number of nodes
> Given a graph G = (V,E) every edge is assigned a real number Xe $\in$ \[0,1\]
>
> The sum of x variables for all edges is equal to the number of edges -1 : $\sum x\_V = |V|-1$
>
> For a subset S $\subset$ V let us denote by $E\_{(S)}$ the set of all edges with both endpoints in the subset S.
>
> Give a polynomial time algorithm that takes as an input graph G and numbers $X\_e$ for e $\in$ E, and either finds a subset S such that
>
> $\sum\_{e \in E(s)} X\_e \> |S|-1 $
>
> or says that no such set S exists.

Analysis of its correctness and its running time.

Any suggestion please ?

---------------------------- IDEAS

1. ### min-cut project selection
2. ### min-cut baseball elimination
3. ### dynamic programming

I was trying to build a list of dictionaries, storing for each node, the sum of the edges of every subgraph in which it is.

work in progress..

# Answer
Your problem is very similar to the classical *densest subgraph* problem, in which you want to maximize the ratio $|E(S)|/|S|$. Goldberg gave a polynomial time algorithm for this problem based on network flow. Perhaps you can use his ideas to solve your specific problem as well.
> 1 votes

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


# Question
Title: NFA - string acceptance (decision problem) test
I am interested in testing for a given string (w) whether it is in the language (L) defined by a nondeterministic finite automaton (A). I have some blurry point in my mind.

What is the complexity of this test by using the NFA and backtracking? Assume my NFA has m states and string (w) has length n (|w| = n). For regular expressions, by using Thompson's algorithm, the resultant NFA has the same complexity (worst case) if I use backtracking?

What are the methods/algorithms other than backtracking and converting to DFA?

# Answer
> 3 votes
A naïve backtracking algorithm will still result in exponential behaviour ($O(2^{n})$ where $n$ is the length of the input string). This behaviour can occur even with very small automata (i.e. where the number of states $m$ is a fixed constant).

Consider for example the NFA $M$ below:

The alphabet is simply $\Sigma =\\{0\\}$, and the language is $L(M) = \\{0^{k}\mid k \in \mathbb{N}\\} = \Sigma^{\ast}$. If our algorithm chooses poorly for even the first step (for example if we use the obvious choice and go by state ID), then we're stuck between $q\_{0}$ and $q\_{1}$, where at each point in the input, we have the choice of moving to the opposite state, or staying where we are - i.e. a binary choice for each character, for the entire length of the string, giving $2^{n}$ steps before we manage to backtrack to $q\_{2}$ and then move along the correct path to $q\_{4}$.

So even with only 4 states and where every string is valid, we can still get terrible performance from a backtracking approach.

There is a much better approach however. Even without converting the NFA to a DFA we can decide acceptance in polynomial time. As we are dealing with a regular language, we don't need to remember the entire computation history up to this point (which is what backtracking does), we only need to know what state we are up to at the current point. In a DFA this is very easy, as we can only be in one state at any point, but an NFA (without knowing the final computation path) allows more possibilities. However we can simply keep track of these possibilities. The algorithm is as follows:

1. Initialise $S\_{0}$ to $\\{s\_{0}\\}$ where $s\_{0}$ is the start state.
2. For each symbol of the input $c\_{i}$ with $1 \leq i \leq n$, for each state $s \in S\_{i-1}$, let $E(s,c\_{i})$ be the set of states reachable from $s$ using $c\_{i}$ and any number of $\varepsilon$-moves1. Set $C\_{i} = C\_{i} \cup E(s,c\_{i})$.
3. If there is an accepting state in the set $C\_{n}$, return $\mathrm{YES}$, otherwise return $\mathrm{NO}$.

So all the algorithm is really doing is keeping track of all the states we could be up to after having read $k$ symbols from the input.

Assuming that the NFA is fixed, this algorithm is $O(n)$-time in the length of the input string. If the NFA is part of the input, it's a little more complicated, but still polynomial time - $O(m^{2}n)$ where $m$ is the number of states (if I haven't missed an implicit loop in there).

**Footnotes.**

1. That is, we take the $\varepsilon$-closure of the state $s$, then from each of these states see if we can move using symbol $c\_{i}$, then for those where we can, we take the $\varepsilon$-closure again, and this gives us $E(s,c\_{i})$.

---
Tags: automata, nondeterminism
---


# Question
Title: Are there minimum criteria for a programming language being Turing complete?
Does there exist a set of programming language constructs in a programming language in order for it to be considered Turing Complete?

From what I can tell from wikipedia, the language needs to support recursion, or, seemingly, must be able to run without halting. Is this all there is to it?

# Answer
> 56 votes
I always though that $\mu$-recursive functions nailed it. Here is what defines the whole set of computable functions; it is the smallest set of functions containing resp. closed against:

1. The constant $0$ function
2. The successor function
3. Selecting parameters
4. Function composition
5. Primitive Recursion
6. The $\mu$-operator (look for the smallest $x$ such that...)

Check above link for details; you see that it makes for a very compact programming language. It is also horrible to program in -- no free lunch. If you drop any of those, you will lose full power, so it is a minimal set of axioms.

You can translate those quite literally into basic syntactical elements for *WHILE programs*, namely

1. The constant `0`
2. Incrementation `_ + 1`
3. Variable access `x`
4. Program/statement concatenation `_; _`
5. Countdown loops `for ( x to 0 ) do _ end`
6. While loops `while ( x != 0 ) do _ end`

# Answer
> 28 votes
> Does there exist a set of computations that need to be performable in a programming language in order for it to be considered Turing Complete?

Yes, in order to be considered Turing complete a programming language needs to be able to perform any computation that can be performed by a Turing machine. So as a minimum requirement one might say, you need to be able to implement an universal Turing machine - or an interpreter for any other Turing complete language - in it.

> From what I can tell from wikipedia, the language needs to support recursion, or, seemingly, must be able to run without halting. Is this all there is to it?

No. For example a language where the only allowed operation is recursion (i.e. the only possible function you can write is `f(x) = f(x)`), is not Turing complete because all you can write in it are programs that never terminate. As I said earlier, a Turing complete language needs to be able to implement any computation that can be performed by a Turing machine. So clearly that does not suffice.

Also a language doesn't have to support recursion in the way you're thinking of. Just an unrestricted way of expressing loops. That might be recursion, but it might also be a while-loop or goto. A language that doesn't have functions at all can still be Turing complete. And again loops or recursive functions aren't a sufficient condition. You still need a way to execute different code depending on a condition and a way to calculate new values from old ones (otherwise all loops/recursion would either be infinite or not run at all).

---

As for whether there's a minimal set of of necessary and sufficient operations, such that any language that supports these operations is Turing complete and any language that doesn't is not: No, there isn't (unless you define "operation" so vaguely, that it becomes meaningless):

For example as I already said, there are Turing complete languages that don't support recursive functions (or any functions at all). Those can still be Turing complete if they have a `goto` statement or `while` loop (and a way to store arbitrary amounts of data). However a language with recursive functions needs neither `while` nor `goto` to be Turing complete. So `goto` would not be in the set of necessary sufficient operations, but there are languages that are no longer Turing complete if you remove `goto`. Thus there is no such set.

# Answer
> 19 votes
There are various single instructions that lead to Turing complete languages. The typical example is "subtract and branch if zero". These are well known in the context of assembly language programming. See the Wikipedia article for details.

This leads to a characterization: a language is Turing complete if and only if it is able to simulate the operations of fetching and storing integers in memory and performing the "subtract and branch if zero" operation on them.

# Answer
> 18 votes
This isn't a general answer to your question, but by the structured programming theorem, all that is needed is the ability to do selection (e.g., `if` in C/C++) and repetition (e.g., `while` in C/C++). *Edit: as pointed out by Dave Clarke in the comments, the structured programming theorem also requires sequence. I didn't initially list this since I took for granted the reader would understand that basic blocks of other instructions, such as those alluded to later for reading from and writing to the memory store, etc., were also necessary). It is, of course, better to be explicit; you need to be able to do these things, too.*

Since both of these can be implemented using a conditional jump instruction (e.g., `JNZ` in x86), that is also sufficient for Turing-equivalence.

Note that other things are required, i.e., the ability to write an unbounded number of symbols (e.g., bits... 0 or 1) to some sort of external memory store. In that sense, real computers are not Turing equivalent, since none of them have an infinite amount of storage. The Turing model is still useful, though, since the amount of memory is typically huge, and even though any problem a real computer can solve can be solved by a deterministic finite automaton, using that model of computation isn't particularly useful (since the number of states would be preposterously huge).

Note that this isn't necessarily at odds with sepp2k's answer; this is sort of just a different way to think about the same question.

EDIT:

Note also that you don't really need both `if` and `while` in C/C++. You can simulate `if` using `while` as follows:

```
bool C;
// some code that sets C
if(C) { /* some other code /* }
// rest of the program

```

The following code is always equivalent:

```
bool C;
// some code that sets C
bool C2 = C;
while(C2) { /* some other code /* C2 = false; }
// rest of the program

```

Well... the construction should work and be possible if you're careful, that is. Note also that if you have recursive functions, you eventually need selection also; since recursive functions without selection can't really implement base cases, so any recursive function would result in infinite recursion.

EDIT:

Also, regarding your question as to whether the ability to write a program that doesn't halt is sufficient for Turing equivalence, the answer is no; it is necessary, but not sufficient. We can solve the halting problem for programs written in a language which cannot express programs that fail to halt; the answer is "the program does halt" for all instances. However, we can define a language where the only instruction causes the machine to enter an infinite loop... such a language isn't Turing-equivalent.

# Answer
> 17 votes
The combinators $\mathbf{S}$ and $\mathbf{K}$ where, $(\mathbf{S}\ x\ y\ z) = (x\ z\ (y\ z))$ and $(\mathbf{K}\ x\ y) = x$ are sufficient to express any (closed) lambda term, therefore any computable function. See this wikipedia page for details.

In fact, the lambda term $\mathbf{X}=\lambda x.((x\ \mathbf{S})\ \mathbf{K})$ is a sufficient basis to express all lambda terms. See later in the same wikipedia page.

# Answer
> 7 votes
## The language constructs are interchangeable

There is no set minimum criteria about what constructs must ***natively*** be provided by a programming language. If it provides some weird constructs that can somehow be convoluted to express a Turing-complete system, then apparently those constructs are "just as suitable" as any others.

To prove this - a language that provides *only* a "subtract and branch if zero" operation is Turing complete; there exist Turing complete languages that don't provide a separate "substract and branch if zero" construct, ergo there is no construct or a set of constructs that is mandatory.

The effects of any TP-complete language construct can be emulated by the constructs of any other TP-complete language.

---
Tags: computability, programming-languages, turing-machines, turing-completeness
---


# Question
Title: The communication complexity of non-equality
I'm familiar with the fooling set technique to obtain lower bounds for communication complexity protocols. The most basic example is the equality function for which the diagonal matrix gives the fooling set of size $2^n$, because each 1-output needs to be in its own monochromatic rectangle. Also, a similar property seems to be true when looking at 0-outputs: If we have a cover of the 0-outputs by a set of monochromatic rectangles, then no rectangle can contain **all** 0-outputs of 2 (or more) rows. This implies that we get the same complexity for the NEQ (non-equality) problem.

However, I read that for non-deterministic algorithms, the complexity of NEQ is only $O(\log n)$. This is because we simply need to "guess" an index $i$ where the inputs of Alice and Bob differ, which takes $\log n$ bits and then use $1$ additional bit to encode if $i=0$ or $i=1$.

But the complexity of such a non-deterministic algorithms is lower-bounded by the log of the size of the smallest cover of the $0$-outputs, which would still be $\log(2^n)=n$ (by the above argument that each row in the matrix accounts for at least one rectangle in the cover).

Obviously, I'm missing something here, but I haven't figured out what it is...

# Answer
The protocol gives you a covering of the zeroes using $2n$ rectangles $R\_{i,b} = X\_{i,b} \times Y\_{i,1-b}$, where $X\_{i,b}$ (or $Y\_{i,b}$) is the set of words whose $i$th bit equals $b$.
> 2 votes

---
Tags: algorithms, nondeterminism, communication-complexity
---


title: Why is Steiner Tree trivially in NP?

text:
# Question
Title: Why is Steiner Tree trivially in NP?
I'm learning about NP-completeness, and many reduction proofs start off by stating that a problem is triviallyin NP. But I can't seem to wrap my head around this.

Why is this so?

# Answer
What is normally meant in cases like this is

> there is a simple, obvious algorithm which demonstrates that the problem is in $\mathcal{NP}$,

with an implicit

> but we don't have enough space, can't be bothered, or don't want to bore the reader by including it.

Whether it really is trivial is a trickier thing (but often it really is).

Before returning to the Steiner Tree problem, recall the two common definitions of $\mathcal{NP}$ membership:

1. A problem is in $\mathcal{NP}$ if, given the input and a solution, we can check that the solution is correct in deterministic polynomial time, or
2. given the input, we can compute the solution in *non*-deterministic polynomial time.

So for the Steiner Tree problem (remember we only concern ourselves with the decision versions), they are saying that at least one of the following is true:

1. Given a graph, a set of required points, a value $k$ and a tree (the alleged solution), we can easily check that the tree is a Steiner tree of value at most $k$, or
2. Given a graph, a set of required points and a value $k$, we can easily compute a Steiner tree of value at most $k$ *if we can make some really good guesses*.

Hopefully in this case both of these should be more obviously true. In the first case, we need only check that the tree1 contains the required points, and the total weight of the tree is at most $k$. In the second, we can use the magic of non-determinism to guess which edges are in the tree, then check that it's okay as in the first case.

The only further requirement is that these procedures be computable in polynomial time, but in both cases we at most need to look at each edge of the graph and each vertex of the graph once(-ish) (if we have sensible data structures to store the graph and tree), so even without being too precise, we can see that they can both be done in polynomial time.

**Footnotes.**

1. As A. Schulz notes in the comments, there is an additional issue of ensuring that the witness (the solution handed to us) has an encoded length bounded by a polynomial in the size of the original input. This may be easy to see, but as A. Schulz also notes, if we're talking about the Geometric Steiner Tree problem, then we might have to make an additional argument about how we encode the geometry of the tree - not necessarily too complicated, but still important. If we're talking about the Steiner Tree Problem in Graphs, then it's more straightforward (as we don't have to worry about the geometry), and perhaps something you can gloss over. Nonetheless it is important to be careful :).
> 9 votes

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


# Question
Title: Comparing random access and sequential access
Assume that we choose randomly $k$ distinct numbers $N\_1$, $\dots$, $N\_k$ in $\\{1, \dots, k\\}$ and we have a file of $k$ parts. We have these two cases :

1. We read (or write) sequentially from part $1$ to part $k$.
2. We read (or write) the part indexed $N\_1$, then the part indexed $N\_2$, ..., and the part indexed $N\_k$.

Have these two cases the same complexity in the RAM model?

In which model these two cases don't have the same complexity?

# Answer
> 3 votes
The answer critically depends on the model in use, specifically whether or not the memory is cached, and how the cache is being used. In the following I'll explore the two main architectures: with and without a cache.

Throughout, we assume the file consists of $k$ parts: $f\_1, \ldots, f\_k$ where $f\_i$ is 4 bytes (32bits).

## A. The simple case: a single-layered RAM.

In this case, we assume that we have a large memory $M$, where each address contains 32 bits of data. Accessing an address in the memory takes $t\_M$ time, and fetches the 32bits stored in that address.

We can assume that the file is stored sequentially in the memory, (although it doesn't matter), that is, $M\[i\]=f\_i$ for $i\le k$ and $M\[i\]=0$ otherwise.

In this case, accessing the file in any order will take the same time, namely $k \cdot t\_M$.

**bottom line:** RAM allows random-access with the same access time as sequential access. (this is why it is called a Random-Access Memory, RAM).

## B. A more realistic case: a cached memory

In the more interesting case, the memory is layered. There is a small *fast* cache we denote $C$ that contains small amount of addresses, say 1024. Each address contains 32bits of data.

When accessing an address $i$ in the memory, the process is the following:

* if $M\[i\]$ exists in the cache, say $C\[j\]=M\[i\]$, then the access time is $t\_c$. (this is called a *cache hit*)
* Otherwise, the slow memory is being accessed, and the data is fetched in time $t\_C+t\_M$. Additionally, $M\[i\]$ is now stored in the cache as well. (this is called a *cache miss*)

It is assumed that $t\_C \ll t\_M$. In case of a miss, if the cache is already full, we assume that the new value brought to the cache replaces the oldest item in the cache (the one that was last accessed the earliest)

### B.1 A Single Access

Assume that at the beginning the cache is empty.

If the file is being accessed only a single time, then, each address we access is a miss, and it will take us $k(t\_C+t\_M)$ to access the entire file, regardless of the order.

### B.2 Multiple Access

Now, assume we need to access the file **twice**. At the first time the cache is empty and so it will take us $k(t\_C+t\_M)$ to fetch the file, as above.

On the second time, things are a bit different.

If $k\<1024$, then in the next access, the entire file is in the cache, and it will take us $k t\_C$ time to access it again, regardless of the access order.

If $k\>1024$ (say $k = 2048$), then in the second access the times slightly change:

* if we access the file sequentially, then we will always have a miss, since the cache will hold the 1024 parts we have most recently accessed, and will never hold the next one that we need. The time is $k(t\_C+t\_M)$,
* if we access it in a random order (that is **independent** of the order in the first time we accessed the file), then the first part will be there with probability $1/2= 1024/2048$, the second with probability $1023/2047$ and so on (the last 1024 parts will always cause a miss). This gives a slightly better access time.

### B.3 Blocked cache

Realistic caches don't work byte-by-byte, but rather they work in blocks.

Let's say the block size is 256 words (that is, the 1024-cells cache holds 4 blocks of 256$\times$32bits each). Now, when you access an address $i$ in the memory, the following process happens:

* if $M\[i\]$ exists in the cache, then the access time is $t\_c$.
* Otherwise, the slow memory is being accessed, and the **entire block** that contains $M\[i\]$ is brought into the cache. This takes time $t\_C + 256t\_M$. We assume we always work in aligned blocks of 256 words: so if you access any address between 0 and 255, the same block $M\[0\],\ldots, M\[255\]$ is fetched into the cache.

Now, if you access the file in sequential order, once you access $M\[0\]$ you get a miss, and the first block gets into the cache. This takes time $t\_C + 256t\_M$. The next 255 access will be a hit. The total time will be about $k(t\_C + t\_M)$.

However, if you access the file randomly, every part has a probability of about $1024/k$ to already be in the cache (this is not exactly correct, but close enough). Thus the time will be (approximately) $k \cdot (1024/k \cdot t\_c + (1-1024/k)(t\_C + 256t\_M))$. This may be substantially worse than in the sequential case.

**bottom line:** if the cache is blocked, you get advantage accessing sequentially. Otherwise, it shouldn't matter that much.

## C. The (even more) realistic case

Finally, I must add that there are more parameters that affect the analysis. First, usually the memory has several cache layers, e.g., L1--L3 cache, and a main memory. Each level has more memory but is slower than the layer beneath it.

In order to give a precise analysis, a full description of the memory and the access pattern should be given, since many parameters might have a dramatic effect on the total access time.

---
Tags: algorithm-analysis, computation-models, randomness, memory-access
---


# Question
Title: Efficiently enumerate all subsets of an ordered set
What's the most efficient way to enumerate all (ordered) subsets of an ordered set? So, for example, given the ordered set $\\{2, 5, 6\\}$ (using the normal ordering for integers), I need the following: $$\\{\\}, \\{2\\}, \\{5\\}, \\{6\\}, \\{2, 5\\}, \\{2, 6\\}, \\{5, 6\\}, \\{2, 5, 6\\}.$$ Smaller subsets should come first, but the ordering of the subsets of equal size is not important.

I'm looking for an algorithm that is efficient both in theory and in implementation (in a general purpose programming language) for very large sets.

# Answer
> 6 votes
One possibility is to generate separately all subsets of size $k$ using the following recursive approach:

> A $k$-subset of $a\_1,\ldots,a\_n$ is either a $k$-subset of $a\_2,\ldots,a\_n$ or $a\_1$ adjoined to a $(k-1)$-subset of $a\_2,\ldots,a\_n$.

Run this recursive algorithm for $k=0,\ldots,n$. If you're careful, you will get a lexicographically ordered output.

# Answer
> 2 votes
If you're interested in subsets of increasing size, then go for k = 1..n, enumerate all subsets of size k. This is a well-known problem with many possible solutions, one of which is described in wikipedia http://en.wikipedia.org/wiki/Combinatorial\_number\_system (see "Applications").

---
Tags: combinatorics
---


title: Applications of model counting

text:
# Question
Title: Applications of model counting
I have been reading about model counting, a.k.a. the #SAT problem. What are the practical applications, if any, of this problem, and how exactly do they reduce to it? I have been unable to find any, though that's simply due to my own ignorance of the subject.

# Answer
A recurring application for SAT model counting in the literature is extracting predictions from Bayesian networks. See "Algorithms and Complexity Results for #SAT and Bayesian Inference" and "On probabilistic inference by weighted model counting".
> 4 votes

---
Tags: complexity-theory, applied-theory, counting
---


# Question
Title: Output of well-known algorithms for the Subset sum problem
According to Wikipedia:

> In computer science, the subset sum problem is an important problem in complexity theory and cryptography. The problem is this: given a set (or multiset) of integers, is there a non-empty subset whose sum is zero? For example, given the set {−7, −3, −2, 5, 8}, **the answer is yes because the subset {−3, −2, 5} sums to zero**. The problem is NP-complete.

What is the **output** of the known algorithms which resolve **exactly** the subset sum problem?

For example:

* The algorithm which take $O(2^N\*N)$ time.
* The algorithme which take $O(2^{N/2})$ time.

Is it just **Yes / No** or do they also give **the extraction of solution**?

Example:

$A = \\{1, 3, 4, 5\\}$

$k = 8$ (The search item)

* Output : YES
* Output : {1,3,4}, {5,3} (where 1+3+4=8 and 5+3=8)

# Answer
The question "is there a subset that sums up to $t$?" has a YES/NO answer. In general, we shouldn't expect an algorithm to do more than it is asked to, so to speak. However, it is rather common that when an algorithm answers YES, it can also naturally give you a certificate that proves it. Moreover, when this happens, you typically get a *one* valid solution. (This was just a clarification because your example outputs 2 valid solutions. Listing *all* solutions is a different thing).

Both algorithms you mention explicitly step through certain subsets, and so it is easy for them to also output the subset whose elements sum up to $t$. Whether you care about that extra information is up to you then.
> 3 votes

---
Tags: algorithms, knapsack-problems
---


# Question
Title: find the shortest path between two nodes where the number of edges is minimal
Say you are given an undirected unweighted graph, where s and t are nodes from the graph. d(s,t) means the distance between s and t which outputs the number of edges.

How do I find the the maximum distance between s and t , max{d(s,t)}, where the edges between s and t are minimal? Also, how can this problem can be related/reduced to the hamiltonian problem?

Any advice would be really helpful.

# Answer
> 0 votes
Hint: Given a graph $G$, add two new vertices $s,t$, each connected to all vertices in the original graph. When does there exist a path from $s$ to $t$ of length $n+1$?

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


# Question
Title: How to represent whitespace in a context-free grammar?
Say we want to support: xx

The following grammar does accept it:

* S -\> xAx
* A -\> ε.

because S =\> xAx =\> xx.

But what about supporting: x x

I realize this might be a stupid question but I'm really unable to find a definite answer. Especially as

* S -\> xAx
* S -\> x A x

appear to be equivalent representations in most references.

# Answer
> 7 votes
This is a classical confusion between language and metalanguage.

More generally, you have the same problem when you want to include in your symbols, expecially terminal symbols, characters that have syntactic meaning in the syntax of grammars, for example the symbol `"|"` which is often used to give on the same line all possible right-hand-sides for a given non-terminal.

In such a case, you do what I just did: use some mechanism for quotation, such as `"|"`, or `" "` in the case of a space. Some form of quoting is the usual technique to avoid confusion between language and metalanguage. And as you remarked, the language of grammars already uses the space for its own (lack of) purposes.

So you write:

```
S -> xAx
A -> " "

```

Of course, the spaces outside the quotes still play the same role as before, wherever allowed. So the grammar could be written as well:

```
S ->  x A  x
A  ->   " "

```

Whatever is within quote must be written exactly as expected.

However, in many contexts (such as programming language syntax), it is implicit that you can add spaces wherever you want between terminal. So you have to be clear whather you just want one compulsory space where you have the terminal `" "`, or whether you forbid spaces, unless specified by the syntax as done here.

The quotation marks are metasyntax, i.e. part of the language used to write the grammar, like the arrow. The analyser (whether LR(1) or any other) will ignore the quotes, as it ignores the arrow `->`. It would work as well with a grammar written as `[(S,xAx)(A," ")]`. Some metalanguages for writing grammars, such as BNF, simplify the issue by making the quotes compulsory around terminals ... though there is still a problem when terminals include the quoting symbols ... but this has solutions.

Another question you may want to look at is: What are the meanings of metalanguage and metasyntax and EBNF?

# Answer
> 4 votes
If I'm not wrong, you just want to include a whitespace in your grammar. In that case, a whitespace is just another character which should be included in your alphabet of the language. Say, denoting whitespace with $$\beth$$ you just include a rule like $$A \to \beth$$ in your grammar.

This will lead to the following derivation: $$S \to xAx \to x\beth x$$ where the beth symbol is nothing but a whitespace. So the string 'x x' is in the language defined by the given grammar.

# Answer
> 2 votes
A space is just another symbol of the alphabet. You can make up a notation for it such as " " to make it easier to spot.

That said, in the context of programming languages, there is no need to describe whitespace as part of the grammar; whitespace is used during lexical analysis to separate the various lexemes, and is otherwise ignored. For example, a C lexer would translate the strings `a+b` and `a + b` to the same sequence of lexemes, which can be something like ID PLUS ID; each ID also comes with an *attribute* giving its name.

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


# Question
Title: How to apply "verification" and "decision" for the SUBSET SUM problem?
The SUBSET SUM problem states that:

```
Given finite set S of integers, is there a subset whose sum is exactly t?

```

Can someone show me why verification is simpler than decision for this problem?

# Answer
> 3 votes
If anybody could show you that verification is simpler than decision, then she would be famous, having solved the P vs. NP problem.

For SUBSET-SUM, *verification* means that given a set $S$ which has a subset summing to $t$, someone can convince you easily that this is the case. The way she would do it is by giving you a subset of $S$ summing to $t$.

In contrast, *decision* means given a set $S$ and a target $t$, decide whether there is a subset of $S$ that sums to $t$. Nobody knows how to do it efficiently, and we conjecture that there is in fact no way to do it efficiently.

A related problem is *co-verification*: given a set $S$ which has *no* subset summing to $t$, we want someone to convince us easily that this is the case. Nobody has any idea how such a convincing argument would look like, and we conjecture that there such convincing arguments don't in fact exist (in general). This is the NP vs. coNP problem.

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


# Question
Title: What is the implication of the sentence: "if any NP complete problem is p time solvable, then all problems in NP are p time solvable"
I find this quote here on page 13

> Does it mean that out of all different problems that are NP complete, if any problem is found to have a p time solution, then all the NP complete problems are p time solvable?

This is very unbelievable to me since NP complete problems are so different in nature and comes in a variety of form such as longest path, dominating vertex, halting problem, knapsack problem. Can someone show me how this statement is true?

# Answer
This statement means exactly what you have said: if *any* NP-complete problem is solvable in polynomial time, then *all* of them are. This follows from the definitions: a problem X is NP-complete if all problems in NP are polynomial time reducible to it, that is, if for any problem Y in NP there is a polynomial time function $f\_Y$ such that for all $w$, $w \in Y$ iff $f\_Y(w) \in X$. Now suppose that you could solve X in polynomial time using some algorithm A. For any NP problem Y, you can use $f\_Y$ in conjunction with A to solve Y in polynomial time.

This is indeed surprising, and it is one reason why most researchers conjecture that NP is different from P: otherwise all these disparate problems will have polynomial time solutions.
> 3 votes

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


# Question
Title: How does "language" relate to "problem" in complexity theory?
I am looking up the meaning of reduction in complexity theory:

On Wikipedia it says: reduction is an algorithm for transforming one problem into another problem

On the Princeton's notes on NP-Completeness, it says: reduction is whereby given all x $\in $ language L1, for instance f(x) $\in$ L2, apply decision algorithm to f(x), then L1 $\<=$ L2

Can someone make clear how a language (which is just a bunch of numbers) relates to a problem? If they are used interchangeably, can someone show how does I can conceptualize a language as a problem?

Thanks

# Answer
> 1 votes
A *(decision) problem* is a predicate on strings (that is, a property of strings) that can be either TRUE or FALSE; the problem is to decide whether a string satisfies the predicate (that is, has the property). We represent this predicate as the set of TRUE strings (that is, strings satisfying the property). A *language* is a set of strings. Thus the *denotations* of *problem* and *language* are the same – they are both sets of strings – and they can be used interchangeably. But semantically we use *problem* when our set of strings comes from a predicate, and *language* in other cases.

Here is an example. The NP-complete problem CLIQUE is the set of all pairs $(G,k)$ such that $G$ is a graph that has a $k$-clique. As stated, this is not really a set of strings, but rather a set of pairs $(G,k)$. But when we say the set of all pairs $(G,k)$ we really have some encoding in mind. For example, we can encode a graph $G$ as a list of edges, where the vertices are indexed by numbers, in the format $((i\_1,j\_1),\ldots,(i\_\ell,j\_\ell))$. For example, the following is an encoding of a triangle $((1,2),(1,3),(2,3))$. Under this encoding, the language CLIQUE contains the string $(((1,2),(1,3),(2,3)),3)$ but not the string $(((1,2),(1,3),(2,3)),4)$ nor the string $()()($, for example. Another issue that comes up when we talk about strings is: strings over *what* alphabet. In this case, our strings are over the alphabet $(),0123456789$; but since everything can be encoded in binary, we typically imagine such binary encoding of our strings.

CLIQUE is a predicate on pairs $(G,k)$ that holds if $G$ is a graph containing a $k$-clique. It is also a property of pairs $(G,k)$, that of $G$ having a $k$-clique. The corresponding language (which we identify with the CLIQUE problem) consists of all strings encoding (in a fixed way) pairs of graphs $(G,k)$ such that $G$ has a $k$-clique. The corresponding decision problem (which we identify with the language of all accepted instances) is to decide, given a pair $(G,k)$, whether $G$ contains a $k$-clique.

---
Tags: complexity-theory
---


# Question
Title: Is this time complexity quasi-polynomial?
I have been working in the time analysis for an algorithm and finally I got a curve that fits:

$O(2^{(\log\_2(N)^{2.01})})$

N is the number of elements.

I'm right to say the above time complexity is quasi-polynomial?

# Answer
Quasi-polynomial means different things to different people, but in many contexts it means a running time of the form $O(2^{O(\log^{O(1)} N)})$, to which your example conforms.
> 2 votes

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


# Question
Title: Number of integers in a certain range with certain properties
How would one (quickly) find the number of integers in the range \[1, x\] for some x, more than half of its digits being one digit, given that $x$ has at most, say, 19 digits.

Brute force would obviously not work in a reasonable amount of time (where "reasonable" means roughly $10^9$ seconds)

# Answer
Hint: Decompose the range $\[1,x\]$ into more manageable ranges of the form $\[N\cdot 10^{k+1},N\cdot 10^{k+1} + d \cdot 10^k)$, where $d \< 10$. Enumerate over the "popular" digit, and use inclusion-exclusion.
> 1 votes

---
Tags: algorithms
---


# Question
Title: Can someone explain in a simple way what "reducible" mean in complexity theory?
I find the word "reducible" used in complexity theory not very intuitive, and too general taken on a face value.

What does it exactly mean by problem A reducible to B?

* Does it mean that A can be reworded into B? i.e. Finding Vertex Set is actually the same as finding an independent set?
* Does it mean that an algorithm that solves problem B will solve A? i.e. An algorithm that finds longest path will in fact also find the shortest path?
* Does it mean that A can be proved to be in the same complexity class as B? i.e. A is NP-Hard, B is NPC, then if A is reducible to B, A is in fact NPC?

In other words, A is reducible to B, what can we say about A or B?

As you can see my understanding is quite flaw at the moment, can someone please clarify the application of the word for me maybe even rephrase it into something more intuitive?

# Answer
> 3 votes
The most common notion of reducibility is many-one polynomial time reducibility.

A problem $A$ is *many-one polynomial time reducible* to a problem $B$ if there is a polynomial time function $f$ such that $x \in A$ iff $f(x) \in B$.

This definition implies that if $B$ is solvable in polynomial time, then so is $A$.

Other notions also exist, but at this stage you're probably better off concentrating just on this one, since it is the one used to define NP-completeness.

---
Tags: complexity-theory, terminology, reductions
---


# Question
Title: Dynamic Programming for finding shortest alternating paths between all pairs of vertices in a graph
I'm learning Dynamic Programming (By myself) and in the textbook there is this question:

> Given two undirected graphs $G\_1=(V,E\_1)$ and $G\_2=(V,E\_2)$ over the same set of Vertices $V$ and a weight function $w: E\_1 \cup E\_2 \rightarrow \mathbb{R}$, let $P = \left\\{e\_1, e\_2, ..., e\_n \right\\}$ be a path in $(V, E\_1 \cup E\_2)$.
>
> We sat that P is alternating if for any $1 \leq i \< n$ at least one of the following two conditions hold:
>
> * $e\_i \in E\_1, e\_{i+1} \in E\_2$
> * $e\_i \in E\_2, e\_{i+1} \in E\_1$
>
> Write a DP algorithm that given $G\_1, G\_2$, returns the weights of the shortest alternating paths between all pairs of vertices in $V$

OK so I sat on this question for a long time but I can't seem to figure out how to do solve it. Since this is a shortest path between all pairs I tried to think of a solution which uses Floyd-Warshall algorithm, but I can't figure out how to factor in the addition of the alternating path.

Every solution I think of fails when inserting special Edge Cases.

Can anyone give a hint as to how to proceed?

# Answer
Hint: Try to modify the Floyd–Warshall algorithm to account for edge types. As described in Wikipedia, we construct an array $A\[i,j,k\]$ which keeps the weight of the shortest path from $i$ to $j$ via the vertices $1,\ldots,k$. Instead, construct an array $A\[i,j,k,x,y\]$ which keeps the weight of the shortest path from $i$ to $j$ via the vertices $1,\ldots,k$ *whose first edge belongs to $G\_x$, and whose last edge belongs to $G\_y$*.
> 1 votes

# Answer
May be it helps you to see more easily the way to attack the problem. The first that you could try it's find or understand the recursive relation behind *Floyd-Warshall Algorithm*. As the next function $f$.

$$ f(u,v,k) = \begin{cases} w\_{u,v} & k = 0\\ \min\\, (\ f(u,v, k-1),\ f(u,k,k-1) + f(k,v,k-1)) & \text{otherwise} \end{cases} $$

* $w\_{u,v}$ it's the weight of edge from $u$ to $v$ in the direct graph $G$. $\infty$ if that edge doesn't exist.
* $f(u,v,k)$ is the weight of a shortest path from $u$ to $v$ if you consider the first $k$ vertices as intermediates.

---

To adapt the above function form for your problem, I'd sketched the essence of the problem in the next graph:

*
* $m\_i\in E\_0$
* $l\_i\in E\_1$
* The curly curve is the shortest path considering the first $k-1$ vertices.
* You have a alternate path that consider the $k$ node when you see the pattern (normal-$k$-dashed) lines in the path, or with convention above: (dashed-$k$-normal) line or $(m\_i, l\_j)^\*$ , $(l\_i, m\_j)^\*$ pattern in general.

So the next step it's construct the recursive relation looking the connection between subproblems, and for that you could think for a moment that your function solve the problem for a small size of problem, or instances pattern (follow principle of optimality).

$$ f(u,v,k,i) = \begin{cases} w\_{u,v,i} & k = 0\\ \min\\, (\ f(u,v, k-1,i),\ f(u,k,k-1,~i) + f(k,v,k-1,i)) & \text{otherwise} \end{cases} $$

* $w\_{u,v,i}$ is the weight for the edge in $E\_i$ (Note that I change enumeration of $E$ for convenience). $\infty$ if that edge doesn't exist.
* $f(u,v,k,i)$ is the weight of a shortest path that ended up with a edge in $E\_i$ that consider the first $k$ vertices as intermediates like the graph above.
* $~i = 0$ if $i = 1$ or $1$ if $i = 0$.

So, the weight of the shortest alternate path from $u$ to $v$ is $$\min \\,(\\, f(u, v, |V|, 0),\ f(u, v, |V|, 1) )$$ where $|V|$ is the number of vertices.

Of course, after some work, you could notice that:

* It's possible delete parameter $k$
* you could implement iterative version or use a memorization technique.
* Other details, that I'm forgiving. It's late.

I'd wrote a python code/ and input test file if you can play with that. But, Here, it's not important.
> 2 votes

---
Tags: algorithms, dynamic-programming, shortest-path
---


# Question
Title: Can someone provide an introductory example of a certificate in complexity theory?
Just stepping into complexity theory, I am befuddled by this notion of a certificate and can't find any utility of this concept.

From my understanding, a certificate is used when you are trying to ascertain whether a problem is NP...a problem is NP if you can verify a p-time solution exist or not (co-NP). I cannot see why you would need a certificate to perform this solution finding. And how is certificate different from "verification".

For example, if I were to try to prove whether all elements in a set is divisible by some number (say 3). Say I then brute force divide all elements by 3 and sees that indeed all elements in this set is divisible by 3. Now where in this process would a certificate come into play?

Also, how would you go about to physically construct a certificate?

# Answer
Suppose you are the verifier for SUBSET-SUM: "given a set $S$ of integers, is there a subset of $S$ whose elements sum up to exactly zero?" To show the problem is in NP, you must be able to efficiently verify that a solution I give you is correct. As the verifier, you *only* care about verifying solutions (*not* "finding solutions"!). You do *not* care where that solution might come from or who constructs it. Now, when you are given a subset, you can easily sum up the elements and announce whether or not those elements sum up to 0.

The example you mention is a problem that is also in P (clearly, we can solve it in polynomial time). Every problem in P is also in NP. We don't have to care about the certificate, but instead we can simply solve the problem in polynomial time. (Check the definition of NP if this feels confusing, but hopefully it doesn't).

You might also enjoy the question How can I verify a solution to Travelling Salesman Problem in polynomial time?
> 0 votes

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


# Question
Title: What does the 2 in a 2-approximation algorithm mean?
Does the 2 in a 2-approximation algorithm mean the solution is within 2\*OPT or OPT/2?

# Answer
> 17 votes
Typically, we use $\alpha \< 1$ for maximization problems, and $\alpha \> 1$ for minimization problems, where $\alpha$ is the approximation guarantee. So, a $2$-approximation algorithm returns a solution whose cost is at most twice the optimal. But as always, to be absolutely sure, go back to the definitions of the text you are reading (if a definition is not available, assume this).

---
Tags: algorithms, algorithm-analysis, np, approximation, polynomial-time
---


# Question
Title: Is the extension of every undecidable theory undecidable?
While it is not the case that the extension of every decidable theory is decidable, is it true that:

the extension of every undecidable theory undecidable?

In other words, given an undecidable theory A, is it enough to show

$$A \subseteq B$$

to prove that B is undecidable?

# Answer
No. A theory is a set of theorems. The set of all formulas is a decidable theory and it is an extension of all theories, including undecidable ones. It is also very inconsistent and thus useless in practice, but it is a counter-example to your claim.
> 3 votes

---
Tags: computability, logic, undecidability, closure-properties
---


# Question
Title: Multitape Turing machine with multiple non-blank tapes
A multitape Turing machine is defined to have input only appear on one tape, with the rest of the tapes blank.

Are there any formulations of a Turing machine that allow other tapes to be not blank? Why does the condition that the input only appears on one tape exist?

# Answer
> 3 votes
The restriction to a single non-blank tape at the start (and a single output tape too) is just convention – it makes the definitions a little simpler and maybe simplifies the analysis a little.

The reason we can make this restriction is that it makes no difference to the class of functions that are computable and it also makes no significant difference to the running time of algorithms. Any interesting Turing machine algorithm is going to need linear time since, otherwise, it can't even read all its input. For example, how would a Turing machine know to halt after $\log n$ steps? It's not read all its input in that time, so it doesn't even know what $n$ is!

This means that any linear-time preprocessing you do before the main part of your algorithm can't affect the asymptotic running time. So, in particular, you can check that, for example, your single input tape consists of three binary numbers separated by semi-colons, and copy those three numbers onto three separate tapes. Then you can run your main algorithm that thinks it has three different input tapes. Likewise, any Turing machine must run in time at least linear in the size of its output. This means that, if you have a machine whose output is spread across multiple tapes, you can postprocess that by copying it onto a single tape with the different parts separated by some special character.

As Raphael points out in his comment, there is at least one model that has more than one non-empty tape at the start. Probabilitstic Turing machines can be defined either by having multiple possible transitions from each state, each with an associated probability. Alternatively, they can be defined as deterministic Turing machine that has access to an infinite tape initialized with random bits. Note that this takes us outside the standard Turing machien model because we now have an infinite input. (This equivalence of a probabilistic machine on deterministic data versus a deterministic machine on random data is closely related to Yao's principle.)

---
Tags: turing-machines, computation-models, tape-complexity
---


# Question
Title: Does the normal form theorem imply that every partially computabe function is primitive recursive?
This is **Normal Form Theorem** (Second Edition of Computability, Complexity, and Languages written by Martin Davis page 75):

> Let $f(x\_1,...,x\_n)$ be a partially computable function. Then there is a primitive recursive predicate $R(x\_1,...,x\_n,y)$ such that:
>
> $f(x\_1,...,x\_n) = L(min R(x\_1,...,x\_n,z)\_z)$ *(minimization is on z)*

So I think an immediate result of this theorem is that every partially computable function is primitive recursive and every primitive recursive function is partially computable. is it true?

# Answer
No it not true. Primitive recursive functions are a subset of computable functions. The minimization operator from $\mu$-calculus is not primitive recursive and not guaranteed to terminate. The constantly false function for instance would cause minimization to loop infinitely. As you likely know primitive recursion is guaranteed to terminate.

What does seem to follow from this is that every computable function is $\mu$-recursive as primitive recursion is a subset of $\mu$-recursion. In fact I happen to know this to be true because $\mu$-recursion is turing complete.

You can check out primitive recursion and $\mu$-recursion on Wikipedia.

I also found a wikipedia page with some related matters. In particular they give another form of the Normal Form Theorem that seems slightly stronger; see here.
> 5 votes

# Answer
You read the theorem wrong; the right-hand side contains this $L(\min \dots)$ -- this is not primitive recursive! Note that, in particular, such $z$ does not necessarily exist (the "algorithm" will loop.)

$L(\min \\\_)$ in that theorem is also called the $\mu$-operator. It can not be expressed with primitive recursion.

This theorem states that one application of the $\mu$-operator is enough for Turing-completeness. In terms of WHILE programs, this means that you can program any function with using at most one WHILE loop.
> 5 votes

# Answer
The classical example of a computable function which is not primitive recursive is the Ackermann function. You can also construct such a function using diagonalization: given some effective enumeration $f\_n$ of the primitive recursive functions, the function $n \mapsto f\_n(n) + 1$ is computable but not primitive recursive.
> 2 votes

---
Tags: computability, normal-forms, primitive-recursion, mu-recursion
---


# Question
Title: Is a grammar that accepts function declarations, function calls and expressions (at any order!) necessarily cyclic?
As the title suggests, assume a grammar which has to recognize function declarations, function calls, and expressions, at *any order*. Does that mean it has to be cyclic, and therefore ambiguous?

I mean, it would have to look something like:

* S -\> function\_declaration | function\_call | expr
* function\_declaration -\> ... | S
* function\_call -\> ... | S
* expr -\> ... | S

Maybe not all of them would have to point back to S, that depends on the specifics. Is there any way to solve this?

# Answer
> 3 votes
There is just no need for rules (or non-terminals) that are cyclic, which I understand means that, for some non-terminal $X$, you have $X\stackrel\*\Rightarrow X$.

What you often need is recursive rules and non-terminals, such that $X\stackrel\*\Rightarrow uXv$, where $u$ and $v$ are strings of symbols. Without them, the language is finite.

For example, in the case of expressions you may have:

* $Expr \to Term + Expr \mid Term$
* $Term \to Factor * Term \mid Factor$
* $Factor \to Ident \mid Literal \mid ( Expr )$

This said, you are right that cyclicity, as you define it, does make the grammar ambiguous iff the cyclic symbol can also derive on a terminal string.

---
Tags: context-free, formal-grammars, ambiguity
---


# Question
Title: Use AVL trees instead of Chord algorithm for Distributed Peer to peer Hash tables
In distributed systems we use the Chord algorithm to create a p2p distributed hash table. While this algorithm is very useful and efficient wouldn't it be better if we used an AVL tree? Chord algorithm relies a lot to the hash function (in order for the nodes to be distributed evenly).

An AVL tree on the other is always balanced so in the worst case it will take $O(h)$ time to search for something, whereas h is the height of the tree and given that AVL trees are always balanced the height of the tree is at most $logN$ (whereas N is the number of living nodes in the network).

In my opinion AVL trees can give the same search speed (or maybe even better). So what is the need to use Chord algorithm instead of an AVL tree? I understand that Chord Algorithm is more of a Peer to peer system as many nodes know many others while in an AVL tree each node knows two descendants. Is this the sole purpose of not using AVL trees?

Is there an issue with handling churns that makes one better than the other?

# Answer
Chord is meant to be used in a **distributed system** where we need to be concerned with load balancing and handling failures of individual machines.

If you try to maintain an AVL tree in a distributed system by spreading the nodes among the available machines, the machine that has to take care of the root node will have a very high load as it is involved in every single request. Moreover, if this machine failed, the AVL tree would be partitioned, which requires you to introduce additional pointers for redundancy (similarly to what is done in Chord using "fingers").

A data structure that is suitable for distributed systems are Skip Graphs, which essentially have the same functionality as balanced trees, in particular, they provide $O(\log n)$-time operations. Moreover, a Skip Graph has built-in fault-tolerance (i.e. can handle churn), as it contains an expander graph as a subgraph (with high probability), and therefore can withstand even a constant fraction of node failures.
> 4 votes

---
Tags: algorithms, data-structures, distributed-systems, search-trees, peer-to-peer
---


title: Sensitivity and Block sensitivity

text:
# Question
Title: Sensitivity and Block sensitivity
May be this question is really silly and obvious but I am missing something subtle. I am reading on Sensitivity and Block sensitivity.

Let $f:\\{0,1\\}^n\rightarrow \\{0,1\\}$ be a Boolean function.

Let $\[n\]=\\{1,2,\dots,n\\}$.

If $i\in\[n\]$, let $\Bbb 1\_i$ be length $n$ vector with all $0$s except $1$ at $i$th position.

If $B\subseteq \[n\]$, then $\Bbb 1\_B$ be the length $n$ vector with $1$s only in positions marked by $B$.

If $i\in\[n\]$ and $x\in\\{0,1\\}^n$, let $x^i=x\oplus\Bbb 1\_i$ where $\oplus$ is $XOR$ operation.

If $B\subseteq \[n\]$ and $x\in\\{0,1\\}^n$, let $x^{B}=x\oplus\Bbb 1\_B$ where $\oplus$ is $XOR$ operation.

Sensitivity of $f$ at input $x$ is $$S\_x(f) = |\\{i:f(x)\neq f(x^i)\\}|$$

Sensitivity of $f$ is $$S(f)=\max\_xS\_x(f)$$

Block Sensitivity of $f$ at input $x$, $BS\_x(f)$ is maximum $r$ such that there is a set of disjoint subsets $\\{B\_i\\}\_{i=1}^r$($\forall i\neq j$, $B\_i\cap B\_j=\emptyset$) such that $$\forall j\mbox{, }f(x)\neq f(x^{B\_j})$$

Block Sensitivity of $f$ is $$BS(f)=\max\_xBS\_x(f)$$

It is clear that $S(f)\leq BS(f)$ since we can take size $1$ blocks at coordinates of input $x$ that are modified to achieves $S(f)$.

So why can't I say $BS(f)\leq S(f)$? That is, suppose we found a maximum set of blocks $B\_i$ that are disjoint, then cant I say:

1. There is no other bit position outside of $\cup\_{i=1}^rB\_i$ where we can change an input in order to change the input (Or else there is a size $1$ block that is disjoint and we can add to list $B\_i$ incrasing $r$).
2. It is clear $S(f) = |\cup\_{i=1}^rB\_i|$ since if we change all bit positions in $B\_i$ we change inputs and there is no other extra bit position by $1$.
3. Split the $B\_i$ in to size $1$ blocks to get $S(f)=BS(f)$?

Am I wrong in the definition that $2$ DOES NOT HOLD since we can only consider $1$ block at a time and hence we can only say $S(f)\geq max\_i|B\_i|$? Anything else I am missing?

Is there any example for which $BS(f)\leq S(f)^{1+\epsilon}$?

# Answer
**2** does not hold as stated. All you know is that if you flip the all bits in a given block $B\_i$, the output flips. Without additional conditions, I don't think you're guaranteed anything about flipping any individual bit within $B\_i$.

EDIT: In fact, if $B\_1, B\_2, \ldots, B\_i, \ldots$ represents a maximal set of blocks, then for any $B\_i$, there cannot be more than one index within $B\_i$ such that flipping the bit at that index will flip the output. Suppose that within $B\_i$ there are two indices, say $j$ and $k$, such that flipping either $x\_j$ or $x\_k$ will flip the output. Then $B\_i$ can be replaced by the two singletons $j$ and $k$, thus contradicting the assumption that the set of blocks was maximal.

Meanwhile, the first function found to have a quadratic gap between $BS(f)$ and $S(f)$ is due to Rubinstein (1995). You can find a quick summary of the construction in this blog post by Scott Aaronson. A function with slightly bigger separation was found later by Virza (2011).
> 4 votes

# Answer
Virza, improving on earlier work of Rubinstein, gives a function on $(2k+1)^2$ variables with sensitivity $2k+1$ and block sensitivity $(2k+1)(k+1)$. His function is defined as follows. Partition the input variables into $2k+1$ "sections" of size $2k+1$. The function is 1 if at least one section $x\_1,\ldots,x\_{2k+1}$ satisfies one of the following: (1) $x\_{2i-1} = x\_{2i} = 1$ for some $1 \leq i \leq k$ and all other $x\_j$ are zero, or (2) $x\_{2k+1} = 1$ and all other $x\_j$ are zero.
> 3 votes

---
Tags: complexity-theory, boolean-algebra
---


title: Vertex Cover of size k in a tree?

text:
# Question
Title: Vertex Cover of size k in a tree?
What is a polynomial time algorithm for finding a vertex cover of size $k$ in a tree? Would depth first or breadth first search be efficient or is there some other algorithm that finds the vertex cover that takes $n^k$ time rather $2^n$ time?

# Answer
Hint: Suppose $x$ is a leaf and $y$ is the unique neighbor of $x$. Show that there is always a minimum vertex cover which contains $y$. (Every vertex cover contains either $x$ or $y$; if it contains $x$, then replacing $x$ with $y$ we still get a vertex cover.)
> 1 votes

---
Tags: complexity-theory, graphs, trees, polynomial-time
---


# Question
Title: Prove that this family of hash function is $3$-wise independent, but not $4$-wise independent
> Consider the hash function mapping $w$-bit keys to hash values in $\\{0,...,m-1\\}$. Suppose $w=cr$. Interpret a $w$-bit key $x$ as a vector $(x\_1,...,x\_c)$ of $c$ $r$-bit keys.
>
> Consider the hash family:
>
> $$H = \\{h\_{T\_1,...,T\_c}:T\_i \in \\{0,...,m-1\\}^{2^r}\\}$$
>
> where
>
> $$h\_{T\_1,...,T\_c}(x) = \sum\limits\_{1\le i \le c}T\_i\[x\_i\]\mod m$$
>
> Prove that $H$ is $3$-wise independent, but not $4$-wise independent.
>
> $H$ is $k$-wise independent if for inputs $x\_1,...,x\_k$ and output $v\_1,...,v\_k$, $\Pr\[h(x\_1) = v\_1 \wedge ... \wedge h(x\_k)=v\_k\] = \frac{1}{m^k}$

So I can certainly see why $H$ is $1$-wise and $2$-wise independent if we're choosing inputs to the hash function that must be different from each other. However, I'm having a lot of trouble seeing why the family is not $4$-wise independent, which I think lends greatly to my difficulty in proving that the family is $3$-wise independent.

So for the family to not be $4$-wise independent, if we have inputs $x\_1,...,x\_4$ and outputs $v\_1,...,v\_4$, $\Pr\[h(x\_1)=v\_1\wedge...\wedge h(x\_4)=v\_4\]\not = \frac{1}{m^4}$. I am trying to think of a counterexample where this will not be the case, but it seems like we need, for example, $x\_4$ to be constructed in such a way that $v\_4$ can be attained by some combination of $v\_1,v\_2,v\_3$. However, all of $x\_1,...,x\_4$ are $w$-bit keys, so even if $x\_4$ had bits taken from each of $x\_1,x\_2,x\_3$, the output $v\_4$ would still be some random sum corresponding to the $c$ $r$-bit blocks accessing each $T\_i$.

Is there something I'm missing here? Perhaps it's not possible for $v\_4$ to be some combination of $v\_1,...,v\_3$, but how else would we show that $H$ is not $4$-wise independent?

# Answer
**Hint for refuting 4-wise independence:** Suppose for simplicity that $c = 2$, pick some $\alpha \neq \beta$ of length $r$, and consider the four inputs $(\alpha,\alpha),(\alpha,\beta),(\beta,\alpha),(\beta,\beta)$.

**Hint for proving 3-wise independence:** Let the three inputs be $x,y,z$. If there is some coordinate $i$ such that $x\_i,y\_i,z\_i$ are all different then we are done. Otherwise, without loss of generality there are coordinates $i,j$ such that $x\_i = y\_i \neq z\_i$ and $x\_j = z\_j \neq y\_j$, and we are again done.
> 0 votes

---
Tags: algorithms, algorithm-analysis, data-structures, probability-theory, hash-tables
---