# Question
Title: Reduction from Vertex Cover to an Independent Set problem
Assume there exists some algorithm that solves vertex cover problem in time polynomial in terms of $n$ and exponential for $k$ with the run time that looks like this $O(k^2 55^k n^3)$. Can we claim that independent set can also be solved in time polynomial in terms of $n$ and exponential in terms of $k$ ? ($k$ here stands for the minimum size of an independent set)

# Answer
> 6 votes
No. The typical reduction from Independent Set to Vertex Cover doesn't preserve the parameter ($k$). A graph with a vertex cover of size $k$ has an independent set of size $n-k$, so we no longer have $n$ restricted to the polynomial part.

This separation is one of the basic conjectures of Parameterized Complexity. Parameterized Complexity is a bivariate complexity theory where problems are given with not only the normal input, but also a parameter. For example the (natural) parameterized version of Vertex Cover is:

> **Vertex Cover**
> *Input*: A graph $G$, a positive integer $k$.
> *Parameter*: $k$.
> *Question*: Does $G$ have a vertex cover of size at most $k$?

So each parameterized problem has two (formally explicit) metrics: the size of the input $n$, and the parameter $k$. We then say that a problem $\Pi$ is *fixed-parameter tractable* if there is an algorithm that decides each instance $(x,k)$ of $\Pi$ in time bounded by $f(k)\cdot|x|^{O(1)}$ for some computable function $f$ dependent only on $k$ (i.e. polynomial with constant degree in $|x| = n$, but essentially free in $k$). We call the class of all such problems $FPT$.

So Vertex Cover is in $FPT$ when parameterized by the size of the vertex cover.

The main intractability framework for Parameterized Complexity is called the $W$-hierarchy, a series of classes $W\[t\]$ where $W\[i\] \subseteq W\[i+1\]$ and $FPT \subseteq W\[1\]$. Although it's split into lots of classes, the $W$-hierachy bears a practical relationship to $FPT$ in a similar manner to that of $NP$ to $P$, in that if a problem is $W\[t\]$-hard for some $t$, then it has no $FPT$ algorithm unless $W\[t\] = FPT$, and we conjecture that $FPT \subset W\[1\]$ for similar reasons to $P \subset NP$.

Getting back to your question again, finally, it turns out that Independent Set is $W\[1\]$-complete when parameterized by the size of the independent set. That is, unless $W\[1\] = FPT$, Independent Set has no algorithm with running time bounded by $f(k)n^{O(1)}$ for any $f$, where $k$ is the size of the independent set.

*Additional Note*:

Of course we don't have to parameterize by the size of the answer, we can use anything we feel like, the normal guidelines are that it should be something that can reasonably be expected to be small compared to the input size, and it should be able to vary independently of the input size. A common structural parameter for example is the treewidth of a graph. You can parameterize by measures relating to the size of the input, but then we have to introduce a bunch of different classes.

---
Tags: graphs, np-complete, np, p-vs-np, parameterized-complexity
---


# Question
Title: Time complexity in Big O notation for Harmonic series with first k terms missing
Firstly, let's suppose there exists an algorithm where $i$ iterates from $1$ to $n$, spending $\frac{n^2}{i}$ time in each iteration.

Thanks to the well known $O(\log n)$ upper bound for the Harmonic series, the big $O$ notation of this algorithm comes to $O(n^2 \log n)$.

Now the actual algorithm that I am working on iterates from $k$ to $n$, where $1 \< k \< n$, spending $\frac{n^2}{k}$ in the first iteration, then $\frac{n^2}{k+1}$, $\frac{n^2}{k+2}$, $\frac{n^2}{k+3}$, and so on.

I've been trying to deduce the upper bound of this new algorithm, but I keep getting the same $O(n^2 \log n)$ time bound, which to me, is counter intuitive and a bit paradoxical, especially considering that the first terms of the harmonic series are the bigger and more significant terms. The time bound that I was actually expecting to get was $O(\frac{n^2}{k} \cdot \log n)$.

Could anyone please be able to shed some light onto this?

Thanks in advance for any help.

# Answer
We can estimate your sum using an integral: $$ \int\_k^{n+1} \frac{dx}{x} \leq \sum\_{i=k}^n \frac{1}{i} \leq \int\_{k-1}^n \frac{dx}{x}. $$ Evaluating the integrals, we obtain $$ \log \frac{n+1}{k} \leq \sum\_{i=k}^n \frac{1}{i} \leq \log \frac{n}{k-1}. $$ We can conclude that for $k \geq 2$, $$ \sum\_{i=k}^n \frac{1}{i} = \log \frac{n}{k} \pm O(1). $$
> 2 votes

---
Tags: time-complexity, lower-bounds
---


title: Efficiently finding key sets

text:
# Question
Title: Efficiently finding key sets
A few years ago I participated in German highschool computer science competition. One of the problems was this (slightly abbreviated):

> A somewhat unusual electronic lock consists of $n$ switches than can be turned on ($1$) or off ($0$). For economic reasons only $k$ of these switches are actually connected to the lock, the rest are dummies. It's impossible to tell these apart. The lock opens when all $k$ connected switches are set to the right combination, regardless of the setting of the dummy switches.
>
> If you want to open the lock without knowing the right combination, you could repeatedly setup the switches into different positions and then press open until the lock actually opens. Construct an algorithm that for a given pair $(n,k)$ finds a set of setups for all keys such that regardless of which keys are connected to the lock and of regardless what combination of those actually opens the lock, one of the setups will open the lock. Try to construct an algorithm that computes a minimal set.

The solution that I coded (which is more or less equal to the reference solution) works like this:

1. Let $S$ be the set of all setups in the output.
2. Generate $M$, a set of $m$ setups randomly where $m$ is a customizeable parameter
3. For each element of $M$, compute how many combinations it covers that were not already covered
4. Add the element of $M$ that covers the most new solutions to $S$
5. For each element of $S$, check if if you remove it from $S$, the number of solutions covered by $S$ would fall. If that is not the case, remove that setup from $S$.
6. If $S$ covers all possible combinations, terminate.

---

Can somebody explain me better ways to solve this problem? Is it possible to find a minimal set of setups in reasonable aka polynomial time (the reference solution hints that this is not possible)?

# Answer
Your problem is discussed in the paper *Efficient construction of a small hitting set for combinatorial rectangles in high dimension* by Linial, Luby, Saks and Zuckerman. The object you're after is called a $(2,n,2^{-k})$-hitting set in the paper (this notation is not standard). They construct such a set of size $\mathrm{poly}(2^k\log n)$ in time $\mathrm{poly}(2^k n)$, and give a lower bound of $\Omega(2^{k+1} + \log n)$. Their construction certainly doesn't produce a *minimal* hitting set, and they're not necessarily interested in your range of parameters, but perhaps you could chase the literature from there on and find more relevant material.
> 8 votes

---
Tags: algorithms
---


# Question
Title: Reducing from Hamiltonian Cycle problem to the Graph Wheel problem
EDIT: This question is different from the other in a sense that unlike it this one goes into specifics and is intended to solve the problem. In the previous post, the only answer was a hint. In this post, the answer is a proper solution.

Is there a way to "polynomialy" reduce the problem of finding graph wheel $W\_{n}$ to the problem of detecting Hamiltonian Cycle (or vice versa) ? The ultimate goal is to show that finding $W\_n$ is NP-complete problem. So far I can show that the problem is in NP. To show that I claim that given an input of graph it is possible in polynomial time to check every vertex and to make sure that it has three edges(except the hub): one goes to the hub, one goes to the next vertex and one to the previous vertex. By checking every vertex in this fashion one can make sure the "ticket" indeed represents $W\_{n}$.

As far as converting from the Hamiltonian Cycle problem to the problem of fining $W\_n$ goes I have encountered that $W\_n$ has many Hamiltonian cycles inside it.It is easy to see if one imagines a wheel with a hub and bunch of spokes. Every triangle created by the spokes forms a Hamiltonian cycle as well as any other "closed loop" formed inside a given $W\_{n}$.

The intriguing part is the fact that only one vertex is in "the way" and that vertex is the hub. Is the hub of the wheel main culprit in figuring out the conversion ?

# Answer
We will add one extra vertex $v$ to the graph $G$ and we make new graph $G'$, such that $v$ is connected to the all other vertices of $G$. $G$ has a Hamiltonian cycle if and only if $G'$ has a $W\_{n+1}$. It is easy to check that if $G$ has a Hamiltonian cycle then $G'$ has a $W\_{n+1}$ wheel (just set $v$ as a center). On the other hand, if $G'$ has a $W\_{n+1}$ then there are two possibility:

1. $v$ is the center of $W\_{n+1} \rightarrow G $ has a Hamiltonian cycle.
2. Another vertex $u$ is the center of $W\_{n+1}$ in $G'$. So both $deg(u) = deg(v) = n$. Then we can change the labeling of this two vertices (actually they are equivalence under isomorphic), now we have again first possibility.

P.S1: By $W\_n$ I mean the wheel with $n$ vertex.

P.S2: In this proof we say if we fix $k=n+1$ (size of the artificial graph), then the problem is NP-Complete in this restricted version, So it's also NP-Complete in the case $k$ is as input parameter.
> 2 votes

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


# Question
Title: What does it mean to say that a language is "effectively closed" under an operation?
I've been reading some formal language theory papers, and I've come across a term that I don't understand.

The paper will often refer to a set being "effectively closed under intersection" or other operations. What does "effectively" mean here? How does this differ from normal closure?

For reference, the paper I'm seeing these in is:

M. Daley and I. McQuillan. Formal modelling of viral gene compression. International Journal of Foundations of Computer Science, 16(3):453–469, 2005.

# Answer
> 15 votes
"Effectively closed" means that the family is closed under the operation, and that the closure can be computed by giving an automaton/grammar for it (if the original languages are also given in such an effective representation). E.g., given a finite state automaton, we can actually find an automaton for the complement.

Then it is a natural question, whether there are examples of closure properties that are *not* effective. I know one right now. For a regular language $R$ and *any* language $L$ the quotient $R/L$ is again regular. There is no effective way to construct a FSA for that quotient if $L$ is e.g. recursively enumarable.

---
Tags: formal-languages, terminology, computability, automata, closure-properties
---


