# Question
Title: How must Grovers algorithm be modified in order to solve 3-SAT?
Grover's algorithm was designed for a database with **exactly one** item that matches a given search criterion, and can be used to find that very item.

However, when checking whether a given formula is in 3-SAT, I don't know how many items match the search criterion (i.e. how many interpretations satisfy the formula) and I just want to know whether there is **at least one**. So, what steps have to be taken in order to make Grover's algorithm suitable for 3-SAT?

# Answer
Grover's algorithm is already suitable. It promises that if there is at least one match, then it will output at least one match. It doesn't promise to output all matches, but you don't need all matches.

It is usually described to work in the case where there is zero or one items that match, but that's just because those are the hardest cases. If there are multiple matches, the algorithm will still work and will still find a match; and the running time will remain the same.
> 5 votes

# Answer
Notwithstanding D.W.'s answer, the other option, if all you knew about Grover's algorithm is that it requires unique solutions, is to use the work of Valiant and Vazirani. Without getting into details, the idea is like this. Suppose that there are roughly $2^k$ solutions. We add random constraints that "kill" a solution with probability $2^{-k}$. With constant probability, the resulting instance has a unique solution. While we don't know $k$, there are only polynomially many possible $k$s, so we can enumerate over all of them.
> 4 votes

---
Tags: quantum-computing, 3-sat
---


# Question
Title: MAP estimation (for stationary iid gaussian environment)
This is my first post, and have been self studying Haykin's Neural Networks and Learning Machines book. I'm not sure if this is a typo or if I'm doing something wrong, but I've been stuck on a statement on page 75.

The context was the process of finding a Maximum likelihood estimate for a parameter vector assuming a stationary, iid, and Gaussian environment.

Given: d is a scalar, i indexes time from 1 to N, and $\mathbf{w},\mathbf{x}\_i $ are m-dimensional vectors.

$\hat{w}\_{MAP} = max\_{\mathbf{w}}\[-\frac{1}{2}\Sigma\_{i=1}^{N}(d\_i - \mathbf{w}^T\mathbf{x}\_i)^2 - \frac{\lambda}{2}||\mathbf{w}||^2\]$

we should get the same result if instead we find the minimum of the quadratic function

$E(\mathbf{x}) = \frac{1}{2}\Sigma\_{i=1}^{N}(d\_i - \mathbf{w}^T\mathbf{x}\_i)^2 + \frac{\lambda}{2}||\mathbf{w}||^2$

Haykin says you should arrive at the result (by differentiation wrt $\mathbf{w}$ and setting the result to 0)

$\hat{w}\_{MAP} = (R\_{xx} + \lambda I)^{-1} r\_{dx}$

where $R\_{xx} = -\Sigma\_{i=1}^N \Sigma\_{j=1}^N \mathbf{x}\_i \mathbf{x}\_j^T $ is the M\*M correlation matrix of x and $r\_{dx} = -\Sigma\_{j=1}^N \mathbf{x}\_i d\_i$

My question is why isn't $R\_{xx} = -\Sigma\_{i=1}^N \mathbf{x}\_i \mathbf{x}\_i^T?$ Haykin goes through about a paragraph saying how the correlation matrix is time averaged and I think this is an important point. Thanks for any help!

# Answer
$\newcommand{\bd}{\mathbf{d}}\newcommand{\bw}{\mathbf{w}}\newcommand{\bX}{\mathbf{X}}$Your observation is correct--it appears to be several typos. To see why let's re-write the likelihood equation to something a bit more suitable for differentiating using matrix/vector notation. $$\text{NLL}(w) = \frac{1}{2}||\bd - \bX\bw||^2\_2 + \frac{\lambda}{2}||\bw||^2\_2,$$

where $\bX$ is our matrix of observations, $\bd$ is our vector of labels and $\bw$ is our vector parameter of interest. Taking the derivative yields, $$\frac{\partial \text{NLL}}{\partial \bw} = -\bX^t(\bd - \bX\bw) + \lambda\bw.$$

Setting this equal to 0 and solving gives, $$ \begin{align\*}\lambda \bw &= \bX^t(\bd - \bX\bw) \\ &= \bX^t\bd - \bX^t\bX\bw \iff\\ \lambda\bw + \bX^t\bX\bw &= \bX^t\bd \iff \\ (\lambda\mathbf{I} + \bX^t\bX)\bw &= \bX^t\bd \iff \\ \hat{\bw}\_{\text{MAP}} &= (\lambda\mathbf{I} + \bX^t\bX)^{-1}(\bX^t\bd). \end{align\*}$$

Notice that $$\bX^t\bX = \sum\_i \mathbf{x\_i} \mathbf{x\_i}^t = R\_{xx}$$ and $$\bX^t\bd = \sum\_i \mathbf{x\_i} d\_i = r\_{dx}.$$
> 2 votes

---
Tags: machine-learning, mathematical-foundations
---


title: Ambiguous context free

text:
# Question
Title: Ambiguous context free
Is there any technique to prove that a given language L is not ambiguous context-free? Here I don't know that whether L is CFL or not.

# Answer
Your question is strange. If you do not know what kind of language you have, the question may well be meaningless, as the concept of ambiguity can only be defined with respect to a known system of enumeration of the sentences of the language. There is none if the language is not Recursively Enumerable.

Thus it does not make sense to ask whether a language is ambiguous in general.

I take this as an opportunity for a little survey of these types of definitions.

In your case, if you specified that your language is context-free (but you did not), the question makes some more sense since CF languages have at least one CF grammar, which can be used as reference rewriting system to generate the sentences of the language (assuming you restrict to leftmost derivations, as canonical representatives of equivalence classes of derivations).

However, each CF language has actually an infinity of CF grammars generating it, and ambiguity has to be defined with respect to a single generation system. Hence the concept of ambiguity makes sense for the language of a given CFG with respect to that CFG, but does not make sense a priori for the langage alone.

However, computer science developed the concept of **inherent ambiguity**.

> A CF language is inherently ambiguous iff all CF grammars generating that language are ambiguous.

It is however becoming common to say that a CF language is ambiguous to mean that it is inherenlty ambiguous.

Notes:

1. Given any CF grammar G, it is trivial to give an ambiguous CF grammar G' that generates the same language. So, what can be interesting is not to know whether a CF language may have an ambiguous CF grammar (that is always possible), but whether it has only ambiguous CF grammars.
2. This refers only to CF grammars. It is possible that an inherently ambiguous CF language can be generated unambiguously by a grammar that is not CF. For example, I would conjecture that there is an inherenlty ambiguous CF language that can be generated by an unambiguous Tree Adjoining Grammar (TAG) (but I do not know whether it is true or easy to check).
3. This kind of knowledge organization framework can apply to other properties related to the generation or recognition process associated with a language. A good example is determinism of automata of a given family recognizing the language. Precision is always important: a language may be inherently non-deterministic with respect to a left-to-right PDA recognizer, but not when the PDA recognizer is right-to-left.
4. This kind of framework, whether for ambiguity or other properties, can also be developed for other families of languages and enumeration mechanisms (possibly up to some notion of generative equivalence, such as the order of rule application in the case of CF grammar derivations).

Hence your question should be better phrased as:

If I am given a language L that is Context-Free, is there any technique to prove that it is not ambiguous.

It is even better if you say "... that it is not inherently ambiguous".

Note that even there, there is the implicit assumption that you refer to the leftmost derivations of CF grammars.

In the case of CF languages and grammars, you have many answers that you can find on the CS Theory site at the question Ambiguity in regular and context-free languages.

In particular:

* it is undecidable whether a given CF grammar is ambiguous (1962-63, Cantor - Floyd - Chomsky and Schutzenberger)
* it is undecidable whether a given CF language is inherently ambiguous (Ginsburg and Ullian - 1966).
> 5 votes

# Answer
the general problem of determining whether a CFL is "inherently ambiguous" is undecidable (as mentioned/ cited in comments) but heuristics do exist and are an active area of research. see eg
> 1 votes

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


# Question
Title: Is there a known way to convert any $QBF_2$-formula into an equisatisfiable $QBF_2$-formula in CNF in polynomial time?
It is easy to turn any boolean formula and any quantified boolean formula into an equisatisfiable formula in CNF using *Tseitin transformation*:

$$ Q\_1 z\_1 Q\_2 z\_2 \ldots Q\_n z\_n \Phi \Rightarrow Q\_1 z\_1 Q\_2 z\_2 \ldots Q\_n z\_n \exists x ((\neg{x} \vee \Psi) \wedge \Phi\[x/\Psi\] ),\ Q\_i \in \\{ \exists, \forall \\} $$

(For details, see for example here). My two questions are:

1. Can any formula of the form $\forall z\_1 \ldots \forall z\_n \exists z\_{n+1} \ldots \exists z\_m \Phi$ be turned into an equisatisfiable formula of the same form (so beginning with $\forall$ and with just one alternation of quantifiers) in CNF using Tseitin transformation? I'm assuming **Yes**, since Tseitin transformation only adds existential quantifiers ($\exists$) right before $\Phi$.
2. Can any formula of the form $\exists z\_1 \ldots \exists z\_n \forall z\_{n+1} \ldots \forall z\_m \Phi$ also be converted into an equisatisfiable formula of the same form (so beginning with $\exists$ and with just one alternation of quantifiers) in CNF in *polynomial time*? I'm assuming **No** since Tseitin transformation would give us the form $\exists z\_1 \ldots \exists z\_n \forall z\_{n+1} \ldots \forall z\_m \exists x\_1 \ldots \exists x\_l \Phi'$ and I'm not aware of any other polynomial time transformation useful in this case.

# Answer
> 2 votes
1. Yes, for exactly the reasons you listed.
2. I don't know of any way to do what you want. However, it is possible to convert it to a formula of the form $\neg \forall x \exists y \Psi$ (negate it, then convert $\neg \Phi$ to CNF via the Tseitin transform and let $\Psi$ be the result), so if you have an oracle that will solve QBF2-CNF queries, it can be used to solve QBF2 queries.

---
Tags: polynomial-time, propositional-logic
---


# Question
Title: How does cpu fetch active program data (using virtual address) from storage when there is a page fault?
I read that cpu generates virtual address and using the same mmu translates to physical address and then fetches the data from RAM. But when there is a page fault, the data is fetched from the HDD(or Secondary Storage) where the program resides. But how does the cpu knows exact location of the program on storage device. Does it maps the virtual address to the address of storage device? If yes, how does it do ?

# Answer
The CPU knows nothing about swapping. This is performed by the operating system.

When a memory access takes place, the MMU consults page tables to find the physical address that is associated to a virtual address. Each page tables contains a number of descriptors that explain to the MMU what the physical address is. A page fault occurs when the descriptor contains an invalid value (i.e. one that does not denote a physical address).

