# Question
Title: denotional semantic for while - fixed points
In my book it is written: $$\[\[\text{while b do S}\]\] = \text{FIX F}$$, where $Fg = cond (\beta\[\[b\]\], g\circ \[\[S\]\], id). $
What is cond ? $\[\[\text{if b then S1 else S2}\]\] = cond (\beta\[\[b\]\], \[\[S1\]\], \[\[S2\]\])$.

I don't understand why we should use $FIX$. What it is FIX ? For me it is sufficient:
$S\[\[\text{while b do S}\]\] = cond(\beta\[\[b\]\], \[\[\text{while b do S}\]\]\circ \[\[S\]\], id)$$

**DEFINITIONS**

$$S\_{ds}\[\[\text{while b do S}\]\] = FIX F$$ where $Fg= \text{cond}(\beta\[\[b\]\], g\circ S\_{ds}\[\[S\]\], id)$

$$FIX: ((State\rightarrow State)\rightarrow (State \rightarrow State)) \rightarrow (State \rightarrow State)$$
In brackets functions are partial.

# Answer
> 6 votes
Your proposed alternate definition is no good. It tries to define $\[\[\text{while b do S}\]\]$ in terms of $\[\[\text{while b do S}\]\]$. That's a circular definition: you can't define something in terms of itself.

"FIX" typically refers to the least fixpoint, and is a way of avoiding circularity. See your textbook for background on fixpoints and the precise definition of the "FIX" operator.

---
Tags: semantics, denotational-semantics
---


title: One-shot Private Randomness Extractor

text:
# Question
Title: One-shot Private Randomness Extractor
Suppose a pair of random variables $(X,Y)\in\mathcal{X}\times \mathcal{Y}$ with joint distribution $P\_{XY}$ is given. I am interested in a deterministic mapping $f:\mathcal{Y}\to \\{0, 1\\}^k,$ for some integer $k\>0$ such that $$f(Y)\perp X, \qquad \text{i.e.}, \quad f(Y)\text{ is independent of } X,$$ and $$H(f(Y))\>0.$$ The second condition is just to rule out the degenerate functions $f$.

For example if $X\sim\mathsf{Bernoulli}(p)$ and $P\_{Y|X}$ is an erasure channel\* with erasure probability $\delta\>0$, then $f:\\{0,\text{e},1\\}\to \\{0,1\\}$ where $\text{e}$ is the erasure, defined as
$$f(1)=f(0)=1,\qquad f(\text{e})=0,$$ satisfies the above condition.

What is a necessary and sufficient condition on $P\_{XY}$ for the existence of such deterministic map?

---

\*By erasure channel, I mean the following conditional distribution: $$P\_{Y|X}(y|x)=(1-\delta)1\_{\\{y=x\\}},$$ and $$P\_{Y|X}(\text{e}|x)=\delta, ~~~~\text{for}~~~~x=0,1.$$

# Answer
> 1 votes
If such a mapping $f$ exists at all, there always exists such a mapping with $k = 1$: you can always collapse a larger function in such a way that doesn't make the mapping constant. In other words, a mapping $f$ exists if there is some non-trivial event $E$ depending only on $Y$ which is independent of $X$. The converse is also true.

---
Tags: probability-theory, cryptography, information-theory, randomness, random-number-generator
---


# Question
Title: Disjoint paths of length at most L and the number of nodes to remove to vanish this property - Inequality
Given an graph $G$ and two, randomly chosen, non-adjacent nodes, let's call them $s$ and $t$, we make the following two notations:

$P\_L(s,t;G)$ = the maximum number of internally disjoint paths (paths that don't have any node in common, except s and t) with a length at most $L$ (L ranges from 1 to |G|).

$K\_L(s,t;G)$ = the minimum size of a set of nodes (s and t not included in the sets) with this property - if we remove the set of nodes, the result is that there are no more paths of length at most $L$, from $s$ to $t$.

I have to prove the inequality $$ P\_L(s,t;G) \le K\_L(s,t;G) $$ and specify the values of $L$ (L ranging from 2 to |G|) for which the relation satisfies the equality too, for any chosen graph G and nodes s,t.

The first idea that comes to my mind is to start a discussion based on the values of $L$ and try to prove the relation by induction. Any ideas how?

# Answer
Hint: Suppose that $P\_1,\ldots,P\_t$ are internally disjoint $(s,t)$-paths of length at most $L$. Show that you have to remove at least one vertex from each path to make the distance from $s$ to $t$ larger than $L$.

When $L = |G|$, the classical Menger's theorem states that equality holds.
> 2 votes

---
Tags: graphs
---


# Question
Title: Can the isomorphic graph problem be solved in deterministic polynomial time?
Here is a recent homework problem of mine:

> Call graphs G and H isomorphic if the nodes of G may be reordered so that it is identical to H. Let ISO = {⟨G,H⟩| G and H are isomorphic graphs}. Show that ISO ∈ NP.

In order to solve this problem, I created a non-deterministic Turing machine that did the following:

1. Check if each graph has the same number of nodes
2. Non-deterministically arrange the edges of G in a permutation that matches H
3. Verify that each edge in the permutation of G matches the corresponding edge in H

As far as I know, this approach is acceptable for solving this problem with non-determinism.

My question is this: if we can compare the edges in the permutation of G against H, why can't we simply check to see if each edge in the original list of edges in G (a maximum of $n^2$ nodes) has a matching edge in H (which also has a maximum of $n^2$ nodes) for a total big O of O($n^4$)? If this is possible, does that mean that this problem is in P?

# Answer
Your approach sounds intuitively appealing on first glance, but it doesn't work. It's not enough that each edge in $G$ has a matching edge in $H$, when taken one at a time. There has to be a way to provide a single matching (isomorphism) that matches every edge of $G$ to a (different) edge of $H$, in a way that preserves the connectivity.

Examples:

1. Suppose you discover that it is possible to match edge $(a,b)$ from $G$ with edge $(u,v)$ from $H$; and you also discover that it is possible to match edge $(c,d)$ from $G$ with $(u,v)$ from $H$. This doesn't mean there will necessarily be a way to stitch this into a complete isomorphism that describes how all vertices and edges are matched. For instance, trying to simultaneously match both $(a,b)$ and $(c,d)$ to the same edge $(u,v)$ does not correspond to any legal graph isomorphism (different vertices have to map to different vertices, and different edges to different edges).
2. Suppose you discover that it is possible to match edge $(a,b)$ from $G$ with edge $(u,v)$ from $H$; and you also discover that it is possible to match edge $(b,c)$ from $G$ with $(w,x)$ from $H$, where $v \ne w$. This doesn't mean there will necessarily be a way to stitch this into a complete isomorphism that describes how all vertices and edges are matched. For instance, trying to simultaneously match $(a,b)$ to $(u,v)$ and $(b,c)$ to $(w,x)$ doesn't work, since you need $b$ to be consistently matched to the same vertex in both (e.g., either to $v$ both times, or to $w$ both times).

For these reasons, your approach will indeed run in polynomial time but will not compute the correct result: there will be some graphs $G,H$ where your algorithm outputs "isomorphic" but where the correct answer is "not isomorphic".

---

If we try to fix this problem, the naive approach is to try to find all ways to match the set of $n$ vertices in $G$ to a re-ordering of the set of vertices in $H$ (i.e., a matching that simultaneously describes what every vertex in $G$ corresponds to, in $H$). However, there are $n!$ such candidates to try, and $n!$ is exponential in $n$, so this leads to an exponential-time algorithm. It's a famous open problem whether the graph isomorphism problem is in P or not. See https://en.wikipedia.org/wiki/Graph\_isomorphism.
> 4 votes

# Answer
The best algorithm for graph isomorphism, due to Babai, runs in time $e^{O(\log^C n)}$ for some constant $C \> 1$. We don't know any polynomial time algorithm for the problem.

Your algorithm, which you haven't quite specified (what are "matching edges"?), doesn't work. Since you haven't specified it, it is hard to explain why it doesn't work, but similar algorithms have been suggested, and have been proven not to work in polynomial time. The archetypal such algorithm identifies types of *vertices*, and then tries to match them against one another. The problem is that there are pairs on graphs in which all vertices have the same type, in which case you have to resort to checking all permutations.
> 3 votes

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


# Question
Title: Transforming training data for machine learning algorithms
If you want to make good predictions with machine learning (supervised learning in particular), you need a good training set. And relevant predictors in your feature set can be overshadowed by irrelevant training data. Validation can help you to figure out what training data is good - you can then remove irrelevant inputs. But what if "irrelevant" data contains something useful, but it just isn't obvious?

I have an exercise schedule, and you can predict what kind of exercise - if any - I'll have for a given day based on the day of the week and my location. The same predictability is true for my friend - and just about anyone who exercises regularly. If I throw my friend's position and day of the week data into my prediction algorithm, then I may over fit because a) day of the week would be repeated, and b) my friend's position is not linearly correlated to my schedule, so it could be mistaken for irrelevant noise. Simply dumping his training set into my training set without any thought is probably bad.

However, if my friend and I are in the same location for a given day, then we are very likely to exercise together, and I follow his schedule when we exercise together. It doesn't matter if my friend is across the city or across the world, his position only becomes strongly correlated when he is very close to me. So there is something "hidden" in my friend's seemingly irrelevant position data that might be missed.

The general problem is, given a set of predictors \begin{align} P= \\{{x\_1,x\_2,x\_3,...}\\} \end{align} for some data set \begin{align} P={\\{y\_i,x\_{1i},x\_{2i},x\_{3i},...\\}}\_{i=1}^n \end{align} we want to predict \begin{align} \\{ y\_i \\} \end{align} We can do this by using supervised machine learning techniques, and we can also try doing this by using linear regression: \begin{align} y\_i = a\_1 x\_{1i} + a\_2 x\_{2i} + a\_3 x\_{3i} + ... + e\_i \end{align} Now, consider the set of all subsets of P \begin{align} Let \space U = \\{ U\_j|\space U\_j \subseteq P \\} \end{align} And consider the set of nonlinear functions of all subsets of P that have nonzero correlation with y (this is messy notation but its just any function of any combination of predictors such that the function has nonzero correlation with whatever it is you are predicting). \begin{align} Let \space F = \\{\[\\{f\_{1j}(U\_j)\\},\\{f\_{2j}(U\_j)\\},\\{f\_{3j}(U\_j)\\},...\]|\space \\{corr(\\{f\_{kj}(U\_j)\\} \space with \space \\{y\_i\\})\\} \cap 0 = \varnothing \\} \end{align}

F is a massive set, and it contains the function for any given nonlinear machine learning technique. Furthermore, the "ultimate" nonlinear predictive function for any data set would be contained in F, and it may not be the conclusion of any machine learning technique. Clearly, the linear regression model and F share no elements by construction. However, they may share linear terms if linear term coefficients are ignored.

