# Question
Title: For any language $A$, there is $B$ such that $A \le _T B$ but $B \nleq _T A$
I am trying to come up with a proof for the following:

> For any language $A$, there exists a language $B$ such that $A \le\_{\mathrm{T}} B$ but B $\nleq\_{\mathrm{T}} A$.

I was thinking of letting $B$ be $A\_{\mathrm{TM}}$, but I realize that not all languages are Turing reducible to $A\_{\mathrm{TM}}$, so $A \le \_T B$ would not hold. What other choice of $B$ do I have that would allow me to write a TM which uses an oracle for $B$ to decide $A$?

Thanks!

# Answer
Let $B=A'$, the Turing jump of $A$. This is a basic result in the theory of the Turing degrees.
> 1 votes

# Answer
Before diving into the *good* answer - namely, that we can relativize the halting problem to assign to each language $X$ a language $X'$ such that (among other things) $X\<\_TX'$ \- it's worth seeing the *silly* answer:

* Cantor showed that there are uncountably many languages.
* But every specific language $A$ can only compute countably many languages: a single Turing machine can only possibly yield one reduction from a given language $A$, and there are only countably many Turing machines.

So in fact we know, without doing any serious work, that:

> For every language $A$, **most (= all but countably many)** languages $B$ satisfy $B\not\le\_TA$.

Now we combine this with the *Turing join*: given languages $X,Y$, the join $X\oplus Y$ consists of "interleaving" $X$ and $Y$. There are various ways to define it - e.g. thinking of $X$ and $Y$ as sets of naturals, we usually let $X\oplus Y=\\{2i: i\in X\\}\cup\\{2i+1: i\in Y\\}$ \- but the important feature is that $X\oplus Y\ge\_TX,Y$ *(and in fact is their $\le\_T$-least upper bound)*.

So we can apply the above, to get:

> For every language $A$, **most (= all but countably many)** languages $B$ satisfy $A\<\_TA\oplus B$.

---

This then raises the question of giving a *non-stupid* proof, namely a natural way to produce a language strictly more complicated than a given one, and this is what the Turing jump is for; but it's worth understanding this nonconstructive argument on its own.
> 1 votes

---
Tags: computability, reductions, undecidability
---


title: A question about linked list

text:
# Question
Title: A question about linked list
I would like to check the answer of this exercise:

*A circular doubled linked list with N elements has pointers that cost **k** bytes each of space in memory. How many bytes do the pointers of this list cost in total?*

Researching about circular linked lists, i can assume that each node has 2 pointers. So am i right to say that the answer is 2(n)k bytes?

Thanks.

# Answer
The list takes $2\*N\*k$ bytes in total. A circular linked list is just a simple linked list with its last node's next pointer pointing back towards head. So, no extra pointer is required to make it circular. Hence, the total space is $2\*N\*k$.
> 1 votes

---
Tags: algorithms, data-structures, linked-lists
---


title: Show that $T(2^n) = \Theta(3^n)$

text:
# Question
Title: Show that $T(2^n) = \Theta(3^n)$
We have a function $T(n)$ defined by $T(1) =1$ and $T(n)=3T(\lfloor n/2\rfloor)+n$ for $n \> 1$. We need to show that $T(2^n)=\Theta (3^n)$. How should I approach this question? Any suggestion?

# Answer
First of all, try to solve the recurrence relation using the master method.

Since $f(n) = O(n^{\log\_2 3 - \epsilon})$ for some $\epsilon$, this is the first case of the master method. Therefore $$T(n) = \Theta(n^{\log\_2 3})$$

If you replace $n$ by $2^n$, you will get your answer. i.e. $$T(2^n) = \Theta(2^{n\log\_2 3}) = \Theta(3^n)$$
> 1 votes

---
Tags: asymptotics, recurrence-relation
---


title: Why can't hash coding be reversed?

text:
# Question
Title: Why can't hash coding be reversed?
Why is it impossible to reverse a hash code? There could be some way to crack this coding?

# Answer
Because, in general, hashing is not injective.

Being injective is a property of a function which states that each distinct element of the domain is mapped to distinct element of codomain. It means that given a value of a function, you will (if it is a valid value) know from what it came from. For more on this, see injective function.

Therefore, if hashing function $h$ is not injective, it can happen that two elements $A,B$ could be mapped to $H =: h(A) = h(B)$ and from knowing only $H$ you cannot determine whether it is the result of hashing $A$ or $B$.

But, there is a concept of perfect hashing which is injective.

---

If your question is about cryptographic nature of hashing, then the reason is the same as why any good cipher is "unbreakable". It is not that it is impossible to decrypt it (it surely cannot be the case, because then the reciever of cipher could not do it), but is just very very time consuming without knowing the key. You can find out more on that at Cryptography Stack Exchange.
> 2 votes

# Answer
As Sandro said, the issue is that a hash function is not injective.

This is easily understood by recognizing that you are mapping from a larger set to a smaller set, and thus losing information.

Perhaps it's easier to understand in terms of other non-injective functions. Say you have pairs of integers $(x,y)$ and you map them to their projection $y$. You have sacrificed the information $x$ to perform this mapping, and there is no way to regain it. If you ask me what is the inverse of 3, I am unable to tell you a unique answer, because every $(x,3)$ maps to 3.
> 1 votes

---
Tags: hash, one-way-functions
---


# Question
Title: Answering questions about the recurrence of certain aspects of an algorithm
I am thoroughly confused by a problem that was brought up in class:

Given the following pseudocode for a function RANDOM which generates a random number based off of recursion:

```
function RANDOM(n)
1.  if n = 1 then
1.1     return 1
1.2 else
2.1     assign x = 0 with probability 1/2, or
2.2     assign x = 1 with probability 1/3, or
2.3     assign x = 2 with probability 1/6
3.      if x = 0 then
3.1         return (RANDOM(n-1) + RANDOM(n-2))
3.2     end-if
4.      if x = 1 then
4.1         return (RANDOM(n) + 2*RANDOM(n-1))
4.2     end-if
5.      if x = 2 then
5.1         return (3*RANDOM(n) + RANDOM(n) + 3)
5.2     end-if
6.  end-if
end-RANDOM

```

Answer the following three questions:

1. Give the recurrence equation for the expected running time of RANDOM.
2. Give the exact recurrence equation for the expected number of recursive calls expected by a call to RANDOM(n).
3. Give the exact recurrence equation for the expected number of times the return statement at line 5.1 is executed, in all calls to RANDOM(n), recursive or not.

Our professor gave us a version of this pseudocode that goes like this:

```
function RANDOM(n)
1.  if n = 1 then
1.1     return 1
1.2 else
2.1     assign x = 0 with probability 1/3, or
2.2     assign x = 1 with probability 1/3, or
2.3     assign x = 2 with probability 1/3
3.      if x = 0 then
3.1         return (RANDOM(n))
3.2     end-if
4.      if x = 1 then
4.1         return (RANDOM(n-1) + 1)
4.2     end-if
5.      if x = 2 then
5.1         return (3*RANDOM(n-1) + RANDOM(n-1) + 1)
5.2     end-if
6.  end-if
end-RANDOM

```

And answered the three questions as follows:

1)

T(n) = expected running time of RANDOM

$$ T(1) = 1 $$

$$ T(n) = 1 + \frac{T(n)}{3} + \frac{T(n-1)}{3} + \frac{T(n-1) + T(n-1)}{3} $$

which, after some algebra, comes out to equal:

$$ T(1) = 1 $$

$$ T(n) =\frac 32 * T(n-1) + 1, $$ , where $n\>=1$.

I have one question about the answer to this problem. Why does the constant $1$ in the original equation not matter to the equation? Is it because it is being lumped in with constant time?

2)

R(n) = the expected number of recursive calls executed by a call to RANDOM(n). $$ R(1) = 0 $$

$$ R(n) = \frac{1+R(n)}{3} + \frac{1+R(n-1)}{3} + \frac{2+2\*R(n-1)}{3} $$

, which, after some algebra, comes out to:

$$ R(1) = 0 $$

$$ R(n) = \frac 32 * R(n-1) + 2 $$

, where $ n\>0 $.

I have a couple of questions about the set-up of this problem.

1. Why is 1 added to the numerators of the first two rational numbers?
2. Similarly, why is 2 added to the numerator of the last rational number?

Finally,

3)

C(n) = the exact number of returns from line 5.1 of RANDOM(n), recursive or not. $$ C(1) = 0 $$

$$ C(n) = \frac {C(n)}{3} + \frac {C(n-1)}{3} + \frac {1+2\*C(n-1)}{3} $$

, which, after some algebra, comes out to be:

$$ C(1) = 0 $$

$$ C(n) = \frac 32 * C(n-1) + \frac 12 $$

, where $n\>0$.

My main question for this answer is: why is 1 added to the last rational number in the expression? What does that 1 represent?

I am so lost, and desperate. Any attempt to shine light on these answers would be such a great help to me. Thank you.

# Answer
> 1 votes
Firstly, there is one minor typo in the question. The "$T(n) =\frac 32 * T(n-1) + 1$" should be "$T(n) =\frac 32 * (T(n-1) + 1)$" since this equality is said to be obtained by simple algebra from the equality above it. However, this typo does not affect either the question or this answer.

---

The answer to all of your questions are so simple that I can hardly imagine that you missed it. Well, on the other hand, it is indeed very easy to miss it.

Let me give you a simple example to illustrate the answer. Suppose we have the following function, which computes the factorial.

```
function FACTORIAL(n)
    if n = 1 then
        return 1
    else
        return  n * FACTORIAL(n-1)
    end-if

```

Suppose we have made a call, `FACTORIAL(4)`. That means we must have called `FACTORIAL(3)`, `FACTORIAL(2)` and finally `FACTORIAL(1)`. So we have made four calls to this function in total, the last three of which are called recursively. In fact, we have the following recurrence relations for $U(n)$, the number of recursive calls made in `FACTORIAL(n)`. $$U(1) = 0$$ $$U(n) = 1 + U(n-1), \text { for } n\gt 1$$ Notice **the first "1" in the last equality**, which stands for the call to FACTORIAL with parameter $n-1$ in the code, `n * FACTORIAL(n-1)` while $U(n-1)$ comes from the number of recursive calls made by `FACTORIAL(n-1)`. In other words, the recursive calls made by `FACTORIAL(n-1)` does not include that call itself, which is, though of course, counted towards the recursive calls made by `FACTORIAL(n)`. We can also check by contradiction. Let us suppose we did not have that "1". Then we would get $U(4)=U(3)=U(2)=U(1)=0$, which said that we had made no recursive calls to `FACTORIAL` when we had computed `FACTORIAL(4)`, which is not true at all.

In the same way as in this simple example, all those constant 1's and one 2 in the question come from right where the calls are made. For example, when `x = 2`, the function will return `(3*RANDOM(n-1) + RANDOM(n-1) + 1)`, which incurs $(1+R(n-1)) + (1+ R(n-1)) = 2 + 2\*R(n-1)$ recursive calls.

---
Tags: algorithms, algorithm-analysis, recurrence-relation, recursion, pseudocode
---


# Question
Title: How can a user process even try to access a memory location its not allowed to when it doesn't have access to page table?
So is it even possible for a user process to even try to access a physical memory location that does not belong to it and therefore getting an error by operating system?