When a page fault occurs, the CPU transfers control to a predefined piece of code in kernel mode and sets a register to the problematic address. The kernel code looks up the address in its own tables to figure out whether it is swapped out or invalid. On many architectures, there are many unused bits in an invalid descriptor, which allows the kernel to store its own data in the page tables. Based on these values, if the kernel determines that the page is swapped out, it will allocate a physical memory page, load the content from swap, modify the content of the faulting descriptor to point to this physical page, and transfer control back to the program so that it executes the memory dereference again. If the kernel determines that the page is invalid, it typically terminates the application, or transfers control to its fault handler.

The layout of descriptors and of any additional kernel data structure is highly dependent on the processor architecture and the kernel. Here's a fictional, simplified example of how it might look like (real machines and operating systems tend to be a lot more complex).

* The machine is capable of addressing 4GB of virtual memory and 8TB of physical memory. Each page is 4kB. A page table consists of 1048576 descriptors, each of which occupies 4 bytes. (In the real world, MMUs use 2 or 3, sometimes 4 levels of descriptors, rather than a single gigantic table.)
* In each descriptor, the lowest bit indicates whether the descriptor is valid. If the lowest bit is 0, the descriptor is valid, and the corresponding physical page is $2^11 \times d$ where $d$ is the descriptor value. If the lowest bit is 1, the descriptor is invalid, and the MMU ignores the other bits. (In the real world, there are more bits in descriptors for permissions, cache maintenance, etc.)
* The operating system uses the 31 higher bits of invalid descriptors to locate a swapped-out page. The OS supports up to 8TB - 4kB of swap; the special value all-bits-one indicates an invalid page. Separate data structures map ranges of swap addresses to ranges of disk locations.
> 3 votes

---
Tags: computer-architecture, operating-systems, memory-management, virtual-memory, paging
---


# Question
Title: How does a turing machine with doubly infinite tape simulate a normal-taped turing machine?
The intuition is that on any input, we can write a symbol like $\\#$ on the left that tells the machine to not move past this symbol. However, I'm running into problems trying to show this using the formal definition of a turing machine. It's not simple using the usual 7-tuple definition. Any help would be appreciated.

# Answer
Given the doubly infinite machine $M = (Q,\Gamma,\sqcup,\Sigma,\delta,q\_{0},F)$ where:

* $Q$ is the set of states,
* $\Gamma$ is the tape alphabet,
* $\sqcup \in \Gamma$ is the blank symbol,
* $\Sigma \subseteq \Gamma\setminus\\{\sqcup\\}$ is the input alphabet,
* $\delta: Q\setminus F\times\Gamma\rightarrow Q\times\Gamma\times\\{L,R\\}$ is the transitions function (there are various common modifications to $\delta$ which you can add in if you wish),
* $q\_{0} \in Q$ is the start state, and
* $F$ is the set of final states,

we can simulate a singly infinite Turing machine with the following modifications to $M$:

