# Question
Title: Decidable questions of undecidable problems
Even if there is no general algorithm to decide if any program will halt, but there could be properties or meta-questions about the programs that is decidable. For example, given program $A$ and a program $B$ that is obtainable from program $A$ by adding in finite steps of calculations that halts. So if $A$ halts, $B$ definitely halts (and vice versa). A trivial example is $B = A$.

The question "Do $A$ and $B$ have the **same** behaviour?" is decidable (they either both halt or run forever), even if we do not know whether $A$ or $B$ halts or not.

My question: Is it true that, for any program $A$, there is always a non-trivial program $B$ such that there is a decidable meta-question about the duo $(A, B)$? (Non-trivial means $B ≠ A$ and $B$ is not obtainable from $A$ via adding extra finite steps that halts. In general, it means $B\neq f(A)$, where $f$ is a computable function.)

I wonder if there is a field of research on this type of meta-problems?

# Answer
> 0 votes
I'm not convinced by your setup. All programs are finite sequences of steps, so the equivalence of $A$ and $B$ in your first paragraph isn't decidable: they're equivalent iff $B$ halts on every input that $A$ halts on.

Your main question seems to be under-specified in a way that makes it trivial. The empty langauge is a decidable problem about pairs $(A,B)$. For any computable function $f$, the language $\\{(A,B)\mid B=f(A)\\}$ is decidable. But I suspect that any attempt to make the problem more precise will fail because of the issue I raised above.

# Answer
> 0 votes
My interpretation:

There is no decidable language $L = \\{(A,B)|B = f(A)\\}$, where $f$ is non-computable and not semi-computable.

Proof: If $L$ was decidable there would be a Turing-Machine $T$ that decides it. We select $T$ in such a way that it has a single reject and a single accept state. This is possible since our language is decidable. Now we look at a specific Input $A$. We construct the Turing-Maschine $T\_A$ that prints $A$ out and then runs $T$. $T\_A$ basically "expects another input B". We know want to find an input to $T\_A$ such that $T\_A$ accepts. We can do that buy. Iterating through all strings $B$ and run $T\_A$ on $B$. Since $T\_A$ always halts we will either find a $B$ that results in an accept state or the procedure will run forever. Thus $f$ is semi-computable. This is a contradiction ans hence the statement is true.

Feedback? Is the proof correct?

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


# Question
Title: Optimal Selection of Non-Overlapping Jobs
I'm trying to find what the family of problem is - as well as an approach - for the following:

I have a set of tasks T = \[t1, ..., tn\] to do, each of which has a corresponding reward ri. Each task takes place during a fixed interval - ie: task 1 is from times 1-4, task 2 from 2-5, and task 3 from 9-15. This means that I would have to pick either task 1 or 2 depending on which is more valuable, and then task 3 which does not conflict with either of the previous.

I'd like for this to scale to `n` tasks, and also to `m` "CPU's" - where more than one task can be executed in parallel. This reminds me of the knapsack problem, but maybe an interval graph would provide a better approach?

Any suggestions on how to approach this problem, or any relevant references?

# Answer
> 1 votes
If you consider each task as a node of a graph, and each conflict as an edge, this is a weighted maximum independent set problem.

It is NP-hard, but you should get good results with a mixed integer programming solver, such as CBC.

---
Tags: algorithms, optimization, sets, scheduling, knapsack-problems
---


# Question
Title: What properties of a discrete function make it a theoretically useful objective function?
A few things to get out of the way first: I'm not asking what properties the function must have such that a global optimum exists, we assume that the objective function has a (possibly non-unique) global optimum which could be theoretically found by an exhaustive search of the candidate space. I'm also using "theoretically useful" in a slightly misleading way because I really couldn't understand how to phrase this question otherwise. A "theoretically useful cost function" the way I'm defining it is:

> A function to which some theoretical optimisation algorithm can be applied such that the algorithm has a non-negligible chance of finding the global optimum in less time than exhaustive search

A few simplified, 1-dimensional examples of where this thought process came from:

Here's a function which, while not being convex or differentiable (as it's discrete), is easily optimisable (in terms of finding the global maximum) with an algorithm such as Simulated Annealing.

Here is a function which clearly cannot be a useful cost function, as this would imply that the arbitrary search problem can be classically solved faster than exhaustive search.

Here is a function which I do not believe can be a useful cost function, as moving between points gives no meaningful information about the direction which must be moved in to find the global maximum.

The crux of my thinking so far is along the lines of "applying the cost function to points in the neighbourhood of a point must yield some information about the location of the global optimum". I attempted to formalise (in a perhaps convoluted manner) this as:

> Consider the set $D$ representing the search space of the problem and thus the domain of the function and the undirected graph $G$, where each element of $D$ is assigned a node in $G$, and each node in $G$ has edges which connect it to its neighbours in $D$. We then remove elements from $D$ until the objective function has no non-global local optima over this domain and no plateaus exist (i.e. the value of the cost function at each point in the domain is different from the value of the cost function at each of its neighbours). Every time we remove an element $e$ from $D$, we remove the corresponding node from the graph $G$ and add edges which directly connect each neighbour of $e$ to each other, thus they become each others' new neighbours. The number of elements which remain in the domain after this process is applied is designated $N$. If $N$ is a non-negligible proportion of $\\#(D)$ (i.e. significantly greater than the proportion of $\\#(\\{$possible global optima$\\})$ to $\\#(D)$) then the function is a useful objective function.

Whilst this works well for the function which definitely is useful and the definitely not useful boolean function, this process applied to the random function seems incorrect, as the number of elements that would lead to a function with no local optima IS a non-negligible proportion of the total domain.

Is my definition on the right track? Is this a well known question I just can't figure out how to find the answer to? Does there exist some optimisation algorithm that would theoretically be able to find the optimum of a completely random function faster than exhaustive search, or is my assertion that it wouldn't be able to correct?

In conclusion, what is different about the first function that makes it a good candidate for optimisation to any other functions which are not.

# Answer
No, I don't think your formalization is heading in a useful direction. It seems convoluted and focused on one particular algorithm, but there might be other optimization algorithms that you haven't considered.

I don't expect there to be a useful characterization of which objective functions can and can't be optimized effectively. It's a notoriously hard problem. There is work on the literature on identifying classes of problems that can provably be optimized efficiently (e.g., convex objective functions, linear programming, semidefinite programming), but the reality is that what we can prove falls short of what empirically often seems to be feasible in practice.

For instance, what you're looking for is at least as hard as the P vs NP problem, since every NP problem can be expressed as an optimization problem; and I don't expect there to be a simple characterization of which NP problems are NP-complete.
> 0 votes

---
Tags: optimization
---


# Question
Title: Cancellation of inequalities in floating point arithmetic
In finite precision floating point arithmetic the associative property of addition is not satisfied. This is, it is not always the case that $$(a+b)+c=a+(b+c)$$ Even $a=(a+b)-b$ is not always true.

To prove that $x+y\<z$ is equivalent to $x\<z-y$ with real numbers we can add $-y$ on both sides of $x+y\<z$ to get $(x+y)-y\<z-y$ and then from this $x=x+(y-y)\<z-y$. But I can't repeat the last step for floating point.

> **Question 1:** Are the inequalities $x+y\<z$ and $x\<z-y$ equivalent in finite precision floating point arithmetic?

> **Question 2:** Are the inequalities $x+y\leq z$ and $x\leq z-y$ equivalent in finite precision floating point arithmetic?

I was too hasty and updated without checking properly. What I really indented to ask is if the breaking of the equivalence could be as drastic as:

> **Question 3:** Could we have $x+y\<z$ and $x\>z-y$?

Possibly there are already answers below for this. If so, I will check them when I get a chance and select the answer.

---

**Motivation:** There is that interview problem that given an ordered array of numbers and a threshold it asks for the number of pairs of numbers of the array which sum is not larger than the threshold. Possible solutions aside, I wanted to understand the particular point of the dangers of switching between testing $x+y\<z$ (and also $\leq$ depending on which variant of the problem is presented) and testing $x\<z-y$ (or $\leq$).

# Answer
Consider the case that x and y hold the largest representable value for the current type, and z is positive infinity. By the rules of floating point arithmetics, x + y is now infinity, which isn't less than infinity. On the other hand, z - y is also infinity, which the largest representable value is less than.

Another example would be when x is very small negative, and y = z and much larger in magnitude than x. Then x + y = y = z, but z - y = 0, which is larger than x.

The examples work for your second question as well if you flip the signs of all numbers - `!(l > r)` is nearly equivalent to `l <= r`. NaNs break the equivalence, but those aren't useful as examples to your question anyways.
> 1 votes

# Answer
Take x=1+u, y=1+2u, z=2+4u, where u is the value of the lowest mantissa bit. x+y = 2+3u gets rounded up to 2+4u, so x+y\<z is false. z-y = 2+4u - (1+2u) = 1+2u, so x \< z-y is true. That’s a counter example for the first case.

With x=1+3u you get a counter example for the second case.
> 1 votes

---
Tags: floating-point
---


# Question
Title: Help with context free grammar excercise
So, I have an exercise in which I have to write a context free grammar for this language:

$$L = \\{x \in L(a^∗b^∗c^∗) : |x|\_a \> |x|\_c; |x|\_b \> 0; |x|\_c ≥ 0\\}$$

meaning every string with any number of $a$'s, $b$'s and $c$'s in that order, with the amount of $a$'s greater than the amount of $c$'s and the amount of $b$'s greater than zero.

I am having trouble figuring out the rule that makes sure there are more $a$s than $c$s.

I have: $$\begin{align}S&\to aABC | ab\\ A&\to aA | a\\ B&\to bB | b\\ C&\to cC | c\\ \end{align}$$ I know this is wrong because I should be adding an $a$ every time I add a $c$, but I don't know how to write that.

# Answer
> 1 votes
I think you can do it in this way

$$\begin{align} X&\to A\ |\ aXc\ |\ aAc\\ A&\to aA\_t\\ A\_t&\to aA\_t\ |\ B\\ B&\to bB\_t\\ B\_t&\to bB\_t\ |\ \epsilon\\ \end{align}$$

Here $X$ can choose to do the first transformation, if there are not going to be any $c$s. $X$ can do the second transformation many times to add an initial chunk of the same amount of $a$s and $c$s, or do the third transformation to put a last pair of an $a$ and a $c$.

In that third case, it goes to $A$ which puts one extra $a$ and goes to $A\_t$, which can put even more $a$s or go to put $b$s.

Then $B$ puts one $b$ and goes to $B\_t$, which puts as many more $b$s as wanted or terminates.

But check it. This is the first ever context free grammar rules that I write in my life.

---

Shorter rules by *nir shahar*

$$ \begin{align} S&\to AB\ |\ aSc\\ A&\to aA\ |\ a\\ B&\to bB\ |\ b \end{align} $$

---
Tags: context-free, formal-grammars
---


title: Size of a context-free grammar

text:
# Question
Title: Size of a context-free grammar
Is there a formal definition for a size of a context-free grammar? The only definition I have seen so far is on this wiki page:

> The size of a grammar is the sum of the sizes of its production rules, where the size of a rule is one plus the length of its right-hand side.

So, how does one define the size of a production rule's RHS?

For example, if I define my CFG as:

```
S : A
A : 'a' B | A
B : 'b'

```

What is the size of the production rule A?

# Answer
What is your intended application. The article you cited does give a definition of size. A production rule

T -\> R

has size |R|+1, where |R| is the number of symbols in R. A more precise definition can be found on page 9 of this document.

This notion of size is meant to compare different grammars that produce the same language. In particular, in the article you cited, the notion of size is used to see that under grammar transformations, the size of the grammar can explode.
> 3 votes

