# Question
Title: Are there name and literature for this SAT-like problem?
Given $f : \\{0,1\\}^\* \to \\{0,1\\}$ and $n \in \mathbb{N}$, we define $\textsf{Prob}(f,n)$ as the following problem:

> Find an $x \in \\{0,1\\}^n$ such that $f(x) = 1$.

A machine solving $\textsf{Prob}(f,n)$ would have $f$ encoded as a bit-string representing another machine computing $f$ and would have $n$ encoded in binary.

$\textsf{Prob}(f,n)$ generalizes some problems. For example:

* If $f$ is a Boolean logical proposition with $n$ variables, then $\textsf{Prob}(f,n)$ would be the search problem that corresponds to the SAT of $f$.
* If $f$ is the decider for a language, then $\textsf{Prob}(f,n)$ would be the problem of finding an $n$-bit string in that language.

Has $\textsf{Prob}(f,n)$ been studied in the literature (presumably with another name)? Is there already a name for this problem? What would be a good starting point to find papers on this problem in the research literature?

What problems are similar to this problem?

Is there linear-time $f$ such that $\textsf{Prob}(f,n)$ has no better algorithm than brute force? Formally, is there $f$ such that evaluating $f(x)$ is in $\textsf{DTIME}(O(\lvert x \rvert))$ and $\textsf{Prob}(f,n) \in \textsf{DTIME}(\Omega(2^n))$?

