# Question
Title: Definition of extensional and propositional equality in Martin-Lof extensional type theory
Martin Hofmann states in Extensional Concepts in Intensional Type Theory (§1.1 p.\[4-5\]) that:

> A similar situation occurs in extensional Martin-Lof type theory where propositional and definitional equality are forcefully identified by the equality reflection rule
> $\frac{\Gamma \vdash P:Id\_\sigma(M,N)}{\Gamma \vdash M=N: \sigma}\text{(Id-DefEq)}$

Does the above mean that we purposefully drop the proof that M and N are equal and just consider them to be equal definitionally (like a presumption)?

Then it goes on and says:

> This rule makes definitional equality extensional and undecidable.

How does it become extensional and what does it mean by becoming extensional in the first place?

And then it states:

> Moreover, type checking becomes undecidable because $Refl(M):Id\_\sigma (M,N)$ holds iff $M$ and $N$ are definitionally equal.

Why would $Refl(M)$ hold only if $M$ and $N$ are definitionally equal? And why would it make it undecidable?

# Answer
> what does it mean by becoming extensional in the first place?

The axiom of extensionality relates to what it means for two functions to be equal. Specifically, extensionality says:

* $f = g \iff \forall x \ldotp f(x) = g(x)$

That is, functions are equal if they map equal inputs to equal outputs. By this definition, quicksort and mergesort are equal, even if they don't have the same implementations, because they behave the same *as functions*.

> How does it become extensional

What's missing is the rule of definitional equality for functions. It usually looks like this:

$\frac{\Gamma, (x : U) \vdash (f x) = (g x):V}{\Gamma \vdash f = g: (x : U) \to V}\text{(Fun-DefEq)}$

That is, two functions are definitionally equal when they produce equal results *when applied to an abstract variable*. This is similar in spirit to the way we typecheck polymorphic functions: you make sure it holds for all values by making sure it holds for an abstract value.