# Answer
In formal language theory, the exact definitions of terms tend to vary.

For instance, context-free grammars as introduced by Chomsky couldn't have empty right-hand sides. They couldn't produce the empty string. Quite a few articles followed this; later on, it became more common to allow this. Usually, the difference is of little or no consequence, but sometimes, it matters.

The same is true for the size of a grammar. In most applications, the exact definition chosen doesn't make much of a difference; in some applications, it does.

This is why articles and textbooks on formal language theory always state their definitions explicitly. So just pick one that suits your needs, preferably one that already appears elsewhere.
> 0 votes

---
Tags: terminology, formal-grammars
---


title: Circuits and formulas for Clique

text:
# Question
Title: Circuits and formulas for Clique
Is it correct to say that the Clique Problem is in $P$ iff there exists a family of Boolean circuits $C$ to decide Clique whose sizes are bounded by a polynomial? And based on this question, does that imply that there exists an equivalent set of Boolean formulas $F$ to decide Clique whose sizes are bounded by a polynomial? And if there is such an $F$, would there be correct derivations based on propositional logic axioms from any member of $F$ to the corresponding large naive formula for Clique?

# Answer
I'm afraid that the answer to all your questions is false:

* There are languages decided by constant size circuits which aren't decidable.
* It is conjectured that $\mathsf{NC^1} \neq \mathsf{P}$.
* It is conjectured that $\mathsf{NP} \neq \mathsf{coNP}$.
> 2 votes

---
Tags: complexity-theory, logic, propositional-logic
---


title: Are there any non-finite automata?

text:
# Question
Title: Are there any non-finite automata?
In automata theory, we all read automata as finite automata, from the very beginning. What I want to know is, why are automata finite? To be clear, what is it in an automaton that is finite - the alphabet, language, strings made with regular expressions, or what? And are there (in theory) any non-finite automata?

# Answer
> 34 votes
All automaton models you'll typically encounter are finitely represented; otherwise there would be uncountably many, which means they are not captured by Turing-complete models. Or, in CS-think, they'd be useless¹.

"Finite automata" are called finite because they only have a finite set of *configurations* (the input string aside). Pushdown automata, for instance, have a stack that can have arbitrary content -- there are infinitely many possible configurations.

---

Nota bene: Configurations of PDAs are still finitely represented! In fact, any computational model that falls inside Turing-computability has to have finitely representable configurations, otherwise TMs wouldn't be able to simulate them.

---

1. I consciously disregard hypercomputation here for the purpose of this question.

# Answer
> 35 votes
The full name is "finite **state** automata". The crucial part is that the state of the automaton can be fully characterized by an element of some finite set of discrete states. This means that if the (relevant) state of the automaton involves a real-valued variable, there is an infinite number of potential states (putting aside the finiteness of floating point representations), and the automaton is not finite.

This might not ever happen in theoretical computer science, but it's not too exotic in the domain of modeling real number sequences. Hidden Markov Models can be used to model a number sequence as the output of a probabilistic system consisting of one output filter for each state of a (discrete, finite) Markov model with unobservable states. The filters compute the next real-valued output from a vector of the previous outputs ("autoregressive" model), but the underlying Markov model is finite since its transition probabilities only depend on the current Markov state.

However, this article (full text) develops a variation where the transition probabilities also depend on the real-number vector of prior outputs. The state of this system is the combination of a discrete Markov state and a tuple of real numbers ("mixed state Markov model"), hence it can be in an infinite number of different states.

In short, non-finite automata are theoretically well-defined, and occasionally even encountered.

# Answer
> 19 votes
In a finite automaton, there is quite a bit of finiteness: the number of states, the size of the underlying alphabet, and the lengths of the strings accepted by the machine.

You can certainly relax the finiteness condition on these by allowing, say, the machine to have infinitely many states but if you do, the resulting machine becomes uninteresting, in the sense that such machines can be designed to accept any languages at all.

# Answer
> 11 votes
In fact, in automata theory (which departs a lots from the origins of Kleene, Rabin and Scott), there are many forms of automata that are not finite. This arises for several reasons.

**Pushdown automata**, for instance, are automata that have an infinite set of configurations (these have a finite number of states, but the reality is that these should be thought as 'infinite automata').

In the same vein, there ar other examples of infinite automata for which the state space is infinite, but with a lot of structure. For instance one considers the class of automata that have as state space a (finite dimension) vector space, and as transition functions linear maps (plus some initial an final things). These are known as **weighted automata** over a base field (due to Schützenberger in 61). These can be minimized and tested for equality. Other examples include **register automata** (these automata have a finite set of registers, and work over an infinite alphabet: these can compare letters with registers and store letters in registers), and the more modern form of **nominal automata** (that have the same expressiveness, but have better foundations and properties). Emptiness of such automata is decidable.

But, even for studying finite state automata, it makes sense to talk about infinite automata. Indeed, consider the **category of finite state deterministic automata** that accept a fixed given language L, equipped with the standard notion of automata morphism, then this category fails to have an initial and a final object. However, if you live in the category of all deterministic (say countable) automata, then there is an initial object (the automaton that has as states $A^\*$, as initial state the empty word, when it reads letter $a$ in state $u$ it goes to state $ua$, and a state is accepting if it belongs to L). There is also a final object (that has as states languages!). The existence of these two objects are one way to explain at high level why deterministic automata can be minimised and is tightly linked to the Myhill-Nerode congruence.

To conclude, there are infinite automata, but the models that are first studied in a lecture are always the finite state ones.

# Answer
> 2 votes
I think the question is assuming the conclusion that there are no infinite state automata when there are, they just aren't worth bringing up.

In Automata Theory, there is a hierarchy of powers of different virtual models. The one I learned had 4 (that I remember, it has been some time), the one I found on Wikipedia has 5. The weakest in either finite state automata, and the strongest is Turing machines. There is a some concept of a level more powerful than Turing machines that is loosely called hypercomputation. Many different descriptions of virtual machines fall into one of these levels. Turing machines are especially known for numerous models all having the same level of computational power.

An infinite state automata, at least one formally defined, will fall into one of these levels. There may something a little interesting in showing how a certain rigorous definition of an infinite state automata fits into one of these levels, but other than that, it wouldn't be of much use given there are far more well studied virtual machines representing each level. It's similar to how there isn't much interest in a billion tape Turing machine, since it would be no more powerful than a single tape Turing machine but more complicated to deal with.

Now, if you happened to find an infinite state automata that wasn't equivalent to an existing level of the hierarchy, that might be interesting. But without that, infinite state automatas are already captured within the existing hierarchy, and given the added complications of dealing with infinity, we just avoid them in the same way we avoid any overly complicated Turing machine model.

# Answer
> 2 votes
The (naive) infinite version of deterministic finite state machine is *too powerful*. Such a thing would be capable of "memorizing" any language at all, so there is not much to be learned from considering them.

For example, over a binary alphabet, consider an automaton in the form of a complete binary tree of infinite height. Every possible string you could consider as input corresponds uniquely to a node of the tree, so you can construct a decider for any language at all simply by making the corresponding nodes accepting states.

# Answer
> 0 votes
There is such a concept as an "infinite" automata, however, they are not normally as interesting as finite automata practically to software or hardware designers. There is some research and research papers on infinite automata, but I'll give a simple (and practical example) below, and you may see why no-one talks about infinite automata except for perhaps, mathematicians, but I dare say some of them have interesting properties.

The counter:

Given some event you want to count, then the infinite automata yields the output, where for the sake of simplicity it's state directly maps to the traditional output symbol in an alphabet (giving the answer). Both state and output symbol space is infinite in this case, and is the set of natural numbers \[0..infinity)

```
count = 0

count --- [event] ---> count + 1

```

Essentially this is "counting". It is however *also* a state machine, but it's so trivial that we say "counter".

(Note that computers may a have limit on the size of the counter, but the premise of the machine is still valid.)

Things may get more interesting with real values and complex mathematical functions, for most people, these are mathematical functions, and not state machines. The marking thing to note about a state machine, however, is that they can be in a given state, and change state based on some external input, like the counter above, and they do so over time through a sequence of inputs.

# Answer
> 0 votes
Infinite automata, that is, like finite automata but with an infinite number of states, are a particular kind of transition system. Infinite transition systems of various kinds are commonly used to describe the behaviour of discrete systems.

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


# Question
Title: Finding connected components without building the graph first
What are good algorithms for finding connected components in a graph defined by a set of elements `X`, where each `x` in `X` is itself a set of features `f` and a Boolean connectivity function (defined by generalization/subsumption) `c(x,x')`?

`c(x,x') = True if generalizes(x,x') or generalizes(x',x) else False`

`generalizes(x,x') = True if x-x'==set([]) else False`

The point is not to build the entire graph (partially ordered set) in the first place but to use `c(x,x')` as an oracle to query while computing component labels on the fly.

This can also be seen as finding weakly connected components of the DAG given by the partial order of the subset relation, but I think perhaps for this algorithm it could be better to have `c` return `True` more often, so I view the DAG as undirected and then define the task.

# Answer
> 1 votes
I have an idea for the algorithm that's slightly better than a simple dfs based on the fact that the relationship is transitive. From transitivity follows that $a \sim b \land b \sim c \Rightarrow a \sim c$. For our undirected graph this implies that every node in a connected component is connected to every other node. This yields following simple algorithm:

```
component = 1
mark = array of size n; initialized with 0
for i = 1 to n:
  if mark[i] == 0:
    mark[i] = component
    for j = i+1 to n:
      if i != j and mark[j] == 0 and c(X[i],X[j]):
        mark[j] = component
    component += 1

```

$mark$ now assigns every node a component. The runtime of the algo is $O(cn)$ where $c$ is the number of components. This would usually considerably faster than a dfs. Notice in the worst case every node is its own component leading to $O(n^2)$. But if this even occurs depends on the properties of your $c(x,y)$ function.

EDIT: The algorithm doesn't work since c(x,y) isn't transitive. My bad.

# Answer
> 1 votes
Okay I'm writing another answer for the sake of tidiness. I suppose that the elements of your sets are integers. Otherwise one could just use pointers to the items.

```
// INPUT
sets    := vector of your sets
// BUILDING INVERTED INDEX
sets_of := map of int (an item) to vector of int (indices of all sets containing it)
for i, set in enumerate(sets):
   for item in set:
      sets_of[item].add(i)
// GETTING THE POSSIBLE SUPERSETS
possible_supersets := array (id of a sets as indices) of maps (see below)
for i, set in enumerate(sets):
   possible_supersets[i] := map int (id of a set) to int (occurrence count)
   for item in set:
      for j in sets_of[item]:
         if j != i:
            possible_supersets[i][j]++
// VERIFYING SUPERSETS
uf := union-find-structure of size length(sets)
for i, set in enumerate(sets):
   for j in possible_supersets[i]:
      if possible_supersets[i][j] == length(set):
         uf.unify(i,j)

```

`uf` now contains all your components. The first phase takes $O(N)$ time, where $N = \sum\_{i=1}^n |ith-set|$. The time taken by the second phase is a lot harder to estimate. Let's assume $a$ is the average number of sets an item is contained in. Now the second phase would have an approx. runtime of $O(Na)$ assuming amortized $O(1)$ for hash-maps.

This algo has actually a better runtime than the last one I proposed because I didn't include how long it takes to calculate $c(x,y)$ and the described algo now takes care of set intersections itself.

---
Tags: dag, partial-order, connected-components
---


# Question
Title: Is there a total binary computable function that specifies Turing machines with nonempty domain?
I am working through Bridge's computablity book and I came across this problem that does not have an answer. I don't know how to precede, any help is much appreciated.