# Answer
The problem, as specified, takes at least exponential time to solve: merely outputting a string $x$ that satisfies $f(x)=1$ takes $\Theta(n)$ time (since $x$ is $n$ bits long), and this is exponential in the length of the input in the worst case (if $f$ has a short description, then the input length is $\Theta(\lg n)$ bits. This is a consequence of the fact that $n$ is specified in binary.

If $n$ is specified in unary and the running time of $f$ is guaranteed to be polynomial in $n$, the problem is NP-hard, and the corresponding decision problem is NP-complete. It is at least as hard as SAT, because any SAT formula can be encoded as a program $f$. Also, it is no harder than SAT, as any program whose running time is polynomial in $n$ can be expressed as a circuit of size polynomial in $n$; then the problem becomes equivalent to CircuitSAT, which is also NP-complete by a standard reduction (basically, the Tseitin transform).

So the unique aspects of this problem come from (a) the fact that $n$ is expressed in binary, and (b) the lack of any guarantee on the running time of $f$.

---

For your last question, you have to be a little bit careful. If you fix $f$ and specify $n$ in unary, the problem seems unlikely to require $\Omega(2^n)$ time. In particular, there is an infinite advice string $A$ such that the answer to the input $n$ is $A\_n$. This shows that there is a non-uniform polynomial time algorithm for this problem, if you fix $f$ and express $n$ in unary (i.e., the problem is in P/poly); this would be surprising, as it implies NP is contained in NP/poly, which is not expected to occur. To avoid trivial situations like this, you might want to treat the description of $f$ as part of the input, rather than fixing $f$.

This suggests we ask whether there exists a class of functions $f$ such that the problem requires $\Omega(2^n)$ time, yet where every function $f$ in the class can be computed in $O(n)$ time. I suspect the answer to that is likely to be yes if the strong exponential time hypothesis is true; simply take as your class of functions the set of SAT formulas of size $O(n)$. Note that this doesn't follow immediately from the strong exponential time hypothesis, due to the extra restriction that the formulas have size $O(n)$, but I would venture a guess that this restriction does not help algorithms solve SAT more efficiently. That said, the strong exponential time hypothesis is a very strong assumption.

Also, if we could prove that the answer to this question is yes, then I suspect we'd obtain a proof that the strong exponential time hypothesis is true. In particular, since $f$ can be computed in $O(n)$ time, there is a circuit that computes it in $O(n)$ time, so it can be expressed as a SAT formulas with $O(n)$ variables (using the Tseitin transform). If we knew that there was no algorithm to solve the resulting class of SAT instances in $O(2^n)$ time, then we'd know there is no algorithm to solve all SAT instances in $O(2^n)$ time, which implies the strong exponential time hypothesis. I think.
> 0 votes

---
Tags: complexity-theory, reference-request, satisfiability, search-problem
---


# Question
Title: What is the name of the property where $f(A) \supseteq f(B)$ when $A\supseteq B$?
Suppose I have a function $f$ on sets.

What is the property of $f$ called when,

for all sets $x$, $y$: $f(x)$ is a superset of $f(y)$ when $x$ is a superset of $y$

i.e.

$$\forall x,y : x\supseteq y \Rightarrow f(x) \supseteq f(y)$$

# Answer
It is called monotonicity with respect to the inclusion ordering of sets.

More precisely, it is in this case *increasing monotonicity* since the order is preserved. If the order was reversed, it would be *decreasing monotonicity*.

It can also be called *direct monotonicity* and *reverse monotonicity*, as *increasing/decreasing* seems used mostly for numeric functions.

The function is said to be *strictly* monotone iff (in the *direct case*)

$$\forall x,y : x\supsetneq y \Rightarrow f(x) \supsetneq f(y)$$
> 6 votes

---
Tags: terminology, sets, partial-order
---


# Question
Title: Difference between Turing machine end state and halt
Is there a difference between the end state of a Turing machine and the halt state? Especially, for example the Busy Beaver 3. It is said that it is with 3 states but there is also a halt. Is the end state $q\_2$ or the $halt$?

# Answer
"End(ing) state" and "halt(ing) state" are just two (four) different ways of saying the same thing.
> 2 votes

# Answer
In the specific case of the Busy Beaver , the end state is the halt state, al other states (q0,q1,q2) must have a transition defined for every symbol in the alphabet of the TM so the machine doesn't halt on them.
> 1 votes

---
Tags: terminology, turing-machines
---


title: What are Markov chains?

text:
# Question
Title: What are Markov chains?
I'm currently reading some papers about Markov chain lumping and I'm failing to see the difference between a Markov chain and a plain directed weighted graph.

For example in the article Optimal state-space lumping in Markov chains they provide the following definition of a CTMC (continuous time Markov chain):

> We consider a finite CTMC $(\mathcal{S}, Q)$ with state space $\mathcal{S} = \\{x\_1, x\_2, \ldots, x\_n\\}$ by a transition rate matrix $Q: \mathcal{S} \times \mathcal{S} \to \mathbb{R}^+$.

They don't mention the Markov property at all, and, in fact, if the weight on the edges represents a probability I believe the Markov property trivially holds since the probability depends only on the current state of the chain and not the path that lead to it.

In an other article On Relational Properties of Lumpability Markov chains are defined similarly:

> A Markov chain $M$ will be represented as a triplet $(S, P, \pi)$ where $S$ is the finite set of states of $M$, $P$ the transition probability matrix indicating the probability of getting from one state to another, and $\pi$ is the initial probability distribution representing the likelyhood for the system to start in a certain state.

Again, no mention of past or future or independence.

There's a third paper Simple O(m logn) Time Markov Chain Lumping where they not only never state that the weights on the edges are probabilities, but they even say:

> In many applications, the values $W(s, s')$ are non-negative. We do not make this assumption, however, because there are also applications where $W(s, s)$ is deliberately chosen as $-W(s, S \setminus \\{s\\})$, making it usually negative.

Moreover, it's stated that lumping should be a way to reduce the number of states while maintaining the Markov property (by aggregating "equivalent" state into a bigger state). Yet, to me, it looks like it's simply summing probabilities and it shouldn't even guarantee that the resulting peobabilities of the transitions to/from the aggregated states are in the range $\[0,1\]$. What does the lumping actually preserve then?

So, there are two possibilities that I see:

* I didn't understand what a Markov chain is, or
* The use of the term Markov chain in those papers is bogus

Could someone clarify the situation?

It really looks like there are different communities using that term and they mean widely different things. From these 3 articles that I'm considering it looks like the Markov property is either trivial or useless, while looking at a different kind of papers it looks fundamental.

# Answer
> 10 votes
A *Continuous-time Markov Chain* can be represented as a directed graph with constant non-negative edge weights. An equivalent representation of the constant edge-weights of a directed graph with $N$ nodes is as an $N \times N$ matrix. The *Markov property* (that the future states depend only on the current state) is *implicit* in the constant edge weights (or constant entries in the matrix). *Implicit* means *implied by*. Mathematicians use it as a euphemism meaning, "you should prove it yourself."

But the first paper defines a notation consistent with a *Continuous-time* Markov Chain, sometimes called a *Markov Process*, while the second paper defines a notation consistent with a *Discrete-time* Markov Chain. They say

> $P$ is the *transition probability matrix* indicating the probability of getting from one state to another, and $\pi$ is the *initial probability distribution* representing the likelihood for the system to start in a certain state. \[emphasis added\]

They are assuming that the matrix is constant over time (thus implying the Markov property). Implicit in the term *probability* is the fact that each constant is in range $\[0,1\]$, that the entries in every column of $P$ sum to $1$, and that the sum of the entries in $\pi$ sum to $1$.

I can't read the third paper, it is paywalled. If the entries in every column of the matrix are required to sum to 1 then they are probabilities and they are talking about Discrete-time Markov Chains. If the entries in every column can sum to an arbitrary number then the entries represent *rates* not probabilities and they are talking about Continuous-time Markov Chains.

*Continuous-time* Markov Chains are not the same as *Discrete-time* Markov Chains. In a *Continuous-time* Markov Chain the edge weights do not represent probabilities, but rather *transition rates*. The edge weights must be non-negative, but can be arbitrarily large, and the weights of the out-edges can sum to any non-negative number. The sum is not required to be $1$.

With both Continous-time and Discrete-time Markov Chains the Markov property is implied by the constant edge weights (or equivalently the constant entries in the transition matrix.)

# Answer
> 8 votes
Markov Chains come in two flavors: continuous time and discrete time.

Both continuous time markov chains (CTMC) and discrete time markov chains (DTMC) are represented as directed weighted graphs.

For DTMC's the transitions always take one unit of "time." As a result, there is no choice for what your weight on an arc should be-- you put the probability of going to "j" given that you're at "i."

For CTMC's, the transition time between any two states is necessarily given by an exponential random variable. This is the key difference between CTMC's and DTMC's: DTMC's always have unit transition time. CTMC's have random transition time.

For a CTMC, the convention is generally to put weights on an arc according to the rate of the exponential random variable going from the source to the destination. That is- the convention is to put *rates* on the arcs, not probabilities.

**Negative Rates**

Although all the CTMC's that I recall were represented with positive rates on the edges, negative rates do come up in CTMC analysis.

Say we're standing at state A, which is connected to B, C, and D as below.

A --\> B (the rate *into* A *from* B is negative) A --\> C (the rate *into* A *from* C is negative) D --\> A (the rate *into* A *from* D is positive)

This is likely not quite what your paper is referring to; I bring it up to show that negative weights aren't necessarily ridiculous if someone was working with a suitable convention.

**Markov Property**

For DTMC's- you're right. The markov property is satisfied trivially. For CTMC's, the markov property is satisfied because the transitions are given by exponential random variables (which are "memoryless"). If the transitions were not given by exponential random variables (say instead they were uniform), then we would be talking about "Semi-Markov Chains" or "Semi-Markov Processes."

---
Tags: probability-theory, weighted-graphs, mathematical-foundations, markov-chains
---


# Question
Title: Creating a single layer perceptron for the OR problem
I am working on the following problem

Find the linear least squares unit weights for the \`OR' problem, ie. $v\_1^T = (0,0), v\_2^T = (1,0), v\_3^T = (0,1), v\_4^T = (1,1)$ and $u\_1 = 0, u\_2 = u\_3 = u\_4 = 1$.

Here $v$ represent inputs and $u$ outputs. For problems like this I usually find a matrix $W$ (the weights) such that $$u\_i=Wv\_i \quad i=1,2,3,4$$ but I think it is obvious a matrix doesn't exist. my reasoning being that the problem is equivalent to finding the matrix $W = \begin{pmatrix} x\_1 & x\_2 \end{pmatrix} $ such that $$\begin{pmatrix} 0 & 1 & 1 & 1 \end{pmatrix} = \begin{pmatrix} x\_1 & x\_2 \end{pmatrix} \begin{pmatrix} 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 \end{pmatrix}$$ And looking at the two middle columns of the left vector and right matrix we must have $x\_1=x\_2 =1$ but then we get $1 + 1 = 1$, a contradiction.

In a unit perceptron a function may be applied to the output, and a step function $$f(x) \begin{cases} 0 & x \leq 0 \\ 1 & x \> 0 \end{cases}$$ would work here.

My question here is, is this correct? I wasn't quite sure if I am answering the right question. I am pretty sure $u\_i = f(Wv\_i)$ but I am not too familiar with what is meant by "linear least squares unit weights" in this context?

# Answer
> 1 votes
The fact that you mention *linear* least squares error seems to hint that they want you to use a completely linear model $u\_i=Wv\_i$ for your perceptron. In this case you won't get exact answers like $0$ and $1$; you will only get approximations with some amount of error.

That said, I don't think a linear model makes sense for this problem, since it is a classification problem with two classes. Using a non-linear step-like function $f$ before the final output of a perceptron classifier is a pretty standard thing to do, so I see no problem with using $u\_i=f(Wv\_i)$.

Assuming you can use $f$, using the weights $x\_1 = x\_2 = 1$ as you mentioned solve this problem exactly with zero error.

---
Tags: neural-networks, linear-algebra, boolean-algebra
---


title: Heaviest planar subgraph

text:
# Question
Title: Heaviest planar subgraph
Consider the following problem.

Given: A complete graph with real non-negative weights on the edges.

Task: Find a planar subgraph of maximum weight. ("Maximum" among all possible planar subgraphs.)

Note: The maximum-weight subgraph will be a triangulation; if the complete graph is on $n$ vertices, it will have $m=3n-6$ edges.

Question: What is the best available algorithm for this problem? What is its time-complexity?

# Answer
> 6 votes
This is NP-hard even for weighted complete graphs. For an easy algorithm, you can compute a maximum-weight spanning tree: negate the edge weights and run Kruskal's algorithm. This gives you a performance ratio of 1/3 (a spanning tree has $n-1$ edges, and as you note, a maximum planar subgraph can contain at most $3n-6$ edges). As far as I know, the algorithm in \[1\] which has a performance ratio at least 25/72 and at most 5/12 has not been considerably improved upon (but see what newer papers reference it).

For complete graphs whose edge weights obey the triangle inequality, the performance ratio of the algorithm in \[1\] is at least 3/8. The algorithm, I think, is rather involved and can be made to run in $O(m^{3/2}n \log^6 n)$ time on general graphs. There are some simpler variants the authors present as well with different performance ratios, and possibly better runtimes.

---

\[1\] Calinescu, G., Fernandes, C. G., Karloff, H., & Zelikovsky, A. (2003). A new approximation algorithm for finding heavy planar subgraphs. Algorithmica, 36(2), 179-205.

---
Tags: algorithms, graphs, optimization, combinatorics
---


# Question
Title: Optimization in multivalued logic. Optimal strings with given patterns
This question comes from an application in multivalued logic.

Suppose, we are given an alphabet of three letters $A, B, C$ and a set of indices $1,2,3,4,5$. Consider items formed by subscripting the letters with one of the indices. Examples are the following:

$$A\_1 \\ B\_4 \\ C\_3 \\ ... $$

Suppose, additionally, that there is a total binary relation $\mathcal{R}$ on items $\*\_i \<= \*_j$ for each pair $ i, j \in \\{ 1,..., 5 \\} $ where $\*$ denotes one of the letters $A,B$ and $C$. The relation is reflexive and transitive.

Consider a set of strings of length $5$ freely generated by the alphabet $A, B, C, ...$ disregarding ordering. Examples are the following:

$$ AABBC \\ AAAAB \\ AABCC \\ ... $$

Since order doesn't count, a string $AABBC$ is the same as $ABBAC$.

Let's call such strings *templates*. The templates can be "filled in" with the indices to form *tuples* of items using the following rules:

* R1: there may be no repetitions of indices disregarding the letter type, e.g.

$$A\_1, A\_1, B\_2, C\_3, C\_4$$

and

$$A\_1, A\_2, B\_2, C\_1, C\_4$$

are both forbidden since the index $1$ is used two times.

* R2: ordering in a tuple does not count, e. g.

$$\left( A\_3 A\_2 B\_1 B\_4 C\_5 \right)$$

is the same as

$$\left( A\_2 A\_3 B\_1 B\_4 C\_5 \right)$$

One can think of such "filling in" the templates as filling in a truth table with several logical levels in general.

Let us denote the set of all freely generated strings of length $5$ from the $A,B$ and $C$ by $\mathbb{Tmp}$. Let $\mathbb{Tpl}$ denote the set of all tuples generated by index assignments according to the rules R1 and R2. We can define a mapping $U:\mathbb{Tpl} \mapsto \mathbb{Tmp}$ which removes the indices from a tuple and gives its underlying template. For example:

$$ U \left( A\_2 A\_3 B\_1 B\_4 C\_5 \right) = AABBC $$

We say that a tuple $T$ *satisfies* the template $t$ if $U(T) = t$. We say that $T$ satisfies a set of templates $\tau = \left(t\_1, t\_2, ..., t\_l \right)$ if there exists a template $t\_i \in \tau$ for some $i \in \left( 1,2,...,l \right)$ s. t. $U(T) = t\_i$.

Suppose, that we are given a set of templates $\tau$ and a total binary relation $\mathcal{R}$ on items.

**What is the greatest item (greatest in the sense of the binary relation $\mathcal{R}$) of all the least items of all the tuples satisfying the templates $\tau$. In other words, what is the maximin item of the tuples?**

The bruteforce algorithm is evident: take a template, build all the corresponding tuples, compare elements in each tuple and find the least, compare all the outcomes of the previous step, take the greatest. I am sure this is an $NP$-complete problem if the underlying truth table is irreducible.

What if we order all the items to obtain a sequence like this:

$$ C\_2 \<= B\_4 \<= C\_1 \<= C\_5 \<= B\_1 \<= A\_2 \<= C\_3 \<= A\_3 \<= B\_3 \<= C\_4 \<= A\_4 \<= A\_5 \<= B\_5 \<= A\_1 \<= B\_2$$

Let's call this sequence $S$.

**Can it simplify the problem by any chance?**

For instance, consider the templates:

$$\tau = \left( AAAAB, AAABB, AAABC \right)$$

Can there be an algorithm more effective than the bruteforce? I was thinking in the following way: one can start in the sequence $S$ form left to right and "drop" items until there is no more letters to drop (otherwise, the templates are violated) or if the indexing requirement is violated.

Example of such a procedure goes like this:

drop $C\_2$, drop $B\_4$, drop $C\_1$, drop $C\_5$, drop $B\_1$, drop $A\_2$, drop $C\_3$, drop $A\_3$, $B\_3$ must be picked

So no tuple may contain an item greater than $B\_3$.

It seems to offer a minor complexity reduction and only for simple templates. For more complex ones, there are subtleties which I won't discuss here. But I am suspicious that there is a fundamental limitation in this problem which makes every algorithm not really better than the bruteforce.

# Answer
> 2 votes
As stated, it looks like the solution is trivial: if $\omega$ is the largest value in the underlying domain of values, then $\omega \omega \cdots \omega$ is the optimal value for the tuple.

Let's take your example, templates $AAAAB$, $AAABB$, and $AAABC$. Suppose the underlying domain of allowable values is $\\{0,1,\dots,9\\}$. Then $99999$ is the optimal tuple. It satisfies $AAAAB$ by the assignment $A\_1A\_2A\_3A\_4B\_5$. It satisfies $AAABB$ by the assignment $A\_1A\_2A\_3B\_4B\_5$. In fact it satisfies every template. For any template, there exists an assignment of values to each $X\_i$ that makes the tuple $99999$ match that template: just assign the value $9$ to every $X\_i$, for all levels $X$ and all variable indices $i$.

Perhaps you meant to provide both the templates and the assignment of values (all $m^2$ values for all the $X\_i$'s, where $X$ and $i$ range over all possibilities) as input.

---
Tags: algorithms, complexity-theory, time-complexity, np-complete, kolmogorov-complexity
---


# Question
Title: Terminology for describing a kind of server
What is the adjective used to describe the fact that a server keep track of queries made by a user. I take the example of a database server.

# Answer
Such a server would be stateful rather than stateless: roughly speaking, stateful means that it keeps some information, possibly partial information, on past queries. If you are looking for a single word to capture the idea that the server stores a complete record of all past queries, in their entirety, I don't know of a single word that does that -- so just use a sentence to describe what you're talking about.
> 1 votes

---
Tags: terminology, databases
---


title: What is an $NP^{NP}$-complete problem?

text:
# Question
Title: What is an $NP^{NP}$-complete problem?
So in this paper I'm reading (https://adamsmith.as/papers/fdg2013\_shortcuts.pdf), the authors talk about an $NP^{NP}$-complete problem, in relation to Answer Set Programming. I know what P, NP, etc. are but I don't unerstand what they mean with $NP^{NP}$. Also I can't Google it because Google doesn't recognize superscript.

I did find out it's also mentioned in this book, but they still don't provide an explanation.

Can anyone ecplain this class of problems to me?

# Answer
$NP$ is the class of problems that, roughly speaking, you can solve by guessing an $y$ of polynomial size (with some magic to guarantee that you guess "right") and then doing a polynomial computation involving $y$ and the original input.

$NP^{NP}$ is the class of problems solvable in this way, if you have access to an oracle for $NP$. After guessing $y$, you're not just allowed to do some polynomial computation, you're also allowed (within this calculation) to solve problems from $NP$ (through an oracle, so in constant time).

The classical $NP$-complete problem of boolean satisfiability is to compute $\exists\_x R(x)$ where $R$ is some boolean formula (and $x$ is a shorthand for $x\_1,\ldots,x\_n$). Its $NP^{NP}$-complete analogue is to compute $\exists\_x \forall\_y R(x)$.

A slightly more intuitive $NP^{NP}$-complete problem is that of formula minimization: given a formula, can you find a formula of length $\leq k$ that expresses the same (boolean) function?

$NP^{NP}$ is also known as $\Sigma\_2 P$, and you will be able to find more info by searching for "polynomial hierarchy" (see, e.g., Wikipedia's article).
> 3 votes

---
Tags: complexity-classes, np, answer-set-programming
---


title: What is a sufficiently complex system?

text:
# Question
Title: What is a sufficiently complex system?
I have been reading about the AI approaches, and I came across the AI emergent approach that has the following definition:

**That is, the appearance of an entity with a sense of its own identity and agency within a sufficiently complex system.**

And I have got trouble understanding the meaning I have read the the paper What is a complex system? and the definition in this site, But I have still got trouble understanding the whole expression what does sufficiently mean exactly in this expression?

# Answer
> 2 votes
It just means "a system whose complexity is high enough to allow it to do \[whatever thing we're talking about\]."

---
Tags: complexity-theory, artificial-intelligence
---


# Question
Title: How can I see which language type will result from the union or intersection of different language types?
I have to decide which language type will result from the union of a type-2 (context-free) and a type-3 (regular) language.

Is there a way or rule to decide this for all language types?

# Answer
> 3 votes
First, a minor point of terminology. In the Chomsky hierarchy, type-2 languages are the context-free family, not the context-sensitive one. I do not know which you meant.

In general, the terminology used is *family* of language rather than *type* of language. The fact that the application of some operation $\diamond$ applied to languages in families $\mathcal F\_i$ always gives a language in the family $\mathcal F$ is called a closure property.

As stated by Hendrik Jan in his answer, there are no general rules to determine closure properties and they can vary a lot. To complement his examples, context-free (type 2) languages are not closed under intersection: the intersection of two context-free languages may not be a context-free language. However, the intersection or union of a context-free language with a regular language is always context-free. (proving it is an excellent exercise).

Since you are ambiguous as to what family of languages you are interested in, it so happens that the context-sensitive languages are also closed under union or intersection with regular languages.

Actually, many (most ?) interesting families of languages are closed under union or intersection with regular languages.

Though there are no general rules for proving it, there are many other operations one may consider on the languages of a family, which leads to many studies of closure properties of languages. It turns out that closure properties are not independent, because many operations can be defined by composition, or complex combinations, of other operations.

This has led to the study of what is usually called Abstract Families of Languages, i.e. families that are closed under the same kinds of operations. But that is now far beyond your question.

# Answer
> 3 votes
This notion is clalled **closure property**. A family $\mathcal F$ of languages is closed under (binary) operation $\\#$ if $K\\# L$ is in $\mathcal F$ for all $K,L$ in $\mathcal F$.

There are no general rules: context-free $\mathsf{CF}$ is closed under union $\cup$, deterministic context-free $\mathsf{DCF}$ is not. However there are resources that list the known closure properties for important families, especially the Chomsy hierarchy.

---
Tags: formal-languages, regular-languages
---


# Question
Title: Skolemization with multiple arguments -- how to unify
Edit: answerers keep finding (valid!) problems with my example. I'll try again. The older version is below the horizontal line. Thanks to Klaus below for pointing out the last problem.

My question is how to unify skolemizations that have differing numbers of arguments. As he points out, there is rarely any need for this. For example, if the statements are

```
Some homes are blue.
There is a home with two stories.

```

The skolemizations here should not unify, because we can't know from this if a blue home is two-storied.

If we're going to ever need to unify one skolemization with another, we'll need to know we're talking about the same home. This would do it:

```
Jane's and Mark's home is blue (their only home).
Jane's home has two stories (her only home).

```

Here it is in FOPC:

$$ \exists x: has(Jane,x) \wedge has(Mark,x) \wedge home(x) \wedge blue(x) \wedge $$ $$ (\forall y: has(Jane,y) \wedge home(y) \implies x=y) \wedge $$ $$ (\forall y: has(Mark,y) \wedge home(y) \implies x=y) $$ and $$ \exists x: has(Jane,x) \wedge home(x) \wedge twoStories(x) \wedge (\forall y: (has (Jane,y) \wedge home(y) \implies x=y) $$

Converting to conjunctive normal form with skolemization gives us this set:

$$ has(Jane,skolem1(Jane,Mark)) $$ $$ has(Mark,skolem1(Jane,Mark)) $$ $$ home(skolem1(Jane,Mark)) $$ $$ blue(skolem1(Jane,Mark)) $$ $$ \neg has(Jane,y) \vee \neg home(y) \vee skolem1(Jane,Mark) =y $$ $$ \neg has(Mark,y) \vee \neg home(y) \vee skolem1(Jane,Mark)=y $$

$$ home(skolem2(Jane)) $$ $$ twoStories(skolem2(Jane)) $$ $$ \neg has (Jane,y) \vee \neg home(y) \vee skolem2(Jane)=y $$

Now, if I want to reason about whether there's a blue house with two stories -- which I *should* be able to start by resolving the first and last clauses in the set -- I can't, because the two skolemizations can't unify: they have different numbers of arguments.

Is there a good protocol of picking arguments to prevent this problem -- other than applying human intelligence after the mismatch is noticed?

---

Here is the old version. It's significantly different, but as Klaus pointed out, the old version simply doesn't give us a skolemization problem (or even a skolem for the first statement):

"Everybody who has a home pays utilities on it," encoded as

$$ \forall x: has(x,skolem1(x)) \wedge home(skolem1(x)) \implies paysUtilsOn(x, skolem1(x)) $$
or $$ \bar has(x, skolem1(x)) \vee ~home(skolem1(x)) \vee paysUtilsOn(x, skolem1(x)) $$ and "Jane and Mark have a home," encoded as $$ has(Jane,skolem2(Jane,Mark)) \wedge has(Mark,skolem2(Jane,Mark)) \wedge home(skolem2(Jane,Mark)) $$ or $$ has(Jane,skolem2(Jane,Mark)) $$ $$ has(Mark,skolem2(Jane,Mark)) $$ $$ home(skolem2(Jane,Mark)) $$

I want to use resolution to prove Jane pays utilities. The problem is that skolem1 has 1 argument and skolem2 has 2 arguments, so they don't unify.

I'm not sure if this matters -- could I just refer to skolem1 and skolem2 and forget the arguments entirely? If it does matter, how do I resolve the problem so that skolem1 and skolem2 can unify, and resolution can work? Not by finding a way around the problem, but by truly using skolemization correctly. The issue is what to do with skolems that have different argument lists if they seem to occur naturally.

# Answer
"Everyone has a heart" gets first encoded first as $\forall x. \text{Person}(x) \Rightarrow \exists y. \text{Hart}(y) \wedge \text{Has}(x,y)$. Then you get the Skolemization (that you found in RN) from that.

Now "Everybody who has a house pays utilities" is just $\forall x. \text{Houseower}(x) \Rightarrow \text{PaysUtilities}(x)$ because there is no assertion that anything exists in this statement. However, if you want to spell out what houseowner means, $\forall x.\text{Houseowner}(x) \Leftrightarrow (\text{Person}(x)\wedge\exists y.\text{House}(y) \wedge Has(x,y))$. And you can skolemize that... but it's not even needed for what you want to infer.

As to "Jane and Mark have a house", it's actually a bit ambiguous. Do they have the same house? But that's an irrelevant detail if you just encode $\text{Houseower}(\text{Jane}) \wedge \text{Houseower}(\text{Mark})$. From that it immediately follows that $\text{Houseower}(\text{Jane})$ and using $\forall x. \text{Houseower}(x) \Rightarrow \text{PaysUtilities}(x)$ it follows that $\text{PaysUtilities}(\text{Jane})$ with the obvious unification $x=\text{Jane}$.

As you can see, the definition of houseowner (which asserts the existence of a house etc.) is completely irrelevant to the inference you wanted. In general, not every "has" in the English language gets translated into a binary predicate, unless it's relevant to what you want to prove. Nobody managed to invent a rigorous way to formally and universally translate all of English (or any other natural language) into first-order logic. While there are some guidelines, a translation of a problem statement from natural language to FO ultimately uses a problem-specific encoding method.

Also note that your first sentence "Everybody who has a house pays utilities" bears some resemblance to a donkey sentence, but it's not actually one; you'd have to say "Everybody who has a house pays utilities on it" to get a donkey sentence.
> 2 votes

# Answer
One issue with your example is that it doesn't say what you seem to think it says. Recall that skolemization is used to eliminate an existentially quantified variable by replacing it with a function depending on whatever universally quantified variables are in scope. Then your initial formula would be the skolemization of

$\forall x\exists y:(has(x,y)\wedge house(y))\Rightarrow paysUtilsOn(x,y)$.

This says that for all $x$ there is some $y$ such that, if $y$ is a house owned by $x$, then $x$ pays utilities on it. This formula is trivially satisfiable by always picking a non-house (or something not owned by $x$) for $y$. The following makes more sense:

$\forall x\forall y:(has(x,y)\wedge house(y))\Rightarrow paysUtilsOn(x,y)$,

i.e. a person pays utilities for every house they own. No existential quantifiers to skolemize away here, though. As for your second statement, Jane and Mark are specific people, so

$\exists y:has(Jane,y)\wedge has(Mark,y)\wedge house(y)$

simply skolemizes to

$has(Jane,s0())\wedge has(Mark,s0())\wedge house(s0())$

(note the complete absence of universally quantified variables).This would change if you had a property like

$\forall x\forall y: partners(x,y)\Rightarrow\exists z:has(x,z)\wedge has(y,z)\wedge house(z)$.

This becomes

$\forall x\forall y:partners(x,y)\Rightarrow has(x,s2(x,y))\wedge has(y,s2(x,y))\wedge house(s2(x,y))$,

and then from $partners(Jane,Mark)$ you could conclude $has(Jane,s2(Jane,Mark))$ and $paysUtilsOn(Jane,s0(Jane,Mark))$.
> 1 votes

---
Tags: logic, first-order-logic, normal-forms, unification
---


title: average time to access a word in memory

text:
# Question
Title: average time to access a word in memory
Here is the question:

> Consider a computer system that has cache memory, main memory (RAM) and disk, and the operating system uses virtual memory. It takes 2 nsec to access a word from the cache, 10 nsec to access a word from the RAM, and 10 ms to access a word from the disk. If the cache hit rate is 95% and main memory hit rate (after a cache miss) is 99%, what is the average time to access a word?

Here is how I solved it. consider 100 references 95 cache hits(due to 0.95 cache hit ratio) 95\*2nsec = 190 nsec

this would leave 5 references which were passed to memory `5*0.99=4.95=5` successfully found in memory

this would count for

5\*10nsec=50nsec

average access time=total time/total accesses =(50+190)/100 nsec =240/100 nsec =2.4 nsec

Is this correct?

Here is another solution

memory access time =cache hit ratio * cache access time + (1 - hit ratio) * miss penalty(or memory access time) =0.95\*2+(1-0.95)10 2.4 nsec

which one is the perfect solution to this problem?

In question memory hit ratio is also given but is not used in the formula I used in second solution.Was it unnecessarily given in the question? If there is a problem where cache hit rate is 85% and memory hit rate is 5% and disk hit rate is 10%, then what would be the miss penalty in that case?

# Answer
> 1 votes
This is not the answer, but you may consider it as hints to find it yourself.

Why do you write `4.95=5` without any explanation. Is that your idea of *perfect solution*? Apparently your first solution never accesses the disk. Your second solution is essentially the same as the first, presented more abstractedly (hence a bit better in my opinion, but the reasonning may not be explicited enough for what seems to be your level of proficiency), but it ignores the disk access as much as the first soution.

That may not always be true, but you should always worry at least a little bit where you are ignoring part of the data of your problem. You should convince yourself that the data you ignore is

* either *redundant* with the data you use. This means that it is actually a consequence of the data you are using, and can thus be taken into acount implicitly through the data you are using;
* or *irrelevant* to the problem. In this case you should preferably have some argument as to why it is irrelevant. This argument may not be required in your answer (though it may not hurt to give it), but you probably at least sketch it for yourself to convince yourself that you are right in ignoring the corresponding data.
* Irrelevance can also include the fact that the corresponding data is *negligible* in the context of your problem. But that usually demands some argument to convince the reader that it is indeed the case.

Does the data you ignore correspond to such a case?

# Answer
> 1 votes
Actually I was not sure about the formula, that's why I posted the question with the work I have done so far. I am posting the right solution so that a student like me can benefit from it in the future The formula for my question is: average access time = (cache hit time x cache hit rate) + (cache miss rate)(RAM hit time x RAM hit rate)+ (cache miss rate)(RAM miss rate)(disk hit time)

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


title: Complexity if special case of SAT

text:
# Question
Title: Complexity if special case of SAT
I have the following problem: How to show that the special case of SAT, in which each clause has either exactly two literals or at most one negative literal, is NP-complete?

# Answer
You pick a problem that is NP-complete and show a reduction that shows your problem is at least as hard as that NP-complete problem. As this is a natural exercise problem, you should practice trying it yourself -- we wouldn't be helping anyone to just spoonfeed you the solution.

Alternatively, you use Schaefer's dichotomy theorem. (Comment: If you're just learning the subject, don't expect this to be easier than doing the reduction! This is only if you want to go deeper on the subject.)
> 1 votes

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


# Question
Title: Express XOR with multiple inputs in zero-one integer linear programming (ILP)
In the below post, it is explained how to express xor of two variables as linear inequalities.

Express boolean logic operations in zero-one integer linear programming (ILP)

Naturally, the xor of multiple variables can be expressed using a sequence of multiple 2-input xors but my question whether there is a smarter way to do it?

# Answer
Here is another way you could try. To express $y=x\_1 \oplus x\_2 \oplus \dots \oplus x\_n$ (the exclusive-or of $x\_1,\dots,x\_n$), try the following constraints:

$$y = x\_1 + x\_2 + \dots + x\_n - 2t$$ $$0 \le y \le 1$$

where $y$ and $t$ are constrained to be integers.

There are no guarantees this will work better than a sequence of 2-input xors or a tree of 2-input xors. Generally, the only way to discover what will work best with an ILP solver is to try each of the operations and see how fast the ILP solver runs.

Caution: If your problem has a lot of XORs, integer linear programming might not be the best tool for the job. A SAT solver might be more effective. See also CryptoMiniSat, which is a SAT solver optimized to deal well with XORs.
> 2 votes

---
Tags: linear-programming, integer-programming, xor
---


# Question
Title: Is a partial function Turing-computable?
From my understanding for a function to be considered Turing-computable the Turing machine which computes it must terminate for all inputs (according to this http://planetmath.org/turingcomputable and various other sources I've read).

But then doesn't this mean that all partial functions are not Turing-computable? (and by extension not computable at all regardless of computational model due to the Church–Turing thesis?)

But this seems rather silly given that most real-world functions are partial, and many clearly computable...

This confuses me greatly, any help would be appreciated.

**A)** Is termination part of the definition of Turing-computability? (and computability in general)

**B)** How does non-termination fit into the concept of computability?

# Answer
So, some of the functions you talk about might be technically uncomputable, but the problem can become decidable with trivial modifications.

For example, consider the function taking a natural number to its predecessor. If you define it partially, nothing comes before $0$, and there's no algorithm to solve this, because there isn't a correct answer. The algorithm can't find it because it doesn't exist.

But, if you make a choice, and say that the predecessor of $0$ is $0$, or some special character, now you have a total function, from which you can extract your partial one.

I suspect most of the "real world" partial functions you talk about fall into this category. You just define a special "fail" output for any inputs where there's no defined output.

What the definition of computability is talking about really is whether a Turing Machine halts for all inputs. If it halts on all inputs, the result is whatever is on the tape, so it's considered total. If it doesn't, then it's partial.

For your specific questions:

Yes, termination is absolutely part of the definition of computability. Otherwise, everything is decidable: I make a Turing machine that runs forever, and since it doesn't ever give a wrong answer, I've "solved" the problem. Given this, solving a problem without termination is pretty meaningless.

A function is computable if there exists a Turing Machine computing it which halts on all inputs.

How does non-termination fit in? Basically, we don't allow non-termination, because of the problem I mentioned above. There is a special class of problems, called "recursively-enumerable" or "semi-decidable" decision (yes/no) problems, where the Turing Machine halts on all "YES"-valued inputs, but might not halt on all NO-valued inputs.

Another thing to watch here is your quantifiers. A problem is decidable if there exists a Turing Machine that solves it and always halts. I can make a Turing Machine solving addition that sometimes loops forever, but that doesn't mean that addition is undecidable, because there exists another machine that solves it and always halts.
> 4 votes

---
Tags: computability, turing-machines, church-turing-thesis
---


# Question
Title: Divide self-intersecting polygon into simple polygons
My question is similar to question here Divide self-intersecting polygon

I have points of self-intersecting polygon, its edges and also I am able to find points where it intersects.

I have to divide it into simple polygons and tessellate them later.

I have an issue how we currently select the edge after the intersection point is encountered. Right now we select an intersecting-edge which makes the smallest angle with the preceding edge. This approach simplifies some intersecting loops (e.g. horizontal '8' is divided into two 'o' loops).

But this approach has some issue. Say two polygons one inside another. Such polygons are not divided into two loops.

I plan to select an intersecting-edge which makes the largest angle with the preceding edge. This way I can get the outermost loop first and than I will form the internal loops with remaining edges. This will solve the problem for 'two polygons one inside another'. (This will fail for cases such as 'horizontal '8''. But this is OK as such case is handles while tessellating polygon)

Are there any known/unforeseen problems with this approach?

# Answer
A self-intersecting polygon induces a plane partition, which should be represented by some data structure. This structure should include at least three types of objects - vertices, edges and **faces**. The faces are what you are trying to construct.

This data structure is called DCEL and it usually represents *both* planar graphs - the original graph with vertices and edges (where intersection points are added as new vertices, and some edges are split), and a **dual** graph with polygonal faces as vertices. Each vertex in the original graph should refer to a list of adjacent edges (sorted by angle, yes) and each vertex in the dual graph should refer to a list of adjacent edges, forming its boundary. Edges are usually represented by two arcs with orientations, opposite to one another. In this case each arc is adjacent to exactly *one* face (including the exterior face), which normally lies "to the left" of it.

Having this data structure implemented you'll be able to calculate all the faces by finding proper cycles in the set of all arcs.
> 1 votes

# Answer
Suppose you've gone counterclockwise along some edges on the exterior of the polygon and now you've come to a vertex and/or intersection point (I'll just refer to them all as vertices from now on) V from vertex U. Then if you begin opening an angle from the V, going counterclockwise, you'll sweep through the exterior of the polygon. So the edge at V creating the smallest angle with V -\> U going counterclockwise is also an edge on the exterior.

To put it another way, if you are going clockwise, the edge that creates the largest angle (where largest means the largest going counterclockwise) is also an edge on the exterior.

To be clear, suppose you're building the outer loop in clockwise order. Then you DON'T want the largest angle as measured by dot products, since that gives you the angle when you're allowed to go either clockwise or counter-clockwise direction.

Here's a suggestion based on the same observation. 1) Find an exterior edge U -\> V oriented clockwise around the polygon. 2) Take the SMALLEST angle as measured going counter-clockwise V. This edge is guaranteed to be an edge of the minimal interior polygon of which U-\>V is a part. Continuing in this manner, you'll get the minimal polygon of which U -\> V is a part. You cut this off and repeat.
> 0 votes

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


# Question
Title: Comparing two graphs, finding vertices that changed their positions
I have a task of comparing two organisation charts. These chart objects are described as a set of nodes (people) where each has a unique ID field and a parent ID field (pointing to another node's unique ID). For simplicity we can assume that there's only one node without a parent ID (head of the organisation) and that no node can reference itself. So it's essentially a tree of all the people in the organisation. Comparison should produce two lists - people who left the organisation, people who joined, and people who have changed their position in the organisation. Leavers and joiners are trivial, but I don't know how to proceed with people who changed their position. I need some ideas on how to proceed with identifying people who really moved within the chart from those who only have new parent IDs.

# Answer
As stated, I think this is a minimum edit distance problem. Encode your graph in some canonical order (e.g. breadth-first, with tokens at each level sorted by id) with a token for each node and a token for each parent. You want the minimum edit distance between that encoding and the encoding of the new tree.

Minimum edit distance counts insertion, deletion, and substitution. Seems to map naturally to your problem.

If what you really have is an org. chart where there are various jobs that define the org chart with people who fill the jobs, then you have two different problems. You need to define your graph in terms of the jobs, and the min. edit distance algorithm is applicable to that. You then need to encode who has which job, and the encoding will make finding people who changed jobs trivial.
> 1 votes

---
Tags: graphs
---


# Question
Title: Unreachable Real Numbers - Randomness & Computability
I've recently read that there were many real numbers that would never be reachable by humanity. The explanation itself says that we can write as many programs as integers which is infinite, but there are infinite real numbers between two integers so Real numbers infinity is bigger than integer numbers.

Well my question is, couldn't we overpass this limitation by writing a program that prints out a random number in every execution? I know this is not a warranty that every real number would be printed but at least they would all have a chance.

Please point out if my reasoning is wrong and why.

Thanks you all very much!

# Answer
**In a nutshell:** *Printing a random non-computable real is a meaningless task, for precise technical reasons. The meaningful problem is to print non-computable numbers precisely identified by some unique property. But these cannot be printed by any program precisely because they are not computable. Using randomness in the hope of **printing by chance the uncomputable number you are interested in is impossible with a program**, unless you use a physical random phenomenon as randomness source (depending on physics, with probability zero, and without knowing whether you are succeeding).*

I am not sure what you mean by a number that is not "reachable by humanity".

The fact that there is an infinity of real numbers between two integers does not imply that there are more real numbers than integers (though there are more).

For example, there is an infinity of rational number between two integers, but the number (cardinality) of integers and rational numbers is the same. Actually, there is an infinity of rational numbers between any two rational numbers, but it does not imply that there are more rational numbers than rational numbers.

By the way, there is an infinity of rational numbers between any two real numbers, but there are more real numbers than rational numbers.

That should at least tell you that determining which set is bigger is not at all obvious, and is not related to the number of angels who can dance between two numbers.

Then **why are there more real numbers than integer?** Here is one of the proofs due to Cantor. The reals in the interval $\[0.0, 1.0\[$ are isomorphic to infinite sequences of the symbols `0` and `1`, which is their representation in binary notation (by just adding a decimal/binary point in front). If you consider any enumeration of these infinite strings, it is always possible to define a string that is not in the enumeration, by using for its $n^{th}$ symbol the opposite (`1` for `0`, and `0` for `1`) of the $n^{th}$ symbol of the $n^{th}$ number of the enumeration. This means that if you attempt to define a one-one correspondance between the integers (used to enumerate) and the reals (being enumerated) there are always reals that are not included in the enumeration, which can be interpreted as implying that there are more reals than integers.

This technique is a diagonalization proof, similar to the proof technique used for proving the undecidability of the halting problem.

Now, as remarked in the question, any program texts can be read as an integer, so that one may consider there are no more programs than integers. This is why we may conclude that there are numbers that cannot be computed by a program, hence cannot be printed (else, each real could be mapped to the integer corresponding to the program that prints it.). But this fast reasonning may not be so convincing, so lets get more into details. and also consider an actual example.

Your printing device, assuming it does what you expect, even if it started at the big bang, is only producing digits one by one, and will at any time have produced only a finite number of digits, say $n$. That only defines a rational number, and even if we are actually printing some irrational number. Assuming we are using binary numbers, if we have already printed $n$ digits, they correspond to a rational number $x$, and all we know is that the number we ultimately print will be in the interval $\[x, x+2^{-n}\[$. But this interval will always contain an infinity of rational numbers, of computable real, and of uncomputable reals. And this will remain so for any future value of $n$. Stating that you want to print an uncomputable number, any uncomputable number, is a meaningless endeavor. It reminds me of people looking for the pot of gold at the foot of the rainbow.

**The meaningful problem is not to write any uncomputable number, but to write a specific one**, identified by a specific property. Consider for example the binary real $h\in\[0.0, 1.0\[$ defined as follows: its $n^{th}$ digit is $1$ iff the Turing Machine with Gödel number $n$ halts on empty input, and $0$ otherwise. This number is very precisely defined. But if it were computable, we would have a way to decide the halting problem. Hence, there is no algorithm, no program, that can enumerate the bits of the real number $h$, and thus there is no way to print it. And using random generators will not help.

Of course, it could be that some random generator, controlled by a random physical process such as radioactive decay would produce precisely that number (with a probability closing to zero as time passes). But, at best:

1- you would have at any time only a rational number which is a prefix of the non-computable real you are interested in

2- you would most likely be unable to check wether your prefix is really correct

3- you would have no garantee that the next digit will still be correct.

But, even then, you must assume that the random generator uses some physical "true" randomness source. Even randomly created, or computing with whatever technique known or yet to be invented, **no computer program can print an uncomputable real number**, such as the number $h$ defined above. That is a result of computability theory that no such program can exist.

Your only hope is that computability theory does not apply to radioactive decay or some other such physical phenomena. But I know of no proof either way. And it would not really help you in any meaningful way, because the probability of success is zero, and because you would have no way of knowing you are succeeding. Note that I cannot say "of knowing you have succeeded", because you never reach the end of that infinite process, so that any proof would have to be an on-going continuous process, which cannot be finitely defined for essentially the same reason a printing program cannot exist for an uncomputable number.
> 5 votes

# Answer
Not all real numbers can be printed.

Consider some system of representing numbers using a finite number of symbols. You can make this system as complex as you want: decimal numbers, fractions, roots, integrals, trig functions, etc.

Because there's a finite number of symbols in any system we have to write or print a number, we can create a bijection from the set of numbers we can write down to the integers.

Cantor proved that there is no 1:1 mapping from the integers to the real numbers. Which means, there are more real numbers than we can print.

Now, there are real numbers which we can't enumerate: that is, there's no algorithm saying "give me the first $n$ symbols of an infinite-length representation of this number.

The thing is, uncomputable numbers do exist. Your random generator could, by chance, generate the first $n$ symbols of an uncomputable number. But there's no way to check if those first $n$ symbols are correct, and there's no way to get the $n+1$th symbol, even if we have the first $n$ symbols.
> 2 votes

# Answer
This is not really an answer to your question, but a direct consequence from the fact that "$\mathcal{R}$ is uncountable", which may interest (or dismay) you.

> There are much more unsolvable (in terms of Turing-decidable) problems than solvable ones.

The argument is as follows:

The set of all algorithms (represented as Turing machines) is *countably infinite*, equinumerous to the set of natural numbers $\mathcal{N}$. We can each Turing machine into a string and count them one by one, e.g., in the order of the increasing string length (note that the alphabet $\Sigma$ is finite).

However, the number of all the problems (represented as languages) is $2^{\mathcal{N}}$ (it is the number of mappings from $\mathcal{N}$ to $\\{0,1 \\}$), which is *uncountably infinite*. It is impossible to count/print all the algorithms, just like it is impossible to count all the real numbers.

We conclude that some problems have no corresponding algorithms at all. Even worse, there are much more unsolvable problems than solvable ones.
> 1 votes

---
Tags: computability, integers, randomness, real-numbers
---


# Question
Title: Explanation of implementation of an algorithm for Dominating Set
I'm working on an application, in which users can use domination in graphs. I have already finished up with graph generation algorithm, I use lists to store vertices... So, I have found a well developed, gorgeous implementation of the needed algorithm.

It is a bit complicated for me, I would like to ask for some description for code above. How is it working? I would like to get only a short summary.

# Answer
> 2 votes
This algorithm just tries every subset of the vertices and calculates whether it is a dominating set. It tries the subsets in increasing order of size, and halts whenever it finds one.

Note that the running time is $O(2^n n)$ so it is exponential, and quite badly so. There are faster algorithms that compute dominating sets in $O^\*(1.7^n)$ or even $O^\*(1.5^n)$ time, but I don't recall whether they are implementable.

By the way, dominating set, being W\[2\]-complete, is not expected to have an algorithm running in time $f(k) \cdot \text{poly}(n)$ for any function $f$ where $k$ is the size of a minimum dominating set.

---
Tags: algorithms, graphs
---


# Question
Title: Difference between normal-order and applicative-order evaluation
The language I'm learning is Scheme and I'm working on an exercise that gives this:

```
(define (p) (p) )

(define (test x y) (if (= x 0)
                               0
                               y))

```

Then the question asks to evaluate the expression: (test 0 (p) ) and to comment on the behavior that would be observed under normal - order and applicative order evaluation.

These are my thoughts:

Under normal order, the program would evaluate the subexpressions before proceeding:

Thus `( test 0 (p) )` becomes:

```
(test 0 p)
( if (= x 0) 0 p))

```

Returning output `0`

The only difference in applicative order would be that the program would run as:

`( test 0 (p) )` becomes:

```
(test 0 (p))
( if (= x 0) 0 (p)))