# Question
Title: How can Computer Science theories and inquiries be resolved?
It's probably possible to prove that P ≠ NP, that one-way functions exist, and that parity games cannot be solved in polynomial time (yes, I've been reading through this list), but how would we go about proving any of those things? Have there been any proofs to any computer science theories, or answers to any substantial computer science questions (such as the ones in that list)? Are they like mathematical proofs (such as Grigori Perelman's resolution to the Poincaré conjecture)? I know that the P versus NP problem seems out of my league, being a junior in high school, but it's a problem that intrigues me, and I would really like to see how others (if any) have answered other, related questions, because I would like to look into a resolution to the problem.

This isn't a duplicate of this question primarily because physics isn't computer science, and secondarily because, unless I'm mistaken, computer science theories are not proven the same way that theories related to physical sciences are proven. They're more like mathematical proofs in that they're logical (right?).

# Answer
> 9 votes
I would disagree on a few counts.

I don't think it's "probably" possible to prove $P \neq NP$. I certainly don't think it's impossible, but Gödel's incompleteness theorems tell us that there are some sentences in a logical system which are true but which can't be proven.

You ask if there have been proofs to Computer Science theories. There have been thousands at the very least. These vary from insignificant to huge. I'll mention some of the most relevant (aka my favorite) ones here.

* Some problems cannot be solved by ANY algorithm. No matter what. Ever. An example of this is determining if a computer program will run forever. There is no way to look at a program and be guaranteed a yes/no answer for if it will run forever.
* The functions which can be computed by a Turing Machine are the same as functions which can be computed by the lambda calculus, are the same as practically every programming language. Basically, though speed might differ, all turing-complete programming languages (which is most of them) can solve the same set of problems.
* The types of a computer program are directly related to its proof of correctness. This is called the "Curry-Howard Correspondence", and is quite complex, so I won't go into the details here. Note that by types I mean things like integer, string, list, array, etc.
* A list of real numbers can't be sorted in faster than $\Omega (n\log n).$ This means that no matter what algorithm you use, in the worst case it will take approximately $n\log n$ steps to sort that list.
* A large number of problems are, at their core, the same problem. If you've ever heard of NP-complete problems, what that means is that these problems all boil down to satisfiability. They are from graph theory, combinatorics, scheduling, and a variety of areas, but ultimately, they are all just checking if there's some input to a logical formula of ORs and ANDs which will spit out true as the overall result.

Note that these are all necessarily complex topics, which I have simplified to give you a taste of the sort of things provable in computer science.

You ask how Computer Science theories are proven. The problem is that Computer Science is an incredibly diverse field, and it really depends on your sub-field. Theory of computation, programming language construction and formal AI ("neat" AI) are highly mathematical, and are based heavily on logic and proofs.

However, there are many sub-fields which are much more experimental. Human-Computer interaction or anything having to do with the human side of computing will rely heavily on studies and experiments involving users. Operating Systems, Graphics and Compilers will rely heavy on performance evaluations, seeing which programs are fastest in the real word, not just on paper.

If you are in Junior High, I think there are many computer science problems which are in your reach. Because it is such a young field, there are many unsolved CS problems which are relatively simple to understand. Unlike physics, where you need tons and tons of calculus background, CS really relies on simple logic. If you can learn induction, logic and the basics of discrete structures (graphs, strings, etc.), I think there are probably lots of concepts that are accessible to a Junior High student.

# Answer
> 11 votes
Theoretical computer science, to which the questions you state belong, is part of mathematics, and the methods used to resolve questions are the same ones used elsewhere in math, namely the method of proofs. The questions you list are notoriously difficult, and seem to be out of reach for current methods.

In the past, the methods used to attack questions of the sort you describe were purely combinatorial. Recently, Ketan Mulmuley and his students have come up with a different method which employs representation theory (via some algebraic geometry), and is conjectured by them to be one day strong enough to resolve the P versus NP question. Currently, though, the only questions within reach of their methods are algebraic ones like permanent versus determinant rather than Boolean ones like P versus NP.

Since it is widely (though not universally) believed that P is different from NP, many results are proved conditional on this assumption. That is, they hold only if P is indeed different from NP. The area of hardness of approximation, which studies how well different combinatorial problems can be approximated in the worst case (in polynomial time), is a good example: all results in this area are conditional on P versus NP or on some even stronger assumptions.

# Answer
> 4 votes
when you say its "probably possible" to solve key/hardest unsolved open problems in CS that is mere "beginners mind" or \[more harshly but honestly, uninformed-\] speculation. anyone who realizes that eg P vs NP has been open for over 4 decades \[*over double your own age!*\] will have to admit that its long history of no resolution, and an unclaimed $1M prize over a decade old, are some circumstantial evidence the possibility of unprovability is not negligible. as I read a poll of theorists,\[2\] about 4-5% say they think its unprovable or equivalently, "independent" of basic arithmetic axioms (it is indeed apparently a small minority view among experts).

there is even an award-winning paper by Razborov/Rudich called Natural Proofs that, under some interpretations, gives some evidence of unprovability, by showing \[roughly, informally\] such a proof if it exists must be fundamentally different from any known "similar" proofs ever devised (or in a strictly defined formal sense "*unnatural*"!). & you should learn about problems that *were* proven undecidable after long being open eg Hilberts 10th problem (open ¾-century).

yes, most major CS proofs at the core are math proofs "under the hood", sometimes highly technical, using elements of eg combinatorics, extremal graphs & extremal combinatorics. the nearest existing proofs to P$\neq$NP are arguably proofs by Razborov & later researchers about monotone circuit lower bounds. there is an undergraduate level presentation \[possibly the most accessible ever published\] in Models of Computation by Savage. see also Lance Fortnows new book, The Golden Ticket.

as an exotic/longshot wildcard footnote, there is some speculation and enthusiasm in math & TCS even by some elite experts (eg WT Gowers) that automated proof technology might someday become much more powerful eg semi-creative and almost AI-like.\[1\] sci-fi scenarios aside, nevertheless it has succeeded with breakthroughs at times on some isolated but very difficult problems such as the 4 color theorem and Keplers conjecture.

another approach for P vs NP might be to work from a proposed proof outline\[3\] or team up with other people working on the problem.\[4\]\[5\]\[6\]

\[1\] adventures & commotions in automated theorem proving, vzn

\[2\] P vs NP poll by Gasarch

\[3\] outline for a NP vs P/poly proof based on monotone circuits, hypergraphs, factoring, and slice functions, vzn

\[4\] Jun Fukuyama P vs NP page

\[5\] monotone circuits tcs.se chat room

\[6\] RJ Lipton P vs NP blog

# Answer
> 0 votes
The resolved ones obviously aren't on that list... burning questions were the halting problem, what is meant by "algorithm", defining a reasonably "machine independent" way of saying when a solution to a problem is "efficient". The analysis of algorithms is a completely new area, with a rich collection of results. The list goes on.

---
Tags: epistemology
---


# Question
Title: Find the longest subsequence of two strings
I want to know which is the best way to find the longest common subsequence of two strings

# Answer
> 1 votes
You know the recipe for dynamic programming: define some subproblems, then show how to use solutions to smaller subproblems to help you solve larger subproblems. So, what you have tried as candidate subproblems?

Hint: When you have a dynamic programming problem that takes a string as input, what are some candidate ways to define subproblems? (Prefixes, suffices, substrings...) Now, how might you apply that general advice here?

I'm not going to spell out the full answer, as this sounds like homework, and to learn from homework, you need to struggle with it yourself.

---
Tags: algorithms, algorithm-analysis, dynamic-programming, subsequences
---


title: PDA with 2 stacks

text:
# Question
Title: PDA with 2 stacks
I urgently need a language which can be recognised by 2 PDA's but not with 1 PDA.

# Answer
A machine using two pushdowns accepts the recursively enumerable languages. So there is a lot to choose from. Look for your favourite non-context-free language, and build a two-stack machine for it!

(added. see also the answer obtained via our sistersite math) The languages $L\_1 = \\{ a^nb^nc^n \mid n\ge 1 \\}$ and $L\_2 = \\{ a^nb^ma^nb^m \mid m,n\ge 1 \\}$ are typical examples of non-context-free languages. They are easily recognized using two pushdowns. E.g., for $L\_1$ store the number of $a$'s on both stacks; it can then be used to check both the number of $b$'s and $c$'s.

We can also shift the symbols from one stack to the other while doubling them. staring with $1$, and iterating we obtain powers of two. Note $\\{a^{2^n} \mid n\ge 1\\}$ is another example of a non-context-free language.

By my earlier remark $\\{ ww \mid w\in \\{a,b\\}^\* \\}$ is another example, and makes a nice puzzle.
> 11 votes

---
Tags: formal-languages, pushdown-automata
---


title: Amdahl's Law and Computer Science

text:
# Question
Title: Amdahl's Law and Computer Science
I would like to learn more about Amdahl's Law and other similar topics. In what branch of computer science would one place Amdahl's law? Could someone point me to a textbook or further reading (aside from Wikipedia or other sites that are found on the first page of a Google search) that discusses it?

# Answer
> 3 votes
Amdahl's Law is perhaps most associated with computer architecture (Gene Amdahl was a computer architect). Although initially applied to the potential speedup from partial parallelization of a task, the formula applies to the benefit from any partial improvement.

In its general form, it can be applied to many different types of problems. E.g., the improvement in voter turn out by getting a fraction of potential voters to always vote.

Since it is a rule of thumb intended to compensate for excessive expectations from dramatic improvements in part of a system, it is most useful when the improvement factor is large and is intended more for quick estimation (and generally the best case--though sometimes an improvement can unexpectedly benefit other aspects) than an exact measurement (as systems tend to have complex and subtle interactions). (Quick estimation facilitates quick pruning of paths of exploration.)

As a mathematically based rule of thumb, it is not an especially deep topic (rules of thumb based on history, economics, etc. are generally more susceptible to discussion), though Gustafson's Law points out that context is important. However, Amdahl's Law is an important corrective to optimism with respect to dramatic (but partial) improvements.

---
Tags: reference-request, parallel-computing
---


# Question
Title: Problem regarding Turing Machine notation
Here I have a Turing Machine (sorry for awful drawing):

So, I have a question regarding the usage of `a` here. It is treated as a variable here. But since it doesn't alter input tape in any way, shouldn't it be stored in an implicit storage? My question is if this implicit storage (tell me if I am wrong) is in conflict with the fact that a Turing Machine only has a single input tape.

My hunch is that it is syntactic sugar and it can be explicitly defined with less-intuitive notation (another input tape?), but I am not sure.

# Answer
Unless I'm misunderstanding the diagram, the way to replace it is with a transition for every letter in your tape alphabet.

Say your tape alphabet $\Gamma = \\{ 0,1,2,3 \\}$, plus the blank symbol. Then you would have a transition from $R$ to $La$ when reading 0, another when reading 1, another when reading 2, another when reading 3, but NOT one when reading a blank.

You are right in your intuition that this is just syntactic sugar. What it is really doing is using one transition to represent several.
> 4 votes

---
Tags: turing-machines
---


# Question
Title: Is there an always-halting, limited model of computation accepting $R$ but not $RE$?
So, I know that the halting problem is undecidable for Turing machines. The trick is that TMs can decide recursive languages, and can accept Recursively Enumerable (RE) languages.

I'm wondering, is there a more limited model of computation which accepts only recursive languages, and not RE? And if so, is there such a model which is always guaranteed to halt?

Obviously this model would be strictly less powerful than TMs and strictly more powerful than PDAs.

I'm open to a machine-style model, or a lambda-calculus style model.

As an example of what I'm thinking: the Coq language has a restriction that for any self-recursive calls, the first argument must be strictly decreasing in "size" i.e. if it is a natural number, it must be smaller, if it is a list, it must be shorter, etc. This guarantees that it always halts, but I have no idea if you can compute all of R this way.

# Answer
> 9 votes
Yes, there are as many models of R as there are of RE! Take a model of RE, and restrict it to the total elements of the model. For example, take Turing machines that halt. Or take total recursive functions. Or take your favorite programming language (idealized to remove memory limitations) but in addition to requiring that the source code be syntactically valid, also require that the program halt on every input.

The catch is that, since the halting problem is undecidable, for any model of R, given a recursive syntax for the elements, there cannot be any algorithm to decide whether a candidate element is valid. For example, a normal programming languages has syntactic rules, and sometimes a type system, to decide whether a program is well-formed; the parser or type checker implements a decision procedure to verify that the source code is an element of the language. If you want a programming language that is a model of RE rather than R, there is no way to decide whether some source code is a valid program.

Coq only allows a subset of all recursive functions: $\mathsf{Coq} \subsetneq \mathsf{R} \subsetneq \mathsf{RE}$. Both bounds of this inequality chain have decidable models but the middle item doesn't. Intuitively speaking, Coq only contains recursive functions whose termination can be proved by sufficiently simple arguments. While “sufficiently simple” covers just about anything mathematicians do, it is still very limited in a theoretical sense. (More precisely, Coq's theory is equivalent to I think the Peano axioms with a schema for recursion that goes up to a certain ordinal, but at that point it gets beyond my comprehension.)