# Answer
My Tip for you: Check out the second recursion theorem and plug $\Psi$ in for $Q$.

If you can't continue on you own here is my solution:

The second recursion theorem implies that there is such a $m$ that: $$\varphi\_m \simeq \lambda n.\Psi(m,n)$$

($\simeq$ means that the left and right expression are equal for every input $n$ equal and if an expression in undefined for a certain $n$ this is also true for the other expression)

Case 1: $\Psi(m,n) = 1$

This implies $f(m) = 0$ and thus $\text{domain}(\phi\_m) = \emptyset$. But notice that $\varphi\_m \simeq 1$ is implied by our assumption. Thus the domain of $\varphi\_m$ is $\\{1\\}$. That's a contradiction.

Case 2: $\Psi(m,n) = \text{undefined}$

This implies $f(m) = 1$ and thus $\text{domain}(\phi\_m)\neq\emptyset$. But once again $\varphi\_m \simeq \lambda n.\Psi(m,n) \Rightarrow \varphi\_m \simeq \text{undefined} \Rightarrow \text{domain}(\phi\_m) = \emptyset$, which is a contradiction.
> 0 votes

---
Tags: computability
---


# Question
Title: Difficulty in understanding the proof of the lemma : "Matroids exhibit the optimal-substructure property"
I was going through the text *"Introduction to Algorithms" by Cormen et. al.* where I came across a lemma in which I could not understand a vital step in the proof. Before going into the lemma I give a brief description of the possible prerequisites for the lemma.

---

Let $M=(S,\ell)$ be a weighted matroid where $S$ is the ground set and $\ell$ is the family of subsets of $S$ called the independent subsets of $S$. Let $w:S\rightarrow\mathbb{R}$ be the corresponding weight function ($w$ is strictly positive).

Let us have an algorithm which finds an optimal subset of $M$ using greedy method as:

> $\text{G}{\scriptstyle{\text{REEDY}}}(M,w):$
>
> $1\quad A\leftarrow\phi$
>
> $2\quad \text{sort $S\[M\]$ into monotonically decreasing order by weight $w$}$
>
> $3\quad \text{for each $x\in S\[M\]$, taken in monotonically decreasing order by weight $w(x)$}$
>
> $4\quad\quad \text{do if $A\cup\\{x\\} \in \ell\[M\]$}$
>
> $5\quad\quad\quad\text{then $A\leftarrow A\cup \\{x\\}$}$
>
> $6\quad \text{return $A$}$

---

I was having a problem in understanding a step in the proof of the lemma below.

> ***Lemma: (Matroids exhibit the optimal-substructure property)***
>
> Let $x$ be the first element of $S$ chosen by $\text{G}{\scriptstyle{\text{REEDY}}}$ for the weighted matroid $M = (S, \ell)$. The remaining problem of finding a maximum-weight independent subset containing $x$ reduces to finding a maximum-weight independent subset of the weighted matroid $M' = (S', \ell')$, where
>
> $S' = \\{y\in S:\\{x,y\\}\in \ell\\}$ ,
>
> $\ell' = \\{В \subseteq S - \\{x\\} : В \cup \\{x\\} \in \ell\\}$ ,
>
> and the weight function for $M'$ is the weight function for $M$, restricted to $S'$. (We call $M'$ the ***contraction*** of $M$ by the element $x$.)
>
> > Proof:
> >
> > 1. If $A$ is any maximum-weight independent subset of $M$ containing $x$, then $A' = A - \\{x\\}$ is an independent subset of $M'$.
> > 2. Conversely, any independent subset $A'$ of $M'$ yields an independent subset $A = A'\cup\\{x\\}$ of $M$.
> > 3. We have in both cases $w(A) = w(A') + w(x)$.
> > 4. Since we have in both cases that $w(A) = w(A') + w(x)$, ***a maximum-weight solution in $M$ containing $x$ yields a maximum-weight solution in $M'$, and vice versa.***

---

I could understand $(1),(2),(3)$. But I could not get how the line $(4)$ was arrived in the proof from $(1),(2),(3)$, especially the part in bold-italics. Could anyone please make it clear to me?

# Answer
> 4 votes
The adjective "maximum-weight" should not appear in item (1) in that proof of the lemma. This is a minor bug of that famous book.

To be fully clear, item (1) should have been the following.

1. If $A$ is any independent subset of $M$ containing $x$, then $A' = A - \\{x\\}$ is an independent subset of $M'$.

With item (1) corrected, item (4) follows naturally from item (1), (2) and (3). Here is more detail.

---

***"A maximum-weight solution in $M$ containing $x$ yields a maximum-weight solution in $M'$."***

Note that "solution" is just a shorthand for "independent set". Let us prove the proposition above.

Suppose $A$ is a maximum-weight solution in $M$. Then $A$ yields $A'=A-\\{x\\}$, which is a solution in $M'$ according to item (1). (The previous version of item (1) works as well.)

Given any solution $B'$ in $M'$, let $B=B'\cup\\{x\\}$, which is a solution in $M$ according to item (2).

Item (3) tells us $w(A)=w(A')+w(x),$ and $w(B)=w(B')+w(x).$ Since $A$ has maximum weight in $M$, we have $w(A)\ge w(B)$, i.e., $$w(A')+w(x)\ge w(B')+w(x).$$ Cancelling $w(x)$ from both sides, we obtain $$w(A')\ge w(B'),$$ which says $A'$ is a maximum-weight solution in $M'$. $\checkmark$

---

***A maximum-weight solution in $M'$ yields a maximum-weight solution in $M$ containing $x$.***

The other direction, as stated above, can be proved similarly. Here is the proof.

Suppose $B'$ is a maximum-weight solution in $M'$. Then $B'$ yields $B=B'\cup\\{x\\}$, which is a solution in $M$ according to item (2).

Given any solution $A$ in $M$, let $A'=A-\\{x\\}$, which is a solution in $M'$ according to (the corrected version of) item (1).

Since $B'$ has maximum weight in $M'$, we have $w(B')\ge w(A')$. Adding $w(x)$ to both sides, we obtain, $$w(B')+w(x)\ge w(A')+w(x).$$

Item (3) tells us $w(A)=w(A')+w(x),$ and $w(B)=w(B')+w(x).$ So the inequality above is the same as $$w(B)\ge w(A),$$

which says $B$ is a maximum-weight solution in $M$. $\checkmark$

# Answer
> 2 votes
For convenience:

$$W(P) = \sum\_{p\in P} \omega (p)$$

First case: $A$ is max. independent set of $M$

Now let's assume $A'$ wasn't the max. independent set of $M'$. Thus another max. independent set $H\in l'$ must exist. $$W(A') \< W(H)$$ Since every independent set in $l'$ has a corresponding set in $l$ including $x$ we can conclude $H\cup\\{x\\}\in l$ and hence: $$W(A') + \omega(x)\< W(H)+\omega(x) \Rightarrow W(A'\cup\\{x\\}) \< W(H\cup\\{x\\})$$ But $A'\cup\\{x\\} = A$ which is a contradiction since $A$ is the max. independent set of $M$.

The other way around is a bit trickier.
Second case: $A'$ is max. independent set of $M'$.

Now we assume $A$ wasn't the max. independent set of M. This would imply the existence of a set $H\in l$ with $W(H) \> W(A)$. Now we can apply the hereditary property to $A$ and conclude that $\\{x\\}\in l$. To $H$ and $Z = \\{x\\}$ we can now apply the independent set exchange property repeatedly to augment $Z$ to $Z'$ until it contains all elements in $H$ except its smallest. Thus
$$Z' = Z \cup H - \\{\text{argmin}\_{h\in H}\\{\omega(h)\\}\\}$$ $$W(Z') \geq W(H)$$. Since $Z'$ contains $x$ and $$W(Z')\>W(A) \Rightarrow W(Z'-\\{x\\}) \> W(A')$$ we have a contradiction (we assumed A' was max. set of M').

---
Tags: algorithms, proof-techniques, greedy-algorithms, matroids
---


title: Pumping Lemma,regular languages

text:
# Question
Title: Pumping Lemma,regular languages
Lets say that we have the language L = { $a^n$$b^m$$c^{m+n}$ $|$ $m$,$n$ $\>=0$ } What is the way that i should follow to prove

that the language is not regular?

* Assume that the language is regular.
* So,there is a string $w\in L$ such that $w = xyz$ , $|xy|\leq n, y\neqε $, **n is the pumping length**

Lets say that the string that i choose( w string) is $w = a^nb^mc^{m+n}$

Is this choice correct ? Can someone explain me the best choice of $y$ ?

Should be $y = a^{n-r} $ and $x = a^n $ ? Because of $|xy|\leq n$ ?

Thank you and sorry for my english.

# Answer
> 1 votes
**Pumping Lemma for regular languages (by Wikipedia):**
Let $\displaystyle L$ be a regular language. Then there exists an integer $\displaystyle p\geq 1$ depending only on $\displaystyle $ such that every string $\displaystyle w$ in $\displaystyle L$ of length at least $\displaystyle p$ ($\displaystyle p$ is called the "pumping length") can be written as $\displaystyle w=xyz$ (i.e., $\displaystyle w$ can be divided into three substrings), satisfying the following conditions:

1. $\displaystyle |y|\geq 1$
2. $\displaystyle |xy|\leq p$
3. $\displaystyle (\forall k\geq 0)(xy^{k}z\in L)$

**Task**
The given Language is $L = \\{a^nb^mc^{n+m}|m,n\geq 0\\}$. We want to show that L is not regular through proof by contradiction using the pumping lemma.

First we assume that $L$ is regular as you wrote. This implies the existence of the pumping length $p$. You called the pumping length $n$ which might lead to confusion cause $n$ appears in the definition of the language; so I called it $p$. Since we make a proof by contradiction we need to choose a word $|w| \geq p, w\in L$ and show for **every possible partition** into $w = xyz, |xy|\leq p, |y|\geq 1$ that there is a $k$ such that $xy^kz\notin L$.

Now what $w$ could you choose? I think $a^pb^pc^{2p}$ is a good choice. Because $w = xyz = a^pb^pc^{2p}, |xy|\leq p, |y| \geq 1$ implies that $x = a^{i}, y = a^j, i+j \leq p, j\geq1$ thus $xy^pz \notin L$ because the the string would look like $a^{i+p\cdot j}b^pc^{2\cdot p}$ and $i+p\cdot j + p \neq 2p$, so the property of the language is violated. That's how proof using the pumping lemma usually looks like.

---
Tags: regular-languages, regular-expressions, pumping-lemma, discrete-mathematics
---


# Question
Title: Time Complexity of inserting a vector to a vector of vectors in C++
I was solving a question on LeetCode, where I had to generate all possible subsets of a given set of numbers.

Although, the solution makes sense to me, I am unable to understand the derivation of time complexity for those solutions.

A solution I found there was:

```
class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> subs = {{}};
        for (int num : nums) {
            int n = subs.size();
            for (int i = 0; i < n; i++) {
                subs.push_back(subs[i]);  <---- LINE X
                subs.back().push_back(num); <---- LINE Y
            }
        }
        return subs;
    }
};

```

It is an iterative solution to solve the problem. What I don't understand is the time complexity of the given solution and **more importantly**, the complexities of Line X and Line Y.

Does copying subs\[i\] take O(n) time and then pushing back take another O(n) time, or is it an O(1) step?

# Answer
First tings first:

Line X does a copy subs\[i\] and creates a new vector. In terms of vector length $n$ this step is $O(n)$.

Line Y is amortized O(1). (The vector might need to reallocate making it O(n) in the worst case; to avoid reallocation see @MSalters post.)