```

Returning output `0`

Thus `(p)` would never be evaluated as it won't be needed.

Is this correct? Please let me know as I have almost no experience programming.

# Answer
> 23 votes
What research have you done to answer that question? I just plugged it as it is in Google, and got as second answer (the first may be as good, I did not check) a reference to a section of a bible on your topic: Hal Abelson's, Jerry Sussman's and Julie Sussman's Structure and Interpretation of Computer Programs (MIT Press, 1984; ISBN 0-262-01077-1), aka the wizard book. The reference is to the section "Normal Order and Applicative Order".

It states:

> Scheme is an applicative-order language, namely, that all the arguments to Scheme procedures are evaluated when the procedure is applied. In contrast, normal-order languages delay evaluation of procedure arguments until the actual argument values are needed.

and adds that the latter is called *lazy evaluation*.

So you have your definitions wrong, and taking one for the other:

* applicative order evaluates subexpressions when, i.e. just before, the procedure is applied.
* normal order passes subexpressions as they are, without evaluation, and proceeds with the evaluation only when the corresponding formal parameter is actually to be itself evaluated. (there is a further twist to it regarding environment issues ... but we better forget that at this point).

Furthermore, you do not properly understand the call mechanism which involves two things:

* the parameter passing mechanism, which include proper processing of actual arguments to the call, depending on the evaluation rule;
* the "replacement" of the call to the function by the body of the function (without the header).

In the case of **applicative order evaluation** of `( test 0 (p) )`, you are supposed to evaluate the argument subxpressions first. These are `0` and `(p)`.

* evaluation of a literal value like `0` yield that value.
* the second argument however is a procedure call to a parameter-less procedure called `p`. It has no parameter, so that we have no worry about evaluation order. Then, in order to pursue evaluation, we have to replace the call by the body of the procedure which follows the list of arguments, and then evaluate that body. The body of procedure `p`, as defined by the declaration `(define (p) (p) )`, is `(p)`, so that we are left with the evaluation of what we were just trying to evaluate. In order words, the evaluation process is caught in a loop, and will not terminate.

... and you never get to actually finish the call to the function `test`, since evaluation of its arguments does not terminate. Your program does not terminate.

This risk of non termination, even when the guilty argument will never be used in the call, is one of the reasons to use instead normal order evaluation, which may be a bit harder to implement, but may have better termination properties.

Under **normal order evaluation**, you do not touch the argument sub-expressions. What you do is replace the call `( test 0 (p) )` by the body of the function `test`, i.e. `(if (= x 0) 0 y)`, where the names of the (formal) arguments `x` and `y` are replaced by the corresponding actual arguments `0` and `(p)` (up to environment, or renaming issues, that are important but would complicate the explanation here, and are the main difference between the original Lisp and the Scheme language).

Hence you replace the evaluation of `( test 0 (p) )` by the evaluation of `(if (= 0 0) 0 (p))`.

Now the function `if` is a primitive function that usually always evaluate its first argument, but evaluates its last 2 arguments in normal order, evaluating only the useful one, depending on whether the first evaluates to *false* or *true* (actually `NIL` or `#f` for *false*, or some other value for *true*, in the case of Scheme - if my memory does not fail me). Since `(= 0 0)` evaluates to *true*, evaluation of the conditional amount to evaluating the yet unevaluated second argument, which is `0`, which unsurprisingly (except in old Fortran) evaluates to `0`.