Every element of F can be broken up into a sum of linear and nonlinear terms (even if there are no linear terms). Now, assume that the "ultimate" nonlinear predictive function contains linear and nonlinear terms such that nonlinear terms can be approximated by low order polynomials and have nonzero correlation with y - and therefore are elements of F. I propose that the addition of these low order polynomials and linear terms can approximate the "ultimate" nonlinear predictive function reasonably well.

But that starts already knowing the "ultimate" function. Now, say we want to find this function and we keep the assumptions we made. Given a set of predictors, could we search through the set "F" by approximating low order polynomials, add these nonlinear functions to our set of predictors, then add and subtract elements to our set of predictors with an iterative technique that uses linear regression techniques to arrive at a good approximation for the "ultimate" predictive function? Are these assumptions reasonable for real world data sets? And, could this be a more general approach than machine learning techniques?

I have tried implementing code that attempts to achieve this, and I seem to be able to generate new predictor sets that yield better predictions when used in KNN compared to analogous KNN predictions from the original predictor sets. So far I have generally been able to boost KNN predictive accuracy by 3-4% for all k values of various distance measures and metrics so long as data sets have reasonable distribution. But I would like to hear some opinions about this idea, and if it is reasonable approach or mathematically sound at all.

I realize that when all possible functions in F are considered, this algorithm becomes huge and computationally very expensive. But I was thinking that maybe you should only check low order polynomials that are functions of reasonable numbers of features from your set of predictors, and only consider them for your model if they meet some performance conditions. Also, you probably don't need to double count functions optimized for the same set of inputs. So If you only considered low order polynomials of two features, you would only have to search through (n^2 - n)/2 instances, and low order polynomial optimization isn't too computationally expensive. So if you limit the number of features for the functions created in this algorithm, then it becomes much more realistic. But limiting the number of features for the functions could limit the algorithm's performance with more sophisticated data sets. There Is probably some optimal balance here.

# Answer
Ok, the notation could use a bit of work and is somewhat needlessly complex, but before I begin with my answer I want to make sure that I've understood your problem formulation correctly.

> Given labeled samples $(y\_i, x\_i)$ where $x\_i$ is some $n$-vector in your feature space, you wish to find the "best-fit" model over all plausible projections.

Now to answer your question. This will most certainly give you great in-sample predictive accuracy, due to the fact that you are massively overfitting your data. You are searching through $2^n$ instances (or at least upper bounded by it) each of which are determined by only by $k \ll 2^n$ samples. If you limit yourself to lower-order polynomials over your features you can still only reasonably fit your data when the number of samples $k$ is greater than the size of your model $O(n^c)$ (without regularization techniques). If you want to proceed with your algorithm despite this concern, I would not use whatever predictive accuracy you are using as a measure of "goodness-of-fit". Predictive accuracy does not take model complexity into account.

Now what you've described is really one way to perform model selection. There are tons of ways to perform this in the literature based on AIC/BIC measures, likelihood ratios, and more complex Bayesian averaging techniques.

Even using something like LASSO or Iterative Hard Thresholding will perform some semblance of model selection without needless searching the entire projection space. For example, lift each $x\_i$ to your polynomial space determined by $c$, then just run LASSO (or equivalent regularized classifier). It will still be able to determine which features (both your original and higher-order terms) will be relevant.
> 1 votes

# Answer
I suspect you are asking about feature selection. There are many reasonable algorithms for feature selection; one could write an entire book about the subject. I suggest you start by reading up on standard methods for feature selection, and see if they will meet your needs.

See, e.g., information gain, AIC, BIC, and many others. Many methods for feature selection use a held-out validation set (or cross-validation) as part of the procedure.

That said, do you really need feature selection? Probably not. In supervised learning you often don't want to do feature selection yourself as a separate step. The simplest approach is to avoid doing any feature selection at all, and just train a classifier on your data (with all of the features), and let the classifier learn which features are most helpful. it sounds like your goal is prediction rather than model building: you're not going to inspect the model or set of features as something that's interesting in its own right, but rather use it to try to help you make predictions that are as accurate as possible. Given that, feature selection is often unnecessary. Many good classifiers render it unnecessary to perform a separate feature selection step: they already incorporate some techniques to "learn" which features are most helpful and rely especially on those (e.g., they use regularization or similar methods).

For this reason, if your goal is *prediction* rather than model-building, and if you are using a reasonable classifier (e.g., with regularization), then I would recommend that you *avoid separate feature selection and just train the classifier directly on all the features*. Only do explicit feature selection yourself if the classifier is known to need feature selection or if your primary interest is in the model itself rather than in ability to make predictions.

Examples of supervised methods that normally don't need or benefit from a separate feature selection step: SVM, random forests, deep learning (with suitable drop-out or regularization), LASSO regression, ridge regression, elastic net regression.

Examples of supervised methods that often do benefit from a separate feature selection step: $k$-nearest neighbors.

Warning: This is a necessarily crude, incomplete summary of an entire area, intended to give you a gist of the field rather than to make precise, 100% accurate statements. Don't rely too heavily on the statements made here; study the area to learn the details.
> 1 votes

---
Tags: machine-learning, artificial-intelligence, data-mining
---


# Question
Title: Question regarding the potential method for amortized analysis
What does the following mean exactly for the potential method? Is this applicable to all situations?

> If the potential is positive, then we overcharged for some operations. If it is negative, we are undercharged.

# Answer
In the potential method, operation $O$, which has real cost (say time complexity) $p(O)$ is charged $c(O)$. The *potential* at any given point is $$\sum\_{t=1}^T (c(O\_t) - p(O\_t)),$$ where $O\_1,\ldots,O\_T$ is a list of the operations that have been performed. The idea of the potential method is that if the potential is always non-negative then $$\sum\_{t=1}^t p(O\_t) \leq \sum\_{t=1}^t c(O\_t),$$ that is, we can bound the total real cost by the total amount of charge.

Hopefully now you can answer your question on your own.
> 2 votes

---
Tags: algorithm-analysis, amortized-analysis
---


# Question
Title: Class of the language only containing the empty string?
$L = \left \\{ \epsilon \right \\}$
Clearly this language is finite so this must be a regular language.
Now since every regular language is Context Sensitive, $L$ is a CSL.
We can define the grammar for $L$ as :
$S\rightarrow \epsilon$
Now since $L$ is a CSL, this grammar must be a Context Sensitive Grammar. But from the definition of a Context Sensitive Grammar:

> A Context sensitive grammar is any grammar in which the left side of each production is not longer than the right side.

But here
$\left | S \right | \> \left | \epsilon \right |$
This is contradictory.
I am unable to figure out what's wrong here.

# Answer
> 10 votes
This issue is covered in wikipedia's article on noncontracting grammars. Such grammars do not allow deriving the empty string, which is no problem when one considers languages $L\subseteq A^+$. When one wants to allow the empty string, a special case is made and the rule $S\to\lambda$ is allowed with ugly side conditions ($S$ cannot appear in a right-hand side).

So the situation is that there are several available, mostly equivalent, definitions, that offer different tradeoffs between elegance, generality, ease of use, etc. This is a typical situation in mathematics. When you scratch the surface, the different definitions are there and they come with extra terminology, like "essentially noncontracting".

This may look confusing for newcomers but the good side is that it separates the important from the not-so-important details.

BTW your reasoning has a flaw. You say that the language is CSL (correct) and $S\to\lambda$ is a grammar for it (correct), **thus** that grammar is CS. That implication is incorrect. You can only deduce that there exists **a** CS grammar for it. But you are right in thinking that any such grammar must have a contracting rule.

---
Tags: formal-languages, regular-languages, context-sensitive
---


# Question
Title: DFA accepts common strings, reduction to NPcomplete
$B=\\{\left\<M\_1,M\_2,...,M\_k\right\>\text{ : Each $M\_i$ is a DFA and all of the $M\_i$ accept some common string.} \\}$

I'm trying to show that B is NP-complete. I know I have to reduce it to another NP-complete problem, but I'm having a lot of trouble coming up with the algorithm that decides B.

I was thinking I could keep track of all the DFAs accepted by M1 and then check those in M2, any that accept there I'd feed to M3 and so on until I either ran through all the DFAs (accept) or ran out of accepted strings (reject). I'm not really convinced this runs in NP time though. How exactly do I prove that it does? Or is this a terrible algorithm?

Thank you!

# Answer
> 3 votes
Your problem is actually *not* NP-complete (unless NP=PSPACE), though it is NP-hard. The problem is that the witness - the string in the intersection - could be very long.

Kozen showed that DFA-intersection is PSPACE-complete, which implies the preceding paragraph. For a very similar proof (of a different statement), see my writeup.

---
Tags: complexity-theory, np-complete, finite-automata, reductions
---


# Question
Title: Do Self Types make the Calculus of Inductive Constructions obsolete?
Self Types are an extension of the Calculus of Constructions \[1\] that allow the language to express algebraic datatypes encoded through the Scott Encoding. The Scott Encoding provides one the ability to pattern-match in `O(1)`, which is one of the main motivators for the inclusion of inductive definitions on CC. Yet, Self Types are make for a much simpler and elegant base theory, and are seemingly no less powerful.

Do Self Types, under a theoretical point of view, make CIC obsolete, or is there still some aspect on which CIC is favorable in relation to Self Tyes?

\[1\] http://staff.computing.dundee.ac.uk/pengfu/document/talks/mvd-2012.pdf

# Answer
> 4 votes
I'm not an expert in this work, but it seems to me that the major current issue is a lack of SN proof, even with restrictions. These proofs are notoriously tricky though, even when the calculus is correct, so I'd give it a little time. The work is certainly very promising.

One thing to note is that these restrictions are actually quite non-trivial to express, which is a large part of the complexity of the formulation of the inductive families in the CIC. The real selling point of an approach like this would be to concisely formulate these conditions.

It's been a somewhat longstanding open problem to have a dependently typed language which is

* Consistent/Normalizing
* Can express all the type families from Coq (or even Agda)
* Allows for a simple expression of recursion over these families
* Simple or has a small number of core constructions ($\Pi,\Sigma,\mu$).