* add a new symbol $\\#$ to $\Gamma$ which will mark the "left-hand end" of the simulated tape,
* add the new states $k\_{0}$, $k\_{1}$ and $r$ to $Q$,
* make $k\_{0}$ the new start state,
* add the following transitions:
    + $(k\_{0}, x) \mapsto (k\_{1},x,L)$ for every $x \in \Gamma$
    + $(k\_{1}, \sqcup) \mapsto (q\_{0}, \\#, R)$
    + $(q\_{i}, \\#) \mapsto (r, \\#, L)$
* make $r$ a reject state in whatever way you're handling reject states.

This new machine starts (as suggested in the question) by writing a new, special, end-of-tape symbol just to the left of the input. Then if it ever sees that symbol again, it rejects (it has "fallen off the tape").

A similar technique can be used to *prevent* a singly infinite TM from falling off the left-hand end of the tape, so you can also encode that into the machine, and it would work similarly.
> 1 votes

---
Tags: turing-machines
---


# Question
Title: Prove the language of all concatenations of words in a regular language is regular
For a language $L\in\Sigma^\*$ we define $$ L^\*=\\{w\mid \exists k\in \mathbb{N}\cup\\{0\\}, ∃x\_1,...,x\_k\in L \ (w=x\_1...x\_k) \\} $$ Let $L$ be a regular language over some alphabet $\Sigma$. Prove that $L^\*$ is regular.

# Answer
I have to guess about your definition of a regular language (I can't comment to ask yet...), so I will assume the following:

> A language $L$ is regular over an alphabet $\Sigma$ if and only if it can be generated by a regular grammar with terminal symbols $\Sigma$.

We are given that the the language $L$ is regular. Therefore, let $G = (N, \Sigma, P, S)$ be an $\epsilon$-free regular grammar that generates $L$. (Such a grammar can always be constructed by considering any regular grammar that generates $L$, and removing all terminals that only produce $\epsilon$.) We now examine the production process for $L$. We first note that, since any rule is of the form $A \rightarrow a$ or $A \rightarrow aB$, where $A,B \in N$ and $a \in \Sigma$, we have at any point in the process at most one non-terminal at the righthand side of the current sentential form. Secondly, if at any point a rule of the form $A \rightarrow a$ is used, the production process is completed, since the sentential form then only consists of terminal symbols and no further replacement can occur.

Let us now consider rules the form $A \rightarrow a$, and for every such form add a new rule $A \rightarrow aS$. We also add the rule $S \rightarrow \epsilon$. This results in a new regular gammar $G' = (N, \Sigma, P', S)$. It is then straightforward to see that $G'$ generates the language $L^\*$, which proves that $L^\*$ is indeed regular.

Note that if you were to use the left-hand definition of a regular grammar (only rules of the form $A \rightarrow a$, $A \rightarrow Ba$ or $A \rightarrow \epsilon)$, the proof would be almost the same, adding rules of the form $A \rightarrow Sa$.
> 2 votes

---
Tags: regular-languages, closure-properties, kleene-star
---


# Question
Title: How does one formulate a backtracking algorithm
I am new to learning algorithms. I was reading backtracking algorithm for generating all strings for n bits. If I dry run the program I know the program is giving right result. But I didn't understood the logic can anybody please explain? What I mean is what will be be the thought process to arrive at this solution

```
void binary(int n)
{
    if(n < 1)
        printf("%s\n",A);    // Assume A is a global variable
    else
    {
        A[n-1] = '0';
        binary(n-1);
        A[n-1] = '1';
        binary(n-1);
    }
}

```

# Answer
This answer begins with a first section explaining the problem in more general terms. The direct answer to the question for the example given by the OP is then given in a second section that illustrate the discussion in the first.

*You may well want to skip the first section and go direcly to the second one, depending on whether you like to start with basic principles or with the analysis of an example.*

## The principles : non-deterministic programming

My description is not intended for this algorithm only, but is more a general way to design such algorithms.

**The key idea is that backtracking is a technique to implement non-determinism with depth-first exploration of the non-deterministic space of possibilities.**

Non-determinism allows you to separate the logic of the problem from the non-deterministic exploration of the solution space. It makes programs clearer, simplifies analysis and proofs of properties. This is pretty much the same advantage that you get when using non-determinism in Automata Theory, to simplify the design of automata performing a given calculation. Non-determinism makes your technical life much easier.

This advantage is such that various programming experts and language designers have analyzed or experimented with the introduction of a standard non-deterministic functionality in various programming languages, not to mention the language Prolog where non-determinism is a central control feature.

Another advantage of using non-determinism is that it leave open the implementation technique, that can also use breadth first exploration, or even dynamic programming (to avoid repeating calculations). And the handling of non-determinism, such as adding the backtrack control, is done entirely by the compiler.

An interesting side-point is that BNF, the language of context-free grammars, can be seen as a simple non-deterministic programming language to write parsers. And you can compile it fairly simply into a depth-first parser (some early ones were just that - Ned Irons, 1961), or a breadth-first one, or a dynamic-programming one (CYK, Earley, and some others).

However, backtracking requires mastering the state of the environment. Without going into details, it is much easier to implement it in a purely functional programming language that has no side-effects (for example, no assignment to global variables), at least not in the parts of programs that use non-determinism.

This is not in contradiction with the use of the global variable `A` below, which is never read, except to collect the answers.

But it explains why I insist on starting with a recursive non-deterministic program, rather than with an equivalent iterative variant.

What is described below could well be done automatically by the compiler of a non-deterministic language.

## Description of the design for the given example

Here is how I would explain the design of this algorithm.

You consider an array `A` of bits where the permutation is stored before printing. It can be a global variable.

First you write a non-deterministic algorithm, that will just produce one permutation, a "random" one, chosen by the god of non-determinism :)

This is a simple recursive procedure that ask the god's oracle **choose** for each bit in succession. The **choose** oracle return non-deterministically one of its arguments (here the word oracle is used in its mythological sense, not in the usual sense of computability theory). Using recursion is important, as I shall explain later.

```
void binary(int n)
{
    if(n < 0)
        printf("%s\n",A);    // Assume A is a global variable
    else
    {
        A[n-1]= choose('0','1')
        binary(n-1);
    }
}

```

You should agree that this algorithm will return one of the permutation, anyone of them. You could organize the recursion differently, it does not really matter. All that matters is that you may follow any of the possible computations.

What you have done with this program is to prepare for all choices that will make a permutation.

Then, instead of making one choice non deterministically, you simply try them all, one after the other, for each of the calls.

Since you have a list of the possible choices (there can be a variable number of them), you just try them in succession. You can do that by having a segment of code for each possible value. But when the possible values are in a list of variable length, you can just loop over that list.

Here you have just 2 values, so you just write twice the same code, once for each of the values, so that:

```
        A[n-1]= choose('0','1')
        binary(n-1);

```

becomes

```
        A[n-1]= '0'
        binary(n-1);
        A[n-1]= '1'
        binary(n-1);

```

The first call to binary will produce all permutations with '0' in position `n` and the second all permutations with '1'.

Instead of choising arbitrarily, you do one, then the other.

There is an invisible trick that helps you. This would be somewhat harder if you had used an iteration rather than a recursion.

The reason is that, for each former call to **choose**, you have to come back to it after trying all possibilities of later choices, and you have to remember what are the choices you have not tried yet.

This is very easily handled by returns of the recursive call, where you find the environment and the execution point where you left it, so that you simply go on.

If you had used an iteration, you would have a beautiful mess managing the data to recall how far you have dealt with each non-deterministic choice.

You could have started with a very simple loop, that is also a non-deterministic way of computing a single permutation.

```
void binary(int n)
{
    for (i=n-1; i=0; i--) {
        A[i]= choose('0','1')
    }
    printf("%s\n",A);
}

```

But transforming this program into a deterministic backtracking program would be a lot harder.

Isolating each non-deterministic choice in a function makes your life easy.

There is an old classical paper that talks of non-deterministic algorithms, though I have not looked at it in a very long time, and I have no memory of how it handles the problem. People were not using recursion as much in those times. You may want to look at it. Bob Floyd was one of the pioneers of computer science.

Non-deterministic algorithms, Robert W. Floyd, 1966.

I do not recall where it was published, but it is easy enough to find.

Note: The previous version of the answer was assuming arrays are indexed from `1` to `n`. I changed that as it may put off users who recognize the code as C code. The site is normally language agnostic. The program given in the question is missing both `A[0]` and `A[n]`.
> 6 votes

# Answer
The idea here is to implement the following recursive definition of the set $A\_n$ of all binary strings of length $n$: $$ A\_0 = \\{\epsilon\\}, \qquad A\_n = \\{x0 : x \in A\_{n-1}\\} \cup \\{x1 : x \in A\_{n-1}\\}. $$ Here $\epsilon$ is the empty string. You can also start at $A\_1 = \\{0,1\\}$, but your program actually has $0$ as a base case. Starting with this recursive definition, it is routine to convert it to your recursive procedure.

To make sure that you understand this, I recommend the following exercise. Try to implement the following slightly different recursive definition: $$ B\_0 = \\{\epsilon\\}, \qquad B\_n = \\{0x : x \in B\_{n-1}\\} \cup \\{1x : x \in B\_{n-1}\\}. $$

---

Languages like python which support generators natively make this even easier. Here is code that generates all binary strings of length $n$, based on the recursions above:

```
def A(n):
    if n == 0: yield ''
    for x in A(n-1): yield x + '0'
    for x in A(n-1): yield x + '1'

def B(n):
    if n == 0: yield ''
    for x in B(n-1): yield '0' + x
    for x in B(n-1): yield '1' + x

```

Python also makes it easy to implement these recursions slightly differently:

```
def C(n):
    if n == 0: yield ''
    for x in C(n-1):
        yield x + '0'
        yield x + '1'

def D(n):
    if n == 0: yield ''
    for x in D(n-1):
        yield '0' + x
        yield '1' + x

```

Can you tell what is the connection between the orders generated by A,B,C,D?
> 3 votes

---
Tags: algorithms, backtracking
---


# Question
Title: Non-erasing Turing machines and loss of generality
A non-erasing Turing machine is one that cannot replace a symbol with a blank unless the symbol under the read head is a blank. I'm trying to understand whether there is loss of generality because of this restriction.

My guess is that there is no loss of generality, because the restriction above merely restricts replacing characters with blanks, but we can just as easily replace them with some other symbol and construct any rules that might have used blanks to use the new symbol. I think that's too simple a solution though.

Can anyone give me any insight as to how to show whether or not generality is lost in the special case of non-erasing Turing machines?

# Answer
The purpose of the blank symbol is to differentiate the tape alphabet from the language alphabet. It is useful, typically, when you are trying to formulate a decision problem. From a more abstract point of view, as you clearly realize, a machine whose tape alphabet has at least two symbols is still exactly a Turing machine.

So you are erring towards generality, so to speak, not away from it.
> 3 votes

# Answer
Your definition of non-erasing Turing machine is "not the common one". Turlough Neary nicely summarizes early definitions and results for non-erasing Turing machines:

> Non-erasing Turing machines are a restriction of Turing machines that are permitted to overwrite blank symbols only. Moore \[Moo52\] mentions that Shannon had proved that non-erasing Turing machines simulate Turing machines, however this result was never published. Shortly after, Shannon proved 2-symbol Turing machines universal, Wang \[Wan57\] proved 2-symbol non- erasing Turing machines universal. Later, Minsky \[Min61\] proved the same result as Wang using a different technique. Minsky proved 2-tape non- writing Turing machines were universal and showed 2-symbol non-erasing Turing machines simulate these non-writing machines.

So here it says "overwrite blank symbols only", while you wrote "cannot replace a symbol with a blank unless the symbol under the read head is a blank".

---

In general, it seems that being non-erasing is not a serious restriction, but the answer here has one reference with results that point in the opposite direction:

> 3. John E. Hopcroft, Jeffrey D. Ullman, "Nonerasing Stack Automata". JCSS, 1(2):166–186, 1967.
> 4 votes

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


# Question
Title: How many ways are there to add a node to a digraph?
In a digraph with $n$ vertices, how many different ways a new vertex can be added to get the digraphs with $n$+1 vertices?

Input digraph with $n$ vertices have following degree criteria :

1. There are no edges $(v,v)$ (self-loops),
2. If there is an edge $(u,v)$, there is no edge $(v,u)$,
3. $d\_{\mathrm{in}}(v) \leq 2$ for every vertex $v$, and
4. $d\_{\mathrm{out}}(v) \leq 2$ for every vertex $v$.
5. $d\_{\mathrm{in}}(v) + d\_{\mathrm{out}} \geq 3$ for every vertex $v$.

After adding one vertex, the digraphs with $n$+1 vertices should also follow same degree criteria.

Is there any way to mathematically express the number of possibilities?

My approach:

I come to know that, In a directed graph with n vertices has total degree k, can have at-most nk/2 edges. So for example (Specific Case) If the original digraph is having 20 vertices and total degree of each vertex is 3 (minimum case). That means maximum edge possible is 30. When I add one node to the digraph, total vertices will be 21 and if i take total degree to 4(maximum). Then maximum possible edges will be 42. Which means there is 12 (42 - 30) possible position where I can add new edge.

So finally I have 12 free positions(indegree and outdegree) and I can add maximum 4 and minimum 3 edges at once and then I will calculate possible combinations...Is this approach correct

# Answer
> 0 votes
Since we are not treating isomorphic graphs as identical, my advice in the comments to try all the options was bad.

Let $G$ be the original graph. Let $A$ be the set of vertices in $G$ that can accept an extra incoming edge and let $B$ be the set of vertices that can accept an extra outgoing edge. Every vertex has total degree 3 or 4 and no vertex in the new graph can have degree more than 4. This means that no vertex of $G$ can have more than one edge added to it, so $A\cap B=\emptyset$.

Now, consider adding a new vertex $x$ to $G$. By the degree conditions, $x$ must be connected to $G$ in one of the following ways:

* it sends one edge to $A$ and receives two from $B$;
* it sends two edges to $A$ and receives one from $B$;
* it sends two edges to $A$ and receives two from $B$.

Working out the total number of ways from here is simple combinatorics.

---
Tags: graphs, combinatorics
---


# Question
Title: What is this trapezoid-shaped logic component?
This is from http://www.cis.upenn.edu/~milom/cse240-Fall05/handouts/Ch05.pdf , slide 9.

From this diagram, I recognize 0001 as the opcode, which corresponds to the ADD instruction. I recognize 011, or 3, as the source register and 101, or 5, as the destination register. I know that the 1 signifies immediate mode or the second operand is directly in the instruction.

From here, I know that the second operand is 11111 or -1 in decimal and that it will be sign extended (SEXT) before being added to the data in the source register.

Does anyone know what the logical component I highlighted does?

The component is shaped like an isosceles trapezoid, and has three inputs: seemingly, two data inputs and one control input.

# Answer
Looking at slide 5-43 "Data Path Revisited" these are `MUX`, multiplexors.

As such they are a "switch": When the red input is `1`, we have immediate mode and the `SEXT` output is passed through unchanged. When it is `0` it needs to look up a value based on the `SEXT` value and some memory or register.

Also in the slides, a `MUX` is represented again at `BR` and `JMP`, slides 5-31 and 5-35, again without actually clearly defining the alternative scenarios, and the `BR` case confuses the issue a bit because it clearly calculates a relative jump previously.

I'd guess the red input is the result of the branch condition and if false the original `PC` is passed through, but if that was the case they might as well have connected up the lines in this diagram.

For the `JMP` it is currently showing an absolute jump and under a different red arrow input it could be an indirect jump, similar to the `ADD` case.

(My latter suggestions have not actually been reconsidered much after reviewing slide 5-43.)
> 4 votes

---
Tags: computer-architecture, arithmetic, memory-hardware
---


title: provability of while loop vs for loop

text:
# Question
Title: provability of while loop vs for loop
*I'm abit afraid to ask this question here seeing as I asked it on programmers SE already, the thing is I think the question is more about the underlying theory than the use in practice (or call it confirmation bias). (If people here agree i should not have asked it here I will delete it and offer my sincere apologies) however I do think it will get a deeper meaning here as to why this is or isn't true.*

**Here is the question:<br>** I have a teacher who (to me) seems quite intelligent, he really knows what he is talking about but he said something which surprised me (I'm paraphrasing): `while` loops can be proven where as `for` loops cannot.
I think this translates to: One can completely explain what happens in a `while` loop whereas you cannot do that for a `for` loop

Is my teacher right? (maybe this was the case when he started learning? ) and a more subjective question: Is there any clear reasoning behind this (why he would have stated this)?

# Answer
> 5 votes
**In a nutshell**: *What your teacher probably meant is that the semantics of `while` is pretty much the same in most languages, while the semantics of `for` may change considerably (see discussion below). Hence, abstract language independent proof are more reliable with a `while`, but one should be careful that a proof with a `for` loop may not match the semantics of the `for` loop in many languages.*

Your question is not precise enough (though that may not be your fault).

The point is that, afaik, there is no official, ISO supported standard, or otherwise officially accepted reference definition of `for` and `while` loops. The definition depends on the programming language.

Hence you cannot make any general statement regarding their equivalence before you have defined precisely what each can do. I adress that more precisely, since it is one of the main argument used in other answers (and the discussion will be useful in what follows).

## On intertranslatability of `for` and `while` loops

**Summary**: *it depends on the programming language, but is always possible a long as you can have one infinite loop and a way to get out of it.*

But you can make such a statement for a specific programming language, and the answer will depend on the features fo the language.

That also means that there is no general proof, but only one for each programming language.

One thing that is generally true is that a `while` loop can generally mimic a `for` loop, because the while loop can do the exit condition testing of the for loop, doing the initialisation of the control variable with an assignment before entering the loop, and doing the incrementation at the end of the loop body, so that

```
for i from 1 by 2 to 10 do { xxx }

```

becomes

```
i=1
while i≤11 do { xxx; i←i+2 }

```

This more or less works for most languages, but it is not as obvious as it seem, and there may be many "details" to worry about.

For example, in many languages, the `for` loop evaluates it 3 arguments (initial value, increment, and final value) as strict arguments, evaluated once before entering the loop, while others will take then as thunk arguments to be reevaluated at each turn, or possibly as lazy argument to be evaluated only when first needed.

Another point may be that the increment variable may be local to the `for` loop, or have to be a local variable of the function where the loop appears.

Depending on such issues, the translation of a `for` to a `while` may vary widely, though it is usually possible to achieve it.

The same holds for the converse, thranslating a `while` into a `for` loop.

Th first problem is that a `while` loop will always reevaluate the exit condition at each turn. But some `for` loops do not provide for a condition that is reevaluated at each turn, other than comparison of the control variable with some fixed value computed on loop entry. Then the translation is not possible unless there is some other mean to jump out of the loop on some arbitrary conditions.

That is achievable with various devices, usually starting with a conditional statement testing the condition, followed by an a jump out implemented, as available, by a loop exit statement, a return statement (after encapsulating the loop in a function), a goto statement or an exception raising.

In other words, it is again very dependent on languages, and possibly on subtle features of languages.

This say, as answered by @milleniumbug, the intertranslation is easy in the language C, because a `for` lopp is essentially a `while` loop plus some extra for an incremented control variable.

But this does not necessarily apply to other languages, and most likely not in the same way.

This being said, programming languages are usually supposed to have Turing power with only one of these loops, since all you need for it is one infinite loop. So, as long as you have some way of looping for ever, and possibly deciding to stop, you are pretty sure you can mimic any other construct ... but not necessarily easily.

## Regarding proofs

**Summary**: *There is no reason known to me to assert that proofs should be significantly harder with one or the other (unless some weird feature of the language).*

There is probably a misunderstanding, or your teacher had his mind on something else.

Formals semantics can be defined for the various kinds of loops defined in programming languages, and then used for proving properties.

It may be, again depending on the language, that conducting formal proofs regarding programs may be more complex in some cases. But that depends on the language.

I cannot imagine a reason why proofs should be significantly harder with one construct more than with the other. The `for` loop may be more complex since it can offer, as in C, all that is done with a `while` plus other things. But if you did it with a `while`, you would have to add the extras in some other form.

I could use the formal general argument of intertranslatability, as long as there is the possibility for a single infinite loop. I will however refrain from doing that, as the constructions involved are nothing you want to deal with in a proof, and it would clearly be an unfair statement, at least in practice.

Following the above discussion, however, we have seen that the difficulties for intertranslatability come from the great variability of the `for` loop from language to language. Hence the following conclusion which is probably the right answer:

One possibility to understand your teacher's statement is that the semantics of the `while` loop is pretty much the same in all programming languages, while the syntax and semantics of the `for` loop can vary significantly from language to language. Hence, **it is possible to make general "abstract" proofs with `while` loops that have language independent semantics to a good extent, while this is not possible for the `for` loop that has syntax and semantics changing too much from language to language.** But this does not apply within a given language, when the semantics of both are precisely defined.

My best suggestion is that you should ask your teacher what he precisely meant, and whether he can give you an example. Misphrasing or misunderstanding is a common event.

---
Tags: correctness-proof, loops
---


title: PAC learning axis parallel rectangles

text:
# Question
Title: PAC learning axis parallel rectangles
I am trying to understand the proof that the axis parallel rectangles are PAC learnable in the realizable case. This means that given $\epsilon, \delta$ with enough data we can find a function $h$ such that $$\mathbb{P}\left\[\text{error} \> \epsilon\right\] \leq \delta$$ Here error can be seen as the probability of making an error with our chosen function $h$.

Now, for axis parallel rectangles (in binary classification) the usual argument goes like this, let $R$ be the true rectangle and let $R'$ be the smallest rectangle containing the positive examples, clearly $R' \subseteq R$, we consider the four rectangular strips between $R'$ and $R$. Clearly if all of them have probability $\leq \epsilon/4$ then the probability of making an error is less than $\epsilon$, so we can assume that at least one have probability of making an error $\geq \epsilon/4$.

For such a strip the probability of correctly classifying all the $m$ training examples is at most $(1 - \epsilon/4)^m$, and thus taking aunion bound over all strips we get that the probability of correctly classifying everything is less than $4(1-\epsilon/4)^m \leq 4e^{-m/4}$, and with a bit of algebra this yields that the sample complexity is $m \geq (4/\epsilon)\ln(4/\delta)$.

Here is a pdf that explains in a bit more detail, with some pictures, I just had to condense the argument as much as I can to fit it in here.

My question is, why do we have to consider the four rectangular strips separatedly, why can't we just say that the probability of the region between $R'$ and $R$ has to be greater than $\epsilon$ (because otherwise we are done), and thus using the same argument we would arrive at the better bound $m \geq (1/\epsilon)\ln(1/\delta)$?

Sorry for the long question, and thanks in advance.

# Answer
The question is a little vague, but it seems like what you want to argue is along the line of this: Let $R$ be the concept to learn, and take any $R^\*\subset R$ be any rectangle covering a $(1-\epsilon)$-fraction of $R$. Then with some probability $R'$ will contain $R^\*$.

The problem with this is that the particular probability depends on the specific choice of $R^\*$. I think what you're confused about is that want $R'$ to perform well on *unseen* examples. By construction $R'$ will correctly classify all the training data. The bad event is actually that all of the training data is concentrated in too small a rectangle; this happens with probability at most that of the event that one of the strips is missed by all the training examples.
> 1 votes

# Answer
hmm... well, in the proof you mention, we draw points (x,y) from some distribution D, and check whether they fall into a square really. I.e. we pick the same $\delta$ for each bound (max x, min x, max y, min y). Now if you had a circle, you can't just do that - you have to pick a delta for a radius, and the radius is a function of coordinates. So that will make the proof more complicated.

If you go for non-concave polygons - its should get much harder.
> 0 votes

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


# Question
Title: Tree decomposition - Fastest algorithm in practise
I'm looking for a fast in practice algorithm for calculating the (preferable optimized) tree decomposition of a graph.

I found the paper "A linear time algorithm for finding tree-decompositions of small treewidth" \[1\] by Hans L. Bodlaender which return a tree-decompsiton with the optimized tree-width and as the name says, the algorithm runs in linear time but since there are no (translation: I have not found ) any implementations, I am not sure if it's being used in practice or not.

Is the paper by Hans L. used in practice or does the constant factor make the algorithm useless?

\[1\] http://dl.acm.org/citation.cfm?id=167161

\[2\] http://www.treewidth.com/docs/libtw.pdf

Edit: Linked https://math.stackexchange.com/questions/1246421/tree-decomposition-by-hand-for-understanding

# Answer
> 11 votes
The first caveat is that deciding whether the treewidth of a graph is at most $t$ is NP-complete, but it is FPT (which is what Bodlaender's paper shows). So for small $t$, we can (in principle) solve the problem exactly (and actually spit out the decomposition as well), but for graphs with large treewidth, then things can get a bit slow.

Having said that, you're right, the hidden constants in Bodlaender's algorithm are prohibitive, but there are more practical ways of getting at least a good tree decomposition. A useful place to start is with another of Bodlaender's papers, "A tourist guide to treewidth", which is now a bit old, but still has some valuable information and references to algorithms for generating tree decompositions, particularly in various restricted graph classes (sometimes the algorithms work in general, you just don't get a nice upper bound on the running time outside of the restricted class). John Fouhy's master's thesis "Computational experiments on graph width metrics" includes a number of way of obtaining tree decompositions (you can find it here under the link "John's thesis").

Probably most useful though is if you can get a copy of Downey and Fellow's new book "Fundamentals of Parameterized Complexity" (Springer, 2013), in which they devote Chapter 11 to heuristics for finding tree decompositions. This is probably the most recent survey in covering this material. They also note that the handful of attempts at implementing Bodlaender's algorithm have not been successful because it was impractically slow, so your lack of success in finding implementations is no coincidence. Bodlaender's algorithm works via recursive application of an FPT algorithm, the problem being that the recursion depth depends on the treewidth, (checking Downey & Fellows, the recursive depth is $O(t^8)$) which just becomes too prohibitively slow too quickly.

---
Tags: graphs, time-complexity, runtime-analysis
---


# Question
Title: How do garbage collectors avoid stack overflow?
So I was thinking about how garbage collectors work and I thought of an interesting issue. Presumably garbage collectors have to traverse all structures in the same way. They can't know weather they are traversing a linked list or a balanced tree or whatever. They also can't use up too much memory in their search. One possible way, and the only way I can think to traverse ALL structures, might be just to traverse them all recursively the way you would a binary tree. This however would give a stack overflow on a linked list or even just a poorly balanced binary tree. But all the garbage collected languages that I have ever used seem to have no problem dealing with such cases.

In the dragon book it uses a "Unscanned" queue of sorts. Basically rather than traversing the structure recursively it just adds things that need to be marked too a queue and then for each thing not marked at the end it is deleted. But wouldn't this queue get very large?

So, how do garbage collectors traverse arbitrary structures? How does this traversal technique avoid overflow?

# Answer
> 11 votes
**In a nutshell**: *Garbage collectors do not use recursion. They just control tracing by keeping track of essentially two sets (that may combine). The order of tracing and cell processing is irrelevant, which gives considerable implementation freedom to represent the sets. Hence there are many solutions that are actually very cheap in memory usage. This is essential since the GC is called precisely when the heap runs out of memory. Things are a bit different with large virtual memories, as new pages can be easily allocated, and the ennemy is not lack of space, but lack of data locality.*

I assume you are considering *tracing* garbage collectors, not *reference counting* for which your question does not seem to apply.

**The question is focussing on the memory cost of tracing** for keeping track of a set: the set $U$ (for untraced) of accessible memory cells that still contain pointers that have not yet been traced. **This is only half the memory problem** for garbage collection. The GC must also keep track of another set: the set $V$ (for visited) of all cells that have been found to be accessible, so as to reclaim all the other cells at the end of the process. Discussing one and not the other makes limited sense, as they may have similar cost, use similar solutions, and even be combined.

The first thing to note is that all tracing GC follow the same abstract model, based on systematic exploration of the directed graph of cells in memory accessible from the program, where memory cells are vertices and pointers are the directed edges. It uses for that the following sets:

* the set $V$ (visited) of cells already found to be accessible by the **mutator**, i.e. the program or algorithm for which the GC is performed. The set $V$ is partitioned into two disjoint subsets: $V=U\cup T$;
* the set $U$ (untraced) of visited cells with pointers that have not been followed yet;
* the set $T$ (traced) of visited cells that had all their pointers traced.
* we also note $H$ the set of all cells in the heap, whether or not in use.

Only $V$ and $U$, or $U$ and $T$, need to be represented somehow for the algorithm to work.

The algorithm starts from some roots pointers that are known to the run-time system (usually pointers in stack allocated memory), and puts all the cells they point in the untraced set $U$ (hence in $V$ too).

Then the collector takes cells in $U$ one by one, and checks for each cell $c$ all its pointers. For each pointer, if the pointed cell is in $V$, then nothing is done, else the pointed cell is added to $U$, since its pointers have yet to be checked. When all its pointers have been processed, the cell $c$ is transferred from the untraced set $U$ to the traced set $T$.

The tracing terminates when $U$ is empty. This is bound to happen, since no cell goes through $U$ more than once. At that points, $V=T$, and all cells in $V$ are know to be accessible to the program, thus not reclaimable. The complement $H-V$ of $V$ in the heap determines what cells are unreachable by the mutator program and can be reclaimed by the collector for future allocation to the mutator.

Of couse, details vary depending on how sets are implemented, and on whether it is $V$ and $U$, or $U$ and $T$, which are effectively represented.

I also skip details about what is a cell, whether they come in one size or many, how we find pointers in them, how they may be compacted, and a host of other technical issues which you can find in books and surveys on garbage collection.

You may have notice that this is an extremely simple algorithm. **There is no recursion, but only a loop on the elements of the set $U$ that can grow as it is being processed**, until it eventually empties. *No a priori assumption about extra memory.* Whatever allows identifying the sets, and doing cheaply enough the needed operations will do. Note that the order in which cells are processed is irrelevant (no specific need for a pushdown stack), which gives a lot of freedom for choosing the means to represent the sets efficiently.

Where known implementations differ is in the way these sets are actually represented. Many techniques have been actually used:

* bit map: Some memory space is preserved for a map that has one bit for each memory cell, which can be found using the adress of the cell. The bit is on when the corresponding cell is in the set defined by the map. If only bit maps are used, you need only 2 bits per cell.
* alternatively, you may have space for a special tag bit (or 2) in each cell to mark it.
* list: you make a list of those cells that are in the set. You do not need a stack, or a specific data structure. In some system, astute pointer reversal technique allow building the list with very little extra memory, precisely $\log\_2 p$ bits where $p$ is the number of pointers per cell, this being further reduced by means of stacks of bits.
* you may test a predicate on the content of the cell, and its pointers.
* you may relocate the cell in a free part of memory intended for all an only the cells belonging to the set represented.
* one interesting special case is having the visited cell relocated in another contiguous area of memory (figuring the set $V$), and representing the set $T$ of traced cells by a single, but changing, boundary address that is greater than adresses of cells in $T$, and less than those in $U$.
* you may actually combine these techniques, even for a single set.

As said, all of the above have been used by some implemented garbage collector, strange as some may seem. It all depends on the various constraints of the implementation. And they can be rather cheap in memory usage, possibly helped by *processing order policies* that can be freely chosen for that purpose, since they do not matter for the end result.

What may seem the strangest one, transfering cells in a new area, is actually very common: it is called copy collection. It is mostly used with virtual memory.

Clearly there is no recursion, and the mutator algorithm stack does not have to be used.

Another important point is that **many modern GC are implemented for large virtual memories**. Then getting space to implement and extra list or stack is not an issue as new pages can be easily allocated. However, in large virtual memories, **the ennemy is not lack of space but lack of locality**. Then, the structure representing the sets, and their use, must be geared towards preserving the locality of data structure and of GC execution. The problem is not space but time. Inadequate implementations are more likely to show unacceptable slowdown than memory overflow.

I did not give references to the many specific algorithms, resulting from various combinations of these techniques, as this seems long enough.

# Answer
> 13 votes
Note that I am not a garbage collection expert. This answer only gives examples of techniques. I do not claim that it is a representative overview of garbage collection techniques.

An unscanned queue is a common choice. The queue can get large — potentially as large as the deepest data structure. The queue is typically stored explicitly, not on the stack of the garbage collection thread.

Once all but one of the children of a node have been scanned, the node can be removed from the unscanned queue. This is basically a tail call optimization. Garbage collectors can include heuristics to attempt to scan the deepest child of a node last; for example a GC for Lisp should scan the `car` of a `cons` before the `cdr`.

One way to avoid keeping an unscanned queue is to modify pointers in place, making the child temporarily point to the parent. This is a constant-memory tree traversal technique that's used in contexts other than garbage collectors. The downside of this technique is that while the GC is traversing a data structure, the data structure is invalid, so the GC has to stop the world. This isn't a deal breaker: many garbage collectors do include a phase that stops the world, in addition to phases that don't but can miss garbage as a result.

# Answer
> 4 votes
The standard way to avoid a stack overflow is to use an explicit stack (stored as a data structure in the heap). That works for these purposes too. Garbage collectors often have a worklist of items that need to be examined/traversed, which serves this role. For instance, your "Unscanned" queue is an example of exactly this sort of pattern. The queue can potentially get large, but it doesn't cause a stack overflow, because it is not stored in the stack segment. In any case it will never get larger than the number of live objects in the heap.

# Answer
> 4 votes
In "classic" descriptions of garbage collection (e.g., Mark Wilson, "Uniprocessor Garbage Collection Techniques", *Int'l Workshop on Memory Management*, 1992, (alternate link), or the description in Andrew Appel's *Modern Compiler Implementation* (Cambridge University Press, 1998)), collectors are classified as either "Mark and Sweep" or "Copying".

Mark and Sweep collectors avoid needing extra space by using pointer-reversal, as described in @Gilles's answer. Appel says that Knuth attributes the pointer-reversal algorithm to Peter Deutsch, and to Herbert Schorr and W.M. Waite.

Copying garbage collectors use what is often called *Cheyney's algorithm* to perform a queue traversal without needing extra space. This algorithm was introduced in C.J. Cheyney, "A Nonrecursive List Compacting Algorithm", *Comm. ACM*, 13(11):677-678, 1970.

In a copying garbage collector you have a chunk of memory that you are trying to collect, called the *from-space*, and a chunk of memory that you are using for the copies called the *to-space*. The to-space is organized as a queue with a `scan` pointer pointing to the oldest copied-but-unscanned record, and a `free` pointer pointing to the next free position in to-space. The picture of this from Wilson's paper is:

As you scan each item in to-space you copy its children from from-space to the `free` pointer in to-space, and then change the pointer to the child from from-space to the new copy of the child in to-space. There's an extra trick you need to use when your data structures aren't trees (when a child can have more than one parent). In that case, when you copy a child from from-space to to-space you need to overwrite the old version of the child with a *forwarding pointer* to the new copy of the child. Then if you ever scan another pointer to the old version of the child you realize that it has already been copied, and don't copy again.

---
Tags: programming-languages, memory-management, garbage-collection
---


# Question
Title: NDTM for Graph Clique Problem in poly-time
I am having a doubt. This is my NDTM algorithm:

GCP(G, k):

* generate a list with k distinct nodes from graph G
* generate an adjacency matrix, fill it with 1 if an edge exist, 0 otherwise
* check if every row has only 1-s, hence return *Yes*, otherwise *No*

Does this run in poly-time? I guess so since in my idea building a matrix takes $n^2$ time.

Is there any flaw in this?

# Answer
You are using *generate* for two different actions, your second bullet is not explained correctly, and your third bullet always fails. Here is a better version of your algorithm:

* Non-deterministically generate a list of $k$ distinct nodes of $G$: $v\_1,\ldots,v\_k$.
* Calculate the $k\times k$ matrix $B$ given by $B(i,j) = A(v\_i,v\_j)$, where $A$ is the adjacency matrix of $G$.
* Return *Yes* if all off-diagonal entries of $B$ are 1. Otherwise return *No*.

What is the running time of the algorithm? This depends on your exact model of computation. However, choosing $k$ nodes takes polynomial time, calculating the $k\times k$ matrix takes polynomial time, and checking all its off-diagonal entries takes polynomial time. So in total, the algorithm runs in polynomial time.

Why do we need the matrix $B$? We don't. We could simplify the pseudocode:

* Non-deterministically generate a list of $k$ distinct nodes of $G$: $v\_1,\ldots,v\_k$.
* If $A(v\_i,v\_j) = 1$ for all $1 \leq i \< j \leq k$ then return *Yes*, otherwise return *No*.

Now for a more interesting question. How much *space* does your algorithm take? It takes space $\Theta(k\log n)$ (since you need $\log n$ bits to store each index), and so in the worst case, $\Theta(n\log n)$. Can you do better? Say, can you do the verification in $O(\log n)$ space? If you could, then you would have shown that clique is in NL. Since NL is in P, this would imply that P=NP (since clique is NP-complete), which is considered unlikely. So you probably need more than $\omega(\log n)$ space. But how much more?
> 3 votes

---
Tags: turing-machines, nondeterminism, clique
---


# Question
Title: Confusing example of a language which may be Context-free or not context-free
Hi so consider the language $L= \\{(0^i)(1^j)\mid i=k\*j \text{ for some positive }k\\}$ Could I not rewrite this as $\\{((0^k)^j)(b^j)\mid k\>1\\}$. Seeing it in this form makes me think of a form $a^n b^n$ which we know is context free so therefore it should be context free. Is my logic wrong and if not what would be the best way to show it's context free.

# Answer
The best way to show that a language is context-free is to use one of the equivalent definitions of context-free languages. The two most popular ones are:

* A language is context-free if it is generated by a context-free grammar.
* A language is context-free if it is accepted by a (non-deterministic) push-down automaton.

The language $\\{ a^n b^n : n \geq 0 \\}$ is generated by the grammar $S \to aSb | \epsilon$. Let's try to use the same idea for your language: $S \to 0^k S 1 | \epsilon$ (we can implement $0^k$ using context-free rules). The problem is that we can't guarantee that the same $k$ is used in all productions. This leads me to conjecture that the language is *not* context-free.

How do we show that a language is not context-free? The most popular way is to use the pumping lemma or one of its variants, though this method doesn't always work. Perhaps you should give it a try.
> 1 votes

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


# Question
Title: Creating a FSA using 3 input codes and a parity check digit
Need help understanding the overall idea behind this scenario, I've got 3 input codes namely: A (0100) B (0010) and C (0001) and i'm supposed to have a odd parity of 0's. I've started making a machine that accepts A however i'm not sure how to incorporate the other letters as well. Been stuck on this for a few days now, any help would be greatly appreciated!

# Answer
> 2 votes
A cheap way to do it is the following:

You build an automaton R that recognizes the language $\\{x^{2n}0 \mid n\geq 0\\}\cup \\{x^{2n+1}1 \mid n\geq 0\\}$.

and an automaton R' which accepts only the three strings, and has a single final state.

Then you replace every $x$-transition from $q$ to $q'$ in R by a copy of the automaton R', merging $q$ with the initial state of the copy of R' and $q'$ with its final state.

You should have 2 $x$-transitions only, hence 2 copies of R' to replace them with.

Can you explain why this works.

# Answer
> 1 votes
Let's start with a regular expression for your language: $$ ((0100+0010+0001)(0100+0010+0001))^\*0 +\\ ((0100+0010+0001)(0100+0010+0001))^\*(0100+0010+0001)1. $$

The easiest way of approaching the construction of the FSA is probably presenting your language as the intersection of two simpler ones: $(0100+0010+0001)^\*(0+1)$ and the language of words having an odd number of 0s. As a first step, construct FSAs for both languages. Then, use the product construction to construct an FSA for their intersection. You might notice a possible shortcut.

---
Tags: finite-automata
---


title: Evaluating Grover's algorithm on 3-SAT

text:
# Question
Title: Evaluating Grover's algorithm on 3-SAT
I recently asked this very similar question on how Grovers algorithm must be modified in order to solve 3-SAT and learned that it actually needs no modification at all.

However, what I still don't get is how to determine whether a satisfying variable assignment was found after having applied Grover's algorithm. The final step (as described in wikipedia) is to measure $λ\_ω$ which in the case of solving 3-SAT would give me an assignment for the variables of my formula. Do I need to check manually whether this assignment is indeed a satisfying assignment? Or is there any better way to find out whether there exists at least one match?

# Answer
"Measuring", in quantum computation, is the act reading the quantum state along some basis. This will cause the the quantum state to collapse. The quantum state after grovers algorithm is such that it collapses with very high probability to the desired result (in this case an assignment). Perhaps you *should* check the result because it might just be a bad case, that is just unlikely, but you don't *have* to check the result to get the output of grovers algorithm. You just have to measure it. To determine with high probability weather or not the formula was SAT you should check the assignment that it gave out.
> 3 votes

---
Tags: quantum-computing, 3-sat
---


# Question
Title: Worst case of based on comparison sorting algorithm
> Explain by reference to the structure of a decision tree why any sorting algorithm based on comparisons cannot in its worst case use fewer comparison than a number proportional to nlog(n).

Any ideas how I can prove this?

# Answer
> 3 votes
This is very, very classical. Here is the idea. You can describe a run of your algorithm as a decision tree. At each node there is a comparison operation performed by your algorithm, and the three children correspond to the three different answers. Every execution of your algorithm ends at a leaf. Since at the end the list is sorted, in particular we can tell what the original order of the list was. So we can annotate each leaf by a permutation on $n$ elements. Since there are $n!$ different permutations, there must be at least $n!$ leaves, so the tree must have height at least $\Omega(\log\_3 n!) = \Omega(n\log n)$. This means that there is some computation path that will result in $\Omega(n\log n)$ comparisons.

If you're not happy with this argument, the web has many, many different versions of the same proof, which you can find using your web searching skills.

---
Tags: time-complexity
---


# Question
Title: Context-sensitive grammars for $a^ib^jc^{ij}$ and $a^ib^jc^{i^j}$
I would like to get some help for finding the **context-sensitive** grammar for the language:

$$L\_1=\\{a^ib^jc^{ij} \mid i,j\geq 0\\}.$$

To answer the question before it's written here, yes I've tried to construct it myself, but my attempts are far from promising, so I don't include them, because there is no point (also I've tried to find a similar question - without luck).

Additionally, although I'm familiar with the one question per post rule, I'm adding another language here:

$$L\_2=\\{a^ib^jc^{i^j} \mid i,j\geq 0\\}.$$

(The reason is that I think these two have a similar solution — of course if I'm mistaken, I will erase it.)

Please include the thought process as I've just started learning grammars. Any hint appreciated.

# Answer
Designing context-sensitive grammars (with productions $\alpha X \gamma \to \alpha \beta \gamma$ with $\beta \neq \varepsilon$) is no fun at all. It is slightly more convenient to construct monotone grammars (with productions $\alpha \to \beta$ with $|\alpha| \le |\beta|$). There is a standard construction from one to the other.

But even then it is full of tiny details that have to be observed.

It is relatively easy to construct a grammar for $\\{ La^ib^jc^{ij} \mid i,j\ge 0 \\}$. First generate strings of the form $LB^jA^i$, just like in a context-free grammar. Add the rule $BA \to ABC$, so that if every $A$ moves over every $B$ we generate $ij$ $C$'s. But now we have $C$'s in between. Let $B$'s move over $C$'s whenever needed.

Then we have to rewrite $A,B,C$ into $a,b,c$ respectively *provided* they are in the right order. This can be done using the boundary symbol $L$ and the productions $LA \to La$, $aA \to aa$, $aB\to ab$ etcetera. Like a finite state automaton that accepts $a^\*b^\*c^\*$.

Now what about the $L$? We used it to mark the start of the string. According to the rules of monotone grammars it cannot be deleted. Well, let the $L$ double as one of the $a$'s. But then we should carefully match the $c$;s with the new design. Thus start by generating the context-free language $aB^jA^iC^j$.

Done? not yet. We now always have at least one $a$, i.e., $i\>0$. Add these special cases.

Problem with the construction is its correctness. Productions can be applied in any order, not only the one order you have considered during its construction.
> 4 votes

---
Tags: formal-grammars, context-sensitive
---


# Question
Title: Reduction of Circuit Satisfiability to CNFSAT
CNFSAT is Karp reducible to Circuit-SAT by replacing all the conjunctions with AND gate, disjunctions with OR gate and negations with NOT gate. However, if we apply the same approach to Karp reduce Circuit-SAT to CNFSAT, it may result in an exponential algorithm but the instance map should be done in polynomial time.

**How should we approach it then?**

# Answer
The exponential blowup when converting circuits to conjunctive normal form is avoided by introducing new variables to represent the output of each sub-circuit plus a simple set of rules represent each sub-circuit and force their output into the variables (see Tseitin transformation). The size of the resulting CNF formula is linear to the size of the circuit, and grows linearly as the circuit size is increased.
> 2 votes

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


# Question
Title: Turing Machines and Algorithm for Language Acceptance
Is there an algorithm to decide if any two Turing machines accept the same language? I can't find a definite answer to this. My guess is that there isn't, because then we would be able to decide if a Turing machine accepts a given language and halts, which is undecidable. Is there a better explanation for why this is or is not the case?

# Answer
> 2 votes
Your guess is correct: deciding whether two Turing machines are equivalent (i.e. accept the same language) is an undedicable problem.

To prove this, it should be possible to reduce this problem to the halting problem.

You can also use Rice's theorem.

The theorem states the following:

> Let P be any non-trivial property of languages of Turing machines. Then, the following language is undecidable, $LP=\\{\langle M\rangle : L(M) \text{ satisfies } P\\}$.

Note that $L \text{ satisfies } P$ means $L \in P$.

Note also that a “trivial property” is a property that is either satisfied by all languages, or a property that is not satisfied by any language.

Now, if you consider two machines $M\_1$ and $M\_2$, deciding whether $L(M\_1) = L(M\_2)$ is deciding whether $M\_2 \in \\{\langle M \rangle : L(M) \text{ satisfies } \\{L(M\_1)\\}\\}$.

Since $\\{L(M\_1)\\}$ is non trivial (there exist machines which recognize it and there exist machines which do not recognize it), this problem is undecidable.

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


# Question
Title: How to choose between several constraints for a SAT task using quality metric?
I'm trying to solve a constraint programming problem using a SAT solver. I have set of constraints in the form of propositional logic statements, which are converted to CNF using Tseitin transformation. A number of inputs are fixed and pretty large - up to ~30k. A number of constraints can be ~200k.

Right now, I have to choose between several constraint candidates which will be added to the CNF formula. All of them have some `quality` parameter - basically, a candidate should not remove too many feasible solutions from a search space. I can choose between smaller rules (a few boolean operators like AND, OR and no more than 10 inputs), but it is just impossible for the larger constraints (dozens of operators and ~100 inputs), there is no way to predict the quality of solution in that case. So, I ended up with the idea of a tool, which will automatically choose the best option for me.

For example, I have the basic rule: $$\neg(A \wedge B \wedge(C \vee D \vee E))1)$$ For this rules, I have two corresponding additional rules and I have to choose one of them: $$\neg(A \wedge B) \wedge blah2)$$ $$\neg (C \vee D \vee E) \wedge blah3)$$ The `(2)` formula is the best for me - it removes lesser number of solutions. `blah` is not relevant to my question, but it always appears inside candidates.