# Answer
> 5 votes
For the reasons given by Gilles, there can't be a formal system that represents all total computations. If you had such a system, you'd have a system equivalent to all halting Turing machines. But the halting problem tells us that you can't decide if a machine halts or not, so you wouldn't be able to decide if an element (a Turing machine) belongs to the system or not.

However, you can get very close. Good formal models for this problem are (strongly) normalizing typed lambda calculi. This means that every term has a normal form - a definite result that you can obtain by a finite number of application of reduction rules. In other words, every computation has a result, every computation is total. The stronger system you have, the more total functions you can express in it (although you can never express all).

A nice example is System F, also known as the polymorphic lambda calculus. There is a theorem that says that

> A function (on natural numbers) is expressible in System F if and only if it can be proved in the second order Peano arithmetic that the function is total.

This means that in System F you can express basically all imaginable total functions. So although you can't express all total function, you can express all total functions for which you can prove they're total, which is basically the best thing you can do.

There is a bit weaker system, Gödel's System T, for which there is a very similar theorem for *first* order Peano arithmetic. However this system is not as nice as System F. (In System F you can represent natural numbers, booleans etc. natively, while System T is constructed as the simply typed lambda calculus with externally added naturals and booleans. Also System F has type polymorphism, which makes it much more elegant in many cases.)

You can find all the details about these systems in *Girard, Lafont and Taylor, Proofs and Types. Cambridge University Press, 1989, ISBN 0-521-37181-3.*

Coq is based on a even stronger calculus of constructions, which is also strongly normalizing, so in Coq you can describe even more total functions.

---
Tags: computability, turing-machines, lambda-calculus, computation-models, halting-problem
---


# Question
Title: Converting an NFA to regex using GNFA algorithm?
So I've been trying to crack this for a long time and almost feel like I am going in loops about this question.

Given the following NFA:

Using the GNFA algorithm get the regular expression.

I understand that you would have the following for the first step(adding empty states):

The next step would be removing the state \[q1\] I would get:

Finally removing \[q2\] would get:

However the answers others have got is: $(a \cup bb^\*a)^\*bb^\*$ Which does not make sense as I got, $a^\*b(b \cup aa^\*b)^\*$? A GNFA(generalised nondeterministic finite automaton) is described as follows:

A GNFA is similar to an NFA but must obey certain rules:

* It has only one accept state
* The initial state has no transitions coming into it
* The accept state has no transitions coming out from it
* A transition can denote any regular expression, rather than just a symbol from the alphabet Note that a symbol is a kind of regular expression.

Furthermore, We may convert an NFA into a GNFA as follows:

* Add a new start state with an ε-transition to the old start state
* Add a new accept state with ε-transitions from the old accept states
* If arrows have multiple labels, or if there are multiple arrows between two states, replace them with the union (or) of those labels

# Answer
> 8 votes
Do you want to know why "the others" obtained a different expression?

When constructing a regular expression, there is no unique correct answer. There are usually several expressions "that make sense." In this case, you use the state elimination method (I learned this under the name of Brzozowski and McCluskey). Here, the order of removal determines the expression found. So, what do you get when removing $q2$ first?

You can also do "clever tricks" during the construction. In your example, you have $b\cup aa^\*b$, which is equivalent to $a^\*b$.

---
Tags: automata, finite-automata, regular-expressions, nondeterminism
---


title: relational algebra and SQL

text:
# Question
Title: relational algebra and SQL
Using the following relations:

```
consultant(id,Name,Skill)

CustomerCompany(Id,name Address, Phone, Email, WebAddr,Market)

project(id,StartDate,EndDate,ConsultantID,CustomerId,Days)

Invoice(id,Date,Customer,Amount,Status)

```

Im trying to work out the following scenario using SQL and Relational algebra

Find the names of the consultants and the names of customers, where the consultant has worked for the customer, and the customer received an invoice in the range of GBP 100k to 200k

Using SQL i have:

```
Select I.amount, C.name
from CustomerCompany C, Invoice I
where I.Customer= C.id and > all
(
  select C.name, Con.Name
  from CustomerCompany, Con Consultant
  where i.amount between 100 and 200
 );

```

Relational algebra:

```
amount = σ(Invoice, amount>=100 and amount<=200)

joininv= Ⓧ(amount, Customer, CustomerCompany, id)

joincon Ⓧ(joiniv, Consultant id, Project, ConsultantID)

π =(joincon, name, Name)

```

I was wondering if write or wrong?

Thanks for any help!

# Answer
> 2 votes
The correct SQL would be :

```
select co.name, cu.name
from consultant co join project pr on co.id = pr.ConsultantID
                   join CustomerCompany cu on cu.id = pr.CustomerId
                   join Invoice i on i.Customer = pr.CustomerId
where i.amount between 100 and 200

```

Converting to relation algebra is straightforward...

---
Tags: databases, relational-algebra
---


# Question
Title: Show that Vertex-Cover is NP-complete, using Stable-Set
My task is to give proof, the Vertex-Cover problem is NP-complete, assuming it's already shown that the Stable-Set problem is NP-complete, too.

My approach: i know, Stable-Set is NP-complete, and all Problems that are NP-complete can be reduced to each other. If i could solve one NP-complete problem, i might be able to solve all NP-complete problems. It should be possible to create a function with polynomial complexity to reduce Vertex-Cover to Stable-Set. At least, this was, what my Professor told.

Now all i have to do, is to find this polynomial function, in order to Show that Vertex-Cover is NP-complete. But here is where i am stuck.. so i need some advice how to build such functions.

# Answer
You have it backwards- you have to reduce a known NP-complete problem to the thing that you want to show is NP-hard. If you were to reduce Vertex-Cover to Stable-Set, you would be saying that Stable-Set is at least as hard as Vertex-Cover... but Vertex-Cover could still theoretically be polynomial.

Since this seems like a homework problem, I don't want to actually give the solution here. What you need to do is find a way of transforming the Stable-Set problem into the Vertex-Cover problem. That way, any solution to Vertex-Cover would be a solution to Stable-Set, so VC is at least as hard as SS. After that, you need to show that VC (note that you need to work with the decision version of VC and SS, which asks does there exists a VC/SS of size k) is in NP by showing that given a witness, you can check if it's correct or not.

Solutions to both problems are sets of nodes in a graph. If there's a VC of size k, that means that all edges have at least one node touching them. If there's a SS of size k, that means no edge has two nodes touching them. I'd suggest drawing out some graphs, finding the VC and SS of both of them, and seeing if there's a relationship between the two sets, as well as the size of each set and the number of nodes in the graph. While I haven't worked out a proof, I don't *think* you need to do a transformation on the graph itself (like drawing in new nodes/edges) in this case. However, for some problems, you might need to.

Here is a handout on NP-completeness reductions, which might help you. I suggest reading some reductions to get a handle on it.
> 3 votes

---
Tags: complexity-theory, graphs
---


title: Wheel subgraph problem

text:
# Question
Title: Wheel subgraph problem
In the following two threads I specified the question in the wrong way (easier to solve that way). Proving that finding wheel subgraphs is NP-complete

Reducing from Hamiltonian Cycle problem to the Graph Wheel problem

My sincere apologies.. I hope moderators will let me post this final version of the question.

In reality the question is different and much harder: is there a way to determine whether a graph $G$ with $n$ vertices has a subgraph that is a wheel $W\_{k}$ ? Is possible to show that this is NP-Complete problem ?

The follwig solution offered by Saeed Amiri seems to only work if the problem is to determine whether the entire graph is a wheel.

> We will add one extra vertex $v$ to the graph $G$ and we make new graph $G'$, such that $v$ is connected to the all other vertices of $G$, then $G$ has a Hamiltonian cycle if and only if $G'$ has a $W\_{n+1}$, is easy to check that if $G$ has a Hamiltonian cycle then $G'$ has a $W\_{n+1}$ wheel (just set $v$ as a center), on the other hand, if $G'$ has a $W\_{n+1}$ then there are two possibility:
>
> 1. $v$ is the center of $W\_{n+1} \rightarrow G $ has a Hamiltonian cycle.
> 2. Another vertex $u$ is the center of $W\_{n+1}$ in $G'$, but both $deg(u) = deg(v) = n$ so we can change the labeling of this two vertices (actually they are equivalence under isomorphic), now we have again first possibility.
>
> P.S: By $W\_n$ I mean the wheel with $n$ vertex.

It seems that Hamiltonian Cycle approach is wrong because with this approach we are forced to think of the cycles across entire set of vertices. Since the problem is asking do determine presence of subset graph $W\_{k}$ the strategy needs to be different.

# Answer
> 3 votes
If there are no restrictions on $k$, then the problem of deciding whether $W\_k$ is a subgraph of $G$ contains the problem of deciding whether $W\_n$ is a subgraph of $G$ as a special case, which implies that the problem is NP-hard. Maybe you are interested in how the hardness of the problem depends on $k$? Here is the complete picture:

* When $k = n^c$ for a constant $c$, the problem remains NP-hard by a padding trick: you can reduce the Hamiltonian cycle problem on graphs of $k$ vertices to the problem of deciding whether $W\_k$ is a subgraph of $G$ (which has $n$ vertices) by executing Saeed's reduction and adding $n-k$ isolated vertices;
* When $k = \omega(\log n)$, an algorithm that decides $G$ contains $W\_k$ as a subgraph in polynomial time would imply an algorithm that solves 3SAT in subexponential time (because the reduction from 3SAT to Hamiltonian cycle has only linear blowup, as does Saeed's reduction); this would contradict the exponential time hypothesis;
* When $k = O(\log n)$ there exists a polynomial time (deterministic, and a simpler randomized one) algorithm that decides whether $W\_k$ is a subgraph of $G$. This is consequence of the beautiful color coding method of Alon, Yuster and Zwick, which allows you to decide whether $H$ is a subgraph of $G$ for any $H$ of constant treewidth and $O(\log n)$ vertices; in your case $W\_k$ has treewidth at most 3 (I think it's exactly 3, but have not verified that).
* In general, the algorithm above decides whether $W\_k$ is a subgraph of $G$ in time $C^k n^{O(1)}$ for some constant $C$. This implies that, assuming the exponential time hypothesis, the problem is not NP-hard for $k = n^{o(1)}$.

You can understand the Alon, Yuster and Zwick result without using treewidth. There is a simple modification of their algorithm for finding a path of length $k$ that works for finding $W\_k$.

Notice the above completely resolves the hardness of finding $W\_k$ inside $G$ as a function of the size of $k$: the problem is NP-hard for polynomial $k$, NP-intermediate under the exponential time hypothesis for $k$ superlogarithmic but subpolynomial, and in P for $k$ at most logarithmic.

# Answer
> 2 votes
As has been noted, Saeed Amiri's solution is quite correct. The problem seems to be that you are misapprehending what needs to be shown to prove NP-completeness.

Of course you have to show that the problem is in NP, but from other posts I gather that's no issue.

The sticking point lies with the reduction from an NP-hard problem. Given an NP-hard problem $A$ and a problem $B$, if we can construct a polynomial time computable function $f$ such that ***for every*** instance $a$ of $A$ ***there exists some*** instance $b$ of $B$ such that $a$ is a Yes-instance if and only if $b$ is a Yes-instance.

Note the ***for every*** and ***there exists some*** parts. This means $f$ maps every instance of $A$ to something, but it says nothing about how many instances of $B$ are the result of some mapping. That is, it's perfectly fine to have $b' \in B$ such that ***there is no*** $a' \in A$ where $b' = f(a')$.

To put it another way, if we take $f(A)$ to be the image of $A$ under $f$, then it's okay that $f(A) \subset B$, it's not necessary that $f(A) = B$.

A third way, $f$ doesn't need to be a surjection (or even an injection).

So for your problem, Saeed Amiri's reduction takes ***any*** instance of Hamiltonian Cycle and produces ***some*** instance of the Wheel Subgraph Problem. It just happens that the only instances it pick out are those where $k=n$, but this doesn't matter, the reduction is enough to show NP-hardness (and hence with membership in NP, completeness).

If you then want to change your problem to force $k \< n$, then a tiny modification to Saeed's proof is enough, we add a second new vertex, with no neighbours. If you want to place further restrictions on $k$, then Sasho Nikolov's answer is fantastic.

An alternate route to understanding this might be to think of the "proof by restriction" technique. This states that if $A'$ is a subproblem of $A$, and $A'$ is NP-hard, then $A$ is also NP-hard. Most reductions use this implicitly, as we have done here. Hamiltonian Cycle is NP-hard, we map that to a subproblem of the Wheel Subgraph Problem (where $n=k$), so this is also NP-hard, and hence the Wheel Subgraph Problem is in general NP-hard (as one of its subproblems is).

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


# Question
Title: Performance differences between Go-Back-N and Selective Repeat ARQ protocols?
This is what I know:

* GBN weakness is the fact that when the window size is too large, the number of packets in the pipeline grows and one packet error causes the retransmition of many packets unnecessarily.
* Selective Repeat solves this by acknowleding just the suspicious packets, which sightly makes performance better, but if a wrong window size is chosen, then the reciever doesn't know if a packet is being retransmitted or another packet is being sent by first time.

So, back to the question, what other important performance differences exists between these protocols?

# Answer
If GBN is used in tandem with AIMD for congestion avoidance, the network link will experience a large amount of latency when a packet is lost. This is because the AIMD CA mechanism will typically wait for a timeout before declaring the packet that hasn't been received as being dropped. Also, the timeout wait-time will occur every time because of the nature of GBN to send cumulative acknowledgments. Worse still, the pipeline will decrease drastically every time this occurs, causing the network to incorrectly gauge congestion.

Once you contrast the above scenario with the SR instead of GBN, it becomes apparent that the window size is no longer really an issue when compared to the latency due to the lost packets in the pipeline. However, SR handles the scenario well since it acknowledges every packet. Thus, the pipeline grows at a favorable rate (as dictated by the AIMD CA) without having unnecessary decreases in the length of the pipeline.

More differences come to light when a congestion avoidance / prevention mechanism is presented.
> 1 votes

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


title: Parsing a string with LR parsing table

text:
# Question
Title: Parsing a string with LR parsing table
Me and my friends are studying for an upcoming test and this exercise is one of the harder ones for us.

We have been trying to solve it and we have been looking at similar exercises, the problem is that the explanations are too complicated for us to understand. Keep in mind we just started with this.

So, my question is: Can anyone explain this as simple as possible, I have included the exercise.

# Answer
> 5 votes
The mechanics of shift-reduce parsing is pretty simple -- the hard part is understanding why it works or how to construct the tables. But since you already have the table, that is not relevent.

To do shift/reduce parsing, you need an action table and a goto table (which you have) and a stack of states. You start with just state 0 on the stack. At each step you look up in the action table with the top state on the stack and the next token of input and perform the corrsponding action.

* for a SHIFT action you consume the token of input and push the state on the stack
* for a REDUCE action, you find the SIZE of the right-hand-side of the rule to be reduced (number of symbols -- ε is zero size) and the SYMBOL on the left-hand-size. You pop SIZE states from the stack and then use the state now on top of the stack and the SYMBOL to lookup in the GOTO table and push the corresponding state.

That's it. You repeat the above until you either reach an ACCEPT action (the string matches) or a REJECT action (any blank in the action table -- the string is not matched). The reduce action is a bit complicated as it chains immediately to a goto action, so you can think of the reduce+goto as a single action or as two distinct actions as you prefer.

If you want your parser to construct the parse tree while you're at it, its a bit more complicated. You need to have your stack hold state × subtree pairs -- when you shift a token you include that token (as a single node subtree) along with the state, and when you reduce, you create a new subtree from the subtrees popped (as children to the LHS symbol) which you push along with the GOTO state. When you get to the ACCEPT state you do a 'reduce 1' action to build the complete parse tree.

---
Tags: parsers
---


title: Is $L$ always context free?

text:
# Question
Title: Is $L$ always context free?
> Consider formal language $L$ over finite alphabet $\Sigma$ consisting of all words over $\Sigma$ that have non-trivial period (non empty prefix that is also a suffix). Is $L$ always context free?

Maybe pumping lemma will do? I was advised to try with a word $a^Nb^Na^Nb^N$ but if I pump only second block of $a$ then this word still is in $L$, because it has non empty prefix $a^Nb^N$ that is also a suffix.

# Answer
> 1 votes
Try to use closure properties instead.

Closer hint:

> CFL is closed against (pre)image of language homomorphisms and intersection with regular languages.

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


title: Is {xyx | |x|≥1} context-free?

text:
# Question
Title: Is {xyx | |x|≥1} context-free?
> Is $L=\\{ xyx \mid x,y \in \\{a,b\\}^\* \text {and } |x| \ge 1 \\}$ context-free?
>
> If yes, please explain how we can write grammar or create a PDA for it. If not a CFL, then prove it through pumping lemma.

I have tried to apply the pumping lemma with $w = a^nb^naba^nb^n$ as the word in $L$, but without success.

# Answer
> 2 votes
Consider $w = a^nb^na^nb^n$, then it is similar to proving language {ww} is not CFL.

In the given language there is no restriction on length of y. So, let it be zero. Now, for any valid decomposition w = uvxyz, $uv^ixy^iz$ belongs to L.

# Answer
> 1 votes
Assume $L$ was context-free. What can you say about $L \cap \mathcal{L}(a^\*b^\*a^\*)$?

Hint: use closure properties. (That won't answer the exercise, but solve the problem.)

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


title: Finding cycles in a graph

text:
# Question
Title: Finding cycles in a graph
Given a directed weighted graph $D = (V, A, w)$ with weight function $w \colon A \to \[0,\infty)$ and a source vertex $s$. How can I find, for each vertex $v \in V$ a shortest (with respect to $w$) cycle that contains both $v$ and $s$ (it is allowed to repeat the same arc in a cycle).

# Answer
Find the shortest path from every vertex to every other vertex. To find the shortest cycle from $s$ to $v$, just concatenate the shortest path from $s$ to $v$ and then $v$ to $s$ which was found earlier
> 1 votes

---
Tags: algorithms
---


# Question
Title: Each of the two sets is recursively enumerable given their cartesian product is
$A \times B$ is an r.e. set, I want to show that $A$ (or $B$) is r.e.

# Answer
> 1 votes
Not sure if that's what you want: with the same idea as @HendrikJan and with a function:

$A\times B$ is r.e. hence, there is a partial recursive function $f$ such that: $$ f(x) = \left\\{\begin{matrix} 0 &\mbox{if}\ x \in A\times B \\ \mbox{undefined/does not halt}\ &\mbox{if}\ x \notin A\times B \end{matrix}\right. $$

$A$ is not empty let $a$ be an element of $A$ ($a\in A$).

Let $g$ be the partial recursive function defined as $g(x)=f(a,x)$.

$g(x)=0$ iff $f(a,x)=0$ iff $(a,x)\in A\times B$ iff $x\in B$. Hence $B$ is r.e.

# Answer
> 1 votes
We assume both $A$ and $B$ are nonempty.

If $A\times B$ is r.e., then it is definable by a $\Sigma^{0}\_{1}$ formula: $$ (a,b) \in A\times B \Longleftrightarrow \exists x \\, R(a,b,x), $$ where $R$ is a recursive predicate. Thus $$ a\in A \Longleftrightarrow \exists x \\, \exists \\, b R(a,b,x), $$ so $A$ is definable by a $\Sigma^{0}\_{1}$ formula and hence r.e. Similarly for $B$.

---
Tags: computability, enumeration
---


# Question
Title: Show that it is undecidable if two Turing Machines accept the same language
I was asked this question at an interview, and couldn't answer it, and would like to know how it is 'shown' that two Turing machines which accept the same language is undecidable. This is not a homework question!

# Answer
> 6 votes
Let's restrict ourselves to Turing machines that ignore their input. Now suppose you have two Turing machines:

1. Some given one `T`.
2. Another that loops forever.

If you could decide if they accept the same language, you'd be able to decide if `T` halts or not. This is impossible - see the halting problem.

---

This applies to SW/HW as well. It's undecidable if two programs perform the same computation or not.

# Answer
> 4 votes
If there were such an algorithm, then we could write another algorithm $P$ that, given a program $Q$ as input, first uses the supposed algorithm to decide if $Q$ accepts all strings. If Q does accept all, $P$ outputs some (fixed arbitrary) program $P(Q)$ that does not accept all strings. If $Q$ does not accept all, $P$ outputs some (fixed arbitrary) program $P(Q)$ that does accept all strings. So $P$ is a total program such that $P(Q)$ always functions differently than $Q$, contrary to the recursion theorem.

---
Tags: algorithms, computability, finite-automata, undecidability
---


title: Strategic vertex labeling

text:
# Question
Title: Strategic vertex labeling
We are given a graph $G=(V,E)$ with positive edge weights $w\_{i}$ and numerical {0,1,-1} labels $l$ for all vertices . We know that $G$ has a subset $G'$ with all vertices labeled 0. The problem is to assign labels to the vertices in $G'$ in such way that this sum is maximized $\sum\_{e\_{u,v}\in E} w\_{i}l\_ul\_v.$ The question is whether this problem is NP-complete or not. If it is not then what is the polynomial algorithm?

Personally I believe that this problem is essentially a form of 3-Coloring. The challenge is to chose the labels {1,-1} depending on the neighbors. Say the boundary between $G$ and $G'$ has a lot of 1s then it is better to chose 1s for the labeling of vertices in $G'$, similarly if the boundary has lots of -1s then it is better to chose -1s for labeling because $-1\*-1=1$. So essentially this becomes some sort of reverse 3-Coloring problem where the neighbors have to have matched color.

Can you help reduce this problem to 3-Coloring (or vice-versa) ? Or perhaps there is polynomial time algorithm ?

# Answer
Hint: Your problem looks a lot like minimum $(s,t)$-cut.
> 1 votes

---
Tags: graphs, np-complete, np, colorings
---


# Question
Title: Confusion related to time complexity of dynamic programming algorithm for knapsack problem
I have this confusion related to the time complexity of the algorithm solving the knapsack problem using dynamic programming

I didn't get how the time complexity of the algorithm came out to be $O(nV^\*)$

# Answer
Since computing each cell in the table is $O(1)$, the running time is just the size of the table. The first coordinate ranges from $1$ to $n$, and the second one from $0$ to the maximal value ever encountered (so it's really a dynamic table), which is $V^\*$.
> 1 votes

---
Tags: computability, time-complexity, dynamic-programming, knapsack-problems
---


# Question
Title: Register Machine code for Fibonacci Numbers
I am not sure whether this is the right place to ask this question.

I would like to write a register machine code which when given an input of n in register 1, returns (also in register 1) the nth Fibonacci number. The Fibonacci numbers are 0 (the 0th), 1 (the 1st), 1 = 0 + 1 (the 2nd), etc.

I tried to write few lines of the codes, but unable to do the recursive property of Fibonacci sequence. Here is my code:

Let A, B, C be registers.

1. (-A; 2,-)
2. (+C; 1)
3. (-C; 4,-)
4. (+B; 5)
5. (+A; 3)

I know that the fifth line is wrong but have no idea how to fix it. And I want to code to be as simple as possible (i.e. with fewest instructions). Thanks in advance.

# Answer
Here is some code in C, which you can "compile" into your assembly language:

```
int x = 0, y = 1, z;
while (n--) {
  z = x;
  x = y;
  y += z;
}
return x;

```

After $n$ iterations of the loop, $x = F\_n$ and $y = F\_{n+1}$.
> 1 votes

---
Tags: programming-languages, recurrence-relation, recursion
---


# Question
Title: How does a program execute with respect to the operating system?
I am reading Operating Systems by William Stallings 6th edition and I came across this text,

## Program execution:

```
A number of steps need to be performed to execute a
program. Instructions and data must be loaded into main memory, I/O devices
and files must be initialized, and other resources.

```

Now I am unable to understand how I/O devices and files are initialized on program execution? I assume it meant to start the I/O resources but what about the files? Please guide. Thanks

# Answer
A initialized file means that you have comprobe that exist, or open it in some mode (write, read, r&w, etc) and create it if is not already.
> 1 votes

---
Tags: operating-systems
---


# Question
Title: Can a language have $\Sigma^{*}$ as its syntactic monoid?
As per the title I was wondering if it's possible for a language $L \subseteq \Sigma^{\*}$ to have $\Sigma^{\*}$ as its syntactic monoid and if so could one give an example of such a language? I first thought that this was probably an easy question with a simple answer but I haven't been able to make much progress with it, maybe it has a simple answer and I am just overlooking it?

If we look at the syntactic congruence $\sigma\_L = \\{(w,z) \in \Sigma^{\*} \times \Sigma^{\*}: (\forall u, v \in \Sigma^{\*}) \\; uwv \in L \Leftrightarrow uzv \in L\\}$ we see that in order to have $w \cong\_{\sigma\_{L}} z \Leftrightarrow w = z$ we must have that $(\forall w, z \in \Sigma^{\*} \\; w \not = z) \\; (\exists u, v \in \Sigma^{\*})\\; uwv \in L \Leftrightarrow uzv \notin L$. Which seems like quite a strong condition. It's also clear that such a language couldn't be regular as it is known that a language is regular if and only if it has a finite syntactic monoid.

# Answer
> 2 votes
Consider $\\{i\\#a\\#w: w\_i = a\\}$, where $i$ is an integer indicating index in a word (say, written in unary), $a$ is a single letter and $w$ is a word. This language says that at $i$-th place the word $w$ has letter $a$.

If $a \neq b$ then $a,b$ differ at some position $i$ and you can say $i \\# a\_i \\# a \in L$ while $i \\# a\_i \\# b \notin L$. Or, they can differ at length, but then you talk about the longer string.

This works for any alphabet with at least two characters; for unary alphabets you can use powers of two, squares etc. $ $

# Answer
> 2 votes
It seems to work to take $L=\\{ww: w\in\Sigma^\* \text{and $|ww|$ is a power of $2$}\\}$.

First, we can show that if $|u|\>|v|$ then they are not equivalent. Indeed, there is $x$ such that $|uxux|$ is a big power of $2$, say $2^{|u|+|v|}$. Therefore, $uxux\in L$.

But then the length of $vxux$ cannot be power of $2$, because its difference to $2^{|u|+|v|}$ is only $|u|-|v|$. Therefore, if we take $y=xux$, we have $uy\in L$ and $vy\notin L$.

Now it suffices to show that words of the same length are not equivalent. Let $u\neq v$ with $|u|=|v|$, and let $x$ such that $|ux|$ is a power of $2$ (and then so is $|uxux|$). Then you can see that $(u,v)\notin\sigma\_L$ because $uxux\in L$ and $uxvx\notin L$.

---
Tags: formal-languages
---


# Question
Title: Lock-free, constant update-time concurrent tree data-structures?
I've been reading a bit of the literature lately, and have found some rather interesting data-structures.

I have researched various different methods of getting update times down to $\mathcal{O}(1)$ worst-case update time \[1-7\].

Recently I begun looking into lock-free data-structures, to support efficient concurrent access.

**Have any of these worst-case $\mathcal{O}(1)$ update-time techniques been used in the implementation of lock-free data structures?**

I ask because; to me, they seem like the obvious practical extension of this "theoretical enhancement".

---

1. Tarjan, Robert Endre. “Updating a Balanced Search Tree in O(1) Rotations.” Information Processing Letters 16, no. 5 (1983): 253 – 257.
2. Driscoll, J R, N Sarnak, D D Sleator, and R E Tarjan. “Making Data Structures Persistent.” In Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing, 109–121. STOC ’86. New York, NY, USA: ACM, 1986.
3. Levcopoulos, C., and Mark H. Overmars. “A Balanced Search Tree with O(1) Worst Case Update Time.” Acta Inf. 26, no. 3 (November 1988): 269–277.
4. Fleischer, Rudolf. A Simple Balanced Search Tree With O(1) Worst-Case Update Time
5. Dietz, Paul F, and Rajeev Raman. “A Constant Update Time Finger Search Tree.” Information Processing Letters 52, no. 3 (1994): 147 – 154.
6. Lagogiannis, George, Christos Makris, Yannis Panagis, Spyros Sioutas, and Kostas Tsichlas. “New Dynamic Balanced Search Trees with Worst-case Constant Update Time.” J. Autom. Lang. Comb. 8, no. 4 (July 2003): 607–632.
7. Brodal, Gerth Stølting, George Lagogiannis, Christos Makris, Athanasios Tsakalidis, and Kostas Tsichlas. “Optimal Finger Search Trees in the Pointer Machine.” J. Comput. Syst. Sci. 67, no. 2 (September 2003): 381–418.

# Answer
$O(1)$ doesn't help in and of itself. In a lock-free data structure there needs to be a single atomic instance when your data structure appears to change. All the representation invariants need to be in force both immediately before and immediately after that atomic instant.

This means that if you are doing a modification to the data structure the important characteristic is that you can do all the mods on a private data structure and then swap in the modifications in a single atomic instruction.

Lock-freedom is usually easiest when your data structures are *immutable* (purely functional). You simply keep a global pointer to the current version of the data structure. Readers don't need to lock anything. Modifications to the data-structure are effected by swapping the global pointer to one immutable data structure to another.

For example: if you have a purely functional tree balanced tree you:

1. Record the current global pointer to the root of the tree.
2. Create a new tree that inserts or deletes a node. (This is logarithmic in time and space in the number of nodes currently in the tree, and involves creating new nodes from the modification point up to the root, and just pointing everything new at the old parts of the previous version of the data structure.)
3. Atomically compare and swap the global pointer to the root. (Note that this might fail if another modification has happened between the time you recorded the old root pointer and now. If this happens you go back to step 1 and try again. This is so-called "optimistic concurrency control.")

Note that the most important part is what I said above about needing to maintain representation invariants. *It is usually not sufficient to have an algorithm that atomically makes a change in the middle of the tree.* Why? For example: you might have a reader thread that is in the process of doing a preorder traversal of the tree. If you modify a node that is an ancestor of the node they are currently reading then you are going to invalidate preconditions that they thought they had enforced. The reader needs to be able to work with the data structure exactly as it was before you made your change, or exactly as it will be after you've made your change. Not something in between.

**Edit**: As @Raphael pointed out there are techniques for making mutable data structures lock-free. A proof by construction that this can always be done is: As long as you have a single global pointer to the "top" of your data structure, even if it is mutable you can always copy the entire data structure, make your mods to the copy, and then, using optimistic concurrency control, try to compare-and-swap the pointer to your newly minted data structure in for the original. The beauty of functional tree-based data structures is that they keep the cost of copying down at $O(log(N))$ of a size $O(N)$ data structure.
> 4 votes

---
Tags: reference-request, data-structures, time-complexity, concurrency, search-trees
---


title: Complement of halting set is not r.e

text:
# Question
Title: Complement of halting set is not r.e
suppose **we don't know that Halting problem is not recursive**.

I want to prove that **complement of halting set is not r.e.** then we can find **halting problem is not recursive**.

**Can you direct prove that complement of halting set is not r.e.??**

# Answer
If a set $S$ and its complement $S^C$ are both recursively enumerable, then the set $S$ and its complement $S^C$ are both recursive. Let $M$ be a TM enumerating $S$ and $M^C$ be a TM enumerating $S^C$. To decide either $S$ or $S^C$, we can use $M$ and $M^C$ in an alternating fashion (i.e., during odd-numbered steps we use $M$, and during even-numbered steps we use $M^C$) to generate all possible strings, and either accept or reject depending on which set we're deciding. This process is guaranteed to halt since, between the two machines, every possible string will be enumerated after a finite number of steps.
> 2 votes

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


# Question
Title: Finding the required value of an algebric expression
I have an expression $$Ax+By+Cz.$$ where $A$, $B$ and $C$ are positive constants $\ge1$. The variables $x$, $y$ and $z$ are non-negative integers. I am also given a number $T$.

I want to find the largest integer value such that it is less than $T$ and not satisfied by $Ax+By+Cz$, how can I do it without using brute force.

# Answer
> 3 votes
This is classical Integer Linear Programming. You have the following problem:

$$\begin{align} Ax+Bx+Cx & \to \max \\ \text{s.t} \quad x,y,z &\ge 0\\ Ax+Bx+Cx &\le T \\ x,y,z &\in \mathbb{Z}\\ \end{align}$$

There are several algorithms available for such problems. Google "branch and bound" or "branch and cut" and you will get to them.

You can picture your problem as follows. Your variables $x,y,z$ decode a grid point in 3d. The constraints cut of hyperplanes, which keeps you left with a set of candidate solutions. In your example this set is finite. You could basically test out all cancidates brute force. But it is more practical to add additional constraints to make the candidate set smaller - or in other words you filter out points. If you relax the condition that $x,y,z$ are integers, then the problem becomes much easier (Linear Programm), because then you know that the optimal point you are looking for is on some "corner" of your candidate set.

# Answer
> 0 votes
Regarding the two-dimensional case, see this answer, which proves the following two results. If $(a,b) = 1$ then every integer $x \geq (a-1)(b-1)$ is representable as $ax+by$ for some $x,y \geq 0$. Also, if $x \< ab$ and $a \nmid x$, $b \nmid x$ then exactly one of $x,ab-x$ is representable.

The first result already tells you that without loss of generality, $T \leq (a-1)(b-1)$. Presumably a similar result holds in your three-dimensional case - perhaps you can assume that $T \leq (a-1)(b-1)(c-1)$. The outcome will be an algorithm running in time $\mathrm{poly}(abc)$.

---
Tags: algorithms, optimization, linear-programming, linear-algebra
---


# Question
Title: Confusion related to calculating time complexity
I have some confusion related to calculating the time complexity of this algorithm

```
opt(i)
   for j=i:n
      a = f(i,j) + opt(j+1)
   end

```

How is the running time of this algorithm $O(n^2)$?

# Answer
Let $T(i)$ be the running time of `opt(i)` then we have $$ T(i)= \sum\_{k=i}^n T(k+1).$$ You have not specified a recursion anchor, but I guess it is something like $T(n+1)=1$. Write down the series $T(n),T(n-1),T(n-2),\dots$ and you get the impression that $T(i)=2^{n-i}$. This guess can be proven by induction, since assuming that $T(i)=2^{n-i}$, we have $$ T(i-1)= \sum\_{k=i-1}^n T(k+1)= T(i)+\sum\_{k=i}^n T(k+1)= 2 T(i) = 2^{n-(i-1)} .$$

Thus, $T(0)= 2^n$ and therefore it is not in $O(n^2)$.

PS I assumed that in the recursion the value of `opt` is never stored and will always be recomputed.
> 1 votes

---
Tags: algorithm-analysis, loops
---


# Question
Title: Issues with using greedy algorithm (Interval scheduling variant)
I am trying to solve a problem of finding incompatible jobs set using greedy algorithm. However, I am not sure if greedy algorithm can solve this problem or I need to perform another approach.

I have a set of jobs with start and finish time and I want to find the smallest subset of this jobs such that all the jobs are incompatible with at least one job of this subset.

Suppose

```
job  start   end
1    1       3
2    2       11
3    4       6
4    7       8

```

My required job set J is {2} since all the jobs are incompatible with at least one job of the job set J. I tried to use greedy algorithm like sorting jobs by start time, end time ( adding one and removing all the ones incompatible and so on) But it is not optimal. As you can see in this example. If I add job 1 and then remove all the job incompatible with it, I will remove job 2, Then I will have to add 3 and 4 in the jobset J.

Am I going the right way?

# Answer
It is clear from your edited post that you will need to use dynamic programming.

Consider solution with the recurrence based on minimum number of time intervals necessary to conflict with all other time intervals, and include a parent pointer so that you can create the set after the algorithm completes.
> 1 votes

---
Tags: algorithms, combinatorics, dynamic-programming, scheduling, greedy-algorithms
---


# Question
Title: Pushdown automation where number of letter `a` is at least as twice as letter `b` in the word
I have talked to my friend and he said this is the only place somebody could know how to solve it. It is the only exercise(from around 80) from exam revise I just do not know how to do at all.

Create pushdown automation for `{w: #a(w) >= 2#b(w)};` and simulate it for the word `ababaaa`

`#` means number

Does any one of you is fluent enought in automation to solve it?

# Answer
> 1 votes
General strategy:

What you want to do is every time you read an input symbol a, if the stack has a b on it delete the b, and if the stack is empty/has a's, add an a. Every time you read a b, if the stack is empty/has b's add bb, if the stack has one a, remove the a and add a b, and if the stack has two or more a's, delete two of them. You're in an accepting state as long as the stack has no b's on it.

You can implement this strategy if you use epsilon transitions and intermediate states in a fairly straightforward way.

---
Tags: pushdown-automata
---


title: What was going on before PAC learning

text:
# Question
Title: What was going on before PAC learning
I am investigating PAC learning (computational learning theory) as a beginner with no previous knowledge of machine learning / AI. I am investigating the model mainly from a historical point of view.

For this, the most important things are of course the results based on the model. There are enough papers out there that document these results. But I also want to write something about what was going on before PAC learning, as to sketch the historical context up to where Valiant came with the notion of the PAC model.

No papers/surveys I've found so far document this, and as someone with no real knowledge of machine learning, it is hard to find this out. I am therefore asking this soft question here, because I believe there are enough experts that can help me with this. References are highly appreciated.

When I can research and study what was going on before PAC, I might get a better appreciation as to why the academic world is so enthusiastic about the PAC model, which is also something interest to document in my historical work!

# Answer
> References are highly appreciated.

An author is expected to address the question of the context and relevance of his results at the begin of his publication. I just skimmed over the introduction of "L. Valiant. A theory of the learnable. Communications of the ACM, 27, 1984." again, and found out that Valiant indeed well covered your question.

The original paper by Valiant is both freely available and not too difficult to read. (Except section 7, which only proves that the author can also tackle challenging mathematical problems, but doesn't contribute much to the real content of the paper.) Reading at least its introduction will be more rewarding than reading my overly long answer to this question, so I suggest to really try it.

---

The rest of this answer tries to cite some passages from the introduction which should indicate whether reading this introduction might answer the question about the historical context. Note however that an author has the natural prerogative to be biased with respect to such questions.

> ... such a system would, at least, be a very good start. First, when one examines the most famous examples of systems that embody preprogrammed knowledge, namely, expert systems such as DENDRAL and MYCIN, essentially no logical notation beyond the propositional calculus is used.

This is interesting information for the context, because propositional calculus is significantly weaker than predicative calculus or the various systems of type theory sometimes used today. (Strange enough though, Prolog (1972) and ML (1973) were among others intended as meta-languages for "such" expert systems, and seem to go beyond simple propositional logic as far as I can see. Also, the relational model (1969) for database management is claimed to be based on predicate logic.)

> Perhaps the main technical discovery contained in the paper is that with this probabilistic notion of learning highly convergent learning is possible for whole classes of Boolean functions. This appears to distinguish this approach from more traditional ones where learning is seen as a process of "inducing" some general rule from information that is insufficient for a reliable deduction to be made.

I fully agree here. It is important to be able to explain how your solution is able to solve a given problem, and in which sense it is a solution. Otherwise, you just end up with "no-free lunch" theorems which don't allow you to distinguish a buggy implementation of a dubious heuristic from a correct implementation of an appropriate heuristic.

> In summary, this paper attempts to explore the limits of what is learnable as allowed by algorithmic complexity. The results are distinguishable from the diverse body of previous work on learning because they attempt to reconcile the three properties ((1)-(3)) mentioned earlier. Closest in rigor to our approach is the inductive inference literature \[...\]. There is a large body of work on pattern recognition and classification, using statistical and other tools \[...\]. Learning, in various less formal senses, has been studied widely as a branch of artificial intelligence.

The properties ((1)-(3)) were that (1) "the machines can provably learn whole characterizable classes of concepts" which are (2) "appropriate and nontrivial for general-purpose knowledge" and (3) "the computational process requires only a feasible (i.e., polynomial) number of steps".
> 8 votes

# Answer
Language identification in the limit is the first known attempt to capture the notion of learnability. It was introduced by Gold in 1967 and is a model for inductive inference that concerns learning classes of languages.
> 4 votes

---
Tags: machine-learning
---


title: Sequential hash tree traversal

text:
# Question
Title: Sequential hash tree traversal
A lot of articles say that hash tree traversal cost to any *randomly* chosen leaf is $\mathcal{O}(\log\_2 N)$ ($N$ is a number of leafs) and that is right. If we have a tree of 8 leafs it will take us at most 3 operations to get to any leaf, if we have a tree of 64 leafs it will take us at most 5 operations etc.

But lets say I need to check ***every*** leaf sequentially to check if ***all blocks*** of a file are correct, then I would need $\mathcal{O}(N \log\_2 N)$ operations. Or if I would check every second leaf (just left leaf of every pair) I would need $\mathcal{O}((\frac{N\log\_2 N}{2}))$ operations. That is, I will need $\mathcal{O}(\log\_2 N)$ operations for every leaf? Which leads to exponentially growing evaluations curve and it would be better to use simple hash list or hash chain? Am I right?

Or I just don't see/know something?

\*Note, chart has logarithmic scale

# Answer
You want to access every leaf in a tree, you probably do not want to start from the root every time. If you would then you need indeed $O(N \log N)$ time. If you only want to access all the leaves in the tree, do a depth-first-search traversal and you are done in $O(N)$. If you only want to have every other leaf, do the same, but ignore the "unwanted" elements.

In data structure design one often takes the leaves and put them (in order) in a double linked list. This only costs a constants factor more place, but speeds up sequential access.
> 2 votes

---
Tags: data-structures, search-trees, graph-traversal, hash-tables
---


# Question
Title: Understanding why the polynomial $p(n) = \sum_{i=0}^{k} a_in^i$ is in $\Theta(n^k)$
Hi I've read this lemma in my book:

> **Lemma 2.1.** Let $p(n) = \sum\_{i=0}^{k} a\_in^i$ denote any polynomial and assume $a\_k \> 0$. Then $p(n) \in \Theta(n^k)$
>
> **Proof.** It suffices to show that $p(n) \in O(n^k)$ and $p(n) \in \Omega(n^k)$. First observe that for $n \> 0$, $$p(n) \leq \sum\_{i=0}^{k} |a\_i|n^i \leq n^k \sum\_{i=0}^{k}|a\_i|,$$ and hence $p(n) \leq (\sum\_{i=0}^{k}|a\_i|)n^k$ for all positive $n$. Thus $p(n) \in O(n^k)$.
>
> Let $A = \sum\_{i=0}^{k-1}|a\_i|$. For positive $n$ we have $$p(n) \geq a\_kn^k -An^{k-1} = \frac{a\_k}{2}n^k + n^{k-1}(\frac{a\_k}{2}n - A)$$ and hence $p(n) \geq (a\_k/2)n^k$ for $n \> \frac{2A}{a^k}$. We choose $c=a\_k/2$ and $n\_0 = 2A/a^k$ in the definition of $\Omega(n^k)$, and obtain $p(n) \in \Omega(n^k)$.

Can anyone explain me the part $p(n)\in \Omega(n^k)$ of the proof? Why should we divide $a\_k\cdot n^k$ by 2? Why can't we take $a\_kn^k$ as coefficient of $n^k$? And how do we obtain that $n\>2A/a\_k$?

# Answer
The starting point is the inequality $p(n) \geq a\_kn^k - An^{k-1}$. We want to deduce from this inequality that for large enough $n$, $p(n) \geq bn^k$ for some $b \> 0$. So take *any* $b \> 0$ satisfying $b \< a\_k$. Since $$p(n) \geq a\_k n^k - An^{k-1} = \left(a\_k - \frac{A}{n}\right) n^k,$$ we have $p(n) \geq bn^k$ as long as $a\_k - A/n \geq b$. As $n \to \infty$, $A/n \to 0$, and so it is clear that the inequality $a\_k - A/n \geq b$ holds for large enough $n$. If we want an explicit lower bound on $n$, we can do some algebra to obtain the equivalent inequality $n \geq A/(a\_k - b)$.
> 5 votes

# Answer
To show that $p(n) \geq cn^k$, given that $p(n) \geq an^k - An^{k-1}$, the $k-1$ term has to be made positive. For that purpose that $an^k$ is divided into two terms. It doesn't matter much whether those terms are both $a/2$ or one is $a-\epsilon$ and another is $\epsilon$ or anything else. The final step is to find $n$, such that $n^{k-1}(\frac{a}{2} n - A) \geq 0$. Then the required inequality follows.
> 1 votes

---
Tags: algorithms, algorithm-analysis, proof-techniques
---


# Question
Title: Reducing from Hamiltonian Cycle problem to the Graph Wheel problem cannot be proved vice versa
I saw a proof by Saeed Amiri, We will add one extra vertex v to the graph G and we make new graph G′, such that v is connected to the all other vertices of G. G has a Hamiltonian cycle if and only if G′ has a Wn+1. It is easy to check that if G has a Hamiltonian cycle then G′ has a Wn+1 wheel (just set v as a center). On the other hand, if G′ has a Wn+1 then there are two possibility:

v is the center of Wn+1→G has a Hamiltonian cycle. Another vertex u is the center of Wn+1 in G′. So both deg(u)=deg(v)=n. Then we can change the labeling of this two vertices (actually they are equivalence under isomorphic), now we have again first possibility. P.S1: By Wn I mean the wheel with n vertex.

P.S2: In this proof we say if we fix k=n+1 (size of the artificial graph), then the problem is NP-Complete in this restricted version, So it's also NP-Complete in the case k is as input parameter.

The proof is valid one way. If a graph has a hamiltonian cycle adding a node to the graph converts it a wheel. If the graph of k+1 nodes has a wheel with k nodes on ring. It has a hamiltonian cycle. BUT IF THE GRAPH OF N nodes has a wheel of size k. Then identifying which k nodes cannot be done in polynomial time. Thus the reduction cannot be done in polynomial time.

# Answer
You don't seem to actually be asking a question, but your assertion about the reduction not being polynomial time computable is incorrect.

There are two parts to the reduction which you are confusing (in the literal mixing together sense). Given two problems $A$ and $B$, there is a many-one polynomial-time reduction from $A$ to $B$ if there is a function $f$ such that for every instance $a$ of $A$, $f(b)$ is an instance of $B$ and:

1. $f$ is computable in polynomial time.
2. $a$ is a Yes-instance of $A$ if and only if $f(a)$ is a Yes-instance of $B$.

In Saeed's proof, the function $f$ is copying the graph, adding a new vertex, adding edges between it and all other vertices in the graph and setting $k$ to the size of the initial graph plus one.

This is the part that must be computable in polynomial time. It should be obvious that we can take a graph, add a vertex and some edges, and set a number pretty quickly. Certainly in polynomial time.

Now we have the second part. All this says is that if there is a Hamiltonian cycle in the first graph, then there is a wheel on $k$ vertices in the second graph and vice versa.

***We do not have to be able to find either*** (in *any* time bound). We only need to know that *if* one exists, *then* the other does. You can prove this in any mathematically valid way. It is a purely existential statement. In practice we almost always show that knowing the solution to $f(a)$ would tell us where the solution to $a$ is, but there is no need for it to show *how* to find it.

This is a lot like showing something is in NP using the verifier definition - we get given a solution and we have to check it. We never say where we got the solution in the first place. Reductions work similarly, we just say that if we can correctly answer Yes or No to one, we can correctly answer the other (out of $a$ and $f(a)$ - note that it doesn't say anything about an arbitrary instance of $B$).

In fact, the whole point of the reduction is to show that we *can't* find a wheel subgraph in polynomial time unless P=NP.
> 0 votes

---
Tags: algorithms, graphs, np-complete, polynomial-time
---


# Question
Title: What makes Bayesian Networks decomposable into joint trees?
Given a Bayesian Network $N$, one can build a junction/joint tree $JT$ over $N$ by applying series of steps (namely, moralisation,triangulation..etc). Then we can use $JT$ to answer queries over $N$.

My question is: what makes BN decomposable into $JT$? The structure (along with the CPTs) must exhibit certain conditions otherwise any graphical model is decomposable.

# Answer
> 0 votes
I found the answer in **valuation algebra** more specifically in this paper .
They assume the set of functions (i.e. tables/relations/potentials/probability distributions) form a commutative semigroup. There are six axioms that the graphical model/representation should obey in order to use local computations (and thus joint trees). The valuation algebra has three operations:

1. **Labeling:** Mapping each potential $\phi$ to its scope $d(\phi)$ (variables that defined it).
2. **Combination:** Two potentials $\phi$ and $\psi$ are combined through combination operator $\phi \otimes \psi$ (in BNs $\otimes$ is the multiplication of CPTs).
3. **Marginalization:** The usual projection operator (this corresponds to summing up irrelevant variables in BNs).

where the axioms are:

1. Commutative Semigroup: it is clear that the set of CPTs represent a commutative semigroup under the combination operator.
2. Labeling: for two potentials $\phi$ and $\psi$, $d(\phi \otimes \psi)=d(\phi) \cup d(\psi)$
3. Marginalization: $d(\phi^{\downarrow x})=x$ where $x\subseteq d(\phi)$
4. Transitivity: $(\phi^{{\downarrow y}})^{\downarrow x}=\phi^{\downarrow x}$ where $x\subseteq y\subseteq d(\phi)$
5. Combination: $(\phi \otimes \psi)^{\downarrow z}=\phi \otimes \psi^{\downarrow{z\cap y}}$ where $d(\phi)=x,d(\psi)=y$ and $x\subseteq z\subseteq x\cup y$
6. Domain: $\phi^{\downarrow x}=\phi$

The axioms are clearly satisfied by the nature of multiplication and marginalization over BN CPTs. Really do not know why axiom 6 is there. Sorry for abusing some of the notations.

---
Tags: graphs, probability-theory, trees
---


# Question
Title: Shortest sub-sequence of one string, that's not a sub-sequence of another string
Given two strings $x$ and $y$ over the alphabet $\\{A,C,G,T\\}$, I'm trying to determine a shortest string $z$ such that $z$ is a subsequence of $x$ and not a subsequence of $y$.

> **Example:** a shortest string that is a subsequence of AATGAAC but not a subsequence of ATCGATC is AAG.

# Answer
A dynamic programming algorithm seems to work.

Given a prefix $X\_k = x\_1 x\_2\dots x\_k$ of string $X$ ($X$ is of length $s$, so $X = X\_s$), a prefix $Y\_m = y\_1 y\_2 \dots y\_m$ of string $Y$ ($Y$ is of length $t$, so $Y\_t = Y$), and a length $L$, we determine if there is a subsequence of $X\_k$ which is also a subsequence of $Y\_m$, such that the sub-sequence is of length exactly $L$ and ends at $x\_k$. Call that (boolean) value: $\text{is\_there}\[k,m,L\]$.

We will also need to know if there is a subsequence of $X\_k$ which is also a subsequence of $Y\_m$ such that the subsequence is of length exactly $L$ and ends at *or before* $x\_k$. Call that boolean value $\text{is\_there\_any}\[k,m,L\]$.

These satisfy the recurrences:

$$\text{is\_there}\[k,m,L\] = \text{is\_there}\[k, m-1, L\] \vee (x\_k = y\_m \wedge \text{is\_there\_any}\[k-1,m-1,L-1\])$$

and

$$\text{is\_there\_any}\[k, m, L\] = \text{is\_there}\[k, m, L\] \vee \text{is\_there\_any}\[k, m-1, L\]$$

The smallest $L$ such that $\text{is\_there}\[k, t, L\] = false$ for all $k$ gives you the result. (Note that $t$ is the length of $Y$).

If the length of the shortest such subsequence is $S$, This can be implemented in $O(stS)$ time and $O(stS)$ space by a triply nested for-loop with $L$ on the outside, then $k$, then $m$.

Something like:

```
Compute isThere for L = 1.
foreach L in (2 ... s)
    foreach k in (1 ... s)
       foreach m in (1 ... t)
         is_there[k,m,L] = blah
         is_there_any[k,m,L] = blah

```
> 5 votes

---
Tags: algorithms, strings
---


title: MAX 10-SAT Algorithm

text:
# Question
Title: MAX 10-SAT Algorithm
The MAX k-SAT problem is:

> “Given a set of clauses C1,…,Ck, each of length k, over a set of variables x1,…,xn, find a truth assignment that satisfies as many of the clauses as possible.”

I'm trying for find a randomized 0.999-approximation algorithm for the MAX 10-SAT problem. Help :(

# Answer
Try choosing a random assignment.
> 7 votes

# Answer
Have a look at chapter 5 of this book (available for free):

The Design of Approximation Algorithms by David P. Williamson and David B. Shmoys

The book discusses several randomized algorithms with different performance guarantees for **MAX-SAT** and **MAX CUT** (for details of the algorithms, you should have a look at the references in the book).
> -1 votes

---
Tags: algorithms, proof-techniques, dynamic-programming
---


# Question
Title: Find longest common subsequence in limited space
Given three strings $x$, $y$, and $z$ over an arbitrary finite alphabet, I need to determine their longest common subsequence (LCS).

**Example**: A longest common subsequence of `bandana`, `cabana`, and `magazine` is `aan`.

I'm trying to find an algorithm which uses $O(|x|\cdot |y| \cdot |z|)$ space where $|s|$ denotes the length of the string $s$.

# Answer
The standard dynamic programming algorithm for the LCS$(x,y)$ problem runs in time $O(|x|\cdot |y|)$. Simply speaking you fill out a $|x| \times |y|$ table $T$ using the recursion $$T\[i,j\] = \begin{cases} 0 & \mbox{ if }\ i = 0 \mbox{ or } j = 0 \\ T(i-1,j-1) + 1 & \mbox{ if } x\_i = y\_j \\ \max\\{T\[i,j-1\],T\[i-1,j\]\\} & \mbox{ if } x\_i \ne y\_j \\ \end{cases}.$$

A natural extension of this recursion leads to an algorithm that fills out an $|x|\times |y|\times |z|$ table and computes the LCS of three strings.

Notice that you can improve the required space even further (while keeping the asymptotic running time) using Hirschberg's extension.
> 3 votes

---
Tags: algorithms, algorithm-analysis, dynamic-programming, strings
---


# Question
Title: Example of a non-context free language that nonetheless CAN be pumped?
So basically L satisfies the conditions of the pumping lemma for CFL's but is not a CFL (that is possible according to the definition of the lemma).

# Answer
> 14 votes
The classical example is $L = \\{ a^i b^j c^k : i,j,k \text{ all different} \\}$. Wise shows in his paper A strong pumping lemma for context-free languages that neither the Bar-Hillel pumping lemma nor Parikh's theorem (stating that the set of lengths of words in a context-free language is semi-linear) can be used to prove that $L$ is not context-free. Other tricks like intersecting with a regular language also don't help. (Ogden's lemma, a generalization of the Bar-Hillel pumping lemma, does prove that $L$ is not context-free.) He also provides an alternative pumping lemma which is *equivalent* to context-freeness (for computable languages), and uses it to prove that $L$ is not context-free.

Wise's pumping lemma states that a language $L$ is context-free if and only if there is an (unrestricted) grammar $G$ generating $L$ and an integer $k$ such that whenever $G$ generates a "sentential form" $s$ (so $s$ can include non-terminals) of length $|s| \> k$, we can write $s = uvxyz$ where $x,vy$ are non-empty, $|vxy| \leq k$, and there is a non-terminal $A$ such that $G$ generates $uAz$ and $A$ generates both $vAy$ and $x$.

By repeatedly applying the condition in the lemma, Wise is able to prove that $L$ is not context-free, but the details are somewhat complicated. He also gives an even more complicated equivalent condition, and uses it to prove that the language $\\{ a^n b a^{nm} : n,m \> 0 \\}$ cannot be written as a finite intersection of context-free languages.

If you cannot access Wise's paper (it's behind a paywall), there's a typewritten version which came out as an Indiana university technical report.

---

A non-context-free language which satisfies the pumping condition of Ogden's lemma is given by Johnsonbaugh and Miller, Converse of pumping lemmas, and attributed there to Boasson and Horvath, *On languages satisfying Ogden's lemma*. The language in question is $$ \begin{align\*} L' &= \bigcup\_{n \geq 1} (e^+a^+d^+)^n(e^+b^+d^+)^n(e^+c^+d^+)^n \\ &\cup (a+b+c+d)\Sigma^\* \cup \Sigma^\*(a+b+c+e) \cup \Sigma^\*(ed+d(a+b+c)+(a+b+c)e)\Sigma^\*. \end{align\*} $$ We can write $L' = L\_1 \cup L\_2$, corresponding to the two different lines. Note that $L\_1 \cap L\_2 = \emptyset$ and that $L\_2$ is regular. Ogden's lemma can be used to prove that $L\_1$ is not context-free, and so neither is $L'$, but it cannot be used *directly* to show that $L'$ is not context-free.

# Answer
> 9 votes
Even simpler: $\\{a^m b^n c^n d^n\colon m \ge 1, n \ge 1\\}$. Can always pump the $a$s; intersection with the regular $\mathcal{L}(a b^+ c^+ d^+)$ gives a non-CFL (and that *can* be proved by pumping lemma).

# Answer
> 3 votes
A simple language is $\\{a b^n c^n d^n \colon n \ge 1\\} \cup \mathcal{L}(a a^+ b^+ c^+ d^+)$. Intersect with $\mathcal{L}(a b^+ c^+ d^+)$ to get a clearly non-CFL, but you can always pump the $a$, and mimetize the equal-length-ness in the sea of ${}^+$.

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


# Question
Title: What is the difference between "definition" and "inductive" in Coq?
In Coq, you can use two different kinds of keywords to do definitions--Inductive and Definition. I do not understand the difference between an inductive and a definition, or when it is appropriate to use one instead of the other.

Could someone with experience in Coq please shed some light on this, or provide a reference that is more succinct/informative on this point than the standard Coq tutorial?

**Update:**

Here are some additional, generally quite basic questions I have about Coq:

* How do you force a set to be finite? Is there a "finite set" data type?
* What exactly do ":" and ":=" mean?

# Answer
`Inductive` creates a new type and gives it a name. It is similar to `datatype` in SML, `data` in Haskell, `type` (defining an ordinary variant or a record) in Ocaml.

In addition to defining the type, `Inductive` also defines induction principles for that type. These induction principles aren't necessary from a theoretical point of view: all they do is to give a name to a particular well-typed term. They are provided because while you could write that term in your proof, it is mechanical and repetitive.

`Definition` gives a name to a term. It's broadly similar to `let` in SML or Ocaml or Haskell (but it doesn't let you write recursive definitions as such). Since Coq is pure (no side effects), if you write two definitions with the same right-hand side, the resulting names are equal. You can use `Definition` at any level of the sort hierarchy, including for types (in which case the definition is similar to `type` aliases in SML, Ocaml or Haskell).

`Fixpoint` is similar to `Definition`, but allows a recursive definition (like `let rec` in ML). It's in fact syntactic sugar for `Definition` plus the explicit fixpoint combinator `fix`, but definitions made using `Fixpoint` are easier to read and write.

The best way to understand these is to write a few proofs about some datatype. Try to rewrite some parts of the `List` library, for example.

There are several ways to implement finite sets in Coq. To to set theory proofs, try `Sets.Finite_sets`. If you want to have decent extracted code, use `MSets.MSetAVL`.
> 5 votes

---
Tags: automated-theorem-proving, coq
---


# Question
Title: Partial recursive function and Turing machine
The wikipedia article about primitive recursion states that

> An equivalent definition states that a partial recursive function is one that can be computed by a Turing machine.

My question is how one can write down formally this definition?

# Answer
You first define what a *partial recursive function* is, and then what a Turing machine is. Then you show that for every set (problem), there is a Turing machine computing it if and only if it is definable by a partial recursive function.

What you actually would do is to simulate a Turing machine by a partial recursive function and vice versa. Right to left is simple, left to right takes some work. You must define an encoding of the machine states (use of e.g. powers of prime numbers), the transition function, a *configuration* of a machine (i.e., what is currently on the tape, where is the head, and in which state is the machine) etc.
> 2 votes

---
Tags: terminology, turing-machines, recursion
---


# Question
Title: Is this simplified consensus problem easier than the original?
There is a famous Consensus Problem in Distributed Computing.

Let's consider and try to find the best possible algorithm for a simplified version of the consensus problem.

**Assumptions:** a process may undergo only crash failure (process abruptly stops and does not resume), process represent a complete graph.

**Simplification**: a crash failure may occur only between round, so there no a case when a process succeeds in sending some message and fails to send other message during the same round.

The algorithm for the general case ***FloodSet*** when a process may crash during the round is described in Distributed algorithms - Nancy Ann Lynch. By the analysis it was shown that $f+1$ rounds is enough to reach a consensus.

Intuitively, it looks like that the simplification completely changes the approach to the solution. It is may be enough just one round, every processes send an input message to every other processes and agree on the minimal value.

What is the simplest possible algorithms for simplified problem ?

What can we do in the case of general graph?

# Answer
> 4 votes
What you're describing as simplified problem is usually called consensus with *clean crashes*. You can just compute the maximum of all received messages once. To see that this is sufficient, observe that everyone receives the exact same messages after the first round. Thus everyone agrees on the same maximum value and all nodes decide correctly.

To solve crash-fault consensus on a general graph you need to assume $(f+1)$-connectivity. Then you could simulate each round of the FloodSet algorithm by flooding through the entire graph (taking $D$ rounds), yielding $D(f+1)$ rounds in total. I would be surprised if there's a more efficient way to do this (without additional assumptions on the graph, .e.g., high expansion).

---
Tags: algorithms, algorithm-analysis, distributed-systems
---


# Question
Title: Is “Find the shortest tour from a to z passing each node once in a directed graph” NP-complete?
Given a directed graph with the following attributes: - a chain from node $a$ to node $z$ passing nodes $b$ to $y$ exists and is unidirectional. - additionally a set of nodes having bidirectional vertices to at least two of the nodes $a \ldots z$ exists. These nodes are connected in a second unidirectional chain.

(the red route is the requested result, the squares are the first chain (unidirectional) and the circles are the second chain (unidirectional). $1$ is the start node and $5$ is the destination node.)

Is it possible to find the shortest path from $a$ to $z$ that includes nodes $b$ to $y$ and the additional nodes once without probing all possibilities?

I think the problem is roughly the same as the minimal traveling salesman problem since adding a vertex from $z$ to $a$ will result in the min-TSP - but this problem is slightly easier since a path from $a$ to $z$ is already known.

# Answer
> 6 votes
If I understood well the question, things are clearer if you draw the graph in this way:

And you can use the following polynomial time greedy algorithm to find an Hamiltonian path from the two endpoint nodes of the bottom line.

Suppose that the nodes on the bottom line are $B\_1,B\_2,...,B\_n$ and the nodes on the upper line are $U\_1,U\_2,U\_m$. You need to find an Hamiltonian path from $B\_1 \to B\_n$.

If you are on node $B\_i$, move to the first node $U\_j$ linked to it (first means leftmost in the upper chain), then scan $U\_{j+1}, U\_{j+2},...$ until you find a link from $U\_{j+k}$ to $B\_{i+1}$ and such that if $j+k\<m$ there is another link from $B\_{i+l}, l\>i$ to $U\_{j+k+1}$ (that will allow you to complete the upper line). If such $U\_{j+k}$ exists, add edges $B\_{i}\to U\_{j} \to ... \to U\_{j+k} \to B\_{i+1}$ to the final path, delete those nodes from the set and repeat the procedure from $B\_{i+1}$. If such $U\_{j}$ doesn't exist, add the edge $B\_{i} \to B\_{i+1}$ and repeat the procedure from $B\_{i+1}$.

---
Tags: algorithms, graphs, np-complete
---