One such attempt that I know of is the Altenkirch & al $\Pi\Sigma$ language, which similarly lacks a full meta-theoretical study (and also isn't consistent without further restrictions).

---
Tags: lambda-calculus, type-theory, functional-programming, inductive-datatypes
---


# Question
Title: If two languages together cover all words and one is regular, is the other one as well?
If $L\_1$$\subseteq$ $\Sigma^\*$, $L\_2$$\subseteq$ $\Sigma^\*$ , $L\_1$ is regular and $L\_1$$\cup$ $L\_2$ = $\Sigma^\*$ then is $L\_2$ necessarily regular?

I think that the answer is yes, but I'm not sure on my proof.

The reason that I think that $L\_2$ is regular is because surely $L\_2$ just accepts all the words in the language that $L\_1$ doesn't? So, to me, that suggests that $L\_2$ must be regular as well, I just don't know where to begin on a formal proof.

Any guidance would be appreciated.

# Answer
> 4 votes
In fact, the answer is no.

If $L\_1$$\subseteq$ $\Sigma^\*$, $L\_2$$\subseteq$ $\Sigma^\*$ , $L\_1$ is regular and $L\_1$$\cup$ $L\_2$ = $\Sigma^\*$ then is $L\_2$ is not necessarily regular.

We can prove this through counter-example.

If we let $L\_1$ = $\Sigma^\*$, then we can choose any non-regular language in $\Sigma$ for $L\_2$.

If we take $\Sigma$ = {a,b} and then let $L\_2$ = $a^n$$b^n$ (A non-regular language) then $L\_1$$\cup$ $L\_2$ = $\Sigma^\*$ and $L\_2$ is non-regular as required.

---
Tags: formal-languages, regular-languages, closure-properties
---


# Question
Title: Difference between Bayesian Networks and Dynamic Bayesian Networks
I'm studying Bayesian networks and want to clarify a couple of things with people who are more knowledgable in the area than me.

As far as I understand it, a Bayesian network (BN) is a directed acyclic graph (DAG) that encodes conditional dependencies between random variables. The graph is drawn in such a way that the the distribution (dictated by a conditional probability table (CPT)) of a random variable conditioned on its parents is independent of all other random variables. I'm assuming that, by definition, both the structure (nodes and edges of the DAG) and the entries of the CPT in a BN assumed to be fixed in time.

Now, I'm wondering about the distinction between BNs and Dynamic BNs (DBNs), specifically, where the *dynamic* term in a DBN arises from:

Does this mean that the structure AND conditional dependencies between variables are time-varying? If so, is a BN with a fixed structure (DAG) but time-varying probabilities also considered a DBN (does this type of 'DBN' have a name)?

I'm not sure if what I've said is correct. Please let me know if I went wrong anywhere or if there is a better way of thinking about this.

# Answer
> 4 votes
A DBN means that your model is replicated over each time discrete time step t, called slice. Variables of each slice can be connected together, as well a from previous slice to a latter slice (in this precise direction only). The probability tables and links remain the same in each slice if the model is stationary, which is the default case (otherwise they are a function of t).

In a 2TBN (2-step Timeslice Bayesian Network), there are links only between the previous and current slices.

For more information c.f. section 3.2 of http://journal.frontiersin.org/article/10.3389/fncom.2014.00131/full

---
Tags: machine-learning, bayesian-statistics, graphical-models
---


# Question
Title: Understanding the proof of the halting problem
I came across the following example that proves that the blank tape halting problem is not decidable.

I understand the proof technique, but I just don't see how the blank tape problem is shown to be undecidable in the proof.

It says $M\_{w}$ starts with a blank tape but then writes $w$ onto the tape, so there is no difference to the general halting problem.

How does this imply that the blank tape halting problem is not decidable? I can't find the logical conclusion. Couldn't we just replace the blank tape halting problem with another DECIDABLE problem and argue the same way?

# Answer
The argument shows that if you can solve the blank tape halting problem then you can solve the halting problem. Since you can't solve the halting problem, it follows that you can't solve the blank tape halting problem. (Here "solve" means "decide with a program that always halts".)

It's true that the same argument shows that many other problems are undecidable. But if you try to prove that a decidable problem is undecidable this way, then something will go wrong. Try it out!
> 3 votes

---
Tags: computability, proof-techniques, undecidability, halting-problem
---


# Question
Title: Performance of microkernel vs monolithic kernel
A microkernel implements all drivers as user-space programs, and implements core features like IPC in the kernel itself. A monolithic kernel, however, implements the drivers as a part of the kernel (e.g. runs in kernel mode).

I have read some claims that microkernels are slower than monolithic kernels, since they need to handle message passing between the drivers in user space. Is this true?

For a long time, most kernels were monolithic because the hardware was too slow to run micro-kernels quickly. However, there are now many microkernels and hybrid kernels, like GNU/Hurd, Mac OS X, Windows NT line, etc.

So, has anything changed about the performance of microkernels? Is this criticism of microkernels still valid today?

# Answer
> 11 votes
**As is always the answer (or at least the preface) to performance-related questions: know your problem domain, run comparative benchmarks, and remember what premature optimization is.**

First, no comprehensive benchmarking trials have compared monolithic kernels to current-generation microkernel systems that operate in an equivalent manner. So, while there may be trials that compare specific elements of those kernels, they're not going to be representative of the "big picture" that your question is looking to paint.

With that being said, there are wildly divergent observations of kernel performance across microkernels; for example, the L4 microkernel family can be said to have IPC performance an order of magnitude higher than the Mach kernel. But every Apple device from this decade is running Mach, and they seem to work plenty fast, right?

The moral of the story is that anybody who's deciding what kernel architecture to use needs to first decide what their ultimate goal is. Microkernel systems are (when properly implemented, of course) more secure, maintainable, and modular. However, they can be tough to architect properly, and may have performance overhead over a monolithic implementation. A monolithic kernel will be faster, but security will be harder to implement and it will be less modular and less easy to customize.

Your kernel architecture should be based on what your end goal is.

<sub>(And when all else fails, try it both ways and see what happens.)</sub>

# Answer
> 5 votes
I prefer to call Windows NT and Apple's XNU kernel monolithic instead of hybrid. I don't find the classification of hybrid to have much meaning in practice. In fact one of the original engineers of XNU calls it monolithic\[1\].

On the issue of performance, the only really in-depth comparison of monolithic vs micro I can find is "Extreme High Performance Computing or Why Microkerenels Suck"\[2\] and a rebuttal presentation "Do Microkernels Suck?"\[3\].

Modularity and customizablity are more issues of design than inherent limitations in monolithic kernels. The Linux kernel, for example, can range from several megabytes to around one megabyte in size dependent on compile-time options and the application of certain patches. The vast majority of Linux's 15 million plus lines of code are loadable kernel modules. They are compiled separately from the base kernel and only loaded when needed. Those modules can implement drivers and system calls (even overriding base system calls).

The two areas where microkernels have an undisputed advantage is in low memory (\<=512k ram) or "hard" Real-time operating systems, like airline flight systems or nuclear reactor control systems.

Edit: Talking further on the advantages and disadvantages of either kernel architecture, Gernot Heiser freely admits at the end of his presentation\[3\] that monolithic kernels are inherently more performant because a microkernel always has some extra overhead. Though, that extra overhead does lead to increased reliability, hence microkernels dominance of RTOS.

\[1\] Louis G. Gerbarg, "Advanced Synchronization in Mac OS X: Extending Unix to SMP and Real-Time", Proceedings of BSDCon 2002 Conference, pp. 2

\[2\] Chistoph Lameter, "Extreme High Performance Computing or Why Microkernels Suck", 2007 Linux Symposium, Volume One

\[3\] Gernot Heiser, "Do Microkernels Suck?", 9th Linux.conf.au, January, 2008

---
Tags: operating-systems, performance, os-kernel
---


# Question
Title: What are the practical uses of ontologies?
I have read many papers and books about ontologies and I am trying to figure out that how they are used in a real project?

For example how the ontology for a soccer player robot can be defined and used with a cognitive architecture in order to make it intelligent?

Are ontologies relations between terms in that domain of knowledge ( for example relation between the ball and foot word and physical rules definition and their relation with the foot and ball movement , ...) or relations between tactics , strategies and different mixtures of tactics ?

Are there any clear examples of ontology usage in real projects and their combining usage with the cognitive architectures like ACT-R for augmenting the cognitive architecture?

# Answer
> 6 votes
I don't know about robotics, but ontologies are part of the standard toolkit for modern expert systems, especially those with a natural language processing component.

For example, consider the process of performing literature searches for systematic reviews in medicine. Of the millions of medical studies out there, reviewers need to find the 20 or so high-quality randomised control trial studies which are relevant to the clinical question that they want to answer. This is a classic needle-in-a-haystack problem, and computer scientists would like to build tools to aid the search.

Medical ontologies such as MeSH, ICD, and GALEN play a role in this, because they represent an "answer" to the question of what a given medical study is "about".

# Answer
> 4 votes
IBM's question-answering system, Watson, used the ontology DBPedia in their evidence scoring algorithms to compete (and win) the Jeopardy Challenge.

# Answer
> 3 votes
Ontology gives you a power to model, reason and manage complex data systems from different domains. For example Natural Language Processing (NLP), Molecular Biology and Bioinformatic, Wireless Sensor Networks, to name a few.

Considering semantic web (RDF-based) as a special **use case** of ontology-based systems, there are many companies and commercials on that like Franz.Inc work on semantic web and Freebase (part of Google).

# Answer
> 3 votes
Ontologies abstractly defined are "representation of knowledge": the object and their relations.

Basically the ontology represent the knowledge exploited by the "intelligent" agent.

Now in practice, ontologies can be used either as:

* a structured knowledge representation for domain-specific databases
* a structured data format for interoperability of different systems
* a way to structure an object hierarchy with a programming language for a target domain

Cognitive architecture, means that there is a decision architecture that nativey exploits knowledge representation and inteligent inference based on it, as it is for example the case with BDI (Belief Desire Intention) agents that use modal logic.

In the field of Multiagent Systems, you can check the many industrial project based on JADE or JACK architecure, which use ontologies and cognitive architectures.

# Answer
> 2 votes
There is a fairly strong connection between ontologies and APIs. An ontology can be regarded roughly as a word-based API. Many are associated with web-based languages in XML part of the so-called semantic web also defined here. Tim Berners Lee, the inventor of the web, has strongly advocated the semantic web & has written on it. Here are two simple examples that are easily understood w.r.t. blogs.

---
Tags: artificial-intelligence, applied-theory, knowledge-representation, ontologies, robotics
---


title: non-binary self balancing tree

text:
# Question
Title: non-binary self balancing tree
I'm looking for a tree data structure that allows to keep the tree balanced in high (minimum high as possible).

I mean, suppose a tree where:

* each node has a parameter k that is the maximum number of sons that can be attached to him, $0≤k≤N$
* all the operations will be about insert and delete (no search): it's just just important that every node know the son/s, I'm not interested at all in search (\<0.1% of operations)

Would an adaption of RB-tree or AVL tree be a good idea for that task or there are better solutions (other data structures, other kind of tree, etc)?

# Answer
You can use a binary prefix-trie (critbit-tree). It's not exactly selfbalancing, but it never requires rebalancing and imbalance is limited. For example, with 64bit keys, the maximum depth is strictly 64. This is not exactly the lowest possible height, but maybe that requirement can be relaxed because no rebalancing ever occurs?

You can find an (my) implementation here.
> 1 votes

# Answer
If your tree is a non-binary tree, and you have no limitations on the number of children, you can create a tree with a single root and infinite number of children. The height of that tree will be always 1.

```
class Node
{
    int data;
    SortedSet<int> children;
    function insert(int n)
    {
        children.add(n);
    }
    function delete(int n)
    {
        if(n exists in children) then delete n;
        else return error;
    }
}

```

**Application:**

```
Node root = new Node(5);
root.insert(8);
root.insert(10);
root.insert(20);
root.insert(-9);
root.insert(72);
root.insert(65);
root.delete(20);

```

The result will look like this:

```
             5
      /   /  |  \   \
   -9   8   10   65  72

```

Both `insert()` and `delete()` will take $O(\log (n-1)) = O(\log n)$ time in the worst case, $n$ being the number of nodes in the tree.
> 0 votes

---
Tags: data-structures, trees, balanced-search-trees
---


# Question
Title: Seems like NP cannot equal coNP by the definition of NP
A yes answer to an NP problem must be deterministically verifiable in polynomial time. The complement is that the no answer must be similarly verifiable. If the problem is NP-complete, there will generally be an intractable number of possibilities. How can it be possible to deterministically verify the no answer for all possibilities in polynomial time?

As an example, would it not be necessary to address every non-empty subset to verify a no answer for the subset sum problem?

# Answer
This kind of argument presupposes that the only way to (for example) prove that a SUBSET-SUM instance is not solvable is by going over all subsets and checking that their sum doesn't match. This isn't true — a meet-in-the-middle algorithm works in time $O(\sqrt{2}^n)$ rather than $O(2^n)$, where $n$ is the number of sets.

Furthermore, consider the analog of this question for polynomial *space* rather than *time*. In this case it *does* hold that NPSPACE=coNPSPACE, for the simple reason that PSPACE=NPSPACE.
> 7 votes

# Answer
If I'm understanding your question correctly, then I see no problem with the ability to verify a "no" answer in polynomial time. I think you misunderstand what the complement is calling for.

Given the subset-sum problem, an answer would be a subset of the given set, and to verify that answer would be to determine whether or not its sum equals the target sum. So for a "no" answer, simply add all values in the answer (in exactly the same way you're adding the values of a "yes" answer) to arrive at the conclusion that the sum of the subset does not equal the target sum for the specified problem.

You say:

> The complement is that the no answer must be similarly verifiable.

This is still true. You don't have to be able to verify all possible "no" answers, together, in polynomial time to satisfy the complement. You only have to be able to verify a *given* "no" answer in polynomial time. Which holds.
> -2 votes

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


title: Branchless function equivalent

text:
# Question
Title: Branchless function equivalent
Does every pure function have a branchless equivalent?

By *pure* function I understand a function that uses only its input values and no global state to produce the output.

By *branchless* function I understand a function that does not use if/else during its execution. A loop contains a branch with and unconditional jump. Constant loops can be unrolled.

As an example, here is the signum function:

```
function signum(x):
  if (x > 0) return 1;
  if (x < 0) return -1;
  return 0;

```

And here is a branchless version of the same function:

```
function signum(x):
  return (x > 0) - (x < 0);

```

# Answer
> 2 votes
The general answer to your question is no. Consider a function which measures the length of a linked list. How would you implement that without a branch?

But if you just stick with functions which (say) take a machine word and return a machine word (which your example does) then the answer is "yes, sort of". In fact, when analysing algorithms in the word-RAM model, we conventionally assume that any function which takes a fixed number of machine words and returns a fixed number of machine words is constant-time, because it could (in principle, at least) be implemented with a lookup table or a new CPU instruction.

Whether the branch-free version is more practical or not depends partly on the function and partly on the CPU's instruction set.

Don't forget, by the way, that pretty much all modern CPUs have a conditional move instruction. Some ISAs (e.g. ARM) can do conditional execution of all, or almost all, instructions. So there's even more ways to implement branch-free code there.

# Answer
> -1 votes
Here is a pure function which cannot be written without if/else. It takes one number and if the number is even it returns "EVEN" string or else it returns "ODD" string.

Also, in your second code sample the expression (x \> 0) is internally a branching and it returns a boolean value and you cannot subtract boolean values.

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


# Question
Title: Proving "QUESTION" is NP-Complete by reduction from n-variable 3SAT
I'm struggling with a problem in my theory of computation course that asks us to prove "QUESTION" is NP-complete by reduction from n-variable 3SAT. I've done a number of other similar reductions but I keep getting stumped on this particular problem.

We define a question as a string over the alphabet $\\{0,1, ?\\}$ and say that a question covers all of the strings where substituting ?? with 0s and 1s yields a string such as $0??1$ covers the four strings $0001$, $0011$, $0101$, $0111$.

We have to reduce the 3SAT problem to QUESTION= {A : A is a set of questions, each of length $n$, such that there exists a string $w$ of length $n$ where no question in A covers $w$}. To show that it is NP-complete.

I recognize that some instance of QUESTION will "cover" less than $2^n$ strings but I'm pretty stumped on how to go forward as all of the things I've tried end up not working out.

# Answer
> 2 votes
The reduction is straightforward, but what's likely tripping you up is that while 3CNF clauses seem to describe what's needed for a satisfying assignment, what they do more directly is describe what assignments *won't* work, and that's the insight you need to do the reduction.

Each clause will be converted into a QUESTION string of length $n$, where $n$ is the number of variables in the 3CNF formula. Number the variables in the formula from 1 to $n$. For each clause output a QUESTION string with a 0, 1 or ? in the position of the string corresponding to that variable's number. Use 1 if the variable is negated in the clause, 0 if it is not negated and ? if it does not appear in the clause at all.

Example: the 3CNF formula has seven variables ($x\_1$ ... $x\_7$) and there is a clause ($x\_1 \lor \lnot x\_4 \lor x\_7$) you would output the QUESTION string 0??1??0 .

Once all the clauses are converted to QUESTION strings, any $w$ string not covered by the QUESTION strings can be directly converted to a satisfying assignment for the 3CNF formula. As in the QUESTION strings each position in $w$ corresponds to previously numbered variable. But in $w$ each 0 represents a variable that should be negated in the satisfying assignment, and each 1 represents a variable that should not be negated.

---
Tags: complexity-theory, reductions, np-hard
---


# Question
Title: What combination of data structures efficiently stores discrete Bayesian networks?
I understand the theory behind Bayesian networks, and am wondering what it takes to build one in practice. Let's say for this example, that I have a Bayesian (directed) network of 100 discrete random variables; each variable can take one of up to 10 values.

Do I store all the nodes in a DAG, and for each node store its Conditional Probability Table (CPT)? Are there other data structures I should make use of to ensure efficient computation of values when some CPTs change (apart from those used by a DAG)?

# Answer
> 12 votes
The "best" data structure probably depends on what particular problem you're trying to solve with it. Here's one approach that I've seen (and have used myself), which simply stores all the information and leaves it up to the algorithm what to do with it.

1. First you index the nodes by unique integers, 0 through n-1. Then you simply store, for each node, the list of its parents as an array of integers --- in C++, for instance, you could have a `std::vector<std::vector<int> >`: first vector over nodes, second vector lists the respective parents). That captures the entire DAG structure.
2. Furthermore, since each node has exactly one conditional probability table associated with it, you could index those with the same integer IDs. For each probability table you need to store its scope, i.e. the set of random variables its defined over. Secondly you'd probably have one large list of floating point numbers that contains the actual conditional probabilities (and you'll want to make sure you get the indexing right). To give a C++ example again, something like this could do:

```
struct CondProbTable {
    std::vector<int> scope;    // list of random variables the CPT is defined over
    std::vector<double> table; // appropriately sized and indexed table of
                               // conditional probabilities
};

```

With that, you could use a `std::vector<CondProbTable>` to store all your CPTs.

Again, this basically only stores the Bayes net, it does not assume anything about what you want to do with it. Including the CPT scope in CondProbTable is somewhat redundant, since it could be inferred from the list of parent nodes described under point 1.

# Answer
> 0 votes
Basically discrete CPT are hypermatrixes, and you should look at them in this way.

A quite common way to represent an hypermatrix is to use an hashtable using string index. e.g. in 2 dimensions t\[1\]\[2\] would be t.get("1\_2")

More memory efficient solution are possible: If the hypermatrix is sparse, you could use special sparse representation (e.g. Fuchs 72), if it has structure you could use ADD (algrebraic decision diagram), or logic-based rules.

Your last question is not very clear, however if you expected your CPT to change often, the probably you'll be better off with a flat representation of the CPT with either a table or an hashtable.

---
Tags: data-structures, machine-learning
---


# Question
Title: Another version of the online set cover problem?
Here is a note about online set cover problem: we are initially given the $m$ sets, but we do not know which elements they contain. At any time $t$, we get a new element $e\_t$ and learn which sets contain $e\_t$. We then have to irrevocably pick a set that will cover $e\_t$ if it is not already covered. The goal is again to minimize the number of sets we pick.

However, I'd like to think about another version: we have a group of sets $\mathcal{S} = \\{ S\_1, S\_2, \cdots, S\_m \\} $ and a universal set $U=\\{ e\_1, \cdots, e\_n \\}$. $U$ can be covered by $\mathcal{S}$. But we don't know what elments each $S\_i \in \mathcal{S}$ contains. Then $S\_1$ comes and now we know what elements $S\_1$ contains. Meanwhile, we have decide either you will use $S\_1$ to cover $U$ or you discard it. Then, $S\_2$ comes, you know what elements $S\_2$ contains and decide to keep $S\_2$ or discard it. The process is repeated until the sets you keep can cover $U$.

I want to ask if there is an algorithm works in the way I mentioned. Must we check all the $S\_i \in \mathcal{S}$ in order to get a solution of set cover? Or what is the expected number of sets that have to be checked in order to get a solution of set cover? If we can also design a $O(\log n\log m)$ approximation ratio algorithm for this online version.

# Answer
> 1 votes
A simple adversary argument shows that you must take every set you are offered, unless it's entirely covered by elements already taken. Indeed, otherwise there must be some element $x$ which hasn't appeared before; perhaps it will never appear again, so you must take the set.

Consider now the following instance: $$ \\{x\_1\\},\\{x\_2,\\},\ldots,\\{x\_{m-1}\\},\\{x\_1,\ldots,x\_m\\}. $$ The algorithm takes all $m$ sets, but the last one would have sufficed. This shows that the approximation ratio can be as bad as $m$, the number of sets.

---
Tags: algorithms, set-cover
---


# Question
Title: How do incompressible strings and random strings share the same properties?
I came across the following theorem in Sipser's about incompressible strings.

> Let $\\;f$ be some computable function which holds for almost all strings. The for any $b \> 0 $, the property $\\;f$ is false only on finitely many strings that are incompressible by $b\\;$.

where "almost all strings" means that as $n$ grows the fraction of strings of length $n$ for which $f$ is false approaches $0$.