What I have tried already:

1. Use Espresso logic minimization tool. I input all candidates at ones and hope to get the minimal representation. It kind of works, but the tool ignores a `quality` metric - the result is too constraining for my problem. Too many possible solutions are prohibited. In addition, my problem is far too big for Espresso and I have to use it in incremental manner. I assume that is an issue too - Espresso does not see the whole picture at ones.
2. # SAT solvers or model counting. The idea is the following - estimate a number of possible solutions under some basic constraints. I can add one of the candidates, estimate a number of possible solutions again, remove it and run such a procedure for each candidate. Eventually, I can choose one with the largest number of legal solutions. It seems to be working, however, it is too slow with real cases - exact counter freezes forever, approximate counter concludes that there are infinite number of solutions.

I would like to brainstorm that problem - maybe someone can propose interesting formulation/approaches for this task? May it can be formulated as ILP task somehow?

UPDATE: I am given a geometry problem - i have a rectangular tile that should be filled with a set of various objects. Some configurations of objects are prohibited (it does not matter why). Each rule is populated in every applicable point of a tile: $$\psi = \neg (A\_1 \wedge B\_1 \wedge C\_1) \wedge \neg (A\_2 \wedge B\_2 \wedge C\_2)$$

Blue bold lines are tile's borders. Such configuration of objects is prohibited: $$ \neg (A \wedge B \wedge C) 4)$$ This fact is represented as a set of clauses. $\psi$ forms a SAT task. You can think of it like "SAT, find me a tile which does not have any of these prohibited configurations". And this is my `core` formula. The same rule in different points of tile forms an identical set of clauses, but over different variables, e.g. $A\_1, B\_1, C\_1$ and $A\_2, B\_2, C\_2$ in the formula above - one rule forbids a set of 3 objects in 2 different points.