The runtime of the whole procedure is a bit more difficult. At the $i$-th number `subs` contains every possible subset of all numbers so far. Thus length of subs $=2^i$, but we are interested in how many numbers we need to copy. this can be calculate with the sum of all subset sizes which is $i2^{i-1}$ (meaning at step $i$ we have to copy $i2^{i-1}$ numbers and make $2^i$ push operations). $$O\left(\sum\_{i=0}^{n-1} i2^{i-1}+2^i\right) = O(n2^n)$$ The complexity on the right makes sense, all sizes of all vectors in `subs` will be $n2^{n-1}$ in the end.
> 0 votes

# Answer
This requires a bit of C++ knowledge.

`push_back` will copy or move the argument. Copying a vector is O(n), moving it is O(1). In this case, the argument on line X is `subs[i]`, which does not allow a move. It will be copied (good, since we need it later).

On line Y, the argument is just a single integer. Copying an integer is O(1), essentially by definition.

But besides copying the argument, `push_back` may also need to move all the existing arguments if there's a need to reallocate memory. Vectors have exponential growth, so this doesn't happen on every `push_back`. As a result, adding N elements to an empty vector will only cause O(log N) realloactions which requires moving O(N) elements.

C++ has a solution to this. `vector.reserve(N)` will perform one allocation so that `push_back` up to `vector.size()==N` will not cause reallocations.
> 0 votes

---
Tags: time-complexity
---


