# Question
Title: Reduction from Independent Set with fixed vertex to Independent Set
I was looking to solve this reduction, but I dont see how to construct the new graph. It seems very simple but I'm not capable of do it.

I give you the complete explanation about this reduction.

We consider a variant of the independent set problem which we shall call, Independent Set with a Fixed Node, in which the input contains additionally a vertex $u$ and it is required that the independent set contains $u$.

# Answer
> 2 votes
As I understand, your problem is a decision problem defined as such:

Independant set with fixed vertex (ISFV):

* Input: a graph $G = (V, E)$, a vertex $u \in V$, an integer $k$.
* Question: is there an independent set of size $k$ containing $u$?

Independent set (IS) is defined as:

* Input: a graph $G = (V, E)$, an integer $k$.
* Question: is there an independent set of size $k$?

Suppose you can solve ISFV. Then you can solve IS by running ISFV for each $u\in V$ and checking if the answer is yes for any $u\in V$. Since there are a polynomial number of vertices, the reduction is indeed polynomial.

Another way to do it is to construct the graph $G' = (V\cup\\{u\\}, E)$ (adding a vertex with no other edge), and check ISFV with $G'$, $u$ and $k + 1$, since the vertex $u$ can always be added to an independent set.

# Answer
> 0 votes
Suppose that we are given a graph $G$ and want to know whether it has an independent set of size $k$ containing $u$. Such an independent set cannot contain any neighbor of $u$, and so it is not hard to check that $G$ contains such an independent set iff the graph obtained by removing $u$ and all of its neighbors contains an independent set of size $k-1$.

We can also reduce in the other direction by adding a dummy vertex which is disconnected from the rest of the graph.

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


# Question
Title: Dividing 2 integers with some constraints
This a problem i came across while practicing binary search. Here is the problem:

Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator.

Return the quotient after dividing dividend by divisor. The integer division should truncate toward zero.

Note:

1. Both dividend and divisor will be 32-bit signed integers.
2. The divisor will never be 0.
3. Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: \[−2^31, 2^31 − 1\]. For the purpose of this problem, assume that your function returns 2^31 − 1 when the division result overflows.

**A Brute force Solution** is that subtract the dividend with the divisor till it is greater and the number of subtractions is the result. But it is giving Time Limit Exceeding error.

How to solve the problem efficiently or using Binary Search ??

Also provide the time complexity as well.

# Answer
> 2 votes
Here is a strategy (I will only consider positive numbers): Let $d$ be the dividend and $x$ be the divisor. Generate all values $x\_i = 2^i x$, up to some some $x\_k$ such that $x\_{k+1}$ exceeds the dividend. This can be done with only one addition per value since $x\_{0} = x$ and, for $i \ge 1$, $x\_i = x\_{i-1} + x\_{i-1}$. Similarly, generate all values $b\_i = 2^i$ for $i=0, \dots, k$.

Let $r$ be a variable that will hold the result. Initially $r=0$. For $i=k$ down to $0$ do the following:

* Check whether $x\_i$ is bigger than $d$;
* If that is the case, then you know that, by subtracting $x\_i$ from $d$, you are effectively subtracting $x$ from $d$ a total of $b\_i = 2^i$ times. Update $d = d- x\_i$, and $r = r + b\_i$.

Finally, return $r$.

This strategy requires only a logarithmic number of operations w.r.t. $d/x$ (up to multiplicative and additive constants). Since this is at most $2^{31}$, the time needed is always upper bounded by a constant.

---

As an example, let's divide $62$ by $3$. The sequences of values $x\_i$ will be: $x\_0 = 3, x\_1 = 6, x\_2 = 12, x\_3 = 24, x\_4 = x\_k = 48$, since $x\_5 = 96 \> 62$. The corresponding values $b\_i$ are: $b\_0 = 1, b\_1=2, b\_2=4, b\_3=8, b\_4=16$.

* Initially $d=62$, $x=3$, $r=0$.
* In the fist iteration ($i=k=4$) we have $62 = d \ge 48 = x\_4 $, and we update: $d = 62 - x\_4 = 62-48 = 14$, and $r = 0 + b\_4 = 0 + 16 = 16$.
* In the second iteration ($i=3$) we do nothing since $d = 14 \not\ge 24 = x\_3$.
* In the third iteration ($i=2$) we have $d = 14 \ge 12 = x\_2$, and we update $d = 14 - x\_2 = 14 - 12 = 2$, and $r = 16 + b\_2 = 16 + 4 = 20$.
* In the forth iteration ($i=1$) we do nothing since $d = 2 \not\ge 6 = x\_1$.
* In the fifth and final iteration ($i=0$) we do nothing since $d = 2 \not\ge 3 = x\_0$.

In the end we have $r=20$ and $d=2$. Indeed: $62 = 3 \cdot 20 + 2$.

# Answer
> 1 votes
With the help of Steven, i am posting the solution.

```
def divide(dd,dr):
    '''
            let dd and dr be the dividend and divisor
            x be the current macium divisor, less that dividend
            c be the counter
            q is the qutotient
    '''
    x=dr
    c=0
    while (x<<c) <= dd:
            c+=1
    print(c)
    q=0

    #then subtract from dividend and update result as usual manner

    #will run c time i.e lgx time  -----------Loop2
    for j in range(c-1,-1,-1):
            if x<<j <= dd :
                    dd-=(x<<j)
                    q+=1<<j

    print(q,dd)

    '''
    total time complexity will be 2lgx i.e lgx
    '''

```

\** Just Little bit doubt in the time complexity of loop1 and loop2.\**

But this solution works.

# Answer
> 0 votes
The best strategy when given a problem with stupid restrictions is to ignore the restrictions and write z = x / y. As it is, solving this problem doesn't help you understanding anything, and doesn't help you doing anything.

---
Tags: algorithms, time-complexity, mathematical-programming, binary-search, bit-manipulation
---


# Question
Title: Prolog: Deletion of all appearances of an element in a list
I am trying to create a predicate in Prolog which allows me to delete all occurrences of X in a list L. I have the following code:

```
my_delete(X, L, R):- [] = L, [] = R
my_delete(X, L, R):- [Y|K] = L, [Y|M] = R, my_delete(X, K, M), (Y \= X)
my_delete(X, L, R):- [X|K] = L, [Y|M] = R, my_delete(X, K, R), (Y \= X)

```

And now, upon querying this following line, I receive no result, implying that no list R could be constructed so that it followed my requirements.

```
?:- my_delete(baz, [foo, bar, baz], X)

```

The construction works fine when the list I want to delete from didn't contain an occurrence of X in the first place, but not if it did. Why is my set of predicates insufficient? What needs to be changed?

# Answer
> 3 votes
There are some rules of thumb I follow when writing prolog. Two of them are:

* Use `dif` instead of `\=`. From the reference manual: *"To make your programs work correctly also in situations where the arguments are not yet sufficiently instantiated, use dif/2 instead."*
* Avoid unnecessary variables and always get rid of the "Singleton variables: \[X\]" error. It makes the code much more readable.

When I rewrite your code accordingly, your

```
my_delete(X, L, R):- [] = L, [] = R
my_delete(X, L, R):- [Y|K] = L, [Y|M] = R, my_delete(X, K, M), (Y \= X)
my_delete(X, L, R):- [X|K] = L, [Y|M] = R, my_delete(X, K, R), (Y \= X)

```

becomes

```
my_delete(A, [], []).
my_delete(X, [Y|K], [Y|M]):- my_delete(X, K, M), dif(X, Y).
my_delete(X, [X|K], R) :- my_delete(X, K, R).

```

which is not only concise and more readable, but it already seems to work.

As for your particular case, I think it has to do with the quote in the first rule of thumb above. Your X and Y are not sufficiently instantiated, so it is no surprise for me, that your program does not work correctly.

But the "`dif` vs. `\=`" issue is probably not a problem in this case. I replaced `dif(X, Y)` with `X \= Y` in the code I suggested above, and it still works. (It may be causing a problem in your code though. I don't know if this is the case.)

Just using `dif` instead of `\=` is not a solution either. After replacing the `\=`s with `dif` in your code, it still does not work correctly. If the element to be removed is at the last position, it does not work. `my_delete(baz, [baz], X)` fails, for example.

So what is the problem? It seems to me that you've made two mistakes in your last line. You've put an unnecessary `(Y \= X)`. Line 3 was supposed to be the case in which L starts with X. So the inequality check there should probably be an equality check. And secondly, you probably shouldn't have splitted `R` into `[Y|M]`.

You can try the code here: https://swish.swi-prolog.org/p/myClMmML.pl

Swish has a great debugger as well. Check out its help.

---
Tags: prolog, predicate-logic
---


# Question
Title: What is the Number of Possible Nonequivalent Propositions with $P_1, P_2, P_3$ Using $\iff$ Operator?
A multiple choice question asks this:

> Number of nonequivalent propositions that only consist of $P\_1, P\_2, P\_3$ and use the $\iff$ logical operator is?$$A)7\text{ }B)8\text{ }C)1\text{ }D)16$$

I am really uncertain about what the question is asking. Is it asking me to find all the possible propositions using the $P\_1, P\_2, P\_3$ terms and logical operators (e.g. $\land, \lor, \neg$...) and see which ones have the same value?

# Answer
You just need to use $P\_1$, $P\_2$, $P\_3$ and $\Leftrightarrow$ symbols, for example $P\_2$ is a formula, $(P\_1 \Leftrightarrow P\_3) \Leftrightarrow P\_2$ is a formula. As stated in the question, you must not use $\vee$, $\wedge$ or $\neg$.

You need to find the number of non-equivalent formulae. For example, $P\_1 \Leftrightarrow P\_2$ is equivalent to $P\_2\Leftrightarrow P\_1$, but $P\_1\Leftrightarrow P\_2$ is not equivalent to $P\_1 \Leftrightarrow P\_3$.
> 2 votes

---
Tags: logic, propositional-logic
---


# Question
Title: Proving NP-hardness of Hamiltonian Cycle problem variant
I need to prove that determining whether a graph has a relaxed-Hamiltonian cycle (definition given ahead) is NP-hard.

> A relaxed-Hamiltonian cycle in $G$ is a closed walk $C$ that visits every vertex of $G$ exactly once, except for at most one vertex that $C$ visits *more than once* (i.e. that vertex may repeated twice or even more times).
>
> **Note**: In a closed walk we can visit a vertex or edge multiple times, but first and last vertex are same. In the relaxed-Hamiltonian cycle this first and last vertex being the same is not counted as repetition.

I am thinking reducing to relaxed-Hamiltonian cycle from Hamiltonian Cycle.

Claim: Construct graph $G'$ given $G$ such that $G$ has Hamiltonian cycle iff $G'$ had relaxed-Hamiltonian cycle.

My idea is that if a graph $G$ has one or more articulation points then it cannot have a Hamiltonian Cycle so simply give a $G'$ which does not have a relaxed-Hamiltonian cycle.

The problem is when graph $G$ does not have any articulation points. In this case the graph $G$ may or may not have an Hamiltonian Cycle. I cannot think of a construction for this case such that my claim holds.

Is my approach correct? If yes please suggest how I could take care of the mentioned case? Otherwise, please hint me towards the correct direction of thinking to get the right construction.

# Answer
Your definition:

> A relaxed-Hamiltonian cycle in $G$ is a closed walk $C$ that visits every vertex of G exactly once, except for at most one vertex that $C$ visits more than once (i.e. that vertex may repeated 2 or even more times).