At the same time, such rules can be partially outside a tile (pay attention to the right side border). The object outside is transparent:

This is prohibited too. The issue is that SAT solver does not know anything about world outside a tile, there is literally nothing out there. However, I still need to capture such configurations. I take each core rule and split it with boundary: $$\neg(A \wedge boundary) 5)$$ $$\neg(A \wedge C \wedge boundary) 6)$$

Over the whole tile it looks like this:

If we choose 5) rule, we will prohibit all obects $A$ near the boundary: $$\psi = \neg (A\_1 \wedge boundary) \wedge \neg (A\_2 \wedge boundary) \wedge \neg (A\_3 \wedge boundary) \wedge \neg (A\_4 \wedge boundary)$$

However, we can choose 6) rule: $$\psi = \neg (A\_1 \wedge A\_2 \wedge boundary) \wedge \neg (A\_2 \wedge A\_3 \wedge boundary) \wedge \neg (A\_3 \wedge A\_4 \wedge boundary)$$ This option is much better - it prohibits 2) rule near the boundary already and at the same time it allows to place single $A$ object near the boundary.

My questions:

1. How can I choose between various candidates?
2. Which tools can me help? #SAT, MaxSAT, MIP?
3. Which metric can I use to optimise a set of rules?

# Answer
It appears that your problem is the following:

Input: boolean formulas $\Phi,\Psi\_1,\dots,\Psi\_k$
Output: a set $S \subseteq \\{1,\dots,k\\}$ whose size is as large as possible, such that $\Phi \land \land\_{i \in S} \Psi\_i$ is satisfiable

This problem can be formulated as an instance of MAX-SAT, specifically PMAX-SAT, and then solved using a MAX-SAT solver.

In particular, introduce boolean variables $t\_1,\dots,t\_k$. Define the formula $\Gamma$ to be the result of converting

$$\Phi \land \bigwedge\_i (t\_i \implies \Psi\_i)$$

to CNF form. Now create the conjunction $\Gamma \land t\_1 \land \dots \land t\_k$, and ask the solver to choose a subset of the clauses $t\_1 \land \dots \land t\_k$ that makes conjunction satisfiable. (You mark the clauses of $\Gamma$ as required and ask it to find a subset of the remaining clauses.) This is an instance of MAX-SAT; and its solution corresponds to a solution to the original problem.

Alternatively, you can express it as an instance of weighted MAX-SAT. As before, use the conjunction $\Gamma \land t\_1 \land \dots \land t\_k$, but now give every clause in $\Gamma$ some large weight $W$ (chosen so that effectively, $\Gamma$ is forced to be satisfied) and each clause $t\_i$ weight 1. This is an instance of weighted MAX-SAT; and its solution corresponds to a solution to the original problem.