We get extensionality when we combine the two: if two functions always produce the same result, we should be able to find some equality proof $P$ such that $\Gamma,(x: U) \vdash P:Id\_V(f x, g x)$ i.e. the proof that the two functions always produce the same result. But, if we combine this with the rule $\text{(Id-DefEq)}$, then any time two functions are extensionally equal (i.e. we can find the proof term $P$, then they are also *definitionally equal*.

This is in stark contrast to an intensional system, where two functions are equal if and only if their bodies are *syntactically identical*. So mergesort and quicksort are intensionally different, but extensionally the same.

The $\text{(Id-DefEq)}$ means that extensional equality is baked into the type system: if you have a type constructor $T : ((x : U) \to V) \to \mathsf{Set}$, then you can use a value of type $T\ f$ in a context expecting $T\ g$ if $f$ and $g$ map equal inputs to equal outputs. Again this is not true in an intensional system, where $f$ and $g$ might be incompatible if they're syntactically different.

> Does the above mean that we purposefully drop the proof that M and N are equal and just consider them to be equal definitionally (like a presumption)?

It's even a bit stronger than that. It's saying that $M$ and $N$ are definitionally equal any time *there exists* some proof that they are propositionally equal. So on the one hand, if you have a propositional proof that two values are equal, you can forget that proof and say that they are definitionally equal. But on the other hand, if you are trying to prove that two values are definitionally equal (as a dependent type checking algorithm would), then you cannot say that they are not equal unless you are certain that no proof $P$ exists. This is why it is undecidable.
> 3 votes

---
Tags: type-theory, dependent-types, equality
---


# Question
Title: Comparison of constructive and local-search heuristics for TSP
In my high school class, we are currently looking at evaluating heuristic methods for intractable problems - especially TSP.

My question is what is the advantages or disadvantages of using a constructive heuristic (like Nearest-Neighbour) compared to local search (something like 2-opt from some research?)

Thank you

# Answer
> 1 votes
So first of all lets consider the techniques. Nearest neighbour is a heuristic that directs the search. That means that it informs how the search should proceed. It can be seen as preemptive.

The 2-opt is not a search heuristic but is a technique used to attempt to improve a solution(partial solution). You can think of it as massaging the solution into a more desirable solution.

As for advantages/disadvantages... well the nearest neighbour heuristic directs the search, but it may make silly mistakes. This in effect allows the search tree to be led "Down a rabbit hole".

The 2-opt solution is computationally more complex. It requires you to consider all quadruples (all pairs of edges if your data structure allows it) and then decide if the cross has occurred. In situations that you are looking for good enough and need an answer quickly, this type of search may be too computationally intensive. Although to the best of my knowledge, in any situation where 2-opt is a reasonable idea, the fitness of your solution should only improve/stay the same... Although I would not be surprised if I were wrong about that.

---
Tags: algorithms, heuristics, traveling-salesman
---


# Question
Title: What publication first introduced the concept of a non-deterministic Turing machine?
What publication first introduced the concept of a non-deterministic Turing machine?

Turing did not define the concept in his 1936 paper.

# Answer
This will be a partially inconclusive answer, unfortunately. Hopefully someone more knowledgeable can chime in and confirm the missing details. Let me summarize what I could find out so far.

Nondeterministic automata were introduced by Rabin and Scott in 1959. They also define two-way automata (which is a prelude to the LBAs introduced by Myhill the following year), but I could not find any mention of a *nondeterministic* two-way automaton (let alone a Turing machine) there.

The next paper (in chronological order) in which both nondeterminism and Turing machines appear is "On computability by certain classes of restricted Turing machines" by Fischer, 1963. In it, he defines general machines and also allow them to be nondeterministic. However, in the proof of Theorem 5 there he curiously states that some results (regarding deterministic and nondeterministic machines) are "well-known" to be equivalent for Turing machines. Hence, one is lead to believe the notion must have arisen sometime between the Rabin and Scott paper and Fischer's paper in 1963. Fortunately, Fischer gives a clue as to where he has those results from:

> The author is indebted to Dr. J. Evey for many of the ideas contained herein. He has worked closely with the author in this area and, in particular, is responsible for the results constituting parts (c) and (d) of Theorem 3 and for the main construction in part (e).

Theorem 3 in case is the computational equivalence of DTMs and NTMs.

Indeed, roughly a month after Fischer's paper Evey published "Application of pushdown-store machines," in which we also find nondeterminism applied to general machines (including Turing machines), and in which he proves the result that Fischer mentions (and extending it to some other types of machines). Fischer's work is actually listed in the bibliography there as well, but as far as I can tell there is no explicit citation of it in the text. The paper is most likely a summary of Evey's doctoral thesis (similarly titled), but I could not find it online; maybe someone with access to it can confirm that.

What I conclude then is that, unless I have made a gross oversight somewhere, the notion of an NTM must have just been evident to the research community once Rabin and Scott had brought nondeterminism to the table. Evey deserves credit for proving the computational equivalence of DTMs and NTMs, but it is hard to tell from the evidence at hand if he was the first to mention NTMs as a concept too (possibly in his doctoral thesis).
> 5 votes

---
Tags: turing-machines, reference-request, nondeterminism
---


# Question
Title: Is there a formal definition for iteration?
I wanted know if there is a formal definition of iteration. In the sense that, this definition will say that after the 4th iteration is termination or the 5th iteration and not the 2nd iteration. Basically a rigorous definition of iteration.

# Answer
The $k$th iteration is just the $k$th element of some appropriate sequence. In general, I doubt it's a formally defined concept; it's just one of those things whose meaning is basically the natural-language meaning of the word.
> 3 votes

# Answer
In the field of *Denotational semantics* they have developed a (very) formal definition of iteration in terms of recursive functions that you might like to look into.

https://en.wikipedia.org/wiki/Denotational\_semantics
> 3 votes

---
Tags: algorithms, logic, iteration
---


title: Condition in Arden's rule

text:
# Question
Title: Condition in Arden's rule
According to Arden's rule, the language equation $X= AX\cup B$, with unknown $X$, has the solution $X=A^\*B$, provided $A$ does not contain the empty string.

My question: what is the problem with the empty string here? Can you illustrate this with a concrete example (which lacks in Wikipedia on this topic).

# Answer
> 2 votes
Consider, for instance, $A = \\{ \varepsilon \\}$. Then $X = AX$, so $X = AX \cup B$ holds for any $X$ with $B \subseteq X$.

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


title: Finite Language Closure Properties

text:
# Question
Title: Finite Language Closure Properties
Let L={F| F is a finite language over Σ} which of the following operation is not closed for L?

a. intersection

b. union

c. complement

d. none of the above

---

I thought the ans as d as all finite languages are regular and since regular languages are closed under all hence **d** seemed apt to me. But ans given is **C** which is correct C or D? and Why?

# Answer
There are infinitely many strings over any alphabet, so if you pick any finite language, there are infinitely many strings not in it. In other words, there are infinitely many strings in the complement of any finite language.
> 1 votes

---
Tags: automata
---


# Question
Title: Looking for the name of this job scheduling algorithm
You have a list of jobs.

Each job has a deadline and an associated profit if completed before the deadline.

Also, each job takes 1 unit of time to complete, and only one job can be completed at any given time (ie single thread)

You are required to choose which jobs to complete such that profits are maximised.

This isn't for homework, just my own interest really. I want to find any resources on this problem or algorithms to solve it. It is similar to the interval scheduling problem, but not quite the same.

Any help would be appreciated.

# Answer
I don't know the name of the problem, but I do know the solution - this is the same problem that I had to solve for my algorithms course, just different terminology. The problem allows for a greedy choice. If you merely wanted a hint, then stop reading here because below is the solution.

Greedy choice: you schedule the job with maximum profit on its deadline. (If jobs should be finished before the deadline, e.g. job 1 should be done before $t = 2$, then simply subtract one from the associated deadline.)

The algorithm is pretty much working backwards in deadlines, (starting at the latest deadline) scheduling the job with highest profit available on that deadline (this boils down to the greedy choice).

I will leave the proof of the greedy choice as an exercise (read, I don't have a proper keyboard available, which isn't too great for my RSI, so I cannot write it now).
> 1 votes

---
Tags: algorithms, optimization, scheduling
---


# Question
Title: Does the Bellman-Ford algorithm find all the negative cycles?
The Bellman-Ford algorithm "can detect and report the negative cycle", but does it guarantee to find them or it may find some?

The algorithm really focuses on the shortest paths, so I'm unclear if it will find any negative cycle or if it might miss it.

Thanks!

EDIT: I'm only interested in knowing if there is a negative cycle (not where it is). How does one prove that Bellman-Ford would find the existence of a cycle?

# Answer
Bellman-Ford simply returns there exists at least one negative-weight cycle, it doesn't actually find all edges part of all such cycles. At best, without extending the algorithm too much, you find at most one edge per negative-weight cycle as cycles may intersect. There are ways to recover a negative weight cycle, see the link you provided, but this is outside the scope of the Bellman-Ford algorithm.

Edit: There is a subtlety that I forgot to mention, Bellman-Ford only returns the existence of a negative-weight cycle if that is cycle is reachable from the source vertex. In a disconnected graph, it may be the case that the negative-weight cycle is unreachable, so it will not be reported. Assume therefore that for every graph with a negative-weight cycle, it is reachable from the source vertex.

The proof is fairly simple. Let $v\_1, v\_2, \dots, v\_k, v\_1$ be a reachable negative weight cycle. We assume for contradiction that $d(v\_i) + w(v\_i, v\_{i+1}) \geq d(v\_{i+1}) for all $i = 1, \dots, k$.

If we add all inequalities, we obtain

$$\sum\_{i = 1}^{k} d(v\_i) + \left(\sum\_{i = 1}^{k - 1} w(v\_i, v\_{i+1}) + w(v\_k, v\_1)\right) \geq \sum\_{i = 1}^{k} d(v\_i),$$

and so $\sum\_{i = 1}^{k - 1} w(v\_i, v\_{i+1}) + w(v\_k, v\_1) \geq 0$. This is a contradiction, thus it must be that there is an edge on the cycle that still can be relaxed. Note that a simple path is of at most length $|V| - 1$, and if an edge can still be relaxed after $|V| - 1$ iterations, it must be an edge of a negative-weight cycle (this is maybe a little too simplified, but the intuition is correct).
> 2 votes

---
Tags: algorithms, graphs
---


# Question
Title: Hardness of approximation statement clarification?
In the paper I'm reading, there is a hardness of approximation result for an algorithm proved using a reduction to set cover. Roughly, the claim states that if there existed an algorithm that solved this problem considered in the paper with an approximation ratio less than or equal to $(1 - \alpha)( 1 + \log x)$ for any $\alpha \> 0$, the result for set cover would be contradicted. $x$ is a quantity that is shown to satisfy $x \leq n$. The set cover result is that set cover is NP-hard to approximate within $(1 - \alpha) \log n$.

My confusion stems from the fact that $(1 - \alpha)( 1 + \log x) \leq (1 - \alpha)( 1 + \log n)$ is not less than $(1 - \alpha) \log n$.

Can we just disregard this constant additive factor of $(1 - \alpha)$? What if the approximation ratio had a constant multiplicative factor? Like it would something like $(1 - \alpha)( 1 + \log x) (1 + \beta)$, where $\beta \> 0$?

# Answer
> 1 votes
Since $1 + \log n = (1 + o(1)) \log n$, for every $\beta \< \alpha$ you can find $N$ such that for $n \geq N$, $$ (1-\alpha)(1 + \log n) \leq (1-\beta) \log n. $$ This suffices to reach a contradiction.

---
Tags: complexity-theory, terminology, approximation, set-cover
---


# Question
Title: Calculation of speed up of a program executed in multi-threaded system
Speed up of execution of a program is to be calculated within a multi-threading rather than a single thread system. The program's 30% instruction can be executed serially & rest can be executed concurrently.The processor has 4 cores.

# Answer
> 1 votes
Say you have 100 units of work. 30 units are such that only one core can be used while performing that unit of work. 70 units are such that four cores each can perform one unit of work at the same time. That should be enough to give a theoretical answer.

But the question is imprecise: can the “serial “ task be in in parallel with three “parallel” tasks? In that case, you take just 30 units, otherwise 55 units.

In practice, there are problems. Using four cores produces heat which forces a reduction in clock speed. You may have four cores, but only one memory subsystem. So four cores hammering the memory will NOT do four times as much work. A single core may be able to use all available cache memory, which would have to be shared if four cores are running, reducing speed.

What makes it more interesting is the fact that sometimes you find an algorithm A which cannot be parallelised, and an algorithm B which takes more steps than A, but can be parallelised. So choosing algorithm B may save time overall, but do more work.

The only way to get a correct answer is to measure it.

---
Tags: operating-systems, process-scheduling, os-kernel, multi-tasking
---


# Question
Title: In what sense if any does java have multiple dispatch?
I'm trying to get my head around the difference between **message passing** *(with which we are all familiar as by far the most common form of object orientation today)* vs **generic functions** as implemented in CLOS (Common Lisp Object System).

In what sense is it possible to say java has a kind of multiple-dispatch system due to method overloading?

To sketch my understanding, in message passing you might do:

```
tell obja move objb
tell objb move obja

```

but where the function is first class and not in any object, you might do:

```
move obja objb

```

The part I do think I understand is that with generics there is no dilemma on where to place a function, whereas in message passing you may have to arbitrarily choose which class to put a function on, then just remember which one you put it on. With message passing, if you want to be able to call the behaviour from either, you have to *duplicate* the code (yes I know there are ways round that, but that's not the point).

I'm not sure I'm really getting the rest of how generics are different yet.

I just found a key reference on this point.

The wiki page on CLOS is also very good.

So, maybe best method is to hold off with the theory and just practice with clojure multi-methods at some point... unless anyone wishes to chip in.

# Answer
> In what sense is it possible to say java has a kind of multiple-dispatch system due to method overloading?

In no sense. What Java's method overloading gives you is *dynamic* dispatch, not multiple dispatch.

The most commonly seen example of multiple dispatch in Java is its event listener system, where you can register multiple listeners which will all be triggered when an event occurs.
> 1 votes

---
Tags: java, object-oriented
---


# Question
Title: Proving whether an input sequence is in a given RE language
I've learned this a few years ago that this is impossible unless one simply 'executes' (in a modern computing sense) the input with the language rules, but I have some problems in just using this statement.

* The fundamental doubt is that the statement itself is well-stated. If I'm using the term 'execution' to describe the act of matching the rules one input element by one, is this statement valid?
* Is this statement (deciding whether an input sequence is in a language is impossible without an execution) not exactly limited to RE? In other words, I wonder this statement also holds even for the languages in other classes.
* I'm not even sure how I can search for this statement and confirm from the external source.

(By RE, here I indicate the recursively enumerable languages, not the regular expression)

# Answer
> 1 votes
A language is recursively enumerable if there exists a Turing machine that:

* halts and says "yes" whenever its input is in the language;
* either halts and says "no" or just doesn't halt whenever its input is not in the language.

The undecidability of the halting problem means that there is no algorithm which, when given an RE language (or, rather, when given the code of a Turing machine which accepts some language) and a string, can determine whether the string is in the language or not. *In general*, all you can do is run the Turing machine and see if it accepts its input. However, if it seems to be taking a long time to run then, *in general*, there's no way of figuring out if it's in an infinite loop, so even this doesn't actually work.

However, that doesn't mean that you can *never* tell whether a particular machine will have certain behaviour. For example, it's easy to tell that the machine

```
IF the first character of the input is 0 THEN accept
ELSE [do something complicated]

```

will accept any string that begins with $0$. More sophisticated analytic techniques will allow you to prove that more complicated machines do or do not accept certain inputs. However, what the lack of a general algorithm means is that, whatever analytic techniques you develop, there will be some machines and some inputs (in fact, infinitely many of them) where your techniques fail. In those cases, your only options are to develop even more advanced techniques (which still won't work in all cases) or to give up and just run the machine.

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


title: Min Fibonacci Heap - increase key

text:
# Question
Title: Min Fibonacci Heap - increase key
I have been trying to implementing heap data structures for use in my research work. As part of that, I am trying to implement `increase-key` operations for min-heaps. I know that min-heaps generally support `decrease-key`. I was able to write the `increase-key` operation for a binary min-heap, wherein, I exchange increased key with the least child recursively. In the case of the Fibonacci heap, In this reference, they say that the Fibonacci heap also supports an `increase-key` operation. But, I couldn't find anything about it in the original paper on Fibonacci Heaps, nor could I find anything in CLRS (Introduction to Algorithms by Cormen).

Can someone tell me how I can go about implementing the increase-key operation efficiently and also without disturbing the data structure's amortized bounds for all the other operations?

# Answer
First note that $\text{increase-key}$ must be $O(\log n)$ if we wish for $\text{insert}$ and $\text{find-min}$ to stay $O(1)$ as they are in a Fibonacci heap.

If it weren't you'd be able to sort in $O(n)$ time by doing $n$ $\text{insert}$s, followed by repeatedly using $\text{find-min}$ to get the minimum and then $\text{increase-key}$ on the head by $\omega$ with $\forall x:\omega \> x$ to push the head to the end.

Now, knowing that $\text{increase-key}$ must be $O(\log n)$ we can provide a very simple asymptotically optimal implementation for it. To increase a node $n$ to value $x$, first you $\text{decrease-key}(n, -\infty)$, then $\text{delete-min()}$ followed by $\text{insert}(n, x)$.
> 5 votes

---
Tags: algorithms, data-structures, trees, heaps
---


title: Global variables and frame stack

text:
# Question
Title: Global variables and frame stack
The below program will read a positive integer from keyboard and print the binary equivalent. This program is using only one variable.

If global variables are not stored in frame stack, how this is working.

```
#include<stdio.h>
int n;
void binary(n)
{
    if(n>0)
    {
        binary(n/2);
        printf("%d",n%2);
    }
}

void main()
{
    scanf("%d",&n);
    binary(n);
}

```

# Answer
The program is actually using two variables. There is a global variable `n`, which is used by `main()`. There is a local variable, confusingly also named `n`, which is used by `binary()` and allocated on the stack.

---

Here are some excerpts from the code generated on my machine:

```
_binary:
...
        movl    %edi, -4(%rbp)
        cmpl    $0, -4(%rbp)
...

_main:
...
        movq    _n@GOTPCREL(%rip), %rsi
        movl    (%rsi), %edi
        movl    %eax, -4(%rbp)          ## 4-byte Spill
        callq   _binary
...
        .comm   _n,4,2                  ## @n

```

The first excerpt contains part of the code generated for `binary()`. The parameter `n` is passed in the register `edi`, and is then stored on the stack. The following command compares it to zero, implementing part of `n>0`.

The second excerpt contains part of the code generated for `main()`. The global variable `n` is allocated as a common symbol. The excerpt consists of the function call `binary(n)`. You can see that `n` is pulled out of the global storage and put into `edi`, before calling `binary()`.
> 1 votes

---
Tags: c
---


title: Undecidable languages

text:
# Question
Title: Undecidable languages
I'm confused on the definition of undecidable languages.

Definition: For an undecidable language, there is no Turing Machine which accepts the language and makes a decision for every input string w.

Can you say a language that isn't recognizable as undecidable?

If given a language like

$L = \\{\langle M \rangle \mid M$ is a turing machine with more than 50 states i.e. $|Q| \> 50 \\}$

I have to give an undecidable language T such that $T \subseteq L$.

A language that is a subset I think would be

$L\_2 = \\{\langle M \rangle \mid M$ is a turing machine with more than 60 states i.e. $|Q| \> 60 \\}$
because if $\langle M \rangle \in L\_2$, then $\langle M \rangle \in L$. Hence, $L\_2 \subseteq L$

But I'm confused on the undecidable part. How do I justify if this language is undecidable or if it even is?

# Answer
> 1 votes
Well, probably you have already heard about the halting problem. It is a well known and the most common example of an undecidable language. Let us call it $\mathcal{H}$.

I claim that $\mathcal{H} \cap L$ is an undecidable language that is a subset of $L$. Informally, the language of all turing machines of at least 50 states that halt after finite number of steps.

Probably you can prove it straight forward as we prove undecidability of $\mathcal{H}$ using diagonalization. However, a simpler (and more amusing) way of proving it is by showing that the halting problem is decidable when the number of states is constant, hence $\mathcal{H} \cap \overline{L}$ is decidable. The reason is that after finite number of steps we will either go through a state we already were in and hence go in infinite loop or finish.

Now that we proved $\mathcal{H} \cap \overline{L}$ is decidable, assuming $\mathcal{H} \cap L$ is decidable as well, $\mathcal{H}$ will be decidable, since each turing machine is either in $L$ or $\overline{L}$, which is a contradiction and hence $\mathcal{H} \cap L$ is undecidable.

**Note** Link for more information about halting problem.

# Answer
> 2 votes
Here is a more general statement:

> A language $L$ has an undecidable subset iff $L$ is infinite.

For the proof, note first that if $L$ is finite then all its subsets are finite and so decidable. Conversely, if $L$ is infinite then it has uncountably many subsets. Since there are only countably many decidable languages, some subset of $L$ (indeed, most subsets of $L$) must be undecidable.

---
Tags: undecidability
---


# Question
Title: What are these tree transformations called?
I want to **transform a general rooted, node-labeled tree into a related binary tree**. I came up with **four different schemes** ("left shallow", "right shallow", "left deep" and "right deep" binarization) that are illustrated by an example in the diagram below. They all preserve certain aspects of the original structure. Children stay children or become grand- (or grand-grand or grand\*-)children. Also, new nodes are introduced (depicted in blue), which is fine for my application.

**Does any of these four schemes have a name?** Or is it documented or studied somewhere?

I am aware of one documented "binarization" scheme, which is called Knuth transform (also in the diagram). It is also possible to recover the original tree from this and you don't even have to introduce new nodes while building the binary tree. However, I am not interested in this, since it brings former siblings into parent-child-relation, which I can't have in my application.

# Answer
The Natural Language Toolkit (NLTK) offers binarization: `nltk.treetransforms.chomsky_normal_form()`. The algorithm in NLTK implements the standard, straight-forward transformation into **Chomsky normal form**. It assumes the tree was generated via an underlying (context-free) grammar. This results in the deep trees in the bottom row (diagram in the question post). By default, you will get the "right deep" variant, as a consequence of putting the artificial non-terminals on the right of the existing non-terminals ("right **factorization**") when transforming the production rules. You can change the default parameter `factor="right"` to `factor="left"`, if you prefer the "left deep" variant.

However, this is not the only way to construct a grammar in Chomsky normal form, since it only requires to have production rules of the form $A\to BC$ (or $A\to a$). You could just as well decide to balance the two sets of children as well as possible and assign them to the artificial nodes on the left and right. Since children can come in odd numbers, you will have to decide to add one more to either side. If you put it on the left, you will get the "left shallow" variant, and the "right shallow" variant otherwise.

For this other algorithm to arrive at a Chomsky normal form (that produces the "shallow" variants) I could not find a term. This is likely because Chomsky normal form comes from the world of theoretical computer science and it is most useful as an existential fact ("there exists a certain normal form, s.t. ...") where the details matter little. I think **"balanced factorization"** would be an appropriate term for this transformation.

The library Discontinuous Data-Oriented Parsing offers more binarization schemes with a confusing set of options. This includes the algorithm from NLTK and approaches described in two papers. The library deals with natural language parsing via Linear Context-Free Rewriting Systems (LCFRS) (a generalization of Probabilistic Context-Free Grammars (PCFG)), and a lot of options might related to this specific application. I was not able to get a "shallow"/"balanced" binarization from this library, but it might be possible.
> 1 votes

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


# Question
Title: How to initialize the first h in an RNN?
Take a Vanilla RNN represented by the function $h\_t = f(h\_{t-1}, x\_t)$, how do you determine $h\_0$?

Edit: This answer over on the stats page has helped.

# Answer
> 1 votes
There are a few different ways. One way is to always give it a zero vector, or some other constant that means "new sequence". Another way is to train the initial state vector just like you train any other weight: initialize it randomly, then apply gradient descent during training. The former is easier and faster, but the latter can sometimes make the RNN more effective.

---
Tags: machine-learning, neural-networks
---


# Question
Title: if $L \in NP$ then its mapping reducible to HALT?
This is true because every language in $NP$ is decidable and therefore HALTS but how do I formally show this?

# Answer
It depends what type of reduction you're talking about. But if you mean a "many-one reduction with no time constraints" (a Turing machine that transforms instances of problem $L$ to instances of problem `HALT` such that the answers remain the same), then yes.

The algorithm goes something like this:

* Take an input $x$
* Use brute force to decide whether $x \in L$ (in potentially exponential but still finite time)
* If the answer is "yes", let $T$ be a Turing machine that always accepts
* If the answer is "no", let $T$ be a Turing machine that always diverges
* Return $\langle T \rangle$

Now, when $\langle T \rangle$ is passed to a `HALT` oracle, the oracle will accept if $x \in L$, and reject if $x \not \in L$.
> 1 votes

---
Tags: np
---


# Question
Title: Why values can not be replaced with their extensionally equal values in an intensional system?
Thomas Streicher states in Investigations into Intensional Type Theory(§Introduction p.5) that:

> Although in Intensional constructive set theory (Intensional Type Theory) one can do most of the things one wants to do... certain theorems simply do not hold due to the lack of extensionality. A typical example is that from $t\in B a$ and $p\in Id A ab$ one is not allowed t conclude that $t\in Bb$ where $A$ is a type and $B$ is a family of types indexed over $A$.(But of course one is allowed to infer $t\in Bb$ from $t\in Ba$ and $a=b\in A$ !)

An almost similar thin is mentioned in Definition of extensional and propositional equality in Martin-Lof extensional type theory:

> The (Id-DefEq) means that extensional equality is baked into the type system: if you have a type constructor :((:)→)→ then you can use a value of type in a context expecting if and map equal inputs to equal outputs. Again this is not true in an intensional system, where and might be incompatible if they're syntactically different.

Why is that? Isn't it that two functions that are producing exactly same output for their inputs, equal? So why can't one be replaced with another in a context? What makes definitionally equal functions eligible to be replaced with each other, but not the extensionally equal ones?

# Answer
> 5 votes
### We don't always want extentionality

In mathematics, a function is a relation between its inputs and its output. Two functions are equal if and only if they map the same outputs to the same inputs. But in computer science, we're often interested in *descriptions of computations* which we also call “functions”, where it matters how the outputs are calculated from the inputs. When we describe a computation in different ways, we want to have a way to distinguish between them.

There are different reasonable definitions of what it means for expressions to be equal (I discussed this a bit in a previous answer). Definitional equality, where two expressions are equal if they can be rewritten to each other, is one of the most fundamental ones. But even it is too coarse for some uses: if you rewrite an expression to one that calculates the same value but in a more efficient way, it's certainly equivalent in some sense (we don't want optimizing compilers to transform our programs into programs that don't do the same thing), but it's also not equivalent in some sense (if we use an optimizing compiler, it's because it does make some useful difference).

Intuitively speaking, definitional equality captures equivalence between functions (in the computer science term) that only requires knowledge of how computation works, and not of what objects they manipulate. A precise formalization of what this means would be very dependent on the details of the calculs, so let me explain that through an example. Suppose you model the integers as follows: $$ \begin{align} \mathtt{N} &::= \mathtt{0} \\;\mid\\; \mathtt{S} \\: (x:\mathtt{N}) \\ \mathtt{Z} &::= (\mathord{\mathtt{+}} \mid \mathord{\mathtt{-}}) \\; (x:\mathtt{N}) \\ \end{align} $$ That is, a natural integer is either 0 or the successor of a natural integer, and a signed integer is a sign (`-` or `+`) and a natural integer. This is a common representation of integers which is convenient for many proofs, and convenient if slow for many computations. Suppose you have a function that returns an element of $\mathtt{Z}$. We might like to say that it doesn't matter whether the function returns `+0` or `-0` for a given input, since `+0` and `-0` both represent the same integer $0$. But `+0` and `-0` are distinct objects. The equality on the implementation type $\mathtt{Z}$ is finer than the equality on the intended denotational semantics in $\mathbb{Z}$. In mathematical terms, equality of denotations induces an equivalence on the implementations that is not equality. This extends to functions that manipulate such objects: you get a coarser equivalence if you allow switching between equivalent representations than if you don't.

Likewise, definitional equality on functions means that these mathematical functions are implemented by the same object (up to computation). It is finer than extensional equality.

### Extensionality is independent of some theories

In many theories, extensional equality is not built in. You can have a perfectly fine theory, useful for many things, where it is impossible to prove that $f = g$ even though it's possible to prove that $\forall x, f(x) = g(x)$.

For example, in the calculus of inductive constructions, or in Coq which is built upon it, it's impossible to prove Streicher's K or functional extensionality. They can be added as axioms without making the logic inconsistent, and you may want to do that for certain developments, but you don't get them from the core theory. Streicher's axiom K is implied by the law of excluded middle (but functional extensionality isn't), but excluded middle is not always desirable.

Properties like the law of excluded middle and extensional equality of functions go against constructive logic, where you don't just know that things are true, you actually have a proof of them. Constructive logic maps well to computations via the Curry-Howard correspondence. The law of excluded middle doesn't have nice a compuational analog. In intuitionistic logic, if you have a proof of $A \vee B$, you can either get a proof of $A$ or a proof of $B$; the computational interpretation is that you have an discriminated union of `A` and `B`, and you look at the tag to see whether it's an `A` or a `B`. But in classical logic, given a proof of $A \vee B$, you don't necessarily know which one it is; so on the computation side, you have to make a non-deterministic choice between `A` and `B`.

### Extensionality is inconsistent with some theories

Sure, you can add Streicher's axiom K or extensionality of functions to Coq. But axioms that are admissible in isolation may be inconsistent if you add them together. There's a diagram of what implies what in the Coq FAQ, showing that impredicative Set plus the law of excluded middle plus the axiom of unique choice is inconsistent (but I think that any two is consistent). I don't know which sets of “reasonable-looking” axioms are compatible with K or with functional extensionality.

Streicher's axiom K is in particular inconsistent with the univalence axiom which is a cornerstone of homotopy type theory. This means that for example you can't directly model HoTT in Idris, since K is derivable from Idris's pattern matching. I don't understand this theory well enough to give an intuitive explanation for this inconsistency.

# Answer
> 6 votes
Supposing we have $a$ and $b$ of type $A$ and $p : \mathrm{Id}\_A(a,b)$, there simply is not any rule of type theory that would allow you to replace $b$ with $a$ arbitrarily. So one answer is "because type theory does not let you do that", and if you think that it can be done, please show me how. But I suppose that is a non-answer, what you really are asking is *why* is type theory designed in such a strange way.

There are many ways to understand equality. Students of mathematics are typically taught only one, namely the equality arising from set theory and classical mathematics. This kind of equality is very intuitive and easily understood. But as you learn more mathematics, you begin to understand that sometimes two objects are not really equal, but are "kind of equal". For example, they could be isomorphic, or connected by a path. So it makes sense to look for other explanations of equality that capture the idea of a more "relaxed" equality.

In mathematics it makes a lot of sense to say that functions are equal if they produce the same outputs, but this is not so in computer science. For example, if functions $f$ and $g$ produce the same outputs, but one is much faster than the other, then it is *useless* for a computer scientist to consider them equal.

Type theory is a formal system which allows us to express these ideas. The identity type $\mathrm{Id}\_A(a,b)$ is *not* necessarily the "true equality" (the only one that a student of classical mathematics knows about, and therefore calls it "true") of $a$ and $b$, it could be one of these other notions of equality that you learn about when you study homotopy theory and computer science.

For instance, one way to undertand $p : \mathrm{Id}\_A(a,b)$ is to say that $p$ is some sort of a "path" from $a$ to $b$. That is, $a$ and $b$ are not "really equal", but there is a way to get from $a$ to $b$. And so, if $P :A \to \mathrm{Type}$, we certainly would not expect $P a$ and $P b$ to be "exactly the same", but rather that "there is a way to get from $P a$ to $P b$". Indeed, this goes under name *transport* and it follows from the rules for the identity type: given $p : \mathrm{Id}\_A(a,b)$, there is a *isomorphism* of types $\mathrm{transport}\_p : P a \to P b$.

---
Tags: type-theory, dependent-types, equality
---


# Question
Title: Are all Integer Linear Programming problems NP-Hard?
As I understand, the assignment problem is in P as the Hungarian algorithm can solve it in polynomial time - O(n3). I also understand that the assignment problem is an integer linear programming problem, but the Wikipedia page states that this is NP-Hard. To me, this implies the assignment problem is in NP-Hard.

But surely the assignment problem can't be in both P and NP-Hard, otherwise P would equal NP? Does the Wikipedia page simply mean that the general algorithm for solving all ILP problems is NP-Hard? A few other sources state that ILP is NP-Hard so this is really confusing my understanding of complexity classes in general.

# Answer
> 22 votes
If a problem is NP-Hard it means that there exists a class of instances of that problem whose are NP-Hard. It is perfectly possible for other specific classes of instances to be solvable in polynomial time.

Consider for example the problem of finding a 3-coloration of a graph. It is a well-known NP-Hard problem. Now imagine that its instances are restricted to graphs that are, for example, trees. Clearly you can easily find a 3-coloration of a tree in polynomial time (indeed you can also find a 2-coloration).

Consider decision problems for a second. A method of proving the hardness of a decision problem $P$ is devising a polynomial (Karp) reduction from another problem $Q$ that is known to be NP-Hard. In this reduction you show that there exists a function $f$ that maps each instance $q$ of the problem $Q$ to an instance of the problem $P$ such that: $q$ is a yes instance for $Q \iff f(q)$ is a yes instance for $P$. This implies that solving $f(q)$ must be "at least as difficult" as solving $q$ itself.

Notice how it's not required for the image of $f$ to be equal to the set of the instances of $P$ . Therefore it's perfectly possibile for problem $P$ restricted to some subset of instances to not be hard.

To return to your original question:

* The assignment problem can be solved in polynomial time, i.e., a solution to each instance of the assignment problem can be computed in polynomial time.
* ILP is NP-Hard: in general it might be hard to compute a solution to an ILP problem, i.e. there are instances of ILP that are hard.
* Some specific instances of ILP can be solved in polynomial time.

# Answer
> 14 votes
No, special cases can be easier.

Consider this IP, for example, given $a\_i \geq 0$ for $i \in \[1..n\]$:

$\qquad\displaystyle \min \sum\_{i=1}^n x\_ia\_i$

s.t. $\quad\displaystyle\sum\_{i=1}^n x\_i \geq 1$
and $\ \displaystyle x\_i \in \mathbb{N}$ for $i \in \[1..n\]$.

It finds the minimum among $a\_1, \dots, a\_n$ (that for which, inevitably, $x\_i=1$ in an optimal solution). Finding the minium of $n$ numbers is clearly a polynomial problem.

# Answer
> 0 votes
You can model a polynomially solvable problem as an IP. This does not mean the problem is NP-hard. It simply means that there is no known polynomial algorithm for solving the IP model of your problem (unless P=NP).

So as you suggested, the assignment problem is in P but your IP model of it is NP-hard.

# Answer
> 0 votes
No, there are a special kind of integer program, if the constraint matrix is TUM (totally unimodular matrix), then it can be relaxed into the linear program, which can be solved in polynomial time.

# Answer
> -4 votes
The assignment problem is not a ILP, but an LP problem and therefore not NP-hard.

---
Tags: complexity-theory, complexity-classes, linear-programming, integer-programming
---


# Question
Title: Constructing a directed graph for O(1) queries
**This question appeared in an undergrad data structures final. The details are sound.**

I need help to design a data structure for a directed graph with the following properties:

1. Initialization should be done in O(1) time.
2. AddVertex(id1,id2,...idK) - Add a new vertex to the graph. The new vertex is added with id=N+1 where N is the number of existing vertices. id1...idK are the neighbors of the new vertex, such that there is an outgoing edge from the new added vertex to each of the vertices id1 .. idK. This should be done in O(K) time.
3. GetNumberOfNeighbors(id) - Return the number of outgoing edges for a vertex with a given id (id is in 1..N). This should be done in O(1) time.

All O(1) times are for worse case.

I know that the idea is to allocate a new array of K\*constant length during the AddVertex method, and to copy K vertices to it in O(K) total, but I don't know how to do this exactly.

Thanks a lot

# Answer
> 1 votes
Make a `Node` class whose objects hold and an array of references to the other nodes they connects to. Make a `Graph` class whose objects store a dictionary mapping node IDs to nodes, and implement your 3 methods.

# Answer
> 0 votes
So here is the solution (a little tricky):

Init()

Define a constant M=5. Initialize n - the number of vertices to be zero. Initialize 2 arrays A1 and A2 of length M and 2M using the known O(1) triple array "initialization" scheme.

AddVertex()

In each addition, if n \< M, do A1\[n\] = K, and then n++. If n==M then do A2\[n\] = K, and copy A1\[n-M\] to A2\[n-M\] (**one element**), then do n++. After 2M additions, n==2M and all A1 elements were copied to the beginning of A2. Then do M = 2\*M, allocate a new array of size 2\*M and point array A1 to it. Keep alternating between A1 and A2 when n==2M again.

In the GetNumberOfNeighbors(id), test the relation between id and M, and choose the correct array (A1 or A2) accordingly.

Maybe someone will find this helpful some day...

---
Tags: graphs, data-structures
---


# Question
Title: What is an example of a Turing-recognizable infinite word, which is not Turing-decidable?
I am confused about Turing Machines that are able to decide languages that contain infinite words.

1. Are languages with an infinite amount of only finite strings always decidable?
2. How can a Turing Machine halt on an infinite input string?
3. Can Turing Machines loop on finite strings?
4. What is the difference between an infinite input string that a Turing Machines can halt on and an infinite input string that a Turing Machine cannot halt on (decidable vs recognizable)?

It's a lot of questions but they are related, please help me.

# Answer
There's is a significant difference between "arbitrarily long" and "infinite".

As a simple example, an integer can have an arbitrarily great magnitude; formally, for every integer, there exists a larger integer (its successor), which in turn has a successor, and so on. But all integers are finite; $\omega \notin \mathbb{N}$. (Or, if you prefer, $\infty \notin \mathbb{N}$.)

Similarly, the Kleene star operator $A^\*$ represents the concatenation of an arbitrarily large number of elements from $A$, but not an infinite number of elements of $A$.

There is an interesting part of formal language theory which deals with sets of infinitely-long strings (ω-strings), but such strings cannot be produced by any regular expression. (You can use ω-regular expressions, which include the infinite repetition operator $A^\omega$.) But you might want to master the material you're currently studying before venturing onto Buchi automata, interesting though they may be.

To answer your questions:

1. No, there are undecidable languages consisting only of finite strings. Indeed, since such languages are undecidable, it is not necessarily even decidable whether they are finite sets. A classic example of an undecidable language is the set of (descriptions of) Turing machines which halt on every input. Note that every Turing machine (like every integer) has a finitely-long description, so the language is a set (an infinite set, in this case) of finite strings.
2. A Turing machine is under no obligation to read its entire input. Consider the language of ω-strings which start with an $a$. This is clearly a set of infinitely-long strings, but only a single character needs to be examined to determine whether a string belongs to the language.
3. Sure, why not. For example, the Turing machine trying to determine whether its input describes a Turing machine which halts on every input could simulate the described machine using every possible input, but that is going to go on forever even if the language describe a Turing machine which always halts.
4. See, for example, deterministic Buchi automata. Basically, an ω-language $L$ can be deterministic if there is a language $L' \subset Pref(L)$ of finite prefixes which can deterministically predict inclusion in $L$.
> 2 votes

---
Tags: formal-languages, turing-machines
---


# Question
Title: Permute an array in O(n) time with O(1) extra space with a given ordering function?
This question arises from a problem on a problem solving site (https://practice.geeksforgeeks.org/problems/-rearrange-array-alternately/0).

Given a sorted (ascending order) array $A$ of $N$ numbers, re-arrange the elements of A to be this order: \[A\[n-1\], A\[0\], A\[n-2\], A\[1\], A\[n-3\], A\[2\], ...\]. While the problem does not actually call for this specific index permutation, that's the approach I took (it will yield the correct answer). If there is a solution that does not involve this approach, I'm interested to see it, but this question specifically is about whether or not it is possible to perform this specific data value re-arrangement without regards to the values stored in the array.

In other words, alternately interleave the maximum, minimum, 2nd-maximum, 2nd-minimum, etc. The algorithm should run in $O(n)$ time and consume only $O(1)$ extra space. It should work regardless of the data values in the array, including scenarios with duplicate values.

Solutions for $O(n^2)$ time with $O(1)$ space and $O(n)$ time with $O(n)$ space are straightforward.

There is a simple function that given a source index in the initial sorted array, determines its destination index in the re-arranged array. I have a partial solution that works by starting at some index and moving through the cycles of source $=\>$ destination element moving. But I couldn't find a way to compute the locations of all the separate index-moving cycles. Instead, after completing a cycle, I search the partially re-arranged array for pairs of values that haven't been moved yet (that hold the original, not new, ordering), and use those indices to start a new cycle (this probably means my solution is not $O(n)$ time because of this search). But this doesn't work in general if the elements of the initial array contain duplicate values.

I have an intuition that there must must be an algorithmic move/swap index ordering dependent only on N, but I haven't been able to find one.

# Answer
> 4 votes
Reverse the last half of the array in-place and then apply one of the interleaving algorithms mentioned in this question.

That question is for even $n$, and I didn't check whether the answers work for odd $n$ as well. If they don't and it's needed you can do a left rotation to move the middle element to the end (its correct position) and then use one of the even-case algorithms to move the first $n - 1$ elements to their correct positions.

# Answer
> 0 votes
Any algorithm which follows the cycles of the permutation will do. They move an element out of the way, place the element that has to take it's place, fill in it's position, until exhausting a cycle; go for the next cycle. Time is $n$ \+ number of cycles (clearly $O(n)$); extra space is one element worth.

---
Tags: algorithms, permutations
---


# Question
Title: Lower bound for merging $m$ sorted arrays (decision tree leaves count - permutations)
I need some help understanding how to calculate the lower bound on the time complexity of merging $m$ sorted arrays of length $n$.

The bound should be $nm \lg(m)$. I need to prove this using a decision tree.

I tried counting the number of possible permutations (which would be the number of leaves in the tree) but I got stuck. I tried the following:

When merging the 2nd array with the first, we have $\binom{2n}{n}$ possibilities to place the elements. When merging the 3rd, we have $\binom{3n}{n}$ and so on, so the total number of permutations is:

$$\binom{2n}{n} \binom{3n}{n} \dots \binom{mn}{n}$$

The height of the tree is denoted $h$.

$$h \> \lg{\binom{2n}{n} \binom{3n}{n} \dots \binom{mn}{n}}$$

And from here I don't know how to prove the complexity.

My question is - did I count the permutations correctly? Is there a more simple bound? How to continue from here?

Also, ould this problem possibly be equivalent to the problem of sorting an $m$-sorted array of size $nm$? Because in this problem it is easy to prove that the bound is $nm \lg(m)$.

# Answer
Stirling's formula shows that $$ \binom{N}{pN} \sim \frac{2^{H(p)N}}{\sqrt{2\pi p(1-p)N}}, $$ where $H(p)$ is the binary entropy function: $$ H(p) = p\log \frac{1}{p} + (1-p) \log \frac{1}{1-p}. $$ In particular, this shows that for $k \geq 2$, $$ \binom{kn}{n} = (1+o(1)) \frac{2^{H(1/k)kn}}{\sqrt{2\pi(1/k)(1-1/k)kn}} \geq (1+o(1)) \frac{2^{n\log k}}{\sqrt{2\pi n}}. $$ Therefore $$ \log \binom{kn}{n} \geq n\log k - O(\log n), $$ where the big O doesn't depend on $k$. Summing this for $k=2,\ldots,m$, we deduce $$ h \geq n \log m! - O(m\log n) \geq nm \log m - O(nm), $$ using Stirling's formula again.
> 1 votes

---
Tags: sorting, lower-bounds, decision-tree
---


# Question
Title: How to use c-gap problems to prove inapproximability?
Suppose there is a specific set function with some properties - $f=2^V\to \mathcal{R}$. It is known that the following problem is NP-Hard: Find $S\subseteq V, |S|\leq k$ such that $f(S)$ is maximized. My goal is to show that designing a constant factor approximation algorithm in polynomial time is NP-Hard.

Correct me if I am wrong: As per these notes on gap reductions, we can design a c-gap problem with $OPT$ being the maximum value of $f$. The problem takes as input $\beta$. The goal is to answer YES if $OPT\geq \beta$. NO if $OPT\< c\cdot \beta$. (here $c\<1$).

To show the desired inapproximability, it would suffice to show the above c-gap problem is NP-Hard. My question is: Why is it this decision problem is designed for one $\beta$ when the optimimum value for the maximization problem is not known? Is the idea that, suppose you have a solver for the c-gap problem, you can call it with multiple values of $\beta$? If so, how many calls are possible?

Also any additional references on proving inapproximability would be greatly appreciated.

# Answer
One way to show that there is no polynomial time approximation algorithm with ratio $c$ for a certain problem X (assuming P≠NP) is to give a reduction $f$ from an NP-hard problem Y to X such that:

* If $x$ is a Yes instance then the optimal value for X is at least $\beta(x)$, where $\beta(x)$ can be computed from $x$ in polynomial time.
* If $x$ is a No instance then the optimal value for $X$ is less than $c\beta(x)$ (for the same $\beta(x)$).

Any approximation algorithm for X whose approximation ratio is $c$ can be used to solve Y via the reduction $f$. Therefore, there cannot be any such efficient approximation algorithm unless P=NP.

I'll let you figure out the proof of these two statements.
> 3 votes

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


# Question
Title: Minimize cost of recursive pairwise sums: how to prove the greedy solution works?
The problem is in this other question.

Why does this always work? It's not clear to me how one would use induction.

For $n = 3$, a quick calculation shows it works, however, I don't think it generalizes well.

# Answer
> 2 votes
Each summing approach can be represented by a binary tree: the leaves represent the original elements and each internal node (including the root) represents the result element of the addition of the elements represented by its two children. For example,

```
Input: [1, 5, 3, 7]
Adding 1 and 3 together (Cost 1+3 = 4)
State: [5, 7, 4]
Adding 4 and 5 together (Cost 4+5 = 9)
State: [7, 9]
Adding 7 and 9 together (Cost 7+9 = 16)
State: [16]

Total cost: 4 + 9 + 16 = 29

```

... can be regarded as the following tree:

```
      16
     /  \
    9    \
   / \    \
  4   \    \
 / \   \    \
1   3   5    7

```

Then we rewrite the cost of each addition as the sum of original elements. For example, the costs in the example above are:

```
4 = 1+3
9 = 4+5 = 1+3+5
16 = 7+9 = 1+3+5+7

Total cost: 4 + 9 + 16 = 29

```

We can see each number corresponding to a leaf is contributed to the total cost in the additions corresponding to its ascendants. For a leaf $e$, If we denote by $h(e)$ the height of $e$, and by $f(e)$ the number corresponding to $e$, then the total cost is exactly $\sum\_{e\ :\ \text{leaves}}f(e)\cdot h(e)$.

Note each tree represents a prefix code of the leaves. In the example above, the tree represents the prefix code:

```
1: 000
3: 001
5: 01
7: 1

```

If we regard $f(e)$ as the frequency of $e$, then $\sum\_{e\ :\ \text{leaves}}f(e)\cdot h(e)$ is the average length of the code, which is optimized by Huffman coding. Note the answer in your link describes exactly how Huffman coding works.

---
Tags: algorithms, correctness-proof, greedy-algorithms
---


# Question
Title: Subgraph isomorphism reduction from the Clique problem
I was trying to understand the Wikipedia proof for NP-completeness of subgraph isomorphism by reduction from the clique problem. It's really just one sentence:

> Let $H$ be the complete graph $K\_k$; then, the answer to the subgraph isomorphism problem for $G$ and $H$ is equal to the answer to the clique problem for $G$ and $k$.

In the subgraph isomorphism problem, $G$ and $H$ are not constrained in any way (e.g., $H$ is not constrained to complete graphs). Yet, in the proof, Wikipedia just states "let $H$ be the complete graph $K\_k$". It's not defined what $K\_k$ represents or why $H$ suddenly becomes constrained to a complete graph.

# Answer
The decision version of the clique problem asks whether a given graph $G$ contains a complete graph with $k$ vertices as subgraph. The wikipedia article just explains why the decision version of the clique problem is a special case of the subgraph isomorphism problem. Namely if the graph $H$ is the complete graph with $k$ vertices, then the answer to this special subgraph isomorphism problem is just the answer to the decision version of the clique problem.

This shows that subgraph isomorphism is NP-hard, since the clique problem is NP-complete. But the subgraph isomorphism is obviously in NP, since it a given monomorphism from $H$ to $G$ can efficiently be checked to be a monomorphism. So we can conclude that subgraph isomorphism is NP-complete.
> 4 votes

# Answer
You misunderstood the proof of NP-completeness of Subgraph Isomorphism (SI).

1. We know that SI $\in$ NP because we can check its solution in polynomial time.
2. **Any** instance of clique problem (which is NP-complete) can be reduced in polynomial time to **some** instance of SI. This concludes that **any** problem in NP can be reduced to **some** instance of SI.

If you read the definition of NP-completeness, you will find out that its requirement satisfied by word **any**. The word **some** doesn't contradict it in any way.
> 0 votes

---
Tags: graphs, np-complete, reductions, graph-isomorphism
---


# Question
Title: how to calculate $2^{5000}$ mod 10 without calculator in fast way?
How is it possible to calculate $2^{5000}$ mod 10 without using a calculator in a fast way? The result with calculator was 6.

# Answer
> 5 votes
Consider the first few powers of 2:

> 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024…

Now take all of those mod 10:

> 1, 2, 4, 8, 6, 2, 4, 8, 6, 2, 4…

Try to solve it yourself, from this, before continuing to read.

---

There's a theorem that says, if $x \times y \cong z \mod m$, then $x' \times y \cong z \mod m$, for any $x' \cong x \mod m$. This means that, if you ever find two powers of two that are congruent (mod 10), the values in between them will form a cycle that loops forever. And it'll always be possible to find such congruent powers, so there'll always be such a cycle with ten or fewer elements in it. (All three of these statements can and should be proven, but those proofs are left as an exercise for the reader.)

In this case, the first such pair of values are 2 and 32. In other words, $2^5 \cong 2^1 \mod 10$. Which means that $2^6 \cong 2^2 \mod 10$, and $2^7 \cong 2^3 \mod 10$, and so on. In general, $2^x \cong 2^y \mod 10$ iff $x \cong y \mod 4$ (for integers $x, y \geq 1$).

So all you have to do now is reduce 5000 mod 4; since we know that $100 \cong 0 \mod 4$, 5000 must also be congruent to zero (and, more relevantly, to four, since our formula only holds for integers ≥ 1—do you see why?). Therefore, $2^{5000} \cong 2^4 \mod 10$. Now you just need to know the first few powers of two, or multiply them out longhand, to find that the answer is $2^{5000} \cong 2^4 \cong 6$.

# Answer
> 4 votes
Write down the first 10 or so powers modulo 10. Do you see a pattern?

# Answer
> 3 votes
$$2^N \bmod 10 = 2^{(N-1) \bmod 4 + 1} \bmod 10$$

(try to prove it)

# Answer
> 0 votes
And a completely different method, not quite as fast but works for other powers: 5000 = 2\*2\*2\*5\*5\*5\*5. 2 squared = 4, 4 squared = 6, 6square = 6, 6 to the fifth power = 1296 = 6, three times more to the 5th power = 6 (all modulo 10)

Basically raising x to the nth power can be done using at most 2 log n multiplications. (Would be useful for 3146^5000 modulo 8428, for example).

---
Tags: discrete-mathematics, modular-arithmetic
---


# Question
Title: Determining equivalence classes of $\{w \in \{0,1\}^*\mid$ the $k$-bit of $w$ from the right is 1$\}$
I want to formally write the equivalence classes of the following language: $$L\_k = \\{w \in \\{0,1\\}^\*\mid\text{ the } k\text{-th bit of }w\text{ from the right is } 1\\}$$

I understand the definition of equivalence classes, yet struggle to come up with a clear intuitive answer.

The language is regular, therefore i'd expect finite equivalence classes.

It seems like the essence of the information I am looking for is only "what is the $k$-th bit from the right", which means i want to focus my attention on suffixes in the form of $\sigma y \in \\{0,1\\}^\*$ where $|y|=k-1$, $\sigma\in \Sigma$.

I would highly appreciate some guidance that would build my intuition for finding equivalence classes in general, and in this specific case.

# Answer
http://users.utu.fi/jkari/automata/fullnotes.pdf explains equivalence classes well (under section 2.8 "Myhill-Nerode theorem") whence the following notation and definition is borrowed.

Define $\text{Ext}(w,L) =\\{x\mid wx\in L\\}$ where $w$ is in $\Sigma^\*$ and $L$ is the language, ie. the set contains of all suffixes that, when added to $w$, yields a word in $L$.

Two words $a$ and $b$ are in the same equivalence class if $\text{Ext}(a,L)=\text{Ext}(b,L)$.

For the language $L\_k$ described, only the last $k$ letters of $w$ matter when figuring out $\text{Ext}(w,L\_k)$ for any word $w$ because the other letters do not matter as they do not contribute to the condition "the $k$-th bit of $w$ from the right is $1$". Since there are only finitely many combinations for the last $k$ letters, specifically $2^k$, there are a finite number of equivalence classes in $L\_k$.

As per your edit about suffixes of length less than $k$, sure, $\text{Ext}$ can contain such suffixes, but they do not matter in showing that there exist finitely many equivalence classes.
> 0 votes

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


# Question
Title: A doubt on converting NOT gate to CNF formula
For a NOT gate if $x\_1$ is input and $x\_2$ is the corresponding output, I see the equivalent CNF (conjunctive normal form) is $(x\_1 \lor x\_2) \land (\overline x\_1 \lor \overline x\_2)$.

My expectations was that the CNF should not include $x\_2$ as it is the output of the gate. I was rather hoping the formula to be of a form $x\_2=F(x\_1, b\_1, b\_2, ...)$ where $b\_1$, $b\_2$, .. are the boolean constants such that when $x\_1$ is zero, the $F(.,.,..)$ would yield true just like the NOT gate.

Can anyone help me understand, how come this CNF including $x\_2$ is equivalent to a NOT gate. How to draw a truth table for this CNF form as in what value to assign for $x\_2$!

# Answer
Your formula *does* actually look like $x\_2 = F(x\_1)$, it's just written with different symbols.

First, we can rewrite the two clauses using implication. Since $(a \to b) \iff (\neg a \lor b)$, we can rewrite the formula as

$$ (\neg x\_1 \to x\_2) \land (x\_2 \to\neg x\_1) $$

Now, you can recognize that this is $(a \to b) \land (b \to a)$, which is to say $a \iff b$.

$\iff$ as a boolean operator behaves the same way as $=$; it evaluates to true when its left hand side and right hand side are the same. So your formula is equivalent to

$$ x\_2 \iff \neg x\_1 $$

Viewing this as a constraint (assuming $x\_1$ can be treated as "fixed"), $x\_2$ is fixed as $x\_2 := \neg x\_1 $
> 1 votes

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


title: Does EXP^EXP = EXP?

text:
# Question
Title: Does EXP^EXP = EXP?
Does $\mathrm{EXP}^\mathrm{EXP}=\mathrm{EXP}$?

Here is my thought: $\mathrm{EXP}$ machine can ask $2^{O(n)}$ queries to the oracle, and each oracle would itself solve an exponential time problem in a single step. So the total power would be $2^{O(n)}\times2^{O(n)}$ which would still be in EXP.

# Answer
> 2 votes
Your definition of EXP is a bit off (you're thinking of $\textbf{E} = \textbf{DTIME}(2^{O(n)})$ instead of $\textbf{EXP} = \textbf{DTIME}(2^{n^{O(1)}})$), but either way the assertion that "each oracle would itself solve an exponential time problem in a single step" is false.

This is because, given exponential time, the machine can write (say) $2^n$ bits to the oracle's input tape, at which point the oracle is allowed to run exponential-time algorithms as measured relative to the size of the $2^n$ bit input (and therefore doubly-exponential in $n$). Thus, just by padding the input to an exponential size and calling the oracle once, you can solve any problem in 2EXP, violating the time hierarchy.

---
Tags: complexity-theory, time-complexity, complexity-classes, oracle-machines
---


# Question
Title: How to find i-th root of n whose remainder is the smallest?
Given a number n, what is the most assymptotically fast algorithm to express it in terms of base^exponent + rem such that rem is the smallest possible and base is limited from 2 to some relatively small number (e.g. the maximum number that can be represented by a unsigned int)?

I'm currently using gmp bignum library in C, and my algorithm is as follows:

It first finds the smallest possible base and the greatest possible base given the circunstances (binaries searches are performed) and then we know the range of i.

Then, for each possible i, we take the i-th root of n and the corresponding remainder. The smallest remainder is updated if the current remainder is smaller than it.

The algorithm does work, but it's far too slow (even using such a powerful library as gmp). For comparison, for a number with roughly 6 mega bits when expressed in binary the algorithm takes ~90 days to complete.

Intuitively, I think there is a better way to solve the problem (i.e. faster way, an algorithm with a smaller time complexity). What can be done to speed up this process?

Obs: Problem: Given n, find i such that the remainder, n - (floor(ithRootOf(n))^i, is the smallest possible. 2 \<= floor(ithRootOf(n)) \<= 2147483647

# Answer
You want to write $n$ as $b^x + r$ with $x,r \ge 0$ and $b \in \\{2, \dots, 2^{31} - 1\\}$.

Since you're asking for the *asymptotic* complexity and the base $b$ is in a set of constant size, you can just focus on a single value of $b$. The exponent is then $x = \lfloor \log\_b n \rfloor$ and can be found using $O(\log \log n)$ operations (search for the first $y$ such that $b^y \> n$ by trying $b, b^2, b^4, b^8, \dots$, where each term is the product of the previous term by itself, then binary search for the last $x \in \\{y/2, \dots, y\\}$ such that $b^x \le n $).

The above procedure already gives you $b^x$, from which you can compute $r = n - b^x$. Return the triple $(b, x, r)$ that minimizes $r$.

If the time of each arithmetic operation is constant, the above requires $O(\log \log n)$ time. If each arithmetic operation takes logarithmic time in the value of its operands, then the complexity is $O(\log n \cdot \log \log n)$.
> 1 votes

# Answer
You say you have a number of 6 Megabits, that is $n \< 2^{6,000,000}$.

We want to find numbers $b^k$ where b and k are integers, $2 ≤ b \< 2^{31}$, k as large as possible such that $b^k ≤ n$, we you want to find the pair b, k that makes $n-b^k$ as small as possible. Since n is fixed, this is equivalent to making $n / b^k$ as small as possible, or making $\log n - k \cdot \log b$ as small as possible.

We find potential candidates by calculating k using double precision floating-point arithmetic. We calculate x = $\log n \div \log b$, and k = $\lfloor x \rfloor$. Then we calculate $\log n - k \cdot \log b$, and pick the b, k where this is smallest.

We need to be careful because of rounding errors in floating point arithmetic: So we can't just choose b, k which make $\log n - k \cdot \log b$ according to our calculation. We also need to consider all b', k' which may give the same or worse results due to rounding errors, but in reality might be better.

We also need to be careful if $x = \log n - k \cdot \log b$ is so close to the nearest integer that we can't determine $k = \lfloor x \rfloor$ for sure. In these cases, let k' = x rounded to the nearest integer and k = k' - 1 (these are the two possible values); we process (b, k) like every other pair, but must consider (b, k') to be a candidate as well.

If b is large then we can save more time: For example, if n is a 6 million bit number, then for b ≥ 70,000 there will always be two or more consecutive values b with the same k. If b is close to $2^{31}$, we find that over 200,000 consecutive values b have the same k. So for large b, we instead find the largest b for a fixed k: b = $\lfloor \exp (\log n \div (k + 1)) \rfloor$; this substantially reduces the amount of work.

Once we have a small number of candidates, to avoid having to figure out whether say $2^{1,234,568}$ or $4^{617,284}$ are closer to n, we exclude values b which are powers of some smaller number.

Then we first examine all the pairs (b, k') where the calculated x was very close to an integer: We have to calculate $b^{k'}$ exactly, reject it if it is greater than n, otherwise keep the smallest one. If none of these were accepted, we examine all the other candidates that might be optimal.

For a 6 million bit number n, if we examine individual b's up to about 50,000 and then switch to examining individual k, we have about 250,000 values to examine. With a bit of luck there is only one pair (b, k) that could be the best, so we only have a few million floating point operations, which should run in a few milliseconds.

(What is the problem with x close to an integer? Say we have $n = 7^{1,000,000} - 1$ and $n' = 7^{1,000,000} + 1$. With b = 7, we will get x = 1,000,000 or something very close, but in both cases we don't actually know whether k should be 999,999 or 1,000,000. So we have to try 1,000,000 separately. $7^{1,000,000} then turns out to be too large in the first case).

If you only want to find the best b, k and not the actual remainder, you may be able to do without high-precision arithmetic altogether.
> 1 votes

---
Tags: time-complexity, runtime-analysis, numerical-algorithms, big-o-notation
---


# Question
Title: Need help understanding regular expressions
I was reading up about formal languages (see here: https://pdfs.semanticscholar.org/18b2/d685d5e244a6bfc5a31d312f1e8d322c16a9.pdf) and got confused when I started reading about this expression: 0(0+1)∗+(0+1)∗0

This is how I think it works:

The first and last 0 indicates where these two characters must be present. In other words, the string this expression describes must start and end with one 0. (0+1)\* describes any combination of 0's and 1's (including none at all), and the plus in between each of these sets of brackets ((0+1)\* **+**(0+1) \*) describes a concatenation of these two strings. Therefore, this expression applies to any binary string that begins and ends with a 0.

If this is indeed how the expression works, wouldn't 0(0+1)\*0 achieve the same thing?

(Also, is there a site I can check these sorts of expressions? I tried this expression in sites like regex101.com but it didn't work on any of them. This isn't important, I was just curious)

# Answer
There are three standard regular expression operators: concatenation, alternation, and Kleene closure. (Note that we're talking about regular expressions in the formal mathematical sense, not the random collections of hacks which comprise typical regex libraries.)

These can be thought of as operators on (possibly infinite sets); alternation is set union, and concatenation of two sets is the Cartesian product; in this sense, alternation and concatenation correspond to addition and multiplication. Alternation is generally written as $+$ (although $\mid$ is also common, because of its use in regexes) while concatenation is generally written without an explicit operator symbol, much the same as mulitiplication.

Kleene closure is a unary operator which produces the arbitrary application of any number of concatenation operations on the same set; in effect, an arbitrarily long concatenation of elements of the set. (It includes 0 concatenations, which is always the empty string.) Kleene closure is always written as a postfix $^\*$.

As with algebra, there is a standard operator precedence; Kleene closure binds the most tightly, followed by concatenation, followed by alternation. If you need different binding, you can use parentheses. So $ab^\*+cd^\*$ should be read as $(a(b^\*))+(c(d^\*))$, much as you would read the algebraic expression $ab^2+cd^2$

So the expression you ask about:

$$0(0+1)^∗+(0+1)^∗0$$

is the union of two subexpressions: $0(0+1)^∗$ and $(0+1)^∗0$. The first of these is any binary string starting with $0$ and the second is any binary string ending with $0$, so the union is any binary string which starts or ends with $0$; in other words, any binary string which doesn't both start and end with $1$.
> 1 votes

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


title: Connected but not adjacent vertex

text:
# Question
Title: Connected but not adjacent vertex
Are there specific terms or adjectives in graph theory to name these two situations?

* Two vertices are non-adjacent (disjoint? I have seen that the term "disjoint" is rather used for paths with non-common vertices or edges).
* Two connected non-adjacent vertices (the shortest path or paths connecting them have a lenght $\> 1$).

# Answer
> 2 votes
You've exactly described the first situation, i.e. we indeed say that $u$ and $v$ are non-adjacent. For the second we do the same, but we want to also specify they are in the same component of $G$ which contains them if $G$ is not connected.

These are already simple and well-understood descriptions and there's nothing "more standard". However, you are also free to use your own definitions in your actual use case if it's worth it.

---
Tags: graphs
---


title: Halting problem in EXP-complete

text:
# Question
Title: Halting problem in EXP-complete
I have some troubles understanding why the halting problem is in EXP.
In Wikipedia the following is written:

> It is in EXPTIME because a trivial simulation requires O(k) time, and the input k is encoded using O(log k) bits which causes exponential number of simulations. It is EXPTIME-complete because, roughly speaking, we can use it to determine if a machine solving an EXPTIME problem accepts in an exponential number of steps; it will not use more.

Why does encoding in $O(\log k)$ makes it exponential?
How can we reduce the other problems to our halting problem?

# Answer
You are referring to the following problem: $$H = \\{ (\langle M \rangle, w, t) \mid \text{$M$ accepts $w$ in time at most $t$} \\}$$ where $t$ is binary encoded. You should note this is *not* the (classical) halting problem, but, rather, the *bounded* version of the halting problem. The halting problem itself cannot be complete for $\mathsf{EXP}$ (or any other subclass of the recursive languages).

Now, to answer your question. First, notice that, because $t$ is encoded in binary, the input has length $|\langle M \rangle| + |w| + \log t$. To simulate $M$ on $w$ for $t$ steps we can use a universal TM, which takes time $O(t \log t)$. Since we are doing a worst-case analysis, we can afford to view $|\langle M \rangle|$ as constant. Also, because $t \in O(2^{p(|w|)})$ for some polynomial $p$, $\log t \in O(p(|w|))$. Hence, the input has size $O(|w| + p(|w|))$ while our simulation takes time $O(t \log t) \subset O(p(|w|) 2^{p(|w|)})$ and, in turn, $p(|w|) 2^{p(|w|)} \in 2^{\textrm{poly}(|w|)}$. This proves $H \in \mathsf{EXP}$.

Reducing a problem $P \in \mathsf{EXP}$ to $H$ is also very simple: If $P$ is decidable by $M$ in time bounded by a function $f \in 2^{\textrm{poly}(n)}$, then any instance $x$ of $P$ is a yes-instance if and only if $(\langle M \rangle, x, f(|x|)) \in H$, where $f(|x|)$ is given binary encoded. The time taken by this reduction is dominated by computing $f(|x|)$, which can be performed in time polynomial in $|x|$ (by first converting it to binary and then computing $f(|x|)$ in polynomial time).
> 6 votes

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


# Question
Title: UNDIRECTED HAMCYCLE to HAMPATH reduction
I'll define the problems

> UHAMPATH
>
> Input: A undirected graph G and 2 nodes, s and t
>
> Question: Is there a hamiltonian path from s to t in G?
>
> UHAMCYCLE
>
> Input: A undirected graph G
>
> Question: Is there a hamiltonian cycle in G?

$$UHAMCYCLE \leq\_p UHAMPATH$$

my reduction is as followed $(G) \to (G', s, t)$

```
function(G)

    for each e = (u, v) in E(G)
        G' = G
        add nodes u' and v' to G'
        add edges (u', u) and (v, v')
        s = u'
        t = v'
        if there is a hamilton path from s to t:
            return (G', s, t)

```

Basically if there is a hamilton cycle in G then some edge in $G$ will form a hamilton path in $G'$.

An example to further illustrate the reduction:

```
 Graph G

(a) ---- --(d)
 | \        |
 |   \      |
 |    \     |
 |     \    |
 |      \   |
 |       \  |
 |         \|      |
(b) ------ (c)

Has a clear Hamilton cycle (a, b, c, d).

If we choose edges (a, d)

 Graph G'

(s)--(a) ---- --(d)
      | \        |
      |   \      |
      |    \     |
      |     \    |
      |      \   |
      |       \  |
      |         \|
     (b) ------ (c)--(t)

```

Doesn't have a hamilton path from s to t. However if you choose any other edge such as (a, d) then

```
(s)--(a) ---- --(d)--(t)
      | \        |
      |   \      |
      |    \     |
      |     \    |
      |      \   |
      |       \  |
      |         \|
     (b) ------ (c)

```

$(s \to a \to b \to c \to d \to t)$. Holds.

---

I'm confused whether or not I can use this line:

```
if there is a hamilton path from s to t:
    return (G', s, t)

```

Checking to see if a graph has a hamilton path is NP complete but since we are looking to reduce it to it I think we can?

# Answer
No. Since you are performing a many-one reduction, you have no capabilities beyond the model you are using for the reduction, in this case a poly-time Turing machine. Queries to the problem you are reducing to are only allowed if you are performing a *Turing* reduction, but that is a different notion and (strictly) more powerful than a many-one reduction (and is not what is used when establishing NP-completeness).

Of course, the line *would* be allowed if you managed to prove HAMPATH is solvable in polynomial time. I don't think you will be able to.
> 1 votes

---
Tags: np-complete
---


title: SIMD Utilization

text:
# Question
Title: SIMD Utilization
Can anyone help me understanding this exercise?

We define the SIMD utilization of a program run on a GPU as the fraction of SIMD lanes that are kept busy with active threads during the run of a program. The following code segment is run on a GPU. Each thread executes a single iteration of the shown loop. Assume that the data values of the arrays A and B are already in vector registers so there are no loads and stores in this program. (Hint: Notice that there are 2 instructions in each thread.) A warp in the GPU consists of 32 threads, there are 32 SIMD lanes in the GPU. Assume that each instruction takes the same amount of time to execute.

for (i = 0; i \< N; i++) { if (A\[i\] % 3 == 0) { A\[i\] = A\[i\] * B\[i\]; } }

I know should determine whether this can yield a SIMD Utilisation of 100%. My answer would be YES.

We can achieve this if each element in array A is divisible by three. (Assume A.length is 32. Then ((32\*2)/32\*2))\*100 = 100%)

The master solution agrees to up to this point, but it also says, that we can yield a SIMD Utilisation of 100% if all elements of array A is not divisible by three. My question would be why? My thought is: When all the elements of A is not divisible by three, then each thread would execute one instruction: (32/(32\*2))\*100 = 50% ?

Thank you!

# Answer
> 1 votes
Of course you can easily *use* all the lanes, but then you throw lots of the results away. How you count this is up to you. Do you count calculating the product as utilisation if you then throw the result away? Mostly a matter of opinion.

# Answer
> 0 votes
If this is real program on real GPU, then CUDA f.e. may perform multiplication always and then conditionally copy the result to A\[i\]. It may be more efficient to perform 2-4 extra instructions when A\[i\]%3!=0 rather than perform conditional jump around unneeded statements.

So probably the point is that you forgot about predicated statement execution.

---
Tags: computer-architecture, digital-circuits
---


title: Can you determinize an NFA in PSPACE?

text:
# Question
Title: Can you determinize an NFA in PSPACE?
**QUESTION**

Given some NFA $A$, can you simulate the determinization of it (using Subset-Construction for example) while remaining in $PSPACE$?

**MORE DETAILS**

I'm asking this as I want to be able to construct $\overline A$ (the complement of $A$) in poly-space complexity.

More specifically, I want to receive $\left \<A,w \right \>$ as input ($A$ is an NFA) and decide if $w \in \overline A$. So I want to construct $\overline A$ and simulate (in poly-space) $\overline A$ on $w$.

**MY ATTEMPTS**

I know that determinizing an NFA (using Subset-Construction) can blow up exponentially. **But**, I thought that the determinization and/or the simulation can happen "on the fly", where each step overrides the previous one.

Other then this thought, I can't manage to develop it into an actual algorithm (if it's at all possible).

**Thank you.**

# Answer
> 1 votes
The subset construction can be computed (and negated) in polynomial space. Remember that the output doesn't count as part of the space usage in bounded space computation.

Determinization can exponentially increase the number of states: the language of $0$$1$strings such that the $k$th-from-last character is $0$ can be recognized by an NFA with something like $k+1$ states, but any DFA for that language has at least $2^k$ states.

So determinizing doesn't give you a polynomial space algorithm to determine if an NFA accepts its input. But you can simulate all computation paths of the NFA simultaneously: as you read the input, just keep track of the set of states the automaton could be in, and see if that set includes an accepting state once you've read the whole input.

---
Tags: complexity-theory, computability, finite-automata, space-complexity
---


title: What are degenerate polygons?

text:
# Question
Title: What are degenerate polygons?
What are degenerate polygons? How does one check whether a given pair of polygons is degenerate or not?

# Answer
> 12 votes
A polygon is *degenerate* if some of its vertices lie on each other. e.g the triangle (0,0),(0,1),(0,0) is degenerate. It has 3 sides, and 3 vertices, but two of vertices repeat. It's possible to repeat a vertex multiple times (for example (0,0),(0,0),(0,0) is another degenerate triangle). By definition, checking whether a polygon is degenerate or not is easy.

But what are the uses of degenerate polygons? One application from graphic acceleration (3D drawing) is as follows:

In 3D drawing GPUs normally use triangulation to render images. The (simple) reason for using triangles is because they are simplest possible 2D objects so don't need much hardware.

If we want to draw a complex 3D image, by this GPU limitation, we have to decompose it into multiple triangles. But if we call the GPU to render each triangle separately, it would be very slow (because of the number of calls). So the triangle strip is used to reduce the number of calls to the GPU. A good explanation of triangle strips can be found on Microsoft Documentation: Triangle Strips, also you can see the wiki for: Triangle Strip.

But the problem arises when we want to draw two separate objects in one strip. In this case degenerate triangles help. The GPU can detect the degenerate triangles and skip their drawing. So we can connect two separate strips with one degenerate triangle.

In general if we have $n$ different components, such that we already have their corresponding triangle strips, we can draw them all by just one call to the GPU. This causes to extra memory usage, but it is a trade off between the number of calls to the GPU for rendering and the overhead of using an extra, degenerate triangle.

# Answer
> 0 votes
A degenerate polygon is one that has zero area. The answer chosen above does not fully define a degenerate polygon. Consider the case of a square with two identical vertices. This could be defined as one or two non-degenerate triangles.

# Answer
> 0 votes
As others have noted, it depends. Generally speaking, a polygon is non-degenerate if it has no anomalous points, but this just pushes the problem back one step; what is "anomalous"?

The real answer is that a polygon is degenerate if it violates the specification. The slightly rude answer is that a polygon is degenerate if it is an edge case which your algorithm can't handle.

Here's an example from the world of GIS. The OGC Simple Features Specification has a very careful definition of what makes a polygon "valid". Quoting from Section 6.1.11.1:

> The assertions for Polygons (the rules that define valid Polygons) are as follows:
>
> a) Polygons are topologically closed;
>
> b) The boundary of a Polygon consists of a set of LinearRings that make up its exterior and interior boundaries;
>
> c) No two Rings in the boundary cross and the Rings in the boundary of a Polygon may intersect at a Point but only as a tangent, e.g. $$\begin{align\*} & \forall P \in \hbox{Polygon}, \forall c\_1, c\_2 \in \hbox{P.Boundary}, c\_1 \ne c\_2,\\ & \forall p, q \in \hbox{Point},\\,p,q \in c\_1, p \ne q,\\ & \left\[ p \in c\_2 \right\] \Rightarrow \left\[ \exists \delta \> 0 | \left\[\left|p-q\right|\<\delta\right\]\ \Rightarrow \left\[ q \not\in c\_2 \right\] \right\] \end{align\*}$$;
>
> Note: This last condition says that at a point common to the two curves, nearby points cannot be common. This forces each common point to be a point of tangency.
>
> d) A Polygon may not have cut lines, spikes or punctures e.g.: $\forall P \in \hbox{Polygon}, P = \hbox{P.Interior.Closure}$;
>
> e) The interior of every Polygon is a connected point set;
>
> f) The exterior of a Polygon with 1 or more holes is not connected. Each hole defines a connected component of the exterior.
>
> In the above assertions, interior, closure and exterior have the standard topological definitions. The combination of (a) and (c) makes a Polygon a regular closed Point set.

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


# Question
Title: how to prove that log(n!) >= c n log(n) for some c >0?
as reading the book Algorithms by Dasgupta, C.H Papadimitriou. on Page 63.

> And it is well known that $\log(n!)≥c\cdot n\cdot\log n$ for some $c \> 0$. There are many ways to see this. The easiest is to notice that $n! \ge (n/2)^{(n/2)}$ because $n! = 1 · 2\cdot\cdots\cdot n$ contains at least $n/2$ factors larger than $n/2$; and to then take logs of both sides. Another is to recall Stirling’s formula.

Can someone help to find the proof on $n! \ge (n/2)^{(n/2)}$, or how should we prove it ourselves? As we take log on both side, it became (assuming that its base is some number constant) $\log(n!)$ on the left side, on the right, it became $\log\left((n/2)^{(n/2)}\right)$, further simplify $(n/2)\log(n/2)$ --\> $(n/2)\log(n^{-2})$, then finally on the right side: $(-n)\log(n)$. Then we completed the proof (?)

I have two questions, is the proof of $n! \ge (n/2)^{(n/2)}$ corrected? If so, how can we argue back to "$\log(n!)≥c\cdot n\cdot\log n$ for some $c \> 0$", if not, how can we proof that "$\log(n!)≥c\cdot n\cdot\log n$ for some $c \> 0$"?

# Answer
> ... further simplify $(n/2)\log(n/2)$ --\> $(n/2)\log(n^{-2})$, ...

This is wrong. In fact, for $n\ge 3$, $n^{\log\_3 2}\ge 2$, so \begin{align} (n/2)\log(n/2)&=(n/2)(\log n-\log2)\\ &\ge (n/2)\cdot\left(1-\log\_3 2\right)\log n\\ &=\left(1-\log\_3 2\right)/2\cdot n\cdot \log n, \end{align} and $\log(n!)\ge \left(1-\log\_3 2\right)/2\cdot n\cdot \log n$ also holds for $n=1,2$, which completes the proof.
> 2 votes

# Answer
$n! = n \cdot (n-1) \cdot ... \cdot 1 \ge n \cdot (n-1) \cdot ... \cdot (n/2) \ge (n/2)^{(n/2)}$

so

$\log(n!)≥c\cdot n\cdot\log n$ for $c \ge 1/2$
> 3 votes

---
Tags: algorithms, check-my-answer
---


# Question
Title: Is the reduction for HAMPATH to HAMCYCLE and UHAMPATH to UHAMCYCLE the same?
HAMPATH/UHAMPATH is A directed / undirected graph G and 2 nodes s and t and is there a hamilton path from s to t?

Likewise with HAMCYCLE/UHAMCYCLE but has a hamilton cycle on $G'$

The reduction for directed is

$HAMPATH \leq\_p HAMCYCLE$

```
function(G, s, t)
    G' = G
    add node t' to G'
    add edges (t, t') and (t', s)
    return (G')

```

$(\Rightarrow)$If $(G, s, t) \in HAMPATH$, then $\\{(s, v\_1), \dots, (v\_n, t)\\}$ is a hamilton path in $G$ from $s$ to $t$ and our reduction for $G'$ has a path $\\{(s, v\_1), \dots, (v\_n, t), (t, t'), (t', s)\\}$ which is a hamilton cycle $(G') \in HAMCYCLE$

$(\Leftarrow)$ If $(G') \in HAMCYCLE$, then $\\{(s, v\_1), \dots, (v\_n, t), (t, t'), (t', s)\\}$ is a hamilton cycle in $G$. Remove the edges $(t, t')$ and $(t', s)$ and we are left with a hamilton path $\\{(s, v\_1), \dots, (v\_n, t)\\}$, $(G, s, t) \in HAMPATH$

---

Wouldn't this reduction also work for the undirected version i.e. $UHAMPATH \leq\_p UHAMCYCLE$? I've seen on the internet another reduction where they add another node and add an edge between every vertex in G for $G'$ but wouldn't this simpler version work as well?

# Answer
Your reduction is correct. However, the standard Hamiltonian path problem does not specify the endnodes $s$ and $t$, which is a bit different from your definition. This is possibly why the internet does not use your simple reduction.
> 0 votes

---
Tags: np-complete
---


# Question
Title: Can a CPU be replaced without interrupting the processes running on it?
When I need to replace the CPU of my computer, I turn it off, replace the hardware, then reboot it. But what if you need to replace the CPU (in a single CPU machine) without stopping the processes running on it?

Is that possible, and if so, how?

*This is a theoretical question. It doesn't matter if the procedure is complicated and impractical or cost-intensive.*

# Answer
On a multitasking operating system, any process can be paused while other processes are executing. When a process is paused, all of its data is in RAM, outside the CPU. The CPU itself only contains a small amount of data in registers.

On a multiprocessor system, this same mechanism also allows processes (or more precisely threads) to migrate from one processor to another. As long as the processors are connected to the same RAM, a processor switch is no more complicated than a context switch.

The operating system kernel can save the few pieces of data that it normally stores in registers to a fixed place in RAM, and can make its startup code read this data back. All major multiprocessing operating systems can in fact do that: it's called suspend to RAM.

What prevents replacing the CPU during a suspend-to-RAM is not a difficulty with software architecture, but with hardware architecture. It is possible on some expensive servers, but not on a consumer device.

You can actually replace your CPU and restart with your old processes, even on a computer where this requires turning off the power, by using suspend-to-disk. Take all the data in RAM and save it to disk. This is similar to swapping. The kernel needs to do more work, because it has to power down all peripherals and restore their state afterwards. But again there is no extra theoretical difficulty, just a lot of practical difficulties in writing drivers.
> 3 votes

---
Tags: computer-architecture
---


# Question
Title: What is the time complexity of a binary multiplication using Karatsuba Algorithm?
My apologies if the question sounds naive, but I'm trying wrap my head around the idea of time complexity.

In general, the Karatsuba Multiplication is said to have a time complexity of `O(n^1.5...)`. The algorithm assumes that the addition and subtraction take about `O(1)` each. However, for binary addition and subtraction, I don't think it will be `O(1)`. If I'm not mistaken, a typical addition or subtraction of two binary numbers takes `O(n)` time.

What will be the total time complexity of the following program then that multiplies two binary numbers using **Karatsuba Algo** that in turn performs binary addition and subtraction?

```
long multKaratsuba(long num1, long num2) {
 if ((num1>=0 && num1<=1) && (num2>=0 && num2<=1)) {
   return num1*num2;
 }

 int length1 = String.valueOf(num1).length(); //takes O(n)? Not sure
 int length2 = String.valueOf(num2).length(); //takes O(n)? Not sure

 int max = length1 > length2 ? length1 : length2;
 int halfMax = max/2;

 // x = xHigh + xLow
 long num1High = findHigh(num1, halfMax); // takes O(1)
 long num1Low = findLow(num1, halfMax); // takes O(1)

 // y = yHigh + yLow
 long num2High = findHigh(num2, halfMax); // takes O(1)
 long num2Low = findLow(num2, halfMax); // takes O(1)

 // a = (xHigh*yHigh)
 long a = multKaratsuba(num1High, num2High);

 // b = (xLow*yLow)
 long b = multKaratsuba(num1Low, num2Low);

 //c = (xHigh + xLow)*(yHigh + yLow) - (a + b);
 long cX = add(xHigh,xLow); // this ideally takes O(n) time
 long cY = add(yHigh,yLow); // this ideally takes O(n) time
 long cXY = multKaratsuba(cX, cY);
 long cAB = add(a, b) // this ideally takes O(n) time
 long c = subtract(cXY, cAB) // this ideally takes O(n) time

 // res = a*(10^(2*m)) + c*(10^m) + b
 long resA = a * (long) Math.pow(10, (2*halfMax)); // takes O(1)
 long resC = c * (long) Math.pow(10, halfMax); // takes O(1)
 long resAC = add(resA, resC); // takes O(n)
 long res = add(resAC, b); // takes O(n)

 return res;
}

```

# Answer
You're mistaken. The analysis of the Karatsuba algorithm takes addition and subtraction into account.

If you analyze your pseudo-code, you can see that you have exactly 3 recursive function calls with arguments of size $n/2$, and all other operations like addition, subtraction, extracting the higher and lower bits, ..., run in $O(n)$.

Therefore you get the recursion $T(n) = 3 \cdot T(n/2) + O(n)$ for the complexity, which gives the following according to the Master theorem: $$T(n) = \Theta(n^{\log\_2 3}) = \Theta(n^{1.58...})$$

---

Fun fact: even if you assume that all the bitwise operations (addition, subtraction, ...) take $O(1)$, the code will still have the same complexity. Since the number of calls to the three subproblems dominates the other work. But I doubt, that any book/lecturer would assume that the bitwise operations are constant, since the whole point of the algorithm is that you want to multiply large numbers.

---

Btw, you have some small errors in your pseudo-code/analyze. E.g. here:

```
long resA = a * (long) Math.pow(10, (2*halfMax)); // takes O(1)

```

You want to multiply with a power of 2, to make it efficient (since you are working with binary numbers). And even corrected it will not run in $O(1)$, because you need to copy/move $O(n)$ bits. So this line will also run in $O(n)$.
> 4 votes

---
Tags: algorithms, algorithm-analysis, time-complexity, arithmetic
---