# Question
Title: Where am I wrong?: "countability" and "recursive enumerability"
I have a a few fundamental doubts in recursive enumerability and countability and below, I have written what I understand them to be with proofs. But there are contradictions at the end. What is wrong with the statements/proofs i have made?

Countability (C=Countable): A set $X$ is C when a bijection exists between the set of natural numbers and the set $X$

Recursive Enumerability (RE= Recursively Enumerable): Say set $S'$ is a subset of another set $S$. When there exists a turing machine with alphabet $A$ (where $S$ is a subset of $A^\*$) which halts if the input to it belongs to the set $S'$ and does not halt if the input belongs to $S-S'$ then I say that the set $S'$ is recursively enumerable (given the fact that inputs comes only from the set $S$ and not from $A^\*-S$ hence the latter will not concern us.) I have referred to the book "Elements of the theory of Computation" by Papadimitrou for this definition, though the introduction of an alphabet A is my own addition to make things more firm

Now I will prove 2 statements:

1. if a set $X$ is RE then it is C
2. if a set $X$ is C then it is RE

Hence proving 3. RE iff C

I will prove 2 first.

I can write a Turing Machine $M$ which when asked to check if an element $x$ belongs to $X$ or not will follow the algorithm:

There exists a mapping from the set of natural numbers to $X$ call it $f$. $M$ can search for $x$ (like a linear search algorithm running on $X$) starting from $f(1)$ going to $f(2)$... and it keeps going till it finds $x$. By this method, $M$ terminates iff $x$ belongs to $X$.

The behaviour above proves that $X$ is RE

Now I prove 1- Given a Turing Machine $M$ exists which halts iff $x$ belongs to $X$

I can construct a bijective map from the set of naturals to $X$ as follows: To map $x$ (given it belongs to $X$) , we run it as input against $M$. I take the concatenation of all configurations (Configuration=tape head position+tape content+state) of $M$ which it goes through from the starting of a computation to the end and decode that string as a natural number. It will be unique.

Hence 1. is proven and so is 3.

But then I find certain resources on the internet which tell me that enumerability and recursive enumerability are different things. How is it possible? Furthermore- We know that the power set of a countably infinite set is uncountably infinite. If $X$ was countably infinite, it would be RE (see 2.). Now we know that the subset of a set which is C is also C. Hence all subsets of $X$ would be C hence they would be RE. Now there would be an uncountable number of RE sets.

Now for each RE set, we can write a turing machine (with appropriate halting behaviour) which can be encoded as a natural number implying that the "set of all RE sets" must be C. This contradicts the conclusion of the previous paragraph.

Where exactly am I wrong? Thankyou in advance!

# Answer
Your algorithm for recursively enumerating any given set doesn't work since the bijection between a countable set $X$ and the natural numbers can be arbitrarily complicated. For example, consider the following set $X$: $$ X = \\{ P : \text{the program coded by $P$ doesn't halt on the empty string as input} \\}. $$ The set $X$ is countable: there are only countably many programs. However, there is no computable bijection between $X$ and the natural numbers, since otherwise RE=coRE (as your argument shows; $X$ is coRE-complete).