Deep breath.

---
Tags: lambda-calculus, functional-programming, evaluation-strategies
---


# Question
Title: Greedy algorithm for Set Cover problem - need help with approximation
I want to approximate how close is the greedy algorithm to the optimal solution for the Set Cover Problem, which I'm sure most of you are familiar with, but just in case, you can visit the link above.
The problem is NP-Hard, and I'm trying to find a bound on how well does the greedy algorithm perform.
I know it looks a lot, but please bare with me. I pretty much did most of the work, I'm just missing that last small piece.

Here is the pseudo code:

Input: $U$ - set of elements, $F$ - family of sets s.t. $\bigcup\_{S\in F}S=U$
Output: $C$ - a family of sets; $C\subseteq F$ s.t. $\bigcup\_{S\in C}S=U$

```
initially C is empty

while U is not empty do:
    choose S from F that maximizes the cover of elements in U
    add S to C
    subtract S's elements from U

return C

```

The algorithm is pretty straight forward, and it is easy to see that it is indeed polynomial.

This is my attempt to approximate:
**Claim 1**: In a set $U$ of $m$ objects, that can be covered with $k$ sets, there has to be a set $S\subseteq U$ whose size is at least $\frac{1}{k}m$.
**Proof**: Trivial. (I decided not to prove it)