The book proves the above theorem and says that if we select some sufficiently long string at random, it's likely that property $f$ would hold true for it. Thus incompressible strings and random strings share this property.

Though I understand the proof for the theorem, I am unable to understand its meaning. How does this show there is some sort of relation between incompressible strings and random strings?

Also how does this theorem help us? Although I can generate random strings, there is no method to generate incompressible strings in general.

# Answer
The theorem says, in effect, that incompressible strings are a deterministic model of random strings. If you have some property that you can prove using random strings, you can also prove it using incompressible strings instead. If you have some construction involving a random string, you can make it somewhat more explicit using an incompressible string.

Another deterministic model of randomness, which is very useful in theoretical computer science, is expanders. These are models of random graphs with respect to a lot of properties. In many cases, instead of using a random graph you can use an expander. Since we can construct expanders explicitly, this allows us to derandomize many randomized constructions.

While the same cannot be said for incompressible strings, they are useful in some circumstances. Their use in lower bounds is known as the *incompressibility method*, which I encourage you to look up.
> 6 votes

---
Tags: computability, data-compression, randomness
---


title: Dijkstra vs Floyd-Warshall

text:
# Question
Title: Dijkstra vs Floyd-Warshall
I know this question is a bit redundant but I am trying to understand a subtle difference between `Dijkstra Algorithm` and `Floyd-Warshall Algorithm`. Can I say running Floyd-Warshall is equivalent to running Dijkstra on every vertex in the graph? In other word, Dijkstra will output the optimal path from a **single source** to other vertices at one runtime while Floyd algorithm does what Dijkstra does but for all vertices in at one runtime so Floyd does not require a source as an input.

Thank you

# Answer
> 0 votes
Bth algorithm proceed in different ways.

First you are right in that Floyd Warshall computes all pairs of shortest paths in one run.

If you want to compute all pairs of paths, in the general case (without knowing special property about the graph that could be exploited), running floyd warshall, is more efficent O(n^2) than running n times dijstra O(n^3 + n^2\*log(n)).

So for this purpose, in terms of the computations performed, they are different, but in terms of the results, you would obtain the same.

---
Tags: algorithms, graphs
---


# Question
Title: Can we do everything in imperative languages with a functional language if it does not allow for a 'state'?
I was reading Structure and Interpretation of Computer Programs (SICP), MIT. What I have understood is that in pure functional programming language, there is no such thing as a local state. SICP, pg 230 says:

"Programming without any use of assignments, as we did throughout the last two chapters of this book, is accordingly known as functional programming."

I come from a imperative programming background, and I can't seem to comprehend how to design a program that models a real world system (like a simple bank or a library management software) without the idea of state.

If functional programming does not have the idea of a state, how do we do this?

# Answer
The key with functional programming is not that there is no state, it's that there is *explicit state*.

What this means is, that your state is passed around as a parameter to your functions. It's an actual value, that you can get your hands on, look at, and pass to other functions.

For example, let's look at the Dynamic Programming method of calculating the Fibonacci numbers. In an imperative language, you'd have something like this:

```
def fib(n):
  A = {}
  A[0] = 0
  A[1] = 1
  for i in [2 .. n+1]:
      A[i] = A[i-1] + A[i-2]
  return A[n]

```

To do this without state, you just have to explicitly pass your store around. Using Haskell-ish syntax:

```
fib n = fibHelper 2 n {(1,1), (0,0)}

fibHelper i end cache =
  if
    i > end
  then
    lookup end cache
  else
    let
      newVal = (lookup (i-1) cache) + (lookup (i-2) cache)
      newCache = insert i newVal cache
    in
      fibHelper (i+1) end newCache

```

Now, this is a bit contrived, since you don't need the whole array for the Fibonacci numbers, but you can imagine using this for more complicated dynamic programming problems like Knapsack, where you do need the entire set of previously computed values.

The key thing to understand here is that `insert` is a function which takes a store, and returns a new store, which is equal to the original with a new value added. The original value of `cache` doesn't get destroyed, so if you had an application where you needed some sort of "undo" operation, you could keep track of your state's history.

You might say "but that looks inefficient! You're creating a whole new store each time!" However, usually in functional languages, these things are implemented cleverly using references, so that there aren't whole new copies of the data lying around.

It's also worth mentioning that this pattern of having a state parameter, passing it around as your computation progresses, and modifying it, is very common. People have invented abstractions, like the State monad, which allow you to write things that look imperative, but which are purely functional "under the hood."
> 8 votes

---
Tags: programming-languages, functional-programming, programming-paradigms
---


# Question
Title: Decidability of empty intersection of two languages accepted by Turing machines
I am really struggling with determining the decidability of languages and cant figure out whether this problem is decidable or not.

I have a language

$\qquad\displaystyle L = \\{ (R(M\_1), R(M\_2)) \mid L(M\_1) \cap L(M\_2) = \emptyset \\}$,

where $R(M\_1)$ and $R(M\_2)$ are representations of Turing machines $M\_1$, resp $M\_2$ and $L(M\_1)$, $L(M\_2)$ are the languages accepted by these machines.

Is language $L$ a decidable language?

I have found this theorem: It is undecidable whether or not the languages generated by two given context-free grammars have an empty intersection. (but I dont know whether $L(M\_1)$ and $L(M\_2)$ are context-free, I only know that they are accepted by some machines, so I dont know if I can use this theorem).

I think that this problem is *undecidable* and my attempt to prove this would go like this:

In order for this language to be decidable. I would have to build a Turing machine that tests whether an arbitrary word is accepted by $M\_1$ and not $M\_2$ (and vice versa) but I cannot guarantee that it will halt for all inputs (since language acceptence does not guarantee that the language is decidable) so it proves the undecidability.

Is this correct approach?

Is $L$ at least recursively enumarable?

# Answer
> 7 votes
It is undecidable whether a Turing machine accepts any input at all (reduction from the halting problem). So, take a machine $M\_1$ that accepts all inputs. $L(M\_1)\cap L(M\_2) = L(M\_2)$ so non-emptiness is undecidable.

The intersection of two RE sets is RE. This is a standard fact: simulate the accepting machines in parallel and accept iff they both accept.

# Answer
> 3 votes
Your approach does not give you a formal proof: There could be other ways to decide membership for $L$ than testing for membership in $L(M\_1)$ and $L(M\_2)$ separately.

You can prove this by reduction instead: Assume you had a TM that decides $L$ and use this TM plus some pre- and/or postprocessing to decide a problem that you know is undecidable. (The intersection of context-free languages is a good candidate here.)

Also the complement of $L$ is recursively enumerable, so $L$ is not (as that would imply decidability).

# Answer
> 2 votes
If $G$ is a context-free grammar, there exists a turing machine whose language is the language generated by $G$. Let two context-free grammars $G\_1$ and $G\_2$ be given, and let $M\_1$ and $M\_2$ be Turing machines accepting the languages of $G\_1$ and $G\_2$, respectively.

A decider for your $L$ would in particular decide whether $L(M\_1) ∩ L(M\_2) = ∅$, which is impossible according to the theorem you quoted.

# Answer
> -3 votes
We can reduce this problem to the decision of an empty language by a turing machine (Etm), as previous posted. In this case I think that the problem can be more easily solved if we use the Etm Decider as a post-processing.

First, we know that L(M1) $\cap$ L(M2) = L(M1) if L(M1) $\subseteq$ L(M2). So we construct a decider that tests if L(M1) $\cap$ L(M2) = L(M1). If the answer is no, we reject. If it is yes, we test if L(M1) $\neq$ $\emptyset$. If yes, we accept. If no, we reject.

It is a contradicition, since Etm is undecidable.

Is this approach correct to this problem?

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


# Question
Title: Patriot Missile Software Bug (Range Gate Calculation)
Okay so I was reading about the Patriot Missile Software Bug, where to calculate the predicted range gate the missile system relied on the time keeping, however it would convert the whole/integer time number it stored (say 3600000) to 24 bit multiplying it by 1/10 (0.00011001100110011001100) to produce the time in real format in seconds, this way 'truncating' the actual time it computed before the converstion to a 'slightly smaller number' due to insufficient precision of 24 bit limitation. My question is not about the conversion or binary manipulation but rather how was the range gate calculated after taking the new calculated/truncated time into account for the purposes of establishing a 'distance/location/space' of where to look for the coming missile? Say the missile velocity is 2km/s, the time it was detected is at 100hrs.

# Answer
> 1 votes
there is some scientific/ engineering analysis of this defect & its background by professionals eg this turned up by the SEERI institute, Software Engr Ethics Research institute, An analysis of the patriot missile system (note, some glitch with figure(s) at time of this writing). essentially the missile tracking logic is highly time dependent and relies on the clock being accurate to predict the missile location and intercept position and steering corrections. there are many other "classic" bugs in software that are related to clock logic. analysis of the failure also includes/ points to inadequate testing.

another reference cited in that article, Roundoff error and the patriot missile / Robert Skeel, SIAM News.

this particular defect is getting some attention lately as it was recently ranked in the 5 most infamous software bugs of all time and of course its related to missile defense technology, a hot topic during wars.

---
Tags: algorithms, physics
---


# Question
Title: Is it possible to calculate the propagation delay if only the length of the link is known & not the speed at which a bit travels into the link?
> *Consider a $10^7$ bps link that is $400$ km long, with a queue large enough to hold $2000$ packets.Assume that the packets arrive at the queue with an average rate of $4000$ packets per second and that the average packet length is $2000$ bits.Find the average number of packets in the queue.*

I am getting Average Queue length = 0.

---

In this question is it possible to calculate Propagation delay?
How can we calculate the propagation delay until we don't know about the speed at which a bit travels in the link?

# Answer
> 2 votes
I believe your approach is right. Since we don't have any other information given. Then this means the packets are getting consumed at the rate same as link bandwidth. So Avg packet waiting must be 0.

# Answer
> 1 votes
Yes, you can infer the propagation delay from the length of the link if you know something about the technology used to transmit the bits. As Wikipedia says, the propagation delay is equal to $d/s$ where $d$ is the distance and $s$ is the wave propagation speed. The wave propagation speed depends upon the technology and might be as fast as $c$ (the speed of light) or might be somewhat slower (e.g., for copper wire).

---
Tags: computer-networks
---


# Question
Title: Finding subset such that one sum is more than target and another sum is less
Consider the following problem: Given positive integers $a\_1,\ldots,a\_n,b\_1,\ldots,b\_n,A,B$, does there exist a subset $S$ of $\\{1,\ldots,n\\}$ such that $\sum\_{i\in S}a\_i\geq A$ and $\sum\_{i \in S}b\_i\leq B$?

Is this problem NP-hard? I'm thinking there is possibly a reduction from the subset-sum problem, but here there are two lists, and the conditions are inequalities rather than equalities, so I'm not quite sure how to start.

