# Question
Title: Can POSIX BRE express all regular languages?
It appears that "Basic Regular Expressions" as defined by POSIX.1-2008 do not support alternation, `a|b` (although some grep implementations recognize the escaped version, `\|`).

Since the regular languages are closed under union by definition, does this mean that POSIX BRE has less expressive power than a finite automaton? Or is there some way to simulate alternation using other constructs?

# Answer
> 18 votes
Indeed the POSIX BRE language cannot express all regular expressions because it lacks alternation. It can't even recognize all finite languages, let alone all regular languages.

For example, $\\{ab, ba\\}$ is not recognizable as a BRE. To prove this, consider what the toplevel syntactic form could be:

* It can't be one of the single-character forms since the language has words of length $\gt 1$.
* It can't be $R^\*$ because that would match the empty string.
* It can't be $R^{\\{m,n\\}}$ except with $m=n=1$ (in which case we're back to the original problem) because that would match strings of different lengths or the empty string.
* So it has to be concatenation: $R\_1 R\_2$. Now consider how $ab$ is recognized:
    + If $R\_1$ recognizes $ab$ then $R\_2$ must not recognize anything anything other than the empty string. So $R\_1$ must recognize $\\{ab,ba\\}$ and we're back to the original problem.
    + If $R\_1$ recognizes $a$ but not $ab$ then $R\_2$ must recognize $b$. But then $R\_1R\_2$ recognizes all words of the form $u b$ where $R\_1$ recognizes $u$, so $R\_1$ must not recognize anything other than $a$. There's no way to recognize $ba$.
    + If $R\_1$ recognizes neither $ab$ nor $a$ then the only way for $R$ to recognize $ab$ is if $R\_1$ recognizes the empty string, in which case we're back to the original problem as above, but for $R\_2$ this time.

When “we're back to the original problem”, that means that the only solution to find a BRE recognizes the language is to find a smaller BRE that has the same property. This is an infinite descent, so there's no BRE that has the desired property.

I don't think there's a “nice” characterization of BRE-recognizable languages, for example as languages recognizable by a “nice” class of automata.

Note that BRE-recognizable languages are actually not a subclass of regular languages, since backreferences add expressive power. For example $\\{w w \mid w \in \\{a,b\\}^\*\\}$ is recognized by the BRE `\(.*\)\1` but is famously not regular. BRE without backreferences are just syntactic sugar over regular expressions so the languages they can recognize are a subclass of the regular languages.

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


title: Translating between coordinate systems

text:
# Question
Title: Translating between coordinate systems
Let's say I needed to render an image at 1920 x 1080 and also at 1024 x 768. Instead of drawing two separate images, it might make sense to draw the scene in a common "virtual" coordinate system and then translate that to the appropriate output coordinate system.

Is there a name for this problem? I'm having a hard time figuring out what to start searching for.

# Answer
> -1 votes
I'll try to answer my own question. The solution is an application of matrix transformations.

This lecture tries to explain some of the maths.

https://www.khanacademy.org/math/precalculus/precalc-matrices/matrices-as-transformations/v/transforming-position-vector

I think what I need to do is apply both a translation and scale matrix to each vertex in the "virtual" coordinate system to get them into the "physical" coordinate system.

Still trying to get my head around exactly how to do that.

---
Tags: algorithms, graphics
---


title: Is powerset construction deterministic?

text:
# Question
Title: Is powerset construction deterministic?
Powerset construction is used to convert a non-deterministic finite automaton (NFA) into a deterministic finite automaton (DFA). Is the method/algorithm used to do this deterministic itself and if so, why?

# Answer
> 3 votes
The method itself is (or at least can be made), though the question is somewhat ill posed. What do you mean by deterministic?

The algorithm cannot be run on an NFA or DFA, so it's not deterministic/non-deterministic in that sense.

In most cases, the algorithm will run on a Turing Machine, or some similar model (RAM machine, programming language, lambda calculus, etc.).

It's known that any non-deterministic Turing Machine can be simulated by a deterministic one, using backtracking. So in this sense, the algorithm certainly can be made deterministic.

Is it possible to define the powerset construction in such as way that it's non-deterministic? Yes. There's some element of choice in which states you process first, which NFA states you choose to expand, whether you look breadth-first or depth-first, etc.

But it's trivial to remove these choices, either by resolving them arbitrarily, or by making the choice with some heuristic.

# Answer
> 2 votes
The usual description of the powerset construction corresponds to a deterministic algorithm whose running time is polynomial in the output size.

Although non-deterministic Turing machines are equal in power to deterministic ones, they are (probably) not equivalent in terms of complexity (a particular case is the well known P vs. NP conjecture).

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


# Question
Title: Using B-method, and formal methods in general, to model and verify a reverse linked list
I am trying to do some formal modeling of a linked list, however instead of referencing the next block, each block needs to reference the previous block instead.

Is there already any formal methods or any formal for doing this ?

Exactly the same as a normal linked list but when a new block (value etc) is added this references the past value (much like the bitcoin blockchain).

I have modeled a normal linked list (Data queue) modeled in the b method

```
MACHINE DataQueue ( DATA , anydata , maxqueue )

CONSTRAINTS anydata E DATA /\ maxqueue > 0
SEES Bool TYPE
SETS TOKEN
PROPERTIES card ( TOKEN ) = maxqueue
VARIABLES TokenSeq , TokenMap

INVARIANT
TokenSeq E iseq ( TOKEN ) /\
TokenMap E TOKEN -|-> DATA /\
dom ( TokenMap )=  USED
INITIALISATION
TokenSeq , TokenMap : [] , {}

OPERATIONS
success , token <-- AddItem( item )  =^
PRE E item DATA THEN
CHOICE
ANY new token WHERE new_token  E TOKEN_USED
THEN
TokenSeq := TokenSeq <-- new token ||
TokenMap ( new token ) := item ||
success , token := TRUE , new token
END
OR
success := FALSE || token :E TOKEN
END
END ;
DEFINITIONS
USED =^ ran ( TokenSeq )
END

```

# Answer
> 3 votes
There are many approaches for verifying linked structures---arguably, more suitable than the B method---that you might want to use, depending on the language and properties you want to verify. Most of the approaches rely on separation logic (which was in big part motivated for verification of linked structures).

Some tools include:

To quote this answer (which answers a very similar question), even though you did not give details about what are you trying to verify, it seems that properties you might want to prove about the "reverse linked list" might be formulated as properties for a regular linked list. (If the reverse list requires some additional (non-standard) implementations, not already declared for the linked list, you might be able to model those in addition.)

I am not sure what was the purpose of your example, but your code seems similar to an example of modelling a linked list with B (which includes other standard operations) method in Program Development by Refinement Case Studies Using the B Method.

---
Tags: data-structures, formal-methods, linked-lists, b-method
---


# Question
Title: Why is Church-Rosser so important for basing programming languages on lamdba-calculus?
So, I know Church-Rosser has 2 thesis:

CR1: If $ E\_1 \leftrightarrow E\_2 $, then there exists an Expression E so $ E\_1 \rightarrow E $ and $ E\_2 \rightarrow E $

CR2: If $ E \rightarrow N $ (with N in normalform), then there exists a reduction row in normalorder (first reduce the left most ouuter most index) from E to N

from CR1 we learn that no expression can be converted to 2 different normalforms, so there is only one result for each function

from CR2 we learn that reduction in normalorder always finds the result (if their is one (no loop))

But i don't understand why these two are so important for basing a programming language on lambda-calculus. So my question is why are they?

# Answer
Think of it as a sanity check. CR cones from the days when we were just figuring out what programming languages were. The Lambda calculus was new, and its basic properties were unknown.

CR says that Lambda Calculus behaves like you would expect: every expression can be evaluated to a unique value, or runs forever. We didn't know if the calculus was well behaved. We had to prove it.

Imagine that CR didn't hold, and that the order you evaluated an expression mattered. We would throw Lambda calculus away. It would be like saying $2+2$ could have more than one value.

CR also justifies the existence of lazy languages, showing that they behave at least as well as eager languages, sometimes better. Haskell certainly owes its existence in part to CR.
> 8 votes

---
Tags: lambda-calculus, functional-programming
---


# Question
Title: Iterative lengthening search: iterative version of Uniform Cost Search or DFS?
Actually my question has two parts:

1) I wanted to know that whether Iterative Lengthening Search is used in combination with DFS or Uniform Cost Search? Actually, in Russell and Norvig book (on page 90), it is described as follow:

> It would seem worthwhile to develop an iterative **analog to uniform-cost search**, inheriting the latter algorithm's optimality guarantees while **avoiding its memory requirements**. The idea is to use increasing path cost limits instead of increasing depth limits. This resulting algorithm is called iterative lengthening search... It turns out, unfortunately, that iterative lengthening incurs substantial overhead compared to uniform-cost search.

It seems that by using "avoiding its memory requirements", they mean that we use it in combination with DFS.

But, here in this link, which is the solution of final exam problems of artificial intelligence course at CMU, on page 4, it is described as follow:

> Iterative lengthening search is an iterative version of uniform cost search. The main idea of this algorithm is that we use increasing limits on path cost.
>
> * We start searching as though we were performing uniform cost search.
>
> and so on...

And also here in this link, question 4, part 1:

> Iterative lengthening is uniform-cost search which is run multiple times with an increasing bound on the maximum cost from the start to reach before quitting. Iterative lengthening search doesn't have advantages in the same way iterative deepening depth-first search does.Iterative lengthening will simply search the same nodes each time adding more at the end since the first closest node, second closest node, etc. is invariant. All that iterative lengthening does is require the algorithm to restart repeatedly before finding a solution.

It seems that they mean we use it in combination with Uniform-Cost search.

Actually, I implemented it using uniform cost search, but to me there is no point in running uniform cost search over and over from beginning while increasing path cost limit (I mean using DFS seems more reasonable).

So which one is correct? (Is it the case that I misinterpreted them?)

2) Would you clarify why iterative lengthening search occurs substantial overhead?(Actually in case of using Uniform-cost search it is obvious, but I wanted to know this in case of using DFS.)

**Clarification:**

In order to resolve any ambiguity, here is pseudocodes for ILS in both cases(using DFS or UCS):

*ILS using DFS:*

```
0. Set limit to zero.
1. Perform DFS on initial node while discarding any generated node with path cost greater than limit.
2. If DFS ended with Failure or Success, return that as a result.
3. Otherwise set limit to minimum path cost of generated nodes that were discarded in previous run of DFS.
4. Go to line 1.

```

ILS using UCS:

