# Question
Title: Is it possible to divide a string, according to pumping lemma, from a language in a way that pumping a section would render the language -non regular
I understand that pumping lemma can only be used to prove that a certain language is "non-regular", it cannot be used for proving regularity

But since, it's a property of regular language, we should be able to pick up a language that is regular, literally, and then see if this property exists in that language, which should def exist

Let's say our alphabet is { 0, 1 }

Our language L = { w | such that w ends in 11 } or in the form of regex it would be ( 0 + 1 )\* 11 ~ basically any string that ends in 11 over the given alphabet

Now, since this is a regular language, if we were to pick up a string that is atleast as large as "number of states" (p) then we should be able to divide the string

Since, a string, atleast as long as 'p', in our mentioned language can be of different forms such as $0^p11$ or $1^p11$ or $(0 + 1)^p11$. Obviously, in the case of proving a language is non regular we just need to show that atleast 1 string fails to adhere to pumping lemma. But in here we are just trying to verify that a certain regular language has the pumping lemma, so in our case all the strings should be in language according to pumping lemma

Now, pumping lemma says that if the language is regular, in our case it is literally a regular language. Then, we should be able to divide a string that is atleast as large as p as follows:

1. $s = xy^iz, where \ i\>=0$
2. $|y| \> 0$
3. $|xy| \<= p$

So, let's assume our string is as follows $s = (01)^{p-2}1$, which is atleast length $p$ and $s$ can be divided as follows: $x= empty \ string \\ y = (01)^{p-2} \\ z = 1$

We can see that the way divided the string in language agrees to condition 2 and 3 but fails to adhere to condition 1:

$s = (01)^{p-2}1 \\ s = xyz \\ s=((01)^{p-2})^{i}1 \\ Now \ we \ will \ try \ to \ pump \ the \ string \ and \ check \ if \ it \ satisfies \ condition \ 1 \\ Put \ i = 0, s = 1\\ $

Hence, s = 1, when we put i = 0, But according to pummping lemma if a languge is regular, which it literally is in our case, then we should just be able to pump the string any number of times even remove that section and still our string should belong to our language

So, if our original laugnage was regular, why did the division and pumping of string failed?

Or is it that i am dividing the string in a wrong way? Like since i do $(01)^{p-2}$ that implies our string has $p-2$ concatenations of $01$, so in order to atleast have a string that is as large as p ~ i need to have 2 more $01$?

In that case since we need to have we can divide the string as follows:

$x = empty \ string \\ y = (01)^{p-2} \\ z = 010111 \ ( because \ we \ need \ the \ prefix \ 11 \ too ) \\ \\ or \ we \ can \ divide \ as \ follows \\ x = 01 \\ y = (01)^{p-2} \\ z = 0111 \\ \\ or \ we \ can \ divide \ as \ follows: \\ x = 0101 \\ y = (01) ^{p-2} \\ z = 11$

And as we can see, in either case of division ~ we do end up having each string in our language. Hence, we can conclude that regular langauges does adhere to a property called "pumping lemma" ( because pumping lemma exists because of regular languages )

Which is it? Was I dividing the string wrong? or is my former logic of string dividing actually correct?

# Answer
The pumping lemma states that **THERE EXISTS** a decomposition $s = xyz$ verifying the 3 conditions. Not that the 3 conditions holds for all decompositions $s = xyz$.

That means that you cannot choose the decomposition yourself, you just know that there exists one.
> 0 votes

# Answer
There are two things that I think is wrong with your example, hence your argument. First the string $s = (01)^{p-1}1$ *may not* always produce a string from $L = \\{ s | \text{ such that } s \text{ ends in 11} \\}$ since in the statement for the pumping lemma, $p \ge 1$. So in your case if $p = 1$ then $s$ is just $1$.

Say we fix that and set $s=(01)^p1$. The second mistake that you have is to assign to $y = (01)^p$. Note that the length of $(01)^p$ is $2p$ and not $p$ thus the way you divide $s$ violates the condition that $|xy| \le p$. With this, please note no matter how you divide $s = (01)^p1$, substring $z$ will always have the form $(01)^q1$ where $\lceil p/2 \rceil \le q \le p - 1 $. Therefore, all possible division of $s$ that satisfies the 3 conditions of the pumping lemma will always produce a string that when pumped is in $L$.

If we did not fix your string such that $s$ is still $(01)^{p-1}1$, the argument I have on the preceding paragraph still holds, albeit you have to change the possible value of $q$.

However, as already stated in the previous answer, it is not required for all subdivision of a string that satisfies the 3 conditions to produce a string that when pumped is in $L$. But that does not mean that the language is not regular. Consider again your example regular language, but this time let $s = 1^p1$. Notice that you can now let $x=\varepsilon$, $y = 1^p$ and $z = 1$. Now if you pump it down, $xy^0z$, then the resulting string is just $1 \notin L$. But there exists a subdivision that will: $x=\varepsilon$, $y = 1^{p-1}$, $z = 11$. Every string in $L$ would be like this - there will be a way (not necessarily all way) to subdivide and pump that will generate a string that is in $L$, since $L$ is regular.

The way you use the lemma, as already pointed in the link you commented in the previous answer, to prove that a language $L'$ is not regular, is that you give a string $s \in L'$ and show that all subdivision of $s$ that follows the 3 conditions of the pumping lemma will result to as string not in $L'$.
> 0 votes

# Answer
Look at how the pumping lemma is proven.

If L is regular then it has a state machine with k states for some k. If you process a string with k or more symbols, then after processing k symbols, you have visited the start state and k further states, k+1 in total. Since there are only k states, two of these must be the same. Do you have run in a cycle.

Instead of 1 cycle, you could repeat the corresponding symbols 0, 2, 3, 4 or more times, and loop through the cycle 0, 2, 3, 4 or more times. And no matter how often you repeat, you get a string in L.

So you can’t split just any way. You have to split s = xyz so that y is exactly the string going from the start of the cycle back to the start of the cycle.
> 0 votes

---
Tags: finite-automata, pumping-lemma
---


# Question
Title: Is there an SMT/SAT algorithm for General Predicate Logic (FOL)?
I'm learning how to write my own theorem prover. After skimming Decision Procedures (Kroening & Strichman, 2016), I didn't find any SMT algorithms for solving quantified n-ary predicate formulas. I realize that some quantified predicate formulas with an arity above 2 are undecidable. But I'm not sure if all of them are provably undecidable. If they are not provably undecidable, then is there an SMT algorithm that can solve quantified n-ary predicate formulas even if sometimes the procedure will not terminate?

Note that for my use case, I'm restricting the model to a finite domain if that helps at all. Yes I'm aware of Trakhtenbrot's theorem.

**Sources**:

1. Kroening, D., & Strichman, O. (2016). Decision procedures an algorithmic point of view. Springer.

# Answer
> 0 votes
You ask two questions. I start by answering your first question.

Undecidability is a worst-case property, which says there is no single algorithm that can work for all problem instances. But some problem instances are, intuitively, "easier". There are problem instances that can be solved. For instance, if you only have a single instance you want to solve, you can write down an algorithm that correctly solves that one instance (it hardcodes the correct answer to that one instance in its source code).

So, in general, it makes no sense to talk about the hardness of a single problem instance -- at least, this is not something we can formalize with the mathematical machinery of undecidability. Rather, we have to talk about the hardness (decidability) of entire classes of problem instances.

Yes, there is an algorithm that can sometimes solve such instances. For instance, you could create an algorithm that hardcodes the correct answer to one instance (input) in its source code, and loops forever on all other inputs. This is correct from a theoretical perspective, but unlikely to be useful in practice.

So, I suspect you are asking from a more pragmatic perspective: I suspect you are hoping for an algorithm that is often successful on many inputs, but is not guaranteed to terminate. Unfortunately I don't know the answer to that. Sorry.

---
Tags: satisfiability, automated-theorem-proving, smt-solvers
---


# Question
Title: SLR parse table construction for left recursive grammar
I have this grammar:

```
E -> E + T
E -> T
T -> T * F
T -> F
F -> ( E )
F -> id

```

And this is the state diagram for it:

I tried to construct a parse table and I am getting shift/reduce conflict. More specifically in state 2 I can shift `*`. Also, FOLLOW(LHS) = FOLLOW(T) contains `*` so I can also reduce using rule 2. Hence shift/reduce conflict.

Am I right?

# Answer
No, you're not right.

State 4 contains the item $E\to\cdot T$. After a GOTO on T, that should produce a state with item $E\to T\cdot$. But the destination state (S2) contains the item $T\to T\cdot$. That's a simple transcription error.

Now, `*` is in FOLLOW(T), but it's not in FOLLOW(E), which is what the item should have included. So the conflict is also a result of the same transcription error.
> 1 votes

---
Tags: parsers
---


# Question
Title: Is there a standard name for the complexity class "embarassingly parallel"
So i'm defining the embarassingly parallel complexity class as the set of decision problems which can be solved in time $O(T(n))$ on a single computer and in time $O(T(n)/g(n))+O(\log(g(n))$ if you have access to $O(g(n))$ machines where $g(n)$ can be of a total size up to $T(n)$.

So these are the types of problems, which might be very expensive to solve (or simple), but you can compute them arbitrarily quickly using arbitrarily many processors (and basically unlimited space).

This is a considerably different class than $NC$ in that $NC$ is a subset of $P$ but the class "embarassingly parallel" is not obviously limited to any runtime (and might include extremely complex problems).

I am guessing this sort of class has been considered before. Does anyone know what the standard name of this complexity class/a related one is?