Another remark is that if the condition is just $\sum\_{i\in S}a\_i\geq A$, then it would be easy because we can check the sum of the whole subset.

# Answer
Consider what happens if you set $a\_i=b\_i$ for all $i$. I expect you should be able to take it from there...
> 0 votes

---
Tags: complexity-theory, reductions, np-hard
---


# Question
Title: Finding an automaton with a given number of states
> Define an NFA with 4 states that is equivalant to the following Regular Expression. $(01 + 011 + 0111)^\*$.

My main problem is that to check for a string of length 4 (`0111`) I need at least 5 states to begin with. So to my (novice) little brain the question seems wrong.

# Answer
Hint: for 0111 you need 4 transitions (one for each input letter). If you have a sequence of 5 separate states (which is probably your first try), than you will have 4 transitions between them. However, if you have 4 states connected in a *circle*, you will also have 4 transition between them...
> 2 votes

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


title: weighted subset exchange question

text:
# Question
Title: weighted subset exchange question
Assume there is a set {1,...,n} of person. For each person i, a set $A\_i$ of items are available for exchange. A is the set of all items. The value of item j to person i is $v\_{ij}$ and assume all values are positive integers. The question is, does there exist a pair of person who can both make profit by exchanging some of their items in $A\_i$.Formally:$\exists$ i and i' and $S\_i\subseteq A\_i$ and $S\_{i'}\subseteq A\_{i'}$ such that $\sum\_{j\in S\_i} v\_{i'j}\>\sum\_{j\in S\_{i'}} v\_{i'j}$ and $\sum\_{j\in S\_{i'}} v\_{ij}\>\sum\_{j\in S\_{i}} v\_{ij}$ I'm not sure whether this question is NP-Complete or there exists a polynomial-time algorithm?

# Answer
> 0 votes
It looks like your question can be written formally

> $\exists i,j\in\\{1,..,n\\}\\:\exists S\subseteq A\_i\\:\exists T\subseteq A\_j : (\sum\_{y\in T}v\_{i,y}\>\sum\_{x\in S}v\_{i,x})\land (\sum\_{x\in S}v\_{j,x}\>\sum\_{y\in T}v\_{j,y})$

If the above is true, then persons $i$ and $j$ benefit from swapping items from $S$ and $T$.

This is hard to decide. Here is an idea for a reduction. We simplify things by assuming there are only two persons $P\_1$ and $P\_2$, that $P\_1$ has just coins and banknotes in $A\_1$, that $P\_2$ has just $A\_2=\\{x\\}$ and that they would both profit if $P\_1$ can buy item $x$ at price $V$ from $P\_2$. This is because $v\_{1,x}-1=V=v\_{2,x}+1$, i.e., $P\_1$ thinks that by paying $V$ for $x$ he wins $1$, while $P\_2$ thinks he wins $1$ by selling $x$. They will trade iff $P\_1$ can find some coins and notes in his $A\_1$ that add up to $V$ exactly (we assumes that $P\_2$ only has $A\_2=\\{x\\}$ so he cannot make any change). NB: the coins and notes are items $c\in A$ with $v\_{1,c}=v\_{2,c}$, their face value is the same for both persons.

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


# Question
Title: Help understanding this algorithm that's supposed to solve the critical section problem through mutual exclusion
Our professor gave us the following algorithm that's supposed to solve the critical section problem. I'm guessing the code is just pseudocode so I'm not trying to focus on the strange syntax and just trying to understand what it does.

```
 Main
  begin
   process_number=1;
   parbegin
    process1;
    process2;
   parend;
  end

Process1;
  begin
   while process_number=2 do;
   critical_section1;
   process_number=2;
   other_stuff;
  end;

Process2;
 begin
  while process_number=1 do;
  critical_section2;
  process_number=1;
  other_stuff;
 end;

```

After the code he says the following:

"Algorithm Guarantees mutual exclusion.

Price is high: P1 must go first, so if P2 is ready to enter its critical section, it must wait.

When P1 enters and leaves its CS, P2 must go next even P1 is ready, and P2 is not ready.

If one of the processes is terminated, then eventually the other will not be able to proceed"

I don't even know what's going on. My best guess is that since process 1 and process 2 are running concurrently, and the variable process\_number is originally equal to 1, Process 1 is going to stop at the condition (`while process_number = 2`). But for process 2 the condition (`while process_number = 1`) is true, so...it will `do` whatever lines of code follow it. But the lines of code that follow it are (`critical_section2;`) and why in the world would it be running critical\_section2 if it the variable `process_number = 1` is true. I..honestly have no idea what my professor was trying to get across in this confusing code.

# Answer
> 1 votes
Note that the `while` bodies are empty, i.e., if the condition is false, they just fall through to the next line.

Horrible, horrible code; extremely restrictive (taking turns!), and very inefficient (busy waiting), if you ask me.

# Answer
> 1 votes
## Assumptions

Consider a Petri Net model of the algorithm, based on the pseudo code (“Help”, 2015) and the following assumptions:

1. Main executes first.
2. process1; in Main is actually a call to schedule the execution of Process1.
3. process2; in Main is actually a call to schedule the execution of Process2.
4. When Main ends, it “waits” and Process1 and Process2 continue to their end. “End” does not mean Main, Process1 or Process2 stops executing. After Process1 or Process2 reaches its end, it is rescheduled to start again.
5. The actual start and restart times for Process1 or Process2 are stochastic. The lengths of time for Process1 and Process2 to complete their tasks are also stochastic.
6. Each of Process1 and Process2 runs on its own thread. Both threads run on a single processor. The processor can run one (and only one) thread at a time.

## Net Model and Pseudo Code

Petri Net Model of Main:

Petri Net Model of Process1:

Petri Net Model of Process1:

Petri Net Model of Algorithm:

Petri Net Model of Algorithm with (Abnormal) Termination

## Notes

In the “Petri Net Model of the Algorithm with (Abnormal) Termination”, each process can terminate before it begins or after it ends, while it is performing its critical section, or while it is doing other stuff.

For the PDF version of this reply, The “Petri Net Model of the Algorithm” and the “Petri Net Model of the Algorithm with Termination” are interactive, dynamic diagrams. Stepping through the algorithm using an interactive, dynamic diagram may help in understanding some properties of the algorithm.

The Petri Net model of the algorithm for Process1 and Process 2 is similar to Figure 14 on page 163 of Petri’s “General Net Theory” (1977); an interactive, dynamic version of the figure is also available.

## References

Petri, C. A. (1977). General Net Theory. Computing System Design: Proc. of the Joint IBM University of Newcastle upon Tyne Seminar, Sep., 1976 / Shaw, B. (ed.) --- University of Newcastle upon Tyne, 1977, p. 131-169. Retrieved on Mar. 15, 2013 from http://www.informatik.uni-hamburg.de/TGI/mitarbeiter/profs/petri/doc/GeneralNetTheory.pdf.

---
Tags: operating-systems, concurrency, mutual-exclusion
---


# Question
Title: Modeling $(x > 0 \wedge y > 0) \Leftrightarrow z > 0$ in a linear program: impossible?
In this question, we see how to model boolean logic in $0 - 1$ ILPs. Moving to a relaxation, modelling $(x \> 0 \vee y \> 0) \Leftrightarrow z \> 0$ with $x,y,z \in \[0,1\]$ with linear constraints is quite simple:

$$z \geq x\\ z \geq y\\ x+y \geq z$$

However, if I want to replace $\vee$ with $\wedge$ in that statement, I'm unable to do this. Can this be done? It seems to me this might imply something about quadratic problems in general, but I'm not familiar with that problem, and I can't prove that it can't be done either. Assuming we could linearize this $\wedge$ relation, would this imply something like polynomial-time equivalence between LP and QP?

Thinking about it geometrically, the set $\\{(x,y,z) \in \[0,1\]^3: (x \> 0 \wedge y \> 0) \Leftrightarrow z \> 0\\}$ is equivalent to the unit cube $\[0,1\]^3$ minus the three faces that intersect the origin, but plus the two edges that emanate from the origin that satisfy $z=0$. This is neither an open nor a closed set. I don't know whether that tells us anything about the applicability of linear programming, but considering I've never come across a linear program with strict inequalities, I suspect it might be a problem.

In fact, strict inequalities can't be allowed in linear programs since

$$\min x\\ x\>0$$

has no solution.

---

@KlausDraeger pointed out that the above constraints and the logical statement with $\vee$ aren't equivalent, and for reasons similar to those that apply to the case with $\wedge$, I suspect we can't find equivalent constraints. The subset of $\[0,1\]^3$ defined by $(x \> 0 \vee y \> 0) \Leftrightarrow z \> 0$ is also neither open nor closed. I overlooked this because for the purposes I had in mind, it seemed to suffice that the linear constraints implied the truth of the logical statement - which isn't the case, I need equivalence between the set of linear constraints and the logical statement.

(Just in case someone is interested, there is a simpler constraint that also implies the truth of $(x \> 0 \vee y \> 0) \Leftrightarrow z \> 0$, and that's $0.5(x+y) = z$; I could not find a set of constraints equivalent to the logical statement, though.)

# Answer
> 4 votes
A linear program consists of a finite collection of inequalities of the form $\sum\_i a\_ix\_i \leq b\_i$. Each such inequality defines a closed convex set, and so their intersection defines a closed convex set. Any domain which is not closed and convex thus cannot be represented using linear programming constraints.

---
Tags: linear-programming, quadratic-programming
---


# Question
Title: Why doesn't the Needleman-Wunsch algorithm find solutions that begin with a gap?
I have implemented in C++ the Needleman-Wunsch algorithm for pairwise sequence alignment using the following scores:

* +1 for match (regardless of base)
* -1 gap penalty
* -1 for a mismatch.

Given two sequences of length $m$ and $n$ the algorithm then generates the $mn$ search space row by row as per the algorithm's specifications and backtracks generating all solutions of maximum score. Given two sequences in which the first two letters overlap ie:

```
GCATGCU

```

and

```
GATTACA

```

the algorithm succesfully generates all the alignments of maximum score. Howeever, given two sequences of the kind:

```
ACTGCUGCTA

```

and

```
UGCTAATCGU

```

the algorithm fails to find any of the solutions that begin with a gap in sequence 1 or 2, thus failing to find the optimal solution as well:

```
ACTGCUGCTA-----
-----UGCTAATCGU

```

Once I add the letter A to the second sequence the algorithm once again has no problem finding the optimal solution (which in this case begins with a match and not a gap)

```
ACTGCUGCTA-----
A----UGCTAATCGU

```

Could someone explain to me why the algorithm doesn't find this subset of solutions and perhaps how I can modify it to find these solutions as well?

# Answer
Your optimal alignment seems to be an optimal *local* alignment, the best substring match. Needleman-Wunsch is for *global* alignment. With the simple program by Eddy that you can find on the internet I have determined a global score of 0. This is better than the gobal score you get: -5 (for 10 gaps and 5 matches).

```
Sequence X: GCATGCU
Sequence Y: GATTACA
Scoring system: 1 for match; -1 for mismatch; -1 for gap

Dynamic programming matrix:
             G    A    T    T    A    C    A
        0   -1   -2   -3   -4   -5   -6   -7
   G   -1    1    0   -1   -2   -3   -4   -5
   C   -2    0    0   -1   -2   -3   -2   -3
   A   -3   -1    1    0   -1   -1   -2   -1
   T   -4   -2    0    2    1    0   -1   -2
   G   -5   -3   -1    1    1    0   -1   -2
   C   -6   -4   -2    0    0    0    1    0
   U   -7   -5   -3   -1   -1   -1    0    0

Alignment:
X: GCA-TGCU
Y: G-ATTACA
Optimum alignment score: 0

```
> 4 votes

---
Tags: dynamic-programming, backtracking, bioinformatics
---


# Question
Title: Why does if A is a spanning tree which doesn't have $e_1$ then $A\bigcup\{e_1\}$ has a unique cycle?
I am studying the algorithm of Sollin and we recently studied a lemma:

Let be G a graph which values are diffferent on the edges.

* We sort the edges $e\_1,e\_2,...e\_m$ such as $v(e\_i)\<v(e\_j)$
* Every tree of minimal value has at least $e\_1$ et $e\_2$

> **Proof**
>
> let be A a spanning tree which doesn't have $e\_1$
>
> *$A\bigcup\\{e\_1\\}$ has a unique cycle*
>
> let be $e\_i \in$ cycle, $e\_i\ne e\_1$ then $A\bigcup\\{e\_1\\}-\\{e\_i\\}$ is a tree which value is \< $v(A)$ because $v(e\_i)\>v(e\_1)$

I don't understand why would $A\bigcup\\{e\_1\\}$ would have a unique cycle? Do you have a justification? A graphical example?

# Answer
The proof outcomes from the definition of a *tree* \- they are non-oriented, **connected** graphs with no cycles.

Lets assume that there's no cycle after adding $e1$. Let $e1$ = $(v1, v2)$. This means that before adding $e1$ there wasn't any path that connects $v1$ and $v2$, which contradicts to the connectivity of the spanning tree. On the other hand, if there *was* a path the connects $e1$ and $e2$ (which didn't include $(e1, e2)$) then adding this very edge will result into a cycle, which again contradicts to the definition of a tree.
> 1 votes

# Answer
In a tree, there is exactly one path between any pair of vertices. When you add edge `e1` you close that unique path to form a unique cycle.
> 2 votes

---
Tags: proof-techniques, trees, spanning-trees
---


# Question
Title: Is Turing machine a programmable machine or Is it like a fixed program computer?
We all know Random Access Machine (RAM) models are programmable machines. We can program a same machine for different problems with the help available instruction set. But in the case of Turing machines,we give full description of TM including transition table (which is equivalent to stored program in RAM model). So should it be considered like a stored program computer? Because for two different languages L1 & L2 we give two different TMs T1 & T2. We never describe two different transition table for same TM.

# Answer
Your regular stored program computer could be compared to the Universal Turing Machine (UTM) in that it *can be seen* as a multipurpose device. Any concrete UTM, nevertheless, still accepts only one *base level* language, as does the computer that you are using right now. "On top" of that language, other languages can be encoded, and the fact that programs/machines can be processed as data is what gives computers an enormous range of applications, or even "incarnations", which we have just begun exploring.

To answer your question directly: a TM that is programmable is also "fixed", depending on how you see it. Conversely, a machine doesn't have to be as powerful as the UTM to be considered programmable, in some way. In fact, many (very) useful languages are not Turing equivalent.

Regarding computational languages/machines, the notion that there would be something like a "proto-language", or "proto-machine" is misleading. The mythology that has been built around the general-purpose computer obscures its candid nature. The *Universal* in "Universal Turing Machine" should not be equated to *absolute*. It is a proposed definition of universality, mathematical in nature, which has been ever since reinstated, repeatedly, in so many ways that it is impossible to describe exhaustively.
> 7 votes

---
Tags: turing-machines
---


# Question
Title: What is an efficient algorithm to see if a set of nodes ultimately depend on a certain node in a DAG?
Hopefully this question makes sense. Basically, given a DAG, a set of nodes *A*, and another node *b*, I'd like to know if node *b* is an ancestor of any of the nodes in *A* in that graph.

This is my current implementation:

```
def is_ancestor(graph, A, b):
    nodes_visited = set()
    frontier = list(A)
    while frontier:
        node = frontier.pop()
        if node not in nodes_visited:
            if node == b:
                return False
            nodes_visited.add(node)
            # add immediate predecessors to the frontier
            frontier.extend(graph.predecessors_iter(node))
    return True

```

However, in the worst case this is `O(|graph|)`, and this would be a function I would need to call very often, so I'm wondering if I'm missing anything that might make this run faster, preferably without requiring quadratic memory, because then I could just store everything and get `O(1)`.

# Answer
> 2 votes
As far as I know, it is an open problem whether one can do significantly better (in an asymptotic sense).

This is known as the reachability query problem for DAGs. You want to do some precomputation, after which you can answer queries of the form Reachable$(u,v)$ (which should return true if $v$ is reachable via some path from $u$, i.e., if $u$ is an ancestor of $v$).

There are two trivial algorithms:

* With no precomputation, you can answer each reachability query in $O(|V|+|E|)$ time by just using DFA.
* With a $O(|V| \cdot |E|)$-time precomputation and $O(|V|^2)$ space, you can precompute the transitive closure of the DAG and then answer each query in $O(1)$ time.

Apparently it is an open problem to do significantly better than this: e.g., to precompute something with less than $O(|V|^2)$ space that enables you to answer reachability queries efficiently. See https://cstheory.stackexchange.com/q/25298/5038 and https://cstheory.stackexchange.com/q/21503/5038.

---
Tags: graphs, partial-order, dag
---


# Question
Title: Shortest continuous path between shapes without passing thru other shapes, in a specific order?
I have the following points, shapes, and paths. I would like to find a path that goes through all of them:

I want a path that first traverses the circle, then traverses the square, then traverses the star in the middle, in that order.

It's simple to go to the circle from the bottom left and around it, hitting each point. However, the second shape (the square) is in the top right corner, so I have to go around the star (so I don't cross it) and traverse the square. Finally, I go to the middle, hit each of the points of the star and done. Once that is done, going backwards is pretty easy.

This is an easy example. In my situation, though, there can be hundreds of shapes in between each of them and I have to go to each shape in the order they are stated.

How do I calculate a path that avoids a particular shape (e.g., the star)? I'm not sure what algorithm to look for. Is it a Travelling salesman problem? A\*?

The shapes are defined on a grid. This is what I mean:

"1" means the path must go thru here and "0" is empty space which can be used to get to from one place to another.

# Answer
The key step is: get from point $Q$ to shape $S$, while avoiding shape $A$. For instance, point $Q$ might be the last point you visit on the circle, $S$ might be the square, and $A$ might be the star.

This can be solved using breadth-first search or A\*. The vertices are the grid points labelled "`0`". You star the search at point $Q$, and try to find the shortest path to some point on $S$ (while at each step you only go through squares marked `0`). You can solve this with either BFS or A\*: BFS is simpler to implement, A\* will run faster.

---

If you additionally want to find the *shortest* path through all of the shapes (something that's not stated in the question), then you can fo the following: for all points $Q$ in shape $S\_1$, and all points $R$ in shape $S\_2$, calculate the shortest way to get from $Q$ to $R$ while avoiding shape $A$. Then add these as edges to a directed graph (where the length of the edge $Q\to R$ corresponds to the length of the shortest such path). Also add edges $R \to R'$ for each pair of points $R,R'$ in the same shape where you can enter the shape via $R$ and exit via $R'$. Finally, you can compute the shortest path in this directed graph.
> 1 votes

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


# Question
Title: Converting a digital circuit to two layers of OR and AND gates
The other day someone mentioned to me that you could take an arbitrary digital circuit which mapped N input bits to M output bits, and replace it with a layer of OR gates and a layer of AND gates. I believe he said there would be 2^N ANDs and ORs each. I haven't been able to find any more information about this though.

Is this true?

And are there similar techniques for say using only XOR and AND gates?

# Answer
> 2 votes
Yes, it's true. You can use conjunctive normal form to express the circuit in two layers, where the first layer has OR gates and the second layer consists of $m$ (multi-input) AND gates. However, there's a catch: you have to have a way to complement (negate) some of the inputs to the OR gates for free. If you want to count the OR gates as a separate layer, then it takes three layers; if you imagine that your OR gates actually allow you to complement any subset of their inputs (e.g., the gate can compute $x \lor y$, $x \lor \neg y$, $\neg x \lor y$, or $\neg x \lor \neg y$), then it's just two layers.

Or, you can use disjunctive normal form to build a two-layer circuit where the first layer uses AND gates and the second layer contains $m$ (multi-input) OR gates. Again, the same catch applies: you need to be able to complement the inputs to the AND gates "for free".

You can use disjunctive normal form to build a circuit where at most one input to any OR gate will ever be true at a time. This means that you can replace the OR gate with an XOR gate without changing its functionality. Therefore, yes, you can built a two-layer digital circuit where the first layer has only AND gates and the second layer has only XOR gates -- assuming you can complement some of the inputs to the AND gates for free.

For "XOR-of-ANDs", you can actually write any N-to-1-bit circuit as an XOR of ANDs, without any complementation at the input, if you allow the final XOR to optionally include an additional input that's held at the constant 1 (or, equivalently, if you allow the final gate to be either a XOR or a NXOR). In particular, given any boolean function $f:\\{0,1\\}^N \to \\{0,1\\}$, you can write it as a multivariate polynomial $f(x\_1,\dots,x\_N)$ modulo 2. Now $x^2=x \pmod 2$, so since everything is modulo 2, that means that you can eliminate all powers of two or higher: every multivariate polynomial can be expressed in the form

$$f(x\_1,\dots,x\_N) = \sum\_S c\_S \prod\_{i \in S} x\_i \pmod 2,$$

for some constants $c\_S$, where $S$ ranges over all subsets $S \subseteq \\{1,\dots,N\\}$. (For example, we might have $f(x\_1,x\_2,x\_3) = x\_1 x\_2 + x\_2 x\_3 + x\_3 + 1 \pmod 2$ as an example of such a polynomial.) Now note that product modulo 2 is AND, and sum modulo 2 is XOR, so we get a XOR-of-AND representation of any boolean circuit.

As your colleague mentioned, in the worst case these circuits might need approximately $2^N$ gates, so this can be highly inefficient in some cases.

I don't know if it is possible to write every circuit as an AND-of-XORs (with some complements or constants somewhere).

# Answer
> 2 votes
D.W. handled the other cases, so I'll handle the case of AND-of-XORs, but first I'll show how the other cases are elaborated. For the XOR-of-ANDs, we remark that $$f(x\_1,\dots,x\_n) = g(x\_1,\dots,x\_{n-1})\oplus h(x\_1,\dots,x\_{n-1})\land x\_n$$ with $g$ and $h$ defined as

$$ g(x\_1,\dots,x\_{n-1}) = f(x\_1,\dots,x\_{n-1},0) $$

$$ h(x\_1,\dots,x\_{n-1}) = f(x\_1,\dots,x\_{n-1},0)\oplus f(x\_1,\dots,x\_{n-1},1) $$

applying this recursively and simplifying the result gives you the XOR-of-AND representation. A similar decomposition is used for then OR-of-ANDs:

$$f(x\_1,\dots,x\_n) = (f(x\_1,\dots,x\_{n-1},0) \land \bar x\_n) \lor (f(x\_1,\dots,x\_{n-1},1) \land x\_n)$$

And applying De Morgan's law to that give us the OR-of-ANDs:

$$\overline{f(x\_1,\dots,x\_n)} = (\overline{f(x\_1,\dots,x\_{n-1},0)} \lor x\_n) \land (\overline{f(x\_1,\dots,x\_{n-1},1)} \lor \bar x\_n)$$

in other words:

$$f(x\_1,\dots,x\_n) = (f(x\_1,\dots,x\_{n-1},0) \lor x\_n) \land (f(x\_1,\dots,x\_{n-1},1) \lor \bar x\_n)$$

You can not decompose an arbitrary function as a AND-of-XORs or a OR-of-XORs (applying De Morgan's law show that if you have one you have the other), even when adding inversers at arbitrary places. It is easy, if somewhat tedious, to convince yourself of that by trying to do so for the 3-variable function $f(x,y,z)=((x \land y) \land \bar z) \lor ((x \lor y) \land z)$ and looking at the truth tables for the six one-variable functions $x,y,z,\bar x, \bar y, \bar z$, the six unique two-variable one ($x \oplus y, x \oplus z, x \oplus z$ and their negation), the three-variable function $x\oplus y \oplus z$ and its negation, and see that you can't build the desired one (only the constant 1 has 1 in all the desired places and to build a function by combining sub-functions with ANDs, all the sub-functions must have 1 at the desired positions in their truth table).

A reference: D. Knuth, *The Art of Computer Programming*, volume 4A, *Combinational Algorithms part 1*.

---
Tags: boolean-algebra, digital-circuits
---


title: Where is the reorder buffer (ROB)?

text:
# Question
Title: Where is the reorder buffer (ROB)?
I just wonder where the ROB is in. Is ROB in the memory or cache or where??

# Answer
Somewhere which is not part of the user accessible memory (i.e. not in the main memory nor in the cache -- that would be too slow, one of the main use of OOO is to hide part of the latency of main memory and low level caches). Probably in register files inside the processor or possibly in the same kind of memory cells used for L1 caches (but not in the L1 caches). Modern processors have lot of internal state which is not directly accessible.
> 6 votes

---
Tags: computer-architecture, memory-hardware
---


# Question
Title: Relationship between an NP-hard problems with the subsets of them?
I am writing a paper. I have a problem and I want to prove that it is an NP-hard problem. However, for simplicity, I select a subset from my problem to prove that it is an NP-hard problem. Although I think that it is reasonable that if a subset of problem is NP-hard, it result in the problem being NP-hard, but I think writing this sentence in a paper need a reference. I will be thankful if anyone helps and gives me a reference for it.

...................... More explanations : My problem includes *N* boxs, B(1) through B(N). Every box B(i) has a size called t(i) and t(i)\<=t(i+1). Now, to prove that my problem is NP-hard, I have considered a subset of my problem such that there are arbitrary number of boxes with size t(N). And for this subset I have proved that my problem is NP-hard, as a result the problem is NP-hard.

> is this an acceptable assumption?

# Answer
I don't think that is valid. For example, every language including every language in NP is a subset of $\Sigma^\*$, but $\Sigma^\*$ is not NP-hard.

To prove NP hardness, polynomial time reduce an NP complete language such as 3-SAT to it.
> 1 votes

# Answer
It is not true that an arbitrary superset of a NP-complete language will also be NP-complete. In other words, just because your problem is a special case of an NP-hard problem doesn't necessarily mean your problem is NP-hard; it might be that your special case is much easier than the other cases of the NP-hard problem. For instance, 2SAT is a special case of 3SAT; 3SAT is NP-complete, but 2SAT is not (believed to be) NP-complete.

However, there are some specific conditions where this kind of inference *is* valid. For example, take Hamiltonian Path ($L\_1$) and Longest Path ($L\_2$), two NP-complete problems. Hamiltonian Path is a special case (subset) of Longest Path: we have $L\_1 \subseteq L\_2$. But one can say more about the relationship between Hamiltonian Path and Longest Path: we have $L\_1 = L\_2 \cap L\_3$ where $L\_3 \in P$. From the fact that $L\_1$ is NP-complete and $L\_2$ is in NP, we can infer that $L\_2$ is NP-complete too.

In general if $L\_2$ is in $NP$ and $L\_3$ is in $P$ and $L\_1 = L\_2 \cap L\_3$ is NP-complete, then $L\_2$ is NP-complete. However, the requirement that $L\_3$ be in $P$ is essential; the corresponding statement doesn't hold if you allow $L\_3$ to be arbitrary (i.e., if you allow $L\_1$ to be an arbitrary subset of $L\_2$).
> 0 votes

# Answer
Take any NP complete language, concatenate "0" at the end of each of its words the resulting language is still NP complete... At the same time it is a subset of the set of all strings that end with "0" (this is different than being a subset of the Kleene closure which is a trivial case)

The set of all strings ending with "0" though is decidable in Polytime.

This serves as an example where the subset is NP complete where as the set which contains it is in P.
> 0 votes

# Answer
Your question is worded very awkwardly, but I think what you're asking is "If we have a language $\mathcal L$ and we know there exists $\mathcal L' \subset \mathcal L$ such that $\mathcal L'$ is $NP$-complete, is $\mathcal L$ $NP$-complete as well?"

Certainly. We know there exists an $NP$-complete language $\mathcal R$ that is polynomial-time reducible to $\mathcal L'$, say via the reduction $f : \mathcal R \to \mathcal L'$. Then if we simply extend the codomain to $\mathcal L$, we get the polynomial time reduction $f' : \mathcal R \to \mathcal L$, and by definition $\mathcal L$ is $NP$-complete.
> -2 votes

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


# Question
Title: Confusion about data types, compilers, hardware data representation and static vs dynamic typing
I am trying to understand static vs dynamic typing, but am really struggling to see how everything fits together.

It all starts with data types. As far as I understand, data types are quite abstract notions, which exist 'in' compilers in order to categorise data so that the operations on various types of data can be validated (i.e. in an attempt to stop you adding a string to an integer), and in order to generate the right machine code for the hardware interpretation of the value. I.e. say we have the following:

```
int myInt = 5;
char myChar = '5';

Console.WriteLine(myInt);
Console.WriteLine(myChar);

```

Both would ultimately write a five to the console window, but, since the representations in memory of integers and characters are different, the machine code which interprets the value in the memory location bound to the variable myInt, which takes that value and displays it on the console window, would be different to the machine code for myChar. Even though Console.WriteLine() 'does the same job', the different representations of five require different low level code.

So my question is this: if data types 'exist only in the compiler' - i.e. once the program has been compiled into machine code there is no knowledge of what type of data the value in a particular memory cell is (everything is just 1s and 0s) - then how can any type-checking be done at runtime? Surely there is no concept of data types at run time? So surely dynamic typing can't be anything to do with type-checking occurring at run time?

Where is my understanding going wrong, and could somebody please explain static and dynamic typing with respect to the argument given above? What is the big picture of what is going on?

I am trying to understand this for an essay, so references to books or online sources would be useful :) Thank you.

# Answer
First, you must be aware that computer science is full of terms which have multiple, related but conflicting definitions. The fact that two authors are using the same term such as "type" does not mean they are using the same definition and thus there may be inconsistencies if you are not careful when you try to combine different sources.

A type is a property attached to entities (values, variables, ...) which allow to know what operations are allowed on those things and what is the result of those operations (including the type of the result). That means that type determines the interpretation of the bits pattern representing a value, but that's not the only effect of types. It is common to introduce several types which gives the same meanings to bits patterns, just to prevent to use them in some context (an extreme example would be to have different types for X and Y coordinates to be sure they are not swapped at the wrong time).

A language may be:

* statically typed: an analysis of the program allows to know the type of an entity without the need to execute it (that is what you were thinking about). That is common for languages which are compiled.
* dynamically typed: value carries information about their type. Choices which need that information must be done at execution time, looking at the information attached to the value at hand. That is common for languages which are interpreted.
* untyped: operations assume that their arguments are correct (note that this is different from implicit conversions, implicit conversions tries to conserve a notion of value, in an untyped language that does not happen), there is no typing error (but an argument may be invalid and trigger an error) nor choice of behavior depending on types. Nowadays the more common languages which are untyped are the assembly languages. Historically languages like BLISS and BCPL were also in that class. The original TCL language was also in that class.

Note that it is quite common for languages to have aspects of several kinds. C++ for instance has a notion of static type which determines some things such as overload resolution, a notion of dynamic type which determines other things such as virtual function dispatch and reinterpret\_cast allows to circumvent the typing system and behave in an untyped way. A language may be defined in a dynamic way, as if the values carried the type information, but a compiler may analyze a program and remove part of the checks that would be needed and even remove the need to attach a dynamic type information on some values. And a language may have types (static or dynamic) but be used in an untyped way (Lisp variants often have a notion of dynamic type, but lists are also often used to represented everything not built-in).

> So my question is this: if data types 'exist only in the compiler'

I've tried to show that this assumption is false. It may be true for some languages, but others attach type information to values (and that's the case for object oriented one -- I've in the past described OO as a way to get the benefits of dynamic typing without dropping completely the benefits of static typing --, if there is a dynamic dispatch based on type, you need to have dynamic type information). Note that the information may be part of the value as a tag, as a pointer to a type-descripting data structure (the vptr of common implementation of C++), or even implicitly (that area of memory is used only to store values of that type, the bits don't have to show what type is the value, the place where they are is giving the information).

References

*Types and Programming* by B. Pierce (but IIRC it is strongly oriented towards static typing)

*Concepts, Techniques, and Models of Computer Programming* by P. van Roy and Seif Haridi, wider of scope but also more oriented towards dynamic typing and may also be useful to organize things before a reference such as B. Pierce which is more concerned about just typing issues.
> 4 votes

---
Tags: compilers, type-checking, typing
---