# Question
Title: Is NSPACE(2^O(n)) = NSPACE(n^2 * 2^(O(n))
As said in the title, i am quite curious wether NSPACE(2^(O(n)) equals NSPACE(n^2 * 2^(O(n))

I am aware of the fact, that NSPACE(k * 2^O(n)) equals NSPACE(2^O(n)) due to linear space reduction (i.e. some sort of super character representing k characters)

But since neighter n nor n^2 is linear, we cant use this here.

Thanks for your advise!

# Answer
Yes. Clearly NSPACE($2^{O(n)}$) $\subseteq $ NSPACE($n^2 \cdot 2^{O(n)}$).

To show that NSPACE($2^{O(n)}$) $\supseteq $ NSPACE($n^2 \cdot 2^{O(n)}$) it suffices to notice that $n^2 \cdot 2^{O(n)} = 2^{O(n) + 2\log n}$ and $O(n)+2\log n =O(n)$.
> 2 votes

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


title: Confusion of halting problem

text:
# Question
Title: Confusion of halting problem
Show that the following problem is solvable.Given two programs with their inputs and the knowledge that exactly one of them halts, determine which halts.

lets P be program that determine one of the program will be halted.

```
P(Program x,Program y){

    if(x will be halted)

          then return 1;

    else

           then return 2;
}

```

since we know that exactly one of them will be halted,if 1 then program x will be halted.Otherwiae program y will be halted.

then we construct a new program call D

```
D(X,Y){

     if(P(X,Y) == 2)

         D will halt;

      else

         while(1)//D will not halt;

  }

```

lets S be aritbrary program.

So if we have D(D,S)

if D will halt then D will not halt

if D will not halt then D will halt

It impiles a contradiction same as halting problem.

But the question stated that it is solvable.

# Answer
To start with an important side note: what are the inputs for $X$ and $Y$ that they will halt on? you need to specify a specific input for the machines in order for the question to be well-defined (for example, the question could be "given $X,Y$ where exactly one terminates on $\epsilon$, find who halted." Or maybe, "given ... where exactly one always halts on itself as an input...")

I see what confused you there. The problem is indeed solvable: in $P$ emulate both $X$ and $Y$ and answer whoever halted first.

The problem in your solution is that an input to $P$ must be $X,Y$ where **exactly** one of them halts, and the other doesn't.

So, a proper input to $D$ must be a proper input to $P$. Now notice you called $D(D,S)$. To make sure that $D$ will return a correct output, we must have proper inputs: only one of $D$ or $S$ halts! But... If $S$ halts then your $D$ *also* halts and **this is not a proper input to $P$**, and therefore also not a proper input to $D$. Thus you cannot rely on output from $D(D,S)$ as it may not be correct
> 0 votes

---
Tags: computability, halting-problem
---


# Question
Title: DFA that accepts all the strings with exactly two a’s and more than two b’s
It works I checked it but I don't know how to make it smaller :( the question is in my book,I can solve but it took too much time and effort and I'm pretty sure there's a simple soloution.

# Answer
> 0 votes
My solution might not be *the smallest*, however it's more organized (and still smaller than your solution):

The column number represents the number of "A"s seen, and the row number is the number of "B"s seen. This DFA solves the language $\\{w\ |\ \\#\_a(w)=2,\ \\#\_b(w)\ge 2\\}$

If you intended to solve the language $\\{w\ |\ \\#\_a(w)=2,\ \\#\_b(w)\> 2\\}$, then just add another row of states (similarly to the rows here).

Hope this helps! (even though, as I stated, it might and probably is not the *minimal* solution)

---
Tags: theory
---


# Question
Title: Why there is no Turing Machine that accepts the Diagonal Language?
Given the diagonal language

$$L\_d = \\{ i : \sigma\_i \notin L(M\_i) \\}$$

Where $M\_i$ are *all* Turing Machines and $\sigma\_i$ are *all* the words, if you put in in a Matrix like this:

$$\begin{array} {|c|c|c|c|c|c|c|} \hline & \sigma\_1 & \sigma\_2 & \sigma\_3 & \sigma\_4 & \sigma\_5 & ...\\ \hline M\_1 & 1 & 0 & 1 & \dotsb & \dotsb & \dotsb \\ \hline M\_2 & 0 & 0 & 1 & \dotsb & \dotsb & \dotsb \\ \hline M\_3 & 1 & 0 & 1 & \dotsb & \dotsb & \dotsb \\ \hline M\_4 & \vdots & \vdots & \vdots & 1 & \dotsb & \dotsb \\ \hline M\_5 & \vdots & \vdots & \vdots & \vdots & \ddots & \dotsb \\ \hline \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \\ \hline \end{array}$$

Then $L\_d$ is represented by the numbers in the diagonal of the matrix. In class I was told that there is no TM that accept $L\_d$, but I do not quite understand why is that, could somebody help?

PS: The above explanation was included because I did not know if this is called Diagonal Language in English, Spanish is my mother tongue.

# Answer
In the following I assume that the matrix has an 1 in coordinates $(i,j)$ if $M\_i$ accepts $\sigma\_j$ and a $0$ otherwise (swapping all 1s and 0s does not affect the argument).

Consider the language $L = \\{\sigma\_i \in \Sigma^\* : \sigma\_i \not\in L(M\_i) \\}$ that contains all the words $\sigma\_i$ such that the entry at coordinates $(i,i)$ of the matrix is $1$. I will first show that $L$ is not acceptable.

Suppose towards a contradiction that there is some Turing machine $M^\*$ that accepts $L$. Since the set of Turing machines is enumerable, and the rows of the matrix are associated with an enumeration of all Turing machines, there must be some integer $i \ge 1$ such that $M\_i = M^\*$.

Then consider the word $\sigma\_i$ and suppose that the entry at coordinates $(i,i)$ is $1$. From the way the matrix is constructed you know that $M\_i$ accepts $\sigma\_i$. However, by the definition of $L$, you also know that $\sigma\_i \not\in L$. This implies that $M^\* = M\_i$ cannot accept $\sigma\_i$. This is a contradiction.

If the entry at coordinates $(i,i)$ is $0$, then $M\_i$ does not accept $\sigma\_i$. However, $\sigma\_i \in L$ implying that $M^\* = M\_i$ accepts $\sigma\_i$. Again, this is a contradiction.

Going back to your language $L\_d$: if $L\_d$ were acceptable then so would be $L$. Suppose towards a contradiction that there is a Turing Machine $M$ that accepts $L\_d$. To accept $L$ proceed as follows:

* find the index $i$ such that $\sigma\_i = x$. This can be done by enumerating the words in $\Sigma^\*$.
* Simulate $M$ with input $i$.
* If $M$ with input $i$ halts and accepts, accept.

Since this is a contradiction, $L\_d$ cannot be acceptable.
> 2 votes

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


# Question
Title: Directed Grid Graphs; All Possible Paths Through Nodes
I have a problem in which I am interested in taking a matrix of positive integer weights, including zero, where the matrix has dimensions nrow x ncol and the columns always sum to the same arbitrary number. I want to search for a list of paths (sets of edges essentially) that traverse through the grid space of the same dimension & create the paths such that the # of edges in a path going through a node is equal to the nodes weight (from the matrix). Ie: if a particular index in my matrix was "3", there would be 3 edges that would run into (and out of) this node.

Some important restrictions. Firstly, The only direction the edges can move is rightward (so vertical edges are disallowed) but only one column distance at a time. I do allow for the edges to go from any row\_j (in column\_i) to any other possible row\_j in column\_i+1, so diagonal edges (either upwards or downwards are allowed). Here's an example of such a solution (it is non singular which is why Im interested in ALL possible paths)

Most importantly, I am interested in two things. First I want all possible paths from this process, and even more critically, I want to minimise the number of possible diagonal edges that my resulting paths will contain.

Any sort of algorithm here to solve this would be hugely helpful.

I have managed to solve the case when I don't care about the number of diagonal edges, and just want a set of paths that match with the weights. To do that, I used the weights at adjacent columns to generate a Markov transition process. This gave me a series of transition matrices (of length ncol-1) which from there I was able to construct probabilistically what my paths through my weights were.

Let me know if anyone needs any more details/explanations here.

****Update & Further Questions****

I've looked into the mincost flow algo's & although they are definitely in the right wheelhouse for this problem here, they aren't 100% exactly what I need for a few reasons. First one **important thing** to note is that in my real world scenario, these weights are actually more of a probability mass, so they can take any value (0,1) non inclusive. But for a toy example, the integer weights work ok to derive a framework.

I think the way I had solved the problem (prior to posting this question) essentially was in a network flow like manner already without realizing it, ie: looking at fluxes coming in & out of the various nodes across my lattice. However, the main problem with this manner of solving the problem is how this solution affects my inference of downstream results. Essentially behind this 'weight' matrix (in the example, it is a 3x3 grid) is a grid that encodes with a binary alphabet {0,1} a letter for each weight. Ie one possible reference grid (as I call it) could be

1 0 0
0 1 1
0 0 0

By using this reference grid & weighted panel together, we end up with a series of weighted references which has two important properties we can calculate (given some weights & some ref panel): the column means from this weighted reference panel, and the expected covariance (how often do 1's stay 1's essentially) of the weighted reference encodings.

Ie. in the example outlined above, we have on column A a weight of (4 * 1 + 0 * 1 +0 * 1)/(4+1+1) = 0.67.

The covariance terms are slightly more difficult to derive but essentially we look at what proportion of the total flow (that we have already derived) comes from elements encoded '1' in column i and stays encoded '1' column in i+1. Here that contribution would only come from {row\_1,column\_1}-\>{row\_2,column\_2}.

To get the longer distance covariance what I do is perform matrix multiplication on the flow matrices. You can think of the flow matrices as a series (of length ncol--1) of matrices (each with dimensions nrow x nrow) which look from each successive column (i-\>i+1), how much % flow is going from one row to itself, or to other rows.

When I perform this inference, I am able to properly calculate the correct expected value for the covariance based on the flow given an underlying reference matrix & weight matrix. **However**, I don't really want the expected value, but actually an expected value **conditional on us having not used as high a proportion of diagonal edges** as we would have in the naive case. The reason for this is when we perform this operation on larger matrices, the covariance terms (the proportion of times 1's flow to other 1's along the columns) is weakened over long distances (this is because this is a memoryless markov process if that helps) since with this diagonal flow we don't get the same set of encodings as the reference panel. (eg: in our example we would looking at the reference have only ({1,0,0},{0,1,1},{0,0,0}) as the possible paths, but with diagonal flow we could have some element such as {0,1,0}.

So in essence I guess what I'm wondering is if there is some sort of expected covariance I can derive, based on the graph traversal (or the framework I have developed here) that would allow me to get the expected covariance based on different # of diagonal switches possible, or more broadly to look at ways how to minimise this long-distance loss phenomena I am facing here.

One idea I had was to sort my reference panel based on the positional burrow wheels transform (http://alimanfoo.github.io/2016/06/21/understanding-pbwt.html) which would allow me to look at series of blocks in my reference panel that were more similar to one another. Unsure exactly how I would use that however?

# Answer
It seems to me that what you need is an integer mincost flow algorithm. Each matrix entry gets a vertex in the network, with each vertex having arcs to all of the vertices in the next column. The solution flow values indicate how many edges to place between each pair of entries. The flow constraint enforces equal numbers of edges in and out of each entry. You would set capacity constraints on the vertices to enforce the limit on how many edges enter and exit each entry.\[\*\] You would assign zero cost for horizontal edges and nonzero cost to diagonal edges (either a fixed cost for all diagonal edges or a cost based on the diagonal length, depending on what you are optimizing for).

Off-the-shelf open source solvers and libraries for mincost flow are widely available, so you can just construct the flow network and then hand it off to a solver to get a solution. If you want to get entire left-to-right paths out of this, you would have to construct them from the flow solution. But that is easy enough by graph search.

\[\*\] Mincost flow is usually presented with capacity constraints on the arcs rather than on the vertices. This is easily worked around by splitting each vertex in two, with a capacity-limited arc in-between. That is, if a vertex $v$ has a capcity limit $c$, replace $v$ with two vertices $v\_1$ and $v\_2$ such that all the arcs that entered $v$ instead enter $v\_1$, all the arcs that left $v$ instead leave $v\_2$, and there is an arc with capacity limit $c$ from $v\_1$ to $v\_2$.
> 1 votes

---
Tags: graphs, weighted-graphs, directed-graphs
---


title: Complexity of generating power sets

text:
# Question
Title: Complexity of generating power sets
Suppose I have two sets $A$ and $B$ containing integers. Let $B'$ be the power set of $B$. Then suppose I have an algorithm that enumerates all possible pairings of elements in $A$ and $B'$ to apply a function $f$ to them and check something.

I understand that generating a power set is $O(2^n)$, but what complexity class does this belong to, and how do I prove it?

# Answer
> 1 votes
Complexity time $O(2^n)$ is called $\text{DTIME}(O(2^n))$ and is a sub-complexity class of  which is in turn a sub-complexity class of EXPTIME.

To prove you can do it within $O(2^n)$ time, you have to provide an algorithm for that and show the algorithm runs in no more than $O(2^n)$.

---
Tags: time-complexity, complexity-classes
---


# Question
Title: How does the sweep line algorithm check for intersection using vector cross product?
I am trying my best to understand the sweep-line algorithm to find line intersections.

I have understood most of the intuition **except how it is calculating the intersection between 2 line segments using cross product.**

*I am providing the code for that below, please ask me any doubts related to the code, so that I can explain it to those people who are not familiar with programming.*

Full code here.

```
public boolean intersect(Line other) {
            // out.println(turn(p1, p2, other.p1) + turn(p1, p2, other.p2));
            // out.println(turn(other.p1, other.p2, p1) + turn(other.p1, other.p2, p2));
            return intersect1d(p1.x, p2.x, other.p1.x, other.p2.x)
                    && intersect1d(p1.y, p2.y, other.p1.y, other.p2.y)
                    && turn(p1, p2, other.p1) * turn(p1, p2, other.p2) <= 0
                    && turn(other.p1, other.p2, p1) * turn(other.p1, other.p2, p2) <= 0;
        }

public boolean intersect1d(double l1, double r1, double l2, double r2) {
        if (l1 > r1) {
            double temp = l1;
            l1 = r1;
            r1 = temp;
        }
        if (l2 > r2) {
            double temp = l2;
            l2 = r2;
            r2 = temp;
        }
        return Math.max(l1, l2) <= Math.min(r1, r2) + 1e-12;
    }

  public int turn(Vector p1, Vector p2, Vector p3) {
        double c = cross(p2.x-p1.x, p2.y-p1.y, p3.x-p2.x, p3.y-p2.y);
        if (c < -1e-12) {
            return -1;
        } else if (c > 1e-12) {
            return 1;
        } else {
            return 0;
        }
    }

public double cross(double x1, double y1, double x2, double y2) {
        return x1 * y2 - y1 * x2;
    }

```

**Comments about the code:**

* The function `intersect(Line)` is called when evaluating whether the present line is intersecting with another line segment which is provided.
* `intersect` in turn calls the functions `intersect1d()` and `turn()` each 2 times respectively. `intersect1d` takes both the starting and ending x-axis and y-axis coordinates for both lines in 2 separate function calls.
* `turn()` is called next. I have no idea what `turn()` is doing.

**Questions about the code:**

* **What is cross product of 2 vectors in** ${\rm I\\!R^2}$ **?**

What does that even mean ? Cross Product is supposed to be defined only for vectors in ${\rm I\\!R^3}$ ?

Post like this say this is a mathematical hack. Well if it works why is it a hack ? **And what exactly is happening with a cross product in 2D ? And why is it relevant here ?**

* **How does the cross product compute the area of a parallelogram ?**

This post mentions that the cross product of 2 vectors calculate the area of the parallelogram. How are we getting a parallelogram and how is the are being calculated by the cross product ?

* **What is `intersect1d()` actually doing ?**

From the looks of it, it is checking that the x coordinates of the first line are less than the x coordinates of the second line. Same for y coordinates.

* **Please explain what `turn()` is doing ?**

I have no clue.

**Other details:**

I have gone through other SO posts like this.

I can almost understand how they are deriving the parametric equations of the lines from the vectors, but I simply have no clue how they are using the cross product to check for co-linearity and intersections.

Namely, I cannot understand these conditions from the SO answer:

> Now there are four cases:
>
> 1. If r × s = 0 and (q − p) × r = 0, then the two lines are colinear.
>
> In this case, express the endpoints of the second segment (q and q + s) in terms of the equation of the first line segment (p + t r):
>
> > t0 = (q − p) · r / (r · r)
> >
> > t1 = (q + s − p) · r / (r · r) = t0 + s · r / (r · r)
>
> If the interval between t0 and t1 intersects the interval \[0, 1\] then the line segments are collinear and overlapping; otherwise they are collinear and disjoint.
>
> Note that if s and r point in opposite directions, then s · r \< 0 and so the interval to be checked is \[t1, t0\] rather than \[t0, t1\].
>
> 2. If r × s = 0 and (q − p) × r ≠ 0, then the two lines are parallel and non-intersecting.
> 3. If r × s ≠ 0 and 0 ≤ t ≤ 1 and 0 ≤ u ≤ 1, the two line segments meet at the point p + t r = q + u s.
> 4. Otherwise, the two line segments are not parallel but do not intersect.

*Note: As you may have guessed I am a novice to linear algebra and vectors, so if you do chose to help me I would request you to write "noob" friendly answers. This will stop me from wasting your time with a ton of follow up questions.*

Thanks.

# Answer
> 2 votes
* What is cross product of 2 vectors in ${\rm I\\!R^2}$ ?

If you compute the crossproduct of 2 vectors on the $xy$ plane you get a vector along the $z$ axis. In 2D the crossproduct is defined as the (scalar) $z$ value of that vector.

Moreover the value is positive is the angle goes one way and negative if it goes the other way (which exact way depends on the handedness you picked for your 3D space). That way you can test whether a line segment crosses another line.

* How does the cross product compute the area of a parallelogram ?

The value of the crossproduct ends up as $|a|\*|b|\*\sin(\theta)$ where theta is the angle between the vectors. If you take $a$ as base then $|b|\*sin(\theta)$ is the height of the parallelogram.

* What is `intersect1d()` actually doing ?

It checks whether there is an overlap between the segments on a 1D line. Doing it on x and y mean the code does an axis aligned bounding box collision test as an early out.

* Please explain what `turn()` is doing ?

It maps the value of the crossproduct to a direction of turn using the sign as I explained above. But values near 0 are mapped to no turn (for accuracy reasons).

---
Tags: algorithms, computational-geometry, linear-algebra
---


# Question
Title: Why are processes on the internet not required to use TCP or UDP?
Here is an excerpt from Andrew S. Tanenbaum, Computer Networks, 5th edition, Chapter 5 (The Network layer), Page 455:

\[Fifth, processes on the Internet are not required to use TCP or UDP. If a user on machine A decides to use some new transport protocol to talk to a user on machine B (for example, for a multimedia application), introduction of a NAT box will cause the application to fail because the NAT box will not be able to locate the TCP Source port correctly.\]

My question is: in this context. what does "processes" mean? Is it a process of data exchange between routers? And why are processes on the internet not required to use TCP or UDP? Isn't it a part of IP protocol and thus it will be used on the internet?

# Answer
In this context, a process is a normal computer application process, e.g., as defined in wikipedia:

> a process is the instance of a computer program that is being executed by one or many threads. It contains the program code and its activity. Depending on the operating system (OS), a process may be made up of multiple threads of execution that execute instructions concurrently

So, as Tanenbaum points out, a process that wishes to communicate over the Internet, need *not* use TCP or UDP. In fact, there are other transport protocols besides TCP or UDP, although those two are the most common. See wikipedia on transport protocols for other transport protocols like SCTP and DCCP. NAT boxes that need a TCP source port to work, would not be able to properly work with other transport protocols. I think Tanenbaum gives the example of a multimedia application, because the requirements can be quite different, e.g., for real-time multimedia, where there is yet another transport protocol combination, RTP/UDP/IP (Realtime Transport Protocol over UDP, then over IP) that is better suited for multimedia traffic than TCP/IP.

Why do we hear the phrase TCP/IP so often? Because we hear that, we may get confused and think like you thought, that TCP was "part of" IP. Actually, TCP and IP are separately protocols on different layers of the protocol stack (transport layer and network layer, respectively). However, in the Internet, TCP is so commonly used, that people started saying TCP/IP, for communications using TCP over IP.
> 1 votes

# Answer
In this context a process is like a process on your computer, like a webbrowser.

No IP is a separate lower layer under TCP and UDP. You can send raw IP packets from your PC and have them arrive on the other side of the world through the existing internet infrastructure (assuming relevant firewall rules allow them through). The IP header has byte to specify which next protocol is being used. Currently just over half are assigned to protocols. Only 2 of the assignments are for TCP and UDP.

The TCP and UDP layers add 2-byte port numbers to let multiple listening processes on the same IP address differentiate which process the packet is meant for. TCP additionally adds connection semantics with resend for lost packets.
> 0 votes

---
Tags: computer-networks, communication-protocols, tcp, ip
---


# Question
Title: Proving complexity of $T(n)=2T(n/3 + 1) + n$ non-Akra-Bazzi
We know that the complexity of $T(n)=2T(n/3 + 1) + n$ is $\Theta(n)$, as has been proved on this exchange before. However, what about proving it inductively? I believe that this method might work.

Guess $T(n) \leq cn-d$. Assume true for $m \< n$. Specifically, $m = n/3 \< n$ Then, $T(n) \leq cn-d$.

$T(n) \leq 2(cn/3 - d + 1) + n$ $= 2cn/3 - 2d + 2 + n$ $=n(2c/3+1)+2(1-d)$. Then for values of $c \geq 1$ and $d \geq2$ we have $T(n) \leq cn - d$. Then $T(n)=\Theta(n)$.

What does everyone think?

# Answer
> 1 votes
You want to prove a tight $\Theta(n)$ bound as @vonbrand commented you could to show: $$am+b \leq T(m)\leq cm+d\quad (1)$$ Now start by assuming $(1)$ holds for all $m \< n$ and conclude: $$T(n) = 2T(n/3+1)+n \geq 2(a(n/3+1)+b)+n \geq n(2/3a+1) + 2(a+b)$$ $$T(n) = 2T(n/3+1)+n \leq 2(c(n/3+1)+d)+n \leq n(2/3c+1) + 2(c+d)$$ Thus $an+b \leq T(n)\leq cn+d$. Hence $T(n) \in \Theta(n).$

# Answer
> 0 votes
You can use the variant by Leighton "Notes on Better Master Theorems for Divide-and-Conquer Recurrences". Lehman, Leighton and Meyer in "Mathematics for Computer Science" on page 1019 state a simplified version: If you have $T(n) = \sum\_{1 \le i \le k} a\_i T(b\_i n + h\_i(n)) + g(n)$, where $a\_i \> 0$, $0 \< b\_i \< 1$, $g(n) \> 0$ such that $\lvert g'(x) \rvert$ is bounded by a polynomial, and $\lvert h\_i(n) \rvert = O(n / \log^2 n)$, then is $p$ is the unique real such that $\sum\_{1 \le i \le k} a\_i b\_i^p = 1$, then:

$$ T(n) = \Theta\left( n^p \left( 1 + \int\_1^n \frac{g(u)}{u^{p + 1}} d u \right) \right) $$

Your $g(n) = n$ certainly qualifies. With $a\_1 = 2$, $b\_1 = 1/3$, $h\_1(n) = 1$ satisfies the condition, you get:

$$ 2 \cdot 3^{-p} = 1 $$

from which $p = \log\_3 2$, so that:

$$ T(n) = \Theta\left( n^{\log\_3 2} \left( 1 + \int\_1^n u^{- \log\_3 2} d u \right) \right) = \Theta(n) $$

---
Tags: complexity-theory, algorithm-analysis, time-complexity, recurrence-relation, master-theorem
---


# Question
Title: What is considered an asymptotic improvement for graph algorithms?
Lets say we are trying to solve some algorithmic problem $A$ that is dependent on input of size $n$. We say algorithm $B$ that runs in time $T(n)$, is asymptotically better than algorithm $C$ which runs in time $G(n)$ if we have: $G(n) = O(T(n))$, but $T(n)$ is not $O(G(n))$.

My question is related to the asymptotic running time of graph algorithms, which is usually dependent on $|V|$ and $|E|$. Specifically I want to focus on Prim's algorithm. If we implement the priority queue with a binary heap the run-time would be $O(E\log V)$. With Fibonacci heap we could get a run-time of $O(V\log V + E)$.

My question is do we say that $O(V\log V + E)$ is asymptotically better than $O(E\log V)$?

Let me clarify: I know that if the graph is dense the answer is yes. But if $E=O(V)$ both of the solutions are the same. I am more interested in what is usually *defined* as an asymptotic improvement in the case we have more than one variable, and even worse - the variables are not independent ($V-1\le E\<V^2$, since we assume the graph is connected for Prim's algorithm).

Thanks!

# Answer
The most permissive definition is as follows.

Suppose that $f(V,E),g(V,E)$ are two running times of graph algorithms solving the same problem.

We say that $f$ is an *asymptotic improvement in some regime* on $g$ if there exists a sequence $V\_n,E\_n$ with $V\_n \to \infty$ such that $$ \lim\_{n\to\infty} \frac{f(V\_n,E\_n)}{g(V\_n,E\_n)} = 0. $$

Sometimes the regime is not deemed interesting, but that's a more subjective matter.

Note also that the problem already manifests itself for one-variable functions. Consider $$ f(n) = n^2, \qquad g(n) = \begin{cases} 2^n &\text{if } n = 2^m, \\ n & \text{otherwise}. \end{cases} $$ Is $f$ an asymptotic improvement over $g$? It is for inputs of a certain length, and is indeed so under our permissive definition above.
> 3 votes

---
Tags: asymptotics, runtime-analysis
---


# Question
Title: Is it true that if L* is recursive, L is also recursive?
Is it true that if $L^\*$ is recursive, where $\*$ is Kleene star, $L$ is also recursive?

I know that the opposite direction is true:

> If $L$ is recursive, then $L^\*$ is recursive.

But I don't know how to prove it in this direction.

# Answer
No.

Take any language $L$ over $\Sigma = \\{0, 1\\}$ that contains 0 and 1. Then $L^\* = \Sigma^\*$ (this is recursive, even regular), regardless of what $L$ might be. It could be a not even recursively enumerable language.
> 11 votes

---
Tags: formal-languages, computability, kleene-star
---


title: Find two disjoint set

text:
# Question
Title: Find two disjoint set
Given an universum $U$ and two sets $A$ and $B$ of sets of elements from $U$. I want to find (if such a pair exists) $a \in A$ and $b \in B$: $a \cap b \equiv \emptyset$. Currently I can do it only in $O(|A| \cdot |B| \cdot |U|)$, is there way to improve this?

Say, $|U| \leq 32$. Is there a way to speed algorithm up?

If it matters, one can assume, that all elements in $A \cup B$ are unique. Another variation of the problem is $A \equiv B$ and there is a need to search $a$ and $b$ from the single set.

# Answer
> 1 votes
Set $A = B$ and $|U| = \Theta(\log |A|)$, and you run up against the Orthogonal Vectors Conjecture trying to do better than $|A|^{2-o(1)}$.

---
Tags: algorithms, sets
---


title: Out-Degree of a Configuration Graph

text:
# Question
Title: Out-Degree of a Configuration Graph
In Chapter 4 in Computational Complexity by Arora and Barak it states, regarding the configuration graph of a Turing Machine, that

> If M is deterministic, then the graph has out-degree one, and if M is nondeterministic, then the graph has out-degree at most two.

In the configuration graph, a directed edge is placed from the configurations $C$ to $C'$ if we can obtain $C'$ from $C$ via a single transition. Also, the authors assume we are working with two tape Turing machine with one read-only input tape and one read-write work tape. Here, the authors define a configuration by

> A configuration of a TM M consists of the contents of all nonblank entries of M’s tapes, along with its state and head position, at a particular point in its execution.

I understand that the out-degree for a deterministic machine must be 1, but I do not see why the out-degree for the non-deterministic machine can be at most 2. Given that the authors assume that $\Gamma= \\{0,1\\}$, I would assume that the number of possible configurations reachable from any given configuration would be $|\Gamma||Q||\\{L,R\\}^2|$ for a two tape Turing machine, where $Q$ is the set of states and one head is on a read-only input tape. Why would the out-degree of this graph be at most $2$ instead?

# Answer
Based on some research into other things related to TMs, I discovered that any NDTM that has at most $k$ possible branches at each step can be modified into an NDTM that has at most $2$ possible branches at each step at the cost of a $\log\_2(k)$ slowdown. Though I can not find any mention of this anywhere in the textbook, I assume this is what the authors are assuming.
> 2 votes

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


# Question
Title: Can an algorithm complexity be lower than its tight low bound / higher than its tight high bound?
The worst case time complexity of a given algorithm is $\theta(n^3logn)$.
Is it possible that the worst time complexity is $\Omega(n^2)$?
Is it possible that the worst time complexity is $O(n^4)$?
The average time complexity is $O(n^4)$?

IMO it is possible as long as you control the constant $c$, but then what's the point of mentioning any other bound than the tight bounds?

# Answer
> 1 votes
Let $t(x)$ be the time taken for input $x\in \\{0,1\\}^\*$, and $T(n)=\max\_{x\in\\{0,1\\}^\*,|x|=n}t(x)$ is the worst case.

If $T\in\theta(n^3\log(n))$, this means that there are constants $C\_1,C\_2$ and $N$ such that for all $n\> N$ you have $$C\_1n^3\log(n)\leq T(n)\leq C\_2n^3\log(n)$$.

Since $n^3\log(n)\geq n^2$ for $n\>1$, then $C\_1n^2\leq C\_1n^3\log(n)\leq T(n)$. Therefore, $T\in\Omega(n^2)$.

We also have that $n^3\log(n)\leq n^4$, for all $n\>1$. Therefore, $T(n)\leq C\_2n^3\log(n)\leq C\_2n^4$.

This implies that $T\in O(n^4)$.

Finally, $$\begin{align}A(n)&=E(t(x), |x|=n)\\\&\leq E(T(n), |x|=n)\\\&=T(n)E(1,|x|=n)\\\&=T(n)\\\&\leq C\_2n^3\log(n)\\\&\leq C\_2n^4\end{align}$$, for $n\>1$. Therefore, the average number of steps satisfies $A\in O(n^4)$.

---

Sometimes computing tight bounds is hard, while more relaxed bounds are more accessible.

# Answer
> 2 votes
If $T(n) = \Theta(n^3\log n)$ then it is *always* the case that $T(n) = \Omega(n^2)$ and $T(n) = O(n^4)$.

If $T(n)$ is the worst-case complexity of an algorithm, then furthermore its average-case complexity is $O(n^4)$, *always*.

# Answer
> 0 votes
Sometimes the algorithm you have or the recurrence relation you have do not give you enough information other than the upper bounded relation. i.e. $T(n) \le 2T(n/2) + n$. So you can only upper bound the algorithm unless you have additional information on the lower bound as well.

---
Tags: data-structures
---


title: MIT 6006 Quiz 2: The shortest path task

text:
# Question
Title: MIT 6006 Quiz 2: The shortest path task
I'm looking for some clarifications on an algorithmic task I've been trying to solve. This task is a part of Quiz 2 from the MIT 6.006 course.

The main idea of creating `k`-copies of a graph `G` is clear. What I'm really confused with is the final graph `G'`:

* Can you explain how the graph `G'` will look like?
* How will the `G'` graph guarantee that all of the places `{v0, v1, v2, vi}` had been visited once we reached the destination vertex `t`?

I'm sorry if the community to post this question is wrong. Any suggestions are highly appreciated.

Input:

Solution:

# Answer
Ok, I think here is how it should look like. You duplicate the graph `G` as many times as many `v` places you have to visit (e.g. `v0`, `v1`, `v2`). The order you must visit these vertices is the constraint which is expressed as zero weight edges (G1.v0 -\> G2.v0, G2.v1 -\> G3.v1).
> 0 votes

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


# Question
Title: Finding an MST with one adding and removing vertex operation
I am facing the following problem: Given an **undirected complete Euclidean weighted** graph $G(V, E)$ and its **MST** $T$. I need to **remove** an arbitrary vertex $v\_i \in V(G)$, and given a vertex $v\_j \notin V(G)$, I have to calculate the MST of $$G^{'}((V(G) \backslash \\{v\_i\\})\cup\\{v\_j\\}, (E\backslash\\{(v\_i, v\_k): v\_k \in V(G)\\})\cup\\{(v\_k, v\_j): v\_k \in V(G^{'})\\}),$$ i.e, the graph $G$ with the vertex $v\_j$ (and edges from $v\_j$ to every other vertex) and without the vertex $v\_i$ (and its respective edges). To solve this, we can apply some well-known MST algorithms, such as Prim's, Kruskal's, Borukva's algorithm. Neverthless, if we do this we would not use the already existing MST $T$, i.e., we would calculate a new whole MST. So, I would like to know if there is any way to reuse the existing MST $T$.

There are two similar questions to this here (with edges, considering only the removing of them), and here (with vertex, considering only the adding of them).

The vertices are points in $\mathbb{R}^2$, and the weight on each edge is the Euclidean distance between the two points.

# Answer
> 0 votes
After long hours facing this problem, with my advisor help, we could solve this problem in $O(|E(G^{'})| log\text{ }C)$ time complexity by using one iteration of the Boruvka's algorithm, where $C$ is the number of connected components of $G^{''} (V(G^{'}), T\backslash \\{(v\_k, v\_i): v\_k \in V(G^{'})\\})$, i.e., the number of connected components of the MST $T$ by removing $v\_i$ (and edges from $v\_i$ to every other vertex in $T$) plus one (due to the inserted vertex $v\_j$).

Note that, this solution might have $O(|E(G^{'})| log\text{ }|V(G^{'})|)$ time complexity if the removing of $v\_i$ in $T$ (and edges from $v\_i$ to every other vertex in $T$) lead to a totally disconnected graph. Also, note that, this solution has $\Omega(|E(G^{'})|)$ if C is equals to 3.

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


# Question
Title: Difference between DNS Spoofing and DNS Hijacking?
DNS Spoofing and DNS Hijacking, both of them basically are type of attacks where the request is redirected to some other malicious website or some other web page. But I did not find some concrete difference between them, Can someone please explain the primary difference between DNS Spoofing and DNS Hijacking..

# Answer
One way of explaining the primary difference between DNS Spoofing and DNS Hijacking is given by this site as:

> While DNS spoofing is often confused with DNS hijacking as both happen at the local system level, they are two different types of DNS attacks.
>
> Most of the time, DNS spoofing or cache poisoning just involves overwriting your local DNS cache values with fake ones so you can be redirected to a malicious website.
>
> On the other hand, DNS hijacking (also known as DNS redirection) often involves malware infections in order to hijack this important system service. In this case, the malware hosted on the local computer can alter the TCP/IP configurations so they can point to a malicious DNS server, one that will eventually redirect the traffic to a phishing website.

So, DNS spoofing is where some malware or something else changes values in your local DNS cache (on your PC, for example), with fake values so you would query and go to the wrong destination.

DNS hijacking, on the other hand, is not so much about attacking your local DNS cache, but something else like the TCP/IP configurations so your PC's pointer to DNS is diverted to a malicious DNS server that could redirect traffic to a malicious website.
> 0 votes

# Answer
DNS Spoofing is a DNS attack that changes DNS records returned to a querier DNS Hijacking is a DNS attack that tricks the end user into thinking they are communicating with a legitimate domain name.
> 0 votes

---
Tags: computer-networks
---


# Question
Title: Mapping reduction from $A_{TM}$ to $INFINITE_{TM}$ same as to $ALL_{TM}$?
I was trying to solve a problem with a mapping reduction from $A\_{TM}$ to $INFINITE\_{TM}$, and came across a solution that was 100% identical to another solution I saw for $A\_{TM} \leq\_M ALL\_{TM}$. This is the reduction:

---

$M\_f$: Given an input of $\langle M, w\rangle$, where $M$ is a $TM$ and $w$ is a word:

Define a TM $M\_1$:

Given the input $x$ do:

1. Run $M$ on $w$ and return its result
2. Return $\langle M\_1\rangle$

---

This is correct for $ALL\_{TM}$ because if $M$ accepts $w$, $L(M\_1)=\Sigma^\*$, whereas if it rejects, $L(M\_1)=\emptyset$

However, it is also given as a solution for $A\_{TM} \leq\_M INFINITE\_{TM}$, where

$INFINITE\_{TM}=\\{\langle {M \rangle} |$ $M$ is a $TM$, $L(M)$ is an infinite language $\\}$, for example here: http://www.sfu.ca/~kabanets/308/lectures/lec7.pdf

I don't fully understand why theirs, or other similar explanations, are correct. What about infinite languages that aren't $\Sigma^\*$? What about finite languages that aren't $\emptyset$?

# Answer
> 1 votes
The m-reducibility definition says

> Language $A$ is m-reducible to $B$ (denoted $A\leq\_mB$) if there is a computable function $f:\Sigma^\* \rightarrow \Sigma^\*$ such that for every $w\in \Sigma^\*$, $$w\in A \iff f(w)\in B$$

The point you should pay attention to is that there is no need to talk about every $x\in B$. If you can map all elements of $A$ to one special element of $B$ say $x\_0$ and all strings that don't belong to $A$ to string which doesn't belong to $B$ say $y\_0$ then you are done!

Maybe if you think of $A\leq\_m B$ as language $B$ *is harder than* $A$ then you feel better about the reduction. This means if you can decide $B$ then you also can also decide $A$.

So by the proof, you have provided we map every $\langle M,w\rangle \in A\_{TM}$ to $\Sigma^\*$ and every $w' \notin A\_{TM}$ to $\emptyset$. Thus $INFINITE\_{TM}$ is harder than $A\_{TM}$. If you could decide just one elements of $INIFINITE\_{TM}$ which is $\langle M \rangle$ that $L(M)=\Sigma^\*$ then you could decide $A\_{TM}$.

---
Tags: turing-machines, reductions, undecidability
---


# Question
Title: If X is polynomial reduction to Y and Y is in NP, then X is in NP?
If X is polynomial reduction to Y and Y is in NP, then X is in NP?

Is this true, false or "we don't know"? Why?

# Answer
It's true:

Assume $Y\in NP$. Now let $N$ be the poly time verifier for $Y$. Lets also call the poly time reduction $\phi$.

Then, notice that $x\in X\iff\phi(x)\in Y\iff \exists w.N(\phi(x),w)$.

Therefore, let us build the poly time verifier for $X$ as follows:

$M(x,w):$

* Compute $\phi(x)$ in poly time
* Emulate $N(\phi(x),w)$ and accept if and only if $N$ accepted.

Now $M$ is polynomial since $\phi$ is and also $N$ is. We also have $x\in X\iff \exists w.N(\phi(x),w)\iff \exists w.M(x,w)$ and thus $M$ is a poly time verifier for $X$, and so we can conclude $X\in NP$
> 2 votes

---
Tags: complexity-theory, terminology, complexity-classes, p-vs-np
---


# Question
Title: The underlying type theory of HOL/Isabelle
Is there a good source on the type theory of HOL/Isabelle/other HOL-based LCF-style theorem provers?

# Answer
> 1 votes
I don't think Isabelle's implementation manual is a good place to look at this. It may certainly contain links to the explanation but you can find instead a pedagogical introduction in section 2 of this thesis.

---
Tags: reference-request, type-theory, proof-assistants
---


title: MAXSAT using dpll algorithm?

text:
# Question
Title: MAXSAT using dpll algorithm?
It's possible to return from a dpll algorithm M as maximum for MAX-SAT problem?:

I have a sample:

https://gist.github.com/davefernig/e670bda722d558817f2ba0e90ebce66f

we can modify recurrency to return the outcome of MAX-SAT?

Resources: https://en.wikipedia.org/wiki/DPLL\_algorithm

# Answer
The DPLL algorithm doesn't try to satisfy as many clauses as possible. If there is a satisfying assignment, DPLL will find it. Otherwise DPLL will try a series of partial assignments until it runs out of possibilities, and then it will declare the formula unsatisfiable. But in the case of an unsatisfiable formula, there is no guarantee that DPLL will discover the maximum number of satisfiable clauses on the way to proving unsatisfiability.

The MAXSAT problem is related to finding the minimally unsatisfiable subformulas (MUSes) of an instance. Determining whether a set of clauses is a MUS is a DP-complete problem. This is expected to be harder than mere NP-completeness, so it is unlikely that modifying DPLL to return partial solutions is going to be fruitful. Given that the class DP is contained in $\Delta^P\_2$ you might devise a scheme that calls DPLL (or related algorithms) a polynomial number of times to produce a MAXSAT result.
> 2 votes

---
Tags: np, satisfiability, recursion
---


title: Is the leapfrog automata problem in P?

text:
# Question
Title: Is the leapfrog automata problem in P?
1. My question is whether a specific decision problem—finding a computation path through a "leapfrog automaton"—is in P or not. It's straightforwardly in NP, and it resembles the hamiltonian path problem in some respects, but it also seems a little easier and I haven't been able to find a reduction.
2. **Definition**. A *leapfrog automaton* is a special kind of machine. A leapfrog automaton consists of a finite number of registers each of which contains a nonempty word from $\Sigma^\*$. There is also a special start register containing the empty word. At any given point, exactly one of the registers is marked as active; initially, it is the special start register.

Like a DFA or NFA, a leapfrog automaton can consume words, accepting or rejecting them. Given a word $w$, if the word is empty, the automaton accepts. Otherwise, the automaton consumes the next symbol $\alpha$ in the word: if there is a register *other than the active register* whose word contains $\alpha$, the automaton nondeterministically picks one such register and sets it to active. It also nondeterministically picks one instance of the symbol $\alpha$ in the register and marks it as "visited". On the other hand, if none of the other registers have $\alpha$ in their word, the automaton rejects the word $w$.
3. **Path problems**. If a leapfrog automaton $M$ accepts a word $w$, we can examine all of the symbols that were marked as visited in all the registers during the computation. Suppose the machine maintains a record of which symbols in which registers were visited, in which order; this is called a *computation path*.

The Blackout Decision Problem is: "Given a leapfrog automaton $M$ and a word $w$, is there an accepting computation path for $w$ which visits every symbol in every register at least once?" (Alternatively: exactly once?)
4. This Blackout Decision Problem is straightfowardly in NP; we nondeterministically choose a computation path and accept if it visits each symbol in each register exactly once, which is checkable in P.

On the other hand, I'm not sure whether the problem is in P or not. I've been trying to construct a reduction from, say, HAMPATH, which would establish that the problem is NP-complete and would therefore convince me it isn't in P.

Such a reduction might look like: Given a graph, construct a leapfrog automaton with one register for every node in the graph. The word in each register lists the nodes that are neighbors of that node. (Not sure where to go from here.)

So, to reiterate, is the blackout decision problem in P? Alternatively, can we show that it's NP complete?

---

**Examples**: A leapfrog automaton has two nonempty registers, containing VNS and ED, respectively. Among other words, it accepts VEND, EVEN, SEVEN, and the empty word. (Note how the order of letters in a register is irrelevant, and letters may be reused, and the first letter may come from any register.) It rejects the word SEVER, because the symbol R doesn't appear in any register. It rejects the words DEN and SEEN, because each letter must come from a different register than the one before.

Because the registers of this particular automaton have no letters in common, every computation path is unique and unambiguous\[\*\]. In contrast, suppose we have a new automaton with three nonempty registers: HP AX A. The word HAX has exactly one accepting computation path, since each letter must come from a new register. The word HAPAX, however, has two accepting computation paths. One of those computation paths visits the third register "A" twice. The other path visits both letter "A"s. That other path is an example of a path that visits every symbol in every register at least once.

Because such a computational path exists, the Blackout Decision procedure, for this machine and this word HAPAX, answers yes (i.e. there is an accepting computational path for this word which visits every letter in every register at least once.)

---

ETA: If the alphabet is unary ($\Sigma = \\{\mathtt{a}\\}$) then the blackout problem is in P. The problem becomes finding a tour that visits each register the appropriate number of times while obeying the "different registers" constraint. Starting from the initial (empty) register, my algorithm is to iteratively visit whichever other register currently has the most unvisited letters (break ties arbitrarily). If there is a tour that satisfies the different-registers constraint, this procedure will find it.

Such a tour does not always exist when there are big disparities between the register sizes. For example, if the automaton has two nonempty registers AAAAAA and AAA, there is no accepting path (for any word!) that visits each letter in each register exactly once.

I haven't figured out whether the problem is efficiently solvable when the alphabet has two letters in it {A,B}.

---

\[\*\] This implies that the Blackout Decision Problem for leapfrog automata is in P when we restrict to machines whose registers have no letters in common. The general case has branching factors which may make it harder than P.

# Answer
$\newcommand{\nameq}{\stackrel{\tiny def}{=}}$

# Problems

For an NP-completeness proof, let's rephrase the **Blackout Decision Problem** as "Given a leapfrog automaton $M$ and word $w$, does $M$ accept $w$ without revisiting any of its registers' symbols?". It's probably your intuition that the "visits each symbol once" version is no easier, and a reduction to that version is pretty easy, so I'll omit that.

We'll reduce to a problem I'll call **DECAY-3SAT**, which is a version of **3-SAT** that allows the truth of each variable to decay to false in subsequent clauses. For example, $v\_0=1$ (true) and $v\_1=0$ (false) satisfies $(v\_0\lor v\_1 \lor v\_1)\land(\lnot v\_0 \lor v\_1 \lor v\_1)$ because $v\_0$ can become false for the second clause. Note that the verifier still runs in polynomial time because it will be given the decay events along with the initial literal truth values. Additionally, **DECAY-3SAT** is no weaker than **3-SAT** because a standard 3CNF formula $\phi$ with $n$ variables is satisfiable if and only if $\phi'\nameq\underbrace{\phi\land\dots\land\phi}\_{n+1\text{ times}}$ is satisfiable with decay since one of those $\phi$ will be evaluated without decay, as decay can happen at most $n$ times (once per variable).

# Reduction

Given a 3CNF formula $\phi\nameq C\_0\land\dots\land C\_{m-1}$, we will construct a leapfrog automaton $M$ with input $w$ such that $M$ accepts $w$ if and only if $\phi$ is satisfiable with decay.

## Programming 3-SAT with Decay

For each clause $C\_i$, make a symbol $c\_i$ and put $2$ copies at register $2i$ and put $3$ copies at register $2i+1$. The idea here is to take away symbol $c\_i$ each time a variable appears in clause $C\_i$. If its current truth assignment satisfies $C\_i$, we'll take $c\_i$ away from the odd register, otherwise we'll take $c\_i$ away from the even one. This forces at least one truth assignment to satisfy $C\_i$.

Without yet going into the details, we can construct $M$ and $w$ in a way that implements simple programs made of 4 kinds of instructions. Those instructions and their use in this reduction are:

* $\texttt{NEW\_VARIABLE\_FIRST\_CLAUSE}$: Go to register $0$ or $1$ nondeterministically.
    + Consider $v\_j$ (0-indexed) as the *current variable*, where $j+1$ is the number of times $\texttt{NEW\_VARIABLE\_FIRST\_CLAUSE}$ has been called. This should be the first instruction in any program.
    + This instruction chooses the initial truth value of $v\_j$ (even means false, odd means true).
* $\texttt{NEXT\_CLAUSE\_DECAY}$: From the current register $r$, go to register $r+2$ or $r+2-(r\mod 2)$ nondeterministically. The second option may happen when $r$ is currently odd, which represents the variable decaying to false.
    + Call this $m-1$ times for each variable, or at least enough times to reach each clause $C\_{\lfloor\frac{r}{2}\rfloor}$ that the current variable appears in.
* $\texttt{DECREMENT}$: Decrement count of the current clause symbol $c\_{\lfloor\frac{r}{2}\rfloor}$ at current register $r$.
    + Call this as many times as the current variable appears as a positive literal in the current clause.
    + Note that when the current variable is true (i.e., $r$ is odd), this decrements from the odd register, and the clause is effectively satisfied.
* $\texttt{DECREMENT\_NEGATED}$: Decrement count of current clause symbol $c\_{\lfloor\frac{r}{2}\rfloor}$ at register $r+1-(r \mod 2)$.
    + Call this as many times as the current variable appears as a negative literal in the current clause.
    + Note that when the current variable is false (i.e., $r$ is even), this decrements from the odd register, and the clause is effectively satisfied.

Such a program will reject if it tries to decrement the number of clause symbols in a register that does not have any. Otherwise, it will accept. Hopefully that's enough to convince you that the NP-hardness reduction holds if we can actually construct an $M$ and $w$ to implement the program.

## Implementing the 4 Instructions

Now comes the task of writing a compiler. We'll do so by adding symbols to $M$ and $w$ for successive instructions. Luckily the instructions are pretty restrictive, so we can track the current clause $C\_i$ associated with each one, even though we don't know whether the current register will be $r=2i$ or $r=2i+1$ during execution.

To guide execution through the appropriate registers, most symbols we introduce will have the clause index $i$ as a subscript. For example, we'll add quite a few $\lambda\_i$ symbols to registers $2i$ and $2i+1$ simply as a way to jump between them.

* Initially: For each clause $C\_i$, put $3$ copies of its symbol $c\_i$ in register $2i+1$ and put $2$ copies in register $2i$.
    + Mentioned in the previous section; copied here for completeness.
* $\texttt{NEW\_VARIABLE\_FIRST\_CLAUSE}$: Add $\lambda\_0$ to registers $0$ and $1$ in $M$. Append $\lambda\_0$ to $w$.
    + When $M$ encounters $\lambda\_0$ it will go to register $0$ or $1$ and consume the symbol. Pretty straightforward.
* $\texttt{DECREMENT}$: Add $\lambda\_i$ to registers $2i$ and $2i+1$. Append $\lambda\_i c\_i$ to $w$.
    + The automaton, currently at register $2i$ or $2i+1$, will jump to the other of those two registers to consume $\lambda\_i$, then it will jump back to its first register to consume the $c\_i$ symbol.
* $\texttt{DECREMENT\_NEGATED}$: Add $\lambda\_i$ to registers $2i$ and $2i+1$. Append $c\_i \lambda\_i$ to $w$.
    + The automaton, currently at register $2i$ or $2i+1$, will jump to the other of those two registers to consume $c\_i$, then it will jump back to its first register to consume the $\lambda\_i$ symbol.
* $\texttt{NEXT\_CLAUSE\_DECAY}$: Add $\delta\_i$ to registers $2i$ and $2i+3$. Add $\lambda\_{i+1}$ to registers $2i+2$ and $2i+3$. Append $\delta\_i \lambda\_{i+1}$ to $w$.
    + If the current register is $2i$, this step is straightforward. First the automaton jumps to register $2i+3$ to consume the $\delta\_i$ at register $2i$. Then it jumps to register $2i+2$ to consume $\lambda\_{i+1}$. In this way, a false variable progresses to the next clause without losing its falseness.
    + If the current register is $2i+1$, there are a few paths to take.
        - Case 1: First, the automaton jumps to register $2i$ to consume $\delta\_i$, then it jumps to register $2i+3$ to consume $\lambda\_{i+1}$. In this way, a true variable **can** progress to the next clause while retaining its truthiness.
        - Case 2: The automaton jumps to $2i$ to consume $\delta\_i$ then jumps to $2i+2$ to consume $\lambda\_{i+1}$. The variable's truthiness has decayed.
        - Case 3: The automaton jumps to $2i+3$ to consume $\delta\_i$ then jumps to $2i+2$ to consume $\lambda\_{i+1}$. The variable's truthiness has decayed.

## Example

For clarity, here's a construction for $\phi = (v\_0\lor v\_1 \lor v\_1)\land(\lnot v\_0 \lor v\_1 \lor v\_1)$. We'd write a program:

```
NEW_VARIABLE_FIRST_CLAUSE  // Choose v[0].
DECREMENT  // v[0] appears in the first clause.
NEXT_CLAUSE_DECAY
DECREMENT_NEGATED  // v[0] appears as negated in second clause.
NEW_VARIABLE_FIRST_CLAUSE  // Choose v[1]
DECREMENT  // v[1] appears twice in the first clause.
DECREMENT
NEXT_CLAUSE_DECAY
DECREMENT  // v[1] appears twice in the second clause.
DECREMENT

```

This complies to a leapfrog automaton $M$ with 4 registers, 2 for each clause, and a word $w$.

* $w=\lambda\_0 \lambda\_0 c\_0 \delta\_0 \lambda\_1 c\_1 \lambda\_1 \lambda\_0 \lambda\_0 c\_0 \lambda\_0 c\_0 \delta\_0 \lambda\_1 \lambda\_1 c\_1 \lambda\_1 c\_1$.
* Register $0$: $2 c\_0$, $5 \lambda\_0$, $1 \delta\_0$.
* Register $1$: $3 c\_0$, $5 \lambda\_0$.
* Register $2$: $2 c\_1$, $5 \lambda\_1$.
* Register $3$: $3 c\_1$, $5 \lambda\_1$, $1 \delta\_1$.
> 8 votes

# Answer
Just want to augment grencez's excellent answer with some gadget illustrations:

1. There are two registers corresponding to each clause, plus two variable-initialization registers.
2. Each clause has three unique symbols/colors, $C\_i$ $v\_i$, $\delta\_i$. Those colors only appear in the clause's two registers, helping to constrain movement.
3. Each pair of registers is initialized with five $C\_i$ symbols arranged as follows:

This gadget helps enforce the rule that the clause must be satisfied by at least one literal.
4. To translate a formula $\Phi$ into a leapfrog automaton and agenda, we read the formula $\Phi$ and iterate over the variables in turn.

a. First we add a variable initialization gadget

b. Then we iterate over each clause, checking whether the variable occurs. For each clause, we add a goto-next-clause gadget:

c. For every time the variable appears as a positive literal in the clause, we add a positive literal gadget. For every time the variable appears as a negative literal in the clause, we add a negative literal gadget. (They are identical except for the agenda order.)
5. By tightly controlling the available transitions, this process creates a leapfrog automata that is winnable if and only if the original formula is DECAY-3SAT satisfiable:

\[Interaction 1\] *When a variable assignment (whether true or false) satisfies the clause, a $c\_n$ symbol is removed from the top register.* Otherwise, it is removed from the bottom register. Because there are three literals in the clause, the game is unwinnable unless at least one is removed from the top.

\[Interaction 2\] *Because there are two registers per clause, the current register simultaneously encodes (a) what clause we're currently considering and (b) whether the current variable has been assigned true or false.* Because these are DECAY-3SAT problems, the goto-next-clause gadget allows a true assignment to optionally decay into a false assignment at any point, while preventing the reverse decay.
> 2 votes

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


title: Lower bound on comparison-based sorting

text:
# Question
Title: Lower bound on comparison-based sorting
I have a question from one of the exercises in CLRS.

> Show that there is no comparison sort whose running time is linear for at least half of the $n!$ inputs of length $n$. What about a fraction of $1/n$ of the inputs of length $n$? What about a fraction $1/2^n$?

I have arrived at the step where for a linear time sorter, there will we $2^n$ nodes in the decision tree, which is smaller than the $n!$ leaves so this is a contradiction but I am unsure of how to formally write out the proof and extend it to the other fractions? The question also states that "for at least half of the $n!$ inputs of length $n$". I do not quite understand how it affects the number of leaves in the decision tree as any input of length $n$ will have $n!$ possible permutations.

# Answer
> 1 votes
If there is a comparison sort whose running time is $f(n)$ on $g(n)$ of the inputs, then there are at least $g(n)$ leaves at depth at most $f(n)$, and so $g(n) \leq 2^{f(n)}$.

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