because for example with a 32 bit cpu the user process has an illusion of having a 32 bit memory all for it self (correct me if I'm wrong) and each page of this virtual memory has a corresponding entry in the page table that says whether this page exists in the real memory or not

but considering user process does not have access to the page table to modify it, how can a process even try to access a memory location in physical memory that doesn't belong to it considering the page table won't let that happen?

does this scenario ever happen? (because i remember reading something about operating systems using exceptions when a process tries to access something that does not belong to it but I'm not sure)

# Answer
> 2 votes
Yes, this typically happens on modern operating systems such as Linux and Windows because they implement demand-paging. That is, whenever a process requests from the OS to allocate a chunk of memory, the OS by default only allocates virtual pages that are not actually mapped to physical pages. The OS satisfies the allocation request by simply modifying its internal data structures to remember that those virtual pages have been allocated and it's OK for the process to access them. This enables the OS to distinguish between virtual pages that have been allocated and those that have not. The OS does not update the corresponding page table entry and leave it invalid.

When an allocated virtual page is accessed for the first time, the CPU sees that the page table entry that describes that virtual page does not map to a physical page and so it will raise an exception known as a page fault. The OS handles the exception by allocating a physical page and updating the page table entry. Then it lets the CPU re-execute the instruction that attempted to access the page and caused the fault. When the instruction is executed again, it will be able to successfully access the page since it's now backed by physical main memory.

The alternative to demand-paging is anticipatory paging where the OS allocates a physical page and updates the page table immediately whenever it allocates a virtual page.

---
Tags: operating-systems, memory-management, virtual-memory
---


# Question
Title: Are there connections between the theory of computation and machine learning?
I am wondering if studying the Theory of Computation/ Computational Complexity theory, specifically Sipser's 'Introduction to the Theory of Computation' will help me do machine learning/statistics/data science better. Are there any connections? I intend to study the book even if there aren't any connections.

# Answer
> 1 votes
Yes, check out Computational learning theory (Algorithmic learning theory) and conferences COLT and ALT although the connection with machine learning is arguably limited.

---
Tags: complexity-theory, computability, machine-learning
---


# Question
Title: Complexity of the language of all TMs $M$ such that $L(M)$ is decidable
Let $$R = \\{\langle M \rangle \mid L(M) \text{ is decidable}\\}.$$ Is $R$ recursively enumerable or co-recursively enumerable?

# Answer
This set is not r.e. nor co-r.e., in fact it's complete at the 3rd level of the arithmetic hierarchy ($\Sigma^0\_3$-complete). This is shown in Soare's textbook.
> 1 votes

---
Tags: computability, turing-machines, semi-decidability
---


title: A' not computable in A

text:
# Question
Title: A' not computable in A
Recall A'= $\\{x \mid \phi^A\_x(x)$ halts and accepts $\\}$

In this article, a proof that A' not computable in A is given: http://www.math.uchicago.edu/~may/VIGRE/VIGRE2006/PAPERS/Flood.pdf

He constructs the function f(x)= $\phi\_x^A(x)$ +1 if x in A and 0 if x not in A

Shouldn't it be f(x)= $\phi\_x^A(x)$ +1 if x in A' and 0 if x not in A'

since we need $\phi^A\_x(x)$ to halt and output a number provided it actually can?

then f will be computable in A and we can then go on to prove that f $\neq$ $\phi^A\_x$ for the witness x

# Answer
> 2 votes
You are right. It seems you completely understand this already: in any case the result can be found many places, as it is a basic result about the Turing degrees.

---
Tags: computability, relativization
---


# Question
Title: What is a non-ambiguous CFG for generating the set of natural numbers?
I'm trying to write a non-ambiguous context-free grammar that can generate the set of natural numbers, including the 0. My current solution is the following grammar:

$\mathcal{G}: S \rightarrow 0\ |\ ...\ |\ 9\ |\ 1S\ |\ ...\ |\ 9S$

From what I understand, there is not an algorithm to determine whether my guess is correct, thus only I—or you—can convince myself it is (or it is not, of course).

# Answer
"From what I understand, there is not an algorithm to determine whether my guess is correct." It looks like your understanding is wrong.

There is no algorithm that determines whether **any** given formal language grammar is ambiguous context-free. There is no algorithm that determines whether **any** given formal language grammar is inherently ambiguous context-free. However, it is possible to decide many particular grammars is (inherently) ambiguous context-free or not by some algorithms. For example, the trivial algorithm that just outputs "ambiguous context-free" determines the grammar with rules $S\to A|B$, $A\to c$, $B\to c$ as ambiguous context-free. For example, the trivial algorithm that always outputs "not inherently ambiguous context-free" determines all regular grammars as not inherently ambiguous context-free.

As said by rici, your grammar is regular. There is an algorithm that can decide any given regular grammar is ambiguous or not. (Immediately by definition, a regular language is context-free.). As demonstrated by Dmitri Urbanowicz, your grammar is, in fact, not ambiguous.

As said by Dmitri Urbanowicz, your grammar is wrong since it cannot generate number 101. Here is a correct grammar, which can be shown to be non-ambiguous context-free.
$\quad S \to BT|A$
$\quad T \to AT|A$
$\quad A \to B|0$
$\quad B \to 1|2|3|4|5|6|7|8|9$
> 5 votes

# Answer
This grammar is unambiguous, because no pair of productions can lead to the same string. Since $S$ doesn't generate empty string, you either get different first characters or strings of different lengths.

Though this grammar is unable to generate $101$, for example.
> 4 votes

# Answer
A possibile solution is also:

$$ \begin{split} \mathcal{G}:\ & S \rightarrow 0\ |\ 1A\ |\ ...\ |\ 9A \\ & A \rightarrow \varepsilon\ |\ 0A\ |\ ...\ |\ 9A \end{split} $$
> 2 votes

---
Tags: formal-languages, formal-grammars, compilers
---


# Question
Title: Using a 16-bit 2,s Complement normalised floating-point representation; 10-bit fractional mantissa and a 6-bit integer exponent: express 2.171875
So far I know how to normalize when you are given, say: 1111010010 Mantissa, and 000100 exponent and are told that it's a positive number:

```
1.111010010 and the exponent value is 4
move point 3 to the right: 1111.010010
subtract exponent by 3 = 1; 000001
replace extra binary digits behind sign bit with trailing 0s
1.010010000

so 1.010010000 , 000001
is the normalized form.

```

Now how do I express 2.171875 under the same representation? I started by converting it to binary: 10.0010110 but how do I represent that as 10-bits 2'C Mantissa and 6-bits exponent to begin with? Or am I completely lost?

# Answer
> 0 votes
I am lost with the given algorithm for a normalized representation.

The most significant bits should be kept, which is *not* what I see in your example.

* 1.111010010 x 2^4 = .1111010010 x 2^5 (This keeps the dot leftmost, and one can possibly truncate bits to the right - or even round 0xxx down, and 1xxx up for positive numbers). Having a 1 immediately after the dot, allows the highest precision, compare with .00001111010010,
* sign 1 bit = **0** (both ones complement, twos complement)
* mantissa '1' + 8 bits = **111101001**
* exponent 6 bits two-complements = **000101**
* result: **0 11110101001 000101**

This is just one possible variant: a ones complement mantissa with extra sign bit (but almost a two's complement mantissa). Here it shifted till a `.1xxx` for a nonzero number. (Hence that 1 is almost redundant.)

Now your recipe:

* 1.111010010 x 2^4 = 1111.010010 x 2^1
* sign 1 bit = **0** (both ones complement, twos complement)
* mantissa 9 bits = **1111 01001**
* exponent 6 bits two-complements = **000001**
* result: **0 11110101001 000001**

It only differs in the implicit +4.

For the .1 method:

* 2.171875 = number \< 1, times 2^exp = 0,54296875 x 2^2
* 0,54296875 = 0.1xxx
* etcetera

---
Tags: floating-point
---


# Question
Title: How many rotations after AVL insertion and deletion
Is it true that inserting an element to an AVL tree requires $O(1)$ rotations?

How many rotations, does deletion from AVL require?

I've searched for these two questions with no luck so far.

# Answer
> 5 votes
The obvious resource, Wikipedia, I did not find very helpful.

When inserting an element at most one (single or double) rotation is needed, at the lowest point where the tree is out of balance. After rotation the height of that subtree is the same as in the original subtree, so all nodes upwards are balanced. See the answer by colleague Raphael to "Does the rebalancing propagate upwards only to update the height of the nodes in an AVL tree?"

> picture: originaly the balance at node $p$ equals $-1$ (left subtree one deeper than right subtree). After insertion in the left subtree the balance is now $-2$. Then rebalancing at $p$ will restore the balance at the root to $0$, while at the same time the heigth of the tree at new root $q$ is now the same as for the original tree. This means that all balance factors above will not change.

When deleting occurs, one is not always that lucky. Rotation does not necessarily restore the original tree height, so the tree has to be updated at other levels higher up in the tree. Worst case trees are those which are minimal AVL trees, meaning with no node can be removed without violating the AVL property. There you might have to rotate every level, thus a logarithmic number of times.

> picture: an AVL tree of "Fibonacci" type. Deleting the node marked "X" results in unbalance at $11$. Rebalancing at $11$ leads to a tree that is shorter than the original tree, and we get an new imbalance at the root. Another rotation will solve that problem. Note that again the resulting tree is shorter than the original one, so this would propagate to levels above.

---
Tags: algorithm-analysis, data-structures, runtime-analysis, search-trees, balanced-search-trees
---


# Question
Title: Complexity of Problems and Ease of Verification
Comparison-based sorting algorithms have a minimum worst-case complexity of $O(n \log n)$, while it is easy to check that an array is sorted in $O(n)$ time.

Are there other problems with proven minimum complexity $O(n^k)$ for some $k \> 1$ that can be checked in $O(n)$ time? How high can $k$ get?

# Answer
Trivial arbitrarily hard example based on the existence of an one-way function $f : \mathbb{N}^k \to \\{0, 1\\}$. The problem:

> Given a set $S$ of size $n$, can we choose a tuple $t$ formed from $k$ elements of $S$ such that $f(t) = 1$?

Since $f$ is one-way you must check all $n^k$ possible $k$-tuplets of elements from $S$, but checking whether a proposed solution is correct is simply $O(1)$ time.

---

However, if you're looking for interesting or deep results, I'm afraid you're out of luck. Forget "at least this hard to compute but easy to verify", we barely even have "at least this hard to compute" for almost anything. See this scarce list here.

Why are lower bounds so scarce? Because they essentially require omniscience in a certain subject area. You must prove that no matter how smart, doing better than the lower bound is impossible. It's as if you're simultaneously exploring every possible algorithm, finding their time complexities and showing that they're bigger than the lower bound. It's nearly impossible, which is why we barely have any proofs that go beyond some version of "you must read all input".
> 1 votes

---
Tags: algorithms, complexity-theory
---


# Question
Title: How to define (logically) the complement language?
I found it a little bit difficult and confusing to define the complement language in specific cases. For example, take the next language:

$$L = \left\\{\langle M, w\rangle \\;\middle|\\; \begin{array}{l}M \text{ is a Non-Deterministic TM,}\\ \text{and it has an accepting run on }w\text{ of length }\leq |w|\end{array}\right\\}\\,.$$

When I've tried to find $L$-complement I did it like this:

> M isn't an NDTM OR it doesn't have an accepting run on $w$ of length $\> |w|$.

My way of thinking is to change each one of the quantifiers. Is that OK? Someone can write the logic behind that (I want to understand for other cases as well, this language isn't critical right now)?

Thanks!

# Answer
This is just the application of de Morgan's laws: \begin{align\*} \neg(A\land B) &\equiv (\neg A)\lor (\neg B)\\ \neg(A\lor B) &\equiv (\neg A)\land (\neg B)\\,. \end{align\*} These are fairly obvious, if you think about them for a moment: if something isn't both $A$ and $B$, then it must fail to be one or the other (or both); if something is neither $A$ nor $B$, then it is not $A$ and it is not $B$.

In your case, $A$ is "it is a NTM" and $B$ is "it has an accepting run on $w$ of length at most $|w|$." Using the first version of the law, the complement is "it is not an NTM or it does not have an accepting run on $w$ of length at most $|w|$."

That alone may be enough to answer the question, but you might also want to push the negation in the second half ("it does not have an accepting run on $w$ of length at most $|w|$"). In this case, we need the rules for negating quantifiers: \begin{align\*} \neg\forall x\\,C(x) &\equiv \exists x\\,\neg C(x)\\ \neg\exists x\\,C(x) &\equiv \forall x\\,\neg C(x)\\,. \end{align\*} Again, take a moment to convince yourself that these are true: if it's not true that everything is $C$, it must be that something is not $C$; if there doesn't exist something that is $C$, then everything must be not $C$.

In your case, writing $B$ more formally gives "There exists a run $r$ on $w$ such that $r$ accepts and $r$ has length at most $|w|$", so $C$ is the property "is accepting and has length at most $|w|$." Negating $B$ gives "Every run $r$ on $w$ is not both accepting and of length at most $|w|$" and applying de Morgan again gives "Every run on $w$ is rejecting or has length more than $|w|$ (or both)."
> 0 votes

# Answer
You aren't exactly correct in your example because of the redundant negation of the $\leq$ sign. In the most general sense, we always have:

$$\neg (x\_1 \land x\_2\land ...\land x\_n)=(\neg x\_1) \lor...\lor (\neg x\_n)$$

Meaning: NOT (A AND B AND C...) equals (NOT A) OR (NOT B) OR (NOT C)...

In your case, we have two conditions with an AND between them:

1. M is a Non-Deterministic TM
2. M has an accepting run on $w$ of length $\leq |w|$

Finding the complement of the language requires negating these conditions, and therefore getting the language where either:

1. M isn't an NDTM, OR
2. M is an NDTM , BUT, it doesn't have an accepting run on $w$ of length $\leq |w|$

Notice the difference in the negation of the second condition - we changed it from having a run satisfying a certain property to not having a run satisfying the same original property.

From my experience, usually in these kinds of questions you have a language composed of TMs/Automata/etc' fulfiling a certain condition, and in such cases the negation would be everything which isn't a TM/automaton/etc', PLUS everything which is of the correct "type" but doesn't fulfill the original given condition.
> 1 votes

---
Tags: turing-machines, computability, reductions, logic
---


# Question
Title: Karp hardness of a vector system allocation
Given an **undirected** graph $G(V,E)$, a **vector system** is a set $S$ of ordered pair (intuitively called **vector**) $(u,v)$ (we shall call $u$ the **initial point**, and $v$ the **terminal point**) that satisfies the following criteria:

* For each vector $(u,v)\in S$, we have that $uv \in E(G)$. So, each vector must be an orientation of an edge
* No two vectors share the same **initial point**. Formally, for every two vectors $(u,v),(w,x)\in S$, we have that $u\neq w$
* An initial point of a vector cannot be the terminal point of other vector. Formally, for every two vectors $(u,v),(w,x)\in S$, we have that $v\neq w$

Now, our problem is defined as follows:

> **Input**: An undirected graph $G(V, E)$ and a natural number $k$
>
> **Output**: **YES** if it is possible to allocate a vector system of size $k$ in $G$, otherwise **NO**

What is the hardness of this problem?

# Answer
> 1 votes
**Omitting the second requirement (allowing vectors to share initial points)**:

This becomes $\mathrm{NP}$-complete since it is exactly $\mathrm{MAX}$-$\mathrm{CUT}$.

Consider the set of all terminal points of the vector system. Exclude all the edges between any two vertices of this set. All the edges inwards constitute the cut.

**Putting back the second requirement (vectors required not to share inital points)**

This is $\mathrm{NP}$-complete by a reduction from $\mathrm{DOMINATING\ SET}$.

Reverse the direction of the vector system.

We see that now the set of initial points (originally terminal points) are dominating the set of terminal points (originally initial points). **Note that these two sets are disjoint**.

So, given an instance $(G,k)$ of $\mathrm{DOMINATING\ SET}$. Our reduction just produces $(G,n-k)$ where $n=|V(G)|$ as an instance of the vector allocation system.

If there is a dominating set of size $k$, then for each of the dominated $n-k$ vertices, we can assign for it a dominating vertex among $k$ dominating vertices. The direction is from the dominating vertex to the dominated vertex (this is the reversed direction). We have formed a (reversed) vector system of size $n-k$.

Conversely, if there exists a vector system of size $n-k$. The set of terminal points (originally initial points) are of size exactly $n-k$. Take the remaining $k$ vertices as a dominating set. This shows that the original instance of $\mathrm{DOMINATING\ SET}$ is a **YES** instance.

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


# Question
Title: C logical consequence of S iff S union {-C} UNSAT
I'm trying to do the following demonstration:

(C and S are CNF) C is a logical consequence of S iff. S u {-C} UNSAT

And I did the following:

C is a logical consequence of S iff. S u {-C} UNSAT iff.

for all interpretation I that SAT S -\> I SAT C iff.

for all I, eval\_I(S) = 1 -\> eval\_I(C) = 1 iff.

for all I, -eval\_I(S) = 1 or eval\_I(C) = 1 iff.

for all I, eval\_I(S) = 0 or eval\_I(C) = 1 iff...

And I got stuck right there. Any clues? Thaks!

# Answer
> 0 votes
You need to apply De Morgan at some point. Trying to stick with your notation:

```
for all interpretations I, I SAT S -> I SAT C
iff
for all interpretations I, not(not(I SAT S -> I SAT C))
iff
for all interpretations I, not(I SAT S and not I SAT C)
iff
for all interpretations I, not(I SAT S and I SAT -C)
iff
not exists interpretation I, (I SAT S and I SAT -C)
iff
not exists interpretation I, I SAT (S u {-C})
iff
not SAT (S u {-C})
iff
UNSAT (S u {-C})

```

---
Tags: propositional-logic
---


# Question
Title: Steps to create a heuristic for solving a problem
I am completely new to AI and doing self-learning to acquire this knowledge. I went through the different available search algorithm like BFS, DFS and A\* but something that I can't understand is a heuristic function that needs to be embedded in these algorithms. I am fine with algorithms but I don't know how we find a good heuristic function for every problem. Is there any steps that needs to be take to achieve a heuristic?

Any comment would greatly appreciated.

# Answer
> 0 votes
There is no general method. Like all mathematics, algorithm design, programming, etc., coming up with heuristics is a creative act which requires you to use your intelligence and understanding of the problem domain.

---
Tags: algorithms, artificial-intelligence, heuristics, search
---


# Question
Title: Strassen's matrix multiplication algorithm when $n$ is not a power of 2
The above image, describing Strassen's matrix multiplication algorithm, is from the book Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein. The algorithm multiplies two square matrices of order $n$, where $n$ is a power of $2$, i.e., $n=2,4,8,16,32,\dots$ and so on.

> Can this algorithm be modified so that we can multiply two square matrices of order $n$, for all $n$?

# Answer
The solution is to pad the matrices with zeroes, using the block matrix identity $$ \begin{bmatrix} A & 0 \\ 0 & 0 \end{bmatrix} \begin{bmatrix} B & 0 \\ 0 & 0 \end{bmatrix} = \begin{bmatrix} AB & 0 \\ 0 & 0 \end{bmatrix} . $$

Here $A,B$ are $n\times n$ matrices, and the big matrices are $N\times N$ for some $N \> n$. In other words, we add $N-n$ rows and $N-n$ columns of zeroes.

You can do this in two ways:

* Pad the original $n \times n$ matrices to $N \times N$ matrices, where $N$ is the closest power of 2. Note that $N \< 2n$, so this doesn't affect the asymptotic complexity.
* Pad the matrices recursively. Whenever a recursive call gets $m \times m$ matrices with $m \> 1$ odd, we pad them to $(m+1) \times (m+1)$ matrices by adding a single row and a single column of zeroes. This also doesn't affect the asymptotic complexity.

A third option is to make use of, say, a 3x3 matrix multiplication algorithm if the dimension is odd but divisible by 3. Laderman found such an algorithm which uses 23 multiplications (instead of the trivial 27).
> 3 votes

---
Tags: matrix
---


# Question
Title: How to prove this obvious theorem in type theory (LEAN prover)
I have the following code:

```
constant B:Type
constant A:Type
constant P:B → A → Prop
definition F:Type := B → A

axiom a1: ∀b:B, ∃a:A, P b a
theorem thrm1: ∀b:B, ∀a:A, (P b a) → ∃f:F, (f b = a) ∧ ∀bb:B, P bb (f bb) :=
    λ b:B, λ a:A,
    assume h: P b a,

sorry

```

It should be almost trivial to prove this, yet I'm not sure how to do it in type theory. Perhaps my intuition is implicitly based on some axiom from classical logic?

The informal argument is as follows: If for a particular $b$ and $a$ the property $P \\; b\\; a$ holds, then we can consider the equivalence class of functions $f:B \to A$ for which $f \\; b= a$. Moreover, since for any $b\in B$, there is an $a\in A$ such that $P \\; b \\; a$ holds, we can simply pick from this the function $f$ which also assigns for every other $b$ some $a$ such that $P\\; b\\; a$ holds. Such a function must always exist, since we can freely adjust the output for each input independently.

But how do we formalize this argument in type theory?

# Answer
If you used `Type` instead of `Prop` in the definition of `P`, then you could easily extract from axiom `a1` a function `f` such that `∀b:B, P b (f b)`. However, there would be no guarantee that this function would satisfy `f b = a` for any given `a` and `b` that satisfy `P b a`. Given a *decidable equality* on `B`, you could turn the function that `a1` gives you into your desired function via `λ bb:B, if bb == b then a else fst (a1 bb)`. Without decidable equality, it's not clear how you would construct a function that you could prove would give `a` when given `b`.

As far as your informal argument, the problem is "picking" from the equivalence class. Constructive logic/type theory is compatible with everything being computable. (Formally, this is usually expressed via realizability.) To say that you can "pick" from an equivalence class subject to some constraints means you are providing an algorithm that can somehow "search" through (some representation of) the equivalence class and find an element that satisfies your constraints. However, you don't even know these types are computably enumerable. At any rate, "picking" is rarely "simple".

I'd have to look at the rules of LEAN to be sure, but with `P` going to `Prop`, you need the (real) Axiom of Choice to even get the function `f` at all before you ever got around to constraints. In fact, while I haven't thought about it too much, I believe the statement you give is equivalent to the (real) Axiom of Choice.
> 3 votes

# Answer
In a nutshell, you want to go from “forall b, exists a” to a function from that maps a to b. This is called the axiom of choice. The axiom of choice is not a given in type theory. Some theories have it, others don't but usually can use it as an additional axiom. This additional axiom is not always automatic because it's an additional burden on the logic which could add opportunities for contradictions. Also it may make proofs impossible to extract to code.

More precisely, suppose that $P$ is inhabited, i.e. that there exists $a\_0$ and $b\_0$ such that $P b\_0 a\_0$. Then `thrm1 b0 a0 proof_of_B_b0_a0` is `∃f:F, (f b = a) ∧ ∀bb:B, P bb (f bb)`. By basic first-order logic, this implies `∃f:F, ∀bb:B, P bb (f bb)`. Getting this from `∀b:B, ∃a:A, P b a` is the functional axiom of choice.

Lean offers choice as an axiom in the standard library. The introduction of this chapter gives some background as to why you'd need to invoke it and why you may not always want to. The Coq FAQ also has some more theoretical explanations on the topic (Coq, like Lean, is based on the calculus of inductive constructions).
> 2 votes

---
Tags: type-theory, dependent-types, proof-assistants
---


# Question
Title: Can interval partition solve by sort by different approach
> The interval partitioning problem is described as follows: Given a set {1, 2, …, n} of n requests, where ith request starts at time s(i) and finishes at time f(i), find the minimum number of resources needed to schedule all requests so that no two requests are assigned to the same resource at the same time.

I read from many sources, that the solution often is:

```
- sort again by earliest time of requests.
- For each requests in sorted request:
     if can choose one resource that can do this requests:
        assign that request to resource
     else
        create new resource
        count++
        assign that request to new resource

```

The result will be count after finishing algorithm.

However, I approach with different idea. The following is algorithm of my idea:

```
- Break all time range into 2 parts: (time=start_time, type=start) and (time=end_time, type=end)
- Sort all that events. If time equals, prefer type=end.
- Go from that sorted events, if type = start: count++. else count --

```

count will be the total machine we need.

My question is: is there any wrong with my approach.

Thanks

# Answer
Yes, **your approach is correct**.

"The interval partitioning problem" is more commonly known as "the interval-graph coloring problem". It is problem 16.1-4 in the book *Introduction to Algorithm* by CLRS, third edition.

The idea behind the common solution described in the question and your approach is essentially the same. Arguably, your algorithm is simpler than that solution given by many sources. On the other hand, there are many sources that give the roughly the same algorithm as yours such as the article at GeeksForGeeks.

There is one distinction of your algorithm, `If time equals, prefer type=end.` It turns out this specification is unnecessarily restrictive in the sense that you can break any tie that consists of requests of the same starting time arbitrarily. On first look, it might sound surprising that the algorithm still works when ties are breaking arbitrarily. One might take for granted that scheduling the one request that ends early should yield more room for later scheduling. However, it does not matter which one to schedule out of the requests of the same staring time. I will leave this little enigma as an exercise for readers to ponder and prove.

By the way, there are **some sloppiness in the question and the algorithm**. In the problem statement, it does not mention explicitly that each request must use one and only one resource all the way from its start time to its end time. That each request can use any resource. It does not specify whether a request that starts at time $t\_0$ can use the same resource used by another request that ends at $t\_0$, that is, whether those two requests are overlapping at $t\_0$. The "total machine" is used suddenly near the end of the question, which should be, for the sake of consistency, "total number of resources". This short answer is written in the hope that all those ambiguities and sloppiness do not affect the high-level thinking by readers.
> 4 votes

---
Tags: partitions
---


# Question
Title: Any finite Graph G with all V have at least degree of 2, is it true that every vertex is necessarily contained IN a cycle?
As title, (note: this questions is asking weather or not all vertices are contained IN a cycle not asking if the G contains a cycle.

My attempt is that:

So this graph would be an counter example that disprove that every vertex is contained in a cycle. Would like to know if this is a valid counter-example since V1 is not contained in a cycle.

PS: As I was finding examples, also observed that if the all V have exactly degree of 2, then it is necessary that all vertices are contained in a cycle. Please prove if I am missing something.

# Answer
You are asking two questions. The first question is whether your graph is a counterexample to the claim that in a graph with minimum degree 2, every vertex lies in a simple cycle. Unfortunately, your graph is not simple, so if by *graph* you mean *simple undirected graph*, then your graph is not a counterexample. However, if you replace the self-loop by a cycle, you should get a valid counterexample.

The second question is whether the claim is true if the graph is 2-regular (all degrees are 2). Indeed, a 2-regular graph is a disjoint union of cycles. I'll leave you to figure out a proof.
> 1 votes

---
Tags: proof-techniques, correctness-proof, check-my-answer
---


# Question
Title: Algorithm to generate the number of tuples that satisfy the sum equals product problem.
**Problem Statement:** Let $n\geq 2$ be a natural number. We are interested in sequences $(x\_1,x\_2,...,x\_n)$ of natural numbers such that $$x\_1+x\_2+...+x\_n = x\_1x\_2...x\_n\text{ and }x\_1\leq x\_2\leq...\leq x\_n.$$ Let $A(n)$ denote the set of all such sequences. Moreover, we denote by $a(n)$ the cardinality of the set $A(n).$ The goal is to generate $a(n)$ for $n\geq 2.$

**Attempt:** Naive attempt in Python 3.5

```
from itertools import product

def prod(tup):
    """
    Computes the product of all elements in the tuple.
    """
    p = 1
    for i in tup:
        p = p*i
    return p

def a(n):
    """
    Check Sum Equals Product Property.
    """
    list_of_tuples = list(product(range(1,2*n+1), repeat = n))
    count = 0
    for tup in list_of_tuples:
        if sum(tup) == prod(tup):
            count = count + 1
    return count

```

It can be proved that for all $n\geq 3$ that $$x\_1+x\_2+...+x\_n\leq 2n.$$ So I just used the bound $1\leq x\_i\leq 2n$ for all $i=1,2,...,n.$ I know this is really bad because it is $O((2n)^n)$ and I not generating non-decreasing sequences. I guess one would want to reduce the number of tuples to check, but I am not sure how to do this. Perhaps someone has an idea?

# Answer
> 2 votes
One simple optimization you can use is as follows: since $x\_1 + \cdots + x\_n \leq 2n$, it follows that at most $\log\_3 (2n)$ values are at least 3. You can go over all possible values for these $O(\log n)$ elements, and for each of them it should be easy to determine whether they can be completed (by adding only 1s and 2s) to a solution.

Taking this one step further, you can start adding elements to the sequence, from $x\_n$ down, keeping track of the current product. If it exceeds $2n$, you can immediately halt.

You can probably optimize this much further, but this is already a good start.

Alternatively, OEIS has your sequence as A033178, and a table for $n \leq 10000$.

---
Tags: algorithms
---


# Question
Title: Time Complexity of the Kruskal Algorithm after sorting
In case I have sorted edges already, What is the best time complexity of Kruskal Algorithm?

# Answer
**Almost linear in term of the number of edges of the graph.**

More specifically, here is the quote from Wikipedia entry on Kruskal's algorithm.

> Provided that the edges are either already sorted or can be sorted in linear time (for example with counting sort or radix sort), the algorithm can use a more sophisticated disjoint-set data structure to run in $O(E \\,\alpha(V))$ time, where α is the extremely slowly growing inverse of the single-valued Ackermann function.

Here $E$ stands for the number of edges in the graph and $V$ stands for the number of vertices in the graph. In fact, $\alpha(n)$ is less than 5 for any practical input size $n$, since $\alpha$ is the inverse of the growing function $f$ and $f(1)=3$, $f(2)=7$,$f(3)=61$, $f(4)=2^{2^{2^{2^{16}}}}-3$, a number whose number of digits is a number whose number of digits is 19727 (all fractional parts ignored). In other words, even if $n$ has trillions of trillions of digits, $\alpha(n)$ is still 4.

Please note in computer science, this factor $a(V)$, however slowly grows, represents a real barrier to achieve a linear algorithm even after the edges have been sorted by weight.
> 1 votes

---
Tags: graphs, time-complexity, trees, minimum-spanning-tree
---


# Question
Title: In Breadth-first search and depth-first search what is the purpose of visited flag
In Breadth-first search and depth-first search, in this source code https://gist.github.com/gennad/791932

```
public void bfs()
    {
        // BFS uses Queue data structure
        Queue queue = new LinkedList();
        queue.add(this.rootNode);
        printNode(this.rootNode);
        rootNode.visited = true;
        while(!queue.isEmpty()) {
            Node node = (Node)queue.remove();
            Node child=null;
            while((child=getUnvisitedChildNode(node))!=null) {
                child.visited=true;
                printNode(child);
                queue.add(child);
            }
        }
        // Clear visited property of nodes
        clearNodes();
    }

    public void dfs() {
        // DFS uses Stack data structure
        Stack stack = new Stack();
        stack.push(this.rootNode);
        rootNode.visited=true;
        printNode(rootNode);
        while(!stack.isEmpty()) {
            Node node = (Node)s.peek();
            Node child = getUnvisitedChildNode(n);
            if(child != null) {
                child.visited = true;
                printNode(child);
                s.push(child);
            }
            else {
                s.pop();
            }
        }
        // Clear visited property of nodes
        clearNodes();
    }

```

what is the purpose of `visited` flag? as I can see it is not used especially if we will use `Queue` and\or `Stack`

# Answer
> 1 votes
Graph is a structure where the nodes can be connected arbitrarily and unlike a tree, you can have edges between any two nodes in a graph in any manner or you might also have a node which is not connected at all to any of the other node. For eg. let us say we have a graph and its adjacency list representation as follows:

Let us say that we are doing DFS starting with node 1. First neighbor is 3 and in DFS we will visit 3 rightaway we encounter it. Let us suppose we haven't marked 1 as visited. Now we will explore 3. First neighbor is 1 and since it is not marked as visited, the algorithm has no means to know that we have visited this node before. So, we will visit 1 again. From 1, we will visit 3 again and this will be an infinite loop. In order to avoid infinite loops like these we will have to maintain `visited` flags for the node.

Now you can apply this concept to BFS as well and also to your iterative and recursive implementations of graph traversals.

# Answer
> 2 votes
The gist of code in Java you see is NOT complete in the sense that it fails compilation miserably. In that sense, you are looking at an example that is incorrect, not pedagogical and misleading to beginners.

With that having been said, let me explain. The `visited` flag is used to prevent the function to visit the same node again. It is used in the calls to method `getUnvisitedChildNode(Node myNode)`, whose definition is missing from the gist. Supposedly, that method will return a child node of myNode that is not visited whenever there is at least one such node. Otherwise that method will return null.

I recommend you to read ntroduction to Graph with Breadth First Search(BFS) and Depth First Search(DFS) Traversal Implemented in JAVA, where BFS and DFS are explained clearly. It also has the complete code that contains the partial source code in your question.

---
Tags: data-structures, trees
---


# Question
Title: Is it true that NEXP = EXP when the input binary strings have size O(n)?
I have a question about this. Because if the input binary strings have size of O(n), it takes exponential time to list all possibilities of it. If an language is in NEXP, then we can list all input possible input strings and then use exponential time to check each one, which is still in exponential time in total. It seems like NEXP=EXP under this circumstance.

# Answer
> 1 votes
"When the input has size $O(n)$." Unless otherwise stated, $n$ is *defined* to be the length of the input. So, generally speaking, the input length is just $n$, and your question is just

> Is **EXP** equal to **NEXP**?

We don't know, but we suspect not. Nondeterminism seems to add extra power that we don't know how to simulate deterministically without requiring exponential time.

> If an language is in **NEXP**, then we can list all input possible input strings and then use exponential time to check each one

That doesn't make sense. In a computational decision problem, you are *given* an input and you must determine whether the answer is "yes" or "no" for *that specific input*. Enumerating other possible inputs doesn't seem helpful: if you're asked a question, your job is to answer that question, not list off all the other questions you could have been asked instead.

# Answer
> 0 votes
A language $L$ is in NEXP if there is a polynomial $p(n)$ and a Turing machine $T$ running in time $2^{p(n)}$ (where $n$ is the input length, in bits) such that:

* If $x \in L$ then there exists a string $y$, of length at most $2^{p(|x|)}$, such that $T(x,y)$ returns Yes.
* If $x \notin L$ then for all strings $y$ of length at most $2^{p(|x|)}$ it holds that $T(x,y)$ returns No.

The string $y$ can be exponentially longer than $x$, and so brute-forcing $y$ would require *double* exponential time.

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


# Question
Title: Karp hardness of testing for homomorphisms to a fixed non-bipartite graph
**Description**: Suppose that we are given a *fixed* **non-bipartite** graph $H$. A graph $G$ is *loopless surjectively homomorphic* to $H$ if there exists a **loopless surjective homomorphism** $\varphi:V(G)\to V(H)$ such that:

> For every $u,v\in V(G)$, $(\varphi(u)=\varphi(v))\lor(uv\in E(G)\implies\varphi(u)\varphi(v)\in E(H))$.

*Note that we do not allow loops and multiple edges. This is just because $H$ is a fixed simple undirected graph. So, mapping to the same vertices is good but remember to map to every vertex of $H$. This also does not put constraint on those vertices mapped to the same $H$-vertex. By standard definition, without a loop at that $H$-vertex, the set of $G$-vertices mapped to it needs to be an independent set.*

We want to decide whether a given graph $G$ is **loopless surjectively homomorphic** to $H$. Note that for each fixed non-bipartite $H$, we have a decision problem, denoted by $\mathrm{HOMOMORPHIC}\_H$.

Formally, for every fixed (i.e. not part of the input) non-bipartite graph $H$, $\mathrm{HOMOMORPHIC\_H}$ is defined as below:

> **Input**: An undirected graph $G$
>
> **Output**: **YES** if $G$ is loopless surjectively homomorphic to $H$, otherwise **NO**

We want to know the computational complexity of this problem.

# Answer
> 2 votes
Your question is more easily phrased as follows. You have a fixed non-bipartite, reflexive graph $H$ (reflexive = a loop on every vertex) and you want to know the complexity of deciding whether there is a surjective homomorphism (in the usual sense) from an input graph $G$ to $H$.

As far as I can see, this question is open.

* The problem is trivially in **P** when $H$ is a clique, since every $G$ with $|V(G)|\geq|V(H)|$ has a surjective homomorphism.
* Golovach *et al.* \[1\] have shown, for each four-vertex $H$, that the problem is either in **P** or is **NP**-complete (including bipartite cases, and allowing loops on any **strict** subset of the vertices).

I don't know of anything else with loops on all vertices.

---

\[1\] P. A. Golovach, M. Johnson, B. Martin, D. Paulusma, A. Stewart, *Surjective $H$-colouring: new hardness results*. ArXiv, 2017.

# Answer
> 2 votes
As others have pointed out in the comments, your definition of homomorphism is highly unusual. In particular, any function whose image is a single vertex is a homomorphism by your definition, thus trivializing the decision problem. The usual definition is as follows:

A homomorphism from $G$ to $H$ is a function $\varphi:V(G)\to V(H)$ such that for all $uv\in E(G)$ we have $\varphi(u)\varphi(v)\in E(H)$.

For the usual definition, the problem is known to be NP-complete for every non-bipartite $H$. The reference (according to Wikipedia) is Hell, Pavol; Nešetřil, Jaroslav (1990), "On the complexity of H-coloring", Journal of Combinatorial Theory Series B, 48 (1): 92–110. (For bipartite $H$, on the other hand, there is a homomorphism if and only if $G$ is bipartite. Thus the decision problem is just bipartiteness of $G$, which is in PTIME.)

A few other notion are somewhat halfway between your definition and the usual one:

* A strong homomorphism from $G$ to $H$ is a function $\varphi:V(G)\to V(H)$ such that for all $u,v\in V(G)$ we have $uv\in E(G)$ if and only if $\varphi(u)\varphi(v)\in E(H)$.
* An embedding from $G$ in $H$ is an injective homomorphism, that is a homomorphism $\varphi$ such that for all $u,v\in V(G)$ with $u\not=v$ we have $\varphi(u)\not=\varphi(v)$.
* An induced subgraph mapping is an injective strong homomorphism.

\[EDIT\]

For each of these variants, the problem is in PTIME for fixed $H$. When injectivity is required, one can reject an instance if $|V(G)|\>|V(H)|$, so only a finite set of graphs remains. For strong homomorphisms, we can have $\varphi(v)=\varphi(w)$ only if $v$ and $w$ have the same neighbours. Hence after some polynomial time preprocessing, we can again assume injectivity.

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


# Question
Title: Does using micro-operations require a higher clock rate than listed
Say we have a modern (Skylake, say) Intel CPU running at a fixed 5GHz clock rate. Since Intel CPUs run micro-operations internally and reaches \> 1 instructions per cycle, it needs to be able to run more than one micro-operation per cycle. But from how registers work we know that new data can only be stored and computation allowed to proceed at certain points of each clock cycle (e.g. the rising edge). Since the CPU internally does more than 1 micro-operation in sequence within a single clock cycle, doesn't that mean it would also need to have more than one internal clock cycle per "external" clock cycle, and hence an internal clock rate that is higher than the listed 5GHz?

# Answer
That's not necessary, and also not how it is actually done. The way Skylake and most other microarchitectures executes multiple instructions in the same cycle is in parallel, not in sequence within a cycle.

So the registers would not be read at several different moments during a cycle, instead several reads are done simultaneously. That does not present a structural hazard: the read logic can be duplicated, as in multi-ported SRAM. Clearly such duplication is not free, but it can be kept in check by exploiting the fact that most registers being read are "hot" (written to recently) and their value will be supplied by different mechanisms anyway (forwarded just-in-time or captured in the reservation station if applicable). Core2 for example could only read 2+1 different entries from its retirement register file (the +1 is for the special case of a register being used as the index in a SIB-encoded address), but for "hot" registers it had no particular limit (or none that I know of). From SandyBridge onward Intel has been using an alternative organization with more of a tag-indexed physical register file style and there seems to be no particular limit on reading from it (so maybe they just went with plenty of read ports there?). Anyway the TL;DR is that the multiple µops in a cycle and their register reads are not sequential and don't need a faster clock.

NetBurst (Pentium 4) actually *did* have a faster internal clock for its fast ALUs and AGU, but not for *everything* (excluding for example the register file), and the reason was not that register reads needed to be sequential (they weren't), just for raw computation speed with low latencies. There were *two* ALUs, so together they can execute 4 ALU operations per cycle, though the front-end cannot supply them with new operations that quickly so the peak throughput cannot be sustained and is only reached in bursts. It is more complicated than executing two operations per ALU in sequence within a "normal cycle" though. Instructions actually take 3 FLCK cycles, in the first cycle the low 16 bits of the result are computed, in the second cycle the high 16 bits are computed and a dependent instruction can already start (since it would also only compute the low 16 bits of its result in the first cycle, so for now it only needs the low 16 bits of its inputs) and in the third cycle the flags are computed.
> 3 votes

---
Tags: computer-architecture, cpu
---


# Question
Title: How is this the expected number of of probes in open-address hashing?
I am reading the "Introduction to Algorithms" by Thomas Cormen *et al*. Particularly the theorem which says that given an open-address hash table with load factor $\alpha = n/m \< 1$, the expected number of probes in an unsuccessful search is at most $1/(1-\alpha)$, assuming uniform hashing.

In the proof they are assuming $p(i)$ to be the probability of exactly $i$ probes where we are finding all of the slots to be occupied. $i$ is $0,1,2,\dots$ so for $i \> n$ we have $p(i) = 0$ since we can find $n$ slots already occupied. I have understood upto this point.

Then it says that expected number of probes in an unsuccessful search is $$1 + \sum\_{i=0}^\infty i\\,p(i)\\,.$$ How is it so?

If there is any confusion to the question please comment. I hope I have explained the question properly. Any help would be appreciated. Thanks in advance.

# Answer
It is the definition of expectation. When the probability of success in exactly $i$ probes is $p(i)$, it means you've been unsuccessful $i-1$ times before! Hence, the expected of unsuccessful steps is $$\sum\_{i = 1}^{\infty}(i-1)\times p(i) = \sum\_{i = 1}^{\infty}i\times p(i) + \sum\_{i = 1}^{\infty}p(i) = 1 +\sum\_{i = 1}^{\infty}i\times p(i)\\,.$$
> 1 votes

---
Tags: hash, hashing
---


# Question
Title: Do not understand a concept in analysis of open-address hashing
I am reading the "Introduction to Algorithms" by Thomas Cormen et al. Particularly the theorem which says that given an open-address hash table with load factor α=n/m\<1, the expected number of probes in an unsuccessful search is at most 1/(1−α), assuming uniform hashing.

In the proof they are saying -

$p\_i$ = It is the probability of *exactly* i probes where we are finding all of the slots to be occupied. i is 0,1,2,…

$q\_i$ = It is the probability of *at least* i probes where we are finding all of the slots to be occupied. i is 0,1,2,…

Then it says -

$$\sum\_{i=0}^\infty i\\,p\_i\\, = \sum\_{i=1}^\infty q\_i$$

How it is so?

# Answer
> 2 votes
For any $i$, $q\_i = p\_i + p\_{i+1} + p\_{i+2} + \dots$. Now look at $\sum\_{i\geq 1}q\_i$ and how many times each $p\_i$ occurs. $p\_1$ occurs only in $q\_1$; $p\_2$ occurs in $q\_1$ and $q\_2$; and, in general, $p\_i$ occurs only in $q\_1,\dots, q\_i$. In other words, each $p\_i$ occurs $i$ times in the sum of the $q\_i$s.

---
Tags: hash, hashing
---


title: Loop Invariant summation

text:
# Question
Title: Loop Invariant summation
So I am stuck:

I have this algorithm from which I need to find a loop invariant but I just can't get my head around it :

```
main_f = x
follow_up = x
while (follow_up < y):
   follow_up = follow_up + 1
   main_f = main_f + follow_up

return main_f

```

So basically I have a list of values of this function(main\_f):

Initialisation : i = 0 , main\_f = x

Iteration 1: i = 1 , main\_f = 2x+1

Iteration 2: i = 2 , main\_f = 3x+3

Iteration 3: i = 3 , main\_f = 4x+6

Iteration 4: i = 4 , main\_f = 5x+10

Iteration 5: i = 5 , main\_f = 6x+15

And basically it goes on and on like this in a while (main\_f \< y) loop;

The loop invariant is certainly a sigma from **i=x** to **y** with the "x" part: (i+1)x but i can't find the formula that fits the integer part I got after the iterations.

Thanks in advance for your help

# Answer
> 2 votes
From your table, the following is apparent: at iteration $i$, $$ \text{main\_f} = (i+1)x + \binom{i+1}{2}. $$ You should be able to prove this formula by induction.

---
Tags: algorithms, loop-invariants
---


# Question
Title: Existence of polynomial time reduction from P to R?
Why the next idea doesn't work:

```
If L_2 in R and L_1 in P and the languages are not trivial,
then there is a polynomial-time reduction from L_1 to L_2

```

I know that if such reduction exists, than L\_1 is also in R --\> But L\_1 is in P and P is in R, so everything looks OK :)

Will be glad for your help here.

# Answer
> 0 votes
The claim is correct, therefore, you need to give a proof that such a reduction exists. I see that you're trying to prove it by contradiction, so your question is a bit unclear. If you did not get to a contradiction by assuming the correctness of the claim, that does not mean that the claim is correct. Instead, you're assuming that it is correct.

By a similar reasoning to yours: as far as i see, if $P\neq NP$ then everything is ok :) Or if $P=NP$ then everything is okay. So maybe the claim is not correct but we don't have the tools to show that yet. Or maybe you can assume both!

Regarding the specific claim you mentioned, consider the following more general claim.

Claim: every non-trivial language $L\_2 \notin \\{\emptyset, \Sigma^\*\\}$ is $P$-hard. That is, if $L\_2$ is non-trivial language and $L\_1\in P$, then $L\_1 \leq\_p L\_2$.

To begin with, note that the claim you wrote is a special case to the above claim. Indeed, we just drop down the assumptions that $L\_2$ is in $R$ and $L\_1$ is non-trivial.

Solution: let $L\_2$ be a non-trivial language and let $L\_1\in P$. We describe a reduction from $L\_1$ to $L\_2$. To begin with, since $L\_2$ is non-trivial, we have that there is a word $x\_{in}\in L\_2$ and a word $x\_{out} \notin L\_2$.

* Defining the reduction: the reduction, denoted $f$, operates as follows. For the input word $w$, check whether $w$ is in $L\_1$. If $w\in L\_1$, the reduction outputs $x\_{in}$. Otherwise, the reduction outputs $x\_{out}$.
* Correctness: follows immediately from the fact that $w\in L\_1$ iff $f(w) = x\_{in} \in L\_2$.
* Runtime: note that the reduction runs in polynomial time in $|w|$ (the input's length). Indeed, since $L\_1\in P$, we have that there is a deterministic TM that decides $L\_1$ in polynomial time and thus one can decide whether $w\in L\_1$ in polynomial time in $|w|$. $x\_{in}$ and $x\_{out}$ are constants (they do not depend on the input $w$), hence they do not affect the runtime of the reduction (you can think about them as words hardcoded in the reduction itself).

Note: a machine that decides $L\_1$ in polynomial time exists, $x\_{in}$ and $x\_{out}$ exist and thus the reduction exists.

---
Tags: complexity-theory, computability, time-complexity, reductions, polynomial-time
---


# Question
Title: Ski design usaco problem alternative solution
problem statement for SKICOURSE is this

Farmer John has N hills on his farm (1 \<= N \<= 1,000), each with an integer elevation in the range 0 .. 100. In the winter, since there is abundant snow on these hills, FJ routinely operates a ski training camp.

Unfortunately, FJ has just found out about a new tax that will be assessed next year on farms used as ski training camps. Upon careful reading of the law, however, he discovers that the official definition of a ski camp requires the difference between the highest and lowest hill on his property to be strictly larger than 17. Therefore, if he shortens his tallest hills and adds mass to increase the height of his shorter hills, FJ can avoid paying the tax as long as the new difference between the highest and lowest hill is at most 17.

If it costs x^2 units of money to change the height of a hill by x units, what is the minimum amount of money FJ will need to pay? FJ can change the height of a hill only once, so the total cost for each hill is the square of the difference between its original and final height. FJ is only willing to change the height of each hill by an integer amount.

and **Naive way** of doing this problem is like this

The problem can be solved with different approaches. A simple idea is of course brute-force -- try all possible elevations and find the minimum amount. We can try all possible values as follows: try the modification for elevation interval (0,17) then (1,18), (2,19), ..., (83,100). For each elevation interval (i,i+17), we need to calculate the cost for each hill j:

```
If the elevation of hill j, say hill[j], is in the interval (i,i+17) then there is no cost.
If it is less than i then the cost increases by (i-hill[j])^2
If it is greater than i+17 then the cost increases by (hill[j]-(i+17))^2

```

Is there any **better way** of doing this i mean if limits exceed drastically

# Answer
> 1 votes
I know, this question is really old, but I will answer it anyway. You can just pick wether you higher the lowest distance or lower the highest one. Then greedy pick the cheaper one until you have your maximum height equal or smaller than 13. In this case, you only need O(max-min-13) steps. Hope it helps.

Just keep in mind that you need to track the former changes because of the quadratic equation.

---
Tags: algorithms, search
---


# Question
Title: Probability of randomly designated subsets cover the universe
Let $U=\\{1,2,\ldots,n\\}$ and $S \subseteq \mathscr{P}(U)$. Let $T$ be a subset of $S$, randomly constructed selecting independently each element of $S$ with probability $p$.

Is there a polynomial time algorithm that computes:

$$\mathbb{Pr}\left\[ U =\bigcup\_{X \in T} X \right\]$$

Or is there any equivalent famous problem?

# Answer
> 3 votes
There is no polynomial-time algorithm that computes an exact solution (i.e. the probability expressed as a ratio of two nonnegative integers $a/b$) to your problem unless $\textbf{P} = \textbf{NP}$. I will show that such an exact solution would provide a polynomial time algorithm for set-cover.

Let $(U, S \subseteq \mathscr{P}(U), k)$ be an instance of set-cover. Let $m = |S|$.

Let $$ \Gamma = \left\\{ K \in \mathscr{P}(S) : U =\bigcup\_{X \in K} X \right\\} $$

For each $h \in \mathbb{N}$ let:

$$ \nu\_h = |\\{K \in \Gamma : |K|=h\\}| $$

Observe that our instance of set-cover is satisfiable if and only if $\nu\_k \neq 0$.

Now, let $T$ be a set, constructed as in the problem statement. $T$ covers $U$ if and only if $T \in \Gamma$. Therefore:

$$ \mathbb{Pr}\left\[ U =\bigcup\_{X \in T} X \right\] = \mathbb{Pr}\[T \in \Gamma\] = \sum\_{X\in\Gamma}p^{|X|}(1-p)^{m-|X|} = \sum\_{h=0}^m \nu\_h p^h(1-p)^{m-h} $$

The rightmost expression is a polynomial over the ring $\mathbb{Q}\[p\]$, which means that its coefficients can be found by computing its value at $m-1$ points and applying an algorithm such as the finite differences method.

---
Tags: algorithms, probability-theory, discrete-mathematics, polynomial-time, set-cover
---


title: Time and space complexity of Radix sort

text:
# Question
Title: Time and space complexity of Radix sort
I had previously asked a question on space complexity of radix sort here. I have also read this question. However, I still get confused about it which means that the concept is not clear. I have the following implementation which is meant only for positive integers:

```
#include <iostream>
#include <vector>
#include <array>
#include <string>
#include <sstream>
#include <algorithm>

void radix_sort(std::vector<int>& arr)
{
    int rad = 1;
    int max_val = *(std::max_element(arr.begin(), arr.end()));
    while(max_val / rad)
    {
        std::array<std::vector<int>, 10> buckets;
        int n = arr.size();
        for(int i = 0; i < n; i++)
        {
            buckets[arr[i] / rad % 10].push_back(arr[i]);
        }

        auto k = arr.begin();
        for(auto b : buckets)
        {
            k = std::copy(b.begin(), b.end(), k);
        }

        rad *= 10;
    }
}

void print_array(std::vector<int>& arr)
{
    for(auto num : arr)
    {
        std::cout << num << "\t";
    }
    std::cout << "\n";
}

int main()
{
    int val;
    std::vector<int> arr;
    std::string s;
    std::cout << "Enter the numbers in the array: \n";
    std::getline(std::cin, s);
    std::istringstream ss{s};
    while(ss >> val)
    {
        if(val != ' ')
        {
            arr.push_back(val);
        }

    }
    std::cout << "Before sorting: \n";
    print_array(arr);
    radix_sort(arr);
    std::cout << "After sorting: \n";
    print_array(arr);
    return 0;
}

```

The time complexity is `O(kn)` and space complexity is `O(k + n)`. Here `n` is the number of elements and `k` is the number of bits required to represent largest element in the array. My problem is with `k` and I am not able to understand how that effects the complexity. In the above code the number of times the outermost `while` loop runs depends on the number of digits of maximum value. Until recently I assumed that `k` represented this number of digits of maximum value. However, that is not the case. Can anyone please explain in simpler terms?

**Edit: Pseudocode**

```
1) Take the array as input

2) Initialize a variable `rad` as 1

3) Find maximum value element in the array

4) Until all the digits in maximum value element are visited:

          i) Create buckets for digits from 0 to 9.

          ii) Based on `rad`, calculate digits in a particular place of number (eg: unit's, ten's, hundred's etc.).

          iii) Fill the buckets with elements, based on the digit they have in the place under consideration in the loop.

          iv) Take out the numbers from buckets in the order bucket0 to bucket9 and use it to populate the original array.

          v) Update `rad` to change the place under consideration for the next loop.

```

# Answer
> 2 votes
A

> $k$ represented this number of digits of maximum value.

B

> k is the number of bits required to represent largest element in the array

This translates to number of digits required to represent the max value in binary.

A is equivalent to B.

Here is how:

Say largest element in the array is 1233.

According to B, $k = log\_2(1233) \approx 11$

According to A, $k = 4$, which is just $log\_{10}(1233)$.

There is formula for converting between the $$log\_a(n) = \frac{log\_b(n)}{log\_b(a)}.$$

The denominator here $log\_a(b)$ is a constant.

So $log\_2(n) = O(log\_{10}(n))$. So it doesn't really matter to radix sort what base you are using.

# Answer
> 1 votes
Another way to think about $k$ is to express the range of numbers in terms of $n$.

If you think this way, the usual radix sort algorithm sorts $n$ integers in the range $\[1,n^c\]$ in $O(cn)$ time using $O(n)$ words of extra space. The parameter $c$ doesn't enter into the space complexity analysis because it measures the number of radix passes.

---
Tags: algorithms, time-complexity, space-complexity, radix-sort
---


# Question
Title: Prove that every CFL has at least one infinite equivalence class
If we define the Myhill-Nerode relation on a CFL how can i prove that there is at least one infinite equivalence class?

# Answer
The language of palindromes over $\\{0,1\\}$ is context-free, but every Myhill–Nerode class is a singleton. So your claim is wrong for context-free languages (unless the alphabet is unary). In contrast, regular languages have a finite number of Myhill–Nerode classes, so at least one of them has to be infinite. The same is true for context-free languages over a unary alphabet, since all of them are regular.
> 4 votes

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


# Question
Title: What is the correct time complexity of the following code
I was wondering what is the correct time complexity expressed in terms of big O on this type of loop:

```
for(i=1;i<=n;i++)
    for(int j=1;j*i<=n;j++)
        // O(1) code here

```

The inner loops will make $n + \frac{n}{2} + \frac{n}{3} + \dots + \frac{n}{n}$. I know that this type of formula is $O(n \log n)$, so is this the correct time complexity on this piece of code?

# Answer
$$n+\frac{n}{2}+\cdots +\frac{n}{n}$$

$$= n(1+\frac{1}{2}+\cdots +\frac{1}{n})$$

Now it is a well-known fact that $1+\frac{1}{2}+\cdots +\frac{1}{n} \le c \log n$, where $c$ is some constant.

$$\le cn(\log n)$$

So the overall Runtime is $\mathcal{O}{(n \log n)}$.
> 5 votes

# Answer
The number of times that the body of the inner loop runs is exactly $$ T(n) = \sum\_{i=1}^n \left\lfloor \frac{n}{i} \right\rfloor. $$ This is sequence A006218 in OEIS, where it is stated that $$ T(n) = n(\log n + 2\gamma - 1) + \tilde O(n^{131/416}). $$ The exact magnitude of the error term isn't known, but it cannot be reduced below $\tilde O(n^{1/4})$.

For more references, see the Wikipedia article on Dirichlet's divisor problem.
> 4 votes

---
Tags: time-complexity
---


# Question
Title: Measuring the information of a document?
I'd like to measure how much information a document $D$ contains.

Clearly, the New York Times published yesterday contains more information than my diary wrote on the same day. But, I do not know how to quantify those differences.

I think there are at least two alternatives. Those are the **information entropy**, and **tf-idf**.

In general, the information entropy $H$ is employed to measure the information. Basically the information entropy seems OK to measure document information.

For instance, let's compare two documents: $D\_1 = \text{"Tom loves Mary. Tom loves Mary"}$; $D\_2 = \text{"Tom loves Mary. Jack loves Jane."}$. In this case, clearly the information of $D\_1$ is less than $D\_2$ and $H(D\_1) \< H(D\_2)$ holds.

The tf-idf is the second option. With tf-idf, more rare words are regarded as more informative words. This also sounds valid. In fact, tf-idf is used to measure the importance of documents in automatic document summarization.

Then, **my questions** are

* Are there standard way to measure the information of a document?
* Are The information entropy and tf-idf used for this purpose? Why or why not?

### Update on Aug 17

Thanks to several kind comments, I came to clarify what my question really was. I'd like to know formal (mathematical) definition of what is *information* or *informative* in the "NYT-and-diary comparison".

*Intuitively*, the New York Times is more helpful than my diary in order to get valuable *information*. In fact, many people pay $3 for NYT, and most people do not for my diary.

However, *formally (mathematically)*, I can not explain why NYT is more *informative*.

Hence, my question is equivalent to **how to formally define information or informative in the NYT-diary case**. Then, the questions in the comments like "what do you mean by *information*" is totally what I'd like to know :)

# Answer
> 4 votes
Assuming that your data comes from a Markovian source, you can estimate the entropy of the source using an optimal compression algorithm such as Lempel–Ziv, whose theoretical version (without limiting the table size) is known to asymptotically converge to the entropy. That is, if the entropy of the source (suitable defined) is $H$, then the expected compressed size of $n$ samples is roughly $nH$. Definitions and proofs appear in Cover and Thomas' Elements of Information Theory, Chapter 13 of the 2nd edition.

The entropy of the source differs from your example. It doesn't make sense to calculate the entropy of a single output – entropy is a function of a random variable (or a distribution), and the entropy of a constant random variable is zero. Instead, we consider your source text as a random variable, and our goal is to estimate the entropy of that random variable from a single sample.

If the source has no memory – that is, the individual symbols of the text are independent – then a good estimate of the entropy of the source is the empirical single-character entropy, which is the function that appears in your question. But general sources – such as a random text – do have memory: if you just sample a random list of characters according to their distribution in the English language, you will get gibberish (a nice example of this appears in Shannon's 1948 paper, p. 7). This is why we need to use a more sophisticated estimator, such as the Lempel–Ziv algorithm.

In practice, you can approximate the information content by just compressing the text using an off-the-shelf program.

---
Tags: information-theory, natural-language-processing, data-mining, entropy, information-retrieval
---


# Question
Title: How to represent symbolic knowledge using real numbers - theory about neural networks and natural/analog computing?
One can define the semantics of one definite word using the references to real world entities, relationships with the other words and other concepts and represent all this knowledge about this one word using logical symbolic expressions. And then one can encode all this set of symbolic expressions into vector of real numbers. This is word embedding that is used in natural language processing, distributional semantics of the word in opposite of the formal semantics of the word.

One can consider function of software program (e.g. functional program or any other program). One can encode this program in the multiple vectors and matrices of real numbers that are used for the definition of neural network.

One can consider symbolic meta-knowledge and encode them into vectors or neural networks as well.

The decoding process can be more tricky. There is more or less elaborate decoding of neural network - e.g. see Google queries "logical program extraction from neural networks" or "symbolic rule extraction from neural networks". But I have not seen the work about extraction of more or less static knowledge base from the word-embedding-vector.

So - I have two questions regarding this matter:

* Is there symbolic knowledge extraction from the word-embedding vectors - some kind of decoding algorithm from vector of real numbers to the set of logical formulas?
* Is there general theory of mentioned encoding algorithms? The usual approach is to train neural networks and to arrive at the encoded form using non-symbolic methods, non-algorithmic methods, implicit way. I have heard about embedding of symbolic knowledge in neural networks to speed-up training, but such kind of work is scarce. But what about general encoding algorithms?

There are discrete, natural Goedel numbers (encoding algorithms) that can be assigned to any theorem of first order logic. But what about such Goedel numbers for the sets of formulas or for some computational program (as a set of commands)? Can we enumerate all such sets using natural numbers only or maybe the real numbers are needed instead naturally. Or maybe even set of real numbers are required for encoding the set of symbolic formulas or program statements? **Is there such research work which I can develop further? If no, then what ideas can be mentioned for such encoding/decoding schemes?**

Such encoding-decoding algorithms can be related to biological computing and ultimately they can lead to the explanation of brain activity.

# Answer
No, probably not. I think you're expecting too much from the current state of the art in word embeddings. Word embeddings don't magically capture all semantic knowledge. They don't reflect perfect understanding of the language. Instead, they're just useful mappings where similar words often have similar embeddings. Moreover, the way word embeddings are constructed has nothing to do with logical formulas.

I don't think you're going to find that word embeddings solve the problem of converting from natural language to formulas.

I don't know what would count as a general theory of encoding algorithms for you. There are certainly multiple papers that propose different methods of constructing different word embeddings; you could read those to understand the state of the art.
> 2 votes

---
Tags: logic, neural-networks, natural-language-processing, knowledge-representation, real-numbers
---


# Question
Title: Turing machine that converts decimal to binary
I'm a beginner in Turing machine computation and want to design two TMs; one that converts decimal number to binary, and other one that converts binary to decimal.

Could anyone help me design these Turing machines? How can I start?

Thanks.

# Answer
> 2 votes
You can play around and try your ideas with this simulator.

Under examples, you can find decimal to binary converter. Furthermore, you can learn about TMs in tutorial section.

---
Tags: turing-machines
---


# Question
Title: What is the procedure to find the time complexity of python program?
Is there any kind of function which is used in python to calculate the time complexity of another function?

# Answer
> 1 votes
Time complexity, like any other nontrivial property of programs, is undecidable: there can be no algorithm to compute it, in Python or anything else.

---
Tags: loops, python
---


# Question
Title: Aren’t most constraining variable and least constraining value the exact opposite?
So aren’t MCV and LCV the exact opposite?MCV tries to choose the variable with the most constraints on remaining variables but LCV is opposite: it tries to rule out as least values for other variables as possible

# Answer
Yes, **these two heuristics sound like inconsistent**. Most Constrained Variable (MCV) (also called MRV for Minimum Remaining Values) tries to reduce the size of the next branch to search while Least Constraining Values tries to enlarge the size of the next branch to search.

However, if you take a close look, they both serve the same goal, which is, given a Constraint Satisfaction Problem (CSP), to find a solution as fast as possible and, if there is no solution, declare that fact as fast as possible, too.

These two heuristics are **applied in different stages of the search**. MCV is about choosing which variable to assign value to and then, given a variable, LCV is about choosing which value to assign.

Here is a quote from a lecture note on Constraint Satisfaction Problems by Max Welling, slighted edited.

> In all stages of the searching for one solution, we want to **enter the most promising branch, but we also want to detect inevitable failure sooner**.
>
> **MCV: the variable that is most likely to cause failure in a branch** is assigned first. The variable must be assigned at some point, so if it is doomed to fail, we’d better found out soon.
> **LCV: tries to avoid failure by assigning values that leave maximal flexibility for the remaining variables**. We want our search to succeed as soon as possible, so given some ordering, we want to find the branch that is more likely to succeed.

In term of the search tree, MCV help pruning bigger branches more often and earlier, thus makes the searching end faster, whether it ends with a solution or no solution possible. LCV help make backtracking less often in case there is a solution, but it does not help when there is no solution since every value has to be searched. In other words, **if the goal is to find all solutions instead of one solution, then MCV still help effectively while LCV does not help at all.**

I would like to use **planning a party as an example**. The variables are who should attend, when to hold it, where to hold it and how much to spend (why and what is another question). The object is to determine if you can set up a party plan that is inviting enough.

Suppose you are almost running out of money. Then the first thing to check is to set a tight limit on spending. You do not want to plan all the other parts in great beautiful detail only to find there is not enough money to support them later. Then within the limit you want to adopt a budget as high as possible so that there is more room to make the party attractive enough to people. Note that you are applying the principle of MCV and then LCV.

Consider another situation. You are planning a birthday party for one of your friends and you are not constrained much by the money. Then you probably do not want to consider your budget first. The first thing you want to decide is probably when to hold the party since there are usually not many choices. It is expected usually on that birthday. Then in order to have most of remaining choices you want to pick a time such as the night on the birthday instead of the afternoon when many people are still working or attending classes. Only in case the night on the birthday does not work, for example because some people cannot attend, will you backtrack to the less likely choice of the afternoon on the birthday. Note again that you are using the approach of MCV and LCV.

We can see that MCV and LCV are working together to enable you to find a viable party plan faster. You can imagine what might happen if you use the opposite approaches, the approach of least constrained variable first and maximum constraining values first

Although far from rigorous, this example of party planning might aid your conceptual understanding of MCV and LCV working together. (You can also view the example as an application of principles of artificial intelligence to guide our decision making process in real life.)

For more related material, you can check chapter 6, "Constraint Satisfaction Problems" in the leading AI book *Artificial Intelligence: A Modern Approach (3rd Edition)* by by Stuart Russell and Peter Norvig.
> 9 votes

---
Tags: heuristics, constraint-satisfaction, backtracking
---


# Question
Title: Minimum spanning subgraph of even degree
I have an unusual problem that I am struggling to solve. I have a set of nodes (with positive distances between them) that I want to connect into a single component. In particular, I want to form a minimum-distance spanning subgraph such that all its nodes have an even degree. Note that the subgraph can have multiple edges between a pair of nodes (multigraph). Below are some examples:

A) We have 8 nodes arranged in a circle, where adjacent nodes are separated by distance 1. We connect them into a single cycle of length 8.

B) The top figure shows all the possible distances. If we use the three single edges then we will have a subgraph of weight 1+1+3=5. But we can do better if we use double edges, giving us a total weight of 1+1+1+1=4 (bottom figure). Note that the center node has degree 4, but this is ok since it is still even.

C) Here all adjacent nodes are separated by distance 1. If we use double edges in the shape of the Sum sign (Sigma) then we will get a subgraph of weight 8. But we can do better by using single edges, giving us a total weight of 6.

D) Here the best way to include the top-right node is to use double edges.

I have come up with an outline for an algorithm for solving this problem, but it is not quite complete. First we compute the minimum spanning tree. This will give us some of the edges of the subgraph. It will also give us some nodes (leaves of the tree) with degree 1. We now greedily connect these nodes to their closest neighbours. This is the bit that I haven't quite worked out. Because if we always pick the closest neighbour then we will get the same edges as the MST. Clearly this will fail in A. So perhaps we want to prioritise connections to other degree-1 nodes. Also at the end of this step, we may still have some nodes with an odd-degree remaining which also need to be connected.

Any help would be greatly appreciated!

# Answer
> 1 votes
I just realised that example A is an instance of the Travelling Salesman Problem, which is NP-hard. So the best we can hope for is an approximation algorithm.

I also realised that this is problem is an instance of b-matching, where you want to select up to b edges incident on each node of minimal total weight. Here we have the additional constraint that b is even. I found a couple of papers that solve b-matching:

http://www.aporc.org/LNOR/10/ISORA2009F12.pdf http://proceedings.mlr.press/v15/huang11a/huang11a.pdf

---
Tags: minimum-spanning-tree
---


# Question
Title: Calculating a polynomial's coefficients from its roots
Let $P$ be a monic polynomial polynomial given by its roots: $$P(X) = (X-x\_1)\times...\times(X-x\_n)$$

What is the minimum asymptotic complexity to compute its expansion of the form: $$a\_nX^n+...+a\_0$$

---

What I have found so far are Vieta's formulas which give an expression of each $a\_k$ as a sum over $1\leq i\_1 \< ... \< i\_{n-k} \leq n$. This would suggest the complexity of computing the $k$th coefficient is something like ${n-1 \choose n-k-1}={n-1 \choose k}=O(n^k)$, thus making the total complexity bonkers (I guess something like $O(n^n)$).

Yet my teacher's presentation suggests it is a $O(n^2)$, which doesn't match my calculation at all.

# Answer
For every integer $i$, $0\le i\le n$, let $$P\_i(X) = (X-x\_1)(X-x\_2)\cdots(X-x\_i)=a\_{i,i}X^i+a\_{i,i-1}X^{i-1}+\cdots+...+a\_{i,0}$$ for some $a\_{i,k}$, $0\le k\le i$. In particular, $a\_{i,i}=1$. Expanding $P$ on both sides of the following equation and comparing the coefficients, $$P\_{i+1}(X) = P\_i(X)(X-x\_{i+1})$$ we see that for $1\le k\le i\lt n$, $$a\_{i+1,k}=-a\_{i,k}x\_{i+1}+a\_{i,k-1}$$ and $$a\_{i+1,0} = -a\_{i,0}x\_{i+1}$$ So for fixed $i$, we can compute all coefficients of $P\_{i+1}(X)$ from the coefficients of $P\_i(X)$ with $O(i)$ steps. Now you should be able to see that your professor's suggestion on the minimum asymptotic complexity makes a lot of sense.
> 3 votes

---
Tags: algorithms, complexity-theory, polynomials
---


# Question
Title: Represent polynomial time complexity as linearythmic
To determine the experimental time complexity of radix sort, I wrote a program that counted the number of steps the algorithm took to sort N points. I ran that program for multiple N length arrays, and I plotted the steps taken in Excel. Then, using the trend line tool, I calculated the polynomial that best fit the function.

It gave me something along the line : $$Steps = 16n^{1.0932}$$

This seems to be $O(n)$, but my prof is telling us to represent this as $O(n \log n)$ . How would I go about to demonstrate this.

Thanks.

PS: If anyone is interested, here are my results.

# Answer
> 1 votes
You cannot "demonstrate" that a running time is $\Theta(n\log n)$ experimentally. All you can do is give evidence. Such evidence would be a constant $C$ such that for large $n$, $Cn\log n$ is a good approximation to the empirical running time.

You found the best polynomial approximation to your input. Since $Cn\log n$ is not a polynomial, this kind of approach cannot possibly give you the answer $Cn\log n$. If you want $Cn\log n$ to be a possible answer, you need to include such functions in the family of functions you are optimizing over.

Finally, to demonstrate that $Cn\log n$ is a better approximation that your polynomial approximation or a linear approximation, all you have to do is to compare the error in the approximation $Cn\log n$ to the errors in the other two options. Smallest error wins.

---
Tags: time-complexity, asymptotics
---


# Question
Title: If $A,B$ are r.e. and $A\cup B,A \cap B$ are recursive, then so are $A,B$
Let be $A, B \subset \mathbb{N}$ are recursively enumerable, $A\cup B$ and $A \cap B$ recursive. I want to show that $A$ and $B$ are recursive.

By negation theorem $X \subset \mathbb{N}$ is recursive iff $X$ and $X^c$ are recursively enumerable.

How do I complete the proof using that?

# Answer
The basic observation is $$ \begin{align\*} A^c &= (A^c \cap B^c) \cup (A^c \cap B) \\ &= (A \cup B)^c \cup (B \cap (A^c \cup B^c)) \\ &= (A \cup B)^c \cup (B \cap (A \cap B)^c). \end{align\*} $$ Using this you can recursively enumerate $A^c$. I'll let you figure out how.
> 3 votes

---
Tags: computability
---


# Question
Title: Non-regular language whose prefix language is regular
I understand that prefix of a regular language is regular, but I am unable to get my head around this:

> Give an example of a non-regular language $A ⊆ \\{0, 1\\}^\*$ for which $\operatorname{Prefix}(A)$ is regular.

# Answer
> 7 votes
One approach to think of examples or counterexamples is to looking for the simplest examples or starting from some known situations.

What are some typical examples of non-regular languages? A typical example is the language of palindromes. Its prefix language contains every word $w$, since $ww^R$ is a palindrome. That is, its prefix language is a regular language.

The question has been answered.

---

However, as pointed out by Bader Abu Radi, the above example breaks down with unary alphabet, when the language of palindromes is the set of all words.

What are some typical examples of non-regular languages over unary alphabet, say $\\{a\\}$?

Let us try $\\{a^{n^2}\mid n\ge0\\}$ or $\\{a^{2^n}\mid n\ge0\\}$ or just any non-regular language you can think of. Since it is non-regular, its words can be arbitrarily long. That means its prefix language contains all words, $\epsilon, a, a^2, \cdots$. That is, its prefix language is regular.

---

Readers may enjoy the following two exercises.

**Exercise 1** (easy). Show that an example over unary alphabet can be considered as an example over any larger alphabet.

**Exercise 2**. A language is prefix-closed if it is own prefix language. Give an example of non-regular prefix-closed language that does not contain a regular infinite language.

# Answer
> 4 votes
The other answer gives a particular example of a language fitting your bill. You can also show that *almost all* languages satisfy your condition.

Fix an alphabet $\Sigma$, and let $L$ be a random language over $\Sigma$ sampled by putting in each $w \in \Sigma^\*$ with probability 1/2. Since there are only countably many regular languages, almost surely $L$ is not regular. Conversely, for every fixed $x \in \Sigma^\*$, almost surely one of the infinitely many words $y \in \Sigma^\*$ is such that $xy \in L$. Since there are only countably many words in $\Sigma^\*$, it follows that almost surely the prefix language of $L$ is $\Sigma^\*$, which is regular.

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


# Question
Title: Can both $f(n) \neq O(g(n))$ and $g(n) \neq O(f(n))$ happen at once?
For which case are both $f(n) \ne O(g(n))$ and $g(n) \ne O(f(n))$ true?

I have following answer to this which I could not understand:

> Sometimes true: For $f(n) = 1$ and $g(n) = |n \sin n|$ it is true, while for any $f(n) = O(g(n))$, e.g. $f(n) = g(n) = 1$, it is not true.

Please someone help in understanding:

* For which case is it sometimes true? An explanation with example will be much appreciated.
* What is meaning of "||" in this?

# Answer
> 1 votes
Consider the following statement about two functions $f,g$:

> $f(n) \neq O(g(n))$ and $g(n) \neq O(f(n))$.

The question wants you to choose which of the following holds:

* The statement holds for every $f,g$.
* The statement holds for no $f,g$.
* The statement holds for some $f,g$, and doesn't hold for other $f,g$.

The third option is correct in your case, and this is the meaning of "sometimes true".

Indeed, if $f(n) = g(n) = 1$ then the statement doesn't hold. Conversely, if $f(n) = 1$ and $g(n) = |n\sin n|$ (where $\left|\cdot\right|$ denotes absolute value) then the statement does hold.

---
Tags: algorithms, algorithm-analysis
---


# Question
Title: Are there problems that are DSPACE(O(1)) complete?
I know there are problems that are NL-complete, NP-Complete, PSPACE-complete, etc. Are there problems that are DSPACE(O(1))-complete I.e. NSPACE(O(1))-Complete I.e. Reg-Complete?

Thanks!

# Answer
> 1 votes
**YES**, there are.

At the beginning of "Andreas Krebs, Klaus-Jörn Lange: Dense Completeness. Developments in Language Theory 2012: 178-189"\[Section 6\], it is stated that some REG languages with a non-solvable monoid are complete for $\mathrm{NC}^1$ under $\mathrm{DLOGTIME}$-uniform $\mathrm{AC}^0$ reductions. The section goes on to state that a REG language is either in $\mathrm{AC}^0$ or its syntactic monoids are non-aperiodic.

Complexity Zoo states that REG is contained in $\mathrm{NC}^1$.

So, some REG language is complete for the class itself. This is **non-trivial**.

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


# Question
Title: Optimization Problem when calculating fitness is expensive
I need to solve an optimization problem, maximizing fitness in a set of around 1 million solutions. Calculating the fitness of any solution is very time consuming, taking around 5 minutes. Therefore, I am only able to calculate the fitness of 100 solutions per run. Each solution is represented by vector in ten dimensions with real values \[0..1\], such that two similar vectors represent similar solutions and should have similar fitness.

Obviously I have no expectation of finding a solution that is anywhere near optimal, but is there a preferred method for AI search when you're only able to test the fitness of very few solutions? I get the feeling that I'm missing one or two keywords that would point my search in the right direction.

I'm considering calculus-based search as one option, as it's better to find a local maxima than just randomly search the space and not find any good solutions whatsoever.

# Answer
> 2 votes
For starters I assume that you can't guess the impact the values of a solution have on its fitness, otherwise you could relax the fitness function to roughly estimate which solutions are promising, and try to find a good solution from there.

However you do know that similar solutions have a similar fitness, so let's work with that. I would suggest something along these lines:

1. Construct a function to measure the similarity of two solutions.
2. Using this function, heuristically group your solutions into 100 clusters.
3. For each cluster, calculate the fitness of the solution closest to its mean.

This will give you the fitness of the 100 most dissimilar solutions, which is a good sample of your search space (it should give you a good idea of the fitness found in most major peaks). As a bonus, you can recursively do this if you want to improve on the best solution found, i.e., divide the best cluster into *k* clusters and proceed in the same way.

# Answer
> 1 votes
One approach: Evaluate the fitness of a variety of configurations. Train a model to predict the fitness given the 10-vector. (For instance, you might use a neural network, or some other form of nonlinear regression.)

Then, apply any standard optimization method (e.g., gradient descent) to find the input to the model that maximizes its output. That is a reasonable guess at a possible solution to the optimization problem.

---

Another approach: use local search methods, such as simulated annealing. Or, you can try particle swarm optimization.

---
Tags: optimization, search-algorithms, heuristics
---