---

I'm not sure why your #SAT solver was returning "infinity". Maybe you need to find a better solver for #SAT. Actually, approximate-#SAT would be good enough for your needs. See e.g. Is there a sometimes-efficient algorithm to solve #SAT? and Using SMT solvers to generate random solutions to given predicate for some relevant literature and techniques.
> 2 votes

---
Tags: optimization, satisfiability, discrete-mathematics
---


# Question
Title: Maximize distance between k nodes in a graph
I have an undirected unweighted graph $G$ and I want to select $k$ nodes from $G$ such that they are pairwise as far as possible from each other, in terms of geodesic distance. In other words they have to be spread around the graph as possible.

Let $d(u,v)$ be the length of a shortest path between $u$ and $v$ in $G$. Now, for a set of vertices $X \subseteq V(G)$, define $$d(X) = \sum\_{\\{u,v\\} \subseteq X}d(u,v).$$

Let the problem SCATTERED SET be the problem which on input $G,k$ asks to find a set of $k$ vertices $X$ maximizing $d(X)$.

> Is there an efficient algorithm solving SCATTERED SET?

# Answer
I don't know if there is a polynomial-time algorithm (it feels like it might be NP-hard), but here are some plausible algorithmic approaches you might could consider, if you need to solve it in practice:

## Heuristics

One well-explored algorithm is Furthest Point First (FPF). At each iteration, it chooses a point that is furthest from the set of points selected so far. Iterate $k$ times. As this is a greedy strategy, there is no reason to expect this to give an optimal answer or even close to optimal, and it was designed to optimize a slightly different objective function... but in some contexts it gives a reasonable approximation, so it could be worth a try.

FPF comes out of the literature on graph-based clustering and was introduced in the following research paper:

Teofilo F. Gonzalez. Clustering to minimize the maximum intercluster distance. Theoretical Computer Science, vol 38, pp.293-306, 1985.

You could try exploring the literature on graph-based clustering to see if anyone has studied your specific problem.

## Exact algorithms

If you have this problem in practice and need an exact optimum solution, you could try to solve this using an ILP solver.

Here's how. Introduce 0-or-1 variables $x\_i$, where $x\_i$ indicates whether the $i$th vertex was selected, and 0-or-1 variables $y\_{i,j}$, with the intended meaning that $y\_{i,j}=1$ only if $x\_i=1$ and $x\_j=1$. Now maximize the objective function $\sum\_{i,j} d(i,j) y\_{i,j}$, subject to the constraints $\sum x\_i \le k$ and $x\_i \ge y\_{i,j}$ and $x\_j \ge y\_{i,j}$. Now solve this ILP with an off-the-shelf ILP solver. As ILP is NP-hard, there's no guarantee this will be efficient, but it might work on some problem instances.

Another approach is to use weighted MAX-SAT. In particular, introduce boolean variables $x\_i$, where $x\_i$ is true if the $i$th vertex was selected, and variables $y\_{i,j}$. The formula is $\phi \land \land\_{i,j} y\_{i,j}$, where $\phi$ must be true (its clauses have weight $W$ for some very large $W$) and each clause $y\_{i,j}$ is given weight $d(i,j)$. Define the formula $\phi$ to be true if at most $k$ of the $x\_i$'s are true (see here for details on how to do that) and if $y\_{i,j}=x\_i \land x\_j$ for all $i,j$. Now the solution to this weighted MAX-SAT problem is the solution to the original problem, so you could try throwing a weighted MAX-SAT solver at the problem. The same caveats apply.
> 4 votes

# Answer
No, the problem is NP-complete.

Let $(G,k)$ be an instance of INDEPENDENT SET. Construct $G'$ by adding a universal vertex $u$ to $G$. The crucial observation is that the distance between two vertices in $G$ is 1 in $G'$ if and only if they are adjacent in $G$, and 2 otherwise.