A corollary is that given the situation described in that claim, the greedy algorithm will choose a set whose size is at least $\frac{1}{k}m$.

**Claim 2**: Given a universe $U$, if there exist a cover of size $k$, then after $k$ iterations, the greedy algorithm will cover at least half of the elements, meaning at least $\frac{1}{2}n$ elements.
**Proof**: By claim 1, in the first iteration the algorithm will cover at least $\frac{1}{k}n$ elements. Upon entering the second iteration, there are at most $n-n\frac{1}{k}$ elements, and so the greedy algorithm will at least cover additional $\frac{1}{k}(n-n\frac{1}{k})$ elements. In general, on the $i$'th iteration, the algorithm will cover $\frac{1}{k}(n-n\frac{i-1}{k})$ elements. So after $k$ iterations:
$$\sum\_{i=1}^{k}\frac{1}{k}(n-n\frac{i-1}{k})=\sum\_{i=0}^{k-1}\frac{1}{k}(n-n\frac{i}{k})$$
$$=\sum\_{i=0}^{k-1}\frac{n}{k}-\sum\_{i=0}^{k-1}\frac{ni}{k^2}=n-\frac{n}{k^2}\sum\_{i=0}^{k-1}i$$
$$=n-\frac{n}{k^2}(\frac{k(k-1)}{2})=n-\frac{n}{2}(\frac{k-1}{k})\geq\frac{1}{2}n$$