```
0. Set limit to zero.
1. Perform UCS on initial node while discarding any generated node with path cost greater than limit.
2. If UCS ended with Failure or Success, return that as a result.
3. Otherwise set limit to minimum path cost of generated nodes that were discarded in previous run of UCS.
4. Go to line 1.

```

I was thinking about this for the past week. I think that ILS in combination with UCS has no advantages to UCS itself. While ILS in combination with DFS, at least is much better than UCS in terms of memory usage. And I think overhead occurs because in both of them, in each iteration only one more node(or a few if we have several nodes with same minimum path cost) is added to nodes that we explore in next iteration. However I'm not sure about these.

# Answer
> 1 votes
Typically iterative deepening searches are used with DFS to improve the memory usage.

Consider BFS and IDDFS, both are optimal and complete but IDDFS in a tree search will use only $O(bm)$ space, where $b$ is thebranching factor and $m$ is the maximum height of the goal.

Now extending this to Uniform Cost Search using DFS, if we increase the max depth step by step, we are doing too many iterations over already visited nodes, whereas this was not true in case of IDDFS because of one step increase at a time (look for the overhead factor). So though using iterative search with DFS can save huge space ($O(bm)$), it gets worse with time complexity.

Secondly, there is no point in using Iterative Search with UCS as it is never a better upgrade over simple UCS in terms of space and time complexities.

---
Tags: algorithms, artificial-intelligence, search-algorithms, graph-traversal
---


# Question
Title: Scheduling N variable-time interdependent tasks across M workers
I have N tasks, each of them requires some time to complete. Time to complete is not the same for all tasks. Each task may depend on a number of other tasks (assume, that no dependency cycles are present). I have M (M is fixed, small and \<\< N) workers that may be used to complete the tasks. I need to find a sequence of tasks, that each worker must complete in order to minimize the total processing time.

How is this problem formalized / modelled? I am not sure, which textbook or paper I should read in order to understand, how one might approach this problem (looking for keywords here).

If there is a need to "peg" some tasks (not all) to certain workers, how is the problem "affected"? That is, does it become significantly harder to solve or reason about?

# Answer
This can been seen as a variation of the job shop problem where you want to find the policy that yields the minimum makespan (time taken for all machines to process all jobs); as well as a variation of the assignment problem (find the optimal pairing of workers to jobs that minimizes cost). The variation in both cases is an added dependency between jobs (Job A must complete before Job C) etc. This collection of combinatorial optimization problems is NP-Hard. Most of what you'd find in the literature is approximation heuristics to find a near optimal policy (sequence of tasks per worker).

This paper is one such approach: "Approximation Algorithms for Multiprocessor Scheduling under Uncertainty"