# Answer
There is no complexity class for this, at least none of which I am aware of. Anyway, I would not define embarassingly parallel computations like this: basically, your second term $O(log(g(n))$ does not exist for embarassingly parallel computations. Indeed, by definition, if the computation is embarassingly parallel, then there is no communication overhead in the message-passing setting (or synchronization overhead in the shared-memory setting).
> 1 votes

---
Tags: complexity-theory, complexity-classes
---


# Question
Title: Single tape TM that converts numbers from binary notation to unary
I need to construct a TM that converts a number from binary notation to unary and calculate time complexity.

I have done the first part.

The idea is as follows:

> binary number is decremented by 1 until it reaches 0. At each decrement an additional 1 is written on the left side.

e.g.

> 111 -\> 1111111 111x (TM goes to the end of the binary number and writes x)
> 110x1
> 101x11
> 100x111
> 011x1111
> 010x11111
> 001x111111
> 000x1111111
> 1111111 (TM removes zeros and x; end)

And now comes the time complexity part. So far I have:
(1) TM will do $n$ (length of the binary number) steps to reach the end of the input word, additional 1 for writing x and 1 for moving back, so $n+2$;
(2) there are $2^{n}-1$ decrements, at that time TM will take in total $2 \times \frac{(2^{n}-1) (2^{n})}{2}$ steps on the left side, plus $2\times (2^{n}-1)$ for the x's. (no idea how many on the right side).
(3) TM will take $2n+1$ steps for removing unnecessary zeros and x at the end.

I don't know how to put this all together, plus some missing information in (2). Can anyone tell me if I'm computing correctly and how to proceed.

Any help will be much appreciated.

# Answer
> 0 votes
As you have said, there are $2^n-1$ total "decrements". Notice that at the $k$'th decrement, you "waste" $O(n)$ time on the left side, plus $O(k)$ at the right side. Sum everything up, from $k=1$ up to $k=2^n-1$:

$\sum\_{k=1}^{2^n-1} n+k = n(2^n-1)+\sum\_{k=1}^{2^n-1} k = n(2^n-1) + O(2^{2n})=O(2^{2n})$

# Answer
> 1 votes
put this code into https://turingmachine.io/

```
name: Binary to Decimal
source code: |
  input: '100#'
  blank: ' '
  B : ' '
  start state : Right
  table:
    Right :
      [0,1] : R
      '#' : {L : q0}
    q0:
      0 : {write : 1, L}
      1 : {write : 0, R : q1}
      ' ' : {R : clear}
    q1:
      [0,1] : R
      '#' : {R : q2}
    q2 :
      ' ' : {write : 1, L : q3}
      1 : R
      '#' : {L : q3}
    q3:
      1 : L
      '#' : {L : q0}
    clear :
      1 : {write : ' ', R}
positions:
  Right: {x: 123.15, y: 317.95}
  q0: {x: 158.84, y: 165.35}
  q1: {x: 339.94, y: 121.45}
  q2: {x: 477.32, y: 257.12}
  q3: {x: 353.45, y: 344.81}
  clear: {x: 34.35, y: 168.07}

```

---
Tags: turing-machines, time-complexity
---


# Question
Title: K in SKI combinator calculus: why doesn't it take one parameter since it ignores its second?
In the SKI combinator calculus, Kxy returns the constant function which always returns x. Since y is always ignored, why not just define K as having a single parameter, namely, x? What is the purpose of having a variable y which is guaranteed to be ignored by K? I'm guessing that there would be some deleterious effect on the system if one were to omit y from the definition of K, but I can't figure out what that would be.

EDIT: For example, one can define K in terms of a simpler combinator, like, say:

$Jx := () \implies x$ (in JS anonymous function style). I.e., $J$ returns a thunk of $x$ just like $K$ does, but without the vestigial second parameter.

Then define $Kxy := Jx$. At that point the $SKI$ calculus is just the $SJ$ calculus since $K$ can be retrieved from $J$ and $I$ is definable in terms of $S$ and $K$.

# Answer
Maybe it would help to think about it comparing to functions:

$K$ can be interpreted as the function with two arguments that returns the first. In Python, it would be

```
def K(x, y):
    return x

```

$I$ is the identity function. It can be written as:

```
def I(x):
    return x

```

Are those Python functions equivalent? No. To prove that the existence of $K$ is necessary, you can actually prove that $I$ can be expressed with only $S$ and $K$, but not the converse : $I = SKx$. Indeed, $SKxy = Ky(xy) = y = Iy$.

From a mathematical point of view: you need projections to do some computations. I am sure that you agree that working with multiple arguments. However, you sometimes need to only keep some of them. This is the same reason one of the basic operations of general recursive functions is the projection. In SK-calculus, you can use the $S$ rule to do a projection on a different argument.
> 1 votes

---
Tags: logic, combinatory-logic
---


# Question
Title: Function / Algorithm that take fixed time to compute
I was wondering if there are any mathematical functions or algorithms that take a known minimum amount of time to calculate. The closest thing I could find to this is Proof of Work algorithms used for blockchain, but the speed at which hashes for these are calculated is affected by device hardware. I'm interested to know if there is any research into this? A function that would always take 100 ms to get the answer to for example?

Excluding sleep functions of course which rely on device clock. I need something this is completely device agnostic.

# Answer
> 2 votes
Here is an example: When you unlock an iPhone, you enter a passcode, and the passcode needs to be checked. That takes exactly 80ms, no matter how fast your phone is. Why?

To check the passcode, the passcode is hashed n times, and then the hashed passcode isn't just checked, but used to decrypt a key, and if the passcode is not right, then you figure out very quickly that the decrypted key doesn't work (so nothing is ever stored that you can use). The number n is determined when you create the passcode, and it is set just large enough that n rounds of hashing take 80ms *on your phone*.

What if you run it on faster hardware? It doesn't work. The hardware itself is part of the hashing algorithm. It doesn't work on an identical iPhone, because the CPUs are not identical. And it doesn't work on some supercomputer with a few thousand cores, because it doesn't work without the CPU in your phone.

The 80ms is chosen so that a normal user doesn't notice it at all, but a hacker who somehow convinces your phone to try all passcodes, one after the other, is stack at the 80ms per passcode limit.

# Answer
> 1 votes
If I understand what you are asking, I don't believe this is likely to be possible. It is possible you might be interested in timelock puzzles, which address some of the issues you raise with proof-of-work and computational puzzles. If you are looking for a purely computational solution, that is as close as you can reasonably get. See https://security.stackexchange.com/q/89094/971, https://crypto.stackexchange.com/q/606/351.

Alternatively, if you don't need a purely computational/algorithmic solution, then you can use trusted hardware, perhaps combined with a trusted time service.

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


# Question
Title: Is the traveling salesman on a map NP-hard?
It is known that the general traveling salesman problem is NP-hard. Even when the distances follow the triangle inequality. But let's take the problem very literally. There are actual cities (points) on a 2-d euclidean space and a tour must be devised to visit all of them in the smallest total distance. We are given the $x$ and $y$ coordinates of each city and the distances between them are the euclidean distances. Is this simplified problem also NP-hard?

# Answer
> 2 votes
This is called the Geometric Traveling Salesman problem. It was proved to be NP-complete by Garey, Graham and Johnson in 1976 and Papadimitriou in 1977.

Source: *Computers and Intractability* (Garey and Johnson)

---
Tags: np, graph-traversal, traveling-salesman
---


# Question
Title: Is there any reason why you cannot use flash memory for a hard disk?
Is there a reason why you cannot use flash memory as a HD? Less moving parts and more affordable. Whats not to like?

Why dont we see Pci-express cards with a couple of terrabytes of flash memory that you can use as a HD?

# Answer
> 3 votes
The first flash disk was introduced in 1987. That's 36 years ago.

https://en.wikipedia.org/wiki/Solid-state\_drive#Flash-based\_SSDs

So, no, there is no reason.

---
Tags: memory-hardware
---


# Question
Title: $L_1= (1$ { $0, 1$ }$^∗) \cup ${ $0x | x \in L$} is NP- complete
If L is NP-complete then how can I prove that $L\_1$:

$L\_1= (1$ { $0, 1$ }$^∗) \cup ${ $0x | x \in L$}

is also NP- complete.

My thoughts: A reduction from (for example) SAT to L can be converted to a reduction to { $0x | x \in L$} by adding a 0 to the output.

# Answer
There is a somewhat trivial reduction from $L$ to $L\_1$

Consider $x\in \Sigma^\*$. Then $x\in L \Leftrightarrow 0x\in L\_1$. Clearly this reduction is polynomial.

I am sure that you can prove that $L\_1\in \mathsf{NP}$.
> 0 votes

---
Tags: np-complete, reductions, np
---


# Question
Title: Is a language semi-decidable iff it is reducible to ATM?
Thank you. I see how it makes sense going in the opposite direction but i need help proving that this is true.

Below is the definition of ATM.

ATM={\<M,w\>| a TM, M accepts w}

The question from my understanding is that a language needs to be reducible to ATM for it to be considered semi-decidable. What I've tried to do is just understand that if a language is semi-decidable , then it must be reducible to another semi-decidable machine including ATM.

The key challenge I face here is how do I prove that? One thought I had is to disprove it by going the opposite way because ATM is also undecidable, meaning if ATM is also undecidable, the languages that it reduces to can also be undecidable and not semi-decidable.

However, the question is asking to prove why the original statement is true? I can't see a proof that goes both direction to prove that it is true.

Thank you.

# Answer
> 0 votes
The proof contains two main statements:

1. prove that $RE$ (the set of all semi-decidable languages) is closed under $\le\_{m}$ reduction (many-one reduction). It means that if we have a reduction $L\_{1} \le\_{m} L\_{2}$ and $L\_{2} \in RE$, then $L\_{1} \in RE$. (**hint**: construct a recognizer for $L\_{1}$ using TM for a reduction function and a recognizer for $L\_{2}$, the easier part)
2. prove that $A\_{TM}$ (or ATM) is $RE$-complete problem (wiki)(the harder part). (**hint**: it's much easier to use the fact that $HALT$ is $RE$-complete, but the direct proof isn't so hard too).

Options 1 (when $L\_{2} = A\_{TM}$) and 2 will give to you **iff** in your statement.

# Answer
> -2 votes
It shouldn't be possible as introducing ATM/an ATM decider to the TM decider of your problem should introduce a contradiction to the decider. I am not an expert in decidablity, but it seems that this paper http://www.cs.toronto.edu/~ashe/comp.pdf from the University of Toronto has a good paper on this proof. It might be better to understand their paper as I could be losing things in translation.

---
Tags: reductions, decision-problem, semi-decidability
---


# Question
Title: In a directed acyclic graph, what do you call the nodes with in-degree zero?
The question is in the title. What do you call "root nodes" in directed graphs. Is there a commonly accepted term? "Root" implies there's only one, which is not the case. I've scanned half a dozen glossaries before asking. I'm starting to suspect that no, there's no agreed moniker.

# Answer
> 15 votes
I believe the common term for that is **source**. While a node with 0 out-degree is called a **sink**.

---
Tags: graphs
---


title: EXACT INDSET is DP-complete

text:
# Question
Title: EXACT INDSET is DP-complete
The class DP is defined as the set of languages L for which there are two languages $L1 \in NP$ , $L2 \in coNP$ such that $L = L1 \cap L2$. (Do not confuse DP with $NP \cap coNP$, which may seem superficially similar.) Show that

(a) EXACT INDSET ∈ DP.

(b) Every language in DP is polynomial-time reducible to EXACT INDSET.

Exercise 8, page 12

Clarifications: EXACT INDSET = {\<G, k\> : the largest independent set in G has size exactly k}.

Thoughts: I know that INDSET is NP-COMPLETE.

# Answer
> 1 votes
Hint: show that $\texttt{EXACT INDSET} = \texttt{INDSET}\cap L$ with: $$L = \\{\langle G, k\rangle \mid G \text{ has no independent set of size }\geqslant k + 1\\}$$ and show that $L$ is $\text{co}\mathsf{NP}$-complete.

---
Tags: np-complete, np, complexity-classes, induction, co-np
---


# Question
Title: Is $L = \{w w^r w | w \in a(b+c)^*a \}$ a context-free language?
Can't understand how to apply pumping lemma to see if a language is context-free or not.

I tried to verify the context-free's pumping lemma, and the language seems to be not context-free but I can't understand if I'm correct. I tried writing all factorizations, but I don't know when I have to stop or if there's a way to understand immediately if it isn't context-free. Is this language context-free?

# Answer
> 0 votes
Assume $L$ is context-free and let $n$ be its pumping length. Let $u = ab^naab^naab^na = (ab^na)^3$. Since $(ab^na)^R = ab^na$, it is clear that $u\in L$. That means, since $|u| \geqslant n$, that the there exists a decomposition $u = vwxyz$ such that:

1. $|wxy|\leqslant n$;
2. $wy\neq \varepsilon$;
3. for $k\geqslant 0$, $vw^kxy^kz\in L$.

* Since a word of $L$ contains exactly $6$ $a$'s, $wy$ contains only $b$'s (otherwise you could pump to get more than $6$ $a$'s).
* If $wxy$ is contained in one of the $3$ sequences of $b$'s in $u$ and you pump it, it will create an imbalance in the number of $b$'s, for example you will get $ab^maab^naab^na$ with $m\>n$, which is clearly not a word of the language.
* That means that $w$ is contained in one sequence, and $y$ in another sequence. But again, pumping it will create a word (for example) $ab^maab^paab^na$ with $m\>n$ and $p \> n$, which is again not in the language.

By contradiction, we can conclude that the language is not context-free.

---
Tags: context-free, pumping-lemma
---


# Question
Title: A kind of generalised assignment problem where we minimise error relative to a goal "weight"/"value" - how to solve it?
I apologize if I did not use the terminology entirely correctly in the title. This problem seems to me quite similar to an assignment problem and likely something that occurs in real life in business.

**The problem**:

* In this problem, we have a set of assets (in the economics/finance sense) $\left\\{ a\_i \right\\} $ with values $\left\\{v\_i\right\\}$ (always positive) respectively, and a set of people $\left\\{p\_j\right\\}$. For each person, we have a (positive) value $\left\\{g\_j\right\\}$ (respectively), which is our goal for the total value we want to assign to this person.
* We can assign multiple assets to a single person but cannot assign an asset to more than one individual or divide an asset in any way. Given such an assignment $f: a\_i \mapsto p\_j$, we can calculate the total value assigned to person $p\_j$, call it $T\_j(f)$, as the sum of the values of all assets assigned to person $p\_j$. We wish to find an assignment $f$ which minimizes $\max\_j(|T\_j(f) - g\_j|)$, i.e., we don't want to have a large error for even a single individual.

I'll describe my questions and then my current attempts/idea.

**Questions**:

1. Does this problem have a name, either with the current objective function I mentioned or maybe minimizing something else, e.g., the sum of absolute errors or squares of errors?
2. The main question is finding an efficient way to solve this. I am looking to solve it with 10 people and 60 assets, i.e., considering $10^{60}$ possible assignments. So a brute-force method will not work.

**My ideas**:

1. my only idea, except for going through all options, is to set some maximum value for that error I mentioned, $\max\_j(|T\_j(f) - g\_j|)$, and this allows to prune the search tree (the search-tree I am thinking of is one where the first level is the assignment of asset $a\_1$ to each of the persons, the second level is the assignment of $a\_2$, etc.) whenever the total value for even a single individual goes above that. This should do a lot of pruning, and I know from experience with my datasets that, in most cases, it is possible to find a solution with a relatively small error (an error of the type I described).

But this pruning method seems not to be that fast/efficient.

# Answer
> 2 votes
The problem you describe is strongly NP-hard since it generalizes the 3-PARTITION problem. Hence you can expect no efficient algorithm for it, unless P = NP.

To see that it generalizes the 3-PARTITION problem, take an instance S of 3-PARTITION that is composed of 3m positive integers summing to mT. Now consider the following instance of your problem: there are m persons, each with a goal of T. There are also 3m assets, one for each positive integer in S, with the corresponding value. Then you can find an assignment with cost zero (that is, meet exactly the goal of each person) if and only if the 3-PARTITION instance has a solution.

---
Tags: algorithms, optimization, combinatorics, assignment-problem
---


# Question
Title: Is there an unsound solution to the halting problem that makes the following functions computable?
I'm interested in this functions

\begin{align\*} g(m) &= \begin{cases} \text{defined} & \text{if turing machine $m$ computes $g$} \\ \text{defined} & \text{if turing machine $m$ loops on $m$} \\ \text{undefined} & \text{otherwise} \\ \end{cases} \end{align\*}

\begin{align\*} f(m,n) &= \begin{cases} \text{defined} & \text{if turing machine $m$ computes $g$} \\ \text{defined} & \text{if turing machine $m$ loops on $n$} \\ \text{undefined} & \text{otherwise} \\ \end{cases} \end{align\*}

and the halting problem \begin{align\*} h(m,n) &= \begin{cases} \text{0} & \text{if turing machine $m$ loops on $n$} \\ \text{1} & \text{otherwise} \\ \end{cases} \end{align\*}

it seems to me that if we have a special unsound solution to the halting problem $h'(m,n)$ we can compute them as follows

\begin{align\*} g(m) &= \begin{cases} \text{halt} & \text{if $h'(m,m)=0$} \\ \text{loop} & \text{otherwise} \\ \end{cases} \end{align\*}

\begin{align\*} f(m,n) &= \begin{cases} \text{halt} & \text{if $h'(m,n)=0$} \\ \text{loop} & \text{otherwise} \\ \end{cases} \end{align\*}

whenever $h'(m,n)$ is wrong $h(m,n)=1$ and $m\equiv g$

can you verify that this is true and do you know how we can find $h'(m,n)$? thanks

# Answer
> 8 votes
I see a repeated pattern here, and I'm unsure how to help. I believe the question is meaningless, so instead of trying to answer an ill-defined question that I don't think can be answered, I'm going to instead try to see if I can offer something to help you achieve better understanding of the topic more broadly. I see that you have repeatedly asked questions on a similar theme, and I'm struggling to identify a single conceptual misunderstanding that I think would help to clear up, so instead I'm going to share a broad range of reactions to this question and your previous questions, in hopes that something is of use to you.

To me, I can't make meaningful sense of those questions. To me, this seems to suggest a lack of a fundamental understanding about the concepts. Yet I am not sure how to help you understand better. It seems like many people have tried, but the ways that we have tried have not been successful, and I am not sure what to say that might help you.

I wonder if it's possible that part of the problem is that you may be starting from some premises and hoping for someone to give you a specific answer, e.g., confirm that your beliefs are accurate, and those premises seem faulty to many of us here.

I suspect that another part of the problem is that you are using non-standard notation and terminology that does not match the ways of communicating about this subject that are accepted in the field. At a surface level, your notation and terminology seems tantalizingly like there might be some meaning there. It has all the surface elements: it defines functions, it uses LaTeX, it typesets variables in italics, it correctly recognizes the concept that a Turing machine can compute a function, it recognizes that variables should be defined before they are first used, it has the structure of providing motivation for the questions you are asking. But when I try to read deeply, I just can't make sense of your writing. This seems to be a pervasive problem across many of your questions. I am not sure how to help when I cannot understand where you are coming from.

It's very hard to get answers to complex technical questions if you won't use the standard, accepted terminology. If you won't use standard, accepted terminology, you force readers to try to learn your terminology or your framework for thinking about the topic, which requires lots of extra effort from readers, so many people will just skip over it. And it requires you to precisely define your notation and terminology, which to date seems like it has been a barrier and has not happened successfully in many of your questions. Non-standard terminology or notation risks having built in some faulty premises that might be hard to diagnose or debug. And finally, even if someone answered you, it is unlikely that such answers would be useful to anyone else in the future, because it's unlikely anyone else will use the same non-standard terminology and notation as you do. Part of our mission is to build up an archive of knowledge that will be useful to others in the future.

So I strongly encourage you to first learn and then use standard notation and terminology. I get the impression you may be struggling to do that. That makes me suspect that your time would probably be better spent studying computability theory from a textbook and working through definitions and proofs and exercises there, and asking about specific exercises you are struggling with, rather than asking these particular questions about your ideas about how to approach the halting problem. I wonder if you're jumping straight to the juicy topic of the halting problem without first working through the foundations. Ultra-marathon runners first have to practice running a few miles at a time, and running marathons, before they can take on an ultra-marathon.

On top of that, the halting problem is one of those problems that seem to attract amateurs who think they have found some insight that everyone else in the field has missed, and if everyone else would just listen to their unique insight, they could correct the widespread misunderstanding that has somehow fooled everyone else. A number of us have had experiences of this sort before, where engaging with these folks was a waste of time for everyone before, and have become weary and wary of doing so again in the future. So people come into this area with some built-in wariness or skepticism. And here you come with a series of questions that seems like it might be fitting that pattern. So you are in a particularly difficult territory.

To me, the notation and definitions in your question make no sense. For instance:

* You can't define a function $g$ in terms of $g$. That's not a meaningful mathematical definition of a function. It's like me trying to define a function by saying that $f(x)$ is one less than $f(x)+1$. That doesn't uniquely specify a function.
* There seems to be a misunderstanding about the difference between a partial function vs a function. Normally, we don't consider "defined" or "undefined" to be outputs of a function.
* I'm not entirely sure what you mean by "loops on". If you mean "enters an infinite loop", what counts as an infinite loop? I'm concerned that $h$ might not correspond to the halting problem. The halting problem is concerned with whether a halting problem halts or not, not whether it "loops". Depending on your definition of "loops", it might be possible for a program to neither loop nor halt. If your definition of "loops" is "doesn't halt", then rather than talking about "loops", you should use standard terminology.
* I don't know what "special unsound solution to the halting problem" means.
* I don't know what "we can compute them" means (it is not clear what "them" refers to).
* There seems to be a failure to distinguish between functions vs algorithms/Turing machines. There also seems to be some inconsistency on whether $g$ is a partial function that is defined or undefined on some inputs, vs whether it is a Turing machine that halts or doesn't halt on some input.
* It's not clear what are the conditions for $h'(m,n)$ to be "wrong".
* It is not clear what the notation $\equiv$ is supposed to represent.

The problems are pervasive enough that I don't think they can be addressed by a simple edit to fix one or two of them. Instead, I have to call into question the approach you are taking. Perhaps what would help you most is more time studying mathematics, so that you have the formal underpinnings relied upon in computability theory? Perhaps your time will be better spent by learning some other subject without trying to resolve your questions about the halting problem?

My advice is that asking questions of this sort is not working: it's not benefiting our mission of building an archive of knowledge, and from where I sit I don't have confidence that it is helping you understand computability theory. So instead of continuing to ask questions about the halting problem (especially your conceptualization of the halting problem), I would suggest that you try to find some other way to learn about the subject: maybe study from a textbook, maybe ask questions about some other subject entirely, maybe study discrete mathematics and mathematical proofs so you have the foundations needed to succeed in this subject. But at least, I don't recommend continuing along the path you've been following so far, as that path seems to be going nowhere.

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


# Question
Title: When applying pumping lemma to prove that a language is not regular, do we need to apply it to all decompositions of a string or just one?
We know according to the pumping lemma if a language is regular, then a string already exists and it can be separated into 3 parts ( called decompositions ), 1 string can have multiple decompositions.

If we were to cross check this property with, basically prove for regular langauges, then we would need to prove it for all such decompositions of a string

But if we were to use the pumping lemma to prove that a language is non regular, then we just need to show for only 1 decomposition of a certain string, that the application of pumping lemma here leads to a contradiction, right?

Even in Michael Sipser's book, 3rd edition, "Introduction to theory of computation" chapter 1 ~ Pumping lemma for regular languages. He just applies pumping lemma to prove non regularity on one such decomposition

But here, and according to the contrapositive statement, we are supposed to apply pumping lemma to all possible decompositions when using it to prove non regularity

So, which is correct?

# Answer
> 1 votes
The decomposition of the input string matches exactly a cycle in the finite state machine used to parse the language.

So you have to either find one suitable decomposition that meets the conditions of the pumping lemma (in that case it is quite likely but not guaranteed the language is regular), or you show no such decomposition exists (in that case the language is not regular).

# Answer
> 0 votes
The Pumping Lemma says that if a language is regular then there is associated with that language a natural number, the pumping length. The point of that length is that for any string in the language at least as long as that length, that string has a decomposition into three substrings, which satisfy the conditions of the lemma. So the short answer is that you look at one decomposition type, not every possible decomposition (for instance, not a decomposition into four parts, or a decomposition into three parts that does not satisfy the conditions).

For example, we can show that $L=\\{a^nb^n| n\in\mathbb{N}\\}$ is not regular. For contradiction, suppose that it is regular. Let its pumping length be $p$. You now need to strategically pick a string longer than $p$. Maybe you say: let $\sigma=a^pb^p$. (So when you say "a string already exists", perhaps this is the point of confusion? Maybe you didn't know that your argument needs to name a particular string in the language?)

Then the Pumping Lemma says that there is a decomposition into three parts, $\sigma=\alpha\beta\gamma$, such that (1) the length of the concatenation $\alpha\beta$ is less than or equal to $p$, and therefore the substring $\alpha$ and the substring $\beta$ consist of only $a$'s since the first $p$-many characters of $\sigma$ are all $a$'s, and (2) the substring $\beta$ is not empty, so it consists of at least one $a$, and (3) all of the strings on this list are also in the language: $\alpha\gamma$, $\alpha\beta\beta\gamma$, $\alpha\beta\beta\beta\gamma$, etc. (That is, we do not look at all possible decompositions of $\sigma$, only this one.)

Now the contradiction is: $\alpha\gamma$ has fewer $a$'s but the same number of $b$'s as $\sigma=\alpha\beta\gamma$. It therefore does not have the same number of $a$'s as $b$'s.

---
Tags: automata, pumping-lemma
---


# Question
Title: Decidable or Not: Set of all Turing Machines M that on input w uses all states of M
Show that the following language or problem is not recursive: $$ L=\\{\langle M,w\rangle\mid \text{computation of TM } M \text{ on input } w \text{ uses all states of } M\\} $$ I was trying to prove it using reduction, but I cannot seem to find a language to reduce it to. I also tried it for the complement of L: $$ \overline{L}=\\{\langle M,w\rangle\mid \text{computation of TM } M \text{ on input }w, \exists q\in Q(M) \text{ such that } q \text{ is not visited}\\} $$ And I still cannot find the solution. How should I approach this problem?

# Answer
> 0 votes
I'm assuming that $M$ is a decider and that by "all states" you are excluding the accepting and rejecting state.

Given a Turing machine $M$, you can build an equivalent Turing machine $M'$ that behaves like $M$ except that $M'$:

* has one additional state $q$ and one additional tape symbol $x$;
* whenever $M$ would accept/reject, $M'$ writes $x$ on the tape, goes through all the states of $M$ plus the additional state $q$, and then halts.

Since $M$ (with input $w$) halts if and only if $M'$ (with input $w$) uses all states, the language of the halting problem reduces to $L$, i.e., $L \not\in \mathsf{R}$.

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


# Question
Title: Self-referential systems cannot predict their future behaviour? (reference request)
Seth Lloyd claims in this video that free will stems from our impossibility of determining how a system capable of self-reference will behave in the future (e.g. whether a human being will have chosen to drink tea or coffee in 5 minutes). He relates this to Gödel's incompleteness theorem in a way that seems completely unjustified, but perhaps I misunderstand his point. Does anyone have a more rigorous reference to the claim that self-referential systems cannot predict their own future behaviour?

# Answer
I'm not going to watch or engage with the video but to answer your question, it is possible for a self-referencing program to make statements about its own behaviour.

Fix an encoding of programs. There is a program with index $e$ that takes another program index as an argument and searches for proofs about the behaviour of the program defined by this index.

Apply the $S^m\_n$ theorem to show that there is a computable-function $s^0\_1$ such that $\varphi\_{s^0\_1(e, n)} \cong \varphi\_e(n)$. This means that when given a program index, we can construct a new program that takes no input and searches for proofs of the behaviour of the program with the index specified.

The recursion theorem tells us that $s^0\_1$ has a fixed point. So there is some $n$ such that $\varphi\_n \cong \varphi\_{s^0\_1(e, n)}$. This means there is a program with index $n$ that computes the same function as a program searching for statements about its own behaviour.

If you're interested, see What are some interesting applications/corollaries of Kleene's Recursion theorem? for more implications of the recursion theorem.

\[1\]: https://mathoverflow.net/a/437912. Joel David Hamkins (accessed 2023-01-5).
> 1 votes

---
Tags: turing-machines, incompleteness
---


# Question
Title: Which definition of decidable is correct?
Please note I don't use any of the "verifier" notation, I only concern definitions made with DTM and NTM .

Now there are two definitions of *decidability*:

**1. A set (predicate) is decidable (solvable) iff exist a machine (DTM/NTM) M(x) that accepts iff x∈A, and rejects iff x∉A. i.e. if it halts correctly against all input.**

Many sources supports this definition, among them the clearest one is on Wikipedia:

> A Turing machine is said to recognize a language (recall that "problem" and "language" are largely synonymous in computability and complexity theory) if it accepts all inputs that are in the language **and is said to decide a language if it additionally rejects all inputs that are not in the language** (certain inputs may cause a Turing machine to run forever, so decidability places the additional constraint over recognizability that the Turing machine must halt on all inputs). **A Turing machine that "solves" a problem is generally meant to mean one that decides the language.**

**2. A set (predicate) is decidable (solvable) iff exist a machine (DTM/NTM) M(x) that accepts iff x∈A i.e. if it halts correctly against all elements with “yes” as output.**

This is posed by Another stackexchange problem, under the user Shitikanth, with 10+ votes.

Now I am genuinely confused. Intuitively I think 1 is correct, as halting problem is obviously decidable against all "YES" input -- you just have to run them and by definition they terminate in finite time, which obviously not making halting problem decidable.

# Answer
#1 looks good, but check a textbook for a formal, precise definition.

None of the sources you mentioned are authoritative sources for this. If you need a correct definition, you should be consulting a textbook, not Internet sources.

A textbook would be an authoritative source for the definitions of decidability. Wikipedia is not a primary source -- it is a summary, with references to where you can read authoritative sources. So, in case of any doubt, go to an authoritative source. For technical matters, Wikipedia is often pretty good, but it's not perfect. A random answer on the Internet is not an authoritative source.

And in this case, for #2, you have not correctly quoted the answer. You left out a key part of the answer (the limit on the number of steps of its execution). I think part of the problem is that the answer you link to in #2 was answering a different question (about polynomial-time algorithms), and gave an answer tailored to that other question. I imagine you tried to adjust what was actually written there to your actual question (by omitting the part of the answer that refers to limits on the number of steps of execution), in hopes that this would give an appropriate version suitable for your question, but your adjustment was faulty and is not the correct way to generalize what they wrote to your situation. In other words, in #2, you've created a self-inflicted problem in the way you tried to modify what you read elsewhere to make it applicable to your situation.

For instance, a Turing machine that halts and accepts for all $x \in A$, but fails to halt for some (or all) $x \notin A$, would not qualify as a valid decider for $A$.
> 1 votes

---
Tags: algorithms, complexity-theory, time-complexity, turing-machines
---


# Question
Title: Efficient algorithm to compute the number of points at the lower left of another point
Consider $N$ points that are located on a 2D plane where the $i$-th point’s location is denoted as $(x\_i, y\_i)$.

Is there any efficient algorithm that can compute $d\_i$ that is defined as the number of points with $x\<x\_i$ and $y\<y\_i$ for all $i$? In other words, we would like to count the number of points on the lower left of point $i$. To simplify, assume there’s no pair of points that have the exact same $x$ and $y$.

By “efficient”, I mean the complexity should be $O(N\log N)$ (in runtime and memory) or better.

EDIT: Adding the specification for the algorithm: The input to the algorithm is a list of the coordinate of the points (not necessarily sorted in any order) and the output will be a list where the $i$-th element is the number of points in the lower left of the $i$-th points.

# Answer
Sort the points from left to right. Then scan from left to right, keeping the points met sorted by ordinate in a balanced search tree.

Now every time you insert a new point, the tree contains all points to its left and by finding the insertion point in the tree you obtain the number of lower points.

These two steps each take time $O(n\log n)$. You cannot do better because the solution to this problem would allow you to sort a list of reals $x\_i$ by processing the points $(x\_i,x\_i)$.
> 2 votes

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


# Question
Title: In data structures, there are many identifiable characteristics, but what are the characteristics are of primitive-data types?
**Data Structure**

> a data structure is a data organization, management, and storage format that is usually chosen for efficient access to data. More precisely, a data structure is a collection of data values, the relationships among them, and the functions or operations that can be applied to the data.

**Language has primitive and non-primitive data types.**

**Primitive**

> In JavaScript, a primitive (primitive value, primitive data type) is data that is not an object and has no methods or properties. There are 7 primitive data types.

> In C language supports four primitive types - char, int, float, void. Primitive types are also known as pre-defined or basic data types.

**Non-Primitive**

> JavaScript non-primitive types are objects. An object holds a reference/address of a single key-value pair or many key-value pairs. Whenever we refer to an object, we refer to an address in memory which contains the key-value pair.

> The non-primitive data structures in C are also known as the derived data structures as they are derived from primitive ones. A large number of values can be stored using the non-primitive data structures.

When we study data structures, we learn to make new data structures with the native data structures (data types) implemented by our language of choice. We would implement functions to add constraints and/or behaviour on non-primitive data structure to hold primitive data as intended.

Sometimes, we implement data structure that cooresponds to a popular abstract data type, like a queue, stack, a tree. These are abstract data types. And if you look at any beginner data structure guide. They say you can commonly identify these data structure with the following characteristics:

For instance you can see Wiki's Queue (abstract data type) quoted for queue: "A queue is an example of a linear data structure, or more abstractly a sequential collection."

Here is my conundrum, a languages primitive and non-primitive data types are all just data structures in and of itself when it was implemented.

if they are just data structures. Then are those characteristics above also applicable to describe these data types? Would this be correct, an int is a data type of C, it is a data structure related to hold the mathematical range of numbers. Behind an interface, the data structure allows users to manipulate the bits that represents numbers. Because bits are lined up in on contiguous memory, it is **linear**. it is **static** for C, but maybe more **dynamic** in Javascript. Identifying whether it is homogenous, may be difficult. But, I would assume it is homogenous, because in each bit, it represent a concept of a number. brute force adding a sequence of bit representing a char to a primitive number would mistaken the purpose of its primitive data structure - and I assume that is often not allowed in higher language.

# Answer
> 1 votes
Primitive data types are predefined entities that the language handles atomically. They have no structure. E.g. a floating-point number.

Data structures are user-defined aggregates created using the primitive data types and the aggregation rules supported by the language. E.g. a list of pairs of integers.

An Abstract Data Type is a data structure that is incompletely specified, i.e. such that some design freedom remains. All that matters is a set of supported operations, regardless how the structure is implemented. E.g. a priority queue.

---

It would be an abuse to say that a primitive data type is a static, linear list of bits, because these are always handled collectively and not in isolation. (By the way, no modern CPU handles single bits, not even as the types boolean nor bitfield.)

# Answer
> 0 votes
I think you're placing more emphasis than is warranted in these "characteristics" (linear, etc.). At best, those are common patterns that might be helpful to recognize. But they are not some fundamental property of data structures, they are fuzzy (not precisely defined), and so you can use them if they are useful and not use them if they are not useful.

I don't think it's useful to try to argue over whether an 'int' should be considered 'linear' or not. The concept of 'linear' isn't precisely enough defined to come to any objective conclusions, and in any case, the answer doesn't really matter. I recommend spending your time and attention on something else. I also recommend learning data structures from a good textbook. Resources on the Internet are of highly varied quality.

# Answer
> 0 votes
It sounds like a very muddled analysis.

"Data structures" are fundamentally a system of *addressing* \- the management of the *placement* of values in a systematic way.

It is not merely a "collection" of data values, but a collection that is ordered or arranged in a particular way. It is no more concerned with the "relationships" amongst values, than the postcoding of domestic premises is concerned with "the relationships between neighbours".

And it is definitely not concerned with the "functions or operations" that can be applied to the data - this is a constraint handled by *data typing*.

The only native data type in the computer as we know it, is the binary "bit". All other types essentially consist of a structured series of bits, handled as a single unit.

And not all types are distinguished by structure. The difference between byte and char, for example, is purely in the nominal type which reflects their different practical usage - their internal structure is completely identical.

To my eye, your description of a "data structure" resembles the definition of an "object" (in the sense of object-oriented programming).

The same is true of your definition of "primitives". Most object-oriented languages have this notion of "non-objects" which they call "primitives".

But in non-OO languages like C, there are no "objects", and "primitives" simply mean the types specified by the language designers as fundamental in their language. These primitives contrast with any composite types defined by the programmer.

The selection of primitives provided by C has more to do with programmer convenience and correspondence with the facilities provided by typical hardware, than with being strictly fundamental in computer science.

---
Tags: data-structures, language-design
---


# Question
Title: When converting DFA/NFA to regular expression, where the DFA/NFA accepted empty string, is it okay to not have empty string as kleene star?
Let's say that we have a DFA, where the initial state was also the accept state. Meaning the DFA accepts the "empty string". Now, let's say that we convert the DFA to regular expression $R$, using Arden's Method ( my prefered method )

Now, the resultant expression looks something like $(R)^\*$, which is obviously capable of representing empty string, implying that the language we are describing also accepts empty string. But is it legal to represent empty string as a "kleene star" or do i have to explicitly mention "empty string" + $R$

My understanding is that, it's okay to represent it as Kleene star

# Answer
If the start state is also a final state, then the empty word **must** be in the interpretation of the regular expression you obtain.

That does not necessarily mean that the regular expression $e$ you obtain is of the form $E = F^\*$, for example, the interpretation of $(a+b)^\*aab(a+b)^\*\mid (ba)^\*$ contains the empty word.

However, if that's not the case, then that means you made a mistake somewhere, no matter the method.

I am not so sure what you mean by 'is it legal to represent empty string as a "kleene star"': if the interpretation of $F$ is not the empty language, then $F^\*$ does not represent only the empty word. However, $\emptyset^\*$ contains only the empty word.
> 1 votes

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


# Question
Title: Does every regular expression describe only 1 language?
If we have a regular expression $R$, will $R$ describe only regular language $L$, but that language $L$ can have multiple different regular expressions such as $Q,W,A,S,D \ etc..$ describing it

Also, $R$ can be equivalent, in terms of describing $L$, to infinite regular expressions including $ Q,W,A,S,D \ etec..$

Is my understanding correct?

# Answer
If $e$ is a regular expression such that $\mathcal{L}(e) = L$, then so is $e+\emptyset$, $e+\emptyset+\emptyset$, …
> 0 votes

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


# Question
Title: Ιf 3SAT reduces to its complement then NP=coNP
Can you please explain to me why the following is true?

Ιf 3SAT reduces to its complement then NP=coNP.

Thoughts: 3SAT is NP-complete so for every X in NP

$X \leq 3SAT$

$\overline {3SAT} $ is NP-complete so for every Y in coNP

$Y \leq \overline {3SAT} $

So, $X \leq 3SAT \leq \overline {3SAT}$

But don't we have to also prove that

$Y \leq 3SAT $?

# Answer
> 1 votes
For $A \in \mathsf{NP}$ you have $ A \le\_p 3SAT \le\_p \overline{3SAT} \in \mathsf{co{\text -}NP}$, which implies $A \in \mathsf{co{\text -}NP}$ and hence $\mathsf{NP} \subseteq \mathsf{co{\text -}NP}$.

Simmetrically, for $A \in \mathsf{co{\text -}NP}$, you have $A \le\_p \overline{3SAT} \le\_p 3SAT \in \mathsf{NP}$, which implies $A \in \mathsf{NP}$ and hence $\mathsf{co{\text -}NP} \subseteq \mathsf{NP}$.

From $\mathsf{NP} \subseteq \mathsf{co{\text -}NP} \subseteq \mathsf{NP}$, it follows that $\mathsf{NP} = \mathsf{co{\text -}NP}$.

# Answer
> 0 votes
Hint 1: $Y\in \text{co}\mathsf{NP}$ if and only if $\overline{Y}\in\mathsf{NP}$.

Hint 2: $A\leqslant B$ if and only if $\overline{A}\leqslant \overline{B}$.

---
Tags: np-complete, reductions, np, complexity-classes, 3-sat
---


# Question
Title: How to use the Pumping Lemma to show that a language is not context free?
I have the following alphabet $\Sigma = \\{0,\dots,9\\}$ and the following language over $\Sigma \cup \\{\\#\\}$: $$L=\\{\\#w \ |\ w \in\Sigma^\*,\sum\_{i\geq1}w\_i\ \text{is prime}\\}\\\\\$$ This language represents all numbers wich have a prime as digit sum. I now want to show that this language is not context free. I want to show this with a *reductio ad absurdum* via the pumping lemma and I am not quite sure if I proofed it correctly:

My idea was to just pick a word wich is in $L$ and then show that it cannot be pumped up with the pumping lemma and because if the language is context free **every** word can be pumped up this shows that $L$ is not context free. But I am not quite sure if this is enough.

Let's assume that L is context free. Then the pumping lemma states that there is a number $k \in \mathbb{N}$ for wich **every** word $w \in L$ with $|w|\geq k$ can be splitted up like the following $w=xuyvz$ where the following constraints hold:

* $0\<|uv|\leq|uyv|\leq k$
* $\forall n \in \mathbb{N}:xu^nyv^nz \in L$

Let $k=5$ and $w=\\#11111$ because $|w|=6 \Rightarrow |w|\geq k$. We can split up $w$ like this $w=xuyvz$ where the following holds:

* $x=\\#$
* $u=1$
* $y=11$
* $v=1$
* $z=1$

Because $|uv|=2 \ \land \ |uyv|=4 \Rightarrow 0\<|uv|\leq|uyv|\leq k$. Now $\forall n \in \mathbb{N}:xu^nyv^nz \in L$ should also be true. But let $n=3$ then $w'=\\#111111111 \notin L$. Thus $L$ is not context free, because the pumping lemma with a number $k \in \mathbb{N}$ is not working for every $w$ with $|w|\geq k$.

I am self learning and have no one who can help me with this, so I really would appreciate if someone could tell me if this proof is working or how I can improve it.

# Answer
> 0 votes
There are several problems in your proof. The language $L$ indeed is not context-free, and the pumping lemma can be used to prove it.

However:

* you cannot choose the value of $k$ yourself;
* you cannot choose the values of $x, u, y, v$ and $z$ yourself.

The pumping lemma states that if $L$ is context-free, then **THERE EXISTS** $k\in \mathbb{N}$ such that **FOR ALL** $w\in L$ with $|w| \geqslant k$, then **THERE EXISTS** a decomposition $w=xuyvz$ verifying the three conditions.

However, to prove that $L$ is not context-free, you have to use the contraposition:

If **FOR ALL** $k\in \mathbb{N}$, **THERE EXISTS** $w\in L$ with $|w| \geqslant k$ such that **FOR ALL** decompositions $w=xuyvz$, not all three conditions are verified, then $L$ is not context-free.

The formulation you have seen may be a bit different, but the same ideas are underlying.

Now back to your problem. Let $k\in\mathbb{N}$ be any integer. Consider $p$ any prime number $\geqslant k$. Given the definition of $L$, it is clear that $w = \\#1^p\in L$ (here the $^p$ denotes $p$ repetitions, not the mathematical exponentiation).

Suppose $w = xuyvz$ with $|uv| \>0$ and $|uyv|\leqslant p$. Let us distinguish:

* if $uv$ contains the symbol $\\#$, then $xyz$ does not contain $\\#$ so $xyz\notin L$;
* that means that $uv = 1^q$ with $0\<q\leqslant p$. Then, $xu^{p+1}yv^{p+1}z = xuyvz(uv)^p = \\#1^p1^{qp} = \\#1^{q(p+1)}$. However, $q(p+1)$ is not prime, so $xu^{p+1}yv^{p+1}z\notin L$.

We conclude that $L$ is not context-free.

---
Tags: context-free, pumping-lemma
---


title: Is graph isomorphism $P$-hard?

text:
# Question
Title: Is graph isomorphism $P$-hard?
Intuitively speaking, it would seem like the graph isomorphism problem (which might be $NP$-intermediate) should be $P$-hard. But maybe it's not? Or maybe it's an open question?

If it is indeed $P$-hard, how can that be shown/argued?

---

Doing some searching, I found the following statement in the Wikipedia article on the Graph isomorphism problem:

> If in fact the graph isomorphism problem is solvable in polynomial time, $GI$ would equal $P$.

which seems (unless I am mistaken) to be indirectly claiming that graph isomorphism is $P$-hard, but there's no reference or argument given.

On the other hand, I found some search results (possibly old) that suggest it may be open; for example, this 2000 paper by Torán suggests that:

> The question of whether GI is P-hard is also open

(Not sure if that's still the case 23 years on?)

# Answer
> 2 votes
The problem here is that the reduction used is unclear in your question.

Both fact are correct, but the $\mathsf{P}$-hardness claim concern logspace-reduction, so it is not contradictory with the fact that $\texttt{Graph-Iso}\in\mathsf{P}\Rightarrow \mathsf{GI}=\mathsf{P}$.

In other terms:

* $\texttt{Graph-Iso}$ is $\mathsf{P}$-hard with polytime reductions;
* the paper claims that it is not known whether $\texttt{Graph-Iso}$ is $\mathsf{P}$-hard with logspace reductions.

---
Tags: complexity-theory, graphs, graph-isomorphism
---


# Question
Title: Prove the expected size of the independence set got by a random algorithm is at least 1/d of the maximum size
I am doing an exercise related to maximizing Independent Set, I have $G = (V = \\{v\_1, . . . , v\_n\\}, E)$ as an undirected graph. This graph as $n!$ possible orderings for the vertices $V$.

If we pick any such orderings uniformly at random i.e. let $\sigma = (\sigma\_1, . . . , \sigma\_n)$ be such random ordering then consider :

Begin with $S = \emptyset$.

Then, at each step for $i = 1$ to $n$, if for all $u \in S$, $(u, v\_{\sigma\_i}) \notin E$, add $v\_{\sigma\_i}$ to $S$.

Suppose we denote by $d$ the maximum degree of a vertex in $V$. We need to prove that the proposed algorithm achieves an independent set with expected value of at least $1/d$ fraction of the optimal solution.

---

My Proposed incomplete solution:

We denote OPT solution as $S^\*$ and $|S^\*| = OPT$ the size of the max independent set.
Let $S$ be the solution and $|S|$ is its size. We can write $X\_i = 1$ if $v\_{\sigma\_i}$ vertex is added to $S$ and $0$ if not. Let $X$ be the number of vertices added to $S$.

Consider any vertex $v \in V$. If $v$ is not added to the independent set $S$, it must be because one of its neighbors was added to the independent set $S$ before it. The probability that $v$ is added to the independent set $S$ is at most $1/(d+1)$, it’s an upper bound. We calculate the expected value of the algorithm: we denote $u$ as an arbitrary vertex of $V$ and $N(v)$ the neighbors of $v$.

$$\mathbb{E}\[X\] = \mathbb{E}\[X\_1\] + ... + \mathbb{E}\[X\_n\]$$

\begin{align} \mathbb{E}\[X\_i\] & = Pr\[v\_{\sigma\_i} \text{ is added to }S | u \notin N(v\_{\sigma\_i})\] \times Pr\[u \notin N(v\_{\sigma\_i})\]\\ & \qquad + Pr\[v\_{\sigma\_i}\text{ is added to }S | u \in N(v\_{\sigma\_i})\] \times Pr\[u \in N(v\_{\sigma\_i})\]\\ & = 1\times Pr\[u \notin N(v\_{\sigma\_i})\] + 0 \times Pr\[u \in N(v\_{\sigma\_i})\]\\ & = Pr\[u \notin N(v\_{\sigma\_i})\] \\ & = 1 - Pr\[u \in N(v\_{\sigma\_i})\] \end{align} since the maximum degree of a vertex is $d$, we have $Pr\[u \notin N(v\_{\sigma\_i})\] \leqslant $ (something? I'm not sure what) for all $i$ from $1$ to $n$.

Here I got stuck on how to proceed further. If there are mistakes in this I would be happy if you identify and correct.

# Answer
Let $Y\_v$ be the random variable that indicates whether vertex $v$ is added to the independence set. The probability that $v$ appears before all vertices that are incident to $v$ in a random ordering is $\frac1{\deg(v)+1}$, since all orderings are equally likely and all $\deg(v)+1$ vertices involved are symmetric to one another. On this situation $v$ will be added to the independence set. ($v$ can be added as well on other situations since none of its neighbors might have been added when $v$ appears after some of its neighbors.) We have $$E\[Y\_v\]\ge\frac1{\deg(v)+1}\ge\frac1{d+1}.$$

So the expected value of $Y$, which is the size of the independence set returned by the given random algorithm is $$E\[Y\]=\sum\_vE\[Y\_v\]\ge\frac{|V|}{d+1}.$$

On the other hand, we will see that the size of the maximum independence set is at most $\frac {d|V|}{d+1}$. We can assume $G$ is connected since it is enough to prove for each connected component. We assume $d\ge1$; otherwise $d=0$, the situation is trivial while the proposition is ill-defined with $\frac1d$.

Let $M$ be a maximum independence set. Since each vertex in $M$ is incident to a vertex not in $M$ (otherwise that vertex is an isolated vertex, meaning $G$ is not connected), we have $$|M| \le|\text{vertices that are incident to }V\setminus M |.$$ Since each vertex is incident to at most $d$ vertices, we have $$|\text{vertices that are incident to }V\setminus M|\le d|V\setminus M|.$$ Since $|V\setminus M|=|V|-|M|$, we get $|M|\le d(|V|-|M|)$, i.e., $$|M|\le \frac {d|V|}{d+1}.$$

So $$\frac{E\[Y\]}{|M|}\ge\frac{\frac{|V|}{d+1}}{\frac {d|V|}{d+1}}\ge\frac1d,$$ which is what we are asked to prove.
> 3 votes

---
Tags: graphs, approximation, randomized-algorithms, independent-sets
---


# Question
Title: Within the set of signed integers representable by a bit string of length n, are any two elements equivalent to each other mod 2^n?
Donald Knuth's *The Art of Computer Programming, Volume 1 Fascicle 1* contains the following exercise:

> If $\alpha$ is any string of 0s and 1s, let $\operatorname{s}(\alpha)$ and $\operatorname{u}(\alpha)$ be the integers that it represents when regarded as a signed or unsinged binary number. Prove that, if $x$ is any integer, we have: $$ x={s}(\alpha) \text{ if and only if } x\equiv {u}(\alpha)\bmod 2^n \text{ and} -2^{n-1} \le x \lt 2^{n-1} \text{ where } n \text{ is the length of } \alpha $$

The solution provided is:

> If $-2^{n-1} \le x \lt 2^{n-1}$, then $-2^n \le x-{s}(\alpha) \le 2^n$; hence $x \neq {s}(\alpha)$ implies $x \not\equiv {s}(\alpha)\bmod 2^n$.
>
> But ${s}(\alpha)={u}(\alpha) - 2^n\equiv {u}(\alpha)\bmod 2^n$ when $\alpha$ begins with 1.

I am confused about the last statement in the first line of the solution (i.e. if $x$ is not equal to ${s}(\alpha)$ , then $x$ is also not equivalent to ${s}(\alpha)$ under modulus $ 2^n$). To me that seems to imply that the answer to the title of this post is "no". But isn't $x=1$, ${s}(\alpha)=-1$ a simple counter example that works for any length bit string? What am I missing?

# Answer
> 1 votes
If $s(\alpha)=-1$, then $s(\alpha)\equiv\_{2^n}2^n-1\not\equiv\_{2^n}1$ for any $n\>1$.

Another argument you may find compelling: if $a \equiv\_m b$, then $a-b$ is a multiple of $m$. Since $x-s(\alpha)=1-(-1)=2$ is prime, $x$ and $s(\alpha)$ can only be equivalent mod 1 or 2.

---
Tags: computer-architecture, binary, modular-arithmetic
---


# Question
Title: What is the difference between the set containing the empty string and the set containing nothing at all?
It's an exercise question from chapter 0 of Michael Sipser's book Introduction to the Theory of Computation.

> e. The set containing the empty string
> f. The set containing nothing at all

I guess the empty string is still something, which is not nothing. Would this be the difference?

# Answer
> 6 votes
Yes, that's it.

One important difference could be seen using concatenation: let $L$ be any nonempty language.

Then $\\{\varepsilon\\}L = L$, but $\emptyset L = \emptyset$. Clearly those are different.

# Answer
> 3 votes
The difference is essentially structural.

In the case of the set containing the empty string, the set has a length of 1.

In the case of the set containing nothing, the set has a length of 0.

A string is typically conceived as a container of characters (as opposed to say an int, which is not typically conceived as a container of numbers or bits).

The string, as a container, can be present, but contain no characters - the string can have length 0, even though the set which contains the string has length 1.

In this way, there are two levels of containment when talking of sets containing strings, and what the set contains is not to be conflated with what the string contains.

This is distinct from "nothing" in the set, which is where even the string-as-a-container is absent from the set.

It might have been slightly clearer if Sipser had phrased himself as:

> e. The set containing the empty string.
>
> f. The set *that doesn't contain anything*.

# Answer
> 1 votes
A general way to check if two sets are equal: **two sets $S\_1$ and $S\_2$ are equal if (i) all of the elements in $S\_1$ are in $S\_2$, and (ii) all of the elements in $S\_2$ are in $S\_1$.** This property is called "extensionality".

In your case, let's apply the definition. Our first set, $S\_1$ is the set containing the empty string $\epsilon$. Our second set, $S\_2$ is the empty set. To check property (i), we look at all elements in $S\_1$: that's just one element, $\epsilon$. But $\epsilon$ is not in $S\_2$, since $S\_2$ is the empty set (and thus contains no elements). So the two sets are not equal.

# Answer
> 1 votes
Think of the set containing the empty string as one, and the empty set as zero.

A Kleene algebra is essentially an idempotent semi-ring, plus the Kleene closure operator. Ignoring the Kleene closure (a.k.a. Kleene star) operator, the ordered "multiplication" corresponds to string concatenation and "addition" corresponds to set union. Most of the axioms should look very familiar:

$$\begin{eqnarray\*} a + (b + c) & = & (a + b) + c \\ a \cdot (b \cdot c) & = & (a \cdot b) \cdot c \\ a + b & = & b + a \\ a\cdot (b + c) & = & a \cdot b + a \cdot c \\ (b + c) \cdot a & = & b \cdot a + c \cdot a \\ 0 + a & = & a + 0 = a \\ 1 \cdot a & = & a \cdot 1 = a \\ 0 \cdot a & = & a \cdot 0 = 0 \end{eqnarray\*}$$

Those last three show the difference between the empty set ($0$) and the set containing the empty string ($1$): the empty set is the identity for set *union*, and the empty string is the identity for string *concatenation*. The empty set also annihilates string concatenation.

That's a lot of terminology, but I think it's much easier to understand if you write it in this algebraic notation, rather than in regular expression notation:

$$\begin{eqnarray\*} \emptyset \\,|\\,a & = & a\\,|\\,\emptyset = a \\ \epsilon a & = & a \epsilon = a \\ \emptyset a & = & a \emptyset = \emptyset \end{eqnarray\*}$$

Just for completeness, the thing that makes addition correspond to set union is that it is *idempotent*:

$$a + a = a$$

All of the other axioms of a Kleene algebra define the Kleene closure operator ${}^\*$, which is important, but isn't relevant to your question. See the link above if you're interested.

# Answer
> 0 votes
It might be clearer to ask yourself whether a set containing an empty set is the same as an empty set. Russell and Whitehead say, "No."

---
Tags: sets
---


title: How to make a Huffman tree

text:
# Question
Title: How to make a Huffman tree
I'm trying to make a huffman tree based off of some words. I have the frequencies of each character stored using a hashtable, but i need to then make a minheap structure in order to then be able to make the huffman tree. What I don't get is how I am supposed to actually use the minheap because I don't understand how I am going to be able to tell (looking through the minheap) what chars freq I am actually looking at.

# Answer
Just as an additional comment, if the symbols are already sorted in increasing frequency order, Huffman tree construction can be done in linear time.

```
q1 <- a queue initialised with the symbols in increasing frequency order
q2 <- an empty queue

while there is more than one element in q1 and q2 do:
    Find the two elements with the lowest frequencies.
        (You only need to look at the first two elements in q1 and q2.)
    Pop them, merge the elements.
    Push the merged element onto q2.

```
> 1 votes

# Answer
If you have a min heap you don't need to know the frequency: the top is the one with the minimum. Just pop two items, join them and add the new item to the min heap. Ideally the frequency is stored in the value of the item stored.
> 0 votes

# Answer
It can be divided basically into three steps:

Step 1: For each character of the node, create a leaf node. The leaf node of a character contains the frequency of that character.

Step 2: Set all the nodes in sorted order according to their frequency.

Step 3: There may exist a condition in which two nodes may have the same frequency. In such a case, do the following:

Create a new internal node. The frequency of the node will be the sum of the frequency of those two nodes that have the same frequency. Mark the first node as the left child and another node as the right child of the newly created internal node.
> 0 votes

# Answer
If you have only 256 symbols, then you can afford brute force: Take the two elements with lowest frequency and combine them, repeat until only one element is left. Takes 256^2 instead of 256 log 256 steps.
> -1 votes

---
Tags: data-structures, trees, heaps, java, huffman-coding
---


# Question
Title: Transforming a Travelling Salesman Problem to a Maximum Clique Problem
Say you have a directed graph consisting of n nodes and containing edge weights. A starting node is also given. You want to begin your route at that node and visit each other node in the graph exactly once before returning to the starting node. Your goal is to take the route that has the smallest sum of edge weights possible.

How could you map this problem to the maximum clique problem (searching for the largest clique in an unweighted graph) or the weighted maximum clique problem (searching for the clique that has the highest sum of node weights in a graph with node weights)?

I think mapping the TSP problem to a weighted maximum clique problem should be possible, but I am not sure how to do it. I did some research but couldn't find anything useful for this problem. Thank you in avance!

# Answer
TSP is reducible to SAT which is reducible to 3SAT which is reducible to CLIQUE.

The reduction is not pretty, but still, it exists.
> 0 votes

---
Tags: complexity-theory, graphs, weighted-graphs, traveling-salesman, clique
---


title: Splay Tree remove step by step

text:
# Question
Title: Splay Tree remove step by step
I am having some difficulties understanding how the `remove()` operation works step by step with the splay tree. My tree looks like so:

```
       2
     /  \
    1    13
         /
        10
       /
      9
     /
    5

```

now I want to `remove(10)` and get the following tree (9 is the previous item from in-order traversal, so I replace 9 with 10)

```
       2
     /  \
    1    13
         /
        9
       /
      5

```

is that correct so far or do I need to splay already before remove? Any guidance would be much appreciated.

**Update** Or do I need to find the `10` to remove it and when found I already need to splay it up to the root?

# Answer
> 1 votes
The splay tree paper presented two variations for delete:

* The first will splay at the node $x$ to be removed then **join** its left and right trees. The join operation will splay $z$, the largest element of $x$'s left subtree, so it will be the root. Then the right subtree of $x$ will be the right subtree of $z$.
* In the second variant, let $y$ be the parent of the node to be removed $x$. First remove $x$ and replace it with the root of the tree created by joining its two subtree, where joining is the same as the one in the first approach. Then finally splay node $y$.

Your idea of splaying the node first before it is removed, follows the first approach. You just have to fix the tree by joining the left and right subtrees of the root after.

You can do some simulations here: https://www.cs.usfca.edu/~galles/visualization/SplayTree.html

# Answer
> 0 votes
The deletion operation is exactly the same as in standard BST:

* first, find the node $x$ to be deleted (either via a pointer or doing classic binary search);
* if $x$ has no child, just delete it;
* if $x$ has only one child $y$, then replace $x$ with the subtree rooted in $y$ and remove $x$;
* otherwise you can do the following:
    + either extract the leftmost node $y$ in the right child and replace $x$ with $y$;
    + or extract the rightmost node $y$ in the left child and replace $x$ with $y$;
    + or delete $x$ and join its two children.

In your example, the node $10$ has only one child, so your operation is correct.

---
Tags: splay-trees
---


# Question
Title: For what applications of the traveling salesman problem, does visiting each city at most once truely matter?
Traditionally, the traveling salesman problem has you visit a city at least once ***and*** at most once.

However, if you were an actual traveling salesman, you would want the least cost route to visit each city at least once, and you wouldn’t be bothered visiting a city 2, 3, or more times. For given city, you might stop and hawk your wares only once, and on subsequent visits, only drive through the city without stopping.

Consider an undirected graph having a city incident to exactly two edges. The cost on one of these edges is only 10 units, while the cost on the other is 99,999,999,999. If you insist on visiting each city ***at most*** once, then you are forced to incur the cost of the high cost edge. However, if you allow yourself to visit cities multiple times, then you simply leave the way you came in (on the low cost edge). The low cost edge leads you back to a city you've passed through before.

The traveling salesman problem is highly contrived for an actual traveling salesman. I want to give students an application for which there's a real incentive to visit each city at most once. For what applications is visiting each city a critical aspect of the problem?

# Answer
> 8 votes
Your conceptual difficulty stems from not distinguishing between TSP and Weighted Hamiltonian Cycle. These are usually discussed as if they are the same problem, but they're not.

In Weighted Hamiltonian Cycle, we are given a graph with nonnegative edge weights and we wish to determine the minimum-weight Hamiltonian cycle, i.e., the minimum-weight cycle that includes every vertex exactly once, and which therefore doesn't repeat any edge. That's just the definition; it's a problem about graphs and it may or may not correspond to any particular problem in the real world.

In TSP, we are given the cities and the matrix of distances between them. That's all the values are: distances. In particular, there is a distance between every pair of cities, regardless of what the road network looks like. You need to visit each city and your job is to choose the order in which to visit them, to minimized the total journey length. For example, consider the following distances:

```
                 B    P    W
Baltimore        -   100   40
Philadelphia    100   -   140
Washington DC    40  140   -

```

The shortest route is to, say, start in Philadelphia, drive to Baltimore, drive to DC, then drive back to Philadelphia. If the distances look a bit strange, it's because I-95 runs from Philadelphia to DC and passes through Baltimore. This means that "then drive back to Philadelphia" means passing through Baltimore again. This doesn't matter, because TSP isn't modelling that. It's just modelling visiting each city and completely ignores what happens *en route* between cities, except for the distances.

In contrast, if you represented this as the graph

```
    40       100
W ------ B ------- P

```

then there is no Hamiltonian cyle at all. This doesn't correspond well to the idea of travelling between cities: as you rightly ask, why not allow yourself to drive back through Baltimore? Should we add in a road from Washington to Philadelphia that doesn't go via Baltimore? That seems weird, as it would be longer. Why force yourself to do that? TSP isn't Weighted Hamiltonian Cycle.

The formal relationship between the two problems is that TSP is the restriction of weighted Hamiltonian path to the case where the graph is complete. Alternatively, you can associate a weighted Hamiltonian path instance as corresponding to the TSP instance where there's one city per vertex and the distance between two cities is the length of the shortest path between the corresponding vertices.

Note that, in the above, I've referred to the "distance" between cities. Even more formally, one should talk about an abstract "cost". The distinction is that distance sounds a lot like it ought to be symmetric and obey the triangle inequality, which corresponds to metric TSP. Cost isn't necessarily either of those things.

# Answer
> 0 votes
The question is whether the distances between cities fulfil the triangular equation: For any three A, B and C, is distance (A, B) ≤ distance (A, C) + distance (C, B)?

In your example, where distance (A, B) = 10, distance (C, B) = 1,000,000,000 and distance (X, B) = infinite (or very, very large) for all other X: Yes, it seems that going A-\>B-\>A avoids the long distance from B-\>C. However, if your distances fulfil the triangular equation, then we must have distance(A, C) ≥ 999,999,990, and distance (A, X) for any other X must be huge. So it is not at all obvious anymore that A-\>B-\>A is actually of any advantage.

Actually, if you find the shortest tour starting at A, visiting each city *at least* once and returning to A: Find a B that is visited twice if there is one. There will be some connection X-\>B-\>Y. With triangular equation, the distance X-\>B-\>Y is not shorter than X-\>Y, so you can replace X-\>B-\>Y with X-\>Y, and get a tour that is not longer, and which still visits every city at least once. Therefore, with triangular equation, being allowed to visit cities twice doesn't improve the optimal solution.

I'm not quite sure what happens if you give me a list of distances, and I can *enforce* that they are triangular, by replacing distance (A, B) with the shortest distance of any path going from A to B, visiting any number of cities in between.

# Answer
> 0 votes
Imagine in real life an area full of mountains. Every village has a short connection to a central point X, but all other connections between villages are very, very long, due to the mountains. The shortest route is very easy to find: Go from A to X to B to X to C to X ... to Y to X to A. The order doesn't matter. Since every other route is very long, the best route will visit X multiple times.

In a less extreme example: Implement "TSP with multiple visits". Then for every triple A, X, B, replace the distance AB with distance AX plus distance XB if that is shorter. Now find the optimal trip with multiple visits. For every AXB where X is visited twice, AB would be the same distance as AXB, so you can replace one AXB with AB (AB isn't shorter because AXB wouldn't be an optimal solution). You end up with an optimal solution for "TSP with multiple visits" with the same total length that doesn't actually have any multiple visits, so it is also the optimal solution for "TSP without multiple visits", but for a slightly different problem.

Summary: There are instances where "TSP with multiple visits" has a shorter solution than "TSP without multiple visits". Each such instance can be trivially changed so that "TSP with multiple visits" for original and modified instance, and "TSP without multiple visits" for the modified instance all have the same length.

In instances where the triangular equation holds, the modified and original instance are the same, so multiple visits won't gain anything. And in the real world, the distance from A to B and from B to A are often not the same, but that's a different problem.

---
Tags: graphs, optimization, graph-traversal, weighted-graphs, traveling-salesman
---


# Question
Title: Perfect ordered hash function on ordered sequence
I have a sequence of integer tuples $t\_1, t\_2,..., t\_N$ of different sizes in lexicographic order, e.g.:

$(1, 1), (1, 2), (1, 3, 5), (1, 3, 6), (1, 5), (3), (3, 2, 3), (3, 7), (3, 8, 1), ...$

* sequence length is $N \le 10^9 \space (2^{30})$,
* a tuple size bounded by $S, |t| \le S \le 32$,
* $i$-th element of a tuple is bounded: $0 \le x\_i \le s\_i$, $s\_i \le N, \prod{s\_i} \> 2^{64}$

Currently I use tuple indexes in the sequence as keys in some associative array, I can search the sequence for a tuple index in $O(\log N)$.

I want to create a substitute for tuple indexes,
a function $f(t)$ that maps a tuple into a $64$-bit integer and has following qualities:

* preservation of the order: $i \< j \rightarrow f(t\_i) \< f(t\_j)$
* time of calculation of $f(t)$ is better than $O(\log N)$, ideally $O(S)$
* preprocessing time is $O(SN)$, requires $O(N)$ additional memory
* the sequence is the domain of $f$, behavior of $f$ for any other tuple is undefined
* given $f(t)$ value it is possible to find $t$ in $O(\log N)$ time

The motivation/context: I'm trying to improve performance of an in-memory OLAP cube. The tuples are indexes of unique values in data columns.

# Answer
> 0 votes
How I solved the problem:
$f(t\_i) = i$, but it is possible to find element index quickly by using several static hash tables.

### Construction

There are hash functions $h\_1, h\_2, h\_3$ with codomains $1..M\_1, 1..M\_2, 1..M\_3$ which are almost universal.

1. Allocate array $K\_1$ of length $2M\_1$ and fill it with zeros, for every element $t\_i$ in the sequence calculate $j\_1 = h\_1(t\_i)$,
store $i$ in the array $K\_1\[j\_1\] = i$, if $K\_1\[j\_1\]$ is already occupied (a collision) then $K\_1\[j\_1\] = -1$ and mark $i$ for the next round.
2. Allocate array $K\_2$ of length $2M\_2$ and fill it with zeros, for every previously marked element calculate $j\_2 = h\_2(t\_i)$,
store $i$ in the array $K\_2\[j\_2\] = i$, if $K\_2\[j\_2\]$ is already occupied (a collision) then $K\_2\[j\_2\] = -1$ and mark $i$ for the next round.
3. Allocate array $K\_3$ of length $2M\_3$ and fill it with zeros, for every marked element calculate $j\_3 = h\_3(t\_i)$,
store $i$ in the array $K\_3\[j\_3\] = i$, if $K\_3\[j\_3\]$ is already occupied (a collision) then $K\_3\[j\_3\] = -1$.

### Calculation

1. For a given $t$ calculate $j\_1 = K\_1\[h\_1(t)\]$, if $j\_1 \> 0$ then $f(t) = j\_1$
2. else calculate $j\_2 = K\_2\[h\_2(t)\]$, if $j\_2 \> 0$ then $f(t) = j\_2$
3. else calculate $j\_3 = K\_3\[h\_3(t)\]$, if $j\_3 \> 0$ then $f(t) = j\_3$
4. else find $f(t)$ with old good binary search.

If $M\_1 = 2N, M\_2 = N, M\_3= N/2$ then on average there will be $1$ binary search in $1024$ calls of $f$
(apply 3 times formula for expected number of collisions in a hash table with size $N$ and number of elements $M$: $\frac{M(M-1)}{2N}$).

There is a lot of fine tuning ahead like choosing the right functions, their codomain sizes, hash table sizes but "smoke" performance tests on both live and synthetic datasets are quite promising.

The idea came from BBHash which is a modern minimum perfect function.

# Answer
> 1 votes
I believe you're looking for "monotone minimal perfect hashing".

---
Tags: time-complexity, search-algorithms, hash
---


# Question
Title: Why would we want to convert a forest or generic tree to binary tree?
Why sometimes we would want to convert generic trees or forests into a binary tree? And what's the main principle behind this convertion?

# Answer
> 1 votes
Such a conversion can occur when trying to represent an abstract tree on a computer.

If you consider an edge between a node and one of its children, it is natural to implement it as a memory pointer. However, on a generic tree, that would mean that each node could contain any number of memory pointers. This is not acceptable.

In an usual representation, each node $x$ contains a linked-list containing all children $\[y\_1, y\_2, …, y\_k\]$ of the node $x$. However, in terms of memory pointers, that means that $x$ contains a pointer to its first child $y\_1$, and each $y\_i$ contains a pointer to the next sibling $y\_{i+1}$.

In such an implementation, each node contains exactly 2 pointers: one to its first child and one to its next sibling. This is a binary tree.

When considering a forest, the idea is exactly the same, since the forest could be seen as a linked-list of the roots of the trees in the forest.

As an example, you could use the following structures:

* In C:

```
struct node{
     int value;
     struct node* first_child;
     struct node* next_sibling;
};

```
* In OCaml (here, the `next_sibling` pointer is not explicit, since we are using the `list` type):

```
type tree = Node of int * tree list
type forest = tree list

```

# Answer
> 0 votes
Binary trees have nodes of constant size, using two links: to the first descendant and to the sibling. This makes allocation easier.

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


# Question
Title: Find connected components in a graph of computer network with parallel pairwise tests
I have N nodes, a node might have an undirected edge to other nodes, resulting in K connected components (K\<=N, K unknown).
I can test if a given pair is connected. In each step in time, I can run N/2 such tests *in parallel* (a given node can be tested once per step). Each connected component is a cluster graph (it has no three-vertex induced path). The goal is to find all K components and list of nodes per component.

The actual application is nodes in a computer network, therefore I can run pairwise tests in parallel. I have ~256 nodes. How to approach this? A naive solution of N\*(N-1)/2 tests is too costly. Hopefully I could reuse a library algorithm in Python a solution.

For example for detecting the graph below (7 nodes, 3 connected-components (CC)), I might need this set of tests:

```
Step1 tests: D-A, C-F, E-B
Step2 tests: A-B, C-B, D-E (found CC: A-B-C)
Step3 tests: D-F (Found CC: D)
Step4 tests: E-F (Found CC: E-F)
Done.

```

# Answer
> 1 votes
The best you can do is about $N$ steps.

You can do it in about $N$ steps, by just testing $N/2$ new pairs in each step, until you've tested all pairs. Then once you have tested all pairs, you can use any standard algorithm to compute connected components (e.g., depth-first search).

You can't do better. In the worst case, you have to inspect essentially every pair of nodes, so you'll need to have inspected about $N^2/2$ pairs. (If there is even a single pair $u,v$ that you haven't inspected, where there is no other path of length $\>1$ from $u$ to $v$, then you can't tell whether $u,v$ are in the same component or not without querying the $u,v$ pair.) Since you can only inspect $N/2$ pairs per step, you'll need at least $N$ steps.

---
Tags: computer-networks, connected-components
---


title: Geometric Set Cover in one dimension

text:
# Question
Title: Geometric Set Cover in one dimension
Consider the geometric set cover problem https://en.wikipedia.org/wiki/Geometric\_set\_cover\_problem.

The Wiki article says there is a simple greedy algorithm for the one-dimension case, what is the analysis of that?

Is there a constant approximation factor possible for the one-dimensional case if each of the sets in the family contains only consecutive integers and the universe is the set of first n natural numbers? In the usual greedy algorithm for set cover, we take the set that covers the most number of elements, is that some constant times worse than the optimal in this case?

# Answer
> 2 votes
Consider $x\_1, …, x\_n\in \mathbb{R}$ and $I\_1, …, I\_k$ be intervals, $I\_i = \[a\_i, b\_i\]$.

Suppose without loss of generality that $x\_1 \< x\_2 \< … \< x\_n$. Let $I\_i$ be an interval such that $x\_1 \in I\_i$, and $b\_i$ maximal for such intervals.

Then there is an optimal solution containing $I\_i$. Indeed, suppose $I\_i$ is not in an optimal solution. Replace any interval containing $x\_1$ (there exists at least one) with $I\_i$. This is still a solution, because there is no point $\< x\_1$, and $b\_i$ was supposed to be maximal.

Reiterate the process with points $x\_j$ for $b\_i \< x\_j$ to obtain an optimal solution.

---
Tags: algorithm-analysis, combinatorics, approximation, set-cover
---