Here is a more tangible example of a countable set for which there is no computable bijection: $$ Y = \\{ 2P : \text{program $P$ halts on the empty string} \\} \cup \\{ 2P+1 : \text{program $P$ doesn't halt on the empty string} \\}. $$ If there was a computable bijection between $Y$ and the natural numbers, then you could solve the halting problem (how?).
> 6 votes

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


title: Does PETSc really give speedup?

text:
# Question
Title: Does PETSc really give speedup?
I searched for linear solver libraries and found out about PETSc library which is considered to be a powerful and useful library. PETSc consists of implementations of various iterative methods with preconditioners and sparse matrix storing methods. All the methods are realized sequentially and in parallel using MPI.

I was very glad for the creators of PETSc. I downloaded and then installed it. However, when I started reading user's guide I encountered the following text:

```
PETSc should not be used to attempt to provide a “parallel linear solver” in an otherwise sequential
code. Certainly all parts of a previously sequential code need not be parallelized but the matrix
generation portion must be parallelized to expect any kind of reasonable performance. Do not expect
to generate your matrix sequentially and then “use PETSc” to solve the linear system in parallel.

```

I was surprised! *Did PETSc developers really parallelize only the matrix generating part? What is a benefit of using PETSc as a parallel solver if the linear system solving part runs sequentially*?

# Answer
You misread the text. The authors of PETSc are just telling you that you can't avoid Amdahl's law.

They have done their best to parallelize every aspect of the linear solver. But a real program is not *just* a call to a linear solver. First *you* generate a matrix and then you pass the matrix to the linear solver. If *your* matrix generator is slow, your whole program will be slow.

For example, suppose your original program spends 1000 seconds generating the matrix $A$ and vector $b$ and then you call a linear solver. Your old (sequential) linear solver took 1000 seconds to find $x$ such that $Ax = b$. Now you replace your old sequential linear solver with PETSc. Suppose the PETSc authors did such a good job that the PETSc parallel linear solver finds $x$ in just *1* second! Now how long does it take your program to run? 1001 seconds. You got less than 2x speedup! *You* need to do some work on your matrix generation code if you want to get a better speedup.

Pretty much the authors of PETSc are just telling you that a parallelized linear solver library is not a magic bean.
> 7 votes

---
Tags: parallel-computing, linear-algebra
---


title: Quantum computing roadmap

text:
# Question
Title: Quantum computing roadmap
I have to create a roadmap for the quantum computing technology. Looking around I found the timeline on wikipedia that is pretty wide but does not highlight the key events in quantum computing research neither sets the possible future for research.

Could somebody help me to define which are key events in the quantum computing fields? When (and why) we started to explore this technology, for which milestones we passed through and (maybe) what we can set as future milestones?

# Answer
This Quantum Information Science and Technology Roadmapping Project is a very detailed roadmap prepared under ARDA (Advanced Research and Development Activity) around ~2004 with further refinements. Here is the introduction/overview. It had a panel of about 19 elite academic scientists/experts.

For a completely contrasting recent overview/review on progress to date/future prospects see this \[controversial\] paper State of the Art and Prospects for Quantum Computing, M. I. Dyakonov (2012).
> 13 votes

---
Tags: reference-request, quantum-computing
---


# Question
Title: 1/r attractive force by cellular automaton
Does there exist a cellular automaton (in 2D) which simulates a $1/r$ force between particles?

More specifically, I would like to know whether it is possible, with strictly local update rules, to have two objects (defined within the model) attract each other with a $1/r$ force, where $r$ is the distance separating the objects. This would in particular entail an acceleration of the object (particles) as they get closer together.

More generally, can long range attractive forces between objects (blobs) be simulated in a cellular automaton setting with strictly local rules?

# Answer
If by "simulate" you mean something like "generate a picture of what the dynamics would be under such a force," then the answer to your question is *yes*: there exist universal cellular automata (including Conway's original Game of Life rule set).

If, however, you're asking about whether our universe can be explained in terms of strictly local update rules, then your question is still open. Konrad Zuse was one of the first to explore this question explicitly in terms of CA; see Wolfram, Schmidhuber, or t'Hooft for more recent work.
> 3 votes

# Answer
this is a very significant research question & there is a more general question here that is studied by some. the deeper question is "to what degree can CA(-like) rules reproduce the laws of physics". the larger question is a very important open question with large amounts of speculation and research on the subject, but unfortunately conventional scientific/physics wisdom considers it a more fringe area of modern physics. my understanding is that your specific question is basically open also.

regarding your question in a more general way, here are links on many closely related themes, having researched this thread/area recently:
> 1 votes

---
Tags: simulation, cellular-automata
---


# Question
Title: Worst case scenario in binary search tree retrieval
Well, i have a binary search tree $T$ that is equilibrated by height witch has $2^d+c$ nodes ($c\<2^d$). What is the number of comparisons that will occur in the worst case scenario, if we ask whether $k\in V(T)$ and why does it arise?

# Answer
> 2 votes
Hint: If the tree has height $h$ then the worst number of comparisons is ...? If the tree is "equilibrated by height" (I guess *balanced*) and has $n$ nodes then its height is ...?

# Answer
> 0 votes
A balanced tree of height 0 has one node. A balanced tree of height 1 has three nodes. A balanced tree of height 2 has seven nodes. A balanced tree of height $h$ has $2^{h+1}-1$ nodes. Looks familiar?

---
Tags: graphs, search-trees, search-problem
---


# Question
Title: Is the following langauge in $P$ or $NPC$
Assuming $P \neq NP$ Is the following langauge in $P$ or $NPC$:
$L=\\{\langle\phi\rangle\mid\phi$ is a 3CNF formula with an assignment satisfying at least half of the clauses$\\}$

The first thing I tried to do is to find a 3CNF formula $\phi$ such that $\phi \notin L$ and I haven't managed to do so. Is it possible that simply all 3CNF formulas have such an assignment (and so the problem is in $P$) or am I missing something ?

# Answer
> 4 votes
Hint: Take a valuation $v$ satisfying less than half of the clauses. What about $\bar{v}$ the valuation such that $\bar{v}(x)=\neg v(x)$?

---
Tags: complexity-theory, time-complexity, np-complete, satisfiability, 3-sat
---


title: Practical Applications of Radix Sort

text:
# Question
Title: Practical Applications of Radix Sort
Radix sort is theoretically very fast when you know that the keys are in a certain limited range, say $n$ values in the range $\[0\dots n^k -1\]$ for example. If $k\<\lg n$ you just convert the values to base $n$ which takes $\Theta(n)$ time, do a base $n$ radix sort and then convert back to your original base for an overall $\Theta(nk)$ algorithm.

However, I've read that in practice radix sort is typically much slower than doing for example a randomized quicksort:

> For large arrays, radix sort has the lowest instruction count, but because of its relatively poor cache performance, its overall performance is worse than the memory optimized versions of mergesort and quicksort.

Is radix sort just a nice theoretical algorithm, or does it have common practical uses?

# Answer
Radix sorts are often, in practice, the fastest and most useful sorts on parallel machines.

On each node of the multiprocessor you probably do something like a quicksort, but radix sort allows multiple nodes to work together with less synchronization than the various recursive sorts.

There are other situations too. If you need a *stable sort* (a sort where whenever two keys are equal they stay in the same order rather than getting rearranged) then I'm not aware of any version of quicksort that will be of use. Mergesort is also stable (if implemented correctly). Your link is the first time I've ever heard anyone say that mergesort could be made to have better cache behavior than radix sort.
> 17 votes

# Answer
@Robert: Your link is quite surprising (actually I could not find the quoted sentence). My personal experience is for random input, radix sort is much faster than the STL `std::sort()`, which uses a variant of quicksort. I used to make an algorithm 50% faster by replacing `std::sort()` with an unstable radix sort. I am not sure what is the "memory optimized version" of quicksort, but I doubt it can be twice as fast as the STL version.

This blog post evaluated radix sort along with several other sorting algorithms. Briefly, in this evaluation, `std::sort()` takes 5.1 sec to sort 50 million integers, while in-place/unstable radix sort takes 2.0 sec. Stable radix sort should be even faster.

Radix sort is also widely used for stably sorting strings. Variants of radix sort are at times seen for constructing suffix arrays, BWT, etc.
> 4 votes

# Answer
Radix sort is also a natural way to sort fixed-length words over a fixed alphabet, e.g. in Kärkkäinen & Sanders algorithm (http://www.cs.cmu.edu/~guyb/realworld/papersS04/KaSa03.pdf)
> 2 votes

---
Tags: algorithms, sorting, applied-theory, radix-sort
---


# Question
Title: Behavior of different multiplied and added time complexities
Θ - Tightly bound

O - Upper bound

Ω - Lower bound

I understand that for addition, the max asymptotic value is taken, for example...

if ƒ1(n) = O(n) and ƒ2(n) = O(n log n), then ƒ1 + ƒ2 = O(max(ƒ1, ƒ2) = O(n log n)

and for multiplication, the multiplied asymptotic value is taken, for example...

if ƒ1(n) = O(n) and ƒ2(n) = O(n log n), then ƒ1 * ƒ2 = O(ƒ1 * ƒ2) = O((n^2)log n)

My question is, what happens to the formulas for adding and multiplying functions of different growth rates when other bounds besides upper bounds (such as Ω - Lower bound and Θ - Tightly bound) are used?

# Answer
Let $f(n)\in \theta(h\_1(n))$ and $g(n)\in \theta(h\_2(n))$.

We start with multiplication: It is easy to prove (from the basic definitions) that $f(n)\cdot g(n)\in \theta ((h\_1\cdot h\_2)(n))$, and similarly for $\Omega,o,\omega$.

Accordingly, multiplication of functions is preserved in all the asymptotic notations ($O,\Omega,\theta,o,\omega$)

As for addition, the idea is to make the following observation: $$f(n)+g(n)=\max\\{f(n),g(n)\\}+\min\\{f(n),g(n)\\}$$ But $\min\\{f(n),g(n)\\}\le \max\\{f(n),g(n)\\}$, so $f(n)+g(n)\le 2\max\\{f(n),g(n)\\}$. Thus, we get $$\max\\{f(n),g(n)\\}\le f(n)+g(n)\le 2\max\\{f(n),g(n)\\}$$

This implies that the asymptotic behavior of $f(n)+g(n)$ differs from that of $\max\\{f(n),g(n)\\}$ by a multiplicative constant, which means that they have the same order of magnitude, and in particular the relation is preserved under all the asymptotic notations.

To add some detail to the above, we use the observation that if e.g. $f(n)\in \Omega(h\_1(n))$ and $g(n)\in \Omega(h\_2(n))$, then $\max\\{f(n),g(n)\\}\in \Omega(\max\\{h\_1(n),h\_2(n)\\})$. This is relatively easy to prove.
> 3 votes

---
Tags: time-complexity, asymptotics
---


# Question
Title: Algorithm for difference of two semi-decidable languages
I have two algorithms

Algorithm 1:

```
if( Condition1(input)==true )
   print(input);
else
   loop forever;

```

Algorithm 2:

```
if( Condition2(input)==true )
   print(input);
else
   loop forever;

```

for any arbitrary fully-computable conditions 1 and 2.

We know both of these algorithms are partially computable.

I want to write a new algorithm (algorithm 3) like this:

```
if algorithm1 prints x and algorithm2 does not print x "if and only if" algorithm3 print x

```

Can I write algorithm3? And how?

# Answer
You are confusing languages with algorithms.

An algorithms is not "computable" or "non-computable". It can halt or not halt, but the latter doesn't mean that the language it defines is non-computable.

In this case, if conditions 1 and 2 are fully-computable (assuming by that you mean decidable, or recursive), then you can write algorithm 3 as follows:

Given x, check both condition 1 and condition 2. Print the input iff condition 1 holds and 2 doesn't.

The fact that algorithms 1 and 2 are "silly" in that they get stuck for no "good reason" doesn't affect the decidability of their languages.
> 2 votes

# Answer
I am reading between the lines. If you want to ask this:

> Given semi-decidable languages $L\_1$ and $L\_2$, is the language $L = L\_1 \setminus L\_2$ also semi-decidable?

In this case, the answer is: no, not always.

Hint: Find a (simple) counter-example using a known non-semi-decidable language.

> Let $L\_1 = \Sigma^\*$ and $L\_2 = K$ with $K$ the language of the halting problem.
> 0 votes

---
Tags: computability
---


# Question
Title: how do you define functions with denotational semantics?
Denotational semantics are abstract functions that give meaning to statements of a programming language. They accept an expression and return a value.

But how do you define denotational semantics for languages that define, for example, functions (and later use these functions), or global variables, and change some global state of the program?

I think the simplest way to do it would be to define the semantics function so that it returns a pair of values and a "global state" instead of just a value.

But is there a place I can read about it some more? I am sure someone have done something like that. For example, is there denotational semantics for languages like Java or C?

It would be nice to find a book that focuses on denotational semantics for programming languages which are not necessarily purely functional (though I think functional languages, like LISP, can also change a global state).

# Answer
> 3 votes
People have been writing denotational semantics for all kinds of languages since the late seventies. The list must now be quite long, and include large real languages, but I never tried to check what is in it. The number of books is probably large too. What you want is to look at toy examples. Anything real is not a good idea for a start. Some are probably in (text)books.

There were some references to such examples in A simple programming language? You may try it ... I did not check the answers.

In some cases people had to write a formal semantics because they wanted to prove correctness of the compiler. Still much research on this.

> Denotational semantics are abstract functions that give meaning to statements of a programming language. They accept an expression and return a value.

Well, only in the sense that any well formed program fragment may be seen syntactically as an expression (a formula), and anything may be seen as a value in denotational semantics, including functions (values belong to domains ... which you can understand approximately as types). Actually the semantics function takes a syntactic formula (you can read "formula" as "abstract syntax tree") and returns a function expressing what that formula is supposed to mean ... or to do when run as (part of) a complete program.

How you write the semantics, and what domains you use is highly dependent on what kind of features exist in you language. For example, if you have exceptions, things may get a bit more complicated.

But just try toy examples to begin with. And then more.

# Answer
> 2 votes
The Scheme specification (revision 4) has an extensive denotational semantics, specified in the appendix of Revised$^4$ Report on the Algorithmic Language Scheme. This is probably not the best starting point to learn denotational semantics.

FYI, the most recent version, R6RS, has changed to use operational semantics.

---
Tags: programming-languages, denotational-semantics
---


# Question
Title: Space(n) not closed under Karp reductions - what about NTime(n)?
In the book on complexity by Arora and Barak, there is an exercise to show $Space(n)\neq NP$, the proof of which goes by showing that $NP$ is closed under Karp reductions, while $Space(n)$ isn't.

To show that $Space(n)$ isn't closed under Karp reductions, the suggested technique (both in the solutions given at my place of study as well as those given at many other universities) is to assume we have a TM that decides language $L$ in $Space(n^2)$. Now take an encoding $enc(x)$ of some $x$ in $L$ with $|enc(x)| = n$ and blow it up (in quadratic, thus polynomial time) to an encoding $enc'(x)$ of $x$ with $|enc'(x)| = n^2$ by padding the smaller encoding with $n^2-n$ padding symbols. Now we take the same TM, and it can decide $L$ in space linear in $enc'(x)$ by ignoring the padding stuff and just operating on $enc(x)$. This implies that $Space(n^2) \subseteq Space(n)$, which contradicts the space hierarchy theorem, so $Space(n)$ can't be closed under Karp reductions.

My problem here is that while I realize that we can easily show that $NP$ is closed under Karp reductions, it somewhat confuses me regarding what this says about $NTime(s(n))$. It seems to me that this approach will also work to show that $NTime(s(n))$ isn't closed under Karp reductions for any time-constructible function s(n) using the time hierarchy theorem, or am I mistaken here?

# Answer
> 2 votes
You're not mistaken. The reason NP is different is that it's defined as the *union* of $NTime(n^k)$ for all $k \geq 0$, so the set of upper bounds on the running time $s(n)$ is closed under substituting polynomials.

---
Tags: complexity-theory, reductions, closure-properties
---


title: What randomness really is

text:
# Question
Title: What randomness really is
I'm a Computer Science student and am currently enrolled in System Simulation & Modelling course. It involves dealing with everyday systems around us and simulating them in different scenarios by generating random numbers in different distributional curves, like IID, Gaussian etc. for instance. I've been working on the boids project and a question just struck me that what exactly "random" really is? I mean, for instance, every random number that we generate, even in our programming languages like via the `Math.random()` method in Java, essentially is generated following an "algorithm".

How do we really know that a sequence of numbers that we produce is in fact, random and would it help us, to simulate a certain model as accurately as possible?

# Answer
The short answer is that no one knows what real randomness is, or if such a thing exists. If you want to quantify or measure the randomness of a discrete object, you would typically turn to Kolmogorov complexity. Before Kolmogorov complexity, we had no way of quantifying randomness of say a sequence of numbers without considering the process that spawned it.

Here's an intuitive example that was really bugging people back in the day. Consider a sequence of coin tosses. The outcome of one toss is either heads ($H$) or tails ($T$). Say we do two experiments, where we toss a coin 10 times. The first experiment $E\_1$ gives us $H,H,H,H,H,H,H,H,H,H$. The second experiment $E\_2$ gives us $T,T,H,T,H,T,T,H,T,H$. After seeing the outcome, you might be tempted to claim there was something wrong with the coin in $E\_1$, or at least for some weird reason what you got is not random. But if you assume both $H$ and $T$ are as probable (the coin is fair), the probability of obtaining either $E\_1$ or $E\_2$ is equal to $(1/2)^{10}$. In fact, obtaining *any* specific sequence is as probable as any! Still, $E\_2$ *feels* random, and $E\_1$ does not.

In general, since Kolmogorov complexity is not computable, one can't compute how random say a sequence of numbers is, no matter what kind of claimed "totally random" process spawned it.
> 18 votes

# Answer
In the case of Java (or similar languages), we **know** the algorithm used to create the random numbers. If it starts with a single seed, the numbers are not random at all, i.e. if we know $a\_i$ in a sequence $a\_0,\dots,a\_n$, we know $a\_{i+1}$, or stated as conditional probability: $$\forall k,l,i: P(a\_{i+1}=k\mid a\_i=l)\in\\{0,1\\}$$

Nevertheless those series may fulfill properties (see e.g. WP:Autocorrelation) that random numbers fulfill and these properties often suffice to accomplish tasks, where we'd like to use "real" (e.g. generated by some physical process) random numbers, but can't effort them.
> 8 votes

# Answer
It is impossible to know for sure whether a given sequence is random or not. You can, however, look at characteristics (or parameters) of a sequence and calculate the probability of such a sequence given the distribution of interest.

If you could generate an infinitely long sequence using your random generator, it should have the same parameters as the random distribution. For example, if you are using the standard Gaussian distribution $(\mu=0,\sigma=1)$, then your sequence should be approaching the mean of 0 and the standard deviation of $1$. So, one preliminary way to check your generator is to generate a really long sequence and check to see that it is approximating the desired random distribution.

You can add additional moments of the distribution (such as skewness) of interest for further validation. For IID numbers, you could also try to train a machine learning algorithm to predict upcoming elements of the sequence and then test for the null hypothesis that the history improves the performance. None of these methods, however, can prove that a sequence is truly random and, at best, can recognize when sequences are NOT random (to some degree of certainty).
> 3 votes

# Answer
The modern theory of computing answer is "a random source is a source that looks random to your favorite class of algorithms". This is a utilitarian perspective: if a source of randomness looks like true randomness to all algorithms you care about, then nothing else matters. You can analyze your algorithms as if they are given truly random coin tosses, and your analysis will give the correct answers.

To be a bit more precise, let's say that you care about all algorithms in a class $\mathcal{A}$. $\mathcal{A}$ could be

* all Turing machines that always halt
* all polynomial size circuit families
* all polynomial time Turing machines
* all logspace Turing machines

The class $\mathcal{A}$ will be the "distinguishers". Then, a sequence of random variables $(X\_n)$ where $X\_n$ takes values in $\\{0, 1\\}^n$ is $\epsilon$-pseudorandom against $\mathcal{A}$ if for all $A \in \mathcal{A}$, $$ \left|\Pr\[A(X\_n) = 1\] - \Pr\[A(U\_n) = 1\]\right| \leq \epsilon, $$ where $U\_n$ is a random variable distributed uniformly in $\\{0, 1\\}^n$.

This idea is behind any modern formal notion of pseudorandomness.
> 3 votes

# Answer
Here's two more cents.

One way to think about randomized algorithms is to picture a box that takes some input, does mysterious things to that input, and produces some ("unpredictable") output.

But instead, it might be helpful to think of them as deterministic algorithms that take two inputs: the "true" input, and some "random" inputs that we get from functions like `Math.Random()`.

Now when we analyze the algorithm, we can make statements like this: "*If* our random inputs are uniform and independent on $\[0,1\]$, *then* with high probability our algorithm runs in time $n \log n$" or "with high probability the answer is correct".

This is a true fact about our algorithm. Now, a second question is whether the random inputs really do match this sort of assumption. I like the Bayesian sort of view that says this: Suppose that, *to the best of my knowledge and beliefs*, the randomness of my input is uniform and independent on $\[0,1\]$. Then the fact we proved above tells me what to believe about the output of my algorithm (namely, that it is very likely to run in time $n \log n$ or to be correct or so on).

As Jonathan and frafl mention, there are ways to sort of check if a random source is behaving "randomly". But all they will do is influence what you believe about future information that comes from this random source. If you think that each bit is equally likely to be zero or one, regardless of the previous bits, then to the best of your knowledge and beliefs, that source is uniformly and independently random and therefore, to the best of your knowledge and beliefs, it will run fast or be correct or so on. That's my philosophical take, anyway.
> 2 votes

# Answer
We cannot generate truly random numbers. There are different methods for generation of pseudo-random numbers using a specified equation and a particular seed value. So the random sequence of numbers depends on the seed value. Once we know the seed value, we can predict the what the sequence is going to be. Apart from this there are other methods for generating random numbers. People are now using some methods to generate true random numbers like using the disk head movement time and other physical methods which can be incorporated in a computer Refer to : http://en.wikipedia.org/wiki/Random\_number\_generation#Generation\_methods
> -2 votes

# Answer
by the given method like you said
Math.random() *in Java*
Randomize; Random(n); *in Delphi*

you can implement your own structure and logic to generate random numbers,
where such "algorithm" can perform by your given specifications for better random results.
and build upon that the logics.

Thanks.
> -3 votes

# Answer
other answers are good, heres some other angles on this very important/unintentionally deep question. computer scientists have been studying randomness for decades and are likely to continue to study it. it has many deep connections and foremost open questions remaining throughout the field. here are a few pointers.

* "true/real randomness" occurs with low-level physical processes & "noise" such as in zener diodes, quantum mechanics etc. which can be harnessed in hardware based RNGs
* other numbers generated in the computer realm is what is known as "pseudorandom" which is simulated and can never match "true randomness". these are so-called PRNGs
* there is an important sense of "cryptographic hardness of random number generators" that in a sense measures their "quality" or "security" see eg cryptographically secure PRNG. basically a "weak" generator does not have as much computational complexity as a "hard" generator and a "weak" one is easier to break.
* another somewhat related sense it comes up is "hardness of proofs". imagine a proof to prove that a RNG is linear time $O(n)$. that proof would seem to be simpler than one required to prove it is quadratic $O(n^2)$ and so on. this concept is still in the process of being formalized/researched but it actually impinges on deep questions like P$\stackrel{?}{=}$NP in a famous paper called Natural Proofs. roughly, the authors show a P$\neq$NP proof must have a certain "complexity" otherwise the same analysis technique could be used to break PRNGs, and moreover, somewhat surprisingly, most or maybe all complexity class separations/techniques known at that date (or possibly even afterwards, to date) do not have sufficient complexity.
* an important research topic in TCS is randomized and derandomized algorithms. the idea is, roughly, to study how much the algorithm is altered by replacing "true randomness" with a PRNG and there are various deep theorems on the subject. here is a highranked cstheory.se question that gives some flavor of research in this area: efficient and simple randomized algorithms where determinism is difficult
* another key related topic in TCS is information entropy— originally introduced in physics long ago— which studies a closely related concept of "information dis-order" and like some other important concepts in (T)CS seems be one of the key ideas that crosscuts the boundary between applied and theoretical analysis, even some of the formulas are the same.
* again attesting to the status of active research, there are other high-ranked questions on cstheory.se that relate to this question. here is one close, almost the same: is a truly random number generator Turing computable
> -4 votes

---
Tags: randomness, modelling
---


# Question
Title: Cross platform apps and programing languages...how is it done?
I always wondered how various certain languages like Java, HTML5 and browser extensions are made with cross platform(operates and functions the same, regardless of OS, being Linux/Windows/BSD not specifically CPU architecture) compatibility in mind...

Is there a certain developmental process semantic or otherwise that one would have to follow, in order to create such?

Can some one give me the "nitty gritty" of how it's done , how it works ... i.e. system calls(if any)

# Answer
> 5 votes
First word: consistent API across platforms - when programming on different platforms, the same API is presented to programmers.

Second word: layered architecture - this hides the low level differences under a consistent layer.

# Answer
> 4 votes
In many cases, Java being a prominent example, the code is interpreted by a virtual machine. The virtual machine is different for each operating system, but they all provide the same functionality, so that the Java code does not see the difference. This is also true for HTML, Javascript, Python, Ruby and many more.

On the other hand, it is possible to write cross platform code in languages that don't have a virtual machine, like C. Here the code only uses the parts of the operating system interface that are the same among all platforms, for example it can stick to the POSIX standard to run smoothly under all unix flavours and (with a little luck?) windows. However, while the code is platform-independent, it needs to be recompiled for each platform so that it can be linked with the concrete libraries that the operating system provides and adhere to the encoding scheme for executables used on that platform.

In both cases a layer of abstraction separates the codes and the operating system. In the first case it's the API provided by the virtual machine, in the second case it's a layer of libraries that provide the same interface across platforms. If code performs syscalls "by hand" it usually is no longer platform-independent (unless it checks on which platform it runs and does different things in each case, of course).

# Answer
> 1 votes
Standardization certainly plays an important role. Specifications can be implemented differently but you can expect the final product to correctly implement the MUST's, SHOULD's, ... of the spec.

# Answer
> 0 votes
This cross-platform consistency is mainly permitted by standardization of various platform features, so that they offer the same behavior independently of how the feature is actually implemented ón each platform.

But on the other hand, this is precisely the reason why standardization is actively worked on and reinforced: to get compatibility. Standardization, platform independence and compatibility (what is often called interoperability) are developed for many reasons, and it shows from the kind of actors who work on it.

If you consider the Internet, it is primarily a mean for communication. If there is no agreement on what can be exchanged and what it means, there is just no communication. Man communicates poorly with dolphins for hardware reasons, and often poorly with other men for software reasons.

Companies want cross-platform compatibility to have larger market for their products, so as to benefit from economy of scale. Companies have to follow the existing standards if they want their products to be accepted by market.

All this converges.

From an abstract point of view, computers are supposed to be universal machines, even with the OS fixed. So there is no surprise that this is possible, and that it happens since it is useful, including for business.

Think of what people do when they mimic Turing machnes of one kind with another kind. It is much the same idea, except that you are more concerned with efficiency which often requires ingenuity. This is why virtual machines hosting full OSs took a long time to develop. In comparison, developing HTML on all platforms was very easy.

And there is also the fact that the determination of (good) standards is done (technically, and hopefully politically) with the idea that they should be realizable on all concerned platforms.

The real problems arise when people (usually companies) try to control standards. The technical problems are easy (they do require work). The hard problems are legal, social, economic ones.

What do you do when you are told that a given interface is private and that you must pay for using it ? or that you are simply not allowed to use it ? Think of CODECs for example.

---
Tags: programming-languages, operating-systems
---


title: Surprising and basic data structures

text:
# Question
Title: Surprising and basic data structures
I'm interested in surprising data structures that extend the things people learned in their first algorithm/data structure course. Usually by offering an additional operation at a very low cost.

I learned that one can create a dynamic array with $O(1)$ access and $O(1)$ amortized append a long time ago. I thought there is no way to remove the amortized cost. I saw a data structure only a few months ago that do both operations in $O(1)$ non-amortized time.

What are some other examples?

# Answer
I would not know what you learned or did not learn, What is surprising depends a lot on who is to be surprised. So your question is pretty much undefined.

All I can do for you (but I am no expert) is to mention one technique that impressed me when I first saw it, the skip lists of William Pugh. And more generally the use of randomness and probabilistic techniques, actually not just in algorithmics but also in "proving" or in quickly identifying things that can then be formally proved (at high computational cost) to have this or that property.
> 1 votes

---
Tags: data-structures
---


# Question
Title: Find the number of topological sorts in a tree
Find the number of topological sorts in a tree that has nodes that hold the size of their sub-tree including itself.

I've tried thinking what would be the best for m to define it but couldn't get anything specific.

Maybe $\mbox{Number of sorts =}\prod\limits\_{x\in \mbox{children}}\mbox{Number of sorts}(x)$ Meaning that starting at the root I call the the method recursively multilying each result by the previous children's result. When we reach a node with size 1 we assume that there's just 1 topological sort;

If this is correct I'd really appreciate some help with proving correctness and if not a explanation why and a clue could be nice :)

# Answer
A clue then.

It seems you have to multiply with a multinomial coefficient in each step. Here the size of the subtree comes in handy.

Explanation: if children have certain topsorts, then these sequences may be shuffled in the topsort for the parent. We 'color' the positions where the various topsorts for the respective children are placed, and at each color we write one of the possible topsorts for that child.

Since the formula is used now in another problem, here it is explicitly. Assume the tree $t$ has $n+1$ nodes, and the subtrees $t\_1, \dots, t\_r$ of the children have $k\_1, \dots, k\_r$ nodes respectively (so $n=k\_1+\dots+k\_r$). Let $\operatorname{NoS}(t)$ be the number of topsorts of tree $t$. Then

$$\operatorname{NoS}(t) = {n \choose k\_1, k\_2, \dots, k\_r}\prod\_{i=1}^n \operatorname{NoS}(t\_i) $$
> 5 votes

---
Tags: graphs, algorithm-analysis, trees
---


# Question
Title: Why is the name half-adder used to represent the half-adder?
I have recently came across half-adders and full adders in my Logic Network lectures. I have somewhat understood the theory, but I am still unable to understand the reason why they called them in that name? I mean, is there any reason why half-adders have the name ‘half-adders’?

# Answer
With a full adder, you can get all outputs from (0,0) to (1,1). With a half adder, you can never get (1,1), which makes it, in a way, incomplete.

Also, in practice a full adder is used more than a bare half adder. For example, addition of binary numbers (one of the most common operations needed by a microprocessor) is done by chaining full adders:

(4-bit adder, taken from Wikipedia)

In the end, since full adders are the ones used for adding, we call them "full" adders.

And since a full adder can be made by joining up two half adders with an OR gate, the half adder becomes "half" an adder.
> 5 votes

# Answer
I can't cite an historical reference, but I would suspect a "half adder" is called that because you can combine two of them (with an `or` gate combining the carries) to make a "full adder".
> 3 votes

# Answer
The half adder can add only two input bits (A and B) and has nothing to do with the carry if there is any in the input. So if the input to a half adder have a carry, then it will neglect it and adds only the A and B bits. That means the binary addition process is not complete and that’s why it is called a half adder.
> 1 votes

---
Tags: terminology, circuits
---


title: $2k$ number assignment

text:
# Question
Title: $2k$ number assignment
Given $k$ numbers $A\_1 \leq A\_2 \leq ... \leq A\_k$ such that $\sum\limits\_{i=1}^k A\_i = k(2k + 1)$ is there an assignment of numbers $i\_1, i\_2, ... , i\_{2k}$ which is a permutation of $1, 2, ... , 2k$ such that

$i\_1 + i\_2 \leq A\_1\\ i\_3 + i\_4 \leq A\_2\\ .\\\.\\\.\\ i\_{2k-1} + i\_{2k} \leq A\_k$

?

I cannot find an efficient algorithm and that solves this problem. It seems to be a combinatorial problem. I was unable to find a similar NP-Complete problem. Does this problem look like a known NP-Complete problem or can it be solved with a polynomial algorithm?

# Answer
> 8 votes
This problem is strongly NP-complete.

Suppose all the $A\_j$ are odd. Then we know that since $i\_{2j-1} + i\_{2j} = A\_j$ is odd, one of $i\_{2j-1}$ and $i\_{2j}$ is even and the other is odd. We can assume that $i\_{2j-1}$ is odd and $i\_{2j}$ is even. By letting $\pi\_j = \frac{1}{2}(i\_{2j-1}+1)$ and $\sigma\_j = \frac{1}{2}(i\_{2j})$, we can show that this is equivalent to asking for two permutations, $\pi$ and $\sigma$, of the numbers $1 \ldots n$ such that $\pi\_j + \sigma\_j = \frac{1}{2}(A\_j+1)$.

This problem is known to be NP-complete; see this cstheory.se problem and this paper of W. Yu, H. Hoogeveen, and J. K. Lenstra referenced in the answer.

# Answer
> 6 votes
Here is a hint to get you started: since the sum of all numbers from $1$ to $2k$ is exactly $k(2k+1)$, a solution is possible only if in fact $i\_1 + i\_2 = A\_1$, $i\_3 + i\_4 = A\_2$ and so on. So given $i\_1$ we know $i\_2$, and so on. Also, $3 \leq A\_j \leq 4k-1$.

# Answer
> 0 votes
It's a matching problem, and so can be solved using Edmond's algorithm. See wikipedia

---
Tags: np-complete, decision-problem
---


# Question
Title: What's better for an algorithm complexity, O(log n) or amortized O(log n)?
**Some context:** I'm to write a program that sorts the lines of a file in C for Linux. Since I have to read all lines of the file (`fgets()` for example) I'm thinking about inserting them in a tree like structure in a sorted manner using the so called tree sort algorithm.

Looking for a self-balancing tree structure I came across two that may be interesting, the red-black tree and a splay tree. According to Wikipedia the red-black tree has an `O(log n)` worst case and the splay tree has *amortized* `O(log n)`.

**The actual question:** I know how to roughly compare some complexity levels in O notation but what's that amortized time? Given two algorithms one that runs in `O(log n)` and the other in amortized `O(log n)` which one would be preferrable?

# Answer
$O(\log n)$ in the worst case implies $O(\lg n)$ amortized.

Basically, given two data structures supporting the same operator, one in $O(\lg n)$ time in the worst case and the other one in $O(\lg n)$ amortized time, the first one is considered to be superior asymptotically: being $O(\lg n)$ time in the worst case means that each call of the operator will be supported in this time, while having an amortized complexity of $O(\lg n)$ means that some (very few) operator calls can take $O(n)$ time. Usually, the concept of amortized analysis is used for data-structures which amortized complexity is *better* than their worst case complexity.

As an illustration, consider a data-structure for integers, storing each such integer $x$ as a string of bits (e.g. $x=8$ represented by $(1,0,0,0)$), and the operator $x.inc()$ which increments $x$ by $1$.

* In the worst case (e.g. on $x=7$ represented by $(1,1,1)$), the operator $x.inc()$ corresponds to $\log(x)+1$ binary write (e.g. to write $(1,0,0,0)$ corresponding to $8$).
* In the best case (e.g. on $x=8$), the operator $x.inc()$ corresponds to exactly one binary write (e.g. to change the last bit of $(1,0,0,0)$ to $1$, giving $(1,0,0,1)$).

In a sequence of increments of the same integer object (e.g. enumerating all integers from $0$), the "best case" described above happens half of the time, and the worst case one every $n$ increment (i.e. after $1,2,4,8,16,...$ increments). A case requiring $i$ bits write happens $1/2^i$ of the time. Summing all those costs gives an amortized cost of $\sum\_i i/2^i \in O(1)$. Hence the operator $inc()$ has a worst case complexity of $O(\lg n)$ but an amortized complexity of $O(1)$.

The notion of amortized analysis is well explained on wikipedia. You might want to see the page on the Potential method for more details.

Hope it helps!
> 10 votes

# Answer
A data structures with amortized guarantees can be very useful even if there exists a data structure with matching worst-case guarantees. Often data structures with amortized guarantees as simpler, and the asymptotic notation hides smaller constants. I think the key difference is:

* Are you using the data structure to support an interactive system, where the user interacts repeatedly with the system and response time needs to be fast? Then you really need a worst case guarantee.
* Is the data structure a way to speed up the overall running time of an algorithm? Then an amortized guarantee is usually enough.

A classical example of the second kind is Fibonacci heaps in conjunction with Dijkstra's algorithm. A simpler example is the one Jeremy gave: if you want to implement a brute-force algorithm that tries all binary strings of length $n$ as possible solutions to some problem, the binary counter is one of the simplest ways to enumerate over all binary strings. If your algorithm does $O(1)$ work per string, then the total running time will be $O(2^n)$, which is as good as it can be since you are enumerating over $2^n$ strings. You can de-amortize the data structure (it's a very cute exercise) but why bother - you'll just lose constant factors and in fact increase the total running time!
> 2 votes

# Answer
There is another factor that distinguishes worst-case and amortized complexity. In some cases, you need to "backtrack" with a data structure. That is, you need to restore the data-structure to its state at some prior time. There are a variety of reasons for this, one possibility is that you detect some contradiction or new information at a given time and want to go back and fix it by changing some earlier choices you made.

If a data structure takes worst-case time $T$ per step, then you can backtrack it at the cost of $T$ per step. However, if it takes amortized time $T$, then there is no guarantee on the cost of backtracking. For example, the steps you are backtracking may have turned out to be the costly steps.
> 2 votes

---
Tags: time-complexity, sorting
---


# Question
Title: How to perform alphabetically ordered DFS?
I've been working on this graph and just completely botching it. I mean to say that my solution may be the worst possible other than if a monkey had thrown darts at the graph to decide the next path. Anyhow, I'm lost and really trying to get a grasp of where my conclusion and the proper conclusion diverged dramatically.

I wanted to perform a DFS, show discovery/finish times, the DF forest, and edge classifications. I assumed that: 1) The vertices are listed in alphabetical order in each adjacency list. 2) The vertices are taken in the alphabetical order in the main loop of the DFS algorithm.

Should I be treating this as a directed acyclic graph?

# Answer
$L$ has an edge to $K$, other than that, the DFS forest you've drawn is correct. And since $K$ would not be expanded before $L$, there should be an edge $LK$ in the BFS forest.
> 0 votes

---
Tags: graphs, search-algorithms
---


# Question
Title: Time complexity of mutually recursive functions
Suppose I have two mutually recursive functions like this:

```
f1(x)
{
   .//some code
   .
   .
   f1(x-1)+g1(x-1);

}

g1(y)
{
   .
   .//some code
   g1(y-1)+f1(y-1);
  ..

}

```

How can I calculate time complexities in such cases?

# Answer
If we set up recurrences, $T\_1(n) = T\_1(n-1) + T\_2(n-1)$ and $T\_2(n) = T\_1(n-1) + T\_2(n-1)$. So from there we can get that $T\_1(n) = T\_2(n)$, which implies that $T\_1(n) = 2T\_1(n-1)$. So for this, the two functions would be $O(2^n)$.
> 1 votes

---
Tags: time-complexity, recursion
---


# Question
Title: Removing identical variables in CFG Unit Productions
Productions of the form A-\> A are removed immediately, but what if the production is of the form A -\> AA?

example: A -\> AA | a

# Answer
> 3 votes
In you example the production `A->AA` can not be removed. If that production is removed then the language described by the grammar will change. But in case of a production like `A->A`, the removal will not affect the language described by the Grammar.

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


# Question
Title: Relationship between Undecidable Problems and Recursively Enumerable languages
I have read the Wikipedia article on Recursively Enumerable languages. The article suggests that the halting problem is recursively enumerable but undecidable. My idea till today was that the halting problem belongs to a class of languages which are not even recursively enumerable. But the article suggests that the halting problem is recursively enumerable. My doubt is about the relationship between undecidable problems and recursively enumerable languages. Are all undecidable problems recursively enumerable languages?

If there is a problem which belongs to the class of non recursively enumerable languages, will it be always undecidable?

Also could any one suggest a problem which is not even recursively enumerable?

# Answer
> 11 votes
> Are all undecidable problems recursively enumerable languages?

No. See my answer to your third question.

> If there is a problem which belongs to the class of non recursively enumerable languages, will it be always undecidable?

Yes. In particular, recursive (decidable) languages are a subset of the recursively enumerable languages, so anything that's not recursively enumerable isn't recursive (decidable).

> Also could any one suggest a problem which is not even recursively enumerable?

The complement of the halting problem is not recursively enumerable. Suppose that it were. Then you could begin recursively enumerating the set $H$ of halting programs at the same time that I'm recursively enumerating the set $H'$ of non-halting programs. Every program would eventually be listed by one of us; if you listed it, you'd shout "accept" and I'd stop enumerating, and if I listed it, I'd shout "reject" and you'd stop enumerating. We'd have an effective procedure for deciding the halting problem.

Note that this generalizes: the complement of any recursively-enumerable (but non-recursive) problem is non-recursively-enumerable, for the reason outlined above.

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


# Question
Title: Where do the length restrictions of the pumping lemma come from?
For a language $L$ with pumping length $p$, and a string $s\in L$, the pumping lemmas are as follows:

**Regular version**: If $|s| \geq p$, then $s$ can be written as $xyz$, satisfying the following conditions:

1. $|y|\geq 1$
2. $|xy|\leq p$
3. $ \forall i\geq 0: xy^iz\in L$

**Context-free version**: If $|s| \geq p$, then $s$ can be written as $uvxyz$, satisfying the following conditions:

1. $|vy|\geq 1$
2. $|vxy|\leq p$
3. $ \forall i\geq 0: uv^ixy^iz\in L$

My question is this: **Can someone give a concise and clear explanation of how regularity (context-freeness) imply the first and second conditions above?** The pumping length is determined by (finite) properties (finite number of states or finite properties of production rules, respectively), the third properties guarantee that a state (production rule) can be skipped or repeated arbitrarily many times, but where do the first and second conditions originate? How are they justified?

# Answer
The first condition, i.e. $|y| \geq 1$, is clearly necessary if you want to say something interesting: for $y = \varepsilon$, $xy^iz \in L$ *trivially* and always holds.

The second condition, i.e. $|xy| \leq p$, is "arbitrary": the lemma still says something interesting if you drop it, and it is still true because the statement becomes weaker.

But remember what we want to use the pumping lemmas for: we want to find a (sufficiently long) word such that *all* valid decompositions into $x,y,z$ fail to pump. Therefore, it is useful to allow as few such decompositions as possible. Lucky as we are, the proof of the pumping lemma readily yields a strong restriction, namely that there *has* to be a pumpable decomposition with $|xy| \leq p$ with *constant* $p$.

Now we have to refute only finitely many prefixes $xy$ (with possibly infinitely many different continuations, of course). If you look at example applications, you will see that they make heavy use of this restriction.
> 8 votes

# Answer
I'll only offer some pointers on the pumping lemma for regular languages; the reasoning is similar enough for the other. Think of $x$ as the part of $s$ generated by everything before starting the first loop for the first time; $y$ as everything generated while in that certain loop for the first loop; and $z$ as everything generated after looping the first time.

1. Since $|s| \geq p$, and $p$ is the number of states in the minimal finite automaton (e.g.) accepting the language, then the automaton must have looped (since at most $p-1$ transitions would have been possible, otherwise). Therefore, $y$ is non-empty; we are stating the fact that since we have a string of a certain length, the automaton accepting it must have looped at some point, so $|y|\>1$ is justified.
2. Since $y$ is the first time you go through the first loop, and $x$ is everything before that, you have not visited any state in the automaton more than once. Since there are $|p|$ states in the automaton, and you haven't visited all of them, you have $|xy| \< p$.

These aren't so much hypotheses requiring support; they're statements of fact based on how the pumping lemma was dreamed up in terms of finite automata.
> 3 votes

# Answer
As you move through the states of an automaton, you'll eventually hit a cycle. The cycle is $y$. There is no point in pumping an empty word, hence condition 1. $xy$ is the number of symbols you had to read to find the first cycle. This can't possibly be more than the number of states, hence condition 2. Almost by definition, a cycle can be repeated any number of times, hence condition 3.

The context free variant is very similar. The first condition is we're only looking for useful cycles. The second condition says that a cycle can be found because you'll run out of non-terminals. The third condition says that once you have a cycle you can pump it. Note that to see a cycle in the context free case, you should draw a parse tree.
> 2 votes

# Answer
There are variants of the pumping lemma. I will use yours.

Note that you have really 3 length conditions. The missing one is about the minimum total length of the word. I treat it with the second condition.

In a (big) nutshell :

I call **subtree** any subpart of the parse tree that has at most one non-terminal at the fringe. The pumping lemma uses **recursive subtrees** where the non terminal in the fringe is the same as the root of the subtree. The whole parse tree is a subtree.

Subtrees as defined here (and recursive subtrees) are the heart of the matter. Their existence is directly related to the **context-freeness**.

**1st condition**: it states simply that if there is an unproductive (fringe with no termina symbol) recursive subtree in the parse tree, it can be short-circuited, so that we are always sure the fringe contains a terminal symbol.

**A finiteness issue**: It will be used twice. If you have a subtree that contains no recursive subtree, then no path in the subtree has twice the same label (subtree root excepted). The subtree is finitely branching with a limited depth (no more than the number of non-terminals).Hence you have a finite set of such subtrees generating only a finite set of strings at their fringe. Being finite in number, there is an upperbound for the length of the fringes. A contrario, if a fringe exceeds the bound, it is a sure indication it contains a recursive subtree.

**"missing condition"**: The "missing condition" that $\mid s\mid \geq p$ ensure that the string is long enough so that there is at least one recursive subtree in the parse tree for pumping.

**2nd condition**: you can always get for pumping a recursive subtree that neither dominate nor contains another recursive subtree in the parse tree. If it does, just take the other recursive subtree. Since the parse tree is finite, this terminates. You end up with subtrees (for $vy$ and for $x$) that do not contain recursive subtrees, and the finiteness analysis above garantees the existence of an upperbound.

In the regular grammar case you just have subtrees that do not branch very much. It is really identical to the CF case with some strings replaced by $\epsilon$.

In the CF case, it is often convenient for the proof of the lemma, or its variations, to assume that the grammar is CNF (depending also on the lemma variant)

Much of the formal proof is mathematical presentation, not understanding.

This was an interesting exercise.
> 2 votes

---
Tags: formal-languages, regular-languages, context-free, pumping-lemma
---


# Question
Title: Is it possible to write a universal loop program for if-then & loop programs and it is possible to write a universal while program for while progra
Is it possible to write a universal loop program for if-then & loop programs and it is possible to write a universal while program for while programs?

---

Long version and some background:

Before anyone asks, YES, it is a homework and I am not here to find an answer, but only clues to help me get this question right !

I'll translate the question from French :

> We call a **universal program** (also called interpreter) a program that accepts, as an input, another program and simulates it to produce the output of this simulated program. A universal program can also be used to simulate programs written in this very same language or in another language.
>
> You can suppose, using Gödel's coding, that the program to be simulated is given to the universal program in the register r1, and the input on which this program but be simulated in the register r2. The coding of the program could simply give out the characters of the program to be simulated in a table as well as its input registers in another table.
>
> Answer the following questions:
>
> a. It is possible to write a universal **loop program** for **if-then programs**?
>
> b. Is it possible to write a universal **loop program** for **loop programs**?
>
> c. Is it possible to write a universal **while program** for **while programs**? To reach a satisfying answer/proof lever, you could use the Church-Turing thesis.

Now the question, is where do I start with this ? My head's going in every direction at the same time, I'm just going crazy.

NOTES :

**if-then programs** are defined like this :

We consider a if-then program to be defined like a loop program, excepted that there are no loops, but an instruction "if rj then \[\]" (rj is the register "rj", the j'th register)

I know for sure this has something to do with imbricated loops...

Any clues would be greatly appreciated !

Thanks a lot

# Answer
For part (a), there are (at least) two approaches:

1. Outline a LOOP program which simulates a given IF program. Seems pretty messy.
2. IF programs can be simulated by a WHILE program, i.e. they are recursive. Moreover, the running time of such a simulator is very manageable. A recursive function with a primitive recursive bound on the running time is primitive recursive, and so implementable as a LOOP program.

For part (b), there are again two approaches (leading to the same result):

1. Suppose that you had a universal LOOP program. Try running the argument used to prove that the halting problem is undecidable, and see what you get.
2. The running time of every LOOP program is on some level of the primitive recursive hierarchy, and the latter is strict and has infinitely many levels. Consider the running time of a universal LOOP program and see what happens.

Part (c) is about universal Turing machines.
> 1 votes

---
Tags: turing-completeness, loops
---


# Question
Title: $FIRST_k$ set -- is algorithm given by Aho&Ullman correct?
I am writing this, because no matter how I look at the algorithm I see an error :-)

Aho & Ullman in "Theory of Parsing, vol.1" (pp. 357-359) described the algorithm for building $FIRST\_k(A)$ set for any $A$ non terminal by incrementally building helper set $F\_i(A)$ which has such property that every $F\_i(A)$ set is contained in $F\_{i+1}(A)$ and it is finally equal to $FIRST\_k(A)$.

However I found a counter example for this, for $k=2$.

```
A := a B
B := b

```

$FIRST\_k(A) = \\{ a b \\}$, while $F\_0(A) = \\{ a \\}$.

Any help is appreciated, here is shortened content of those pages -- FIRST(k) -- and if you don’t have a book, I asked the same question in longer form as blog-post -- LALR(k) FIRST sets.

# Answer
> 1 votes
In your example $F\_0(A) = \varnothing$ (!) while $F\_0(B) = \\{b\\}$. Then $F\_1(A) = \\{ab\\}$. Voila.

By construction $F\_0(A) = \\{ x \in\Sigma^\* \mid A\to x\alpha \text{ where } |x|=k \text{ or } \alpha = \varepsilon \\}$. The only production $A\to aB$ has no terminal prefix with length two, so $F\_0(A)$ must be empty.

On the other hand, also the production for $B$ is shorter than two. But here we include the string $b$ as in consists of terminals only (the $\alpha=\varepsilon$ case).

As you note, $F\_{i+1}(A) = F\_i(A) \cup \text{ something }$, so we have $F\_0(A) \subseteq F\_1(A) \subseteq F\_2(A) \subseteq \dots$. The sets are increasing. The construction stops when two consecutive sets are equal (for *all* $A$), nothing will be added after that moment.

---
Tags: parsing
---


# Question
Title: Is the language of pairs of words of equal length whose hamming distance is 2 or greater context-free?
Is the following language context free? $$L = \\{ uxvy \mid u,v,x,y \in \\{ 0,1 \\}^+, |u| = |v|, u \neq v, |x| = |y|, x \neq y\\} $$

As pointed out by sdcvvc, a word in this language can also be described as the concatenation of two words of the same length the hamming distance of which is 2 or greater.

I think it's not context free but I'm having a hard time proving it. I tried intersecting this language with a regular language (like $ \ 0^\*1^\*0^\*1^\* $ for example) then use the pumping lemma and \ or homomorphisms but I always get a language that is too complicated to characterize and write down.

# Answer
> 7 votes
**Note \[2019-07-30\]** The proof is wrong ... the question is more complicated than it sounds.

After a failed attempt here it is another idea.

If we intersect $L$ with the regular language $L\_{reg} = 0^\*10^\*10^\*10^\*$ we get a CF language.

Perhaps we can have more luck if we use $L\_{reg}' = 0^\*10^\*10^\*10^\*10^\*$ (a string with exactly 4 1s).

Let $L\_1 = L \cap L\_{reg}'$, informally $w \in L\_1$ if it can be split in two halves, such that one half contains exactly $\\{0,1,3,4\\}$ $1s$ or both halves contain two $1$s but their positions don't match.

Suppose that $L\_1$ is CF and let $G$ be its grammar in Chomsky normal form, and let

$$w = uv = 0^a 1 0^b 1 0^c 1 0^d 1 0^e \in L\_1$$

We have $|u|=|v|$ (even length) and $d(u,v) \geq 2$

If we restrict our attention to the ways in which the four 1s of $w$ can be generated we have the three cases shown at the top of the figure 1. The central part of the figure 1 shows the first case (but the others are similar).

Figure 1 (the full picture can be downloaded here)

If we pick $a=e, c=2a$ and $b,d \gg a$ we see that the zeros between the two pairs of 1s must be independently pumpable (red nodes in the figure): in particular, for large enough $b \gg a$, we get a duplicate nonterminal node on a internal subtree (node X in figure 2) or a repeated subsequence in the path towards the first or the second 1 (node Y in figure 2). Note that Figure 2 is a little bit simplified: there can be more nonterminal nodes between the two $X$s, and also between the two $Ys$ ($Y\to ... \to Z\_i \to ... Y$ but with $Z\_i$ that produces only 0s on the right of the first 1).

Figure 2

So we can fix an arbitrary $a = e = k, c = 2a$, then pick large enough $b$ to get an independently pumpable node on the sequence of zeros between first and second $1$. For the sequence of zeros between the third and fourth 1, we can choose $d = b! +b$.
But $0^b$ is independtly pumpable so there is a $p \leq b$ pumpable substring $y$, i.e. such that $b = xyz, |y|=p, |x|\geq 0, |z|\geq 0$ and $xy^iz = b!+b$. The string we get is:

$$w' = 0^k 1 0^{b!+b} 1 0^{2k} 1 0^{b!+b} 1 0^k$$

but $w' \notin L\_1$. Thus $L\_1$ is not CF and finally $L$ is not CF.

If the proof is correct (???) it can be extended to every language $L\_k = \\{ uv : |u|=|v|, d(u,v)\geq k\\}, k\geq 2$

# Answer
> 2 votes
After 2 failed attempts, that were disproved by @Hendrik Jan (thank you), here is another one, that is not more successful. @Vor found an example of a deterministic CF language where the same construction would apply, if correct. This allowed identifying an error in the anchoring of the $y$ string in the application of the lemma. The lemma itself does not seem at fault. This is clearly too simplistic a construction. See more details in the comments.

---

The language $L = \\{ uxvy \mid u,v,x,y \in \\{ 0,1 \\}^\*\text \\{ \epsilon \\} \ ,\ \mid u \mid = \mid v \mid \ , \ u \not= v \ , \ \mid x \mid = \mid y \mid \ , \ x \not= y \ \\} $ is not Context-Free.

It is helpful to keep in mind the characterization $L= \\{uv:|u|=|v|,d(u,v) \geq 2\\}$ where d is the Hamming distance, proposed by @sdcvvc. What one needs to think about are 2 selected positions in each half string such that the corresponding symbols differ.

Then you consider a string $10^i10^j$ such that $i \lt j$ and $i+j$ is even. It is clearly in the language L, by cutting $u$ and $x$ anywhere between the two 1's. We want to pump that string on the first part between the 1's, so that it will become $10^j10^j$ which is not supposed to be in the language.

We first try to use Ogden's lemma, which is like the pumping lemma, but applies to $p$ or more distinguished symbols that are marked on the string, $p$ being the pumping length for marked symbols (but the lemma can pump more because it can pump also unmarked symbols). The pumping marked-length $p$ depends only on the language. *This attempt will fail, but the failure will be a hint.*

We can then choose $i=p$ and we mark symbols on the first sequence of $i$ 0's. We know that none of the two 1's will be in the pump, because it can pump out once (exponent 0) instead of pumping in. And pumping out the 1's would get us out of the language.

However, we could be pumping on both sides of the second 1 as fast or even faster on the right side, so that the second 1 would never get across the middle of the string. Also Ogden's lemma does not fix an upper limit to the size of what is being pumped, so that it is not possible to organize the pumping to get the rightmost 1 exactly across the middle of the string.

We use a modified version of the lemma, here called Nash's Lemma, which can handle these difficulties.

We first need a definition (it probably has another name in the literature, but I do not know which - help is welcome). A string $u$ is said to be an *erasure* of a string $v$ iff it is obtained from $v$ by erasing symbols in $v$. We will note $u \prec v$.

**Nash's Lemma :** If $L$ is a context-free language, then there exists two numbers $p\gt0$ and $q\gt 0$ such that for any string $w$ of length at least $p$ in $L$, and every way of “marking” $p$ or more of the positions in $w$, $w$ can be written as $w=uxyzv$ with string $u$, $x$, $y$, $z$, $v$, such that

1. $xz$ has at least one marked position,
2. $xyz$ has at most $p$ marked positions, and
3. there are 3 strings $\hat x$, $\hat y$, $\hat z$ such that
    1. $\hat x \prec x$, $\hat y \prec y$, $\hat z \prec z$,
    2. $1 \leq \mid \hat x \hat z \mid \leq q$, $1 \leq \mid \hat y \mid \leq q$, and
    3. $ux^j\hat x^i\hat y\hat z^iz^jv$ is in $L$ for every $i \geq 0$ and for every $j \geq 0$.

*Proof*: Similar to the proof of Ogden's lemma, but the subtrees corresponding to the strings $y$ and $xz$ are pruned so that they do not contain any path with twice the same non-terminal (except for the roots of these two subtrees). This necessarily limits the size of the generated strings $\hat x\hat z$ and $\hat y$ by a constant $q$. The strings $x^j$ and $z^j$, for $ j \geq 0$, corresponding to an unpruned version of the tree, are used mainly with $j=1$ to simplify the accounting when the lemma is applied.

We modify the above proof attempt by marking the $p$ leftmost symbols 0, but they are followed by $2q$ symbols 0 to make sure that we pump in the left part of the string, between the two 1's. That make a total of $i = p + 2q$ 0's between the 1's (actually $i = p + q$ would be sufficient, since the rightmost 1 cannot be in $\hat z$, which would allow to simply remove it).

What is left is to have chosen $j$ so that we can pump exactly the right number of 0's so that the two sequences are equal. But so far, the only constraint on $j$ is to be greater than $i$. And we also know that the number of 0's that are pumped at each pumping is between 1 and q. So let $h$ be product of the first $q$ integers. We choose $j=i+h$.

Hence, since the pumping increment $d$ - whatever it is - is in $\[1,q\]$, it divides $h$. Let $k$ be the quotient. If we pump exactly $k$ times, we get a string $10^j10^j$ which is not in the language. Hence L is not context-free.

.

*I think that I shall never see
A string lovely as a tree.
For if it does not have a parse,
The string is naught but a farce*

# Answer
> -1 votes
by this question I think $L$ is context-free and generated by the following grammar $\qquad\begin{align} S &\to AXBY \mid BYAX \\ A &\to 0 \mid 0A0 \mid 0A1 \mid 1A0 \mid 1A1 \\ B &\to 1 \mid 0B0 \mid 0B1 \mid 1B0 \mid 1B1 \\ X &\to 0 \mid 0X0 \mid 0X1 \mid 1X0 \mid 1X1 \\ Y &\to 1 \mid 0Y0 \mid 0Y1 \mid 1Y0 \mid 1Y1 \\ \end{align}$

---
Tags: formal-languages, context-free, pushdown-automata, pumping-lemma, open-problem
---


# Question
Title: What are the drawbacks of using an algorithm that is not backwards stable?
(This question might be legitimately crossposted to stackoverflow or mathoverflow or programming StackExchanges.)

# Preface

I'm reading this paper on solving linear systems of equations `Ax = b` using an explicit inverse (held by conventional wisdom as a big no-no): Druinsky & Toledo, "How accurate is inv(A)\*b?", http://arxiv.org/abs/1201.6035

It asserts that in non-pathological cases, calculating a solution to `Ax=b` via `inv(A)*b` using the explicit inverse of a matrix produces solutions that are as accurate and as stable as preferred methods such as via LU factorization. It goes on to describe exactly which situations using "inv" might be *bad* (technically, when the right-hand side, `b`, is nearly orthogonal to the subspace spanned by left-singular vectors of `A` with low singular values). Even in these cases, the paper asserts, the solutions of `inv(A)*b` are *as accurate* as preferred methods, they're just not backwards stable.

# Question

My question is: what are the specific drawbacks of using an algorithm that isn't guaranteed to be backwards stable? If all I wanted was some solutions to `Ax=b`, and I was guaranteed accurate results, does it matter that the solutions aren't backwards stable? Is there any specific examples of when it's ok to use an accurate but backwards-unstable algorithm?

# Furthermore

My experimentation in Matlab/Octave shows me that the difference between a backwards-unstable and -stable algorithm is that slight perturbations to the solution result in bigger errors when going back through the linear system:

```
norm(A * (inv(A) * b) - b)

```

is much larger than

```
norm(A * (A \ b) - b)

```

for a "bad" `b` (nearly orthogonal to the subspace of left-singular vectors with low singular values), where `\` solves linear systems using Gaussian elimination (http://www.mathworks.com/help/matlab/ref/mldivide.html). The solutions themselves have the same accuracy, i.e., `norm(A\b - true_x)` is about the same as `norm(inv(A)*b - true_x)`.

I can imagine that in the case that

1. I *only* cared about getting a solution to `Ax=b` and
2. knew I would *never* propagate the solution back through `A`,

could I justify using `inv(A)` when I didn't want to bother checking that `b` isn't "bad", i.e., without ensuring that the solution was backwards-stable. To me, this doesn't seem worth it, even without the speed and convenience advantages of using LU or Cholesky or QR decompositions.

# Answer
Sivan Toledo responded to my query with the following:

> In general, the significance and the broad-context meaning of mathematical results is a matter of opinion and debate, so perhaps not every researcher would agree to our explanation below.
>
> In most of the literature, backward stability is a technical and/or analytic tool that makes it relatively easy to prove that an algorithm produces accurate results (or to bound the inaccuracy). In these contexts, the user of the numerical method worries about accuracy, not about backward stability, and the numerical analyst uses backward stability just as a mechanism to prove the bound that the user cares about.
>
> (The analysis in our paper proves accuracy without relying directly on backward stability, but this is atypical.)
>
> When an algorithm is backward stable, the user gets not only a bound on the magnitude of the error, but also an estimate of its direction; it lies in the direction of right singular vectors that correspond to small singular values (for the case of solving linear equations). In many cases this is completely meaningless to the user.
>
> Backward stability may be meaningful to the end user if the parameters of the problem (say the coefficients of a linear equation) are only known approximately, say because they are measured or estimated using some limited-accuracy physical instrument. In some of these cases it may be good for the user to know that the output she/he got is an exact solution to a nearby problem.

I'd still like to better understand theoretically what the drawbacks of using `inv(A)*b` are when `b` is "bad". That is, if the solution using `inv` is as accurate as with a "better" algorithm, what really matters. (This is hinted at computationally in my question: the projection matrix `A * inv(A' * A) * A'` is at least unreliable.)
> 1 votes

---
Tags: linear-algebra, numerical-analysis
---


# Question
Title: Get nodes that are participating in any cycle in a graph
I have a problem that states the following :

> Given a cyclic graph , output for each node if the node removes all cycles in the graph.

The most trivial way to do this is using a Union-find disjoint set , and for each node , try **not** putting it in the Union-find disjoint set , if there are no cycles , then this node should output "Yes" , otherwise "No".

This approach would take about $\Theta(N^2)$ time and $\Theta(N)$ memory.

The problem also stated that $N \leq 1,000,000$ which would definitely get a TLE (Time Limit Exceeded) Answer on any problem.

So, my question is, What's the algorithm that would take $\Theta(N \lg N) $ or $\Theta(N)$ time and $\Theta(N)$ memory?

# Answer
First use Tarjan algorithm to find all of the bridges in the graph. Then remove all of them. Remaining graph should be made of some cycles, such that all of them have at least one common vertex, otherwise we can return false for all vertices. Is possible to check this with DFS, further reasoning is easy, total running time is $O(|V|+|E|)$.
> 5 votes

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


# Question
Title: Minimum number of vertices to remove to bound the largest connected component of a graph
I have this problem, maybe anybody could help.

Given a graph $G = (V, E)$ and an integer $k \geq 1$, find the minimum number $l$ of vertices to remove to make the largest connected component of $G \setminus \\{v\_1, \dots,v\_l\\}$ have at most $k$ vertices.

I wonder it this problem can be solved quickly (in polynomial time)?

(Related: finding the vertices when $k$ is small)

# Answer
The optimization version of this problem is known as Graph Integrity, which is unfortunately NP-Hard problem:

> The integrity of a graph G, denoted $I(G)$, is defined by: $I(G) = min\\{ |S| + m(G − S) : S \subset V (G) \\}$ where $m(G − S)$ denotes the maximum order of a component of $G − S$;
> 5 votes

---
Tags: graphs, np-complete, combinatorics
---


# Question
Title: Longest subsequence such that A[i].x < A[i+1].y
I have an issue for which I am looking for an algorithm (if it exists)

What I have: An array of items which have certain properties, e.g. item $A$ has properties $x$ and $y$.

Example: $\[ A(x,y), B(x,y), C(x,y), D(x,y), E(x,y) \]$

What I want: A result list consisting of elements of the original list, such as $\[ A(x,y), C(x,y), E(x,y) \]$, for which the following properties are true:

* No reordering of elements, they are in the same order as the original list
* The result has the maximum number of elements, i.e. the longest 'path' possible
* For each pair of consecutive items $(A(x,y), B(x,y))$ in the result, $A.x \lt B.y$. In other words, an item's $x$ must be less than the next item's $y$.

Complexity: The list in the case I have is about 35 items long, so an algorithm which is $O(n!)$ might not work.

Does such an algorithm exist?

# Answer
It's easier to change notation. Suppose the array is $A$, with the $i$-th element denoted $A\[i\]$ for $i=1,2,\dots,n$, and that element $i$ has attributes $A\[i\].x$ and $A\[i\].y$. Associate a directed graph $G$ with the array as follows. The vertices of $G$ are the indices $1\dots n$ of the array. Vertex $i$ is connected to vertex $j\ $ if *both* conditions $i\<j$ and $A\[i\].x \< A\[j\].y\ $ hold.

You are then asking for a longest directed path in $G$.

Note that $G$ is actually acyclic, since the arcs form a subset of the usual order on the set $\\{1,\dots,n\\}$. Any standard linear algorithm can then be used to compute the longest path, such as a topological sort.
> 5 votes

# Answer
So, your comparison is based on numerical properties x and y? If this is the case, then do some kind of sorting algorithm first, and adjust the order after sorting so that your condition of no reordering holds (that is delete those elements that are not at the correct location).
> -2 votes

---
Tags: algorithms, sorting, subsequences, lists
---


# Question
Title: Simple examples of Artificial Intelligence
I am having trouble understanding the concept of AI.

Is AI just a software that uses Probability, Linear Algebra and some advanced Mathematics to make independent decision ?

Please give me some simple examples of AI.

# Answer
> 6 votes
Artificial Intelligence is a catch-all term for a large collection of everything from philosophical questions down to very specific programming techniques.

At heart, AI comes from the question *is it possible to build a machine that displays intelligent behavior to the same level as human beings?* This is often clarified with examples like, can we build a machine that plays chess, composes a sonnet, tells a joke or recognizes kittens. Investigating this question has led to the distinctions between strong and weak AI, and thought-experiments like the Turing test and the Chinese room.

On the more practical side, there is a collection of techniques that are being used to (partially) solve some of these problems. For instance, we can build a machine that beats any human at chess or checkers. Computers can recognize objects in images with reasonable accuracy. They can diagnose diseases, sometimes better than doctors, they can parse a sentence into its constituents and make a reasonable mapping to the meaning behind it.

Many of these algorithms and techniques use probability, linear algebra, logic and a variety of other subjects, but that's just a matter of using what works. There are plenty of systems that use linear algebra that have nothing to do with AI. What makes a technique AI is that, in some sense, it attempts to behave intelligently.

A precise definition beyond that is difficult to give. The trouble with defining AI is that it's the study of something that doesn't exist yet, and we don't know that it ever will. But we're pretty sure that we'll know it if we see it.

# Answer
> 2 votes
An easy example is Artificial Intelligence in (video) games ("Game AI").

In 1997 Deep Blue won a six games match against Garry Kasparov and (*in my opionion*) that match is a milestone in the A.I. history: for the first time a computer beated a human in one of the most ancient, famous and "intelligent" game (though recently the relation between chess skill and IQ has been disproved). Nowadays most people think that a computer could easily beat the best chess players.

Modern video games often make large use of "A.I." and you can find a lot of documentation/references online about the techniques and approaches used.

# Answer
> 1 votes
There is no proof that a computer can make an "independent decision". In fact, there is no real proof that humans can, either...

Perhaps the AI "holy grail" is the Turing-Test.

In practice, AI covers, or touches a wide range of topics, from theorem-proving, planning, decision-making, multi-agent systems, some machine learning, and many more. Try reading this.

As for your description of AI: not every AI program uses any of the concepts you suggested, and not every program that uses them is considered AI. So in that sense - no. But any program that is implemented to solve some task which is considered as AI (e.g. an autonomous car driver), is considered as AI.

Also, this rather amorphic concept is often referred to as "weak AI", as opposed to "strong AI", which refers to machines that can "think for themselves", which is something that we don't have (yet).

---
Tags: terminology, artificial-intelligence
---


title: Is there a name for this kind of graph?

text:
# Question
Title: Is there a name for this kind of graph?
Is there a name for the DAG obtained from a directed graph by collapsing together the strongly connected components?

# Answer
The graph you describe is called the **condensation** of the original graph.
> 5 votes

---
Tags: graphs, terminology
---


# Question
Title: How is a hypergraph different from a bipartite graph?
How is a hypergraph different from the bipartite graph generated from the hypergraph by introducing new vertices for each hyperedge, and connecting these vertices with the vertices connected by the original hyperedge. Alternatively, I could also start with a bipartite graph, designate one of the sets of vertices as the hyperedges, and connect these hyperedges with the vertices connected to the original vertices.

Is there anything wrong with this construction? Are there theorems about hypergraphs that don't have a natural interpretation in terms of the bipartite graph just described?

---

I haven't read in detail what vzn is proposing here, but this got me interested in the question whether hypergraphs are really non-trivial generalizations of graphs. I googled for hypergraphs (and Wikipedia indeed also described the construction given above) and searched stackexchange and mathoverflow, but somehow hypergraphs are always treated as a non-trivial generalization of graphs, and somehow considered to be much more complicated than graphs. Don't read too much into this question, I have neither done an excessive literature research nor thought too deeply about hypergraphs. (Perhaps I even accidentally searched for multigraph instead of hypergraph, but I don't think so.)

# Answer
in math/cs in a sense many different objects can be seen as equivalent to other types of objects, but it seems more "natural" to study certain forms in certain contexts. for example a hypergraph is equivalent to a set of bitvectors, a SAT formula is also, etcetera.

> is there anything wrong with this construction?

cant actually follow your descriptions from your words. you need to use mathematical notation, but yes in general one can convert between hypergraphs and graphs using different natural schemes. in fact that is part of many theorems on the subject of hypergraphs is ironing out these subtleties, finding the hypergraph "analogs" of basic graph theorems. and notice that two objects are equivalent if you can show there are functions ("constructions") $f,f^{-1}$ such that $f(x)=y$ and $f^{-1}(y)=x$ ie a mapping and an inverse, which you didnt actually sketch out.

wikipedia actually does give such a construction for "the bipartite graph model of hypergraphs" ie converting it to the *incidence graph* of the hypergraph.

> Are there theorems about hypergraphs that don't have a natural interpretation in terms of the bipartite graph just described?

a ref I should perhaps have cited in that post which inspired it to some degree, which seems to me very comprehensive, wideranging, and pointing to some future developments, and should answer this question in a more general way—ie "why hypergraphs" versus other approaches—is:

an interesting perspective on hypergraphs is that in a sense they are a *"fractional"* generalization of *"integer"* graphs. in other words, a kind of "apparently natural" generalization in the way that fractional numbers are a generalization of integers. from p.viii, which also links it in to other trends in math:

> This example illustrates the theme of this book, which is to uncover the rational side of graph theory: How can integer-valued graph theory concepts be modiﬁed so they take on nonintegral values? This “fractionalization” bug has infected other parts of mathematics. Perhaps the best known example is the fractionalization of the factorial function to give the gamma function. Fractal geometry recognizes objects whose dimension is not a whole number \[126\]. And analysts consider fractional derivatives \[132\]. Some even think about fractional partial derivatives!

to further quote from the introduction by Berge:

> By developing the fractional idea, the purpose of the authors is multiple: ﬁrst, to enlarge the scope of applications in Scheduling, in Operations Research, or in various kinds of assignment problems; second, to simplify. The fractional version of a theorem is frequently easier to prove than the classical one, and a bound for a “fractional” coeﬃcient of the graph is also a bound for the classical coeﬃcient (or suggests a conjecture). A striking example is the simple and famous theorem of Vizing about the edge-chromatic number of a graph; no similar result is known for the edge chromatic number of a hypergraph, but the reader will ﬁnd in this book an analogous statement for the “fractional” edge-chromatic number which is a theorem. The conjecture of Vizing and Behzad about the total chromatic number becomes in its fractional version an elegant theorem.

so in short one can indeed apparently prove some novel ideas with hypergraphs that are not really yet formulated in terms of graphs and one would expect this trend to continue in active research. but note that graph theory plays a core role in hypergraphs. so in a sense there are the apparent beginnings of many **bridge theorems**.

another interesting angle that shows recent advance and possibly some future promise in the area: Fields-prize winning Gowers somewhat recently generalized the Szemeredi regularity lemma to hypergraphs. Szemeredi recently won the Abel prize (2012) in part for that work.
> 1 votes

# Answer
> Essentially, a hypergraph may be "nice" in some sense, but there may be no equivalent (or at least natural) corresponding notion of niceness for the associated bipartite graph.

One way to approach the question is by analogy with graphs. Every graph can be represented by its incidence graph, a bipartite graph with vertices in one partition, and edges in the other. Yet we seldom want to use this "standardised" bipartite representation of graphs, for a variety of reasons. The same reasons (and more) apply to keeping hypergraphs as they are.

You comment below that this analogy with the graph case was your starting point. Perhaps we have a different set of intuitions about why turning every graph into a bipartite graph is unnatural, so instead let me try another tack.

First, there are many different notions of what a hypergraph is, depending on the application.

One rather general definition is a *set system*, which allows the set of edges of the hypergraph to be a subset of the powerset of the vertices. This allows empty edges, edges with size one, edges that are strictly contained in other edges, and some vertices may also not participate in any edge. There are versions of hypergraphs that disallow some combination of each of these "features". These features are important for some applications, and authors tend to rely on them implicitly, so it is worth checking the definition each time.

The best reference I know is Berge's book. Note that it is essentially a reprint of the second half of his 1973 book on graphs and hypergraphs, and is quite hard to use: it is a useful reference but I can't wholeheartedly recommend it. Berge requires in a hypergraph that there are no empty edges and that every vertex should be part of some edge, but allows repeated edges (giving a multiset of subsets of the powerset). He calls a hypergraph with no edge contained in another a *simple* hypergraph.

* Claude Berge, *Hypergraphs: Combinatorics of Finite Sets*, 1989, Elsevier.

If one disallows edges that are contained in other edges, but allows empty or singleton edges and repeated edges, then the dual graph of the hypergraph that you describe (usually called the *incidence graph* of the hypergraph, or sometimes referred to as its Levi graph) is a bipartite graph. Further, the hypergraph can be reconstructed from its incidence graph.

Sometimes this is perfectly appropriate. However, useful things do get scrambled if one breaks this particular shell. As an example, various notions of colouring are interesting for hypergraphs, but these are highly unnatural in the bipartite graph setting. Many other properties of classes of hypergraphs are also scrambled going to the incidence graph.

Perhaps the best part of Berge's book is its continual insistence (with many examples) that hypergraphs really are worth studying, and that they do nontrivially extend graphs.

*Edit:* clarified terminology, as suggested by vzn's answer.
> 5 votes

---
Tags: graphs, terminology
---


# Question
Title: Find all items which are subsets of an item
I have a problem that I think should have been studied. I am looking for algorithms for it.

Each item is a set of key-value pairs. Let $x$ be an item and $F$ be a set of items.

Each key and each value can appear multiple times. The number of possible keys and possible values can be arbitrary large.

We are given $x$ and $F$. We want to find all those items $y$ in $F$ such that $y.val \subseteq x$.

For example,

$x = \\{(a,1), (b,2), (c,3), (d,4)\\}$

$F= \\{$
$(A, \\{(a,1)\\}), $
$(B, \\{(a,1), (b,2)\\}),$
$(C, \\{(a,1), (b,3)\\}),$
$(D, \\{(b,2), (c,3), (d,4)\\}),$
$(E, \\{(a,1), (b,2), (c,3), (d,4)\\}),$
$(F, \\{(a,1), (b,2), (c,3), (d,4), (e,5)\\}),$
$(G, \\{(a,1), (b,2), (c,3), (e,5)\\})$
$\\}$

The answer is: $A$ yes, $B$ yes, $C$ no (right keys, wrong values), $D$ yes, $E$ yes (exact match), $F$ no, $G$ no.

Has this problem been studied?

The problem seems similar to finding features from a DNA sequence or detecting plagiarism in a document.

I asked this problem in theoretical CS stack exchange and did not get very helpful answers. https://cstheory.stackexchange.com/questions/18052/find-all-items-which-are-subsets-of-an-item

# Answer
Your problem is the same one faced by SAT solvers who want to eliminate subsumed clauses from a CNF formula. Any clause $B$ that contains a superset of the literals of another clause $A$ in the formula is redundant and can be removed without changing the satisfiability of the formula. We say $A$ subsumes $B$, so $B$ can be discarded. Instead of single valued literals, you have these item tuples but it is the same problem as finding $A$.

The algorithms used are refinements of the naive algorithm, where you iterate through each element of a potential subset, checking to see if it occurs in $x$. If you sort $x$'s items you can reduce the linear time search to log $\vert{x}\vert$. If you use a hashtable to store $x$'s items you can have amortized constant time for each search. Because of the hashing overhead, save this optimization for large sets. Bitmask signatures for each set allow you to do a cheap initial check, only doing the expensive iteration and searching of $x$ if the bitmaps can't rule out a subset match.
> 3 votes

---
Tags: algorithms, search-algorithms, sets
---


# Question
Title: Why/how does the definition of PCP use randomness?
I am confused by the definition of probabilistic checkable proofs.

Language $L$ has an $(r(n),q(n))$ - PCP verifier, if there is a PPA V satisfying:

**Efficiency**: $V$ uses at most $r(n)$ random coins and makes at most $q(n)$ nonadaptive queries to location of $\pi$.

**Completeness**: $x \in L, \exists \pi \in \\{0,1\\}^\*, Pr\[V^{\pi}(x)=1\]=1$

**Soundness**: $x \notin L, \forall \pi \in \\{0,1\\}^\*, Pr\[V^{\pi}(x)=1\]\leq\frac{1}{2}$

The main question:

* Why does PCP need randomness?
* How exactly are random coins used in the PCP?
* And what happens when these random coins are actually deterministic?
* Where does the effective proof length bound of $2^{r(n)}q(n)$ come from?

# Answer
The way a PCP works is like so: in order to verify some property, the prover presents a proof P which is "easily testable". The way to test it is to query the proof at a small number $q(n)$ of points. We want the PCP to satisfy two properties:

1. If the property actually holds, the verifier should always (or almost always) accept.
2. If the property doesn't hold, then the verifier would notice with some constant probability.

Now if the proof is long and the verifier only looks at a small number $q(n)$ of them, then they better be random! Otherwise it's very easy to fool the verifier. That should answer your first and third questions.

How are the random coins used? In an arbitrary way. The verifier chooses $r(n)$ random coins, and based on them queries the proof at $q(n)$ points. Then she applies a test which always succeeds in YES instances (the property holds), but fails with constant probability (over the coin tosses) in NO instances (the property doesn't hold). That should answer the second question.

Since there are $r(n)$ coins, there are $2^{r(n)}$ different outcomes for the coins, and so the verifier in total queries the proof in at most $2^{r(n)}q(n)$ different places. That answers your fourth question.

What's the point of a PCP? We can encode the verifier as a CNF whose variables are the bits of the proof: for each of the $2^{r(n)}$ coin tosses, there are clauses encoding that the $q(n)$ bits sampled pass the verifier's test. If it's a YES instance, then this CNF is satisfiable. If it's a NO instance, then the verifier fails with some constant probability, and so a constant fraction of the clauses in the CNF are always unsatisfied.

The PCP theorem gives a PCP for 3SAT with $q(n) = O(\log n)$ and $r(n) = O(1)$. That means that given a 3CNF, we can come construct a new CNF of length $O(2^{q(n)}) = n^{O(1)}$ using the construction outlined in the preceding paragraph such that (i) if the original 3CNF formula is satisfiable, so is the new one, (ii) otherwise, at most $1-\epsilon$ fraction of the clauses can ever be satisfied in the new CNF. That gives a hardness of approximation result for 3SAT.

Using Raz's parallel repetition theorem, Håstad obtained a construct in which in case (ii), at most $7/8+\epsilon$ of the clauses can be satisfied, thus obtaining an optimal inapproximability result. (It's optimal since a random assignment satisfies $7/8$ of the clauses; this algorithm can be derandomized using the method of conditional expectations.)
> 4 votes

---
Tags: complexity-theory, terminology
---