A quick way to solve your problem (quick as in prototype a solution, not necessarily runtime, or necessarily near optimal), is to construct a topological sort of your job dependency graph, use breadth first search to batch all jobs of a given height and put that batch on a stack (assumes directed edge represents a depends on relationship, with zero out degree nodes having no dependencies). Afterwards, Until the stack is empty, pop a batch and treat it as a traditional assignment problem and solve using the Hungarian algorithm, then enqueue the tasks to each assigned worker's task queue. Afterwards you'd have a policy. (When you go to execute the policy, you'd have to have some signalling mechanism that a task completed so that workers don't start on a task whose dependencies haven't finished yet.)
> 2 votes

---
Tags: optimization, scheduling, modelling
---


title: Computing counts of combinations (?)

text:
# Question
Title: Computing counts of combinations (?)
I'm not sure what terminology to use. Here is some input:

```
John  has items: A B D
Peter has items: A C D

```

And I want to produce such a table, that would count the # of people having these items (0-count is not required to be outputted):

```
A     2
B     1
C     1
D     1
A,B   1
A,C   1
A,D   1
A,B,D 1
A,C,D 1

```

What's the name of such a table and what sort of efficient algorithm could I use to produce it?

Functional programming style more preferable. An Excel solution would be great though I'm not sure it's doable.

It would be used to determine if there are any correlations.

Thank you.

PS here is a rudimentary example solution in Scala which isn't efficient:

```
scala> val items = List('A', 'B', 'C')
items: List[Char] = List(A, B, C)

scala> val people = List(List('A', 'B'), List('B', 'C'))
people: List[List[Char]] = List(List(A, B), List(B, C))

scala> val combos = (1 to items.size).view.map(items.combinations(_).map(_.toSet).toSet).flatten
combos: scala.collection.SeqView[scala.collection.immutable.Set[scala.collection.immutable.Set[Char]],Seq[_]]#Transformed[scala.collection.immutable.Set[Char]] = SeqViewMN(...)

scala> combos.map(s => s -> people.count(p => s.subsetOf(p.toSet))).toMap
res15: scala.collection.immutable.Map[scala.collection.immutable.Set[Char],Int] = Map(Set(A, C) -> 0, Set(B) -> 2, Set(A, B, C) -> 0, Set(A, B) -> 1, Set(A) -> 1, Set(C) -> 1, Set(B, C) -> 1)

```

# Answer
> 3 votes
These combinations of items are sometimes called *itemsets*. There are algorithms for finding itemsets that are especially common in a database; see association rule learning.

In general there is no efficient algorithm for producing such a table, as the size of the table can be exponentially large in the size of the input. Consequently any algorithm will take exponential time on at least some inputs (i.e., will be extremely slow on at least some inputs). You might want to consider what you plan to do with the table and whether there's a way to achieve your ultimate goal, without building the table explicitly; that might turn out to be a better approach.

---
Tags: algorithms, permutations, counting
---


# Question
Title: A linear temporal property that represents this (basic) execution?
A question gives me a set of atomic propositions `AP = {a, b, c}`and asks me to give a linear temporal property that represents all executions over AP such that:

(1) *a* and *b* never happen at the same time

**OR**

(2) *a* is preceded by *c*

Can anyone give me some pointers on how to answer this question (possibly with a model solution)? So far all I have done is split the property into two parts such that the property $P$ is the union of $P\_1$ and $P\_2$ but I don't know how to formulate my answer.

(This question is from a past exam paper).

Any help is highly appreciated.

# Answer
Since you are asked to formulate these properties in LTL, you might want to think of them as properties given with predicates over infinite sequences of states (or events where each event changes the state); in your case, you know that at each state some of the three propositions, `{a, b, c}` might be true.

When we talk about LTL, it's good to summarize what does the formalism support to figure out whether the given property can be formulated in it. Note that previously mentioned propositions are often formulated as *state formulas*, which might hold in a particular state. So, LTL supports: state formulas (propositions that might hold in particular state), (standard) Boolean operators (like logical or `||`), and path quantifiers (like globally `G` and next `X`, which produce other state formulas), which effectively allow state formulas to describe sequences of states.

I will describe one potential solution in the "extended" LTL, which includes additional operators besides the fundamental ones. (These are easily expressible using only the basic operators, next and until; more details can be found in a more thorough treatment of LTL).

> So far all I have done is split the property into two parts such that the property P is the union of P1 and P2 but I don't know how to formulate my answer.

Indeed, at the top level, as you recognized, you should have union, which effectively translates to `||` of `P1` and `P2`:

```
P1 || P2

```

Going back to `P1` ((1) a and b never happen at the same time), which states that something should *never* happen, it's good to think whether such temporal quantification can be translated to some of the offered quantifiers in LTL. This is indeed possible, and "*never* some property `P`" can be expressed in terms of combining a Boolean operator and a quantifier, in the following way:

> `G( not P )` (always, P is not true)

thus, `P1` can be expressed by using given propositions as:

> `G( not (a && b) )` (always, it is not true that both `a` and `b` hold)

On the other hand, as Shaull pointed out, the second property is a bit trickier. Although, such a requirement might have been written more precisely (to avoid ambiguity), we can interpret it to mean that `a` and `c` should happen, at some point, such that `c` happened earlier than `a`.

Now, when we identified *earlier*, we might think of another LTL quantifier that semantically matches the notion of ordering states (or events). That quantifier is:

> `X` (quantifier for next, i.e. formula that will hold in the next state)

Thus (under the interpretation that both propositions must be true at some point), we want to say that eventually, `c` happens, while at a point after that, eventually `a` happens as well:

> `F( c && X(F a))`

arriving at the final solution:

> `P1 || P2 = (G( not (a && b) )) || F( c && X(F a))`

which checks that either of the given properties are satisfied in the execution, as you originally suggested.

After you have an idea of how the formula should look like to makes sense (semantically, with respect to the property you want to model), you always want to check whether the formula is well formed, i.e. whether the formula is syntactically correct. (More details can be found in one of the more thorough treatments of LTL.)
> 1 votes

---
Tags: model-checking, linear-temporal-logic
---


# Question
Title: Is paradox recognition paradoxical or not paradoxical?
Russell's paradox: The set that contains all the sets that do not contain themselves. Does it contain itself? It contains itself if and only if it does not contain itself.

Russell's paradox for the lambda-calculus: The functions that may not be applied to themselves when combined with themselves, they negate themselves.

lambda calculus uses anonymous functions called lambda-expressions. So, the paradox re-stated in lambda-calculus terms becomes:

The lambda-expressions that may not be applied to themselves when combined with themselves, they negate themselves.

If such a lambda-expression is encoded into a string w, then input to a Turing machine, will the Turing machine (Paradox Recognizer machine) accept it? not accept it: reject it? or loop forever?

Thanks in advance for your comments.

Rafee Kamouna.

# Answer
Russel's paradox does not apply to the lambda calculus. Intuitively speaking, Russel's paradox comes up when there is a level system (e.g. sets that are members of “bigger” sets one level up), and there is a form of negation. The lambda calculus has neither: all lambda terms are at the same level and there is no negation.

I don't know what you think you mean by “The lambda-expressions that may not be applied to themselves”. Any lambda term can be applied to any lambda term.

An analog of Russel's paradox (or rather the similar Burali-Forti paradox) arises in the higher-order **typed** lambda calculus, where terms have types that themselves have types. If $\mathsf{Type} : \mathsf{Type}$, it's possible to construct a well-typed term that of type $\mathsf{Type}$ that does not terminate. See Example of a false proposition when assuming Type : Type. As can be done in set theory, type theory can solve the problem by adding a universe stratification: base types have the sort $\mathsf{Type}\_0$ and higher-order types obey $\mathsf{Type}\_n : \mathsf{Type}\_{n+1}$.
> 4 votes

---
Tags: computability, lambda-calculus
---


# Question
Title: What method of collective recogintion to use for digits recognition?
***The structure of the question is as follows:*** at first, I provide the concept of *collective recognition*, further I provide explanation of the various methods of group classification that I found, in the end I introduce you the question. Those who are experts in this field and may not need explanations might just look at the headlines go straight to the question.

---

### **What is a collective recognition/classification**

What is meant by the term *collective recognition* is the task of using multiple classifiers (committee, ensemble, etc.), each of which will decide on the class of one entity with the subsequent coordination of their decisions with the help of a certain algorithm. Using a set of classifiers, typically lead to higher recognition accuracy and better computational efficiency indicators.

Some approaches of multiple classifiers decisions integration:

1. based on the concept of classifiers’ *competence areas* and procedures that assess the competence of classifiers with respect to each input of the classification system.
2. methods for combining classifiers decisions based on the use of *neural networks*.

---

### **Competence areas method**

The idea of collective classification based on the competence areas is that each base classifier can work well in some feature space area (*area of competence*), excelling in this area remaining classifiers in terms of accuracy and reliability of decisions. The area of competence of each base classifier must somehow be estimated. Appropriate program called *referee*. Classification task is solved so that each algorithm is only used in its own competence area, i.e. where it produces the best results compared to other classifiers. At the same time in each area the decision of only one classifier is taken into account. However, you must have certain algorithm that for any input determines which of the classifiers is the most competent.

So, one approach suggests that with each classifier a special algorithm (*the referee*, which is designed to assess the competence of the classifier) is used. What is meant by the term “*competence of the classifier*” in a given region of space of classification objects representation is the accuracy, i.e. probability of correct classification of objects whose description belongs to that area.

The general collective recognition training scheme that is based on competence assessment consists of 2 steps (Fig. 1). At the 1-st step training and testing of each individual base classifier is implemented. This step does not differ from conventional training schemes. In the next step, after each classifier testing, the training sample that was used in the testing phase of a certain classifier, is divided into two subsets, L+ and L-. The 1-st subset includes those instances of the initial test sample that were classified correctly during testing. The 2-nd subset includes other instances of the test sample, i.e. those that were classified incorrectly. Considering these two data sets as the areas of competence and incompetence of the classifier, it can be used as training data for "referee" algorithm training process. During new data classification the task of referee is to determine (for each input instance) whether it belongs to its area of competence or not, and if it belongs, estimate the probability of correct classification of this particular input instance. After that the referee instructs the most competent classifier to solve the classification task.

---

### **Neural network approaches.**

*Neural network* approaches of collective classification divided into methods: that use neural network to combine multiple classifiers, *ensembles of neural networks* and those that use neural networks constructed from modules.

**A neural network for combining classifiers**
One approach uses a neural network to combine basic classifiers multiple decisions (Fig. 2). The output of each base classifier is a decisions vector (a vector containing 'soft tags' values), the values of which belong to a certain numerical interval \[a, b\]. These values are delivered to the neural network input (network must be trained to combine base classifiers decisions). The output of the neural network is a final decision in favor of one or another class. The output of the network can also be a vector whose dimension is equal to the number of classes of objects to be recognized that at each position has some confidence degree value in favor of one or another class. In this case, the class with a maximum value of such confidence value can be selected as a decision.

*Decisions integration functionates as follows:*

1. a number of base classifiers is selected and trained;
2. metadata for the neural network training is prepared. For that, base classifiers are tested using the interpreted data sample. Then for each test sample a vector of base classifiers decisions is generated. Then, a component which includes the true class value of the test sample is added to the decisions vector;
3. meta-data sample is used for training the neural network that performs decisions integration.

---

### **Modular neural networks method**

For *modular neural networks* it is proposed to use the so-called *gating network* (neural network for assessing the classifiers’ competence for a particular input vector of data provided for classifiers). This option represents the neural network paradigm to integrate decisions based on competences. The corresponding theory is called *mixture of experts*. Each classifier is associated with the so-called "referee" program, which predicts its competence degree with respect to a specific input, that a set of base classifiers is provided with (Fig. 3).

Depending on the input vector **X**, decisions of different classifiers can be somehow selected and used in order to obtain a combined decision. Number of inputs of predicting network equal to the dimension of the input vector of feature space. Number of network outputs equal to the number of classifiers **L**. Given a specific input vector, predicting neural network is trained to predict the competence degree of each classifier, i.e. evaluation of the fact that the classifier provides the correct decision. The degree of competence is represented by the number on the interval **\[0,1\]**.

---

### **Ensembles of Neural Networks**

Also, decisions integration system architecture, which consists of several “experts” (neural networks) is proposed. Combining the knowledge of neural networks in the ensemble proved to be effective, demonstrating the prospects of application of the collective recognition technology to overcome the problem of "*fragility*".

*The ensemble of neural networks* \- a set of neural network models, that makes the decision by averaging the results of the individual models. Depending on how the ensemble is constructed, its use allows to solve one of two problems: the tendency of base neural network architecture to underfit (this problem is solved by boosting meta-algorithm), and tendency of the base architecture to overfit (bagging meta-algorithm).

There are various universal voting schemes, for which the winner is the class:

1. *maximum* \- with a maximum response of the ensemble members;
2. *average* \- with the highest average response of the ensemble members;
3. *majority* \- with the largest number of votes of the members of the ensemble.

---

### **My question**

Which scheme of collective recognition is most suitable for symbol/digit recognition?

Mostly, I will work with digits. Data sources from which I took the information about the various schemes of collective classification dated **2006**, and I am afraid that some methods may become obsolete.

I have mentioned the following methods:

* on the basis of *competence areas*
* on the basis of using a *neural network* to combine classifiers
* on the basis of *modular neural networks*
* on the basis of *neural network ensembles*.

Which method, potentially, can show better classification accuracy and performance in the task of symbols/digits recognition?

Or, are there new and more efficient methods of collective recognition/classification that I did not mention here?

# Answer
The state of the art for digit recognition does not use collective recognition, competence areas, ensembles, or any of the other ideas you propose in your question.

Instead, the state of the art for digit recognition uses convolutional neural networks. Just a convolutional neural network: no need for multiple of them, no need for any kind of other fancy business on top of it. Instead, the state of the art focuses on the specific architecture of the convolutional neural network (e.g., how many layers? what types of pooling?) and on the training procedures (e.g., adjusting the learning rate in stochastic gradient descent, dropout, batch normalization, and more).

As far as I know, the same is true for the state of the art for object/symbol recognition.

So, my advice is: while all those concepts sound nice on paper, they don't seem to actually be needed or useful for the tasks you care about. You're better off ignoring those concepts. Sorry to be the bearer of bad news when you've obviously put a bunch of effort into typing up an explanation of those concepts.
> 4 votes

---
Tags: machine-learning, artificial-intelligence, neural-networks, classification, pattern-recognition
---


# Question
Title: Does local optimization in a genetic algorithm decrease diversity?
I want to create a hybrid genetic algorithm for a project to solve really high dimensional problems (1000+) One of my ideas is to incorporate a local optimization method within GA so each individual will be optimized to its local optima before fitness evaluation. I've read some papers on hybrid GAs with hill climbing. So I understand that doing this will allow a somewhat fairer representation of each individual's search area by preventing the GA from obtaining bad sample from good search regions. It would obviously increase the search completeness. But I was wondering if adding such a local optimization method would significantly decrease genetic variation? If so, should this be a big problem? And how can one prevent it?

# Answer
The details depend on your fitness function, which you have not shared.

With your modification, you can only ever jump from one local optimum to the slope of another. Hence, you will certainly get little diversity if

* there are few local optima or
* the local optima are far apart but you do only small steps (e.g. local mutations).

In the first case, little can be done.

In the second case, you can alleviate the effects by making *larger steps*. Some standard techniques like crossovers can help. You may also want to look into simulated annealing. You can also keep both the original point and it's local optimum, and select globally.

On the other hand, if there are many local optima and/or they are close together, I would expect little problems and your approach is likely to speed up the search.
> 4 votes

# Answer
Adding on Raphael's answer:

* in a hybrid genetic algorithm (HGA), mutation plays a different role than it does in a "pure" GA.

The local refinement requirement of the mutation operator is unnecessary in the existence of an explicit local operator allowing the mutation operator to take a more exploratory role (see Evolutionary algorithms with local search for combinatorial optimization by Mark Land).

Using larger mutations, at least large enough to move from one basin to another, is a good idea.
* you can introduce parameters to control the frequency / duration / probability of local search so reaching a balance between GA and hill climbing.

Hybrid Genetic Algorithms: A Review by Tarek El-Mihoub, Adrian Hopgood, Lars Nolle and Alan Battersby contains further details.
* a nice approach you can try is to perform a local search only when the best offspring (solution) in the offspring population is also the best in the current parent population (aka *BOHGA*: **B**est **O**nly **H**ybrid **G**enetic **A**lgorithm).

This allows GA to explore a wide search space.
> 5 votes

---
Tags: algorithms, optimization, genetic-algorithms, evolutionary-computing
---


# Question
Title: Get mathematical relation of node IDs of a subtree based on a given tree
(I was not really sure in which "stackexchange" I should put this question. I hope CS is ok.)

Let's say I have the following tree A. Every node has a unique ID, which will be counted up, beginning from 0. The ID counting is taking place in breadth-first order.

Now I want to pick out a part of the graph A. The information of the subtree is given by a node ID in the original tree A.

**Example**

Let's say the new tree starts with the node ID 3 of the original tree. For this example, the tree depth has an offset of 1 (because 3 is in depth 1 of the original node). The result is the following

You might have noticed that the new tree have the same structure than the old tree. The unique ID of each node in the new tree, will also be counted up in breadth-first order. In the brackets, you can see the link to the original node tree A.

**Background**

The reason, why I need this node link is the fact that I need to copy some node properties from the original tree node to the new tree node.

**Question**

What is the mathematical relation between the unique node IDs of the new tree and the node IDs of the original tree? I want to compute the ID's of the old tree, based on the ID's of the new tree.

Thanks for any help.

# Answer
I don't think there is any "mathematical relationship". Observe that if you change the tree around the extracted subtree, the original IDs change arbitrarily.

You should copy properties while creating the copy of the tree you want to extract. Perform a tree traversal on the subtree in question and do everything in one pass.

You can also link new nodes to the old ones in case you need the relationship later.
> 1 votes

# Answer
This answer was based on a msiunderstanding of the question but I'll leave it here in case it turns out to be useful to anyone.

---

Clearly, the root of your subtree goes to ID 0 from whatever ID it originally had.

Now, consider the leftmost child on some row of the subtree. Let that vertex's ID in the original tree be $i$. If $i$'s parent is the root of the subtree, let $j$ be its ID in the original tree; otherwise, let $j$ be the ID of the parent's rightmost sibling (again, in the original tree). Finally, let $k$ be the ID of vertex $j$ in the new tree.

Notice that, in going from the new tree to the old one, you've deleted every vertex whose ID $x$ satisfies $j \< x \< i$. So, we need to subtract $i-j-1$ from $i$'s ID. But, also, we deleted $j-k$ vertices before vertex $j$, so we need to subtract that off, too. So, vertex $i$ becomes vertex $i-(i-j-1)-(j-k)=k+1$.

And, at this point, we realise we're wasting our time. Trying to update the vertex IDs intelligently has caused us to do a breadth-first search of the new tree, setting the ID of each vertex to be one more than the ID of the previous vertex in the subtree. In other words, you can forget about trying to do anything smart and just renumber the vertices of the subtree in the obvious way.
> 0 votes

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


# Question
Title: What all can be said when you say that the CPU is 32 bit?
When someone tells a computer scientist that a CPU is, say, 32 bits, what all does he/she infer from this information?

I know that it means that the physical address has 32 bits. This meas that the physical memory can't hold more that 2^32 bytes of RAM. This also means that the word size is 32 bit or 4 bytes. Please correct me if I am wrong and also tell me what more we can infer from this.

I have searched over the internet only to get websites answering the above question to layman. Can anyone answer it from the technical point of view?

# Answer
> 4 votes
An $n$-bit processor is a processor for which the preferred integer size is $n$ bits. That's usually the size of the integer or general purpose registers (a processor may not have exposed registers in its ISA, a processor may have some other kind of registers of different width, a processor may provide instructions to do some integer operations on different -- smaller or wider -- width, the width of buses used in the ISA implementation do not define its architectural width: there may be several implementations using buses of several sizes).

Data of that size is usually called a *word*, but when an ISA exist as a family and is extended to provide wider registers, the term *word* tend to continue to refer to data of the width adequate for the first member of the family (thus the continued use of word to refer to 16-bit quantities in the x86 world which has grow now to a 64-bit ISA).

The address space size is determined by the ISA width only if the ISA is using the same registers for address computation as for integer one. That's a very common property of later architectures, but it has not always be the case (the 8086 used 24-bit addresses but its word size was 16 bits, Cray had 64-bit data register but its address registers were 24 bits IIRC). Even when the registers used are the same, the amount of addressable memory may be different, either because some bits are not used for addresses (the 68000 for instance, and programmers making use of that caused issues for their followers when all of the bits were token into consideration), or because virtual memory allows for a process $n$-bit addressable space to be mapped into a wider physical address space (you could consider the 24-bit address of the 8086 a special case of that).

---
Tags: computer-architecture
---


title: N-queens problem objective function

text:
# Question
Title: N-queens problem objective function
I have read about the N-queens problem and I don't understand the following objective function:

$O(board)=N^2/2-L$

$N$ ... number of queens $L$ ... number of pairs of queens that attack each other

Why they use $N^2/2$? They wrote that it is the number of pairs of queens but I don't understand that can someone maybe explain it to me maybe with visualization

# Answer
The objective function you describe satisfies two properties:

1. It is maximized at a solution.
2. It is non-negative.

One can think of many other functions satisfying these two properties, for example $\binom{N}{2} - L + C$ for every $C \geq 0$. The exact choice is not so important – indeed, they chose $N^2/2$ whereas they could have chosen $\binom{N}{2} = N(N-1)/2$.
> 1 votes

---
Tags: optimization, board-games
---


# Question
Title: Problems conjectured but not proven to be easy
We have many problems, like factorization, that are strongly conjectured, but not proven, to be outside P. Are there any questions with the opposite property, namely, that they are strongly conjectured but not proven to be *inside* P?

# Answer
> 23 votes
Two decades ago, one of the plausible answers would be primality testing: there were algorithms that ran in randomized polynomial time, and algorithms that ran in deterministic polynomial time under a plausible number-theoretic conjecture, but no known deterministic polynomial-time algorithms. In 2002, that changed with a breakthrough result by Agrawal, Kayal, and Saxena that primality testing is in P. So, we can no longer use that example.

I would put polynomial identity testing as an example of a problem that has a good chance of being in P, but where no one has been able to prove it. We know of randomized polynomial-time algorithms for polynomial identity testing, but no deterministic algorithms. However, there are plausible reasons to believe that the randomized algorithms can be derandomized.

For instance, in cryptography it is strongly believed that highly secure pseudorandom generators exist (e.g., AES-CTR is one reasonable candidate). And if that is true, then polynomial identity testing should be in P. (For instance, use a fixed seed, apply the pseudorandom generator, and use its output in lieu of random bits; it would take a tremendous conspiracy for this to fail.) This can be made formal using the random oracle model; if we have hash functions that can be suitably modelled by the random oracle model, then it follows that there is a deterministic polynomial-time algorithm for polynomial identity testing.

For more elaboration of this argument, see also my answer on a related subject and my comments on a related question.

# Answer
> 12 votes
It's a tough question, because there isn't a consensus. There are still people who conjecture that $P=NP$.

But in my mind, the most notable problem with a significant conjecture that it's in $P$ is Graph Isomorphism

But, again, nobody really knows.

In general, the "conjecture that it's in $P$ " is going to be rare. We only conjecture that a problem is in $P$ if we have no polynomial time algorithm for it already. But, not being able to find a $P$ algorithm for it, after all these years, is probably going to be seen more as "evidence" that the problem is hard, not easy.

# Answer
> 4 votes
Although I'm not even close to be an expert in the field, I'd suppose that the unknotting problem is believed to be in P. It is known to be in $\sf NP\cap coNP$, and there are subexponential algorithms for it. More specifically, there is an algorithm which works $e^{O(\sqrt{n})}$, where $n$ is the number of crossings, see here. Note that another answer also indicates belief in the unknotting problem lying in $\sf P$.

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


# Question
Title: Least squares fit of a 1D lattice of points to a 2D dataset
Given a set of data points (shown in red), it is possible to fit a line $y = mx + c$ through the points using linear least squares regression.

I would like to modify this to fit a 1D lattice (grid) along the line such that $d$ is the offset of the the grid along the line and $i$ is the interval between neighboring grid points along the line.

An additional constraint is that more or less the same number of data points should be in the neighbourhood for each grid point in order to prevent picking an arbitrarily small $i$ and overfitting the data.

I believe that calculating the mean square error on a solution can be simple. The squared distances of all of the data points in the neighbourhood of the grid point would be:

$$mse = \sum\_{j = 0}^{g} \sum\_{k = 0}^{h} distance^2(\vec{latticePoint\_j}, \vec{dataPoint\_{j,k}})$$

(Where $g$ is the number of clusters and $h$ is the number of points inside the grid point's neighborhood.)

However, I'm not sure how to go about solving for all four variables $m$, $c$, $d$ and $i$ since I'm left with a discrete function. My hope is that since $i$ is fixed and points are distributed reasonably evenly among the clusters this could be done without invoking an overly complicated clustering algorithm.

The number of clusters are not known ahead of time and may contain outliers. Any help is much appreciated.

# Answer
> 2 votes
Define an objective function $\Psi(m,c,d,i)$ that specifies how "bad" a particular choice of values for $m,c,d,i$ are. Then, use any standard black-box optimization algorithm (e.g., gradient descent) to find $m,c,d,i$ that minimize the objective function. You might choose the initial values of $m,c$ based on a least-squares fit, and choose the initial values $d,i$ based on a best guess (maybe by projecting the points to the line $y=mx+c$ and then taking a FFT and looking for peaks, to try to find the periodicity), and then run gradient descent from there.

So, it all reduces to choosing an objective function $\Psi(m,c,d,i)$ that captures what you want. We can't give that for you, since you haven't fully specified the problem. For instance, you say you want "more or less the same number of data points" in each cluster, but you haven't specified how to trade off the errors: of course, we can't achieve this exactly, so we need some way to measure and compare different candidate solutions.

For instance, given a set $P$ of points, you might use an objective function like

$$\Psi(m,c,d,i) = \sum\_{p \in P} d\_{m,c,d,i}(p)^2$$

where $d\_{m,c,d,i}(p)$ is the distance from $p$ to the nearest grid point on the line $y=mx+c$, i.e.,

$$d\_{m,c,d,i}(p) = \min\\{\sqrt{(p\_x-x)^2 +(p\_y-(mx+c))^2} : x=d + ij, j \in \mathbb{Z}\\}$$

where $p=(p\_x,p\_y)$ in $(x,y)$-coordinates.

This doesn't do anything special about outliers; they incur a very large penalty. That might be undesirable -- it might lead to poor results in the presence of outliers. There are various methods for dealing with outliers. One simple one is to fit a line using a robust least-squares fit, find outliers and remove them as part of a pre-processing step, and then run the procedure on the result.

Also, you mention fear of overfitting the data set. Another way to avoid overfitting is to add a regularization term that penalizes values of $d,i$ that are considered a priori unlikely. For instance, you might add a penalty term that is proportional to $1/i$ or to $-i$. The penalty term gets added to the objective function. Then, when you minimize the objective function, this will exert some pressure to avoid choosing small values of $i$.

---
Tags: optimization, statistics, clustering
---


# Question
Title: How to verify a property about a certain order of events in TCTL / UPPAAL?
I'd like to check if a certain order of events happens if another property holds true using UPPAAL and TCTL.

`If A==true then eventually (B==true and eventually (C==true and eventually (D==true)))`

But since "In contrast to TCTL, Uppaal does not allow nesting of path formulae." I'm not sure how to do this.

What I'v got so far is only something like:

E$\diamond$ (A && B)

E$\diamond$ (A && C)

E$\diamond$ (A && D)

# Answer
> 2 votes
Under the assumption that your property can be interpreted in an intuitive way, as it is written, it seems that you can formulate it both in LTL, as:

```
a => F(b && F(c && F d))

```

and in CTL, which in the given example is equivalent to TCTL, due to lack of timing constraints (you may assume they are of form \[0, inf) and consider a TCTL formula as a CTL formula), as:

```
a => AF(b && AF(c && AF d))

```

but not in the logic supported in UPPAAL. Your property requires nested quantifiers, which are not supported in UPPAAL (as you suggested).

In general, it is not possible to model properties like `a => F b` ("whenever a is true, b should be true eventually") directly in UPPAAL. A workaround that might work is to consider all states in which `a` holds as the initial states and then formulate and check `AF b`. Of course, since you have multiple of such nested formulas, this does not seem possible in your case. Note that such properties require that for all reachable states X where a is true, there should be a state y (reachable from X), such that b is true in y (which does not fall into category of supported classes of properties in UPPAAL such as "liveness" and "safety").

Since you are trying to express a property that requires a nested CTL formula, UPPAAL is not suitable to formulate and model-check it. You should try SPIN or other tools that support full CTL.

---
Tags: formal-methods, model-checking, computation-tree-logic
---


title: Positive Definiteness Constraint

text:
# Question
Title: Positive Definiteness Constraint
I want to add a constraint to a convex program, to guarantee some matrix $A$ to be positive semidefinite. How should I do it?

The library I am working with can cope with linear/ quadratic inequalities only.

By definition, $A$ is positive semidefinite iff $\forall x \in \mathbb C^n : x^T A x \geq 0$, but this is a set of inifinitely many constraints. So, my question is: how can I formulate it using a finitely many set of contraints and using linear/ quadratic inequalities only.

Thanks in advance!

# Answer
A matrix $A$ is positive semidefinite if and only if there exists a matrix $V$ such that $$A = V^\top V.$$ So, you can use the entries of $V$ as your unknowns, and express each entry of $A$ as a quadratic function of the unknowns. Whenever you want to use $A$, instead rewrite that equation in terms of the entries of $V$.
> 5 votes

---
Tags: optimization, linear-algebra
---


# Question
Title: Visual programming tools, why don’t they work with the AST directly?
I've found several open source visual programing tools like Blockly and friends, and other projects hosted at Github, but could't find any that work directly with the abstract syntax tree.

**Why is that?**

I'm asking because once I discovered that every compiler out there has a phase in the compilation process where it parses the source code to an AST, it was obvious to me that some visual programing tools could take advantage of this to give the programer ways to edit the AST directly in a visual way, and also to do the round trip from source to node-graph and then back again to source when needed.

For instance one could think that from the JavaScript AST Visualizer to an actual JavaSript visual programming tool there isn’t too much of a difference.

**So, what am I missing?**

# Answer
Many of these tools **do** work directly with the abstract syntax tree (or rather, a direct one-to-one visualisation of it). That includes Blockly, which you've seen, and the other block-based languages and editors like it (Scratch, Pencil Code/Droplet, Snap!, GP, Tiled Grace, and so on).

Those systems don't show a traditional vertex-and-edge graph representation, for reasons explained elsewhere (space, and also interaction difficulty), but they are directly representing a tree. One node, or block, is a child of another if it is directly, physically inside the parent.

---

I built one of these systems (Tiled Grace, paper, paper). I can assure you, it is very much working with the AST directly: what you see on the screen is an exact representation of the syntax tree, as nested DOM elements (so, a tree!).

This is the AST of some code. The root is a method call node "for ... do". That node has some children, starting with "\_ .. \_", which itself has two children, a "1" node and a "10" node. What comes up on screen is exactly what the compiler backend spits out in the middle of the process - that's fundamentally how the system works.

If you like, you can think of it as a standard tree layout with the edges pointing out of the screen towards you (and occluded by the block in front of them), but nesting is as valid a way of showing a tree as a vertex diagram.

It will also "do the round trip from source to node-graph and then back again to source when needed". In fact, you can see that happen when you click "Code View" at the bottom. If you modify the text, it'll be re-parsed and the resulting tree rendered for you to edit again, and if you modify the blocks, the same thing happens with the source.

---

Pencil Code does essentially the same thing with, at this point, a better interface. The blocks it uses are a graphical view of the CoffeeScript AST. So do the other block- or tile-based systems, by and large, although some of them don't make the nesting aspect quite as clear in the visual representation, and many don't have an actual textual language behind them so the "syntax tree" can be a bit illusive, but the principle is there.

---

What you're missing, then, is that these systems really *are* working directly with the abstract syntax tree. What you see and manipulate is a space-efficient rendering of a tree, in many cases literally the AST a compiler or parser produces.
> 28 votes

# Answer
At least two reasons:

1. Because source code is a *much* more concise representation. Laying out an AST as a graph would take up a lot more visual real estate.

Programmers prize having as much context as possible -- i.e., having as much code present all at once on the screen at the same time. Context helps them better manage complexity. (That's one reason why many programmers use these crazy small fonts and enormous 30" screens.)

If we tried to display the AST as a graph or tree, then the amount of code that you could fit on a single screen would be much less than when it is represented as source code. That's a huge loss for developer productivity.
2. AST's are intended for compiler programming, not for easy understanding by programmers. If you took an existing AST representation and displayed it visually, it probably would be harder for developers to understand, because ASTs weren't designed to be easy for developers to learn.

In contrast, source code usually *is* designed to be readable/understandable by developers; that is normally a critical design criteria for source code, but not for ASTs. ASTs only need to be understood by the compiler writers, not by everyday developers.

And, in any case, the AST language would be a second language developers have to learn, in addition to the source language. Not a win.

See also https://softwareengineering.stackexchange.com/q/119463/34181 for some additional potential reasons.
> 6 votes

# Answer
The typical AST by compilers is rather complex and verbose. The directed graph representation would quickly become quite hard to follow. But there are two large areas of CS where ASTs are used.

1. Lisp languages are actually written as AST. The program source code is written as lists and directly used by the compiler and/or interpreter (depending upon which variant is being used).
2. Modelling languages, e.g. UML, and many visual domain specific languages use graphical notations which are effectives abstract syntax graphs (ASG) at a higher level of abstraction than the typical general purpose language AST.
> 3 votes

---
Tags: programming-languages, language-design, syntax-trees
---


title: MLTT not being Turing Complete

text:
# Question
Title: MLTT not being Turing Complete
Where can I find a proof that Martin-Löf Type Theory isn't Turing Complete, if such proof exists?

# Answer
It is a general feature of reasonable total programming languages that they do not have self-interpreters, but interpreters for reasonable programming languages are Turing-computable. So, a concrete example of a total computable function which is not definable in a total programming language is an interpreter for that programming language.

See Definition 2.1, Theorem 2.2, and Corollary 2.3 of this note. It proves that a self-interpreter for Gödel's T is not definable in Gödel's T. You can use the exact same proof for MLTT.

It is generally well known that a confluent terminating normalization system such as that of MLTT leads to a Turing-computable normalization procedure.
> 6 votes

# Answer
Section 4 of P. Martin-Löf's An Intuitionistic Theory of Types presents a normalisation proof of (a variant of) MLTT.

More (related) proofs can be found in the following papers.

A problem with normalisation of MLTT is that there are many variants of MLTT, and even small changes in the definition of what MLTT is might have substantial effect on normalisation.
> 0 votes

---
Tags: type-theory
---


# Question
Title: How to get this upper bound on worst-case heaps?
I've seen answers on the subjects, however I still don't get such answers. In the Cormen book (Introduction to algorithms) it is explained that the worst case for a $Max-Heapify$ call happens when the last level is "half full", in this case the worst case cost is modeled by the inequality:

$$ T\left(n\right) \leq T\left( \frac{2n}{3} \right) + \Theta(1) $$

I understand the equality (i.e. what it is modeling) but I don't understand how the worst case is built, I've tried to imagine an heap where the left subtree of the root is full up to level $h$ while the right one has (for example) just one node at level $h$, and with this example I can't see why the worst case modeling doesn't work, why such case would not represent an instance of the worst case?

The second question is that I don't understand why the number of nodes at height $h$ are at most $\lceil \frac{n}{2^{h+1}} \rceil$. There are proofs but I can't understand the motivation.

Update:

Trying to explain in more detail what I don't understand. As far as I know/remember for given $n$ that somehow measures how large is the input of an algorithm the worst case analysis is "*choose among all the possible instances of size $n$ the one that would give you the worst case execution cost*"

Following this direction, to me is not particular clear how for given $n$ we can be sure that the left subtree has $\frac{2n}{3}$ nodes, it is ok when the value $n$ is such that the distribution of nodes is such that half of the last level is full, while the other one is empty. In the proof for cost bounding I would differently.

I would distinguish two cases :

1. The tree has height $h$ and is complete, i.e. the total number of nodes is $2^{h+1} - 1$, I would also explain that it is possible to build in such case an heap such that starting from the root key it is possible to push down such key until it reach a leaf, how much is the cost in such case? it is exactly $h = ln\_2(n+1) - 1 = O(ln \\;n)$.
2. The tree has height $h$ but it is not complete, given the heap structure the left-most leaf is at height $h$. As done in point 1 I would explain it is possible to build a tree such that the root would be pushed down always in the left branch. How much is the cost in this case? Given that $n \> 2^{h} - 1$ we have that $h \< ln\_2(n+1) = O(ln(n))$.

I don't think is difficult to build a particular example for both 1. and 2. I also don't really see the point of "completing a tree" for computing the worst case cost, I can understand this operation can make the analysis easier, but for what I know about worst case analysis (assuming it is correct) it doesn't sounds correct to me.

# Answer
> 1 votes
In Heap sort we use a data structure which is a binary tree, and it is nearly complete. So, height is bounded by where n is the no. of nodes. In comparison to root, height of left and right subtree can differ by 1 at max.

Now, Imagine a tree `T`, and also assume `left subtree` height = `h+1` and `right subtree` height = `h`

What is worst case in `max_heapify()` ? Worst case is when , we end up doing more comparision and swaps while trying to gain heap property.

If the recursive `max_heapify` algorithm runs and it recursively goes to the longest path, then we can say : a possible worst case.

Well, all the longest paths are in the `left sub-tree` (because height is `h+1` ).

So, to get more longest paths we need to have make `left subtree` completely full. Since left subtree is of height h+1 , it will have leaf nodes and longest paths from root. This is the maximum possible number of longest paths ( of `h+1` height ) in T, such that while `max_heapify()` is running in a recursive way, it may traverse to the bottom of the `left subtree`. And we maximize such longest paths by considering left subtree as FULL to make the possibility of deep traversing more frequent in `max_heapify()` `function`.

Below is tree structure in worst case situation :

From the above figure assume yellow and red portions has `x` nodes each. Red portion is total `right subtree` and yellow portion is excluding the last level of `left subtree`. Both red and yellow sections now have height `h`.

How many nodes we have to add ( or attach or pad ) in the bottom layer of yellow portion to make the `left subtree` completely full as well as of height `h+1` ?

Well, bottom layer of yellow portion has nodes and we now add `2 children` to each of these nodes, =\> total x ( ) nodes have been added. Why adding, just to make `left subtree` of height `h+1` and full to meet worst case criteria.

OK !! DONE !! .. now , count how many nodes overall...

total =

And left subtree contains `2x` nodes = `2n/3` nodes.

So, for worst case one of the subtree should have `2n/3` nodes.

More in the following links : https://stackoverflow.com/questions/9099110/worst-case-in-max-heapify-how-do-you-get-2n-3

https://math.stackexchange.com/questions/181022/worst-case-analysis-of-max-heapify-procedure

---
Tags: algorithm-analysis, data-structures, heaps
---


# Question
Title: Why does many to one reduction imply Turing reducibility?
So, $ A\leqslant\_mB $ (many to one reduction) means that language $A$ can be reduced to language $B$ if there exists a Turing-calculable function $f$ so $ f(A) \subseteq B$ and $ f(\overline{A}) \subseteq \overline{B} $.

$ A\leqslant\_TB $ (Turing reducibility) means that language $A$ can be Turing-reduced to language $B$ if there exists an oracle machine $O^B$ which decides $A$.

I sort of get them both individually, but I don't get why $ \leqslant\_m $ implies $ \leqslant\_T $.

# Answer
> 17 votes
To put it informally, $A\leq\_{\mathrm{T}}B$ means "If I had a subroutine for $B$, then I could solve $A$", whereas $A\leq\_{\mathrm{m}}B$ means, "If I had a subroutine for $B$, then I could solve $A$ using a program that calls the subroutine only once and, furthermore, just returns the answer of the subroutine without doing any further calculation."

If you can solve a problem using a subroutine such that blah blah blah, you can solve that problem using the subroutine.

---
Tags: computability, reductions
---


# Question
Title: Existence of interval arrangement satisfying constraints
Problem statement:

> Input:
>
> (a) A natural number $n$.
>
> (b) $m$ requirements on $I\_1,\ldots,I\_n$ of the form:
>
> 1. Segment $I\_i$ is entirely to the right of segment $I\_j$.
> 2. Segments $I\_i$ and $I\_j$ intersect.
>
> Output:
>
> Is it possible to find $n$ non-empty segments (on the real number line) which fulfill the $m$ requirements?

Here is my solution attempt.

I started by considering what happens when I have only requirements of type 1 (no particular reason, just easier to visualize). I created a directed graph with $V=\\{v\_1,v\_2,\ldots,v\_n\\}$ nodes, where each node represents a segment. I added an edge $e=(u,v)$ iff the segment $u$ is to the right of segment $v$ ($e$ represents a requirement of type 1). A solution exists if the graph is a DAG, which can be checked in linear time using DFS.

My problem is with edges of type 2. I understand that a solution exists iff there is no edge of type 2 between two nodes which have a path with edges of type 1 between them. I believe I found an $O((m+n)m)=O(mn+m^2)$ algorithm using BFS from every node $u$ for which an $e=(u,v)$ of type 2 exists. I run the BFS from the node $u$ and check if $v$ is discovered. If it is, no solution exists.

Is there a linear time algorithm for this?

# Answer
Construct a graph in which each vertex corresponds to an *endpoint* of an interval. Then add the following edges:

1. If $\ell\_i,r\_i$ are the endpoints of $I\_i$, then add the edge $\ell\_i \to r\_i$.
2. For a constraint $I\_i \< I\_j$, add the edge $r\_i \to \ell\_j$.
3. For a constraint $I\_i \cap I\_j \neq \emptyset$, add the edges $\ell\_i \to r\_j$ and $\ell\_j \to r\_i$.

Now check that there are no directed cycles. (This answer is inspired by an answer on stackexchange.)
> 4 votes

---
Tags: algorithms, graphs, graph-traversal
---


# Question
Title: Is there a faster algorithm for my graph problem?
I'm working on a tool that can analyze sizes of individual functions in a compiled binary. For each one it calculates how much space would be saved if the function was removed.

However, the current algorithm is quadratic in the number of functions and as such is quite slow. Is there a better one? The problem formulation follows.

---

Let $G=(V, E)$ be a directed graph with labeling $f\colon V\to\mathbb{N}$, and $R\subseteq V$ be a set of root vertices. Here, $V$ represents the functions in the binary. The graph edges represent the dependencies between the functions: $(u, v)\in E$ iff $u$ references $v$, thus forcing $v$ to be present in the binary. $f$ assigns to each function its size in bytes. Functions in $R$ (the main function in the executable or the set of exported functions in an .so) are the functions we want in the binary, the rest of them were pulled in directly or indirectly from $R$.

For a set of vertices $U\subseteq V$ and edges $F\subseteq E$, we define $r(U, F)$ as the set of vertices reachable from $U$ along the edged from $F$.

$$r(U, F)=\\{v\in V\mid \exists r\in U. (r, v)\in F^\*\\}$$

We guarantee that $r(R, E)=V$, that is all vertices are reachable from $R$ in the original graph (not that it helps).

We define $s(U) = \sum\_{u\in U} f(u)$ as the total size of all functions from $U$.

For each $u\in V$, let $E\_u\subseteq E$ be the restriction of $E$ in which all edges adjacent to $u$ are removed. Then $r(R\setminus\\{u\\}, E\_u)$ is the set of functions that will be present in the binary if we remove $u$. Note that other functions besides $u$ may disappear as they will no longer be reachable from $R$.

Our goal is to compute for each $u\in V$ the size of the binary after removing $u$, i.e. to compute $g\colon V\rightarrow\mathbb{N}$ at all points, where

$$g(u)=s(r(R\setminus\\{u\\}, E\_u))$$

I can easily compute $g(u)$ in $O(|V|+|E|)$ with a simple depth-first-search. Computing the entire $g$ thus yields $O(|V|(|V| + |E|))$. Is there a faster algorithm?

# Answer
In practice, just as you can calculate g (u) for one particular u quite quickly, you can calculate g (u) for all $u \in V$ in parallel, operating with bit vectors of $|V|$ bits instead of boolean values - this changes the number of operations only be a constant, but by a rather large constant. This is quite useful if you actually want the number of bytes saved for *every* u.

If you are only interested in *one* u, then you only want to know for each function: 1. Can it be reached from u? 2. Can it be reached from any function other than u? To decide that, just combine all the other functions in V into one single function which calls everything that any of these functions calls. You don't need to know all the individual call graphs, just what can be reached from *any* of the functions in V other than u.

Second comment: I thought that you wanted to know how many bytes are saved by removing *one* function. That took you O (|V| * (|V| + |U|) by calculating all g (u). Which looks quite bad and can be improved if you want to know the answer for *one* function. If you want to answer the question for *all* functions, then calculating all g (u) is fine. It still takes O (|V| * (|V| + |U|), but the work can be reused for *every* function.

That's a very common situation, where solving n problems can be done a lot quicker than n times solving one problem.
> 1 votes

# Answer
For $v\in V$, define the set of necessary vertices for $v$ as

$$N(v)=\\{v' \in V : \text{for any path } u\_0,\dots, u\_n \text{ so that } u\_0 \in R\text{ and } u\_n = v, \text{ there is an } i \text{ so that }u\_i = v'\\}$$

The idea here is that $v'\in N(v)$ iff any path from $R$ to $v$ goes through $v'$ iff removing $v'$ makes $v$ unreachable.

---

Assuming you have computed $N(v)$ for all $v$, then $$ g(v)=\sum\_{v'\in V}f(v')-\sum\_{\substack{v'\in V\\v\not\in N(v')}}f(v')=\sum\_{\substack{v'\in V\\v\in N(v')}}f(v')$$

```
For each v
  g[v] := 0
For each v'
  For each v in N(v')
    g[v] += f(v')

```

Computing $g$ therefore costs $O(|V|^2)$ at most (but if you look closer, it's $\displaystyle O\left(\sum\_{v'\in V}|N(v')|\right)$ which should often be way smaller).

---

Let's first try to compute $N$ in acyclic graphs:

I'll call $\operatorname{Pred}(v')$ the set of predecessors of $v'$ : $\operatorname{Pred}(v'):=\\{v\in V : v \to v'\\}$.

Then, I believe that $$N(v')=\\{v'\\}\cup \left(\bigcap\_{v\in \operatorname{Pred}(v')}N(v')\right)$$

```
For v' in V in topological order
  sets = map((x -> N(x)), pred(v'))
  smallest_set, remaining_sets := smallest_set(sets)
  S := smallest_set
  for set in remaining_sets
    for v in S
      if v not in set
      remove v from S
  add v' to S
  N(v') := S

```

The cost is $O(|V|+|E|)$ for the topological sort, $O(|V|^2)$ to find the smallest set and then $O(|V|^3\log |V|)$ to compute the intersection (but it's also $\displaystyle O(\sum\_{v'\in V}d^-(v')k\_{v'}\log K\_{v'})$ with $k\_{v'}$ the size of the smallest necessary set of the predecessors of $v'$ and $K\_{v'}$ the size of the biggest, and $d^-(v')=|\operatorname{Pred}(v')|$, and overall this shouldn't be too big because many predecessors implies many sets to intersect which implies small sets). You can therefore compute $N$ in $O(|V|^3\log |V|)$.

---

Then, for general graphs, I'm not sure how to proceed. I'm trying to see if computing it as a fixpoint can work. Maybe using the quotient graph could also work.
> 0 votes

---
Tags: algorithms, graphs, optimization, efficiency
---


title: Finding all faces in a wireframe mesh

text:
# Question
Title: Finding all faces in a wireframe mesh
I'm trying to find an algorithm for finding all faces in a wireframe mesh. Wireframe means only the vertices and edges are given as input. There is no restriction on the number of edges a resulting face can have and the face can be convex or concave.

# Simple Example

In a wireframe of a square-based Pyramid there are 5 faces - the base is a square and the sides are triangles.

The algorithm should produce 5 sets of edges (since there are 5 faces). One set of edges would contain the 4 edges that make up the square base and then 4 sets of 3 edges for each side of the pyramid.

# Bonus

It would be a **bonus** if the algorithm can create an edge winding resulting in all faces pointing inwards or outwards.

# Answer
> 3 votes
After conducting more research I did find a solution, but first I will examine solutions suggested by posters and considered by myself and review why they didn't work.

```
This problem reduces to finding all chordless cycles in a planar graph.

```

This was one of my first thoughts early on, but this doesn't work when you consider the following:

```
      5-------f-------6
     /               /|
    /               / |
   e               g  |
  /               /   h
 /               /    |
1-------a-------2     7
|               |    /
|               |   /
d               b  i
|               | /
|               |/
4-------c-------3

```

Given three sides, the answers should be: **1 2 3 4 1**, **1 5 6 2 1**, and **2 6 7 3 2**. Unfortunately, **1 4 3 7 6 5 1** is considered chordless and is not a correct answer.

```
If you have vertices and edges - connect them. Adjacent edges will constitute a face.

```

Unfortunately, without weighting or accounting for spatial information you'll end up running into the edge cases described below.

# Edge Cases

The highlighted "face" in the following two examples should not be in the solution. These highlighted faces are referred to as "internal faces" (yes, even the highlighted face on the right is considered an internal face in graphics terminology).

Then there are other issues like objects with distinct subgraphs, holes, and ambiguous face loops.

# The Solution

While researching I found the paper: A new algorithm for finding faces in wireframes by Peter A. C. Varley and Pedro P. Company (full text here). The algorithm attempts to solve the problem for both 2D and 3D input. The solution is non-trivial: the setup alone is polynomial time.

## Basic Description

Start by creating a set of directed edges from all edges of the graph (so the initial set is of size 2e were *e* is the number of edges). These sets of directed edges are stored as the vertices that comprise them and are referred to by the paper as "strings". Each string must be given a priority according to the geometry around it (e.g. there will be a different priority assigned depending upon if it touches a triangle or quadrilateral).

You then exhaustively attempt to merge the strings by finding ones that start were another one ends. You do this by picking the highest priority strings first.

When merging strings you remove the original strings from the set and add the merged version back in. When the merge is preformed a new priority must be calculated using the existing priorities and spatial information about the strings themselves (the spatial calculation differs depending upon if your running the algorithm against 2D or 3D input).

Strings are removed from the set if their first and last vertex match (that means a loop was found). You continue repeating the algorithm until the set is empty.

# Complete Algorithm

Here is the complete algorithm copied directly from the paper. Hopefully the description I gave above helps a bit. The paper is very well written and its a good read for anyone interested in the topic.

Some steps in the algorithm come down to guesswork and assumptions about the input. For example, step #3 says to "choose a trihedral vertex", but if there is no trihedral vertices (e.g. octahedron or icosahedron) then the paper suggests breaking the symmetry by assuming that an arbitrary triangular loop of edges is a face.

```
(Top level of algorithm)
Create initial master string list, two entries per edge
Assign priorities to all strings in the list
Choose a trihedral vertex, and concatenate two strings at this vertex
While there are strings remaining in the master list
Examine the master list for the presence of forced concatenations
    If there are forced concatenations, perform them
    Otherwise, examine the master list for the presence of voluntary mergers
    If there are voluntary mergers, perform them
    Otherwise, examine hypotheses (see subroutine below)
(Subroutine: Examine Hypotheses)
Take a working copy of the master string list
Repeat
Take the highest-priority string S in the working string list
Find the string T which has the best mating value with S
Concatenate S and T, and reduce the priority of the resulting string
Repeat
Examine the working string list for the presence of a forced concatenation
If there is a forced concatenation, perform it
    If the forced concatenation created a new face, update the master list accordingly and exit this subroutine
If there is no forced concatenation
    If there is a voluntary merger available, create the face, update the master list accordingly and exit this subroutine
    Otherwise exit this inner loop

```

# Other Solutions

According to the paper, the current face-finding algorithms generally fall into four categories: exhaustive search approaches, pseudo-random approaches, shortest-path approaches, and heavily mathematical approaches. It does a good job citing other possible solutions along with their advantages and disadvantages.

Keep in mind that this algorithm acknowledges that it still produces incorrect output for certain input. However, this is still an improvement over the previous best solution which fails for even more input.

---
Tags: algorithms, graphs, enumeration, graphics, polygons
---


# Question
Title: K shortest paths - any relation between K and % of graph nodes in discovered paths?
Let's say I have a graph with $N$ nodes, $A$ arcs and an average branching factor $b$. I want to find the $K$ shortest paths between two nodes.

Is there some relation (even approximate is fine) that expresses the dependency between the parameter $K$ and percentage of nodes included in the paths discovered by running the algorithm (Yen's loopless KSP)?

For example, in a graph of 20 nodes, the ($1st$) shortest path from node $1$ to $12$ is $1-4-7-12$, while the $2nd$ shortest path is $1-4-6-9-12$.

So for $K=1$, the discovered path contains $4/20 = 20\\%$ of the nodes in the graph. For $K=2$, the two paths contain $6/20 = 30\\%$ of the nodes. This relation between $K$ and the percentage is what I'm looking for.

# Answer
It seems to me the relation depends purely on how the graph is made. Think about a cycle. The shortest path between two adjacent vertices contains 2 vertices while the second contains n vertices
> 1 votes

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


# Question
Title: Smallest set of features that would make relational algebra Turing complete
I'm thinking this should be just one or two things, since lambda calculus is so tiny and still Turing complete.

Probably just recursion (something like "MY\_QUERY(param) = select * from param UNION MY\_QUERY(DO\_SOMETHING\_WITH(param))"). But I don't see how I could define aggregate functions with this.

Any idea?

# Answer
You need just two things: new values and recursion/while.

New values means the ability to execute some external function that returns values that were not already to be found in the database. Obviously most implementations (including SQL) have that.

Recursion/while means the ability to execute a loop or iterative computation that may not terminate. The CTE RECURSIVE feature of SQL is one such.

SQL with CTE RECURSIVE is Turing Complete (without stored procedures).

See the Alice book http://webdam.inria.fr/Alice/ for a detailed treatment.
> 5 votes

---
Tags: computation-models, turing-completeness, relational-algebra
---


# Question
Title: Representing non-contiguous memory regions as a standard vector with O(1) access
What interesting alternatives are there for constructing an arbitrarily large static array from smaller scattered blocks of fixed-sized non-contiguous blocks of memory?

This is similar to the problem solved by hardware MMU pagetable mappings from virtual memory to physical memory, but in this particular case the scale is different, and it needs to be implemented in software, with virtual memory, and also in userland.

To clarify a bit, I'm using baker's treadmill as my GC, but it only supports fixed sized allocations (the current chunk size is 128 bytes, but I have some slight flexibility in re-defining it). The language I'm implementing requires arbitrary sized vectors with something close to O(1) access/write.

Currently I'm just building a pyramid of chunks, which gives something like log12(n) lookups, but the memory overhead sucks. Are there any interesting hashing solutions for mapping monotone index ranges to pointers?

What about run-time generation of a minimal perfect hash function? It seems they require at minimum 1.44 bits per key. If we bump the allocation block size to 512, we can support vectors with up to 1454080 elements, since we only need to map block numbers and not vector indices.

---

Edit:

See the paper "Z-rays: divide arrays and conquer speed and flexibility" (http://dl.acm.org/citation.cfm?id=1806596.1806649&coll=DL&dl=GUIDE) for more information regarding optimization of this array format:

These scattered blocks are sometimes called arraylets and are used by other GC algorithms: https://www.ibm.com/developerworks/websphere/techjournal/1108\_sciampacone/1108\_sciampacone.html

Also related: the Staccato GC: http://researcher.watson.ibm.com/researcher/files/us-groved/rc24504.pdf

# Answer
> 3 votes
A simple approach is to have a one-level lookup table that maps each block of the array to where it is stored. In other words, for a logical array $A\[0\dots n-1\]$ containing $n$ bytes, we have a lookup table $T\[0\dots \frac{n}{128}-1\]$ containing $n/128$ pointers; the bytes $A\[128k \dots 128k+127\]$ are stored at the physical address $T\[k\]$. To look up $A\[i\]$, we compute $p = T\[i \gg 7\]$ (where $\gg$ indicates logical right shift), then read the byte at address $p + (i \bmod 128)$.

This does require a single contiguous region large enough to store $n/128$ pointers (e.g., holding $n/32$ or $n/16$ bytes, depending on whether you're on a 32-bit or 64-bit system). Given that, array operations become fast: you basically have one extra table lookup and indirection.

If you can't even have *any* contiguous region, not even a smaller one for storing the lookup table, but have to build everything out of 128-byte chunks that can be at arbitrarily-inconvenient locations with arbitrarily-bad fragmentation, then I don't think it's possible to do any better than your solution.

Rather than looking for a better data structure to handle this kind of arbitrarily-bad fragmentation, a cleaner solution is probably to design your memory management system to avoid creating worst-case memory fragmentation in the first place. One architecture that can help deal with this is a buddy allocator. The entire memory address space can be divided into 128-bit chunks, but we then impose a binary tree structure on it: the 128-byte chunk at address $256k$ is the sibling/buddy of the 128-byte chunk at address $256k+128$. Those two chunks, if they're both available, can be coalesced into a (fused) 256-byte chunk. Each 256-byte chunk has a buddy, and if they're both available, they too can be merged to obtain a 512-byte chunk. And so on. This allows you flexibility to deal with small 128-byte chunks when you need them, but also provides a way to build up larger chunks of contiguous memory and try to avoid arbitrarily-bad fragmentation.

---
Tags: data-structures, arrays, virtual-memory
---


title: Treewidth of k x k square grid graphs

text:
# Question
Title: Treewidth of k x k square grid graphs
According to some slides I found on google, the treewidth of any $k \times k$ square grid graph $G$ is $tw(G) = k$. I just started researching about treewidth and tree decomposition, and for the most part it makes sense. However, I am particularly interested in the $k \times k$ square grid graph case, but have been struggling on how it is possible to make a tree decomposition of such a graph with that low of a width.

One of the problems I run into when trying to draw out decomposition trees of small square grids with groups of at most $k+1$ (to ensure a decomposition tree where the width is $k$) is that since the graph is "cyclic", one of the corner nodes shows up in two opposite ends of the tree, but not in any nodes on the path between the two. This clearly violates the coherence property of decomposition trees, which according to Wikipedia (which gives a more precise definition than most) is:

> If $X\_{i}$, $X\_{j}$, and $X\_{k}$ are nodes (in the decomposition tree), and $X\_{k}$ is on the path from $X\_{i}$ to $X\_{j}$, then $X\_{i}\cap X\_{j}\subseteq X\_{k}$.

For the case of the $3 \times 3$ graph, the only valid (or at least what I believe to be valid) decomposition tree I can think of contains 2 nodes: $\\{\\{1, 2, 3, 4, 6, 7, 8, 9\\}, \\{2, 4, 5, 6, 8\\}\\}$ where the nodes are labeled by row starting from the top left corner:

$1\space2\space3$

$4\space5\space6$

$7\space8\space9$

I did this by taking the perimeter vertices for the first tree node, and the inner vertex ($5$) along with its adjacent vertices to ensure all edges and vertices are included.

Ultimately, my question is, how can the treewidth of a square $k \times k$ square grid graph actually be equal to $k$? And if this is correct, could you present/explain a simple example of a decomposition tree that demonstrates this property?

# Answer
> 19 votes
The treewidth (and pathwidth) of the $k\times k$ grid is exactly $k$. (And, more generally, the treewidth and pathwidth of the $k\times\ell$ grid is exactly $\min\\,\\{k,\ell\\}$). For the example grid

$$\begin{matrix}1&-&2&-&3\\\|&&|&&|\\4&-&5&-&6\\\|&&|&&|\\7&-&8&-&9\end{matrix}$$

the bags of the tree decomposition are $\\{1,2,3,4\\}, \\{2,3,4,5\\}, \\{3,4,5,6\\}, ..., \\{6,7,8,9\\}$.

Note that the bag $\\{1,2,3,4\\}$ already contains all edges adjacent to $1$, so we don't need to include that vertex ever again. Similarly, $\\{2,3,4,5\\}$ contains all of the edges adjacent to $2$ that weren't already in the first bag.

---
Tags: graphs, planar-graphs, square-grid
---


title: Is Logical Min-Cut NP-Complete?

text:
# Question
Title: Is Logical Min-Cut NP-Complete?
### Logical Min Cut (LMC) problem definition

Suppose that $G = (V, E)$ is an unweighted digraph, $s$ and $t$ are two vertices of $V$, and $t$ is reachable from $s$. The LMC Problem studies how we can make $t$ unreachable from $s$ by the removal of some edges of $G$ following the following constraints:

1. The number of the removed edges must be minimal.
2. We cannot remove every exit edge of any vertex of $G$ (i.e., no vertex with outgoing edges can have all its outgoing edges removed).

This second constraint is called logical removal. So we look for a *logical, minimal removal* of some edges of $G$ such that $t$ would be unreachable from $s$.

### Solution attempts

If we ignore the logical removal constraint of LMC problem, it will be the min-cut problem in the unweighted digraph $G$, so it will be solvable polynomially (max-flow min-cut theorem).

If we ignore the minimal removal constraint of the LMC problem, it will be again solvable polynomially in a DAG: find a vertex $k$ such that $k$ is reachable from $s$ and $t$ is not reachable from $k$. Then consider a path $p$ which is an arbitrary path from $s$ to $k$. Now consider the path $p$ as a subgraph of $G$: the answer will be every exit edge of the subgraph $p$. It is obvious that the vertex $k$ can be found by DFS in $G$ in polynomial time. Unfortunately this algorithm doesn't work in general for an arbitrary directed graph.

I tried to solve the LMC problem by a dynamic programming technique but the number of required states for solving the problem became exponential. Moreover, I tried to reduce some NP-Complete problems such as 3-SAT, max2Sat, max-cut, and clique to the LMC problem I didn't manage to find a reduction.

I personally think that the LMC problem is NP-Complete even if $G$ is a binary DAG (i.e., a DAG where no node has out-degree greater than 2).

### Questions

1. Is the LMC problem NP-Complete in an arbitrary digraph $G$? (main question)
2. Is the LMC problem NP-Complete in an arbitrary DAG $G$?
3. Is the LMC problem NP-Complete in an arbitrary binary DAG $G$?

# Answer
Let G = (V, E) be a weighted DAG, s and t be two vertices of G, and LSTMC = (G, s, t) be an instance of the logical s-t min-cut problem. It is obvious that the LSTMC problem is NP.Now, we should show that the LSTMC is NP-Hard. We reduce the hitting-set problem to the LSTMC problem. Let S = {s1, s2, ..., sn} be the given sets and {a1, a2, ..., am} be the union of all the sets. Given the number k1, the decision problem of the hitting set problem states whether there exists a set A with k1 elements such that every element of S (every set si s.t. i = 1..n) contains at least one element of A. We denote the hitting set problem as HS(S). We construct the weighted DAG G′ from the set S by Algorithm HS2LSTMC. This algorithm considers s as the source vertex of the DAG G′. For each set si of HS s.t. i = 1..n, the algorithm considers the corresponding vertex, si, and adds an edge with infinite weight from s to each si. Then, for each element aj of the union of the input sets s.t. j = 1..m, the algorithm considers the corresponding vertex, aj, and adds an edge with zero weight from each si to any aj s.t. aj ∈si in HS. Finally, the algorithm considers two final vertices called t and k, and add two edges from each aj s.t. j = 1..m to the both final vertices. It is clear that G′ can be made in polynomial time.

Now, we should demonstrate that HS(S) has an answer with k1 elements if and only if LSTMC = (G′, s, t) has an answer with some logically removed edges such that the sum of the weights of the removed edges is k1.

For simplicity, we perform this part of proof, by providing an example:

In the following figure, suppose that S = {s1, s2, s3} such that s1 = {1, 2, 3}, s2 = {1, 4}, and s3 = {2, 5}. Fig. 2 shows the weighted DAG G′ of the LSTMC problem corresponding to the hitting set problem HS(S). In this example, the set A, namely the union of all elements of S, is A = {1, 2, 3, 4, 5}. We have |S| = 3 and |A| = 5. This example shows how an arbitrary instance of the hitting set problem can be solved by the help of a specific instance of the logical s-t min-cut problem in a weighted DAG. If we compute an answer to LSTMC = (G′, s, t) and consider those removed edges of the answer which are in the form of (aj, t) called E1 (1 ≤ j ≤ m), then the tail set of E1 is an answer to HS(S). An answer to the LSTMC problem is the edge set E1 = {(s1, 2), (s1, 3), (s2, 4), (s3, 5), (1, t), (2, t)}. So, the tail set of the subset E2 = {(1, t), (2, t)} of the edge set E1, namely the set {1, 2}, is an answer to the HS(S).
> 1 votes

# Answer
Here's (an attempt at) a polynomial-time algorithm for LMC on arbitrary binary DAGs $G$.

This answers Question #3. (Sorry for the messy write-up ahead of time. :))

To begin, throw out "forever" any vertex not reachable from $s$. We don't care about these, since they're not part of any $s$-$t$ path.

Next, define sub-DAGs $A$ and $B$, initially empty. Then, for all vertices $v \in G-\\{s, t\\}$,

Test whether there is a path from $v$ to $t$. If so, add $v$ to $A$. If not, add $v$ to $B$.

Let the edges of $A$ and $B$ be those induced by the vertices within each set (for now, ignore any edges from $s$ to $A$, from $A$ to $t$, and from $A$ to $B$; also note there are no edges from $B$ to $t$ by construction).

Then, compute the transitive closure of $A$. Namely, we are interested in finding some set of vertices $\\{a^\*\\}$ that are the "leaves" of the sub-DAG $A$.

Fix any such $a^\*$. Observe that there must be a directed edge from $a^\*$ to $t$. This is because, by construction, (i) there is an $s$-$t$ path through $a^\*$, (ii) there are no paths from $a^\*$ through $B$, and (iii) since $A$ is itself a DAG and $a^\*$ is a leaf of $A$, there is no path from $a^\*$ through another vertex of $A$ to $t$.

Now, there must also be a directed edge from each vertex in $\\{a^\*\\}$ to some vertex in $B$, or some of the $\\{a^\*\\}$ have a single edge to $t$. In either case, we are allowed to delete any $a^\*\rightarrow t$ edge.

If $|\\{a^\*\\}|$ = 1, then either we must delete the edge from the unique $a^\*\rightarrow t$, or there is a vertex earlier in the $s$-$t$ path containing $a^\*$ that has two paths to $t$ -- one through $a^\*$ and one directly. In case that the latter might hold, we record $a^\*\rightarrow t$ and proceed "backwards greedily" (details on this below).

If $|\\{a^\*\\}|$ \> 1, then we must either delete all of the edges from $\\{a^\*\\}\rightarrow t$, or else there are some number of edges $k \< |\\{a^\*\\}|$ earlier in the transitive closure of $A$ that disconnect all paths from $s$ through the $\\{a^\*\\}$ to $t$.

This is where we use the fact that the graph $G$ is a binary DAG.

Consider the set of predecessors of $\\{a^\*\\}$. Since each of these vertices has out-degree at most two, there are exactly three cases:

**Case 1.** A predecessor has an out-edge to some vertex in $\\{a^\*\\}$ and an out-edge to some vertex in $B$.

In this case, it doesn't matter whether we delete the edge from the predecessor to the vertex in $\\{a^\*\\}$ or the edge from the vertex in $\\{a^\*\\}$ to $t$. Therefore, we can "skip past" this vertex (and check whether the backwards path merges with a path of another vertex in $\\{a^\*\\}$).

**Case 2.** A predecessor has an out-edge to a vertex in $\\{a^\*\\}$ and another predecessor of the $\\{a^\*\\}$.

In this case, we must either delete both edges from the $\\{a^\*\\}$ to $t$, or we can delete a single earlier edge in the path from $s$ to the predecessor that disconnects both paths.

**Case 3.** A predecessor has an out-edge to two vertices in $\\{a^\*\\}$.

This is identical to case 2. It doesn't matter whether we delete one of this predecessor's edges and the corresponding other edges from $\\{a^\*\\}$ to $t$, or both of the edges from the $\\{a^\*\\}$ to $t$. We just want to know whether we can disconnect the path from $s$ through this predecessor to $t$ with a single edge earlier in the path from $s$ to the predecessor.

Altogether, as we scan backwards through predecessors in the transitive closure of $A$, we can greedily keep track of the "best so far" choices. That is, at every step, we have an obvious choice that involves deleting some number of edges, but we want to wait to see whether a better option is available. Once a better option is found, we can "forget" about the previous option. Hence, a greedy choice at each layer of predecessors suffices (so long as we wait until the end to commit to any choice).

Therefore, with some basic memoization, the time and space complexities of this process appear to be at most $O(|E|)$. This leaves out the fact that, while we can locally/greedily identify when we have found a "cheaper choice," it's a priori unclear which previously-recorded edges to remove. Therefore, we record the order in which we check edges as we go. Upon finding a better option, we repeat the search up to this point in order to find which previously-recorded edges to remove. The total time complexity of this step is $O(|E|^2)$ and space complexity $O(|E|)$.

Altogether, the time complexity is $O(|V|\cdot(|V|+|E|))$ for initialization, plus $O(|V|^3)$ for the transitive closure, plus $O(|E|^2)$ for the search. The total time is $O(|V|^2+|E||V|+|V|^3+|E|^2) = {\bf O(|V|^3+|E|^2)}$.

Upon completing the process, we obtain the minimum set of edges required to disconnect $s$ from $t$ while preserving at least one out-edge of every vertex in the graph (or we discover that a solution is impossible along the way, and abort).
> 0 votes

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