# Question
Title: Specific Examples with Explanation of Similarities and Differences of how Distance Functions are used Across Different Fields
I took a tangent from a student project I had done a number of years ago and spent some time studying distance functions.

(please note that the above link contains the full question with links as I don't have sufficient reputation to post more than two links)

I found this textbook on data mining which includes a chapter on Similarity and Distances (chapter 3 of *Data Mining The Textbook* by Charu C. Aggarwal)

And so the text says:

> Sometimes, data analysts use the Euclidean function as a “black box” without much thought about the overall impact of such a choice. It is not uncommon for an inexperienced analyst to invest significant effort in the algorithmic design of a data mining problem, while treating the distance function subroutine as an afterthought. This is a mistake.

And so there are a number of sections addressing quantitative data, categorical, text, etc.

I'd be curious about how distance functions are used in similar and different ways across varied fields such as data mining, machine learning, computer vision, natural language processing, error-correcting codes, or for example in specific applications like spell checkers.

On the one hand, in my independent study, I saw various passages speaking about the necessity of applying domain knowledge.

From 3.6 Supervised Similarity Functions of the above mentioned book:

> In practice, the relevance of a feature or the choice of distance function heavily depends on the domain at hand.

Also in An Introduction to Statistical Learning with Applications in R they mention:

> The choice of dissimilarity measure is very important, as it has a strong effect on the resulting dendrogram. In general, careful attention should be paid to the type of data being clustered and the scientific question at hand. These considerations should determine what type of dissimilarity measure is used for hierarchical clustering

Section 10.3.3 Practical Issues in Clustering also talks about some related issues.

On the other hand I took a brief look at this Ph.D. thesis by Ofir Pele on distance functions, and so at the beginning it says:

> Our proposed methods have been successfully used both by computer vision researchers and by researchers in other fields. The success of the methods in other fields is probably because the noise characteristics in those fields are similar to image noise characteristics.

which suggested to me that there could be some overlap in different cases; however, I haven't read those papers in detail.

Anyway, the question is: what are similarities and differences in how distance functions are used among disparate fields, and in what ways do those similarities and differences arise.

## Few Thoughts on this Question

I thought to myself this may be a bit of an unusual question. After all people don't generally study looping in Java, Python, Lisp and Prolog and then go on to study variable declaration in five other programming languages. People more often study one particular programming language as a whole not a certain construct in multiple ones. But on the other hand within programming languages as an academic discipline at universities people might certainly talk about similarities and dissimilarities. Those very similarities and differences could be seen in light of differences as to whether the code is (usually) interpreted or compiled, or whether it tends to favor an imperative style or a recursive one. One might also seek to see how various characteristics developed within the evolution of programming languages throughout history and how different programming languages built on earlier ones. Certain design decisions could very well derive from certain goals: ease of learning, readability, speed, verifiability.

Similarly in human languages people don't usually study a set of words or phrases in multiple human languages but usually study one particular human language as a whole. Yet linguists might certainly study similarities and differences in particular words or phrases across languages as that can be indicative of how various human languages evolved and could also be indicative of various aspects of culture. I could also mention that browsing through Encyclopedia of Distances I read about how linguists have sought to create ways to measure distances between languages.

Also, as a practical application of such a cross-sectional approach within human languages, one might think of the airline and travel industry where employees learn how to say particular words and phrases in multiple languages so that it is possible to communicate with the passengers.

So anyway I think such comparisons could be interesting.

I could mention that I don't think it's necessary to have a huge number of examples. I think a few would be fine with some brief explanation. I think perhaps more interesting than a lot of breadth would be how constraints, goals, or the problem domain lead to different approaches. I'm not an expert at all in any of those fields, so I may not be familiar with some of the terms. For people who find this page later on and are trying to find more details there can be a few resources listed such as books, websites, or search strategies.

I've thought about how I might answer this question based on my independent study and what I looked into, so I could seek to work on my response tonight and probably tomorrow. As long as the question meets the site guidelines perhaps there could be then at least one response. Other responses though might be more comprehensive, more incisive and trenchant, or better educationally. So a better response would be more deserving of the credit from the asker and also reputation points.

I was thinking of waiting a week or two before awarding an answer; however, if a response is made beforehand which I think is good I could just decide to award it to that one.

There also might be a response before I post mine, and so if that one is good and I haven't finished mine I might not post mine at all.

Hope this meets the site guidelines, but if not let me know.

# Answer
Okay, so here are some of my thoughts along with some links to some of the things that I found interesting in my independent study.

(please note that a version with additional links is available on GitHub)

In multiple books I found sections speaking about clustering. In particular within these three books:

* *Introduction to Artificial Intelligence* by Mariusz Flasiński
* *An Introduction to Statistical Learning with Applications in R* by Gareth James, Daniela Witten, Trevor Hastie, Robert Tibshirani
* *Data Mining: The Textbook* by Charu C. Aggarwal

there are sections speaking about hierarchical clustering.

For hierarchical clustering one can use an arbitrary dissimilarity measure and so they talk about that choice.

It's not as though one dissimilarity measure predominates in artificial intelligence, another in statistical or machine learning, and then a third in data mining, but the dissimilarity measure is determined by the data, and what the data means in the context of the situation.

In the statistical learning book an example is given in the section on hierarchical clustering of how an online retailer might prefer a correlation based dissimilarity measure to the Euclidean distance. Clustering together shoppers who purchase less from shoppers who purchase more may not be as desirable as clustering together shoppers who purchase similar items.

In the data mining textbook an example is given of how the cosine measure can be used as a comparison between texts. That section speaks about how with a bag-of-words representation document length would be prominent. That wouldn't necessarily be desirable as similar documents on the same or similar subjects but with different lengths wouldn't get grouped together.

In any event, as stated above, the dissimilarity measure is not determined by the field and nor is it being determined by the domain (say medical, legal, business, etc.), but is being driven by the nature of the data and what that data means.

In the case of hierarchical clustering then, if the algorithm is the same and the dissimilarity measures are being driven by the data (so they could certainly by the same across the three fields), then for that case these three fields are using distance functions in similar ways.

To go out on a tangent, this raises a question in my mind concerning what are the distinctions between these three fields (and perhaps other fields).

I thought it was interesting to read in the lead of the Wikipedia article on data mining that the title of a book was changed from *Practical machine learning* to *Data mining: Practical machine learning tools and techniques with Java* and the reason given was that it was largely for marketing purposes.

And so the Wikipedia articles on machine learning and data mining both say that those terms are buzzwords. The end of the lead for the article on machine learning speaks about how projects may fail to work because the problems can be difficult.

On that note I found it interesting in my independent study to read in the Wikipedia article on the history of artificial intelligence how the initial optimism and few strings attached funding was then met with disappointment in the mid to late 1970's. So the article speaks about various failures (machine translation) and also successes (the DART battle management system).

In terms of distinctions between the three fields the Wikipedia article on machine learning states:

> Machine learning is sometimes conflated with data mining, where the latter subfield focuses more on exploratory data analysis and is known as unsupervised learning

Yet on the other hand in *Data Mining: The Textbook* the preface speaks of classification as being one of the four main super problems of data mining where it seems to me that classification as defined in chapter 10 of the book is basically supervised learning.

In any event it suggests in my mind that the distinctions between these three fields might be a bit fuzzy, and the example above indicates that naming decisions could be driven by a variety of factors including marketing.

Based on my independent study, to my ear, artificial intelligence being the first term coined, carries with it a connotation of a more theoretical field while machine learning and data mining are more focused on developing practical solutions.

In the text on artificial intelligence chapter 17 includes a section called Determinants of AI Development where artificial intelligence is seen as drawing from such fields as: computer science, biology, neuroscience, physics, mathematics, logics, philosophy, linguistics, and psychology.

There's a discussion of Searle's Chinese room, strong AI and weak AI, and a chapter on theories of intelligence in philosophy and psychology. There's a brief section on artificial intelligence as it pertains to social intelligence, emotional intelligence, and creativity.

In Russell and Norvig's book *Artificial Intelligence: A Modern Approach* there is a chapter on philosophical foundations.

In comparison within *Data Mining: The Textbook* privacy is addressed but essentially as a technical problem.

In *Elements of Statistical Learning* (from which the above mentioned statistical learning book is based) the chapters look to be all of a technical nature.

So I think this sentence from History and relationships to other fields section of the machine learning article is consistent with that assessment:

> The field changed its goal from achieving artificial intelligence to tackling solvable problems of a practical nature.

Thinking back to the article on the history of artificial intelligence one might wonder about how various funders of different kinds (government, corporate, philanthropic, etc.) began to see AI as a longer term prospect while machine learning and data mining were more likely to produce working results more quickly.

I was curious about books in these three fields that were written from the perspective of a particular domain (medical, business, legal, etc.). So I did Google searches of the form: `textbook <field> <domain>` for field being either artificial intelligence, machine learning, or data mining, and domain being either medical, business, or legal. So a variety of different books have been written from the standpoint of a particular domain.

Data miners might be able to apply domain knowledge in the course of exploratory analysis, or in other kinds of analysis.

---

So back to distance functions.

I see a difference in the way distance functions are used in hierarchical clustering within the fields artificial intelligence, machine learning, data mining and applications discussed in Ofir Pele's thesis within computer vision (which could be seen as a subfield of machine learning). Simply put various applications of the distance functions developed do not involve clustering. This is true for the multiple view geometry application mentioned at the beginning of the abstract for the thesis.

In error-correcting codes the simple concept of Hamming distance is used; however in this case it seems to me that unlike the hierarchical clustering case no distance function choice is going on. Hamming distance arises from the mathematical model which in turn is from the physics of information transmission over noisy channels.

In the case of a spell checker a simple implementation could just list words that are say 1 or 2 hops away under the edit distance; however, a more sophisticated approach can work better.

Spell checkers can take into account properties of language, keyboards, common errors, etc.

At another level of sophistication one could have spell checkers that seek to automatically learn characteristics of users so as to improve suggestions and other aspects of performance.

In the case of a spell checker it doesn't seem to me that a distance function is necessarily warranted or helpful.

If a mathematical concept doesn't seem useful for an application then one doesn't have to use it.

---

I also wrote a summary of my independent study including listings of some of the various sources I went through:

Summary of Independent Study (link removed, see top of response)

There is also an extended response which is available here:

Extended response to distance function question on CS StackExchange (link removed, see top of response)

The length of the extended response ended up growing to a size of about 14 regular pages, so I can summarize what it is about:

In the extended response I continue the tangent in the middle which starts by comparing the fields of artificial intelligence, machine learning, and data mining. I speak about the question of whether research has shifted from universities to companies, the factor of motivation in education, economic systems and other systems for the organization of labor, social hierarchy, economic inequality, and climate change.

To a certain extent I wonder if I did not entirely follow my own advice in terms of more breadth rather than depth; however, perhaps that's partly just the nature of the Internet.

I didn't do any portions of this for a class, but worked on it over the past few days. I brought in things that I had seen or read over the years.

I think that a lot of various other people have probably had similar thoughts and questions.
> 0 votes

---
Tags: algorithms, algorithm-analysis, computer-vision, data-mining, clustering
---


# Question
Title: What is the time complexity of text justification algo?
The following algo is a simplified version of a text justification algo taken from dynamic programming lecture notes of MIT OCW.

I am confused why this particular algo has a time complexity of $\mathcal{O}(n^2)$ and not of $\mathcal{O}(n!)$ -:

```
function foo(int index) {
//some constant time operation like 2+2
       for( i = index + 1 to end ) {
           foo(i);
           }
}

```

Lets say `end` is 10.

So if `foo(0)` were called, the sequence of function calls would be something like this (*correct me if I am wrong*)-:

```
foo(0) = 9 calls to foo using (1 to 9)
Each foo(1) = 8 calls to foo using (2 to 9)
Each foo(2) = 7 calls to foo using (3 to 9)
and so on...

```

So it is $n * (n-1) * (n-2) ... * 1$ = $n!$

So shouldn't the **time complexity be $\mathcal{O}(n!)$ ?** Instead I find that in most cases this algorithm is represented as $\mathcal{O}(n^2)$.

Why is that ?

The original version was of the follwing form-:

```
DP[i] = min{DP[j] + badness(i,j), for (j in range(i+1,n+1))}

```

Where `badness = (page width - total width of string) ^ 3`

# Answer
> 2 votes
There are two problems, here. Your `foo` algorithm doesn't have $\Theta(n!)$ complexity and it isn't the proper tranlation of the dynamic programming system.

`foo(0)` makes calls with arguments $1, 2, \dots$. The call to `foo(1)` makes calls with arguments $2, 3, \dots$. So now we have two outstanding calls to each of `foo(2), foo(3), ...`. Each call to `foo(2)` one more call for $3, 4, \dots$, so we now have four outstanding for each of those. Thus, `foo(i)` gets called $2^{i-1}$ times. The total number of calls is $\sum\_{i=1}^n 2^{i-1}=2^i-1$.

But the main problems is that your `foo` isn't what the dynamic programming system does. The whole point of dynamic programming is to avoid making the same recursive call many, many times. To do this, you remember the results of the function in an array, precisely so you don't have to call the function again. You can see this in the code fragment you posted: `DP[j]` isn't a function call, but an array look-up.

# Answer
> 0 votes
This pseudo code is recursive version of the problem, as you said in mathematical form. This is definitely not $O(n^2)$. Note that you compute $DP(i)$ more than once which is known as **overlapping problems**. That's why the time complexity grows very fast.

What you need is compute $DP(i)$ only once for each $i$ storing them in a table. This is the gist of DP. In your case, given $n$, you have to compute $DP\[n\]$, then compute $DP\[n-1\]$ using $DP\[n\]$, then $DP\[n-2\]$ using $DP\[n-1\]$ and $DP\[n\]$, and so on. Since $1+2+\dots + n = \frac{(n+1)n}{2}$, its complexity is $O(n^2)$.

Example: for $n = 4$

$DP\[4\] = 0$

$DP\[3\] = \min \\{DP\[4\] + badness(3,4)\\} = \min\\{ 0 + badness(3,4)\\} = badness(3,4)$

$DP\[2\] = \min \\{DP\[3\] + badness(2,3), DP\[4\] + badness(2,4)\\} = \min\\{badness(3,4)+badness(2,3), badness(2,4)\\}$

$DP\[1\] = \min\\{DP\[2\] + badness(1,2), DP\[3\] + badness(1,3), DP\[4\] + badness(1,4)\\} = \\{\dots\\}$

---
Tags: runtime-analysis, dynamic-programming
---


title: Mathematical equivalent of reduce()?

text:
# Question
Title: Mathematical equivalent of reduce()?
filter() in functional programming can be thought of as being analogous to an equation that *filters* the range of the variable.

map() can be through of as a function mapping domain to codomain.

reduce() is the only one I have a problem with. To me it just seems to be a special instance of map / function, where $R^{n} \rightarrow R^{1}$.

Is there a unique general mathematical concept / object associated with reduce()?

# Answer
**Map** applies a unary function to each element in the sequence and returns a new sequence containing the results, in the same order

$$\mathrm{map}\colon (E\to F) \times \mathrm{Seq}\langle E\rangle \rightarrow \mathrm{Seq}\langle F\rangle\\,.$$

**Filter** tests each element with a unary predicate. Elements that satisfy the predicate are kept; those that don’t are removed.

$$\mathrm{filter}\colon (E \rightarrow \mathrm{boolean}) \times \mathrm{Seq}\langle E\rangle \rightarrow \mathrm{Seq}\langle E\rangle\\,.$$

**Reduce** combines the elements of the sequence together, using a binary function. In addition to the function and the list, it also takes an initial value that initializes the reduction, and that ends up being the return value if the list is empty.

$$\mathrm{reduce}\colon (F \times E \rightarrow F) \times \mathrm{Seq}\langle E\rangle \times F \rightarrow F\\,.$$

Example:

\begin{align\*} \mathrm{result}\_0 &= \mathrm{init} \\ \mathrm{result}\_1 &= f(\mathrm{result}\_0, \mathrm{list}\[0\]) \\ \mathrm{result}\_2 &= f(\mathrm{result}\_1, \mathrm{list}\[1\]) \\ &\ \ \vdots\\ \mathrm{result}\_n &= f(\mathrm{result}\_{n-1}, \mathrm{list}\[n-1\]) \end{align\*}

Hence you can see it as a function $\mathbb{R}^n \rightarrow \mathbb{R}$

Source: http://web.mit.edu/6.005/www/fa15/classes/25-map-filter-reduce/
> 1 votes

---
Tags: functional-programming, mathematical-foundations
---


title: RAM and the degrees of freedom

text:
# Question
Title: RAM and the degrees of freedom
This question is about computation/computational physics.

Imagine that you want to solve $10^6$ equations of motion, and you have $10^6$ degrees of freedom (position of the particle).

How many RAM memory would you need (theoretically) to do this?

(I am not interested in the final answer, I am just interested in the thinking of estimate this.)

Thank you

# Answer
As a first approximation, most of the memory will be spent on storing $10^6$ floating point numbers (one per degree of freedom). Assuming double precision numbers are used, each number takes up 8 bytes, for a total of 8MB.
> 1 votes

---
Tags: memory-management, memory-hardware, virtual-memory
---


# Question
Title: Understanding commutativity and associativity for primitive types
In Elements of Programming Interviews, authors talk about a tip for understanding how to use primitive types (`int`, `double`, etc).

> Be aware that commutativity and associativity can be used to perform operations in parallel and reorder operations.

I'm having trouble even imagining what these means in the context of bits. For anyone who better grasps what this means, could you explain it and flesh it out with some examples?

# Answer
> 1 votes
Consider the following code:

> a = (b + c) + d
>
> e = c + (b + f)

Using associativity and commutativity, we can improve it to

> t = b + c
>
> a = t + d
>
> e = t + f

This uses one less addition. Since integer addition (ignoring overflow) is guaranteed to be commutative and associative, an optimizing compiler is allowed to use this optimization. The same isn't quite true for floating point addition, which is not associative.

---
Tags: algorithms, data-structures, parallel-computing
---


# Question
Title: What is the complexity of deciding if the intersection of a regular language and a context free language is empty?
Let's say we have a context free language, the CFG that produces it.

And then we have a DFA for a regular language.

If the intersection is empty is decidable, but how and how efficiently?

And if you could be so kind, please explain the best known algorithm as simple as you can?

# Answer
The answer depends on how the two languages are given to you; I will assume that the context-free language is given as a CFG, and that the regular language is given as a DFA/NFA. Beigel and Gasarch show how to compute a CFG for the intersection in polynomial time. You can then check whether the resulting language is empty using grammar simplification (described in any decent textbook).
> 4 votes

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


# Question
Title: Why $\left\lceil lgn \right\rceil <lgn+1\le 2lgn\quad for\quad all\quad n\ge 2$
I have some confusion about 3.2-4 in CLRS. Here is the question :

Is the function $\left\lceil \log { n } \right\rceil !$ polynomially bounded? Is the function $\left\lceil \log { \log { n } } \right\rceil !$ polynomially bounded?

Here is the official answer:

There is a point I can't understand.Why $\left\lceil lgn \right\rceil \<lgn+1\le 2lgn\quad for\quad all\quad n\ge 2$? I even draw a graph in desmos.

In the graph, I find it should be $n\ge 1.414$ instead of $n\ge 2$. If $n\ge2$, there will never be $\left\lceil lgn \right\rceil =2lgn$.

# Answer
> 0 votes
$\lceil \log n\rceil = \Theta(\log n)$ (or $\lceil \log n\rceil \in \Theta(\log n)$) means that there exist 2 constants $c\_1 \> 0, c\_2\>0$ such that

* $\lceil \log n\rceil \geq c\_1 \cdot \log n$ for sufficiently large $n$
* $\lceil \log n\rceil \leq c\_2 \cdot \log n$ for sufficiently large $n$

The first case is trivial, just pick $c\_1=1$ and $\lceil \log n\rceil \geq \log n$ holds for sufficiently large $n$. \[Condition 1 satisfied\]

For the second case, if you choose $c\_2=2$, you have that $\lceil \log n\rceil \leq 2 \cdot \log n$ for sufficiently large $n$. \[Condition 2 satisfied\]

**Note**: It does not matter the value of smallest possible $n$ such that the inequality holds, it is enough that *for sufficiently large $n$* it holds. If it was $"\forall n \geq 1000"$ nothing would have changed.

---
Tags: asymptotics, notation
---


# Question
Title: How can I multiply a binary representation by ten using logic gates?
So I’m currently working on something and I have converted all decimal digits 0-9 into binary. But now I want to take say 6 in binary and increase its order of magnitude by base 10 (turning 6 into 60) without converting back to base 10. Is this possible and if so is there a way to do it with any number, X --\> X0 ?

EDIT 1: sorry the first part of the question was super vague and I forgot to mention I’m trying to do this with logic gates.

# Answer
I assume that the task is to compute $mul(10, a)= 10a$. You don't need to do multiplication. A single binary adder is enough since $$10a = 2^3a + 2a$$ meaning you add one-time left-shifted $a$ to 3-time left-shifted $a$. For general multiplication $mul(x,y)$ please see this article.
> 47 votes

# Answer
Multiplying by 10 is the same as multiplying by $(1010)\_2$. To multiply a binary number $x$ by 10, we thus just have to add $x0$ and $x000$. For example, $6 \times 10 = 60$ is implemented by $$ \begin{array}{ccccccc} &0&0&1&1&0&0 \\ +&1&1&0&0&0&0 \\\hline &1&1&1&1&0&0 \end{array} $$ The input is $(6)\_{10} = (110)\_2$, and the output is $(111100)\_2 = (60)\_{10}$.
> 11 votes

# Answer
Sure. You just compute $1010\_\mathrm{b}\times 110\_\mathrm{b}$ using the binary version of long multiplication (or some other algorithm). The nice thing about long multiplication in binary is that you never have to carry anything, except when you're adding things up at the end.

```
   1010
    110 x
  ------
    000
   110
  000
 110
--------
 111100
--------

```

and note that $11100\_\mathrm{b}=60\_\mathrm{d}$, as expected.
> 6 votes

# Answer
Multiply by 8 (left shift 3) then add to it a multiply by two (left shift 1).
> -2 votes

---
Tags: arithmetic, binary
---


# Question
Title: If $B$ is in $SPACE(n^2)$ and $A \leq_p B$ then so $A$ will be in $SPACE(n^2)$?
We know that if $B$ is in $P$ and if $A \leq\_p B$ then $A$ is in $P$ too.

If $B$ is in $SPACE(n^2)$ and $A \leq\_p B$ then so $A$ will be in $SPACE(n^2)$?

I think that the answer to this question is true, because if $A\in P$ then $A \in PSPACE$, and then $A$ could be in $SPACE(n^2)$. I doubt my answer because of that $(n^2)$.

# Answer
$A$ may or may not be in $\mathrm{SPACE}(n^2)$.

Any language $A\in\mathrm{P}$ can be reduced be reduced to any nontrivial language $B\in \mathrm{SPACE}(n^2)$ in polynomial time. Fix your favourite strings $x\_\mathrm{yes}\in B$ and $x\_{\mathrm{no}}\notin B$ ("nontrivial" means that $B$ is neither $\emptyset$ nor $\Sigma^\*$, so both of these strings exist). The reduction is to determine if the input is in $A$; if so, map it to $x\_\mathrm{yes}$; if not, map it to $x\_\mathrm{no}$.

This is true regardless of whether $A\in\mathrm{P}\cap\mathrm{SPACE}(n^2)$ or $A\in\mathrm{P}\setminus\mathrm{SPACE}(n^2)$.

To get some intuition, it might help to look at it in another way. To show that $A\in\mathrm{SPACE}(n^2)$, you'd want to show that the algorithm "Reduce to $B$, then decide $B$" runs in quadratic space. However, the reduction from $A$ to $B$ might blow up the length of the instance by any polynomial amount. For example, It could map a instances of length $n$ to ones of length $n^2$. So, now, if you try to decide $A$ by first reducing to $B$, you'll need space $(n^2)^2 = n^4$ to solve the instance of $B$. Or the reduction itself might take more than $n^2$ space.
> 2 votes

---
Tags: complexity-theory, time-complexity, space-complexity
---


# Question
Title: Are typical sets larger, when information is messier?
Let $0\le q\<p\le \frac{1}{2}$, and let $P,Q$ be two Bernoulli Random Variables such that: $$Pr\[P=1\]=p ; Pr\[P=0\]=1-p$$ and $$Pr\[Q=1\]=q ; Pr\[Q=0\]=1-q$$ **My question:** Does it follow that, for any $\epsilon\>0$ and $n$ as large as desired $|A\_\epsilon^{(n)}(Q)|\<|A\_\epsilon^{(n)}(P)|$? I.e., that the Typical Set of $P$ is larger than that of $Q$?

Intuitively, I would say **yes** because of $q\<p\le \frac{1}{2} \Rightarrow H(q)\<H(p)$, and that the "messier" the information (i.e., the higher the entropy), the more elements in the *Typical Set*, but I've been unable to prove this.

**What I've tried:**

* Working with typical sets size bounds, namely that: $(1-\epsilon)2^{n(H(q)-\epsilon)}\le|A\_\epsilon^{(n)}(Q)|\le2^{n(H(q)+\epsilon)}$. I was able to prove that $2^{-n(H(p)-\epsilon)}\<2^{-n(H(q)-\epsilon)}$ and $2^{-n(H(p)+\epsilon)}\<2^{-n(H(q)+\epsilon)}$, but that seems like a dead end.
* Proving that $A\_\epsilon^{(n)}(Q)\subsetneq A\_\epsilon^{(n)}(P)$ but that's false.
* Finding an Injective Function: $f:A\_\epsilon^{(n)}(Q)\rightarrow A\_\epsilon^{(n)}(P)$ but couldn't find one.

# Answer
As mentioned in the question, it can be shown that: $$(1-\epsilon)2^{n(H(q)-\epsilon)}\le|A\_\epsilon^{(n)}(Q)|\le2^{n(H(q)+\epsilon)}$$ And similiarly: $$(1-\epsilon)2^{n(H(p)-\epsilon)}\le|A\_\epsilon^{(n)}(P)|\le2^{n(H(p)+\epsilon)}$$ So in order to prove what we wanted, it's enough to find some $\epsilon\_0\>0$ and $n\_0$ such that for all $\epsilon\<\epsilon\_0, n\>n\_0$: $$2^{n(H(q)+\epsilon)}\<(1-\epsilon)2^{n(H(p)-\epsilon)}$$ Let $d:=H(P)-H(Q)\>0$, $\epsilon\_0:=\frac{d}{2}$.
**Claim:** The above holds for all $0\<\epsilon\<\epsilon\_0$ and $n$ large enough such that $n\>\frac{log(1-\epsilon)}{2\epsilon-d}$. Proof: $$2^{n(H(q)+\epsilon)}\<(1-\epsilon)2^{n(H(p)-\epsilon)}\iff$$ $$log(\frac{2^{n(H(q)+\epsilon)}}{(1-\epsilon)})\<log(2^{n(H(p)-\epsilon)})\iff$$ $$nH(q)+n\epsilon-log(1-\epsilon)\<nH(p)-n\epsilon\iff$$ $$2n\epsilon-nd\<log(1-\epsilon)\iff$$ $$n\>\frac{log(1-\epsilon)}{2\epsilon-d}$$ Because the last inequation holds (by definition), so does the first, and that is Q.E.D.
> 0 votes

# Answer
Recall that $$ A\_\epsilon^{(n)}(P) = \left\\{ (x\_1,\ldots,x\_n) \in \\{0,1\\}^n : 2^{-n(h(p)+\epsilon)} \leq p^{\sum\_{i=1}^n x\_i} (1-p)^{\sum\_{i=1}^n (1-x\_i)} \leq 2^{-n(h(p)-\epsilon)} \right\\}. $$ We can rephrase the condition as follows. First, it is equivalent to $$ 2^{-n(h(p)+\epsilon+\log(1-p))} \leq \left(\frac{p}{1-p}\right)^{\sum\_{i=1}^n x\_i} \leq 2^{-n(h(p)-\epsilon+\log(1-p))}. $$ Taking the logarithm, we obtain $$ -n(h(p)+\epsilon+\log(1-p)) \leq \log\_2 \frac{p}{1-p} \sum\_{i=1}^n x\_i \leq -n(h(p)-\epsilon+\log(1-p)). $$ This means that $$ |A\_\epsilon^{(n)}(P)| = 2^n \Pr\left\[\frac{n(h(p)-\epsilon+\log(1-p))}{\log \frac{1-p}{p}} \leq \mathrm{Bin}(n,1/2) \leq \frac{n(h(p)+\epsilon+\log(1-p))}{\log \frac{1-p}{p}}\right\] $$ In order to estimate the probability on the right, we need to use *binomial tail bounds*. The Chernoff bounds is a well-known upper bound, and there are almost matching lower bounds, see for example (1) and (3) in Pelekis, A lower bound on binomial tails: an approach via tail conditional expectations. Plugging these bounds, we would get a rather accurate estimate for $|A\_\epsilon^{(n)}(P)|$, which we could then compare with $|A\_\epsilon^{(n)}(Q)|$, estimated using the same method.

Unfortunately, this calculational method seems like a lot of work, better done with the aid of a computer algebra system, and I am not motivated enough to actually carry it through. However, it seems likely (if not certain) that this method will be able to settle the conjecture.
> 0 votes

---
Tags: probability-theory, sets, information-theory
---


# Question
Title: Minimal colouring problem aproximation threshold
> Given that 3-colouring and 4-colouring are NP-complete show that the aproximation threshold of the minimal colouring problem is greater or equal than $\frac{4}{3}$.

My current approach is to work by contradiction assuming there was such an algorithm that in polynomial time can produce a $\delta$-aproximation with $\delta \< \frac{4}{3}$ using the fact that 3-colouring and 4-colouring are NP-complete. I didn't obtain much progress.

**References**

I just wanted to point out that this is an application of the "Gap technique" presented in the book "Complexity and Aproximation" of Auseillo et alii., I wasn't familiar with the notation they use so I couldn't understand how to fully apply the technique.

# Answer
> 1 votes
Consider 3-coloring and suppose that a $\delta$-approximation algorithm $A$ for the minimum coloring problem with $\delta \< \frac{4}{3}$ exists.

Let $G$ be the input graph and $x$ be the solution returned by $A$.

* If $G$ is 3-colorable then $A$ would return $3$. In fact, $x \lt 4$ since $A$ would return a solution $x \lt \ ( 3\cdot \delta)=3\* \frac{4}{3}=4$ by hypothesis.
* If $G$ is not 3 colorable then $A$ would return $x \geq 4$ since $G$ needs at least $4$ colors.

Hence, with $A$ you would be able to determine whether $G$ is 3 colorable or not.

But 3-Coloring is NP-Complete (contradiction).

---
Tags: complexity-theory, colorings
---


# Question
Title: Cases where string concatenation is commutative
Strings are known to not satisfy the commutative property. pq is not equal qp unless p is empty string. Is there a case where pq can be qp where both are non empty strings and p and q are distinct

# Answer
> 12 votes
Simple solution: $a\cdot aa = aa \cdot a$?

In general there is a characterization due to Lyndon and Schützenberger. For nonempty words $x,y\in \Sigma^+$ the following are equivalent:

* $xy=yx$
* there exists $z\in \Sigma^+$ such that $x=z^k$ and $y=z^\ell$ for some $k,\ell \>0$.
* there exist $i,j\>0$ such that $x^i = y^j$.

This means that $x$ and $y$ commute ($xy=yx$) iff they are powers of the same string, like $bbabba\cdot bbabbabba = bbabbabba \cdot bbabba$. So, basically the examples will not get more complicated than the proposal $a\cdot aa = aa \cdot a$ above.

---
Tags: formal-languages
---


# Question
Title: What is different between Set and Type in Coq?
AFAIU types can be a `Set` whose elements are programs or a `proposition` whose elements are Proofs. So based on this understanding:

```
Inductive prod (X Y: Type) : Set :=
| pair: X -> Y -> prod X Y.

```

Following code should compile but it does not due to the following error. If I change `Set` with `Type` or the other `Type` with `Set` it compiles fine. Can someone help me understand what the following error means? I am trying to teach myself Coq using Software Foundations book.

Error:

```
Error: Large non-propositional inductive types must be in Type.

```

# Answer
Coq has 4 "big" types:

* `Prop` is meant for propositions. It is impredicative, meaning that you can instantiate polymorphic functions with polymorphic types. It is also erased at run-time, meaning you can't pattern match on a Prop value to build a Type value, unless there's only one possibility.
* `SProp` is like Prop, but with definitional proof irrelevance, meaning that if $p\_1, p\_2 : P$ then $p\_1 = p\_2$.
* `Set` is meant for computation. It's predicative, and doesn't have proof irrelevance, which lets you do nice things like not assuming $1 = 2$. The `Set` parts remain during code extraction.
* `Type` is a supertype of both of these, allowing you to write code once that works with either

I'm pretty sure your error is because you're defining a `Set` whose parameters can be `Type`, which means they can be `Prop`, which isn't allowed. If you change to this:

```
Inductive prod (X Y: Set) : Set :=
| pair: X -> Y -> prod X Y.

```

your code should work.

EDIT: Updated to include SProp.
> 19 votes

---
Tags: dependent-types, coq
---


# Question
Title: If $L_1,L_2\in \mathrm{NP}$ and $w\in L_1$ or $w\in L_2$ then can $L_1\cup L_2=L$'s verifier use the same certificate $c$ for $w$?
I read the following solution for Showing that $\mathrm{NP}$ is closed under union and they used the same $c$ for both the verifies $V\_1$ and $V\_2$. **Why is it correct?**

> Let $L\_1$ and $L\_2$ be languages in $\mathrm{NP}$. Also, for $i = 1, 2$ let $V\_i(x, c)$ be an algorithm that, for a string $x$ and a possible certificate $c$, verifies whether $c$ is actually a certificate for $x \in L\_i$. Thus, $V\_i(x,c) = 1$ if certificate $c$ verifies $x \in L\_i$, and $V\_i(x, c) = 0$ otherwise. Since both $L\_1$ and $L\_2$ are both in $\mathrm{NP}$, we know that $V\_i(x, c)$ terminates in polynomial time $O(|x|^d)$ for some constant $d$. To show that $L\_3 = L\_1 \cup L\_2$ is also in $NP$, we will construct a polynomial-time verifier $V\_3$ for $L\_3$. Since a certificate $c$ for $L\_3$ will have the property that either $V\_1(x, c) = 1$ or $V\_2(x, c) = 1$, we can easily construct a verifier $V\_3(x, c) = V\_1(x, c) \lor V\_2(x, c)$. Clearly then $x \in L\_3$ if and only if there is a certificate $c$ such that $V\_3(x, c) = 1$. Notice also that the new verifier $V\_3$ will run in time $O(2(|x|^d))$, which is polynomial. Therefore, the union $L\_3$ of two languages in $\mathrm{NP}$ is also in $\mathrm{NP}$, so $\mathrm{NP}$ is closed under union.

taken from here.

$M\_1,M\_2$ TM which accept $w$ can accept $w$ for different reasons so we can't claim that $c\_1=c\_2$

Questions:

1. Is it legal to use the same certificate for both $V\_1,V\_2$ in the answer? Why?
2. Is a verifier by definition is deterministic TM?
3. In the above answer, does $V\_3$ runs $x,c$ on both $V\_1$ and $V\_2$ in the worst case?

# Answer
Assume that $c\_1$ and and $c\_2$ are polynomial size certificates for $x \in V\_1$ and $x \in V\_2$. Then define $c=c\_1\\#c\_2$, a new certificate formed by concatenation of $c\_1$ and $c\_2$ which is clearly polynomial size. Then $V\_1$ and $V\_2$ still can use $c$ as a certificate to verify $x\in V\_1$ and $x\in V\_2$. $V\_1$ will use the left part of $c$ and the $V\_2$ will use the right part of $c$.

> Is a verifier by definition is deterministic TM?

Yes, the verifier is a deterministic TM, by definition.

> In the above answer, does $V\_3$ runs $x,c$ on both $V\_1$ and $V\_2$ in the worst case?

You can treat $V\_3$ as a TM which invokes (as subroutines) $V\_1(x,c)$ and $V\_2(x,c)$, so if $V\_1$'s worst case is $O(f)$ and $V\_2$'s worst case is $O(g)$ then $V\_3$'s worst case is either $O(f)$ or $O(g)$ which is polynomial.
> 1 votes

---
Tags: complexity-theory
---


# Question
Title: Is boolean validity a harder problem than satisfiability?
I am aware that satisfiability is NP complete and unsatisfiability is co-NP complete. But somehow I feel that labeling satisfiability as NP-complete and unsatisfiability as co-NP complete is papering over the fact that unsatisfiability (or equivalently validity) is inherently a harder problem than satisfiability. Suppose I have a NDTM. Then given a potential model I can surely check it in polynomial time. However to check unsatisfiability I would need to check all possible assignments, surely this makes the problem EXPTIME?

# Answer
> However to check unsatisfiability I would need to check all possible assignments, surely this makes the problem EXPTIME?

Well, $EXPTIME$ but not necessarily $EXPTIME$-complete.

Congratulations, you've found the (possible) difference between $NP$ and $Co-NP$.

The first thing to realize is that there's a duality here. Satisfiability requires only a single example to prove a YES, but (as far as we know) needs to search a possibly exponential space for a NO. Unsat is the exact dual of this: you need to search a possibly exponential set to prove a YES, but a single counter-example will prove a NO. So neither is a harder problem, it's just that one is easy for YES, and the other is easy for NO.

The second thing to realize is that *every* NP-complete problem has a dual like this, and that's exactly why we study $Co-NP$ complete problems. For Hamiltonian Path, one path proves it, and a full search is needed to disprove. The converse is true to for NOHAMPATH, it's complement problem. Every NP-problem has a dual by switching the "yes" and "no" cases.

Nobody knows if $NP = EXPTIME$, though it's pretty unlikely. But it seems like just having to do an exponential search isn't enough to characterize all exponential algorithms.
> 3 votes

# Answer
No, it just means that there's no obvious algorithm for a nondeterministic Turing machine to check unsatisfiability in polynomial time, which is part of the reason why we don't know if **NP** and **co-NP** are the same thing.

For deterministic machines, unsatisfiability *can't* be harder than satisfiability since, if you could solve either one, you could solve the other by negating the answer. Negating the answer is non-trivial for nondeterministic machines.
> 1 votes

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


# Question
Title: Showing MAXIMUM CLique is NPO-simple and MAXIMUM GRAPH COLORING is not
Recall the notion of NPO problem. An NPO problem is simple if the following is true:

$\forall k \in \mathbb{N}^\*. (\forall x. OPT(x) \leq k) \in P$

In words, given any positive integer $k$, the problem of deciding if for instance $x$ its optimal is less or equal than k is in $P$.

I'm asked to show the MAXIMUM CLIQUE problem is simple and that assuming $P \neq NP$ MINIMUM GRAPH COLORING is not simple.

**References**

This is problem 3.13 of "Complexity and Approximation" of Ausiello et alii.

# Answer
> 2 votes
$k-Clique$ is in $\mathsf P$. More precisely, this can be done in $O(|V|^k)$ time. How? If you have a set of power $|V|$, then, how many subsets of power $k$ does it contain? Answer is $C^k\_{|V|}\in O(|V|^k)$.

$3-Coloring$ is $\mathsf{NP}$-complete and reduction is well described in this paper. Since SAT can be reduced to 3SAT, any Coloring also can be reduced to 3-Coloring.

---
Tags: complexity-theory, optimization, colorings, clique
---


# Question
Title: Average number of comparisons in sorted insertion
The questions is pretty simple: Given a sorted array of N elements, what is the average number of comparisons made in order to add a new element (let's call it x) in its correct position?
I am using linear search for that task.

So far, I've tried to solve it this way:

```
# of Comparisons     Probability of A[i] > x (Not sure if correct)
     1                         1/n
     2                         1/n
     3                         1/n
     4                         1/n
    ...                        ...
     n                         1/n

```

Hence, the expected value would be:

$$E\[x\] = \sum\_{x=1}^{n}x \cdot Pr(X=x)$$ $$E\[x\] = 1 \cdot Pr(X=1) + 2 \cdot Pr(X=2) + 3 \cdot Pr(X=3) + ... + n \cdot Pr(X=n)$$

Using $$Pr(X = n) = \frac{1}{n} $$ for all n,

$$E\[x\] = \frac{1}{n} \cdot \sum^{n}\_{i=1}{i}$$

and finally $$E\[x\] = \frac{n+1}{2}$$

Still, I'm not sure if this is the correct way to solve it, since I'm not sure about my 1/n assumption.

Any insights would be helpful!

# Answer
Well, that would strongly depend on the algorithm that you use to find out where to insert the new element, and on the distribution of new elements.

Assuming that you do a linear search, and the new element could go to any position with the same probability, your result is close, but not quite exact. The new element can go into one of (n + 1) positions, not n. There may be up to n comparisons needed; n comparisons are needed both if the new element goes into the first array position, and if it goes into the second array position. So the result is

```
(1 + 2 + 3 + ... + (n-1) + n + n) / (n + 1) =

= (n (n+1) / 2 + n) / (n + 1)

= n (n + 3) / 2 / (n + 1)

= (n + 2 - 2 / (n + 1)) / 2 ≈ (n + 2) / 2,

```

which is just a tiny bit more than your answer (n + 1) / 2.
> 1 votes

---
Tags: algorithm-analysis, mathematical-analysis
---


# Question
Title: A confusion about the Reduction via Computation History
\[Updates: Thanks for @Raphael 's notification, I delete the screenshot of the book and type the $LaTex$ materials\]

In Sisper's Intro to the theory of Computation, there is a reduction method via Computation History. He proves theorem 5.10 and 5.13 (3rd edition, page223) by that method. (I append the related part at the end)

Take theorem 5.10 as an example, to construct the LBA B, we need to know the computation history in advance. As far as I understand, there is only one way to get this history -- run turing machine on the input. But if we do this, it has chance to bring us to a loop since we don't know if it's gonna halt or not.

If we do this to get the Decider S in the proof (see the appended proof), we can not say that S is a decider, because in step 1 where we construct the LBA B, we may not halt. So the proof doesn't work.

Thanks for @fade2black 's explanation, let me clarify my question further:

In the proof, we are constructing a decider S for $A\_{TM}$. For a decider, we expect tow things:

1. On input in the language, it halts and accepts
2. On input not in the language, it halts and rejects

Now let's consider the Decider S in the proof. It works well on $\<M, w\>$ where M accepts w. It satisfies the first condition above.

But if it is given an input $\<M, w\>$ where M dose not halt on w, problems can happen. The first behavior of Decider S is to construct B from $\<M, w\>$. Now since M does not halt on w, we don't have a accepting history. Without an accepting history, how can we construct B? You may argue that if M does not halt on w, just let B accept nothing. But I want to ask: How do you know in advance that M does not halt on w? For me, the only way is to run M on w. If M does not halt, we know that M does not halt on w. But that is to say, we run M on w for the purpose to construct B, which is the first step in Decider S. $\textbf{This Step May Never Halt}$, thus S may never halt. Therefore we know that S is not a decider (A decider must halt no matter it accepts or rejects).

Can any one correct my thought? Thank you.

Here is the related part in the book. (All the following is a paraphrasing of Theorem 5.10 from $\textit{Introduction to the Theory of Computation}$, third edition, Micheal Sisper)

---

$E\_{LBA} = \\{\<M\>|\text{M is an LBA where } L(M) = \emptyset\\}$

* LAB stands for Linear Bounded Automaton. But it seems you don't need to understand LAB to answer my question, since I'm asking about his methodology of using Computation History.

$\textbf{Theorem 5.10}$

$E\_{LBA}$ is undecidable.

$\textbf{Proof Idea }$ This proof is by reduction from $A\_{TM}$. We show that, if $E\_{LBA}$ were decidable, $A\_{TM}$ would also be.

* Note that $A\_{TM} = \\{\<M, w\>|\text{M is a Turing Machine and M accepts w}\\}$

We will construct a $LBA$ B. The language B recognizes comprises all accepting computation histories for M on w. So if we can determine whether B's language is empty, clearly we can determine whether M accepts w.

Now we construct B from M and w. Assume $x$ is an accepting computation history for M on w. For the purpose of this proof we assume that the accepting computation history is presented as a single string, with the configurations separated from each other by the $\\#$ symbol, i.e. $x = \\# C\_1 \\# C\_2 \\# ... \\# C\_l \\#$.

The LBA B works as follows. When it receives an input $x$, B is supposed to accept if $x$ is an accepting computation for M on w. B can just check whether the $C\_i$ satisfy the three conditions of a computation history.

1. $C\_1$ is the start configuration
2. Each $C\_{i+1}$ legally follows from $C\_i$
3. $C\_l$ is an accepting configuration for M

If 1, 2 and 3 are satisfied, B accepts its input.

$\textbf{Proof }$ Suppose Turing Machine (TM) R decides $E\_{LBA}$. Construct TM S that decides $A\_{TM}$ as follows.

S = "On input $\<M,w\>$, where M is a TM and w is a string

1. Construct LBA B from M and w as described in the proof idea.
2. Run R on input .
3. if R rejects, accept; if R accepts, reject."

Then this S is a decider for $A\_{TM}$. This contradicts to the fact that $A\_{TM}$ is Turing-undecidable.

# Answer
> 1 votes
It seems you confused two things

1. What computation history is and
2. How the hypothetical decider $R$ and LBA $B$ are used to decide $A\_{TM}$

You can think of TM **configuration** as snapshot of the tape content plus machine's state at some particular time. Every step of a TM generates a new configuration. The set of all that configurations is a **computation history**. If computation halts then that set is finite. So, if $C\_1\\#C\_2\\#\dots \\#C\_n$ is a sequence of configurations and $M$ is a TM, you can check if a configuration $C\_i$ is a legal configuration with respect to the TM $M$. We can also check if two adjacent configurations $C\_i\\#C\_{i+1}$ is a legal pair of configurations., i.e., if $C\_{i+1}$ legally follows $C\_i$ with respect to TM $M$. In other words, we want to be sure that machine's transitions between states were really made according to the machines's transition rules. In addition we can check if some configuration represents a start configuration or accepting configuration of a TM $M$ on some input $w$.

Now, we can construct a LBA $B$ which takes input $x$, in fact, a computation history for $M$ on $w$, and accepts $x$ if it is accepting computation history. In other words, what $B$ does is it takes $x = C\_1\\#C\_2\\#\dots \\#C\_n$ and checks if it is legal sequence and if it is accepting. At this point you may object: **What if $M$ on $w$ never halts?** The answer is that we construct LBA $B$ which recognizes only those $x$s (histories) that correspond to the accepting ones for $M$ on $w$. In fact we never simulate $B$, we simply feed it to our hypothetical decider. (I would write it LBA $B\_{M,w}$ rather than $B$ to avoid confusions). **Thus, $M$ halts on $w$ iff the language of LBA $B$ is not empty.**

Now, our algorithm as following:

```
   decide(M,w)
     construct LBA B for <M,w>
     Run the hypothetical decider R on B
     if answer is ACCEPT, i.e. language of B is empty (no accepting history for M,w)
       REJECT and halt
     else
       ACCEPT and halt
     end
   end

```

Note that we do not bother with running or simulating $B$, we just construct it. In fact, $R$ takes care of it. Since we have just constructed decider for $A\_{TM}$, such $R$ cannot exist. Q.E.D

---
Tags: computability, reductions, undecidability, proof-techniques, linear-bounded-automata
---


# Question
Title: Construction of the complement of universal Turing machine - where is the catch?
This is pretty fundamental but I'm getting confused. Let $U$ be the Universal Turing Machine and $L\_{u}$ the language it accepts which is recursively enumerable. Obviously we are not able to construct the machine for its complement i.e. for $\bar{L\_{u}}$, otherwise the whole theory crashes but still let's try. Let $V$ be a Turing Machine constructed the same way as $U$ but with the final states switched i.e.: on input code $\langle M, w \rangle$ it simulates $M$ on $w$ but if $M$ accepts $w$ then $V$ rejects $\langle M, w \rangle$ and if $M$ rejects $w$ then $V$ accepts $\langle M, w \rangle$ (implicitly if $M$ loops then $V$ loops). So the language that $V$ accepts is $\bar{L\_{u}}$, isn't it? There must be a flaw in this construction but where?

# Answer
> Let V be a Turing Machine constructed the same way as U but with the final states switched

This construction won't work. This is a pattern in automata theory, by the way: for deterministic deciders, flipping final states provides a new proof for closure against complement. For all others, it usually fails.

Here, observe that your semi-decider $U$ of L is, by definition, of the form:

> Accept after finite time if $w \in L$; loop otherwise.

With your construction for $V$, you get:

> Reject after finite time if $w \in L$; loop otherwise.

This is *not* a semi-decider for $\overline{L}$!

Intuitively, you can not flip a non-termination; you *don't get* the result you would flip!
> 3 votes

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


# Question
Title: Movement on Labyrinth with Best First Search
I have the following labyrinth where `R` is the robot(the parent node), red blocks are the obstacles where the `R` cannot move and `GOAL` is the node where we want the robot to go. Every node should be written in this form `R(1,2,4)`, `1` is the row, `2` is the column and `4` is the distance from the current node to the goal node `GOAL`.

I am in a position where the solution tree looks like this

Now, I don't know which node should I select `C` or `D` ? Both of them have the same distance to the goal.

# Answer
> 1 votes
It doens't matter which one you take, because they both have exactly the same value. Which one actually gets taken will depend on unimportant details of the implementation, such as the order the nodes were added to the tree.

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


# Question
Title: Feature selections : Still a high dimentionality
One of the advantage of using a features reduction/sub feature selection is to avoid a high dimentionality.

The most known method is the Forward selection, where it finds the best combinations of features among others, iteratively. Now please have a look at this picture retrieved from a ppt slide on the internet.

The second row of the table shows that the 11 features are the features selected/reduced from initial 20 features. My question is that, the 11 features are still considered as a high-dimensional features set, indeed one can't just subtitute it over a KNN function. Now I'm confused as to how he/she then adapt it to the KNN classifier for the 11 features?

# Answer
> 1 votes
There seems to be a misconception. You can use $k$-nearest neighbors with any number of dimensions. There is no prohibition on using it with a large number of features. And in some cases $k-NN will work well even in high dimensions (a large number of features); it all depends on the dataset, and to find out whether it will work well, you have to try it. In general, feature selection might make the algorithm work better, or it might make it work worse -- it all depends.

---
Tags: image-processing, classification, features
---


# Question
Title: A general algorithm for greedy algorithms
I have been refreshing on greedy algorithms as an algorithm design technique. I have read many sources for an explanation of what a greedy algorithm is, because I would like to put together a general greedy algorithm.

When reading these sources, I have gathered all of the important concepts to try to come up with this general algorithm for the greedy selection technique. By "general" I mean that it summarizes the behavior of the technique for all possible problem for who this technique would yield a correct solution.

I would like some input on it. Here is take 1:

Let $f$ be a function from $S$ to any set. The following algorithm tries to perform greedy choices per each search iteration of element of $S$, in order to try come up with the best possible point for $f$ over $S$ given a set of constraints $C$:

```
Select p0 from S;
i := 1;
Let P be a set of already chosen points from S to be initialized to {}
Let F be the set of values of f for each element of P to be initialize to {};
while S != {}:
    Make a greedy choice for p_i based on p_{i - 1};
    if f(p_i) is feasible based on constraints from C and has improved:
        p_{i - 1} := p_i;
    Add f_i := f(p_i) to F;
    Remove p_{i - 1} from S and save it in P;
 return P, F;

```

My specific question is: How far is this first take from being a correct generalization of the greedy selection technique for algorithmic design?

This should be fun :)

# Answer
There is no such thing as the *correct generalization of the greedy selection technique*, because it's an informal technique. That said, there has been some effort at modeling the greedy heuristic, with a view toward understanding its limitations. This study has been initiated by Borodin, Nielsen and Rackoff, (Incremental) priority algorithms, and continued mostly by Borodin and his coauthors.

Before discussing the work of Borodin et al., let me briefly mention the subject of *matroids* and *greedoids*. They answer the following question:

> Consider the greedy algorithm for maximizing a linear objective subject to constraints. For which constraint structure does this algorithm produce optimal results?

We can think of the constraints as a set system, any member of which is a feasible solution. For hereditary set systems (any subset of a feasible set is feasible), the greedy algorithm produces an optimal result if and only if the constraints form a matroid. Greedoids answer a more refined question.

Back to Borodin's priority algorithms. The exact definition of a priority algorithm depends on the context, but here is a general flavor. There is some iterative procedure for constructing a solution for a given instance. The instance consists of a set of objects (think scheduling algorithms). At each step of the procedure, the algorithm chooses an ordering of all objects, and the best available object according to the ordering is added to the solution set. All objects incompatible with this object are thrown out, and the following iteration is executed. The process stop when the set of available objects becomes empty.

What I described above is the *adaptive* priority model. In the *fixed* priority model, the ordering is chosen once and for all rather than at each step. In both models, the algorithm is not allowed to look at the set of available objects (that would be cheating).

The situation for graph algorithms is somewhat more complicated, see for example Borodin, Boyar and Larsen, Priority algorithms for graph optimization problems, and there are several models which are more realistic than the model considered above. There are several other variants of priority algorithms which can be explored through the relevant work of Borodin and others.
> 6 votes

---
Tags: algorithms, greedy-algorithms, algorithm-design
---


# Question
Title: When is conditional Kolmogorov complexity zero?
It seems intuitive that conditional Kolmogorov complexity is only zero when the bitstrings are the same, and otherwise is greater than 0. I.e. if $b\_1 = b\_2$, then $K(b\_1|b\_2) = 0$, otherwise $K(b\_1|b\_2) \> 0$.

However, if that is the case, then we could break a long bitstring into many smaller, different bitstrings, and then use conditional Kolmogorov complexity to establish a lower bound on the long bitstring's Kolmogorov complexity.

E.g., original bitstring is $\mathcal{B}$. It is broken into different, smaller bitstrings $b\_1,b\_2,\ldots,b\_n$. We then use conditional Kolmogorov complexity to establish a lower bound on $K(\mathcal{B})$, in the following way,

\begin{align\*} K(\mathcal{B}) &= K(b\_1,b\_2,\ldots,b\_n) \\ &= K(b\_1) + K(b\_2|b\_1) + \ldots + K(b\_n|b\_1,b\_2,\ldots,b\_{n-1}) + O(log(K(b\_1,b\_2,\ldots,b\_n)))\\ &\geq n. \end{align\*}

*The equality is not strict, there are errors involved, which may invalidate the argument.*

As the bitstring length grows, we can continue to grow the lower bound $n$ arbitrarily large, since there are a greater number of distinct smaller bitstrings that can be used to construct the large bitstring. This appears to violate Chaitin's incompleteness theorem, which states with a fixed axiomatic system there is a limit $\mathcal{L}$ above which we cannot prove $K(\mathcal{B}) \> \mathcal{L}$.

What am I missing here?

# Answer
> 1 votes
The answer depends on whether your encoding is prefix-free or not, and in the latter case, on your universal Turing machine.

There are two variants of Kolmogorov complexity: one in which the set of programs form a prefix-free code, and one in which there is no such requirement. For the first variant, the Kolmogorov complexity is always positive. For the second variant, the universal Turing machine can do whatever it wants given an empty program (or indeed, any fixed program). You can arrange that $K(x\_1|x\_2) = 0$ for your choice of $x\_1,x\_2$, for example.

---
Tags: kolmogorov-complexity
---


title: Check if I have a phone number

text:
# Question
Title: Check if I have a phone number
I was recently in an interview and was asked what would be the smallest memory foot print and fastest system to check if a given phone number is in your data store given that all phone numbers will only be 7 digits.

I was told the answer is a byte but, I'm still not 100% sure how this would work and have not been able to find any information on it as of yet. If anyone knows the name of the structure/algorithm or would be willing to explain it I would be very appreciative.

Example data set:
6041234567
6041234568
6041234569
6041234570
6041234571

Output if checking for 6041234569:
True

Output if checking for 6041234580:
False

Edit: Please ask questions so I can try and make my question more clear.
Edit2: I only need to know if the phone number exists. I don't need to get it out.

# Answer
> 1 votes
**Rewritten to match the new edited version of the question**

What you want to think about is the size of the state for a DFA corresponding to a regular expression to match the number in question.

(I don't know how to draw DFAs here so work with my hand waving if you can.)

Since the thing you are looking for is a constant string the regular expression is just that string, say for example `6041234567`. As a DFA this is a start node connected 10 intermediate nodes and a final accepting node. Then each of these nodes connect to the next node if the next character is the right one in the stream or back to the start if it is an incorrect input. If you ever reach the final accepting node you have found the phone number and can do a happy dance.

That is all a setup for the fact that the only thing that matters state-wise is the current node you are matching on. In my simple example here there are 12 nodes total, so you really only need 4 bits of data.

So you could have one upped the interviewer and said that in reality all you needed is a single nybble, instead of a whole byte.

**A note about loop unrolling and state hiding**

You can also achieve this by just writing a long list of checks for each individual digit as David commented above with what appears to be zero state. But what that long list of checks is really doing is just moving the state into the program counter. You can do that with any fixed length matching problem, it is technically true but not really interesting.

One can also argue that I am moving state into the DFA, how is that represented? That is a fair cop, if one is being super pedantic, we would have to specify things like "A DFA is a 5-tuple consisting of yada yada yada" when we really need that precision. Unless you were interviewing for a position in CS theory or compiler design no interviewer would be going there.

The reason that I am pretty certain that my answer is the right one in this case is that this question sounds like one that is asked all the time. About half-way through a Theory of Computation course right after you learn about using DFAs to match REGEXPs you will look into the number of states and how to represent them. This gives a nice intuition about the complexity and "size" of the various languages they match. It also nicely segues into the way that removing determinism can greatly shrink the resulting transition graph and going the other way can result in an explosion in the number of states.

# Answer
> 1 votes
It's possible, if the "data store" referred to is small enough, that an 8-bit *Bloom Filter* or some better equivalent would be the answer they're looking for.

God only knows what a good enough set of hash functions would look like though…

# Answer
> 0 votes
This has of course nothing to do with computer science, but if you realistically want to check if a string represents a phone number, then you use something like libphonenumber which knows the rules of 150 or so countries, knows everything mobile phone numbers, service numbers and so on.

If someone says "a phone number always looks like 123-XXX-XXXX", you just laugh.

# Answer
> 0 votes
Since there is no pattern neither between phone numbers, nor between input numbers. Then there is no optimization.The only solution is to iterate over your array and test. If you can optimize this, then you are welcome to optimize compilers or memory/CPU structure that has been designed for decades.

---
Tags: algorithms, searching
---


# Question
Title: How to convert DFA to regular expression using arden's rule
I generally use state removal method to convert DFA to regular expressions. But I want to try other methods like using algebraic methods and arden's rule.

How to solve a DFA with multiple final states using algebraic method? I refered this link https://cs.stackexchange.com/questions/2016/how-to-convert-finite-automata-to-regular-expressions and arrived at this solution which I think is wrong since a can be followed by only a or c not b.

I used state removal method and arrived at below regular expression which seems to be correct as the language won't contain ab.

# Answer
> 1 votes
Your equations are wrong; your solution works for the reversed arrows. You should be solving the following system: $$ q\_0 = (b+c)q\_0 + aq\_1 + \epsilon \\ q\_1 = cq\_0 + aq\_1 + \epsilon $$

---
Tags: regular-expressions, finite-automata, formal-languages
---


# Question
Title: Are context-free languages in $a^*b^*$ closed under complement?
The context-free languages are *not* closed under complement, we know that.

As far as I understand, context-free languages that are a subset of $a^\*b^\*$ for some letters $a,b$ are closed under complement(!?)

Here is my argument. Each CF language $L$ has a semi-linear Parikh image $\pi(L) = \\{ (m,n) \mid a^mb^n \in L \\}$. Semilinear sets are closed under complement. The set of vectors that represent the semi-linear set can easily be transformed into a linear grammar.

**Question.** Is there an easily accessible reference to this fact?

Technically these languages are called *bounded*, i.e., a subset of $w\_1^\* \dots w\_k^\*$ for some words $w\_1,\dots,w\_k$.

My motivation for this question is from a recent question on the context-freeness of $\\{ a^nb^m \mid n^2 \neq m \\}$. Its complement within $a^\*b^\*$ seems easier to handle.

# Answer
> 12 votes
This characterization of bounded context-free languages is due to Ginsburg ("The Mathematical Theory of Context-Free Languages"), and appears as Corollary 5.3.1 in his book. For general $k$ there are some restrictions on the semilinear sets, but for $k \leq 2$ these restrictions are always satisfied, and so it is straightforward to deduce that the complement of such a language (within $w\_1^\* w\_2^\*$) is context-free.

Ginsburg mentions these implications in his book.

Corollary 5.6.1 If $M\_1 \subseteq w\_1^\*w\_2^\*$ and $M\_2$ are \[context-free\] languages, $w\_1$ and $w\_2$ words, then $M\_1\cap M\_2$ is a \[context-free\] language.

Corollary 5.6.2 If $M\_1 \subseteq w\_1^\*w\_2^\*$ and $M\_2$ are \[context-free\] languages, $w\_1$ and $w\_2$ words, then $M\_1 - M\_2$ and $M\_2-M\_1$ are \[context-free\] languages.

# Answer
> 2 votes
Another proof uses the following characterization proved in this answer:

> The language $\\{ a^i b^j : (i,j) \in A \\}$ is context-free iff $A$ is definable in Presburger arithmetic.

Clearly $A$ is definable in Presburger arithmetic iff $\overline{A}$ is definable in Presburger arithmetic.

This shows that if languages $L\_i \subseteq a^\*b^\*$ are context-free then every Boolean expression in the languages (involving union, intersection, and complementation) is context-free as well.

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


# Question
Title: How to prove a complete binary tree of depth N has $2^{N+1} - 1$ nodes?
Here is the description of a proof problem:

A complete binary tree of depth **N** is a binary tree in which every node on levels $0,1,2,...,N-1$ is a parent and has two children, and each node on level **N** is a leaf.

It's asking for *proving binary tree of depth N has $2^{N+1} - 1$ nodes*.

I am not really sure how to approach this proof. I tried to plug in some values in $D(N) = 2^{N+1} - 1$ just to play with the formula, I get $D(1) = 2^{1+1} - 1 = 3$, $D(2) = 2^{2+1} - 1 = 7$, $D(3) = 2^{3+1} - 1 = 15$, and so on. I still did not see how these numbers relate to the descriptions given and how I would relate these values to given facts to build a proof.

# Answer
> 8 votes
**Hint 1:** Draw some binary trees of depth $0, 1, 2$ and $3$. Depth $0$ is only the the root.

**Hint 2:** Use Induction on the depth of the tree to derive a proof.

The base case is depth $n=0$. With depth $0$ we only have the root, that is, $2^{0 + 1} - 1 = 1$ nodes, so the formula is valid for $n=0$.

The next case is depth $n=0+1=1$, since the tree is full the root must have $2$ leafs. So we have $1 + 2 = 3$ nodes in total. The formula still holds since $2^{1+1} - 1 = 3$.

Can you generalize this procedure? Does this hold for all $n \geq 0$?

---
Tags: algorithms, data-structures
---


title: How is it possible that $L_1$ is $NP$?

text:
# Question
Title: How is it possible that $L_1$ is $NP$?
**The question is from my complexity-theory course.**

## The question

If $L\_1,L\_2,L\_3 \in \lbrace 0,1 \rbrace^\*$, and different from $\lbrace 0,1 \rbrace^\*$ and from the empty language, prove that if $L\_1 \leq\_p L\_2 \cap L\_3$, where $L\_2 \in NP$ and $L\_3 \in P$ then $L\_1 \in NP$

### My answer

Due to the fact that $P \subseteq NP$, we know that $L\_2 \in NP$ and that $L\_1 \in P$. $L\_2 \cap L\_3$ is at most $L\_3$ so $L\_2 \cap L\_3 \in P$ then I proved that $L\_1 \in P$. But the question asks to prove that $L\_1 \in NP$. Is it a joke? Am i missing something?

# Answer
No, your proof is faulty. You claim "we know that $L\_1 \in P$", but that doesn't follow. You haven't justified that claim, and I don't think it's true. It's not clear why you think that would be true, so it's hard to say why you went astray, but that's the first step that is wrong. Also "is at most $L\_3$ is not well-defined, and the intersection of a language in $P$ and a language in $NP$ is not necessarily in $P$.

I think you need to be more careful with your proofs: you have multiple steps where you make claims that simply don't follow from the previous steps. I recommend you justify each step much more carefully, in more detail -- and if you can't, you should be suspicious of whether it is actually true.
> 3 votes

---
Tags: complexity-theory, np, complexity-classes, sets
---


# Question
Title: Decidable properties of computable reals
Is "Rice's theorem for the computable reals" -- that is, no nontrivial property of the number represented by a given computable real is decidable -- true?

Does this correspond in some direct way to the connectedness of the reals?

# Answer
> 10 votes
Yes, Rice's theorem for reals holds in every reasonable version of computable reals.

I will first prove a certain theorem and a corollary, and explain what it has to do with computability later.

**Theorem:** *Suppose $p : \mathbb{R} \to \\{0,1\\}$ is a map and $a, b \in \mathbb{R}$ two reals such that $p(a) = 0$ and $p(b) = 1$. Then there exists a Cauchy sequence $(x\_i)\_i$ such that $p(\lim\_i x\_i) \neq p(x\_j)$ for all $j \in \mathbb{N}$.*

*Proof.* We construct a sequence of pairs of reals $(y\_i, z\_i)\_i$ as follows: \begin{align\*} (y\_0, z\_0) &= (a, b) \\ (y\_{i+1}, z\_{i+1}) &= \begin{cases} (y\_i, (y\_i + z\_i)/2) & \text{if $p((y\_i + z\_i)/2) = 1$} \\ ((y\_i + z\_i)/2, z\_i) & \text{if $p((y\_i + z\_i)/2) = 0$} \\ \end{cases} \end{align\*} Observe that for all $i \in \mathbb{N}$:

* $p(y\_i) = 0$ and $p(z\_i) = 1$
* $|z\_i - y\_i| = |b - a| \cdot 2^{-i}$
* $|y\_{i+1} - y\_i| \leq |b - a| \cdot 2^{-i}$
* $|z\_{i+1} - z\_i| \leq |b - a| \cdot 2^{-i}$

Thus the sequences $(y\_i)\_i$ and $(z\_i)\_i$ are Cauchy and they converge to a common point $c = \lim\_i y\_i = \lim\_i z\_i$. If $p(c) = 0$ then we take $(x\_i)\_i = (z\_i)\_i$, and if $p(c) = 1$ then we take $(x\_i)\_i = (y\_i)\_i$. $\square$

**Corollary:** Suppose $p : \mathbb{R} \to \\{0,1\\}$ and $a, b \in \mathbb{R}$ two reals such that $p(a) = 0$ and $p(b) = 1$. Then every Turing machine either runs forever or it does not run forever.

*Proof.* By the theorem, there is a Cauchy sequence $(x\_i)\_i$ such that $p(x\_j) \neq p(\lim\_i x\_i)$ for all $j \in \mathbb{B}$. Without loss of generality we may assume that $p(x\_j) = 1$ and $p(\lim\_i x\_i) = 0$.

Let $T$ be a Turing machine. Define a sequence $y\_i$ by $$y\_i = \begin{cases} x\_j & \text{if $T$ halts in step $j$ and $j \leq i$}\\ x\_i & \text{if $T$ does not halt within $i$ steps} \end{cases} $$ The sequence is well-defined because we may simulate $T$ up to $i$ steps and decide whether it has stopped or not within that many steps. Next, observe that $(y\_i)\_i$ is a Cauchy sequence because $(x\_i)\_i$ is a Cauchy sequence (we leave this as an exercise). Let $z = \lim\_i y\_i$. Either $p(z) = 0$ or $p(z) = 1$:

* if $p(z) = 0$ then $T$ runs forever. Indeed, if it stopped after $j$ steps, then we would have $z = x\_j$, and so $p(z) = p(x\_j) = 1$ would contradict $p(z) = 0$.
* if $p(z) = 1$ then $T$ does not run forever. Indeed, if it did, then we would have $z = \lim\_i x\_i$, and so $p(z) = p(\lim\_i x\_i) = 0$, contradicting $p(z) = 0$. $\square$

Now we can explain why this gives us Rice's theorem for real numbers. **The proofs are constructive, therefore they yield computable procedures.** This is true of any model of computability and any compute structure of reals that deserve to be so called. In fact, you can go back and read the proof as instructions for building a program -- all the steps are computable.

Thus, if we had a computable map $p : \mathbb{R} \to \\{0,1\\}$ and computable $a, b \in \mathbb{R}$ such that $p(a) = 0$ and $p(1) = 1$, then we could apply the computable procedures arising from the constructive proofs of the theorem and the corollary to create the Halting oracle. But the Halting oracle does not exist, therefore, every computable map $p : \mathbb{R} \to \\{0,1\\}$ is constant.

**Supplemental:** There was also a question about whether Rice's theorem is related to connectedness of the reals. Yes, it is essentially the statement that the reals are connected.

Let us first observe that a continuous map $p : X \to \\{0,1\\}$ (we take the discrete topology on $\\{0,1\\}$) corresponds to a pair of disjoint clopen (closed and open) sets $U, V \subseteq X$ such that $U \cup V = X$. Indeed, take $U = p^{-1}(\\{0\\})$ and $V = p^{-1}(\\{1\\})$. Because $p$ is continuous and $\\{0\\}$ and $\\{1\\}$ are open, $U$ and $V$ will be open, disjoint, and they obviously cover all of $X$. Conversely, any pair $(U,V)$ of disjoint clopens that cover $X$ determines a continuous map $p : X \to \\{0,1\\}$ that maps elements of $U$ to $0$ and elements of $V$ to $1$.

From this we learn that a space $X$ is disconnected if, and only if, there exists a continuous map $p : X \to \\{0,1\\}$ and $a, b \in X$ such that $p(a) = 0$ and $p(1) = b$ (we need $a$ and $b$ so that we get a non-trivial decomposition of $X$). There is another way to say the same thing: a space $X$ is connected if, and only if, all continuous maps $X \to \\{0,1\\}$ are constant.

In computable mathematics we have a basic theorem: *every computable map is continuous*. So, as long as we are within the realm of computable objects, Rice's theorem does in fact state that a certain space is connected. In the case of the classic Rice's theorem the space in question is the space of partial computable functions $\mathbb{N} \to \mathbb{N}$.

# Answer
> -1 votes
No. Or, at least, the proof isn't trivial, since you can choose among the (generally many) possible ways to compute a real, and may be able to choose one with a structure that is total w.r.t. the chosen property so that you don't reduce testing the property to the halting problem.

Also, I think I need a better understanding of what "nontrivial" means w.r.t. the properties of numbers. For Rice's theorem, "nontrivial" is basically non-syntactic and not implied by syntax. However each computable real number isn't a single program, but rather an equivalence class full of programs.

---
Tags: computability, real-numbers, computable-analysis
---


title: Using SMT Solvers in formula checking

text:
# Question
Title: Using SMT Solvers in formula checking
I'm currently working on a static analysis work in which I need to check whether a given formula is met or not. I hope the following example clarifies my requirement.

Suppose we have a list of three-addressed expressions whose operators are simple arithmetic and bit-wise operators (such as `add`, `sub`, `and`, `xor`). Each expression could have constant literals or variable symbols. For example, consider the following list:

```
a = b + 1
c = d
c = c xor d
a = a + c
a = a + 4

```

What I need is that to see whether a given formula is established or not. For example, the following formulas:

```
a == b + <some_constants>   # In this example: Yes, because a == b + 5
a == d + <some_constants>   # In this example: No

```

So can a SMT solver (Z3 for example) help me in this situation? If not, could you please point me out if there is a suitable tool applicable for this requirement?

# Answer
> 2 votes
Yes, absolutely. SMT solvers are actually quite well suited for such problems. Unfortunately, the input language to them (SMTLib) is rather machine-oriented, but there are many "high-level" interfaces to many solvers, Z3 itself providing a Python interface, for instance.

For this problem, I'll use the Haskell SBV library, which translates your constraints more or less directly to Z3. Note that I've put the equations into SSA form (single-static assignment), as is usual in such analyses. The whole problem is:

```
{-# LANGUAGE ScopedTypeVariables #-}

import Data.SBV

q = do k1 <- sInt32 "k1"
       k2 <- sInt32 "k2"

       a0 :: SInt32 <- forall "a"
       b0 :: SInt32 <- forall "b"
       c0 :: SInt32 <- forall "c"
       d0 :: SInt32 <- forall "d"

       let a1 = b0 + 1
           c1 = d0
           c2 = c1 `xor` d0
           a2 = a1 + c2
           a3 = a2 + 4

       constrain $ a3 .== b0 + k1
       constrain $ a3 .== d0 + k2

```

Also note that I (arbitrarily) picked 32-bit integers, though you can go with other types as well as needed. As stated, we get:

```
*Main> sat q
Unsatisfiable

```

Meaning that there's no such `k1`/`k2` that satisfy your equations, as you yourself observed. If we let go of the second constraint (by commenting out the very last line in the definition of `q`), we get:

```
*Main> sat q
Satisfiable. Model:
  k1 = 5 :: Int32
  k2 = 0 :: Int32

```

Here's the solver picked the arbitrary value of `0` for `k2` since there are no constraints on it; but `k1` became `5` as you predicted.

Long story short, yes; this sort of reasoning is absolutely possible with SMT-solvers; and there are high-level language bindings that let you express them rather concisely.

---
Tags: logic, arithmetic, sat-solvers, smt-solvers
---


# Question
Title: Using SMT solvers to generate random solutions to given predicate
I am interested in generating random solutions to predicates. I only need SMT for integers with the following predicates/functions \<, \>, \<=, \>=, ==, !=, +, *

The algorithm I want should produce a random assignment of variables to values (a substitution) such that applying the substitution to the given predicate yields a true statement. In the UNSAT case I just need to know that it is UNSAT.

It is probably important to clarify what I mean by random. I think a sufficient definition is that there might be an extra parameter that acts as a seed. If I give a different seed the algorithm should give me a very different solution rather than the same solution. Frankly I'm not sure how to cash this out but it much the same way that a typical random number generator generates an integer between X and Y (well with a modulus and an addition anyhow) I'd like to generate to a wider class of predicates.

I would like to use existing SMT solvers ideally in either Haskell or the JVM stack (more ideally Haskell however). I have thought of basically just randomizing the DPLL algorithm and translating the SMT problems into SAT my self but that sounds like a terrible idea when really good existing SMT solvers exist.

# Answer
Let $\varphi(x)$ be the SMT instance, so the task is to find $x$ such that $\varphi(x)$ is true.

One approach is to fix a hash function $h$ that maps a value of $x$ to an element of some small set $S$. Then, you randomly select a value $s \in S$, and ask your SMT solver to find a satisfying assignment for the formula $\varphi(x) \land h(x)=s$.

If you want to generate $k$ random satisfying assignments to $\varphi(x)$, you might choose $S$ to have size a bit bigger than $k$; that will probably suffice.

You probably want to make the hash function $h$ as simple as possible. There is a tradeoff between a simpler hash function (easier for the SMT solver to find satisfying assignments to $\varphi(x) \land h(x)=s$) and a better hash function that mixes the bits better (leads to more random solutions $x$). In practice, often surprisingly simple hash functions suffice. For instance, sometimes your hash function can be chosen via the following simple procedure: pick a random subset of the variables in $x$, project to just those variables, and then hash those variables in some simple way. The hash function itself can be a relatively simple function, e.g., a random linear function: for example, select a random boolean matrix and multiply it with the bit vector obtained from $x$, so that $h(x)=Mx$ for some boolean matrix $M$).

There may be other ways to do it, but this is one way that allows you to use an existing SMT solver, unmodified, as a black box.
> 4 votes

# Answer
A simple approach would be to simply generate a solution, and then ask for a "different" one, surely? Since you mentioned Haskell, you can use the SBV library to implement this easily, and use the `allSat` function to generate "different" assignments. Here's an example; not quite the same question as yours but somewhat similar, coded in that style: https://hackage.haskell.org/package/sbv-7.2/docs/Data-SBV-Examples-Queries-FourFours.html
> 1 votes

---
Tags: functional-programming, nondeterminism, smt-solvers
---


# Question
Title: SMT solves with functions for free varibles
So this sounds like this might lead to an undecidable theory but I thought I would give it a try and ask about it after I found nothing on the subject. I am somewhat interested in finding functions which are counter examples to predicates (or solutions to the inverse rather). I would like to restrict the functions to some small class however (possibly even smaller than primitive recursive) so I think there is hope of this working if I restrict them enough.

Has any work been done in this area? Have any tools been written for such things?

# Answer
> 1 votes
SMT solvers do support uninterpreted-functions as part of many logics. If there's a counter-example, then they will also print a "counter-example" function, which will be the predicate you're looking for. If you have a concrete example, we can surely see if one can be coded up using Z3.

---
Tags: logic, sat-solvers, smt-solvers
---


# Question
Title: Branch & Bound: Avoiding equivalent solutions
There is a certain family of typical branch & bound problems in which we have to put $n$ objects into $m$ indistinguishable bags.

Usually solutions are represented by $n$-size vectors in which $V\[i\]$ means that the $i$-th element is in the $V\[i\]$-th bag.

Is there a way to avoid generating equivalent solutions without performing an $\mathcal{O}(n)$ time check once the potentially equivalent solution has been built?

I was trying to do something similar as when avoiding circular permutations, but no adaptations seems to work.

# Answer
You could impose a canonical ordering on the bags.

For instance, in each bag find the lowest-numbered item in that bag, and imagine labelling the bag with that number. Now add the additional constraint that to be a valid solution, the bags must be in sorted order according to their label. In other words, the label on the $i$th bag must be less than the label on the $i+1$st bag.

If you can express this constraint within your system, it ensures that each equivalent solution will be generated only once.
> 2 votes

---
Tags: time-complexity, branch-and-bound
---


# Question
Title: Algorithm to choose the best team of 6 Pokémon given a constraint
Apologies if this is a duplicate. I searched for some time and the closest I could find was the Knapsack Problem, which does not fit because I have a fixed team size & a different value function.

I have $N \approx 50$ Pokémon, from which I need to choose a team of six to attack an enemy. Each pokemon can survive for a certain time "$t$" against the enemy, and each pokemon does a certain amount of damage per second "$DPS$" to the enemy. I may or may not defeat the enemy, but I would like to optimize the damage I can do to it within the time limit of 300 seconds without my entire team dying.

These data are sufficient to determine the optimal team. The damage done by a team, which fights in order of highest \> lowest $DPS$, is the sum $$Damage(DPS\_i, t\_i) = \sum\_{i=1} DPS\_i * \hat{t\_i} $$ where $0\<\hat{t\_i}\<t\_i$ is the amount of time each pokemon battled for. Typically the first few pokemon will battle until they die ($\hat{t\_i}=t\_i$), one pokemon will win with a fraction of its health remaining ($0\<\hat{t\_i}\<t\_i$), and the rest may never get to battle ($\hat{t\_i}=0$).

The optimization problem can be phrased as follows:

* Maximize the function $Damage(DPS\_1, ST\_1, ..., DPS\_6, ST\_6)$
* Given the constraint that $\sum\_i t\_i \>300$

It is clear that this can be brute-forced by checking the damage and survival time of all team combinations. This is not an option because it takes too long.

Another possibility was to start with the highest-DPS team and then make "trades" in order of highest gain in $t$ per sacrifice of $DPS$. However I'm not convinced this will converge to the optimal solution.

I would be very thankful for any suggestions or references to analogous problems.

# Answer
You could use A\* to solve this problem. A\* is designed to optimally search through a state space to solve a problem based on trying to minimize a "cost."

The first thing I'd do is reframe the problem. Instead of thinking in terms of time and DPS, use time and "damage" by multiplying them together. I recommend this because that's the term you're trying to maximize. It'll make it clearer.

Let's define a "state" in this A\* algorithm as a team of 0-6 Pokemon, and their total damage. State transitions consist of adding Pokemon to the team, updating the total damage. Don't forget that this is a combination problem, not a permutation problem. Team `ABCDEF` is the same as team `FEDCBA`. The easy way to handle this is to sort by name when adding to the team. *(And as a small optimization, if you care, 50 pokemon is small enough to fit into a 64-bit integer, so your teams could be defined by a datastructure as small as an int)*

To fit this problem to A\*, we have to define a goal function. The goal function defines an "acceptable" solution, but saying nothing about whether its the best solution. The goal function is a team of 6 Pokemon that has a total time greater than 300. This will satisfy your constraint.

We can handle your goal of maximizing damage by using it as our "cost" metric. A simple way to do this is to say the "cost" is equal to $-damage$, that is to say that it's always a negative number. A\* doesn't mind the final cost being negative.

The last thing you need for A\* is the "heuristic underestimate." You need an estimated cost for finishing out the team that is always an underestimate (a lower "cost" than the real answer, which means a higher damage than the real best answer). This can easily be constructed by finding a "best damage team" using the remaining Pokemon, ignoring the time constraint.

Put those together, and A\* will do the rest. A\* is "optimal," meaning that it is the most efficient algorithm you can come up with given the information provided. Any more ideal algorithm will need to use more information than what we gave A\* (i.e. more than just a cost function and a heuristic underestimate).
> 2 votes

# Answer
After observing the worst case performance of my other answer, I decided to take another swing at it. This time I decided to use dynamic programming approach. In dynamic programming, we break the problem into smaller pieces and then use those pieces to build the bigger solution.

In the case of these Pokemon, we observe that the effect of any subteam of Pokemon is not affected by the performance of any others. If I have a team `ABCDEF` and look just at the DPS and time of the `AB` subteam, its identical to `AB`'s performance if it were part of team `ABXYZW`. Thus, we can maximize the value of subteams, and then bring the results together.

First, note that the original brute force approach has to explore $\_{50}C\_6$ possible teams -- that is, out of 50 pokemon, it chooses 6 of 50, combinatorially. $\_{50}C\_6 = 15890700$, so that's the number to beat if we want to be more efficient than brute force. *(As an aside, 16 million is actually really small for computers. The brute force approach is actually probably good enough)*

Let's drop this number by building teams of 2 pokemon first, then combining those teams into a final answer. To explore teams of 2, we have to study $\_{50}C\_2 = 50\*49 = 2540$ different teams of 2. Now from these teams, we can reject the majority of them as "provably worse" than another team. A team is "provably worse" than another if they are beaten on both damage and longevity. For example, if `AB` can deal 500 damage and last 50 seconds, and `CD` can deal 400 damage and last 40 seconds, there is no case where you would want to use `CD` in which `AB` would not be simply better.

In the worst case, every single pokemon has a unique lifespan, so there's $50+50=100$ possible lifespans for a team of 2. Realistically, there are likely to be fewer possible lifespans, because many Pokemon will last the same amount of time. However, this guarantees that, at most, we will only have to consider 100 possible 2-pokemon teams in the next step. Why? Because for any given lifespan of a 2-pokemon team, there's no reason to include any teams which are anything less than the best for that lifespan. There's only 100 possible lifespans, thus only 100 worthy teams to consider going forward.

Now we can build up a team of 6. This will involve picking 3 teams of 2. You'll have to make sure we don't include a pokemon twice when you write your code, but that's easy. Thus we have 100 2-pokemon teams, and we choose 3 from that. $\_{100}C\_3=161700$, so you will have to consider around 161k sets of 3 2-pokemon teams to find your best solution.

Thus, our total number of teams (of any size) built is $2450+161700=164150$. Doing a quick division, this shows that our solution now costs 1.03% of the cost of the brute force. This is, of course, a worst case. In reality, there will likely be more collisions on the lifespan of the different 2-pokemon teams, reducing this even further.
> 0 votes

# Answer
You can solve this problem with dynamic programming. We will first pick the member of the team that wins with partial health remaining; there are 100 possibilities for it, so just try all possibilities, and for each, do the following procedure to pick the rest of the team. That gives you 100 candidate teams; choose the best one.

So now suppose we have picked the team member who wins with partial health remaining; call her Gina. Next, we will pick the team members who die. By assumption, all of those team members have DPS that is at least as large as Gina's DPS. So, discard all Pokemon whose DPS is lower than Gina, and form a pool from the reamining Pokemon.

Now we want to pick a group of at most 5 Pokemon from that pool, such that the sum of their survival times (their $t\_i$ values) is somewhere in the range $\[300-t\_\text{Gina},300\]$ and such that the sum of their damages ($DPS\_i \times t\_i$) is as large as possible. That's a variant of a knapsack problem, and can be solved with dynamic programming. Let $A\[j,k,s\]$ denote the maximum-achievable sum-of-damages, for a team that uses at most $k$ Pokemon selected from among the first $j$ Pokemon in the pool and that has a sum of survival times equal to $s$. It's easy to write a recursive expression for $A\[j,k,s\]$; we have

$$A\[j,k,s\] = \max(A\[j-1,k,s\], A\[j-1,k-1,s-t\_j\] + DPS\_j \times t\_j).$$

Applying dynamic programming then gives a way to compute all of the $A\[j,k,s\]$ values. Now you just take the maximum value of $A\[j,k,s\]$, where $j$ is the number of Pokemon in the pool, $k$ ranges over $0 \le k \le 5$, and $s$ ranges over $300-t\_\text{Gina} \le s \le 300$. That gives you a way to pick at most 5 other Pokemon who die before Gina.

What's the running time? The dynamic programming algorithm fills in the $A$ array in about $100 \times 5 \times 300$ steps, as there are 100 possible values of $j$ 5 possible values of $k$, and 300 possible values of $s$. You have to run the dynamic programming algorithm 100 times, for each choice of who will play the role of Gina. That's $100 \times 5 \times 300 \times 100 \approx 2^{24}$ ... not much better than brute force.

It might be possible to replace the dynamic programming algorithm with a greedy algorithm. You can sort the pool by decreasing value of $DPS\_i \times t\_i$, then try to pick Pokemon from the pool (in sorted order) until sum of their survival times ($t\_i$ times) is over 300. That gives you a team. Repeat 100 times for each possible choice of who plays the role of Gina.
> 0 votes

---
Tags: algorithms, optimization, reference-request
---


# Question
Title: Is the word problem for regular languages in ALogTime?
Given a regular language (by a sparse or dense matrix describing the graph of the NFA) (initially the description was supposed to be a regular expression) and a word, can the problem whether the word belongs to the regular language be decided on a (random access) alternating Turing machine in a logarithmic amount of computation time? (The many links above try to compensate for the fact that I didn't find a nice self-contained description of ALogTime.) The length of the input is the length of the description of the regular language plus the length of the word.

# Answer
If the regular expression is not fixed, it is rather doubtful that your problem belongs to ALOGTIME. However, the phrase *word problem* usually refers to a fixed setting, which in this case means that the regular language is fixed.

If the regular language is fixed, this is apparently shown in Barrington's famous paper. Alternatively, you can describe a logtime game for deciding the word problem for regular languages. The game starts with the YES player stating the final (accepting) state and the state at the middle (the initial state is of course fixed). The NO player then chooses one of the halves, and the game continues until it comes down to a word of length 1, in which case the problem can be settled by examining one character of the input.
> 4 votes

# Answer
If (the regular expression or) NFA is not fixed, then the problem is NL-complete. So if the problem would be in ALogTime, then ALogTime=L=NL, which is an open problem.

It is clear that the problem is in NL, we only need one pointer into the word on which the NFA runs, the current (and guessed next) state of the NFA (its size is $\log |A|$, if $A$ is a description of the NFA by a list of possible transitions), and a pointer into the description of the NFA.

To see that it is NL complete, reduce reachability to the NFA membership problem over the unary language. Use the given digraph as NFA, and add a self-loop to the target node whose reachability is being checked. Let the source node be only state in the set of initial states, the target node be the only state in the set of (accepting) final states, and check whether this NFA accepts the word $1^n$, where $n$ is the number of nodes of the given digraph (which is also the number of states of the constructed NFA).

The reason why Yuval Filmus' algorithm (explained in his answer above, together with the comments below) doesn't solve this problem in ALogTime is not that the last step would not work. That checking can indeed be done in NLogTime. But the size of a state is $\log n$ if the NFA is not fixed, and hence the algorithm takes $\log^2 n$ time instead of $\log n$ time.
> 2 votes

---
Tags: complexity-theory, regular-languages, decision-problem
---


# Question
Title: Are the undecidable languages closed under complement?
Are the undecidable languages closed under complement? How can the answer be proved?

# Answer
> 6 votes
Suppose you could decide the complement. Wouldn't you then be able to decide the language itself?

---
Tags: formal-languages, computability, undecidability, closure-properties
---