OK, now this is where I need help: I know that in the first $k$ iterations, the algorithm picks at least half of the elements. After another $k$ iterations, another half was covered, out of what's left (meaning another $\frac{1}{4}n$). So in general, I know that the bound is $k\log n$, I just can't figure out how to formalize it.
What formula represents this behaviour? $T(ki)=T(\frac{1}{2^i}n)$ and solve for $i$? It didn't work...
What formula or equation should I solve to actually show that the number of iterations is bounded by $k\log n$?

# Answer
You have shown that if there is a set cover of size $k$ and there are $n$ elements left uncovered, then the greedy algorithm finds $k$ sets which cover at least $n/2$ elements, and so at most $n/2$ elements are left uncovered. You can prove by induction that if there is a set cover of size $k$ and there are $n$ elements left uncovered, then for each $t$, the first $tk$ sets found by the greedy algorithm cover all but at most $n/2^t$ elements. The idea now is to pick a value of $t$ such that $n/2^t \< 1$. Since the number of elements left uncovered by the algorithm is an integer, if the number $m$ of elements left uncovered satisfies $m \< 1$, then in fact $m = 0$, i.e., all elements are covered.

As a side note, you can actually improve on your reasoning and show that the first $k$ sets cover at least $(1-1/e)n$ elements, and so leave only $n/e$ elements uncovered. This improves the bound from your $k\log\_2 n$ to the sharp $k\ln n$, which is known to be tight (unless P=NP).
> 4 votes

---
Tags: algorithms, approximation, set-cover
---


# Question
Title: Primitive Recursion and course-of-values recursion - examples?
I ran into examples that I not trivially understand on course-of-values recursion,

> In defining a function by primitive recursion, the value of the next argument $f(n+1)$ depends only on the value of the current argument $f(n)$. Definition of functions by course-of-values recursion, $f(n+1)$ depends on value(s) of some or all of the preceding arguments $f(n),…,f(0)$. very basic examples of definition by course-of-values recursion are Fibonacci numbers...

My examples, from the computation course, wrote following $f\_1$ and $f\_2$ is Primitive recursive. I reproduce them here:

Let $g$ be a `primitive recursive` function,

1. $f\_1(0)=c\_1, f\_1(1)=c\_2, f\_1(x+2)=g(x,f\_1(x),f\_1(x+1))$, and
2. $f\_2(x)=c, f\_2(x+1)=g(x,\[f\_2(0),...,f\_2(x)\])$ are `primitive recursive`.

I couldn't say how $f\_1$ and $f\_2$ are Primitive Recursive? any idea to finding these are P.R.?

Edit 1: after the Yuval Hint the $f\_1$ is easy, but for $f\_2$ there is a problem, I try more than three days, but not capable to create an easy encode for $f\_2$. any hint or idea?

# Answer
The idea is to use some appropriate coding. A *primitive recursive encoding of pairs* is an encoding $\mathbb{N}^2 \to \mathbb{N}$, denoted by $\langle x,y \rangle$, such that the following functions are recursive: $e(x,y) = \langle x,y \rangle$, $p\_1(\langle x,y \rangle) = x$, $p\_2(\langle x,y \rangle) = y$. Coming up with a primitive recursive encoding of pairs is tedious but possible. Using such an encoding you can implement the first type of recursion in your question. The second type uses a more elaborate encoding scheme, which you can figure out on your own.

More explicitly, here is how you would implement a recursion of the first type: $$ G(x,y) = \langle p\_2(y), g(x,p\_1(y),p\_2(y)) \rangle \\ h(0) = \langle c\_1,c\_2 \rangle, \quad h(x+1) = G(x,h(x)) \\ f\_1(x) = p\_1(h(x)) $$ The trick in this case is that instead of computing the function $f\_1$ itself, we compute the function $h(x) = \langle f\_1(x), f\_1(x+1) \rangle$; the value of $h$ at the point $x+1$ only depends on its value at the point $x$.

For the second type, similarly we compute the function $k(x) = \[f\_2(0),\ldots,f\_2(x)\]$ instead of $f\_2$ itself; the value of $k$ at the point $x+1$ only depends on its value at the point $x$.
> 6 votes

---
Tags: computability, computation-models, recursion-theory, primitive-recursion
---


# Question
Title: I can not see why MSD radix sort is theoretically as efficient as LSD radix sort
Here is the pseudocode for LSD radix sort from http://www.cs.princeton.edu/~rs/AlgsDS07/18RadixSort.pdf

```
   public static void lsd(String[] a)
   {
        int N = a.length;
        int W = a[0].length;
        for (int d = W-1; d >=0; d--)
        {
             int[] count = new int[R];
             for(int i = 0; i < N; i++)
                   count[a[i].charAt(d) + 1]++;
             for(int k = 1; k < 256; k++)
                   count[k] += count[k-1];
             for(int i = 0; i < N; i++)
                   temp[count[a[i].charAt(d)]++] = a[i];
             for(int i = 0; i < N; i++)
                   a[i] = temp[i];
        }
   }

```

I guess that by 256 they mean $R$. We have a simple for loop, so the time is $\Theta(W(R+N))$ The reason why I use $\Theta$ is because the bound is tight, this is how many operations you will be doing no matter what, so it's worst case and best case performance at the same time. The space requirements are $\Theta(N+R)$

The following is the pseudocode of MSD:

```
    public static void msd(String[] a)
    {
        msd(a, 0, a.length, 0);
    }

    private static void msd(String[] a, int lo, int hi, int d)
    {
        if (hi <= lo+1) return;
        int[] count = new int[256+1];
        for (int i = 0; i < N; i++)
             count[a[i].charAt(d)+1]++;
        for (int k = 1; k < 256; k++)
             count[k] += count[k-1];
        for (int i = 0; i < N; i++)
             temp[count[a[i].charAt(d)]++] = a[i];
        for (int i = 0; i < N; i++)
             a[i] = temp[i];
        for (int i = 0; i < 255; i++)
             msd(a, l+count[i], l+count[i+1], d+1);
   }

```

Since the recursion we will stop recursing after $W$ levels in the worst case, the space complexity becomes $\Theta(N + WR)$

however what about time? Just from space itself, it seems like MSD is actually pretty bad. What can you say about the time? To me it looks like you will have to spend $R$ operations for every node in your recursion tree and also $N$ operations per every level. So the time is $\Theta(NW + R\*amountOfNodes)$.

I do not see how and why MSD would ever be preferred in practice given these time bounds. They are pretty horrible, but I am still not sure whether I get the time bounds in a correct way, for instance I have no clue how big is `amountOfNodes`..

Keep in mind that I would like the analysis to be in terms of R and N. I know that in practice R is usually small so it's just a constant, but I am not interested in this scenario, since I would like to see how much does R affect the performance as well.

I asked a kind of similar question yesterday but I did receive any replies, I think the reason for that was because my question was not well structured, so I could remove this question if the admins wanted. Thank you in advance!

# Answer
If I understand OP's question correctly - the question is what is the time-complexity estimate for MSD radix sort, taking into account what OP calls `AmountofNodes` or recursive frames for an MSD sort, which must fill the `count[]` array ($R$) per each recursive frame and than iterate through the `count[]` array to create subfiles. I couldn't find this in the literature and I presume jsguy hasn't found a satisfactory explanation either.

I'm going to assume we are talking about the Naive MSD sort as described in the OP's pseudo code. (otherwise if you have 20 items in a subfile and $R = 256$, a hash-table would be significantly cheaper than the `count[]` array).

From the looks of it worst case time-complexity for that should be $\Theta(NW + NR^{(W-1)})$, where each item is unique. Specifically a worst-case number of $R$ calls will happen if none of the recursive calls terminate early (before $W\_{i-1}$) and if a subfile is broken up as much as possible from the root (the maximum number of recursive calls started from any subfile is $R$).

Considering a set of subfiles $N$ - if the set is already dense duplicates only cost $W$ ($N \> R^W$ and all combinations appear), if the set is sparse ($N \< R^W$ and without duplicates), adding a duplicate costs at most $R(W-1)$ (if a single subfile would otherwise have terminated early at $W\_1$).

If the set $N$ is sparse, either some combinations will not diverge at level $W\_0$ (which is always more expensive than diverging at some further level $W\_x$) or as many as possible will diverge at each level but some will terminate before $W\_{i-1}$ because the branch will have only a single item remaining - therefore for sparse sets the worse-case is to have maximal divergence at each level $W$ until there are two duplicates in each subfile, for which the above estimate of $R(W-1)$ per item should apply.

---

**edit:** As to why people use MSD Radix sort, I hope someone that works with an application that utilizes Radix sort can answer that, I suspect there are cases like long RNA strings where there are very long strings with a very small $R$, and the ability to parallelize is an advantage (just a guess though). My worst case estimate definitely sounds pretty bad, but I think in practice no one tries to split a file of two duplicate items into $R$ buckets at every single $W\_i$.
> 2 votes