I'll call this revisited vertex (for a given $C$) the ***nexus*** of $C$ and look at a case that shows that even if we know which node must be the nexus of any relaxed-Hamiltonian cycle, the problem is still NP-hard.

Consider two graphs $G\_1,G\_2$ for which finding a Hamiltonian cycle is NP-hard (which may be two copies of the same graph). Then we create $G$ by identifying a vertex in $G\_1$ with a vertex in $G\_2$, with the single vertex thus created called $w$. $w$ is an articulation vertex so $G$ cannot have a (standard) Hamiltonian cycle.

If a relaxed Hamiltonian cycle exists in $G$, it must have $w$ as its nexus. To visit all nodes in $G$, we have to visit $w$ and that is the only node which allows us to cross into $G\_2$ and visit all nodes there. So we have the second (minimum) visit and $w$ is the nexus.

The definition of the relaxed Hamiltonian cycle means that we could in principle find disjoint cycles all including $w$ within either $G\_1$ or $G\_2$ and still meet the relaxed-Hamiltonian standard. We can avoid this case by ensuring that nodes in $G\_1$ and $G\_2$ that we pick for identification to create $w$ are maximum degree $3$, so we cannot re-enter a second cycle in the same graph part from $w$.

Then the problem of finding a relaxed Hamiltonian cycle in $G$ is as hard as finding Hamiltonian cycles in both $G\_1$ and $G\_2$ which we know can be NP-hard.

Further to your claim, we therefore know that if we find a relaxed Hamiltonian cycle for $G$ we have found a Hamiltonian cycle for both $G\_1$ and $G\_2$ (and $G\_2$ is allowed to be a copy of $G\_1$).
> 2 votes

# Answer
Here we will refer relaxed- Hamiltonian cycle as Ultra-Hamiltonian cycle. We know Hamiltonian-Path problem is known to be in NP-complete, Now to prove that ultra-Hamiltonian Cycle is NP-hard we will reduce Hamiltonian-Path problem to ultra Hamiltonian Cycle problem. To prove: Hamiltonian Path ≤P ultra-Hamiltonian Cycle Proof:For every instance of the Hamiltonian Path problem consisting of a graph G =(V, E) as the input can be converted to ultra-Hamiltonian Cycle problem consisting of graph G’ = (V’, E’). We will construct the graph G’ in the following way: V’ = Add vertices V of the original graph G and add 5-additional vertex V0 V1 V2 V3 V4 in butterfly formation(Explained below), such that each and every vertex of the original graph G are connected to vertices V3 and V4. Here in Graph G’ The number of vertices increases by 5, V’ =V+5. E’ = Add edges E of the original graph G and add new edges between the newly added vertices V3 and V4 to the all original vertices of the graph G. In G’ The number of edges increases by the number of vertices 2V. These 5 added vertices (V0 V1 V2 V3 V4) are in a butterfly graph with V0 as articulation point The new graph G’ can be obtained in polynomial time. The validation of reduction can be proved by the following two claims: i)(Forward Direction) Let us assume that the graph G contains a hamiltonian path covering the V vertices of the graph starting at a random vertex say Vstart and ending at Vend, now since we connected all the vertices to two new vertices V3 and V4 in G’. We extend the original Hamiltonian Path to a ultra-Hamiltonian Cycle by using the edges Vend to V3 and V4 to Vstart respectively. The graph G’ now contains the cycle traversing all vertices exactly once except V0 (articulation point in butterfly graph) which is visited more than once, this traversal start from V0 to V1 to V2 to V0 to V4 to Vstart to ”hamiltonian path in G” to Vend to V3 to V0. (Here V0 V1 V2 V3 V4 are of butterfly graph). So this is ultra-hamiltonian path in G’. . ii)(backward Direction) We assume that the graph G’ has a ultra-Hamiltonian Cycle passing through all the vertices, inclusive of V0 V1 V2 V3 V4, as V0 is an articulation point so it must be visited more than once and no other vertex is visited more than once, also the path from Graph G can enter the Butterfly graph either at V3 or V4 and leave the butterfly graph at V3 or V4(whichever is not used for entering in butterfly graph). Once the path leave the butterfly-graph it will visit each vertices of Graph G in path and comeback to butterfly graph(never to go back to vertex of graph G). This path must use one of V3 and V4 for exit and other for entry from Butterfly graph to vertices of Graph G (Ad V0 is articulation point and is already being visted more than once, so no other vertex can be visited more than once). Now to convert it to a Hamiltonian Path, we remove all the edges corresponding to the vertex V0 V1 V2 V3 V4 in the cycle. The resultant path will cover the vertices V of the graph and will cover them exactly once. So here we get hamiltonian path in G, from ultra-Hamiltonian cycle in G’ Thus we can say that the graph G’ contains a ultra-Hamiltonian Cycle if and only if graph G contains a Hamiltonian Path. Therefore, any instance of the ultra-Hamiltonian Cycle problem can be reduced to an instance of the Hamiltonian Path problem. Thus, the ultra-Hamiltonian Cycle is NP-Hard.
> -1 votes

---
Tags: graphs, np-hard, hamiltonian-path, polynomial-time-reductions, hamiltonian-circuit
---


# Question
Title: Build an FA that accepts only the words baa, ab, and abb and no other strings longer or shorter
I have been trying solve this problem for a while now for a university assignment. I'm required to build a DFA and an NFA for the above question. So far I have been able to solve the DFA but can not find a solution for a proper NFA after multiple tries.

The solution of my DFA for the language provided above:

**My attempts for the NFA are down below. I apologize for my messy handwriting but these were just rough works that I was drawing out on the go.**

My first attempt at solving the NFA

My second attempt at solving the NFA

My third attempt at solving the NFA

# Answer
For any language of finite cardinality you can make an NFA that has a totally separate linear path from the start node for each string in the language, with the last node of each path being an accepting node. In some sense this is the "simplest" NFA that accepts the language, and it may be what whoever set this question had in mind.

But as others have said, it's a silly question because any answer to the DFA part is automatically an answer to the NFA part.
> 0 votes

# Answer
The question is not clear as formed: if you want an NFA which is not a DFA and matches the language then you could take your DFA and add a new unreachable state with an $\epsilon$-transition to itself, or add other $\epsilon$-transition self-loops or many other things that will not change the language.

If the aim is to use non-determinism to reduce the size of the automaton, then you can omit the garbage state (so that the word would just "fall out of" the NFA at that point). Given that you have already optimised the paths for $ab,abb$ (based on their shared prefix) and $baa$ has no shared prefix or suffix with the other words, it looks like this is the only possible optimisation to be made.
> 1 votes

---
Tags: finite-automata, nondeterminism
---


# Question
Title: Run time for first and last index as a pivot in Quicksort?
What is the running time of quicksort if we always use the first index as the pivot? What if we always use the last index as the pivot? Is the running time $O(n)$?

# Answer
The worst case running time is not influenced by the strategy to select the pivot and is $O(n^2)$.

The average case is also not influenced if the distribution of the input is uniform, and is $O(n\log n)$.

The average case can be biased when the distribution is not uniform. For instance it will tend to $O(n^2)$ if there is a strong bias in favor of initially sorted arrays.
> 0 votes

---
Tags: quicksort
---


# Question
Title: Simplifying $b(abb + abbbb + aba^*bbb)^*$
I'm having issues simplifying regular expressions. I can't find a method to approach this problem.

How would I approach simplifying this regular expression:

$$b(abb + abbbb + aba^\*bbb)^\*$$

# Answer
> 1 votes
Note that $abbbb+aba^\*bbb = aba^\*bbb$. Also, note that you can "factorize" common expressions in the parentheses.