Now, the optimal solution of SCATTERED SET on input $(G',k)$ is $2\binom{k}{2}$ if and only if $G$ has an independent set of size $k$.
> 8 votes

---
Tags: algorithms, graphs
---


# Question
Title: Proof of SAT is randomly reducible to UNIQUE-SAT
I am asking for help to explain some crucial points of the central lemma and it's proof of famous paper NP is as easy as detecting unique solutions by L.Valiant and V.Vazirani.

The proof can be found in the section **2. The proof** of the paper.

**The idea of the lemma**: lemma shows that there is a randomized polynomial - time reduction from SAT to Unique-SAT. Lemma uses GF\[2\] inner product with polynomial few {0,1} vectors.

**Problem in general**: I have some difficulties in understanding the definition of the lemma and in usage of GF\[2\] for proving the lemma.

**Specific questions:**

Following is the number of citations from the paper with relevant question to the citation.

> **Lemma 2.1.** If $f$ is any CNF formula in $x\_1,...,x\_n$ and $w\_1,...,w\_k \in \\{0,1\\}^n$,

Q:I think $x\_1,...,x\_n$ are literals, but what are $w\_1,..,w\_k$? Are they literals or something else? If yes, why to distinct between them and $x$ literals.

A:$w\_1,..,w\_k$ are the truth assignments.

> then one can construct in linear time a formula $f'\_k$ whose solution $v$ satisfy $f$ and the equations $v\cdot w\_1=...=v\cdot w\_k=0$. Furthermore, one can construt a polynomial-size CNF formula $f\_k$ in variables $x\_1,...,x\_n,y\_1,...y\_m$,

Q: $x\_1,...x\_n$ are unknown literals, how can we construct $f\_k$ with unknown literals and where $y\_1,...,y\_m$ came from?

> for some $m$ such that there is a bijection between solutions of $f\_k$ and $f'\_k$, defined be equality on the $x\_1,...,x\_n$ values.
>
> **Proof**: It is sufficient to show the lemma for $k=1$. Then, $f'\_k$ is
>
> $f \wedge (x\_{i\_1} \bigoplus x\_{i\_2} \bigoplus ... \bigoplus x\_{i\_j} \bigoplus 1)$

Q: this is the most vague point, how do we come to the such construction of $f'\_1$ and why showing only $f'\_1$ sufficient for the proof.

I hope you forgive me for my naivety. I will appreciate any hint in accordance to the above questions.

# Answer
> Q: $x\_1,...x\_n$ are unknown literals, how can we construct $f\_k$ with unknown literals and where $y\_1,...,y\_m$ came from?

$x\_1, \ldots, x\_n$ are *variables*, each of which can appear as a positive literal ($x\_i$) or a negative one ($\lnot x\_i$). To construct an equivalent formula $f\_1$ of another formula $f\_1'$, you don't have to know the values (truth assignments) of $f\_1'$. (A simple example is $x\_1 \to x\_2 \Leftrightarrow \lnot x\_1 \lor x\_2$.)

The variables $y\_1, \ldots, y\_m$ are unimportant (at least in this Lemma). The Lemma define the "equivalence" of the two formulas $f\_1$ and $f\_1'$ by equality on the $x\_i$ values (leaving $y\_i$ values unspecified).

---

> Q: How do we come to the such construction of $f'\_1$ and why showing only $f'\_1$ sufficient for the proof?

Each $f\_i$ (and $f\_i'$) is independent and similar. Therefore, the case of $f\_1'$ is sufficient for the proof. To justify the construction of $f\_1' = f \land (x\_{i\_1} \oplus x\_{i\_2} \oplus \cdots \oplus x\_{i\_j} \oplus 1)$, you should prove the following two points:

* Each solution $v$ to $f\_1'$ satisfies $f$.

This is trivial by the definition of $f\_1'$.

* Each solution $v$ satisfies the equation $v \cdot w\_1 = 0$.

This is the tricky part. We argue as follows:

First, $$v \cdot w\_1 = x\_{i\_1} + x\_{i\_2} + \cdots + x\_{i\_j} \text{ (here \`+\` is over GF\[2\])} = x\_{i\_1} \oplus x\_{i\_2} \oplus \cdots \oplus x\_{i\_j}$$ The first equality follows from the fact that other $w\_l$ with indices $l \neq i\_1, i\_2, \cdots, i\_j$ are all 0 (according to the definition of all $x\_{i\_j}$).

Because $v$ is a solution to $f\_1'$, we have $$x\_{i\_1} \oplus x\_{i\_2} \oplus \cdots \oplus x\_{i\_j} \oplus 1 = 1$$ Thus, $$v \cdot w\_1 = x\_{i\_1} \oplus x\_{i\_2} \oplus \cdots \oplus x\_{i\_j} = 0$$
> 4 votes

---
Tags: complexity-theory, reductions, proof-techniques
---


# Question
Title: Which bound is better, a logarithmic or a polynomial with arbitrarily small degree?
I have a randomized approximation algorithm which can be tuned by selecting the randomization probabilities. I found out that:

* For any $\epsilon \>0$, there are probabilities for which the approximation factor is $O(n^\epsilon)$.
* There are probabilities for which the approximation factor is $O(\ln n)$ (smaller factor is better).

I know that $O(\ln n)$ is asymptotic smallerer than any $O(n^\epsilon)$ when $\epsilon$ is fixed, but here $\epsilon$ can be made arbitrarily small, so I don't know, which of these two bounds is considered better? Specifically:

A. Theoretically, which of these two bounds should I report in a paper? Is the bound $O(n^\epsilon)$ interesting, or is it considered useless given the logarithmic bound?

B. Practically, if I have to run the algorithm on very-big-data, with no possibility of making tests in advance, which tuning is better?

(Just to get some feeling, I compared $n^{0.1}$ with $\ln n$. It turns out that $n^{0.1}$ is better even for very large $n$ - they become equal at about $n=4 \cdot 10^{15}$)

# Answer
> 4 votes
Since $\log n = O(n^{\epsilon})$ for an $\epsilon \> 0$, if you can prove an approximation ratio of $O(\log n)$, then approximation ratios of $O(n^{\epsilon})$ (for any $\epsilon \> 0$) immediately follow. You should always prove the best approximation ratio that you can, unless:

* The best approximation ratio holds only in expectation, and some other approximation ratio holds with high probability.
* You have several incomparable approximation ratios (this is more common in expressions involving more than one parameter).

That is, your worse guarantee needs to have *some* advantage over your better guarantee for you to report both.

Regarding practical performance, you are highlighting the fact that asymptotic performance can be misleading when it comes to evaluating algorithms in practice. The most well-known instance is probably "fast" matrix multiplication, which is usually slower than the trivial algorithm. Here you have two options:

* Prove non-asymptotic guarantees on the approximation ratio, say $100\log n$ and $(2/\epsilon)n^{\epsilon}$. This allows you to obtain concrete guarantees for every $n$.
* Do experiments. The experiments reveal the actual approximation ratio on the average. If you can fit your results to a nice function, you can say that empirically, the average approximation ratio is (say) $10\log n$, though in the worst case all you know is (say) $100\log n$. Experiments, however, are not so welcome in theoretical papers, unfortunately.

---
Tags: algorithm-analysis, asymptotics, approximation
---


# Question
Title: If an NP problem reduces to an NPC problem, it is NPC?
Is the following statement true?

> If a problem P1 is in NP and polynomial time reducible to P2, where P2 is NP-complete, then P1 is also NP-complete.

Intuitively I think the answer is No because I need to prove that it is NP-hard as well for P1 to be NP-complete. But I cannot get the exact proof.

# Answer
> 0 votes
Hint: *Every* problem in NP is reducible to $P\_2$. In particular, if $P\_1$ is in NP but not NP-complete then it reduces to $P\_2$ without being NP-complete. So the question is:

> Are there problems in NP which are not NP-complete?

Perhaps you can answer this question somehow. Try to think of the simplest possible problems.

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


# Question
Title: Optimize binary search on Segment Tree by storing past result
## Goal

Let $A\[n\]$ be an arbitrary array of integers of length $n$. Let $S$ be a segment tree, represented by an array of records: each record containing the left and right bounds ($\[l,r\]$) of the segment the node covers, and a "sum" value equal to $\sum\_{k=l}^rA\_k$. I would like to perform a Weighted Random Selection on $A$, and because $S$ is a balanced binary tree, I can perform a binary search by traversing $S$ and do WRS in $\Theta(\lg n)$ time. In this case, the domain of my random variable $r$ is $\[0,\sum\_{k=1}^nA\_k\]$.

Now, suppose I delete the element $A\_d,d\in\[1,n\]$, but because reconstructing $S$ takes $\mathcal{O}(n\lg n)$ time, I choose to let $S$ remain unmodified.

To perform WRS in this case, I am thinking that instead of starting from the first element of $A$, I can start from the $(d+1)$st element, tighten the domain of $r$ to $\[0,(\sum\_{k=1}^nA\_k)-A\_d\]$ ($A$ here refers to the array *before* deletion, since the original values are stored in the "sum" values of the leaf nodes of $S$), and wrap back around to the start if I reach the end of $A$ while searching. The trouble is that the nice property of $\Theta(1)$ time needed at each iteration of the binary search (thanks to the balanced binary tree property of $S$) is no longer true. Now, each iteration of the binary search takes $\mathcal{O}(\lg n)$ time (summation over arbitrary segment in $S$), and since the binary search is $\Theta(\lg n)$, WRS done this way takes $\mathcal{O}(\lg^2 n)$ time.

*Is it possible to perform WRS on $S$ in $\mathcal{O}(\lg n)$ time while omitting $A\_d$?*

---

## Attempt at a solution

An easy way to make this operation faster is storing the cumulative sum calculated from the last iteration of binary search, and only calculate the ranged sum from the last midpoint to the current midpoint. This halves the size of the segment to be calculated at each iteration. However, this still appears to be in $\mathcal{O}(\lg^2 n)$ time. Halving the size of the segment at each iteration means $\lg(n)+\lg(\frac{n}{2})+\lg(\frac{n}{4})+...+1=\mathcal{O}(\lg \frac{n^{\lg(n)}}{2^{\lg(n)}})=\mathcal{O}(\lg^2 n)$ array accesses.

# Answer
There turns out to be a very simple way to do this in $\mathcal{O}(\lg n)$:

1. Restrict the domain of $r$ to $\[0,(\sum\_{k=1}^nA\_k)-A\_d\]$
2. If $r≥\sum\_{k=1}^{d-1}A\_k$, add $A\_d$ to $r$.
3. Search using the original method.

Finding $\sum\_{k=1}^{d-1}A\_k$ is $\mathcal{O}(\lg n)$ time, finding $A\_d$ from $S$ is $\Theta(\lg n)$ time, and the binary search is $\Theta(\lg n)$ time.
> 2 votes

---
Tags: algorithms, data-structures, binary-trees, binary-search
---


# Question
Title: Efficient algorithms for finding the limit of a sub-sequence
Given a sequence $A\_N={a\_1,a\_2,a\_3...,a\_N}$ of real numbers, and given that there exist some sub-sequence which generated from some deterministic converging sequence.

Are there any efficient algorithms for finding the limit of the converging sub-sequence?

# Answer
> 1 votes
This answer is for a different version of the question; doubtless there will be other versions in the future. The version of the question this answer is targeted at had an infinite sequence $(a\_i)$ of real numbers and a real number $L$ which is a *known* accumulation point of the sequence.

It really depends on your notion of computation, as Raphael comments, but the following idea is probably your best bet:

1. Identify a member $a\_{i\_0}$ within distance $1$ of $L$.
2. Identify a member $a\_{i\_1}$ within distance $1/2$ of $L$, where $i\_1 \> i\_0$.
3. Identify a member $a\_{i\_2}$ within distance $1/4$ of $L$, where $i\_2 \> i\_1$.
4. And so on.

---
Tags: complexity-theory, computability, real-numbers
---


# Question
Title: Switching Lemma and AC0 reductions between SAT problems
Have there been efforts to show (using the Switching Lemma), for example, that SAT or 3SAT cannot have an AC$^0$ reduction to 2SAT? What are the issues or difficulties involved?

SAT and 3SAT are complete for **NP**, and 2SAT is complete for **NL** under AC$^0$ reductions. Hence such a proof would separate **NP** from **NL**.

In the case of a 3SAT to 2SAT reduction in AC$^0$, the bottom fan-in is bounded by 3 (at least prior to the first switching).

# Answer
It is hard to see how you would use the fact that the target of the reduction is 2SAT rather than, for example, 3SAT.

The common way one applies the switching lemma is roughly this. Apply a random restriction that fixes all but a $\lambda$ fraction of the inputs, for some small parameter $\lambda$ which depends on the parameters (size and depth) of the AC0 circuits in question. Then with constant probability, the function computed by the AC0 circuit becomes constant.

Applying this in our case, we have fixed all but $\lambda n$ of the inputs, and in return, some $\mu$ fraction of the outputs is fixed. And now what? We don't know anything about the reduction, so it's not clear how to obtain a contradiction. What's more, I don't see how you would use the fact that the target problem is 2SAT rather than, say, 3SAT, in which case there can be no contradiction.

The switching lemma is at its best when you have a concrete function in mind and you want to prove AC0 lower bounds for this specific function. Another, less typical, use of the switching lemma is to prove some general properties of *any* function computed by an AC0 circuit. The most famous example is Linial–Mansour–Nisan, which gives bounds on the rate of decay of the Fourier spectrum. It's not clear how you'd use information like this in your case.
> 8 votes

# Answer
some other angle/ pov on your question not taking it narrowly/ literally. a switching lemma-like construction has "coincidentally" been found to be at the heart of a celebrated/ very advanced proof in complexity theory showing an exponential lower bound required for a SAT-like problem in monotone circuits, initially discovered by Razborov, who won the Nevanlinna prize for this years ago. however his initial proof was not understood to be in that form and it took many years of reanalysis over multiple papers to bring out that connection. this effort is summarized in this paper: Monotone Complexity by Switching Lemma / Harnik, Raz. as cited in their paper its connected to a reformulation by Berg and Ulfberg \[BeUl97\].

so the switching lemma and reformulations of it continues to be an active area of research and a basic "device" in separating complexity classes, and therefore it probably would not be advisable to completely rule out its use in future (important? / significant?) separation results. also your question touches on P vs L which is open also and is thought by many to be possibly as hard as P vs NP (both questions have been open almost the same amount of time, roughly ~4½ decades). however, some limitations of the technique can be seen in the natural proofs barrier identified by Razborov/ Rudich.

as for 3SAT vs 2SAT as you inquire in your question, of course 2SAT is in P and 3SAT is NP complete, so any significant "reduction" would necessarily likely also relate P vs NP. wrt your NP vs NL idea, there are other active areas of research touching on the P vs NL question eg this recent analysis by Wehar, Hardness results for Intersection Non Emptiness

as for AC0 reductions and its implications for (open) complexity class separations, there are some connections noted in this recent breakthrough result, An average-case depth hierarchy theorem for Boolean circuits / Rossman, Servedio, Tan (eg p5)

> **Meyer's Question:** Is there a relativized world within which the polynomial hierarchy is infinite?
>
> ... to answer Meyer’s question in the affirmative, it suffices to exhibit, for every constant d ∈ $\mathbb{N}$, a Boolean function Fd computable by a depth-d AC0 circuit such that any depth-(d − 1) circuit computing Fd requires super-quasipolynomial size.
> 2 votes

---
Tags: complexity-theory, satisfiability
---


# Question
Title: Memory access on byte/word addressable memory
I'm doing a question on architecture and I've come across this question which I do not understand how to answer the question.

Q. How many bits are required to address 4G x 32-bit main memory if

a) Main memory is word addressable b) Main memory is byte addressable

I have read this question Word- or byte-addressable? Correct terminology but it did not clear up my understanding of the question as I am NOT asking what is the difference between byte and word addressable, more specifically I want to understand this question I've written.

The answer given says we need 34 bits for byte addressable memory and 32 bits for word addressable memory. I have thought about this for a while and have come to this conclusion which I do not know if it is correct or not:

Each row in the main memory is 32 bits in width and if it is byte addressable then we have 4 bytes in each row. To select a byte from the row requires log2(4) = 2 bits. Row width + 2 = 34 bits? Similiar concept for 32 bits. Is this correct logic?

# Answer
> 0 votes
The error in your solution comes where you say "Row width + 2?" To select a byte in memory, you must (a) select a row, and (b) select a column.

Let's see how this works out for the byte-addressable case. As you say, selecting a column takes 2 bits, since there are 4 columns. However, the number of bits to select a row is log2(number of rows), not the row width \[the row width is irrelevant\]. So, figure out how many rows there are, then take the binary logarithm of that, and add 2 to it -- you'll get the correct number of bits needed to address byte-addressable memory.

The same methodology can be applied for the word-addressable case. Just count the number of bits needed to select a row, and the number of bits needed to select a column.

# Answer
> 1 votes
The question is probably about address bits, not data bits.

A 4G x 32bits memory size is 16Gbytes.

* With a 8bits data bus, you need 34 address bits (typically A\[33:0\])
* With a 32bits data bus, you need 32 address bits (typically A\[33:2\]. A\[1:0\] is for selecting individual bytes inside the 32bits word.)

---
Tags: computer-architecture
---