---
Tags: algorithms, algorithm-analysis, sorting, performance, radix-sort
---


# Question
Title: When can we assuredly say that a function is little o of some other function?
I'm trying to determine a function $f(x)$ that is $O(f)$ but not $o(f)$ and also not $\Omega(f)$. Note the $f$ used in the asymptotic notation is not the same as $f(x)$.

Originally I thought of $f(x)=\log(x), O(x)$ but I am not convinced that $o(x)$ is invalid for this function.

Previously I thought it was, because I could always come up with some constant $c$ that would bring the function $x$ below $f(x)$. However, I could say the same for $o(2^x)$ because surely there is some infinitesimally small constant that I can find that will put $2^x$ below $f(x)$ at a given value $x$. Any advice in this matter?

# Answer
> 2 votes
Your example doesn't work, since in fact $\log x = o(x)$. However, the function $\phi$ below is $O(x)$ but not $o(x)$ or $\Omega(x)$: $$ \phi(x) = \begin{cases} x & \text{if $\lfloor x \rfloor$ is even}, \\ 1 & \text{if $\lfloor x \rfloor$ is odd}. \end{cases} $$

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


# Question
Title: Going deeper with pseudo-polynomial time algorithm for set partitioning
If I have a set of (edit) **positive** integers, and I'm sure that the pseudo-polynomial time algorithm for partitioning the problem will not give me an answer - what would I do next?

To illustrate this problem let's take a look at this example: {`100,1,2,3`}.

The p-p algorithm will give an answer *False*, and then I can end with result: This set can be partitioned into two set with difference `100-6 = 94`

(The `6` is the last result from p-p algorithm on with \[`_`\]\[`vector.size()`\] = *True*, the `106` is the sum of all digits).

But what if I really would like to know the maximum by sum two-split of this set in which every subset has the same sum - for example the result that I'm looking for should be `3`. This set - {`100,1,2,3`} can be split (by bypassing the `100`) into two subset with the same sum - {`1,2`} and {`3`}.

How can I achieve this result?

# Answer
You can extend the dynamic programming algorithm to handle this variant. Suppose that the weights are $w\_1,\ldots,w\_n$. You are looking for a vector $x \in \\{0,\pm 1\\}^n$ such that $\sum\_{i=1}^n x\_i w\_i = 0$, and $\sum\_{i=1}^n |x\_i| w\_i$ is as large as possible. This suggests two possible approaches. The first approach is to construct a large table keeping track of all possible pairs of values $(\sum\_{i=1}^m x\_i w\_i, \sum\_{i=1}^m |x\_i| w\_i)$, where $x\_1,\ldots,x\_m \in \\{0,\pm 1\\}^m$. This leads to an $O(nM^2)$ algorithm, compared to the $O(nM)$ subset-sum or partition algorithms.

The second approach is to explicitly list all vectors $x$ such that $\sum\_{i=1}^n x\_i w\_i = 0$ (using dynamic programming), and choose the one maximizing $\sum\_{i=1}^n |x\_i| w\_i$. This takes time $O(nM + nS)$, where $S$ is the number of vectors $x$ such that $\sum\_{i=1}^n x\_i w\_i = 0$. In practice $S$ might be small enough for this approach to be practical.
> 2 votes

---
Tags: algorithms, dynamic-programming, greedy-algorithms, partitions
---


# Question
Title: Term rewrite system is non-confluent, but cannot find different normal forms of term
I wrote a simple TRS that I believe is non-confluent, but I'm not able to find a term with two normal forms for it.

The TRS is defined on the signature $\mathcal F=\\{f,\ l,\ s,\ o\\}$ and the rewrite rules $\mathcal R$ are defined as follows:

* $l\to s(o)$
* $t(x,\ l)\to s(x)$
* $t(l,\ x)\to s(x)$.

This TRS is clearly finite and terminating.

For the first two rules, we have a critical pair $(t(x,\ s(o)),\ s(x))$ which is not joinable. Therefore, the TRS is not confluent.

It seems that for such a simple example I should be able to find a term with two normal forms. What am I missing?

# Answer
> 0 votes
$t(o,l)$ has two normal forms: $t(o,l)\to s(o)$ and $t(o,l)\to t(o,s(o))$.

---
Tags: normal-forms, term-rewriting
---


# Question
Title: If $F$ is valid then $F \cup \{res(C_1,C_2,A_i)\}$ is valid
I have to prove the following problem in propositional logic:

Let $F$ be a set of clauses and let $F' = F \cup \\{res(C\_1,C\_2,A\_i)\\}$ be the extension of $F$ by a resolvent of some clauses $C\_1,C\_2 \in F$ where $A\_i$ is a literal occuring positively in $C\_1$ and negatively in $C\_2$.

Prove that: If $F$ is valid, then $F'$ is valid.

So in other words I have to prove that when I construct the union of the original formula $F$ and the formula resulting by applying resolution on $F$ over a literal $A\_i$ in $F$, validity is still preserved.

I think that this should be provable by applying a direct proof.

Recall: Note that resolution is defined as follows: given two clauses: $C\_1 = (A\_1 \lor \dots \lor A\_i \lor \dots \lor A\_n)$ and $C\_2 = (B\_1 \lor \dots \lor B\_j \lor \dots \lor B\_m)$ such that for some $i, j$ with $1 \leq i \leq n$, and $1 \leq j \leq m,\\; A\_i = \neg B\_j$,
the resolvent of $C\_1$ and $C\_2$ on $A\_i$ is the clause

$res(C\_1,C\_2,A\_i) = (A\_1 \lor \dots \lor A\_{i-1} \lor A\_{i+1} \lor \dots \lor A\_n \lor B\_1 \lor \dots B\_{j-1} \lor B\_{j+1} \lor \dots \lor B\_m)$

**EDIT:** Here is my try:

Let $I$ be an interpratation taken from the set of models $Mod(F)$. Hence, $I(F) = 1$. Because this interpretation satisfies $F$ it must also be the case that it satisfies $C\_1$ and $C\_2$. If we take a look at the structure of $C\_1$ and $C\_2$ we have to distinguish between $2$ different cases:

(1) $A\_i$ is positive in $C\_1$ but negative in $C\_2$ and

(2) $A\_i$ is negative in $C\_1$ but positive in $C\_2$.

In case (1) if $A\_i$ is set to true in $C\_1$ it would be false in $C\_2$. In case (2) if $A\_i$ is set to true in $C\_2$ it would be false in $C\_1$.

$A\_i$ cannot be the literal which preserves satisfiability of $F$. Hence $I$ must include some assignment of other literals in $F$ such that $F$ is satisfied. Thus, the resolvant $res(C\_1,C\_2,A\_i)$ is also satisfied.

# Answer
> 2 votes
Since you are only asking for a hint:

You have to prove that, for any interpretation I, if it satisfies all the clauses in $F$, then it also satisfies the resolvant $res(C\_1,C\_2,A\_i)$, and hence it satisfies all the clauses in $F'$.

From that you can infer the result to be proved, with some universal quantification.

Note on terminology and notations:

* I would rather say that, when $F$ is valid, every interpretation satisfies it. It is $F$ that is to be satisfied, not the interpretation. Or more generally, it may also be a clause $C$, a literal $A\_i$, or a set of clauses $F$ that may (have to) be satisfied.
* $F$ is valid iff for any interpretation $I$, $I(F)=1$.
You should not say "*for any interpretation $I(F)$*", since as you noted yourself, $I(F)$ is a truth value. An interpretation in propositional logic is (usually) an assignment of truth values to the symbols used in the clauses, i.e. a mapping of the set of symbols to the set of truth values. It also implies interpreting logical connectives in the usual way, and sets of clauses as a conjunction of the clauses. Then, truth tables allow you to associate truth values to each construct, up to the whole set of clauses, which is what is meant by $I(F)$. The interpretation is $I$. while $I(F)$ is the truth value it gives to the set $F$ of clauses.

Interpretation may be defined in a more general way, but the above should be enough here.

---
Tags: logic, propositional-logic, logical-validity
---


# Question
Title: Recursive algorithm to compute a sum of product like function
I am working on a recursive formula associated with discrete mathematics which seems very difficult to compute. The formula is as follows

$F\_{i,j}(m)=\sum\_{t=j}^{m}\left \[ x\_{ij}.\sum\_{k=1}^{m}\sum\_{l=j-1}^{m} F\_{k,l}(m-ij) \right \]$

It's given that $F\_{i,j}(m)=0$ for $m\<0$.

Here $x\_{ij}$ is defined as a random number with the property that $0\<x\_{ij}\<j$.

How do I write a recursive algorithm to compute $F\_{i,j}(m)$?