Your regular expression is equivalent to $b(a(\varepsilon + ba^\*b)bb)^\*$ (I don't know if it can be simplified again).

---
Tags: regular-expressions
---


# Question
Title: Upper bound for runtime complexity of LOOP programs
Recently I learned about LOOP programs, which always terminate and have the same computational power as primitive recursive functions. Furthermore primitve recursive functions can (as far as I understood) compute anything that isn't growing faster than $Ack(n)$.

Is this implying that the upper bound runtime complexity for LOOP programs is $O(Ack(n))$? And are there functions similar to Ackermann's function, which can't be computed by primitive recursive functions, but grow slower than $Ack(n)$?

(sorry for spelling and grammar)

# Answer
> 1 votes
The Ackermann function is a two-argument function:

$$\begin{eqnarray\*}A(0,n) & = & n + 1 \\ A(m,0) & = & A(m-1,1) \\ A(m,n) & = & A(m-1,A(m,n-1))\end{eqnarray\*}$$

Ackermann's function is an example of a function that isn't primitive recursive, but that doesn't by itself mean that the bound is tight.

It has the following properties:

1. The family of functions $\mathrm{Ack'}\_m(n) = A(m,n)$ are all primitive recursive. You can trivially see this by fixing $m$ and expanding the definition of $A$.
2. If $f : \mathbb{N} \rightarrow \mathbb{N}$ is a primitive recursive function, then there exists some integer $n$ such that $f(i) \< A(n,i)$ for all $i \ge n$. This result is not immediately obvious, but it's in most textbooks on the topic.

Note that from property 2, it follows that $\mathrm{Ack}(n) = A(n,n)$ is not primitive recursive.

These two properties taken together mean that Ackermann's function does, in some sense, give you a tight bound on the time complexity of primitive recursive functions. Intuitively, of all primitive recursive functions, $\mathrm{Ack}'\_m$ grow the "fastest".

So a function $f : \mathbb{N} \rightarrow \mathbb{N}$ is primitive recursive if and only if there is a natural number $m$ such that $f(n)$ can be computed by a Turing machine that always halts within $A(m,n)$ or fewer steps. This can be fairly easily extended to primitive recursive functions of multiple arguments.

# Answer
> 0 votes
Take Ack(n-1). Grows much slower than Ack(n).

---
Tags: algorithms, time-complexity, runtime-analysis, upper-bound
---


# Question
Title: All strings that contain no run of a's of length greater than two for $\Sigma = \{a,b,c\}$
The solution to this problem is $$(b + c)^\*+(b + c)^\*((a + aa)(b + c)^+)^\*(a + aa)(b + c)^\*. $$ Isn't the $+$ sign a union between sets?, I am asking because I am viewing the line $(b + c)^\*+(b + c)^\*$ as $A\cup A$ which is $A$ so I do not see a reason to repeat the same set.

# Answer
The $+$ sign stands for union, but you got the order of operations wrong. Your regular expression is the sum of $(b+c)^\*$ and $$ (b+c)^\*((a+aa)(b+c)^+)^\*(a+aa)(b+c)^\*. $$
> 1 votes

---
Tags: regular-expressions
---


title: Padding a 2SAT clause

text:
# Question
Title: Padding a 2SAT clause
In http://web.mit.edu/neboat/www/6.046-fa09/rec8.pdf, I see that they pad a 2SAT clause $(x\vee y)$ to make it a 3SAT clause by writing $(x\vee y\vee p) \wedge (x\vee y\vee \neg p)$. Why doesn't $(x\vee y\vee y)$ work instead? Isn't the truth table identical?

# Answer
Sometimes we insist that the three literals in a 3SAT clause belong to different variables. This ensures, for example, that a random assignment satisfies a clause with probability exactly $7/8$. The translation $x \lor y \lor y$ doesn't satisfy this condition, but the other one does.
> 3 votes

---
Tags: complexity-theory, reductions, logic, 3-sat, 2-sat
---


title: Why is KMP preprocessing O(N)?

text:
# Question
Title: Why is KMP preprocessing O(N)?
My intuition tells me that there is \<=1 increase in lps for each increase in the index. Can someone make a better argument why this is O(N)? My confusion arises from `len_ = lps[len_- 1]` .

def computeLPSArray(pat, M, lps):
    len_ = 0 # length of the previous longest prefix suffix

    lps[0] = 0 # lps[0] is always 0
    i = 1

    # the loop calculates lps[i] for i = 1 to M-1

    while i < M:
        if pat[i]== pat[len_]:
            len_ += 1
            lps[i] = len_
            i += 1
        else:
            # This is tricky. Consider the example.
            # AAACAAAA and i = 7. The idea is similar
            # to search step.
            if len_ != 0:
                len_ = lps[len_- 1]

                # Also, note that we do not increment i here
            else:
                lps[i] = 0
                i += 1

```

# Answer
Each `len_ = lps[len - 1]` decreases $lps$ by at least 1, thus, it can only happen for `lps[i - 1] + 1 - lps[i]` times, since you initialize `lps[i]` as `lps[i - 1] + 1`. Therefore, the maximum number of times `len_ = lps[len - 1]` can happen is $\displaystyle \sum\_{i=1}^n (lps\[i - 1\] + 1) - lps\[i\]$. As you know, $lps$ can increase by at most $n$ in total, therefore, it can decrease by at most $n$ in total, since $lps$ can never be negative, or equivalently, for each $+1$ $lps$ gets, it can get at most one $-1$. thus $\displaystyle \sum\_{i=1}^n (lps\[i - 1\] + 1) - lps\[i\]$ will be $O(n)$.
I hope my answer was helpful.
> 2 votes

---
Tags: algorithms, strings, python, string-matching
---


title: Convert NFA to DFA

text:
# Question
Title: Convert NFA to DFA
Is there a unique DFA for every NFA or there are more than one DFA an NFA can be converted to? I've read the algorithm for converting NFA to DFA.

# Answer
You say you are familiar with the standard subset construction that turns an NFA into a DFA. Let's start from there. If you study some examples you may realize that the result is not optimal. By "trimming" you might obtain a "better" DFA that still is equivalent.

In the first example you see that not all sets in the construction are reachable from the initial state. Of course those states can be deleted without changing the language. (top NFA, bottom DFA, unreachable states grayed out in the figure)

In my second example all states are reachable, but there is a "cluster" of states at the end, all of them which are accepting (states that contain "F"). Those states can all be indentified. This will give you a smaller equivalent DFA.

Although there is no unique DFA for a given regular language, it turns out that there is a unique *minimal* DFA for the language. That is the topic of DFA minimization algorithms.
> 2 votes

# Answer
There is more than one DFA. Just add a useless state with transitions from it to the other states. With no way to reach this useless state, the new DFA will be equivalent.

There are in fact an infinite amount of equivalent DFA's.
> 1 votes

---
Tags: automata
---


# Question
Title: Using saved registers at the main function with no other function calls [RISC-V]
The convention when a function is going to use a saved register is to save the contents of that register to the stack in case the caller (if there's one? the main function doesn't have one) had been using this register too and to restore the contents right before returning. Is this convention always obeyed? In the case of a really simple program, with just a main function and no other function calls, would the compiler prefer to optimize and disobey the convention, which means no saving before using the saved register? Of course, a convention is not a rule so i was wondering in which situations can these not be followed?

# Answer
Calling conventions may be called "convention", but they are rules. The reason they are called "convention" is because each compiler uses a different one, once a convention was chosen - it acts as rules.

Regarding the particular case of "main", it's being called by the operating system, so convention must be obyed.
> 1 votes

---
Tags: compilers, stacks
---


title: Regular expression of an FA

text:
# Question
Title: Regular expression of an FA
> If we convert an NFA to a DFA, is the regular expression of the DFA the same as the NFA?

I know the difference between an NFA and DFA and the algorithm to convert an NFA to DFA

# Answer
For any DFA, NFA or regular expression, there is only one corresponding language. But for one language, there can be multiple corresponding DFA's, NFA's or regular expressions, so it is incorrect to talk about **"the"** regular expression of a DFA, but would be correct to say **"a"** regular expression associated to a DFA.

If you know a regular expression $e$ associated to a DFA $\mathcal{A}$, and a NFA $\mathcal{B}$ associated to the same DFA $\mathcal{A}$, then that means that all 3 objets share the same language:

$L(e) = L(\mathcal{A}) = L(\mathcal{B})$

In particular, that means that $e$ is also a regular expression associated to $\mathcal{B}$.
> 1 votes

# Answer
Depending on the algorithm to convert it.

We can construct an algorithm to convert an NFA to a regular expression by first converting it to a DFA, and then the DFA to a regex. This will yield that the regex for the DFA would be identical to that of the NFA (by definition of the algorithm)

But, you might find some other way to directly convert an NFA to a regex. Since there might be more than one different regular expressions for the language of the NFA, you can't be sure that the regex of the NFA will be the same as that of the DFA.

But an important remark is that even if the regular expressions are different, they always recognize the same language. Converting an NFA to a DFA and that to a regex doesn't change the language, thus any regex created from them must recognize the same language.
> 1 votes

---
Tags: automata, finite-automata
---


# Question
Title: How is conditional jump implemented in the CPU?
After reading the question I'm still not sure how CPU does branching.

I understand that we have an instruction counter which points to the current instruction. And after performing conditional jump it either stays the same (increments as usual) or increases (jumps) and points to another branch, that's clear.

The problem: to define conditional jump we need a conditional jump? I mean in order to evaluate an `IF` the processor has to evaluate condition and `IF` it's true, then jump, otherwise not. It's an endless recursion.

So how does the conditional jump work on the lowest level?

# Answer
> 29 votes
> The problem: to define conditional jump we need a conditional jump? I mean in order to evaluate an IF the processor has to evaluate condition and IF it's true, then jump, otherwise not. It's an endless recursion.

Processors have some level of code that is *directly* executed, by hardware circuits. That might not be the same level that they expose as their ISA, processors may translate ISA-level instructions into some other form before really executing them or even treat ISA-level instructions as small subroutines that are implemented in micro-code, but there is still some level is not interpreted in terms of something else and built into the physical structure of the hardware.

Below is a diagram of a simple processor. The "if" in the logic of "if we need to branch then take PC+offset as next PC, otherwise take PC+4" is implemented by the top left multiplexer (labeled `Mux`). A multiplexer does not actually "do one thing or the other", it combines two signals and a control signal via the formula: `(~condition & a) | (condition & b)`. That's just a boolean formula that can be implemented easily as a physical circuit.

# Answer
> 6 votes
> The problem: to define conditional jump we need a conditional jump? I mean in order to evaluate an IF the processor has to evaluate condition and IF it's true, then jump, otherwise not. It's an endless recursion.

We can define a conditional jump in terms of a conditional move. For example, a conditional jump can be:

1. Increment the program counter to point to the next instruction.
2. Test the condition.
3. Conditionally load the program counter with the jump target if the condition tested true in step 2.
4. Go to the instruction the program counter refers to.

Notice that step 3 is executed unconditionally. It is a conditional move, but we *always* execute the conditional move. No jump capability of any kind is required here.

So conditional jumps are built out of conditional moves which are not implemented using any kind of jump at all. The conditional move *always* takes place, it just doesn't always have the semantic affect of moving anything.

It is important to understand that conditional moves can be built out of unconditional moves. If we do some math that results in the value we unconditionally move being the same as the previous value we are moving on top of, the effect is the same as if the move never occurred. So we can build the semantic effect of a conditional move entirely out of unconditional code.

Here's an example of a way to implement a conditional move that doesn't involve any conditions:

1. Multiply the current value of the program counter by the condition.
2. Invert the condition.
3. Multiply the current value of the jump target by the condition.
4. Add the result of step 3 to the program counter.

You can see that this leaves the value of the program counter unchanged if the condition is zero and loads the program counter with the jump target if the condition is one. This code is a straight-through flow with no conditional code at all.

Because a conditional move can easily be built out of unconditional operations, reducing a conditional branch to a conditional move is sufficient to implement conditional branches.

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


# Question
Title: Decidability of directed strongly connected graphs
Consider the problem of determining if a directed graph is strongly connected.
How to phrase it as a language and prove that it's decidable.

**My Thoughts :**
To think of decidability given a graph I could run DFS on each node and see that all the nodes
are reachable from the original node. So it can be determined if the graph is strongly connected
in polynomial time.
But I am confused about the formal automata definition of decidability. Which says a language is
decidable if there is a Turing machine such that this language is the one exactly accepted by the
Turing machine. Now given the above logic of DFS is that enough to prove decidability
or does one have to build a turing machine ?

# Answer
> 0 votes
Yes, the DFS is an algorithm, and hence has an equivalent turing machine. The definition of the decidability as you have said, is for the language to be exactly accepted by some turing machine.

The formal definition of the turing machine accepting the language of strongly connected graphs probably is waaaay too hard to explicitly write, so I guess your teacher meant for you to show an algorithm and state that an algorithm is equivalent to a turing machine.

Btw, as a side note, you can run DFS only twice in total instead of $n$ times - once per node. If you have free time, its a good exercise in algorithms :)

---
Tags: graphs, turing-machines, automata, connected
---


# Question
Title: Dynamic programming: Maximize total value
I was trying to solve this problem using dynamic programming.

We have $n$ objects in a row where each object has a value represented with a positive number. This is encoded with an array $V\[1\], . . . , V\[n\]$ where $V \[1\]$ is the value of the first object in the row, $V \[2\]$ is the value of the second object in the row and so on. We want to select a set $I \subseteq \\{1, . . . , n\\}$ of objects in such a way that the sum of its values, $\sum\limits\_{i\in I} V \[i\]$, is as large as possible. However, we cannot select objects that occupy consecutive positions in the row. That is, if we select object $i$, then we cannot select object $i − 1$ nor object $i + 1$. For example, if $V = (6, 4, 3, 7, 3)$ then the best option would be to select the first object (with value $6$) and the fourth object (with value $7$). It is easy to see that any other option would have smaller total value. We want a dynamic programming algorithm that, given as input array $V$ , computes the value of the set with highest value. Note that, in order to simplify matters, we do not ask that the algorithm returns the set, only its total value.

The probleem comes when it says "we cannot select object $i − 1$ nor object $ i + 1$". For $i-1$, the recursive case should be Optimal$(j-2)$+Value$(j)$, but no idea about $i+1$.

# Answer
> 1 votes
For $k \in \[\\!\[1, n\]\\!\]$, you can define $f(k)$ as the maximum value reachable using objects $1$, $2$, …, $k$, without two consecutives objects.

Now the key to the dynamic programming implementation is to see that:

$\forall k \in \[\\!\[3, n\]\\!\], f(k) = \max(f(k-1), f(k-2) + V\[k\])$

The reason is that to compute $f(k)$, you can either keep the $k$-th object or not. If you keep it, then you cannot keep the $k-1$-th object.

Finally, you want to compute $f(n)$.

---
Tags: dynamic-programming
---


# Question
Title: Show that a language is not decidable by reducing from ATM
Let (ATM denotes the language $\\{\langle M,w \rangle \mid \text{TM $M$ accepts $w$}\\}$)
show that the language L={\<M1,M2,w\> | M1 and M2 both accept or reject w} is undecidable by reducing
ATM to L
Not really sure how to approach this. Any hints or pointers

# Answer
> -1 votes
Try to define $M'$ that would accept $\iff$ both $M\_1$ and $M\_2$ accepted or rejected (together)

---
Tags: turing-machines, undecidability, halting-problem
---


# Question
Title: How can a one-counter machine accept $a^n b^n c^n$?
It is mentioned in Which languages are recognized by one-counter machines? that a one-counter machine can accept $\\{a^n b^n c^n\mid n\geq 0\\}$. Can someone please explain how this is done?

# Answer
Be careful where the hyphens are! *One counter-machine* can recognize $a^n b^n c^n$, but *a one-counter machine* cannot.

From the answer you linked to:

> Languages recognized by one\[-\]counter automata form a proper subset of the context free languages.

(There's a proof for this, but it's long and boring, so I'm going to leave it out; you can find it online if you're interested.)

Since $a^n b^n c^n$ is not context-free, it cannot be recognized by a one-counter automaton.

It *can*, however, be recognized by a *two*-counter machine (a machine with two counters). The basic structure goes something like this:

* When you see an $a$, increment $X$, increment $Y$
* When you see a $b$, decrement $X$
* When you see a $c$, decrement $Y$
* Accept iff the letters are in the right order (a trivial state machine), AND $X = 0$, AND $Y = 0$

This is "one counter-machine" (in the sense that it's a single machine using counters). But you need at least two counters to do it.
> 3 votes

# Answer
Dexter Kozen mentions, in his textbook *Automata and Computability*, that a counter automaton has a two-way read-only input head and counter. The counters store a non negative integer. In each step the automaton can independently increment, decrement or test for zero its counter and can move the input head in either direction. Here is the exact definition he uses:

> A *$k$-counter automaton* is a machine equipped with a two-way read-only input head and $k$ integer counters. Each counter can store an arbitrary non-negative integer. In each step, the automaton can independently increment or decrement its counters and test them for $0$, and can move its input head once cell in each direction. It cannot write on the tape.

Your language is mentioned explicitly in the textbook:

> One-counter automata are not as powerful as arbitrary TMs, although they can accept non-CFLs. For example, the set $\\{a^nb^nc^n \mid n \geq 0\\}$ can be accepted by a one-counter automaton.

I think the **bidirectional** nature of input head is what gives the automaton the power to check equality of the number of $a$'s and the number of $b$'s up to the $b$-$c$ border, then the input head goes back to the $a$-$b$ border and then checks for equality of the number of $b$'s and the number of $c$'s. If the string fails any of the above equality it rejects the string.
> 2 votes

---
Tags: formal-languages
---


# Question
Title: Is programming an emulation of the real world?
Assume that we have a car in the real world, this car would be composed of atoms, and we can do operations on this car (for example: we can move the car or change its color, etc.).

And assume that we have a car object in the computer world (in RAM), this car object obviously is not a real car but rather a representation of a real car, but we can imagine that this car object is a real car, and we can also do operations on this car object (for example: we can move the car object or change its color, etc.).

Now if we want to for example change the color of the car in the real world, we have to manipulate some of the atoms that compose the car to accomplish that. And to change the color of the car object in the computer world (in RAM), we have to manipulate some of the bits that compose the car object to accomplish that.

However, one difference that I can think of between the real world and the computer world is that in the real world the car is visible to people, however in the computer world the car object is not visible to people (you have to paint the car object on the screen to make it visible to people).

So can we think of programming as an emulation of the real world? more specifically, can we think of the real world as "real world RAM" that can contain any object (these objects would be composed of atoms) in the same way that RAM can contain any object (these objects would be composed of bits)?

# Answer
This is a third true, a third false, and a third unknown.

## Why you might think its true

As you have stated, it does intuitively makes sense that any kind of "computation" or "effect" in the real world has an equivalent computation in the computer. After all - the world we know is compromised of atoms and such, and it makes sense we can store such data in bits. If im not mistaken, the Church-Turing hypothesis that was based on this intuition hypothesizes that anything that can be done in the real world can be done in a computer

## Why we might think its false

Think about our world - it has a lot of people, which independently and simultaneously do things. This kind of behaviour is not really natural for a computer - a computer can only process one thing (or at most a handful of things, if it has a few cores) at once. This leads us to think it might be impossible to think of the world as a giant computer.

## Why we still don't know, and will probably never know

Physics is a branch of science that always develops. There is always more to uncover about our universe and its underlying mechanisms. Therefore, there will always be a way to create a newer and mpre sophisticated computer that can do more things. For example, the recent developments for quantum computers might change things up: In a quantum computer there are things that can be computed faster than in a normal computer. In fact, a quantum computer is capable of doing something *similar* to parallel computing (a common misconception is that it does compute in a parallel way, but actually it does something else that creates this effect).

This means that both statements for why it could be true and why it could be correct! It might be true that normal computers can't emulate all of the stuff that can be done in the real world, but don't know whether it will still hold for a newer computer based off of a brand new idea in physics that would be developed in a few hundred years from now.

Still, this is only my own opinion. If you want more (and probably better) answers, you might want to consider asking this to philosophers.
> 2 votes

# Answer
You can think of it any way that is useful to you. There's no one right way to think about programming; there are many ways to think about it, each of which have some advantages and disadvantages.

Some kinds of programming might be aimed at attempting to simulate the real world to some degree of accuracy. Other kinds of programmming have other goals, such as doing something that has no correspondence in the real world.

Remember that all models are wrong, but some are useful. In other words, when we try to model or simulate the real world, we are building a model of the world, and often we don't try to model everything with full accuracy: instead, our model might focus on some aspects that we consider important for our particular setting (e.g., which direction the car moves when we turn the steering wheel) and not on other aspects that we consider unimportant for this particular application (e.g., the tiny smear you get on the hood when a bug hits it).

Philosophical questions about how to think about reality are beyond the scope of this site.
> 1 votes

---
Tags: object-oriented
---


# Question
Title: How would I prove that the regular expression rejects string?
Prove that the regular expression $\Sigma\Sigma(ab\cup ba)^∗a$ rejects the string $aabaabba$.

Would this be because the union of $ab$ and $ba$ would not accept the string $aabaabba$? I'm just confused on how to explain it.

# Answer
> 2 votes
Any word accepted by this regular expression has to be either in length 3 or to end with $aba$ or $baa$.

Try to prove this fact, and use it to show that $aabaabba$ must be rejected.

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


title: What is this turing machine doing

text:
# Question
Title: What is this turing machine doing
There is a following Turing machine. I want to understand what it is doing :

I tried running it on input 100, 10000. Both these strings are accepted whereas 10,1000 are rejected
That leads to a good guess that it's accepting the string's with 1 followed by 0's where number of
0's = power of 2. But I can't prove it or deduce it from looking at the state diagram of it.
Any insights into it ?

# Answer
> 0 votes
I think your interpretation is correct. $q\_i$ and $q\_{ii}$ are states that guarantee that $10$ and $100$ will be correctly accepted. It is clear that any other input of size $\leq 3$ will be rejected.

Now suppose you are in state $q\_s$, the tape is $1Z^{2^k}u$ (with $u\in \\{0,1\\}^\*$), and the head is in position of the first $Z$ of the tape. The cycle $q\_s, q\_d, q\_r, q\_l$ will let you do round trips, each trip transforming a $Z$ in $Y$, and a $0$ in $X$.

On the last trip, you will transform the last $Z$ in $Y$, then cross all $X$'s (in $q\_{pf}$), and transform a zero in $X$. Therefore, if $u\neq 0^{2^k}v$, the Turing machine will reject. If not, we will get in $q\_f$.

If $u = 0^{2^k}v$, then three cases are presented:

* $v = \varepsilon$, we finish in $q\_{acc}$ so the word is accepted (and the input was necessarily $10^{2^{k+1}}$);
* $v = 1w$, we reject;
* $v = 0w$, we transform all $X$'s and $Y$'s into $Z$'s, reach the left most symbol (which must be 1), and finish in $q\_s$. The tape is then $1Z^{2^{k+1}}v$ and we are in the first situation.

---
Tags: turing-machines
---


# Question
Title: A monotonically nondecreasing function $ f(n) $ s.t $ f \in O(n^2) $ and $ f \notin o(n^2) $ but also $ f \in \Omega(n) $ and $ f \notin \omega(n) $
I am trying to look for an example of a monotonically non-decreasing function $ f(n) $ such that:

$ f(n) \in O(n^2) $ and $ f(n) \notin o(n^2) $ but also $ f(n) \in \Omega(n) $ and $ f(n) \notin \omega(n) $. The domain could also be all real numbers.

I considered different variations of piecewise functions, for example I considered the function $$ f(n)= \begin{cases} n^{2-\frac{1}{n}} &\text{if}\\, n =2k+1\\ n^{1+\frac{1}{n}}&\text{if}\\, n=2k\\ \end{cases} $$

which satisfies the growth rate conditions, but is clearly not monotonically non-decreasing.

I would be happy to hear your ideas, thank you.

# Answer
> 3 votes
I may be wrong, but it seems to me that the function defined by:

$f(n) = \left\\{\begin{array}{rl}1 & \text{if }n=1\\2^{2^{\left\lfloor \log\_2\log\_2 n \right\rfloor+1}}&\text{otherwise}\end{array}\right.$

satisfy the conditions.

To explain why, the values taken by $f(n)$ will be $1, 4, 4, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 256, 256, …$

The idea is that when $n=2^{2^k}$, then $f(n) = 2^{2^{k+1}} = n^2$, and when $n=2^{2^k}-1$, then $f(n) = 2^{2^{k}} = n +1$. That way, you will guarantee the 5 conditions: $(O(n^2) \setminus o(n^2)) \cap (\Omega(n) \setminus \omega(n))$ and increasing.

---
Tags: asymptotics, big-o-notation
---


title: Asymptotic notation for summations

text:
# Question
Title: Asymptotic notation for summations
I am struggling to understand why this property of asymptotic notation is true

# Answer
In general, it is not: see Summation of asymptotic notation, Why is $\sum\_{i=1}^n O(i)$ not the same as $O(1)+O(2)+\dots+O(n)$?.

But if each $O(f(k))$ term uses the same hidden constant, then it follows by expanding the sum: see https://en.wikipedia.org/wiki/Big\_O\_notation#Sum, Summing big-O-notation, and then apply them repeatedly.
> 3 votes

---
Tags: complexity-theory, asymptotics, big-o-notation, summation
---


title: Time Complexity of Memoized Solution

text:
# Question
Title: Time Complexity of Memoized Solution
I was solving Stone Game II on LeetCode. I was able to come up with a recursive (TLE) solution, which I optimized using memoization. The recursive solution computes a function $u(i,m)$, depending on an array $A\_1,\ldots,A\_n$, where:

* $i$ is the starting index
* $2m$ is the maximum size of the window at $i$

Here is the recurrence: $$ u(i,m) = \begin{cases} \sum\limits\_{j=i}^{n} A\_j & \text{if } i + 2m-1 \> n, \\ \sum\limits\_{j=i}^{n} A\_j - \min\limits\_{\substack{0 \leq k \leq 2m-1 \\ i+k \le n}} u(i+k+1, \max(m,k+1)), & \text{if } i + 2m-1 \le n. \end{cases} $$ (Using $O(n)$ preprocessing, the sums can be computed in $O(1)$.)

I am interested in the value of $u(1,1)$.

However, I am not sure about the time complexity of this solution.

According to me :

* There are $m \times n$, where:
    + $n$ is the number of elements in $A$.
    + $m$ is the width of window that varies at each step.
* Each state is being calculated only once.
* $m$ can not be greater than $n$, the size of $A$.

Hence, the time complexity of the solution should be $O(n^2)$.

Is there something that I am missing? Is there a mathematical way to prove this?

# Answer
> 1 votes
For each $i,m$ in the range $n/3 \leq i,m \leq 2n/3$, computing the recurrence requires going over $\Theta(n)$ values of the parameter $k$, hence calculating $u(i,m)$ for all of these values of $i,m$ requires time $\Theta(n^3)$.

Do you actually encounter such values of $i,m$ when calculating $u(1,1)$? It's not immediately clear to me, but you'll have to rule it out if you want to prove a better upper bound on the running time of your procedure.

---
Tags: algorithms, time-complexity, runtime-analysis, dynamic-programming, memoization
---


title: Randomized algorithm for minimum cut

text:
# Question
Title: Randomized algorithm for minimum cut
Given a simple undirected connected graph $G$, I want to find a min-cut of $G$ using a randomized algorithm.

My attempt was to select a random edge in $G$ and reduce that edge to a single vertex. And recursively do it until the number of vertices is at most 2.

The number of edges present (in the resulting multi-graph) will be the min-cut. This is the standard algorithm I found at many places.

Will this lead to the exact number of min-cut and how can I extract the vertices on each side of the cut?

# Answer
Yes, that's exactly the correct algorithm, and what you have produced is Karger's algorithm.

Since the algorithm is randomized, you can run it several time over in the hope of getting a better solution. There is no guarantee that you will get the optimum cut, but you can make the error probability as low as you want to.

Here is Thore Husfeldt's illustration of it (cc-by-sa-3.0), *10 repetitions of the contraction procedure in Karger’s algorithm for minimum cut on a 10-vertex graph. The 5th repetition finds the minimum cut of size 3.*
> 1 votes

---
Tags: randomized-algorithms, minimum-cuts
---


# Question
Title: Decidable? If a Turing Machine M, on input w, will M ever move its read/write head to the left?
1. If a Turing Machine M, on input w, will M ever move its read/write head to the left?
2. Determine if this violates Rice's Theorem.

**1.** I think the answer for Q1 is decidable because we can make a Turing Machine that decides the problem as follows:

> Step 1: If M halts on w and it never moved left, reject it.
>
> Step 2: If M ever moves left, halt and accept.
>
> Step 3: If M loops forever (some configuration repeats) then reject it
>
> Step 4: Otherwise, reject (M moves right, eventually encounters a blank symbol, and moves right forever, which means that M will never move left. So, reject it.)

**2.** We proved that for some language L L(M) is decidable. So, we can say that L(M) is Turing-recognizable. The property 'L(M) is Turing-recognizable' is trivial because there does not exist a Turing-recognizable L2 such that L2 does not belong to L. Thus, our problem is decidable with the following decider:

> "Step 2: If M ever moves left, halt and accept."

, and this does not violate Rice's Theorem.

# Answer
> 7 votes
I'm afraid that your logic doesn't make sense, since you can't implement Step 1. In order to implement it, you'll have to run $M$ and see if it every halts, but this is impossible, since it's the halting problem.

Nevertheless, the problem is decidable. The details of this argument depend on the exact Turing machine model, but in order to illustrate the basic idea, it suffices to consider the simplest possible model, in which there is only one head, and at each step, it has to move (either one step to the left, or one step to the right). We simulate $M$ for $|w|$ steps. Either it has moved to the left (in which case we know the answer), or otherwise, it has gone past the input.

In the latter case, suppose that the Turing machine is at some state $q$ after $|w|$ steps. Let's say that a state is *bad* if when $M$ reaches it, if the input under the head is blank, then it moves left. Construct a directed graph in which there is an arrow from $q$ to $p$ if $M$ transitions from $q$ to $p$ when the input under the head is blank. There are three cases:

* The path starting at $q$ reaches a bad state. In this case the head of $M$ will eventually move left.
* The path starting at $q$ reaches a halting state or closes a cycle, in both cases not going through a bad state. In this case the head of $M$ will never move left.

This shows how to decide whether $M$ every moves left upon reading $w$.

---

This might seem to contradict Rice's theorem, but it doesn't. The reason is not what you state — the problem is not trivial: there are pairs $(M,w)$ for which $M$ does move left when running on $w$, and there are other pairs when this doesn't happen. Rather, the property of never moving left is a *syntactic* property rather than a *semantic* property: it depends on the Turing machine $M$ instead of on its language $L(M)$.

---
Tags: turing-machines
---


# Question
Title: How does strong NP-completeness agree with encoding complexity?
I've recently read about the concepts of weak and strong NP-completeness, but faced a problem in wrapping my head around them. I've understood that problems which have numerical parameters (like discrete knapsack) and can be solved polynomially in the values of those parameters (which implies exponential time in their binary encoding) are said to be weakly NP-complete. There exists no known polynomial-time computable mapping from any NP-complete problem which produces a unary encoded input to another NP problem like the knapsack problem, where the numerical parameters are polynomially bounded in the input length of the original problem. On the other hand, problems which are known to be NP-complete when restricted to the subset of instances where the numerical parameters are polynomially bounded in the input length of the original problem are called strongly NP-complete, but there isn't any known pseudopolynomial algorithm for those. Whether the classes of weakly and strongly NP-complete problems are the same is unknown and depends on the outcome of the P-NP question.

Now, my confusion stems from the chosen encoding. Weakly NP-complete problems are thought not to be NP-complete in their pseudopolynomially solvable instances. Those, however, are only polynomial because their input is provided in unary encoding, which avoids the exponential unfolding of the numerical values from binary format. So, an alternative way of defining weak and strong NP-completeness would simply depend on the existence of a polynomial algorithm when provided the input in unary encoding. But how could any problem being provided unary encoded input be NP-complete, that is, possess a Karp reduction (i.e. computable in polynomial time) from any other NP-complete problem? Since the original problem cannot be assumed to be given in unary encoding, its binary encoding has to be unfolded into unary encoding during the mapping, which would always require exponential time, wouldn't it? This holds even if we only require the numeric parameters of the problem be given in unary encoding, since we must assume the length of numbers to grow with the problem size. But then, this would imply that there cannot be any strongly NP-complete problems, and that any form of NP-completeness must be a weak one. Since the opposite is known, I clearly must've made an error in my reasoning, but I cannot spot it.

# Answer
> 0 votes
I figured it out after looking at this paper. My error in thinking came from generally assuming some direct (i.e. linear) relationship between the numbers in the source problem and those in the target problem to which the reduction is mapping. However, producing unary output in the reduction in polytime requires that such a connection must only exist in those cases where the source problem is a number problem which has its numerical values polynomially bound in its binary input length. If, on the other hand, the source problem is allowed to have exponentially large numbers, the #bits required to encode the numbers in the target problem may only scale logarithmically with the #bits required for the numbers in the source problem, ensuring polynomial boundedness of the maximum value and enabling changing from binary to unary encoding in polytime.

---
Tags: complexity-theory, np-complete, reductions, complexity-classes, encoding-scheme
---


title: Four functions problem

text:
# Question
Title: Four functions problem
**This is not from online contest**

Hi guys, a friend of mine recently give me this problem that I couldn't figure out an effective way to solve it.

---

## Four functions

You are given four functions $$ \begin{align} A(x)&=\text{Number of }i\text{ where }1\leq i\leq x\text{ and }\gcd(i,x)=1\\ B(x)&=\sum\_{d|x}A(d)\\ C(x)&=\text{Sum of exponents of each prime in the prime factorization of }B(x)\\ D(x)&=\sum\_{i=1}^{x}C(x) \end{align} $$

**Input:**

* First line: $T$ \[number of test cases\]
* Each test case consists of an integer $N$

**Output format**

For each test case, print a single integer denoting the value of $D(N)$ in a new line.

**Input constraints**

$$\begin{align}1\leq T\leq 10^6\\1\leq N\leq 10^6\end{align}$$

---

Here's my observation:

* About the constraints, there are 10^6 test cases, each test case can be as large as 10^6, I estimate we need an algorithm that is at least O(nlogn). Otherwise we will have TLE.
* I guess this problem is a **math** one. We somehow need to come up with an efficient formula to resolve all 4 functions.
* I know for sure if we solve this problem naively, we cannot pass all test cases. Even if we use the best method to compute `gcd` and `prime factor`.
* I've thought about this one for two days I can't find an acceptable solution for this problem. You can assume that this problem have time limit of 5 seconds.

Since this is a **math** problem, some talented and gifted genius out there might be interested. :D

Please help to come up with a formula to solve this, or provide an understandable solution. Thank you very much.

# Answer
> 1 votes
Let me put together the two comments.

The function $A$ is Euler's totient function, which is often called $\phi$.

The function $B(x)=\sum\_{d|n}\phi(d)$ is known to be equal to $B(x)=x$.

Now, observe that $D(x)=\sum\_{i=1}^{x}C(B(i))=\sum\_{i=1}^{x}C(i)=C(x!)$, where the last equation is because $C$ satisfies $C(a)+C(b)=C(ab)$.

Now, if $p\_1\<p\_2\<\ldots\<p\_k$ are the primes less than or equal to $x$ and $x!=p\_1^{a\_1}p\_2^{a\_2}\dotsm p\_k^{a\_k}$, then $$C(x!)=a\_1+a\_2+...+a\_k$$

We can use Legendre's formula to compute each $a\_i$. Note that the formula doesn't need to compute $x!$, but it computes $$a\_i=\left\lfloor\frac{x}{p\_i}\right\rfloor+\left\lfloor\frac{x}{p\_i^2}\right\rfloor+\left\lfloor\frac{x}{p\_i^3}\right\rfloor+\ldots$$ where there are actually finitely many summands.

So, an algorithm to compute $D(x)$ can be:

1. Compute the primes $p\_1,p\_2,\ldots,p\_k$ up to $x$. This can be done using some sieve, like Erathostenes' or Atkin's
2. Then for each prime evaluate Legendre's formula above, which takes about $\log\_{p\_i}(x)$ divisions.

---
Tags: mathematical-programming, mathematical-analysis, primes
---


# Question
Title: I'm quite confused about the convergence of pix2pix cGAN, how can we tell whether my model is well trained?
Usually we will see decreasing loss for regular CNN model, but for GAN, it seems to be not that simple. How can we tell whether my model is well trained?

# Answer
Create a test set, by taking a subset of the training set (make sure to **not** train on this test set!). Then evaluate the model against the given labels in the test set.

Also, this trick is very useful generally, since it works for any supervised machine learning model.
> 1 votes

---
Tags: artificial-intelligence
---


# Question
Title: Given two DFA's accepting the same language, does one have to refine the other?
I have a logical question that I can't quite crack:

> Given two automata accepting the same language $L$, does one have to refine the other?

In other words, if $A\_1$ and $A\_2$ both accept $L$, with associated equivalence relations $R\_{A\_1}$ and $R\_{A\_2}$, does $R\_{A\_1}$ have to refine $R\_{A\_2}$, or vice versa?

I am leaning toward the answer yes because if we have a regular language $L$ which is accepted by an automaton $A$, we can show that the relation $R\_A$ refines the relation $R\_L$, meaning $R\_A \sqsubseteq R\_L$, which means that both $R\_{A\_1} \sqsubseteq R\_L$ and $R\_{A\_2} \sqsubseteq R\_L$.

We are currently studying the Myhill-Nerode Theorem, so I'm guessing it has something to do with it. I've tried combining few theorems together, but came out empty.

# Answer
For an integer $n$, consider the following DFA $A\_n$ on the alphabet $\\{a\\}$. The set of states is $\\{q\_0,\ldots,q\_{n-1}\\}$. The initial state is $q\_0$. All states are accepting. The transition function is $\delta(q\_i,a) = q\_{i+1}$, where we identify $q\_n$ with $q\_0$.

Do the relations of $A\_2$ and $A\_3$ refine each other?
> 2 votes

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


# Question
Title: Bucket sort has uniformly distributed data
Implementation of bucket sort is mainly useful when input is uniformly distributed over a range. So the ques here is what is the significance of having input data uniformly distributed for applying bucket sort? What happens if this does not hold?

# Answer
> 1 votes
Bucket sort will be slower if the data distribution is highly non-uniform. The primary advantage of bucket sort over other sorting algorithm is that it is faster when the data is uniformly distributed; so if the data is highly non-uniformly distributed, the advantages of bucket sort may evaporate.

---
Tags: algorithms, sorting
---


# Question
Title: Consider a 1-tape TM that starts with n ≥ 1 written in unary/binary notation on its tape. Explain how it can count down from n to 0 in O(n) steps
> Consider a 1-tape TM that starts with n ≥ 1 written in unary/binary notation on its tape. Explain how it can count down from n to 0 in O(n) steps.

For binary notation, if we have a binary counter representing the number n, then will there be a total of O(log n) different bits (since each bit represents exponentially smaller and smaller values)?

# Answer
> 1 votes
Here is a rough sketch of how you can solve the second part. Suppose that the number $n$ is of the form $2^k - 1$ for some non-negative integer $k$ and that the head of the Turing Machine is initially located at the end of the binary representation of $n$ (i.e., at the position of the rightmost, least significant, bit).

Proceed as follows:

* While the current tape symbol is a $0$, replace it with $1$ and move the head to the left.
* If the current symbol is $1$:
    + Replace the current symbol with a $0$
    + Move right until you reach the last non-blank symbol of the tape
    + Repeat from the beginning
* Halt

In analyzing the time complexity, I will ignore the transitions that move right. This is because each of these transitions can be "charged" to a distinct transition that moved the head to the left, and we can safely ignore multiplicative constants in our asymptotic upper bound on the running time.

Notice how, once we ignore these transitions, at most a constant number of steps pass from the instant in which a TM flips a bit of the input tape, to the instant when the next bit flip happens. Then, to estimate the running time we can just count the overall number of bit flips.

Consider all values of $n$ from $2^k-1$ down to $0$, in this order. The rightmost bit changes every time we move from one value to the next. The 2nd to last bit changes every other time, the 3rd to last bit changes once every $4$ values, and so on. In general, the $i$-th least significant bit changes once every $2^{i-1}$ values.

The total number of bit flips is then: $$ n + \frac{n}{2} + \frac{n}{4} + \dots = O\left(\sum\_{i=0}^\infty \frac{2^k}{2^i}\right) = O(2^k) = O(n) $$

# Answer
> 0 votes
If you consider the binary representation of a number $n = (a\_0a\_1…a\_{k-1}a\_k)\_2$ ($a\_0$ being the least significant bit) written on the tape, then in order to decrement $n$ by one, you will have to do the converse of an increment:

* with $i$ starting at $0$, while $a\_i = 0$, transform $a\_i$ into $1$ and increment $i$;
* unless $n = 0$, you will find $i$ such that $a\_i = 1$.

+ if $i = k$, then transform this $1$ into the blank symbol;
    + otherwise, transforme this $1$ into $0$.

Once you have done that, you can return to the left-most bit, and do it again, until you reach $0$.

Now to analyse the complexity: it seems that in the worst case, we will have to move the head of the Turing machine until the last bit of the input, and that may take $\Theta(\log n)$ steps. Since $n$ decrements are necessary, it looks like the total complexity is $\Theta(n\log n)$, but in reality the worst case for one decrement is not that often reached.

Actually, the necessary steps for one decrement are equal to the number of consecutives $0$'s at the beginning of the tape ($\times 2$ since we have to return to the left-most bit). Now you just need to count $\sum\limits\_{k=0}^n$(number of 0's at the beginning of k), and verify that it is $O(n)$.

---
Tags: time-complexity
---


# Question
Title: Algorithm to get any spanning tree not necessarily a minimum spanning tree
Is there an algorithm to find a spanning tree. I know that there are $n^{n-2}$ of them and we have algorithms to find a minimum spanning tree.

1. But what if I just want any spanning tree? It doesn't have to be minimum.
2. For a graph with no edge weights, should I just assume that the edge weights are all 1 and then use a Kruskal's or Prim's algorithm for minimum spanning tree?

# Answer
> 10 votes
Use the BFS or the DFS algorithms. They work in $O(n)$ and output a spanning tree if the input is a connected graph

# Answer
> 10 votes
Just do a graph traversal algorithm, like DFS or BFS.

# Answer
> 1 votes
While I agree with the other answers as the "best" way to find a spanning tree, your intuition to just assume all edge weights are 1 and then use an algorithm for MST is also good. Prim's and Kruskal's algorithms are both quite fast. In particular, if you avoid sorting the edges by weight (which you know you don't have to do because you set all the weights to 1, Kruskal's algorithm just becomes:

start with an empty set of edges T. For each edge see if $T \\,\cup \\,e$ has a cycle, if not $T := T \\,\cup \\,e$

This is $O(m)$ running time with the proper data structures (where m is the number of edges), which is on par with DFS and BFS theoretically. However, BFS and DFS are probably going to be faster and simpler.

---
Tags: spanning-trees
---


title: Resolution in prolog

text:
# Question
Title: Resolution in prolog
What exaclty is resolution in prolog and how does it enables Prolog to obtain the following answer:
?- sublist(\[b,c\],\[a,b,c\]).
true

# Answer
As expressed, this looks like a homework question, and there is missing information, specifically, the definition of `sublist/2`.

Having said that, you did ask a good computer science question, namely, what exactly is "resolution" in Prolog and, more to the point, why is it called "resolution" in the first place.

If you're not used to reading sequent notation, what follows is going to need a little bit of explanation. A sequent is a formula of this form:

$$A\_1,\ldots,A\_p \vdash B\_1,\ldots,B\_q$$

where the $A\_i$ and $B\_i$ are logical formulas. The turnstile symbol, $\vdash$, is pronounced "entails".

A good intuitive sense of what this sequent means is that the conjunction of everything on the left-hand side of the turnstile, $A\_1 \land \cdots \land A\_p$, logically entails the disjunction of everything on the right-hand side of the turnstile, $B\_1 \lor \cdots \lor B\_q$.

The exact form of a sequent may in general depend on the logic being studied; for example, some logics only use one formula on the right-hand side of the turnstile. Or the formulas may have special forms.

A rule is a line with zero or more sequents above it and one sequent below it. Here is an example of a rule, the "$\land$-introduction" rule in propositional logic:

$$\frac{\Gamma \vdash A \quad\quad \Delta \vdash B} {\Gamma,\Delta \vdash A \land B}$$

If the assumptions $\Gamma$ entail the conclusion $A$, and the assumptions $\Delta$ entail the conclusion $B$, then the combined assumptions $\Gamma,\Delta$ entail the conclusion $A \land B$.

This is the resolution rule in logic:

$$\frac{\Gamma \vdash \Sigma, c \quad\quad \Delta \vdash \Xi, \neg c} {\Gamma,\Delta \vdash \Sigma,\Xi}$$

Making the disjunctions explicit, you can think of it this way:

$$\frac{\Gamma \vdash A\_1\lor \cdots \lor A\_p \lor c \quad\quad \Delta \vdash B\_1\lor \cdots \lor B\_q \lor \neg c} {\Gamma,\Delta \vdash A\_1\lor \cdots \lor A\_p \lor B\_1\lor \cdots \lor B\_q}$$

If it helps, you can think of what is going on in a classical propositional logic. By the law of the excluded middle, $c$ is either true or false. If it's false, then all of $B\_1, \ldots, B\_q$ might be false, but at least one of $A\_1, \ldots, A\_p$ must be true. Similar reasoning applies if $c$ is true.

Now to get the intuition on what resolution in Prolog means, we're going to look at a cut-down version of Prolog with no explicit disjunction and no negation. Every clause is a Horn clause, which of this form:

```
p :- q,r,s.

```

The comma symbol means logical "and", and the `:-` should be thought of as an implication pointing to the left. If we can prove `q`, `r`, and `s`, then we can conclude `p`. Or, to put it another way, $\left( q \land r \land s \right) \Rightarrow p$. Or, to put it yet another way, $\neg q \lor \neg r \lor \neg s \lor p$.

You can think of a cut-down-Prolog program as being essentially in conjunctive normal form. All of the clauses are true, so they are logically "and-ed" together. Each clause is an implication with one conclusion, so it is logically an "or".

To prove $p$ in this system, you can essentially do it by contradiction: you assume $\neg p$ and try to show that the program (which, remember, is in CNF) is unsatisfiable.

Applying logical resolution to $\neg p$ and $\neg q \lor \neg r \lor \neg s \lor p$ gives $\neg q \lor \neg r \lor \neg s$. So now, to prove that this is unsatisfiable, we can perform resolutions with other clauses that have $q$, $r$, or $s$ positive, that is, they are the left-hand side of some Prolog clause.

What actually happens in Prolog is the same thing, only without all the negation: we prove $p$ by trying to prove $q$, $r$, and $s$.

What I can hope you can see here is why it's called "resolution", because Prolog's inference rules play the same role as predicate logic resolution.

Prolog's actual inference rule is known as "selective linear definite clause resolution, with negation-as-failure", or SLDNF resolution for short. It deals with the fact that pure Prolog is a first-order predicate system with a full complement of logical operators, so you need to deal with unification and variable substitution and negation-as-failure.

Extra-logical operators such as the cut are another issue entirely. Coming up with formal semantics for Prolog was something of an industry in the 80s and 90s because of this. I think we have now decided that Prolog has an *operational* semantics, and if you need something that is more "logical", you need a "purer" logic language than Prolog. But still, the basic mechanism is SLDNF resolution.
> 3 votes

---
Tags: prolog
---


# Question
Title: Join of recursively enumerable set and its complement
The union of a recursively enumerable set and its complement is $\Sigma^\*$, which is definitely recursively enumerable. What if instead we consider the following operation, on an RE set $S$? $$ \\{ \\# w : w \in S \\} \cup \\{ \\\\$ w : w \in \overline{S} \\} $$ Is the result recursively enumerable?

# Answer
The operation you described in actually the join operator in the semilattice of Turing degrees, defined as $A\sqcup B=\\{0x | x\in A\\}\cup \\{1x | x\in B\\}$. It is not hard to show that $A,B\le\_T A\sqcup B$, thus if $A\in RE\setminus R$ then $\overline{A}\notin RE$ and thus $A\sqcup\overline{A}\notin RE$.
> 2 votes

---
Tags: computability, undecidability
---


# Question
Title: Essential bit content - prove that we can't use less bits than that
Let $H\_0$ be $\log\_2(|A|)$, where $A$ is a set.

Let $C$ be a compressor $C\colon A \to \\{1,0\\}^l \cup \bot$.

This is a silly question, because intuitively it seems obvious.

How can I prove that $l$ can't be less than $H\_0$?

I can prove that $l = H\_0$ is sufficient, but how can I prove that it can't be less.

# Answer
> 1 votes
The function wouldn't be one-to-one otherwise.

The size of the set in the left is $|A|$, and its image would be of size at most $2^l\<2^{H\_0}=|A|$, therefore, the function wouldn't be injective and thus you wont be able to de-compress some of the data.

Therefore it will be a lossy-compression for any $l\<H\_0$.

---
Tags: information-theory
---


# Question
Title: Divide and conquer problem:sequence of integers (with possible repetitions)
I was trying to solve this problem.

Let $A\[1\] . . . , A\[n\]$ an ordered sequence of integers (with possible repetitions) and let $k$ be any integer. A contiguous subsequence $A\[i\], A\[i + 1\], . . . A\[j\]$ of $A$ is $k$-separated if the difference between every pair of its consecutive elements is at most $k$.

For example, if $A = \[1, 3, 3, 4, 4, 4, 5, 7, 8\]$, then the contiguous subsequence $3, 3, 4, 4, 4, 5$ is $1$-separated but not $0$-separated.

We would like an algorithm that given $A$ and $k$ as input returns the length of the longest contiguous k-separated subsequence.

Some examples:

* Input: $A = \[1, 3, 3, \textbf{4, 4, 4}, 5, 7, 8\]$, $k = 0$. Output: $3$ (longest contiguous $0$-separated subsequence has been hightligthed)
* Input: $A = \[1, \textbf{3, 3, 4, 4, 4, 5}, 7, 8\]$, $k = 1$. Output: $6$ (longest contiguous $1$-separated subsequence has been hightligthed)

This can be solved in $O(n^2)$ with a nested loop that checks all possible contiguous subsequences but we would like to do better.

I understand that I need to split my array in 2, but after that I don't know how to find the condition to select first half or second. How will be the algorithm to find the correct answer? Any help it's welcome.

# Answer
If you want to use a divide-and-conquer algorithm, you can cut the array $A = \[a\_1, …, a\_n\]$ in two arrays by the middle $B = \[a\_1, …, a\_{\frac{n}{2}}\]$ and $C = \[a\_{\frac{n}{2}+1}, …, a\_n\]$.

Then the longest $k$-separated sequence in $A$ is one of the three following:

* the longest $k$-separated sequence in $B$;
* the longest $k$-separated sequence in $C$;
* the concatenation of the longest $k$-separated sequence in $B$ ending with $a\_{\frac{n}{2}}$ with the longest $k$-separated sequence in $C$ beginning with $a\_{\frac{n}{2}+1}$, with the condition $a\_{\frac{n}{2}+1} - a\_{\frac{n}{2}} \leq k$.

Now the first two values can be computed recursively, and the third can be computed easily in time complexity $O(n)$. The complexity of this algorithm verifies $C(n) = 2C\left(\frac{n}{2}\right) + O(n)$, which implies $C(n) = O(n\log n)$.

Without divide-and-conquer, I think there exists a $O(n)$ dynamic programming algorithm:

For $A = \[a\_1, …, a\_n\]$ and $i \in \[\\!\[1, n\]\\!\]$, define:

* $f(i)$: length of the longest $k$-separated sequence in $\[a\_1, …, a\_i\]$;
* $g(i)$: length of the longest $k$-separated sequence in $\[a\_1, …, a\_i\]$ ending with $a\_i$.

Then it is easy to see that:

* $g(i + 1) = \left\\{\begin{array}{rl}1 & \text{if }a\_{i+1}-a\_i \>k\\ 1 + g(i)&\text{otherwise}\end{array}\right.$
* $f(i + 1) = \max(f(i), g(i + 1))$

That way, you can easily compute $f(n)$, which is the value you want, in time complexity $O(n)$.
> 1 votes

---
Tags: algorithms, divide-and-conquer
---


title: Minimal Path Covering

text:
# Question
Title: Minimal Path Covering
Consider a connected undirected graph $G = \langle V, E\rangle$, we say that a subset $C$ of vertices is a Path-Cover if the following holds. For every finite path $p$, it holds that $p$ traverses all the vertices in $C$ iff $p$ traverses all the vertices in $V$. I am interested in finding a Path-Cover of minimal size in polynomial-time, yet all my attempts failed.

I tried a greedy approach where I start with $C = V$, and then I remove a vertex and check whether the graph remains connected. Yet, I'm not sure whether this greedy approach gives a global minimal Path-Cover.

# Answer
This is only my Intuition on the problem, without any proof or explicit algorithm. This might yield an algorithm that can calculate directly the minimal path covering, or at least you might be able to use it to approximately solve the problem.

---

To start out, consider the simplest case: a path graph with $n$ nodes. Clearly, you will need only 2 vertices - both endpoints.

Now, lets take a look at a more complicated (and useful) graph: a cycle with $n$ nodes. The smallest path covering must contain all nodes, since otherwise we can easily construct a path that goes through all nodes except one.

The important bit here, is that we can think of a general graph as a "combination" of such cycles and path graphs (any combination of such graphs with one or more nodes in common).

Basically, an idea behind trying to find the smallest path covering is to identify the cycles and paths. Then, start by "marking" each node at those cycles. Then using the "path graphs" try to identify which nodes you don't have to include (for example, think of two cycles connected by a path. Marking any node in one cycle is the same as marking the "endpoint" of the path graph. So the minimal path covering will mark every node that isnt in the path). Always make sure that both graphs at the endpoints of a path graph are "marked" (a graph is marked if any node in it is marked), as well as any graph connected to a node in a cycle is marked.

This is the basic idea of an algorithm to find which nodes we have to include in the minimal path covering. Try to refine this idea a bit more, and it will give a way to calculate or at least approximate the minimal path covering.
> 2 votes

---
Tags: algorithms, graphs, np-complete
---


# Question
Title: Time Complexity: Does the following problem belong to NP?
> Suppose n people live in a house and wish to share their expenses equally. Their respective expenses (before settling) are x1, ..., xn. They agree to write checks to each other so as to make all their net expenses equal. Naturally, they want to use as few checks as possible.
>
> SETTLEMENT denotes the decision version of this problem: Given nonnegative integers x1, . . . , xn (written in binary) and an integer k, can the net expenses be balanced using k or fewer checks?

I am not sure if I am understanding this problem correctly.. So, given the information, k is a balanced net expense, right? We should find the average net expense of {x1,...,xn}, where x1,...,xn represent the respective expenses. So, SETTLEMENT is as follows:

SETTLEMENT = {(x1,…,xn; k) : there exists some k such that (x1+x2+...+xn) / n = k}.

# Answer
Your interpretation is incorrect. The value of $k$ is not an expense, $k$ is the minimum number of checks needed to make sure that the **net** amount of money paid by each person is $\overline{x} = \frac{1}{n} =\sum\_{i=1}^n x\_i$.

For example if $n=2$, $x\_1=1$, $x\_2=5$ then $\overline{x}=3$ and $k=1$. In particular it suffices from the 1st person to write a check to the 2nd person for an amount of $2$.
> 0 votes

---
Tags: time-complexity
---


title: Bounds on graph partitioning

text:
# Question
Title: Bounds on graph partitioning
I am trying to find some generic upper bounds on the "standard" graph partitioning problem. Say I have a graph with $|V|$ vertices and $|E|$ edges I want to partition it into two equal $N/2$ (or approximately equal if easier) parts while minimizing the cut i.e. $\min(|C|)$ where $C$ is the set of edges with nodes on either side of the partition (similarly nodes that the cut goes through).

So far this is standard stuff and clearly the optimal solution depends on the details of the graph. However, what I want is an upper bound on $\min(|C|)$ in terms of $|V|$ and $|E|$ without knowing anything else about the graph. If no upper bound then even some type of average case estimate would help.

Also, the same thing for a multigraph.

# Answer
This is an area in which I'm not very familiar, but what you are looking for are so-called *expander graphs*.

A graph $G$ has *edge expansion* $$h(G) = \min\_{0 \leq |S| \leq \frac n 2} \frac{|\partial S|}{|S|},$$ where $\partial S$ is the *boundary* of $S$, i.e., the edges with exactly one endpoint in $S$.

This isn't exactly what you ask for, but you can also consider only $S$ of size exactly $\frac n 2$. There are $d$-regular expander graph classes. Perhaps that will point you towards something.
> 1 votes

---
Tags: graphs, partitions
---


# Question
Title: Showing that a problem in $NP$ admits two distinct verifiers that satisfy additional constraints
Show that any $S \in NP$ has 2 different polynomial-time verifiers $V\_1, V\_2$ such that, for all $x,y$, the following conditions hold:

1. If $V\_1(x,y)=1$ then $V\_2(x,y)=0$
2. If $V\_2(x,y)=1$ then $V\_1(x,y)=0$

I show a guideline that say to define $V\_i(x,y)=1$ if $y=p(|x|)+i$ and there exists a prefix $y'$ of $y$ such that $V(x,y')=1$ but I'm confuse to find how it help to find the solution.

# Answer
Since $S \in \mathsf{NP}$, there is a non-deterministic poly-time Turing machine $T^\*$ that decides $S$. Given $x \in S$, let $y^\* = \langle y^\*\_1, y^\*\_2, \dots\rangle \in \\{0,1\\}^\*$ be the list of non-deterministic choices of $T^\*$ that lead to an accepting state in the execution of $T^\*(x)$.

It is easy to see that $|y^\*| = O(\mathrm{poly}(x))$ and that $y^\*$ is a certificate for the the polynomial-time (deterministic) verifier $V^\*$ that, with input $V^\*(x,y^\*)$, checks that the (unique) computation path of $T^\*(x)$ when the non-deterministic choices are those in $y^\*$ leads to an accepting state.

Define $y\_1 =\langle 0, y^\*\_1, y^\*\_2, \dots \rangle$ and $y\_2 =\langle 1, y^\*\_1, y^\*\_2, \dots \rangle$.

When $y=\langle y\_0, y\_1, y\_2, \dots \rangle$, the verifier $V\_i(x, y)$ behaves as follows: if $y\_0 \neq i-1$, it rejects. Otherwise $V\_i(x, y)$ simulates $V^\*(x, \langle y\_1, y\_2, \dots\rangle)$ and accepts iff $V^\*$ accepts. It is clear that $V\_1$ and $V\_2$ are polynomial-time verifiers for $S$ for the certificates $y\_1$ and $y\_2$, respectively. It remains to show that they satisfy the additional constraints from your question.

Notice that, if $V\_1(x,y)$ accepts, then $y\_0=0$, and hence $V\_2(x,y)$ rejects since $y\_0 = 0 \neq 1 = 2-1$. Similarly, if $V\_2(x,y)$ accepts, then $y\_0=1$, and hence $V\_1(x,y)$ rejects since $y\_0 = 1 \neq 0 = 1-1$.
> 1 votes

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


# Question
Title: Where does 1.3606 approximation ratio come from for vertex cover approximation?
I was watching a coursera video on Approximation algorithms and I understood the 2-approximation algorithm.

Later, the professor asks if we can do any better. The lecturer went on to say that computing `1.3606` approximation is NP-hard in the following words at 8:14.

Here's the transcript for that part.

> Actually, what is also interesting to note is that okay, maybe we still have some hope that we can get a little bit below two for the approximation ratio, but as the second staple that you see here shows is that it's not possible to get really close to one, but it's impossible to get something better than roughly 1.3, because already computing a 1.36 approximation as you see here, already that problem is NP-hard.

1. How does he skip from *nobody found a 1.99-approximation algorithm* to getting `1.3606` is NP-Hard?
2. Where does `1.3606` come from?

# Answer
The fact that nobody found a $1.99$ approximation doesn't necessarily mean that the problem of finding one is $\mathsf{NP}$-hard (e.g., it might be the case that that $\mathsf{P} \neq \mathsf{NP}$ and a polynomial-time $1.99$-approximation algorithm exists, we are just unaware of it).

Additionally, we can prove that finding a $1.3606$-approximation is a $\mathsf{NP}$-hard problem, i.e., if $\mathsf{P} \neq \mathsf{NP}$ no $1.3606$-approximation algorithm exists. This is not a direct consequence of the previous fact, but a separate result by Irit Dinur and Samuel Safra. The details can be found here.
> 4 votes

---
Tags: approximation, vertex-cover
---


# Question
Title: Expected behavior of an algorithm to minimize rankings
Suppose $n$ students have preferences over $n$ different notebooks. Their preferences can be represented with a square matrix of size $n$ where each column is a different permutation of the vector $\[1:n\]$, where the first entry in the column represents the most desirable notebook for student 1, and so on. We are interested in the assignment of the notebooks to students that minimizes the sum of rankings.

For example, such allocation in the problem below

```
  1    2    2
  2    1    3
  3    3    1

```

would be the allocation (1,2,3) with a ranking sum of 1+1+2=4.

My two questions are the following. If the matrix with preferences is chosen uniformly at random, what is the expected sum of rankings in the assignment that minimizes the sum of rankings?

Second, I can answer this question by running a simulation, but is there a known algorithm that efficiently finds the allocation that minimizes the sum of rankings?

Idea: In the best-case scenario, this sum is $n$. In the worst-case scenario, where each column is identical, the sum is $n(n+1)/2$. The expectation over all possible cases must be somewhere in between.

# Answer
> 4 votes
Finding the minimum matching is known as the assignment problem, and it has efficient solutions.

Your exact problem has been considered by Parviainen, Random assignment with integer costs — it's his "Case I". Parviainen showed that the expected value is between $\frac{\pi^2}{6} n$ and $2n$, and his simulation results suggest an intermediate value $cn$, where $c \approx 1.830$. See also the survey by Krochmal and Pardalos, Random assignment problems.

---
Tags: graphs, greedy-algorithms
---


# Question
Title: Are disjoint edges the same as matchings?
I am reading *Chapter 9 Approximation Algorithms* of Dasgupts et al.'s *Algorithm* book for vertex cover approximation and they bring up the concept of **matchings**.

To support this, I am also watching Coursera's *Approximation algorithms* course by EIT digital.

This video mentions using **disjoint edges** and would like to confirm that the **2** are actually the same and I am not missing and subtle details.

# Answer
> 2 votes
Two disjoint edges $(a,b)$ and $(c,d)$ are edges that do not share any endpoint, i.e., $\\{a,b\\} \cap \\{c,d\\} = \emptyset$. A matching is a set of *pairwise* disjoint edges.

---
Tags: approximation, vertex-cover
---


# Question
Title: A visitor at a political convention with n delegates
So I have been asked to specifically construct a divide and conquer algorithm for the question:

"You are a visitor at a political convention with n delegates; each delegate is a member of exactly one political party. It is impossible to tell which political party any delegate belongs to; in particular, you will be summarily ejected from the convention if you ask. However,you can determine whether any pair of delegates belong to the same party or not simply by introducing them to each other—members of the same party always greet each other with smiles and friendly handshakes; members of different parties always greet each other with angry stares and insults.

Suppose more than half of the delegates belong to the same political party. Describe an efficient algorithm that identifies all members of this majority party. How many introductions do you need?

So I came up with the pseudocode:

```
AMajorityPolitician(set of politicians S):

 if |S| == 1 :
  return S
 L = AMajorityPolitician(half of S)
 R = AMajorityPolitician(other half of S)

 if party[first item in L] == party[first item in R]:
  return L U R
 else
  return max(|L|,|R|)

AllMajorityPolititians(set S of n politicians):

 M = AMajorityPolitician(S)

 first = first item of M

 ans = {first}
 for each p in S:
   if first smiles to p:
     ans = ans U {p}

 return ans

```

But I don't think this works because if I have a list of politicians parties such as: 2,2,1,1,1 and it is split s.t. L=2,2,1 and R=1,1 then majority of L is party 2 of size 2 and majority of R is party 1 of size 2 so algorithm could pick 2 as the majority.

But I don't really know where to go from here to fix it. Do you guys have any suggestions?

# Answer
> 0 votes
You need to make sure what is returned from `AMajorityPolitician(set of politicians S)` is indeed a politician from the majority in `S` if there is a majority.

To ensure majority, we need to count the number of politicians who are in the same party as the chosen one. Here is the simple routine.

```
def number_of_friendly_politicians(person, all_people):
    count = 0
    for p in all_people:
        if smiles_between(person, p):
            count ++;
    return count

```

Now refactor `AMajorityPolitician` to the following function, which returns a majority politician in `politicians` whenever there is a majority.

```
def a_majority_politician(politicians):
    if size(politician) is 1:
        return that person

    L = a_majority_politician(half of politicians)
    R = a_majority_politician(other half of politicians)

    if number_of_friendly_politicians(L, politicians) * 2 > size(politicians):
       return L
    else:
       return R    # R may or may not in a majority.

```

---
Tags: algorithms, algorithm-analysis, divide-and-conquer
---


# Question
Title: Primes not dividing sequence $a_{n+1} = 1 + a_0 a_1 \cdots a_n$
> Prove that there are infinitely many primes that divide none of the elements of the integer sequence $a\_{n+1} =1+a\_0 a\_1 \cdots a\_n$, with a starting point of $a\_0 \geq 0$.

I thought about $$\log (x\_n-1)=\log x\_0x\_1\cdots x\_{n-1}= \log x\_0 + \log x\_1 +\cdots+\log x\_{n-1} $$ to solve the problem but couldn't.

# Answer
> 3 votes
Let me write it here, because I had a typo in the comment.

First observe that $$ \begin{align} a\_{n+2}&=1+a\_0a\_1\dotsm a\_na\_{n+1}\\ &=1+a\_0a\_1\dotsm a\_n(1+a\_0a\_1\dotsm a\_n) \end{align}$$

So $$4a\_{n+2}=(2a\_0a\_1\dotsm a\_n+1)^2+3$$

This implies that for an odd prime $p$ that divides $a\_{n+2}$, we must have that $-3$ is a quadratic residue modulo $p$. By quadratic reciprocity, $-3$ is a quadratic residue modulo $p$, when $p$ itself is a quadratic residue modulo $3$. Therefore, any odd prime of the form $3K+2$, with $K\in\mathbb{Z}$ doesn't have $-3$ as quadratic residue and cannot divide $4a\_{n+2}$ for any $n\geq0$.

Since there are infinitely many primes of the form $3K+2$ (see here for example), then an infinite collection of primes that don't divide any of the elements of the sequence are the primes of the form $3K+2$, excluding from them $2$, the primes that divide $a\_0$ and the primes that divide $a\_1$.

# Answer
> 1 votes
Suppose that $a\_1 \cdots a\_m \equiv 1 \pmod{p}$ for some prime $p$, which in particular implies that $p$ doesn't divide $a\_1,\ldots,a\_m$. We claim that $a\_i \equiv a\_{i \bmod m} \pmod{p}$ for $i \> 0$, where the modulo returns an answer in the range $1,\ldots,m$. We prove this by induction. This is clear when $i \leq m$. Now suppose it holds for all $j \< i$. Let $i-1 = dm + r$, where $0 \leq r \< m$. Then modulo $p$, \begin{align} a\_i &= 1 + a\_0 \cdots a\_{i-1} \\ &\equiv 1 + a\_0 (a\_1 \cdots a\_m)^d a\_1 \cdots a\_r \\ &\equiv 1 + a\_0 a\_1 \cdots a\_r \\ &=a\_{r+1}. \end{align}

It follows that if $p$ doesn't divide $a\_0$, then it doesn't divide any element in the sequence.

It thus suffices to show that there are infinitely many primes that occur as factors of $a\_1 \cdots a\_m - 1$ (only finitely many can divide $a\_0$).

---

Let us now assume that $a\_0 = 1$, and so $a\_1 = 2$. If $p$ is any prime divisor of $a\_1 \cdots a\_m - 1$ then $a\_1 \cdots a\_{km+1} \equiv a\_1 \not\equiv 1 \pmod{p}$, since no prime can divide $a\_1 - 1 = 1$.

In particular, this implies that a prime divisor of $a\_1 \cdots a\_{a\_j} - 1$ cannot be a prime divisor of $a\_1 \cdots a\_{a\_{j+1}} - 1$. It follows that there are infinitely many primes that occur as factors of $a\_1 \cdots a\_m - 1$.

I'm not quite sure how to handle larger $a\_0$ at the moment.

# Answer
> 0 votes
We can prove that $x^2+x+1$ doesn't have any prime divisor of the form $3n-1$ and $x\_{n+1}=1+x\_0x\_1...x\_n$ so $x\_{n+1} = 1 +A$ then $x\_{n+2} = A^2+A+1$ and we are done because there are infinitely many $3n-1$ primes

---
Tags: discrete-mathematics, number-theory
---


# Question
Title: How to prove NP-completeness of this mail-problem?
Let's say we have **n** postmen that are bringing people mail in a neighbourhood, and that they start and end at the same post office. This situation can be decribed with a directed graph, where the vertices represent the people's houses the mails are brought to. If the graph has an edge from **a** to **b**, it means it is an accepted path to travel. Each postman must go from one house **a** to the next house **b** and cannot detour to a house **c** during that time. The post office manager says that a yes instance to this problem means that there exist **n** cycles so that

1. Each of the cycles contains a vertex **x** (represents the post office).
2. Every vertex except for **x** only appears once in each **n** cycle.
3. Each **n** cycle is of equal length.

**The manager then wonders how to prove that this problem containing 3 cycles (3 equals n, so there are 3 postmen in this case) is a NP-complete problem?**

Thank you.

# Answer
Given an instance of partition $X=\\{x\_1, x\_2, \dots, x\_n\\}$ you can build the graph $G=(V,E)$ where $V=\\{0, 1, \dots, n\\}$ and, for any pair of indices $i$, $j$ with $0 \le i\<j \le n$, there is an edge $(i,j) \in E$ of weight $x\_i$. Additionally, $E$ contains all edges $(i,0)$ for $1 \le i \le n$ with weight $0$.

The deposit will be vertex $0$. If you are able to find two cycles $C\_1$, $C\_2$ of the same length then the sets $\\{x\_i : i \ge 1 \wedge i \in C\_1\\}$ and $\\{x\_i : i \ge 1 \wedge i \in C\_2\\}$ will be a partition of $X$. Similarly, a partition of $X$ induces two cycles of the same length in $G$.

This shows that the problem is $\mathsf{NP}$-hard even with just $2$ postmen. You can generalize this reduction to any number $k$ of cycles by adding $k-2$ additional vertices $y\_1, \dots, y\_{k-2}$ along with all edges $(0, y\_i)$ of weight $\frac{1}{2}\sum\_{i=1}^n x\_i$ and $(y\_i, 0)$ of weight $0$.
> 1 votes

---
Tags: np-complete, np-hard, np, polynomial-time
---