# Answer
> 1 votes
Assuming we are given the $x\_{ij}$'s and $i,j,m$, your formula already *is* a recursive algorithm to compute $F\_{i,j}(m)$. If you use dynamic programming (memoization) to avoid re-computing $F\_{i',j'}(m')$ more than once for any given tuple $(i',j',m')$, the running time will be $O(m^3)$, since you only evaluate $F\_{i',j'}(m')$ for tuples $(i',j',m')$ where $0 \le i',j',m' \le m$.

If the $x\_{ij}$'s are not given, your question is not well-defined. If that's what you meant, it's possible you might be asking for us to compute the *distribution* of $F\_{i,j}(m)$, but if so, the question needs to be edited accordingly.

Either way, I suspect that there must be some additional base cases you have not provided. As it currently stands, the solution $F\_{i,j}(m)=0$ for all $i,j,m$ satisfies your equation. I suggest you edit your question to specify the missing base cases.

---
Tags: algorithms, computability, recursion
---


# Question
Title: What's the difference between declarative syntax and encapsulation?
I had been first introduced to the idea of declarative syntax when using Angular JS. From what I understand, the idea is that you say, "do this" instead of "in order to do this, do this, this and this". You don't care how it's done, you just want it done, and you pass it off to some lower level of abstraction to do.

Now I'm going over the idea of encapsulation as I learn Java, and the idea seems very similar. From what I understand, the idea is that you break things up into modules, and you define an outwards-facing API for people to use. So people could use your *in a declarative manner* to say, "do this".

Is this true? If so, what is the real difference between declarative syntax and encapsulation? Just that one describes syntax and the other describes the more abstract design philosophy?

Edit: I think that my question boils down to: what's the difference between making a declarative statement and making an API call?

# Answer
They're orthogonal.

In declarative programming, you describe what would count as an acceptable solution, without necessarily describing how to find it. For instance, a declarative program might have rules like "if you want to install the package `gcc`, you must have first installed the `binutils` and `cpp` packages" and "if you want to install the `binutils` package, you must have first installed `coreutils`". It's up to the platform to figure out a way to meet all of these constraints.

Encapsulation refers to protections that prevent the client of an API from tampering with the internal state of the service that implements the API. Nothing here says the API has to be declarative in nature. You could have a API that is more declarative in nature (e.g., the client provides some constraints, and the service figures out how to meet them), or you could have an API that is more operational in nature (e.g., the client specifies what actions should be performed, rather than listing the desired goal and leaving it to the service to figure out what actions will accomplish that goal).

So, you can have an encapsulated API that is not declarative in nature.

---

To elaborate: invoking an API is not necessarily declarative in nature. You can design APIs that are declarative in feel; and you can also APIs that are operational in feel. Not all APIs will be declarative. For example:

* A declarative API might let you give it some rules/constraints, and then specify the goal (I want gcc to be installed), and then let the service infer a sequence of actions that will achieve your goal (a sequence of packages to install, and what order to install them in). For example, the client might call `findWayToInstall("gcc")`, and the service comes up with a sequence of packages to install that ends with gcc installed -- that'd be a declarative API.
* An operational API might let you repeatedly give it an action to perform (e.g., you repeatedly invoke `installPackage()`; this succeeds if you've met all the prereqs, and it's up to you to identify a valid sequence of packages that ends with gcc installed). For example, the client might call `installPackage("coreutils")` then `installPackage("binutils")` then `installPackage("cpp")` then `installPackage("gcc")`, and if this sequence of operations meets all of the prerequisites, it ends with gcc installed. With this API it is the caller's responsibility to identify a sequence of actions that ends with gcc installed. Thus, this kind of API is more operational than declarative in nature.

Of course, declarative vs operational are just concepts to help us talk about properties of programming languages and APIs. There's no hard, bright line between them. It's not black-and-white; there's a spectrum. But they are useful concepts nonetheless.
> 4 votes

# Answer
## In a nutshell

My first impulse was to agree with D.W.'s answer that the two concepts are orthogonal. On second thought, I think it is only partially true, and I will also try to argue that they are two sides of the same coin.

In first approximation, **declarative programming** just specifies what you want and lets the system find how to get it, while imperative programming gives precise instructions to the system that ensure you get the result you want. In practice, you usually have a mix of both. You may add hints to your declarative programming so that the system can better find how to do it. Conversely **imperative programming** often includes high level concepts that let you skip over some details that are automatically handled by the system.

Since encapsulation helps you increase the number of high level concepts that you can use just as needed, it is quite fair to consider that encapsulation also supports a more declarative form of programming.

To put it another way:

**Declarative programming** assumes that the compiler/interpreter will include something like a theorem prover or a solver that will find how to do it from a specification of what is to be done.

**Encapsulation** is a way, for some predefined cases, to have the proofs already prepared and applied as code in the encapsulation. The specification of what is to be done hiding the internal description of how to do it.

Denotational semantics does not make a difference between $3+4$ and $7$. Should we then consider that there is much difference between a proof and code to be done and a canned proof and code already done?

In that respect, one can consider, as does the author of the question, that encapsulation has strong similarities to declarative programming.

But this is also to a large extend a matter of style, and of interpreting what is written.

BTW: I do not like very much the expression "declarative syntax". The issue is very much a semantics issue. "Declarative style" would be a more appropriate expression.

## Declarative programming

To better explain my understanding of declarative programming, I will try to use, as much as I understand it and somewhat loosely, the Curry-Howard isomorphism. One basic idea of this isomorphism is that it describes a correspondence between programs and proofs, and between program specifications and theorems.

So a program may be read as a (constructive) proof of its specification. Conversely, given a mathematical statement with some existentially quantified variables, you can turn it into a theorem by providing a proof, and if you limit yourself to constructive proofs, you can extract from that proof a program that actually tells you how to make the statement true.

For example if the statement is $\forall a,b,c \in \mathbb C,\\; \exists x\in\mathbb C,\\; ax^2+bx+c=0$, you can extract from the proof an operational way of solving second degree equations. In some cases, the proof may work only under some conditions, which will be conditions you impose on the data for the program to run.

BTW The word algorithm comes from the name (of the home town) of a Persian mathematician who was solving equations. It is all consistent.

Some research on automated program generation consists precisely in taking the specification of a program as a theorem to be proved, in some appropriate formal theory. A proof assistant will record all the formal steps of the proof, which can be partially automated, and then the program meeting the specification is extracted from that proof.

Ideally (sometime in the future in most cases), if the whole process is fully mechanized with a theorem prover and does not need human intervention, you can just specify your program, as use the system to compile the specification into running code.

This approach is the ultimate declarative programming: you describe what you want, but not how to get it. An you can leave it to some kind of deductive system the task of determining the steps to achieve the desired results.

This is used in practice, not so much to mechanically generate complex programs, but to handle automatically simple problems without requiring the programmer to specify all the operational steps. To take a trivial example, the steps for bootstrapping a compiler written in its owns language with an interpreter can be found automatically by a small logic program. And computer science has many other examples, in very specialized area where it is tedious, but easy, to determine the steps needed to achieve a result.

## Encapsulation

The principle of encapsulation is to take some meaningful subpart of a program, and represent it by an interface which actually specifies it, so as to hide the way it is actually implemented. The specification includes precise interfaces (API) to use the encapsulated code, but may also include other information, assertion, or formal mathematical statement about the API, that fully specifies what it is supposed to do, and possibily some pragmatic properties regarding performance, or even some assertions about complexity. Of course, such full specification are not so common.

This has several purposes. It gives a precise specification of part of a program, abstracting away the implementation details so as to simplify reasonning by considering only high level concepts and properties defined in the interface. It allows easy reuse of the encapsulated code in other program. It allows making improvements to the encapsulated program without affecting the larger programs that use it, as long as the specification is respected by all. And more ... but let's stay on topic.

Once you have encapsulated some concepts, you can use the encapsulation in any program so as to have the concepts available for programming without having to tell more about the details of their implementation. Note, in passing, that the high level language compiler also provides that kind of service.

If you see your program as a proof, it becomes a simpler proof, with less details, thus closer to the specification it proves. So in this sense, the encapsulation helps you to be more declarative. You use only its specification, and forget the implementation which is only a canned proof of that specification (so you can forget the theorem prover).

Now, the API provided by an encapsulation may be seen as more or less declarative, as explained by D.W. depending on whether the primitive operations it provides seem to be more specification of what should be done, or low level operational steps.

The distinction is important, as trying to be more declarative may have a impact on the properties of your program (readability for example). But it is also very much in the eyes of the beholder.

By nature, an encapsulation will be somewhat more abstract, higher level, that what it is implemented with. In that sense it is necessarily more declarative.

Another point is that asking for an equation to be solved is a very declarative kind of thing to do. But how different is the call `solve2(a,b,c)` to solve a second degree equation from the call `matrix3(a,b,c)` to make a 3-dimensional matrix, which may be seen as very operational.

Programmers tend to consider that thing are more declarative when using logical rules, constraints, equation, that have to be applied or resolved, rather than computation steps to be executed.

But even these distinctions are not always clear cut.

My favorite example is context-free grammars. Most people learn to see them as rewriting systems, which are a rather operational kind of object. All the words are generated by rewriting other words. But a context-free grammar may equally be seen as a set of language equations, which is a very declarative kind of thing.

Note that this answer in not in contradiction with D.W.'s answer. But I do believe that your initial concern was well justified. There is a matter of style, of feel (says D.W). But there is also a matter of level of discourse. The higher the level, the less you need to prove, and the more declarative you are. And encapsulation helps that, by providing high level definitions. That was my reason for bringing in the Curry-Howard isomorphism and automated programming.
> 1 votes

---
Tags: programming-languages, object-oriented, api-design, design-patterns
---


# Question
Title: Showing that $\{ c^n a^m b^{n+m} : n+m \geq 6\}$ is not regular
I'm trying to show that $L\_6=\\{c^n a^m b^p : n+m=p,p \geq 6\\}$ is not regular. I need a little help, I was practicing the pumping lemma, and I encountered this language, I saw these conditions and got totally confused, what to do now?

Earlier I showed that $L\_5=\\{a^n b^n : n≥0\\}$ is not regular. In this Language it was very simple to choose $w$, namely $w= a^pb^p$, where $p$ is the pumping length. But this new Language is complicated, so I thought you guys could help me out.

# Answer
If $L\_6$ were regular, then so would the following language be: $$ (L\_6 \cap a^\* b^\*) \cup \\{ \epsilon, ab, a^2b^2, a^3b^3, a^4b^4, a^5b^5 \\}. $$ However, this language is none other than $L\_5$.

You can also use the pumping lemma. Try to pump the word $c^qa^qb^{2q}$ for large enough $q$.
> 3 votes

---
Tags: formal-languages, regular-languages, pumping-lemma
---


# Question
Title: How to prove that these two languages are regular, or not regular?
I have these two languages

$L\_1={\\{a^n b^m,n≥m+5,m\>0}\\}$ Where $∑=(a,b)$

$L\_2={\\{a^n b^m,n≥m+5,m≤5}\\}$ Where $∑=(a,b)$

As you can see that there is only one difference, the condition of `m` is different.

My question is to determine whether these two languages are regular or not, and to prove it.

If one or both these languages are non-regular. then how can we prove that using pumping lemma?

These two languages have so many conditions, I am just confused that how to solve these kind of Languages.

# Answer
> 1 votes
For problems like this, where there are several constraints, it can be helpful to deal with the constraints separately. In this problem, look at what the languages can be for each value of $m$ and recognize that the original language can be expressed as the union of the languages for each value of $m$.

Consider first your $L\_2$. For each $0\<m\le 5$, consider the languages $$ A\_m=\\{a^nb^m\mid n\ge m+5\\} $$ So $A\_0=\\{a^n\mid n\ge 5\\}$, $A\_1=\\{a^nb\mid n\ge 6\\}$, and so on. It's easy to see that each $A\_m$ is regular. It's also easy to see that $$ L\_2=A\_0\cup A\_1\cup A\_2\cup A\_3\cup A\_4\cup A\_5 $$ and since $L\_2$ is the finite union of regular languages, it must be regular, as @babou implied.

For $L\_1$ we can do the same thing, expressing $$ L\_1=\bigcup\_{m=1}^\infty A\_m $$ but that doesn't seem to be of much help, since the infinite union of regular languages isn't necessarily regular. We thus guess that $L\_1$ is not regular, so we'll try to use the Pumping Lemma to prove that it isn't.

Let $L\_1=a^{p+5}b^p$ where $p$ is the integer of the pumping lemma. Them we can express $L\_1=xyz$ with $|y|\>0$ and $|xy|\le p$. This means that $y=a^k$ for some $1\le k\le p$. Now pump down: $xy^0z=a^{p+5-k}b^p$ and since $n=p+5-k\<p+5=m+5$ the string $xy^0z\notin L\_1$ which is the contradiction we need, so $L\_1$ isn't regular.

# Answer
> 1 votes
Hints:

One of the two languages is not regular. It is the one that forces you to count beyond 10 to decide whether some strings are in the language. Regular languages are not very good at counting without bound.

However, the use of the pumping lemma to prove it requires that you start from a string in the language where $n$ is as close to $m$ as permitted by the definition of the language, and that you pump out rather than in, i.e. remove the only $w$ of the $xwy$ decomposition of the string, rather than inserting more copies of $w$.

Alternatively, you can prove that the reverse of the language is not regular, if you know about closure properties.

---
Tags: formal-languages, regular-languages, automata, pumping-lemma
---