title: Is legislation NP-complete?

text:
# Question
Title: Is legislation NP-complete?
I would like to know if there has been any work relating legal code to complexity. In particular, suppose we have the decision problem "Given this law book and this particular set of circumstances, is the defendant guilty?" What complexity class does it belong to?

There are results that have proven that the card game Magic: the Gathering is both NP and Turing-complete so shouldn't similar results exist for legal code?

# Answer
> 35 votes
Laws can include arbitrary language, and arbitrary language is able to express NP-complete logic. So in theory it would be possible to create an NP-complete or even an undecidable law. However, in practice the vast majority of criminal laws are simple decision trees.

Let's take, for example, section 187 (a) of the California penal code ("First Degree Murder").

> (a) Murder is the unlawful killing of a human being, or a fetus, with malice aforethought.
>
> (b) This section shall not apply to any person who commits an act that results in the death of a fetus if any of the following apply:
>
> (1) The act complied with the Therapeutic Abortion Act, Article 2 (commencing with Section 123400) of Chapter 2 of Part 2 of Division 106 of the Health and Safety Code .
>
> (2) The act was committed by a holder of a physician's and surgeon's certificate, as defined in the Business and Professions Code, in a case where, to a medical certainty, the result of childbirth would be death of the mother of the fetus or where her death from childbirth, although not medically certain, would be substantially certain or more likely than not.
>
> (3) The act was solicited, aided, abetted, or consented to by the mother of the fetus.
>
> (c) Subdivision (b) shall not be construed to prohibit the prosecution of any person under any other provision of law.

This can be expressed as a simple set of boolean logic.

```
IF !victim.isAlive
   AND victim.species == HUMAN
   AND defendant.hasKilled( victim )
   AND defendant.hadMaliceForethought
   AND !(     victim.age < 0
          AND wasTherapeuticAbortion
          AND defendant.profession == DOCTOR
          AND ( victim.survivalChance == 0 OR victim.mom.survivalChance < 0.5 )
          AND victim.mom.wantedAbortion )
THEN defendant.moveTo(PRISON)

```

Now there is of course a lot I trivialize here, like "what's malice forethought", "what is a therapeutic abortion" and "how do you determine the survival chance of a pregnancy". But these can also be expressed as similar boolean decision trees.

From a software engineering point of view, the legal system can be seen as a form of Business Rule Engine with the law being its ruleset.

That means that most laws have a computational complexity of `c`. If you also take the process of evidence examination into account which is required to determine the values of all these boolean variables, then the complexity becomes `n` where `n` is the amount of evidence which needs to be evaluated.

However, sometimes laws include language which isn't decideable at all and requires an external oracle. For example, when it mentions concepts like "reasonable doubt". What is "reasonable"? That's for a court to decide.

# Answer
> 96 votes
It's undecidable because a law book can include arbitrary logic. A silly example censorship law would be "it is illegal to publicize any computer program that does not halt".

The reason results for MTG exist and are interesting is because it has a single fixed set of (mostly) unambiguous rules, unlike law which is ever changing, horribly localized and endlessly ambiguous.

# Answer
> 10 votes
This is a very interesting question.

Law is somewhere between everyday language with its arbitrary, constantly changing and often soft rules, and programming language with its very specific, defined rules.

Legalese actually **defines** its terms and thus many words (but not all!) used in the law actually do have precise meanings.

However, **interpretation** is where your approach of presenting a case to a logical system and getting a result will fail. The law is a generic definition that needs to be adapted to the specific case in question. Often this is a trivial, straightforward process, but there is no guarantee that it is and no non-trivial way to define the boundary.

A good example is self-defense. In most law systems, you can lawfully hurt another person provided that you are acting in self-defense. However, the wording is explicitly context-sensitive. For example, the british criminal law writes:

> A person may use such force as is reasonable in the circumstances in the prevention of crime \[...\]

Case law defines what is "reasonable" **in specific cases**, but no general definition is on the books. There is also case law clearing up what exactly "prevention of crime" means. Since by definition a crime has not yet occurred, much less a court having decided that the action was, in fact, a crime, **reasonable belief** is enough in this particular case, but that is not actually written in the law!

To create a digital decision maker about the law, you would have to feed it not just the law itself, but also all the case law, a lot of natural language understanding, and a lot of rules about how to **apply** all that knowledge, because sometimes case law is solid, sometimes you can bend it (especially if it is old, as interpretations change over time).

And finally, the law changes and adapts, not just in the book, but also in its interpretations. There are many famous examples of highest courts overruling their own 20-year old decision. Very often, such challenges to previous case law happen exactly because a judge decided to go against those established laws and he would rather take the risk of being overruled at the higher court than pass down a decision he does not stand behind. I wonder how you would model this ability in an NP-complete system?

To calculate the complexity of a system requires us to understand the inputs and outputs. The law, however, is an open system. Literally anything in its environment can influence it, especially changes on society and culture. Most countries have laws on the books that are rarely applied anymore because society has changed, but the law-making process lags behind. Laws against homosexuality are a current example. Or the death sentence, which in most countries had not been actually applied for years or decades before it was removed from the law books. And not because there were no cases where it could have been applied, but simply because judges did not apply it despite having the choice.

These environmental factors make a complexity estimate almost impossible, because we cannot enumerate them in a finite list unless we use all-quantors (e.g. "every kind of ..." or "all the ...")

# Answer
> 8 votes
NP-completeness, as with other complexity classes, has to do with problems that take an input of varying size, whose size we denote by *n*. In particular:

* A problem is **NP** if it's possible to determine whether any proposed solution is actually a solution with runtime polynomial in *n*.
* A problem is **NP-complete** if it is NP and moreover every NP problem can be reduced to it by a reduction process with runtime polynomial in *n*.

In the problem you propose, namely

> Given this law book and this particular set of circumstances, is the defendant guilty?

I'm not sure what *n* is meant to be. It seems like the inputs here are the "set of circumstances" and the name of the defendant. Only the former could be of varying length, but then what do we even mean by the "set of circumstances"? Do we just feed in an arbitrary number of arbitrary facts like "the defendant owns purple socks" and "the judge had a sandwich for lunch today" or what? Moreover, are there constraints on these circumstances, or can we feed in a "circumstance" like "the barber of Seville shaves precisely those barbers who do not shave themselves"?

I don't think this question is well-posed, nor do I see any obvious way to make it well-posed.

# Answer
> 5 votes
I think what's missing in the excellent answers so far is that computation theory assumes known, certain, input data, whereas legislation is operating in a field where the facts are usually uncertain and fuzzy. Criminal law, for example, concerns itself with the "intent" or "state of mind" of a defendant, which can never be known with certainty. The divorce courts have to decide whether a marriage has "irretrievably broken down". There can never be an algorithm for deciding that question.

# Answer
> 0 votes
While some answers say it's undecidable, I suppose it's not what laws are for, as they are not enforceable.

If it's restricted in some ways that make it always decidable, it probably does not make much sense to talk about the actual complexity. It's because the inputs of laws as functions are generally not the definitions of events in the law, as in a card game, but evidences of events being legal or not.

There could be arbitrarily much evidences about a single event. For an event, there isn't an objective input length to make it possible to define the complexity. And for a given set of evidences, while there is an input length, the laws don't usually specify that someone must have a definite conclusion. They could, and usually prefer to try collecting more evidences even if the answer could be theoretically deduced logically in a difficult way. And a suspect could admit to something in a puzzling way to boost the complexity artificially if one has to work without evidences.

There would be more problems if cryptography is involved. They could theoretically reverse a strong encryption algorithm if they could compute for very long, but they may break the confidence of a signature algorithm to make it not usable as an evidence at the same time.

# Answer
> 0 votes
Jury members ultimately render verdicts based on applicable law given by judges to the jury to follow and the facts as determined by the jury using the factors in the jury instructions. Especially credibility of witnesses...who to believe. Not reducible to an algorithm.

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


# Question
Title: Nearest Insertion Traveling Salesman Heuristic: is it faster to insert nearest nodes first?
I am trying to implement the nearest insertion TSP heuristic. However, I am wondering if it matters which node I insert into the subgraph first.

For example, should I start with one node; calculate the distance between this node and the other nodes; and sort the other nodes by this distance? Then, I will insert the closest node (to the first node) first. Will this be faster than randomly choosing nodes to insert?

# Answer
> 0 votes
Inserting a random point instead of a nearest point can be faster, but then you are not following the nearest insertion heuristic anymore. The key is to realize that the point is not the runtime efficiency of the algorithm, but rather the *quality of the solution obtained*. Indeed, remember that we are dealing with an NP-hard problem.

The nearest neighbor heuristic should return considerably shorter tours than random insertion. In fact, we can *prove* that the ratio of the nearest insertion heuristic's solution to the minimum tour length is bounded by $O(\log n)$, where $n$ is the number of cities. No such guarantee exists for the random insertion that you propose, i.e., such a heuristic can return very long tours.

---
Tags: algorithms, heuristics, traveling-salesman
---


# Question
Title: Color a graph using k colors, k>4, with the most equal distribution of colors
Given a planar graph G with $N$ nodes, 4 colors are enough to color each node, so that adjacent nodes have different colors.

Let $k \> 4$. Is there an algorithm to color the nodes with $k$ colors, so that the colors are distributed the most equally possible?

In other words:

Let's call $c\_1, ..., c\_k$ the colors. We define $\forall c\_k\in\[1,k\], f(c\_k)=\textrm{number of nodes of color}c\_k$. Obviously, $\sum f(c\_k) = N$. Find an algorithm to color the $N$ node with the $k$ colors to maximize the value $\min f$, with 2 adjacent nodes having different colors.

# Answer
> 1 votes
You are perhaps looking for an equitable coloring, which is a proper coloring where the size of any two color classes differ by at most one. Finding an equitable 3-coloring is NP-complete for planar graphs.

---
Tags: algorithms, graphs, colorings
---


# Question
Title: Trouble understanding this proof about the minimum number of states of a deterministic finite automaton
So I was browsing online looking for the general structure to proving a DFA has a minimum of $n$ states for some $n$ and most of them use contradiction. However, I'm having a hard time understanding why the proof of proposition 5 works in proving the statement.

My understanding of the proof is that we assume there's a DFA consisting of $\<n$ states and we construct $n$ strings. We then use the pigeonhole principle which would mean that two of these strings would have to be in the same state meaning that if we append a new string to both of these strings that are currently in the same state, these new strings should either both be accepted or rejected. This is where we want the contradiction.

I have two questions,

1) Do we have to make strings such that each would be in its own state or can we just make a set of any $n$ strings and so long as we can append something to each pair such that one of the strings in the pair is accepted and the other, rejected (leading to a contradiction)?

2) Does the proof imply that there is a DFA of exactly six states or just that there aren't any DFAs of five, four, three, two,or one state(s)?

# Answer
Let $L$ be an arbitrary language. We say that two words $x,y$ are *equivalent modulo $L$*, written $x \stackrel{L}{\sim} y$, if for all words $z$, either both $xz,yz$ are in $L$, or both are not in $L$.

**Lemma 1.** Suppose that $x\_1,\ldots,x\_n$ are pairwise inequivalent modulo $L$. Then any DFA for $L$ must contain at least $n$ states.

**Proof.** Consider a DFA accepting $L$. Let $q\_i$ be the state that the DFA reaches after reading $x\_i$. I claim that $q\_1,\ldots,q\_n$ are all distinct. Indeed, consider any two states $q\_i,q\_j$. Since $x\_i,x\_j$ are inequivalent modulo $L$, there exists a word $z$ such that $x\_iz \in L$ and $x\_jz \notin L$, or vice versa; without loss of generality, assume the former. Since $x\_iz \in L$, $\delta(q\_i,z)$ must be an accepting state, whereas since $x\_jz \notin L$, $\delta(q\_j,z)$ must not be an accepting state. This shows that $q\_i \neq q\_j$. $\quad\square$

This is the method which is used in Proposition 5 that you mention.

What is the best lower bound that Lemma 1 can give us? Once you notice that $\stackrel L \sim$ is an equivalent relation, it is not hard to check that the maximum $n$ that you can choose is the number of equivalence classes of $\stackrel L \sim$:

**Corollary 2.** Any DFA for $L$ must contain at least $n$ states, where $n$ is the number of equivalence classes of $\stackrel L \sim$. In particular, if $\stackrel L \sim$ has infinitely many equivalence classes, then $L$ is not regular.

It is natural to ask whether this method is optimal:

1. If $L$ is not regular, can we always prove this using Corollary 2?
2. If $L$ is regular, is there always a DFA having $n$ states?

The positive answer to both questions is the main result of *Myhill–Nerode theory*, which you might learn about in the future.
> 1 votes

---
Tags: automata, finite-automata, proof-techniques
---


# Question
Title: Monte Carlo Algorithms : Are there any problems where two opposite Monte Carlo algorithms could solve it?
I started reading on Probabilistic algorithms and Monte-Carlo algorithms. Since a Monte-Carlo can only give a certain answer for either True or False, I was wondering if it's conceivable that **for the same problem**, there exist two opposite Monte-Carlo Algorithms capable of giving a certain answer. (By opposite, I mean one would be sure when it's FALSE, and the other would be certain when it's TRUE)

**For example** : There exist a prime number test Monte-Carlo based algorithm that can check whether or not a number "n" is prime. If the answer is FALSE, then "n" is not a prime number (it is a composed number). However, if the answer were to be TRUE, then "n" COULD be prime (with a certain probability). To my knowledge, there is no efficient algorithm (Monte-Carlo) capable of saying with certainty if "n" is a prime number.

# Answer
> 2 votes
A *Las Vegas algorithm* is one which is always correct, but is only efficient in expectation. Given two "opposite" Monte Carlo algorithm, you can create a Las Vegas algorithm by alternating both algorithms (or running them in parallel), halting whenever one of them produces a certain answer.

In the language of complexity theory, this corresponds to the statement $\mathsf{ZPP} = \mathsf{RP} \cap \mathsf{coRP}$. You can find more information on $\mathsf{ZPP}$ on Wikipedia.

---
Tags: probabilistic-algorithms, monte-carlo
---


# Question
Title: Determining initial and final states from FA diagram
I am new to automata. And learning to find concatenation of two FAs. But this one has confused me

I know how to do concatenation but I am confused that in FA 1, what does **x1** means? Is it mean final state or does it mean both initial and final state because it is on the start?? Just clear me on this that what is initial state and what is final state in **FA 1**? Then I'll take it from here and will be able to do concatenation.

P.S I know that **+-** in a state mean both initial and final state but I don't know about double circle form. Kindly help me on this.

# Answer
> 0 votes
In your diagrams, a triangle points at the initial state, and double circles indicate final states. Inside the circles you can find the state names, such as `x1`.

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


# Question
Title: Number of states in DFA equivalent to given NFA
Let's say there is a NFA with $n$ states with an alphabet consisting of $x$ symbols. I convert it to an equivalent DFA. Can I say that the number of states in the equivalent DFA is $x^n$?

# Answer
The standard powerset construction takes an NFA with $n$ states over an arbitrary alphabet and produces a DFA with $2^n$ states; this is tight for alphabets containing at least two symbols (see Chrobak's paper below for several references for this).

As for unary alphabets, Chrobak showed in his paper Finite automata and unary languages that a unary NFA with $n$ states can be converted to a unary DFA with $O(e^{\sqrt{n\log n}})$ states, and showed that this is tight (up to the hidden constant factor).
> 1 votes

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


title: Dominance Law in Boolean Algebra

text:
# Question
Title: Dominance Law in Boolean Algebra
The dominance law states that **x + 1 = 1**

If we go by that logic, does that mean that **x' + 1 = 1?**

Please just tell me if it's a yes(as I think that this is the answer but I just want to clear my doubts) and maybe provide a little explanation if it's a no.

Thanks!

# Answer
> 1 votes
If $x+1=1$ then, substituting $x'$ for $x$, we deduce that $x'+1=1$.

In other words, your claim follows from the fact that $x'$ has the same "type" as $x$.

# Answer
> 0 votes
That is correct.

In Boolean Algebra, '+' is synonymous to '∪' (**union**), and your problem can be illustrated as the '**or**' logic gate to better understand it:

If we allow *B* to be 1, *Z* is always 1, regardless of the state of *A* (in your case, it could be X or X').

---
Tags: algebra
---


# Question
Title: Why do we use $\Gamma$ to denote a TM's tape alphabet?
In many formal definitions of Turing machines, the Greek letter $\Gamma$ is used to denote the tape alphabet of the TM.

What is the origin of using $\Gamma$ for this? I'm having a hard time imagining what this might stand for.

# Answer
> 2 votes
Following up on @PartialOrder's comment, while $\Gamma$ is not used in Chomsky & Schutzenberger or in Chomsky's 1962/1963 papers on PDAs, it is used in Ginsburg and Greibach 1966 as follows:

> A *pushdown automaton* (abbreviated *pda*) is a 7-tuple $M=(K,\Sigma,\Gamma, \delta, Z\_0, q\_0, F)$ where \[...\]

Here $K$ is the set of states and $q\_0$ is the start state. $\Gamma$ is the finite nonempty set of auxiliary symbols. $F$ is the set of final states. $\Sigma$ is the finite nonempty set of inputs. Etc.

Nowadays we would call the set of states $Q$ if the start state is called $q\_0$. I think this just indicates that not too much consistency and reason was required for these letter choices.

This is "original research" but I figure $\Gamma$ may just have been used since it is **the first capital Greek letter (to indicate the same type as $\Sigma$) which looks distinctly greek** (A and B looking Roman as well).

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


# Question
Title: How binary search works in real world scenario?
In binary search, we need an array of **integers** for it to search for an element. Also, many other sorting algorithm sorts array of **integers**.

But in real world, we may search for a name of an employee in a database, title of a post etc. So how does binary search actually works in such cases? Is the data converted and stored in some numeric format? Then how does it point to the original record?

Please explain in detail with a small example if possible.

# Answer
As Prof. Filmus said, it isn't necessary for Binary Search Trees (hereafter referred to as BST's) to necessarily have ints/Integers as the data within the nodes.

At least in Java, all we need is data that is either Comparable to itself or some superclass of itself (implementing Comparable) or can be compared with an outside tool (using a Comparator). But I digress, as that is language-specific. It should be clear however that we only need elements to be comparable/order-able. They do not only need to be integers.

You could always, theoretically, use BSTs to model decision making, as you're simply going through Decision A or Decision B at any given point. You'd have to create Decisions that were comparable to one another, but that's fuzzy on my end.

Let me therefore take an example in your post - searching through a database for a name. Of course, names are usually encoded as Strings (a sequence of characters, informally speaking). Strings are usually ordered *lexicographically*, that is, by alphabetical order. This means that to retrieve a given String from a BST of Strings, we'd start at some root node which contains a root String (consider a String of this database in the M or N range, as that is the middle of the English alphabet), and if the name comes after M/N or before M/N, it will go to the right node or the left node of the root node (containing the *middle* name), respectively.

Theoretically, you could encode the entire English lexicon into one very large BST, if you have a word that you've set as the exact middle of the English language. Every word that isn't the exact middle word would be coming after or before said word, alphabetically speaking.

I'd point you to this link, about Legislation perhaps being NP-Complete, for some discussions about decision trees. This may be an interesting, albeit not necessarily appliable analogue with BST's: Is legislation NP-complete?

Hope this helps!

EDIT: Edited to say "Prof. Filmus..." as that is more formal.
> 9 votes

---
Tags: algorithms, search-algorithms, binary-search
---


# Question
Title: Language of all strings that has exactly 1 triple b
I am new to automata and learning to make regular expression for languages. But I have been stuck on this one.

Suppose we have a language L, Language of all strings that has exactly 1 triple **“b”** defined over alphabet set **Σ = {a, b}**
Now after several tries, I came up with this **(a\* (ab)\* (ba)\* )\* bbb (a\* (ab)\* (ba)\* )\*** but then I realize that this is wrong too because the string **abbbabababb** doesn't fit on this.

Kindly someone point out at my mistake or help me solve it as I have spent almost an hour on this.

# Answer
> 2 votes
To be clearer, we use "triple $b$'s" to mean three consecutive $b$'s.

What you would like to figure out first is a detailed description or characterization of a string that has not triple $b$'s and that does not end at an $b$, the part of the string that is before that triple $b$.

That string should start with zero or more $a$'s, possibly followed by one or two $b$'s followed by one or more $a$'s, possibly followed by one or two $b$'s followed by one or more $a$'s, and so on for some rounds. That is, $a^\*((b\mid bb)aa^\*)^\*$.

So, a regular expression could be $a^\*((b\mid bb)aa^\*)^\*bbb(aa^\*(b\mid bb))^\*a^\*$, or written symmetrically, $a^\*((b\mid bb)aa^\*)^\*bbb(a^\*a(bb\mid b))^\*a^\*$.

# Answer
> 4 votes
It seems you are almost there. You just need to care substrings with $abb$. One possible way is $R.E = (a^{\*} (ba)^\*(bba)^\*)^\*bbb(a^\*(ab)^\*(abb)^\*)^\*$

Note that I came upon this regular expression from the $FM$ of language you described. So, another way to find $R.E$ is from $FM$ directly.

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


# Question
Title: In pipelining (at least, in MIPS), why is the incremented program counter address saved in the IF/ID pipeline register?
In D. Paterson's book, *Computer Organization and Design, Fifth Edition*, there is a paragraph that says

> Instruction fetch: The top portion of Figure 4.36 shows the instruction being read from memory using the address in the PC and then being placed in the IF/ID pipeline register. The PC address is incremented by 4 and then written back into the PC to be ready for the next clock cycle. **This incremented address is also saved in the IF/ID pipeline register in case it is needed later for an instruction, such as `beq`**. The computer cannot know which type of instruction is being fetched, so it must prepare for any instruction, passing potentially needed information down the pipeline.

I'm trying to understand why an incremented address must be saved in the IF/ID pipeline register, at least in MIPS. I understand that it might be needed by some instruction somewhere later.

However, how does an instruction such as `beq` use the program counter value?

# Answer
> 2 votes
beq doesn't contain the destination address in the instruction, but an offset relative to the location of the instruction. For example "branch if equal to the instruction 12 words ahead of the branch instruction". You cannot execute such an instruction if you don't know what the address of the branch instruction was.

---
Tags: computer-architecture, mips
---


title: How come O(n) + O(logn) = O(logn)

text:
# Question
Title: How come O(n) + O(logn) = O(logn)
How come O(n) + O(logn) = O(logn)?

When talking for example about an algorithm that has two operations. One of them takes O(n) and the other O(logn) and in the end we say that the total complexity is O(logn). It doesn't make sense to me since n is bigger than logn.

# Answer
As Chi say to you, if you have in a program two operations, one $\mathcal{O}(log{}n)$ and another $\mathcal{O}(n) $ you must take a superior bound, and your result will be $\mathcal{O}(n)$ in this case.

you can see here the complexity graph. If you say, that one operation take time $\mathcal{O}(n) $ , and nobody other operations take more of this, you can be at least $\mathcal{O}(n) $ time complexity. If just one operation are over $\mathcal{O}(n) $, the complexity will be change in new bound (and so on).

P.s Sum two bound, will maintain the most higher, multiply increse time complexity, like two neasted loop of $\mathcal{O}(n)$ will give you $\mathcal{O}(n^2)$ complexity.

I hope that this will help you.
> 2 votes

---
Tags: asymptotics, landau-notation
---


# Question
Title: Find all values repeating more than $\lfloor n/k \rfloor$ times in $O(n \log k)$ time
Given a parameter $k$ and an array (not sorted) of length $n$ return all values which repeat more than $\lfloor n/k \rfloor$ times in $O(n \log k)$ time.

I've managed this in $O(nk)$ time, but can't figure out how to do it in the required performance.

# Answer
> 13 votes
The Misra-Gries summary is a simple technique which will find, for a given $k$, all elements in a sequence of $n$ elements which occur more than $\lfloor n/k \rfloor$ times, introduced in the 1982 paper *Finding Repeated Elements* as a generalization of the more well-known Boyer-Moore majority vote algorithm, which is essentially the case where $k = 2$.

The Misra-Gries summary can be computed in $O(n\log k)$ time and $O(k)$ space with a single scan of the sequence. However, it always returns $k-1$ distinct values without any guarantee that any of them satisfy the criterion; it only guarantees that if a value satisfies the criterion, it will appear in the list. Reducing the summary to the required values requires a second scan of the sequence to count the occurrences of each candidate value. This scan can be performed in $O(n \log k)$ time by the simple expedient of putting the $k$ values into an associative array implemented with a balanced binary search tree, such as a red-black tree.

In fact, constructing the BST for the second scan is not really necessary because the $O(n \log k)$ Misra-Gries computation actually produces such a tree. The computation can be performed as follows:

1. Initialise an empty associative array $\mathit{C}$ which maps sequence elements onto non-negative integers. The array will have a fixed capacity of $k$ elements, but may contain empty slots.
2. For each element $a$ from the sequence in turn:

1. *Precondition*: $C$ contains at most $k-1$ pairs.
    2. If $a\text{ is in }C$, increment its associated value.
    3. Otherwise, add $\langle a, 1\rangle$ to $C$.
    4. If $C$ now has $k$ pairs, decrement all of the associated values and remove all keys whose associated value is $0$. \[Note 1\]
    5. *Postcondition*: $C$ contains at most $k-1$ pairs.
3. At the end of the scan, $C$ contains at most $k-1$ pairs with distinct keys, which include all elements which appear in the sequence more than $\lfloor n/k \rfloor$ times.

The proof of the postcondition is simple: If step 2 was performed, the size of $C$ was not changed, so it is still at most $k-1$ because of the precondition. Otherwise, step 3 is performed, after which $C$ contains at most $k$ because step 3 adds exactly one pair to $C$. If step 4 is performed, there must be at least one pair whose associated value is $0$ and will be deleted from $C$, because step 4 can only be performed if step 3 was performed and step 3 adds a pair with associated value $1$ to $C$.

The intuitive explanation of why any element repeated more than $\lfloor n/k \rfloor$ times must be in $C$ at the end of the scan is explained by @YuvalFilmus in this related question.

The fact that the scan takes $O(n \log k)$ time can be seen from a simple amortised time analysis of the iteration. Every element from the sequence will be added to $C$ exactly once, either in step 2 or step 3, each of which take $O(\log k)$ since $C$ has at most $k$ pairs. Furthermore, each element (except for the $k-1$ final candidates) will be decremented exactly once in some occurrence of step 4. (Step 4 decrements $k$ values, but each decrement pertains to a different element of the original sequence, so the total number of decrements is $O(n)$. Another way to look at this is to observe that step 4 can be performed no more than $\lfloor n / k\rfloor$ times.)

Each decrement in step 4 consumes $O(1)$ time, but at least one pair must be deleted from $C$, which requires $O(\log k)$ time. Again, we rely on amortised analysis to see that the total number of deletions is $O(n)$.

---

In practice, this algorthm will usually be implemented with a hash table rather than a balanced binary tree. The hash table implementation replaces the guaranteed $O(\log k)$ steps with expected $O(1)$ (but worst case $O(k)$). Since the worst case is extremely unlikely, the hash table algorithm is generally cited as linear-time, although strictly speaking it is linear *expected* time.

---

### Notes

1. As an optimisation, it's possible (and, I believe, common) to avoid adding and removing $a$ in a single iteration. It is also unnecessary to remove pairs which have been decremented to 0 provided you can find such a pair in $O(1)$ for step 2. This can be done with a bit of bookkeeping. You can also implement "decrease all counts by one" by using a base value (so that the values are the stored value minus the base value) and incrementing it by one to effectively decrement all counts. All that will change the iteration step from amortized $O(1)$ to guaranteed $O(1)$ but the extra bookkeeping is likely to result in a slower total execution time.

---
Tags: algorithms, data-structures, time-complexity
---


# Question
Title: How to prove if a heuristic function is admissible or not
Can somebody tell me how to solve this problem?

# Answer
> 0 votes
Euristic is ammisible if and only if not overestimate the result. My hint is check if your euristic follow this rule. Check the cost of your euristic, with simple substitution. Good euristic for your problem is movements cost 1.

I hope that help you.

---
Tags: heuristics
---


# Question
Title: Is it possible to create a regular language from an non regular language? (details inside)
I am wondering, is it is possible to create a regular language from a non regular language if we add or remove finite number of words from it?

say L is irregular, if we add or remove finite number of words can we create a regular language?

i might be mistaken, but since all regular languages are finite - if we add a finite amount to a non regular language - it still stays non regular, but if we substract, let's say a finite amount from infinity, it is still infinity.

so is it safe to say that in both cases a regular language cannot not be obtained by adding/substracting a finite amount of words?

i was told to ask this question here rather then in softwareengineering.

thank you very much for your help. really curious about that

# Answer
> 3 votes
We have a language $L$ which is non-regular. We subtract a finite subset $S \subset L$ of words in $L$ to get the rest: $R = L \setminus S$.

Assume that $R$ is regular. Since regular languages are closed under union, and finite sets of words are trivially regular, we can construct a language $L' = R \cup S$ which is also regular.

Since $S \subset L$, we have $(L \setminus S) \cup S = L$, thus $L' = L$. But $L'$ is regular while $L$ is not - a contradiction. Thus our assumption that $R$ is regular was wrong.

---
Tags: automata, regular-languages, finite-automata
---


# Question
Title: Is there any example of Regression Tree driven optimization (or active learning)?
Bayesian Optimization is the classic example of meta-model driven optimization where new observations are used to train a Gaussian process that provides a clue to where to optimize next.

LEM (Learnable Evolution Models) are evolutionary models where rather than recombining observations (like GAs) a population is fit to a classifier to find out which areas are more promising (although the method itself has quite a lot of non-statistical operations on top of this).

I was looking for something simpler where the optimization is driven by a simple regression tree (sample from most promising leaf or through some bandit algorithm on the leaves). However I can't seem to find any reference on the subject. It must have been tried before.

# Answer
An active learning approach using which combines an incrementally-learned Regression Tree with bandit-style sampling from leaf nodes to determine which instance to request a label for next is described in the “Adapting to Concept Drift in Credit Card Transaction Data Streams Using Contextual Bandits and Decision Trees” paper (**disclaimer**: I'm an author on the paper).

A short summary:

* A regression tree is learned to predict targets $\hat{y}$ based on feature vectors $x$. This is done with an incremental tree learner, it can grow over time as labelled data becomes available (for instance due to active learning)
* Every node in the regression tree also contains linear models that are trained such that we can additionally distinguish between different instances within the same leaf nodes. Training linear models in *all* nodes, rather than only the leaf nodes or only the root node, allows us to both generalize across the tree as well as specialize for subsets of the tree.
* Predictions made by linear models be treated as "ground truth" labels for unlabelled instances and plugged into the Regression Tree Learner to allow the tree to grow more quickly than it could if we only used data with real labels (Semi-Supervised Learning).
* Leaf nodes are treated as arms of a Contextual Multi-Armed Bandit (contextual because we also happen to have feature vectors for instances drawn from leaf nodes)
* A Contextual Multi-Armed Bandit algorithm is used to select unlabelled instances for which we'd like to obtain labels (i.e. active learning)
> 2 votes

---
Tags: optimization, machine-learning, bayesian-statistics
---


# Question
Title: Algorithm to find smallest number divisible by N with sum of digits as N
Problem:

> Given $N$, find the smallest number divisible by $N$ whose sum of digits is equal $N$.

For example:

* $n = 1$, answer is $1$
* $n = 10$, answer is $190$

There is some dynamic programming algorithm, but I can't find it. It is sequence https://oeis.org/A002998.

# Answer
> 1 votes
Here is some Python code that solves this problem:

```
def niven(s, base=10):
    # if s < base:
    #     return s
    best = dict()
    best[(0, 0)] = 0
    new_candidates = dict()
    new_candidates[(0, 0)] = 0

    target_key = (s, 0)
    dc = 0
    while (True):
        dc += 1
        candidates = new_candidates
        new_candidates = dict()
        for ((ds, r), v) in candidates.items():
            vhi = v * base
            rhi = r * base
            for d in range(0, base):
                nv = vhi + d
                nds = ds + d
                nr = (rhi + d) % s
                nkey = (nds, nr)
                if nkey not in best or nv < best[nkey]:
                    best[nkey] = nv
                    new_candidates[nkey] = nv
        if target_key in best:
            return best[target_key]

for i in range(1, 20):
    print "%d => %s" % (i, str(niven(i)))

```

The logic behind this code is following:

For a fixed sum `s` the dictionary `best` contains the best solution for a more general problem: given digits sum `ds` and reminder `r` what is the minimal number with that sum of digits and that reminder modulo `s`? Obviously the solution for our problem is the record in that dictionary for a key `(s,0)`.

So now the question is how to fill the dictionary? The algorithm is based on a simple formula for calculating reminder for a number with a known last digit `d`:

```
(10*v + d) mod 10 = (10*(v mod 10) + d) mod 10

```

In other words, the best solution for some key `(ds, r)` should be based on the best solution for a smaller number with a last digit added for some of the possible last digits

```
best(ds,r) = min(for d in [0..9] of d + 10 * best(ds-d, (r-d) mod 10) if ds > d))

```

which is exactly a dynamic programming problem. The code above fills the `best` dictionary starting from an obvious solution `best(0,0) = 0`. It stops after it has processed all the solutions of `dc` digits if the `best[(s,0)]` is filled now. This works because obviously any number of `dc+1` digits is bigger than any number of `dc` digits.

# Answer
> 1 votes
Assuming that "number" means "positive integer", every number divisible by $N$ must be at least $N$. Conversely, $N$ has the same digit sum as itself. Therefore the answer is simply $N$, as your two examples demonstrate.

# Answer
> 0 votes
Note that the question has changed: There is an answer for the trivial question "Find the smallest multiple of N which has the same digit sum as N". The more sensible question is "Find the smallest multiple of N which has the digit sum N". For example for N = 10, the first multiple of 10 with a digit sum 10 is 190 (1+9+0 = 10).

(It seems that SergGr's answer is much better... :-)

The solutions for 0 ≤ N ≤ 9 are trivial, so assume N ≥ 10.

Start with k = 0. Define d(x) = "sum of decimal digits of x". Replace k with the first integer k' \> k with d(k') = N. If k' is a multiple of N then we are done. Otherwise replace k with the smallest multiple of N which is greater than k' and start all over.

How do we find k'? Starting with k' = k, if d(k') \> N then add the number from 1 to 9 which makes the last digit 0. If still d(k') \> N then add the number 10, 20, 30, ... 90 to make the last two digits 0, and so on until d(k') \<= N. As long as d(k') \< N add 1, or add 10 if the last digit is 9, or 100 if the last two digits are 99, and so on.

---
Tags: dynamic-programming
---


# Question
Title: DFA that accepts strings with last character being repeated at least 1 time before
I'm trying to design a DFA in a 4 digit language, for example L(a,b,c,d) or L(1,2,3,4) that accepts strings with the last character being already repeated before.

Everyway im trying, i get so many transitions im literally lost in them...

So, for example, abbdb is accepted (because b is showed again at least 1 time) but abc is rejected since c (last char) never shows up more than 1 time.

I managed to make it work for a language with 2 DIGIT:
For example:
Which accepts for example aa or ababa but can't do for 4 DIGIT language.

# Answer
> 2 votes
I would write out a description of this machine rather than drawing it.

* States ($Q$): the states of this machine are five-tuples $(\alpha, \beta, \gamma, \delta, \sigma)$: alpha, beta, gamma, and delta are in $\\{0,1\\}$ and record whether or not the corresponding symbol has been seen before, while sigma is in $\Sigma \cup \textrm{Nothing}$ and indicates the last symbol read.
* Alphabet ($\Sigma$): the alphabet, as you specified, is $\\{a,b,c,d\\}$.
* Start ($q\_0$): the starting state is $(0,0,0,0,\textrm{Nothing})$. In other words, we've seen no symbols yet, and the previous symbol read was nothing.
* Final States ($F$): a state is final if the last symbol read was seen before. For example, the state $(1,\\#,\\#,\\#,a)$ is final, regardless of what those $\\#$s in the middle are.
* Transition function ($\delta$): this is the trickiest part. If we're in a state $(\alpha, \beta, \gamma, \delta, \sigma)$ and see the symbol $s$, we want to go to the state where $s$ has been seen, and where $s$ is the last symbol read. If we see $a$, for example, we go to state $(1, \beta, \gamma, \delta, a)$: we mark that $a$ has been seen, don't change $\beta$, $\gamma$, or $\delta$, and record $a$ as the most recently read symbol.

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


# Question
Title: Are you allowed to change the specifications of a problem when doing reductions?
I'm doing a polynomial time reduction from problem **A** (known graph problem) to problem **B** (funky and specific longest path problem). There is a lot of demands on how problem **B** is supposed to be solved. However, the input of problem **A** does not give me enough information to be able carry out all of these demands that problem **B** require.

My reduction will look something like this:

```
**A**(G(V, E), K) =
     a = V
     b = E
     P = **B**(a, b, K)
     if(P)
         return true

```

My question is if it is okay to ignore some of these demands and simply change the **B** problem to a simpler one which then would allow me to find a reduction which satisfies both problems?

I'm sorry for being so vague, it is a homework problem and I would like to not publish the details.

# Answer
It doesn't matter what B exactly is, it could be graph problem or something else. Nobody cares as long as you construct its instance in polynomial time and it has a solution precisely when the instance of A has. Maybe you need to use some structure of A to construct B, but maybe some parts of A don't need to be used at all, who knows.

So precisely what you must do is follow the definitions, and then everything is fair game with no authority setting any special rules.
> 2 votes

---
Tags: graphs, reductions, polynomial-time
---


# Question
Title: Big O notation for finding duplicates in a list using binary search
I've written an algorithm to find duplicate integers in a sequential list of integers, but I'm running into issues when trying to calculate it's worst case complexity.

Given a sequential list of integers the algorithm is as follows:

```
1. get the length of the list of integers, assign to list_length - O(1)
2. while list_length is greater than 0: O(n)
  1. remove the item at index 0 from the list and assign to checking - O(1)
  2. set list_length to the current length of the list
  3. perform a binary search of the remaining list for the value assigned to checking - O(log n) where n is the current length of the list
  4. if the item is in the list return True
3. if none of the binary searches found a match return False

```

My understanding is that the complexity of a binary search is $O(\log n)$ and if I were not to remove an item from the list on each iteration, the complexity of my algorithm would be $O(n \log n)$ (as I am running an $O(\log n)$ algorithm $n$ times).

What I am not sure of is how the shortening of $n$ will affect the binary search, as on each iteration the complexity of the binary search will change: $O(\log (n - 1))$ on the first iteration, then $O(\log (n - 2))$ on the second.

How do I represent the diminishing size of $n$?

# Answer
I have two different points:

1. As for complexity of your algorithm I believe this still to be `O(N*log N)`. Consider the first half of the checks. For each check you do a binary search over the list of the size at least `N/2` so it is `O(log (N/2))` but given that `log (N/2) = log(N) + constant` it is just `O(log N)`. And you do at least `N/2` such checks. So it is `O(N*log N)`
2. If your list is not sorted, just sorting it to use binary search will take at least `O(N*log N)` so this is the lower bound anyway. And if it is sorted, your algorithm is very inefficient. You can do it in just `O(N)` by comparing each 2 sequential elements in the list (duplicates obviously have to be next to each other in a sorted list).
> 2 votes

# Answer
Your running time is $T(n) = \log n + \log (n-1) + \log (n-1) + \dots + \log 1$. As you've observed, this contains $n$ terms, each of which is $O(\log n)$, so $T(n) = O(n\log n)$.

This sum contains $n/2$ terms that are at least $\log(n/2)$, so we have $$T(n) \> \frac{n}2\log\frac{n}2 = \frac{n}2\log n - \frac{n}2\log 2 = \Omega(n\log n)\\,,$$ and we can conclude that $T(n) = \Theta(n\log n)$.
> 1 votes

---
Tags: algorithms, complexity-theory, algorithm-analysis
---


# Question
Title: Can any problem that runs in exponential time on a deterministic RAM be run in polynomial time on a non-deterministic RAM?
If P is a program that can be run in exponential time on a deterministic RAM. Can P always be run in polynomial time on a non-deterministic RAM?

# Answer
We don't know, but probably not.

You shouldn't equate nondeterministic polynomial computation with deterministic exponential computation. A problem being **NP**-complete does mean that we probably don't know anything better than an exponential deterministic algorithm for it; however, there are a great many exponential deterministic algorithms for which we don't know any nondeterministic polynomial algorithms (e.g., anything that's **EXP**-complete).

There's no particular reason to assume that **EXP**$\\,=\\,$**NP**. In particular, exponential-time algorithms are allowed to use an exponential amount of storage, but any computation path of a polynomial-time computation can only use a polynomial amount.
> 1 votes

# Answer
Consider a program that prints all the subsets of a set. There are an exponential number of those and a non-deterministic RAM doesn't make the process any faster. So I'd say the answer is no.
> 0 votes

---
Tags: complexity-theory
---


# Question
Title: Greedy algorithm to find Minimum Dominating Set in a tree
Is it possible to find minimum dominating set on a tree $G$ using a greedy algorithm?

# Answer
Any negative answer that says that no greedy algorithm will work cannot be proved rigorously since we do not have a definition of an greedy algorithm. So I will just say, no, it is very unlikely that there is a greedy algorithm that will always yield a minimum dominating set if it is given a tree graph as input.

The most common greedy algorithm for dominating set is to repeatedly selecting a vertex with the maximum number of adjacent vertices that are not selected and that are not connected to any vertices selected (not dominated) so far until all vertices are dominated. The following graph illustrates how soon it fails. In the first step we will select vertex 0, the only vertex whose degree is greater than 2. Then we will select vertex 2, 4, 6 for our dominating set. However, the minimal dominating set, {vertex 1, vertex 3, vertex 5} has only three vertices.

Furthermore, any strategy that avoids selecting a vertex that has been dominated might not succeed at all. According to Do Almost All Trees Have No Perfect Dominating Set? by BQ Yue, the average number of perfect dominating sets among all trees of order $n$ is likely approaching zero as $n$ goes to infinity.

A proper strategy to find a minimal dominating set for a tree is dynamic programming. Root the tree at an arbitrary vertex if it is not rooted yet. Now you start computing recursively the minimal dominating set for each subtree with its root included in the set as well as with its root not included in the set.
> 2 votes

---
Tags: algorithms, graphs, trees, greedy-algorithms
---


title: LL(1) and LR(0) Grammars

text:
# Question
Title: LL(1) and LR(0) Grammars
The value in the parenthesis of language expressions signify how many next symbols are needed to make a decision.

For example, without reading a symbol from the input, we cannot decide in LL(1) grammars which rule must be applied for derivation.

In this point, Some thought like that occurs: `we can make a decision without reading a symbol from the input in LR(0) grammars for specific derivation.`

However, I do not think like that, because we always need an input character in LR(0) parsers. We decide to apply shift or reduce operation by regarding next input symbol. In this case, why is it regarded as LR(0) ?

# Answer
The question to be answered in an $LR(k)$ parse is "has the parse reached the end of a production?" (And if so, which production?)

If we are at the end of a production, we choose a reduce action. Otherwise, we shift the next input *whatever it is*.

So it should be clear that there are grammars which can be parsed without any lookahead; they are grammars in which no right-hand side is a prefix of a different right-hand side.
> 2 votes

---
Tags: formal-languages, compilers, parsers
---


title: Turing Reduction vs Karp Reduction

text:
# Question
Title: Turing Reduction vs Karp Reduction
When do you use Turing- and when Karp Reduction? What are the advantages and disadvantages?

I've read about Karp Reduction mainly used in the Context of reducing a Language:

e.g. L1 $≤\_p$ L2

# Answer
The **huge** difference is that a Turing reduction allows you to call the black-box more than once. Suppose you have the $\mathtt{GraphColor?(G, k)}$ decision problem which tells you if the graph $G$ can be colored with $k$ colors. A Karp reduction only allows you to call this problem exactly once. But a Turing reduction allows you to call $\mathtt{GraphColor?(G, k)}$ a polynomial number of times. So if you want to figure out the chromatic number of the graph, call the function with $k=1, k=2, \ldots$ and so on until you get something that works. To make it more efficient, use binary search instead.
> 0 votes

---
Tags: complexity-theory, computability, reductions
---


# Question
Title: Subset of a regular language, for each of whose words there exists an element with the same number of 1s in the other regular language
For regular languages $A,B\subseteq\\{0,1\\}^\*$, is

$$L\_2 = \\{x \in A \mid \exists y \in B : |x|\_1 =|y|\_1 \\}$$

regular, where $|x|\_1$ means the number of appearances of 1 in the word $x$?

i need to demonstrate $L\_2$ automata.

Thought about using the multiplication automata, not so sure.

# Answer
> 1 votes
The idea is as follows:

* We run two automata in parallel: one verifies that the input is in $A$, and the other verifies the other condition.
* The second automaton simulates an automaton for $B$, in the following way. At any point in time it may simulate reading a $0$. It ignores all $0$s in the real input, and forwards all $1$s in the real input.

I'll let you construct an NFA given this description.

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


title: Give a Search Problem in co-NP

text:
# Question
Title: Give a Search Problem in co-NP
Ex.1. Give a Search Problem whose deciding Problem is in co-NP.

Assuming 3SAT is in NP then asking wether a given Boolean formula has a Solution is a search problem in NP right?

Then would asking wether a given Boolean formula has no Solution be in co-NP?

# Answer
Specifically speaking, 3-SAT is an example of **NP-Complete** problem. But your problem is only considered with **NP** problems.

We have the decision problem:

> Is a SAT problem in NP?

Obviously, it is. Because you could always verify a "certificate" in time linear to your input size (values of your literals, that is a sequences of 0s and 1s).

For your question:

> Is a un-SAT problem in co-NP? (complement to SAT problem)

We could find the following definition:

> A decision problem X is a member of **co-NP** if and only if its complement X is in the complexity class NP\[1\].

Therefore, un-SAT is **co-NP** by definition.
> 1 votes

---
Tags: computability, search-problem, co-np
---


# Question
Title: Does this context-free grammar generate a regular language?
Does the following set of production rules produce a regular language or not?

$S \to AB \mid b $
$A \to SB$
$B \to AS \mid a$

I have generated following words with above grammar

1. $b , baa , baaaa , baaaaaa, .....$
2. $bbaba , babab , bababaa , bbbabba ,.....$

But I am not able to create a language using it. Is this grammar just context free or is this regular also ? If yes, how to prove that ?

# Answer
The grammar can be transformed to

$\quad$ $S \to SBB \mid b $
$\quad$ $B \to SBS \mid a$

Let $L\_S$ be the language generated by the rules above (with $S$ as the start symbol). $L\_S$ is context-free by definition.

We will prove it is not regular. The idea comes from the rule, $B\to SBS$.

---

Let $L\_B$ be the language generated by the two rules above with $B$ as the start symbol.

Claim: We have the following inclusions of languages.
$\quad\\{b\\}\cup\\{b^{i+1}ab^ia\mid i\ge0\\}\subseteq L\_S$
$\quad\\{b^iab^i\mid i\ge0\\}\subseteq L\_B$

Proof: Use mathematical induction on $n$, the upper bound for $i$.

* The base case when $n=0$. $S\Rightarrow SBB \Rightarrow^\* baa$ and $B\Rightarrow a$.
* Suppose it is true for $n$. Then $B\Rightarrow SBS\Rightarrow^\* b(b^nab^n)b=b^{n+1}ab^{n+1}$. $S\Rightarrow SBB\Rightarrow^\* b(b^{n+1}ab^{n+1})a=b^{(n+1)+1}ab^{n+1}a$. So it is true for $n+1$ as well.

---

Claim: We have following inclusions of languages. $\quad L\_S\subseteq E\_S :=\\{ba^{2i}\mid i\ge0\\}\cup\\{b^{i+1}ab^ia\mid i\>0\\}\cup\\{\text{words that have at least three } a\text{'s}\\}$ $\quad L\_B\subseteq E\_B:=\\{a\\}\cup\\{\text{words that have at least two } a\text{'s}\\}$

Proof: It is easy to check that $E\_SE\_BE\_B\subseteq E\_S$, $a\in E\_S$, $E\_BE\_SE\_B\subseteq E\_B$ and $b\in E\_B$.

---

The above two claims implies that $L\_S\cap L(b^\*ab^\*a) = \\{b^{i+1}ab^ia\mid i\ge0\\}$, which is not a regular language. Since $L(b^\*ab^\*a)$ is regular, $L\_S$ cannot be regular.

---

**Exercise 1.** Show that the following grammar generates a regular language.
$\quad$ $S \to SAS \mid b $
$\quad$ $A \to ASA \mid a$

**Exercise 2.** Show that the following grammar generates a non-regular language.
$\quad$ $S \to AB \mid b $
$\quad$ $B \to SA $
$\quad$ $A \to BS \mid a$
> 3 votes

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


# Question
Title: is it possible to know if a language is regular if its equivalence classes are finite?
i have a theoretical questions, and was wondering if you could help me with it so i could understand the material better.

1)suppose we have some language L over $\Sigma$, can we know if L is regular if all of it equivalence classes of relation $R\_L$ is finite?

2)and what about L\*? is it finite? i mean the cardinality is infinity(alef), but can it be made into a finite language?

Edit: my question is about Myhill–Nerode relation

i am curious about those and your input would really help me understand more about it

thank you very much!

# Answer
One of the main results of Myhill–Nerode theory is that a language is regular iff its Myhill–Nerode relation has finitely many equivalence classes. You can find a proof in many online resources. In particular, if all equivalence classes of the Myhill–Nerdoe relation of a language are finite, then it must have infinitely many equivalence classes, and so be non-regular.

The language $L^\*$ is finite in two cases: if $L = \emptyset$ or if $L = \\{\epsilon\\}$. In any other case it is infinite.
> 0 votes

---
Tags: automata, regular-languages, finite-automata
---


title: Defining Gap Problems

text:
# Question
Title: Defining Gap Problems
I recently started studying about approximation problems in the complexity class that I'm taking. I feel like some of the definitions in this subject presented in my course and that I came across online are somewhat inaccurate and confusing.

Specifically, the concept of **gap problems** wasn't completely clear to me. It was presented to us that gap problems are a way to formulate decision problems from approximation problems. However, it seems to me that a gap problem isn't precisely a decision problem (or, let's say, a language), but rather a set of decision problems/languages that satisfy two common conditions.

For example, I would think that gap-$IndependentSet\[a,b\]$ could be defined as the set of all languages $L$ such that:

* If $G=(V,E)$ has an independent set of size $\>b$ than necessarily $G\in L$
* If $G=(V,E)$ doesn't have an independent set of size $\>a$ than necessarily $G\notin L$

If such a definition for a gap problem is valid, then I think two more definitions need clarification:

1. A **gap-preserving-reduction** isn't in fact a proper Karp reduction, because it doesn't map a single language to another language. Rather, it maps certain "good inputs" to other "good inputs" and "bad inputs" to other "bad inputs", without having any requirements about the rest of the inputs.
2. A gap problem cannot be an element of a complexity class (such as $NP$), but rather a subset of the class. In that case, saying that **a certain gap problem is $NP$-complete** would actually mean that all languages in the problem are $NP$-complete

Is this a valid way to think about the subject? Am I just confusing myself? Should I stick to the basic intuition and not try to define approximation related concepts in these terms?

# Answer
Gap problems are examples of *promise problems*, which are really the three-valued logic analogs of languages: some elements are in the language, some elements are not, and for the rest, we don't care.

A promise problem is in P if there is a polynomial time algorithm that answers Yes on all Yes instances and No on all No instances; we don't care what it answers on the don't care instances.

A promise problem $L$ is NP-hard if for every NP problem $L'$ there is a polytime reduction $f$ such that if $x \in L'$ then $f(x)$ is a Yes instance of $L$, and if $x \notin L'$ then $f(x)$ is a No instance of $L$.

We can similarly define the analogs of many other properties of languages. Usually this is done in an ad-hoc basis. We definitely think of promise problems as *single* languages rather than as a *class* of languages.
> 2 votes

---
Tags: complexity-theory, approximation
---


# Question
Title: Is the verifier for an $NP$ and its $co-NP$ the same?
I have a hard time to find the goal of having $co-NP$ problems.

* $NP$: *Is there a Hamiltonian path in this graph*?

We need to bring a certificate, and the verifier checks the certificate in polynomial time. However, finding such a path might not be done in polynomial time. It may need searching the entire problem space.

* $co-NP:$ *Isn't there any Hamiltonian path in this graph*?

To say "no", we need to bring a counterexample, and the counterexample (the same certificate) is checked by \[the same\] verifier in polynomial time. However, finding such a counterexample might not be done in polynomial time. It may need searching the entire problem space.

Am I right in the definition of my examples?

It seems we can reduce them to each other:

For example, "*Isn't there any Hamiltonian path in this graph?*" We ask the complement $NP$ problem "Is there any Hamiltonian path in this graph", if it said "Yes", we would say "No" to the $co-NP$ problem and if it said "No", we would say "yes" to the $co-NP$ problem.

So, what is actually the difference? Is it just playing on words? Are there questions for which the NP and its co-NP different to answer?

Anyway, I don't know the goal here, please guide me.

# Answer
I think you might be slightly confusing your definition for co$NP$. To show that a certain graph doesn't contain a Hamiltonian path, you need to show that all paths in it aren't Hamiltonian, and providing a specific path as a "counter example" isn't enough.

In general, $coNP$ isn't defined using a witness the same way $NP$ is, because if it did than it would be the same as $NP$, and for now this is an open problem (we don't know if the two are equal, and they are usually believed to be different). Therefore, it doesn't really make sense to talk about a witness for a $coNP$ problem the same way you talk about a witness for an $NP$ problem.

Specifically, for a certain language in $coNP$ and a witness-based TM $M$ accepting it, $x$ is in the language iff $M$ accepts $(x,v)$ for all witnesses $v$. This is in contrast to a TM for a language in $NP$ that needs to accept only for a single witness.

I would like to add that for me, studying about the Polynomial Hierarchy using its witness-related definitions helped me understand $coNP$ better, but it isn't a necessity.
> 2 votes

# Answer
Taking an $\mathtt{NP}$ problem, formulating its complement, and then looking at their verifiers is pointless, because of this logical equivalence:

$$\neg \exists x. P(x) \equiv \forall x. \neg P(x)$$

So, you are right that this is a boring thing to do.

However, consider a decision version of factorization problem:

> Given integers $N$ and $B$, is there an integer $x$, such $1 \< x \< B$ and $x$ divides $N$?

"Yes" answer is certified by $x$ itself: just perform the division.

"No" answer is certified by the full factorization of $N$: we can check that each factor is prime and their product is $N$ (so this is indeed the factorization) and none of the factors satisfies $1 \< x \< B$.

The conclusion is that factorization is both $\mathtt{NP}$ and $\mathtt{coNP}$. It is considered highly unlikely that $\mathtt{NP} = \mathtt{coNP}$, so it follows that factorization hardly can be $\mathtt{NP}$-complete. And now this is something interesting to say.
> 1 votes

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


# Question
Title: Suitability of high-level languages for embedded systems
Low-level languages have for a long time dominated the field of embedded systems due to their rapidity and flexibility. As high level languages are becoming faster and faster, might the situation get reversed soon? Can high-level languages become frequent in embedded systems in a near (or not so near) future? What would it take for a high-level language to be suitable for embedded systems?

# Answer
What is a high level language? What is an embedded system? Once upon a time C was a high level language and a Raspberry Pi would have changed the outcome of major wars, now almost every microcontroller can be programmed with C and we use Pis that run a full-blown desktop OS to turn servo motors. Let's say a high level language is a language that has strong abstraction mechanisms and an embedded system is a system with very limited memory and a processor with few features.

That alone is not enough to say whether this language is suitable for embedded programming or not. The important part is how the programs in the language can be compiled. Many languages (have to) add something called a *runtime* to the programs. For Haskell for example the runtime added by GHC is about 50k LOC and includes a garbage collector, a scheduler and a bunch of other stuff. That is quite a lot of code for a small chip to handle and might require processor features that aren't present.

Rust is another language that I'd call high-level, but it is possible (in theory at least) to run Rust on many embedded systems. This is because Rust has the possibility to use a much smaller runtime that can be handled by simpler processors and doesn't add as much overhead.

So in summary, the important part is not the features of the language, but how much of those features need support at runtime as opposed to a clever compiler. Garbage collection is typically too difficult for embedded systems, but a surprising amount of abstraction power can be provided without any extra costs at runtime.

Note that in practice you're still limited to C or Assembler in many cases, because you need a compiler that supports your target architecture. Unfortunately it is often the case that the architecture is proprietary and you're limited to using the compiler provided by the manufacturer. That is typically a compiler that supports some flavor of C.
> 4 votes

# Answer
There is metaprogramming exists many years ago, so y**ou can do hardware/software codesign in any programming language** including Python, Prolog, Lisp or anything you want to use.

Take code generation as a base principle, wrap C code writing to files, or wrap LLVM which can cross-compile directly to your system object code. Implement some class tree represents both source code elements (modules, functions, control structures), and your target model components (finite automata, DSP processing elements,..).

You can construct the target software you want to build by interconnecting these like objects and transform model object to source code objects by your metaprograms. And finally, call code generation method in a recursion starting from the top-level object, which will generate files with C source code, or directly call LLVM.

Of cause, it is not an easy or well-described method, but it works at least at the level of parametric code snippets composition. As an example, look on CodeMX init code generator suite provided by STMicro. It is a closed-source vendor-provided system, but you can brew your own analog maybe not GUI but script-driven.

Also look on knowledge representation and reasoning, it will give you an idea of how it can be implemented.
> 0 votes

---
Tags: programming-languages, software-engineering
---


# Question
Title: Counterexample to an Algorithm Complexity Statement
Say I have the following statement:

> If $f(n) = O(s(n))$ and $g(n) = O(r(n))$, then $f(n) - g(n) = \Theta(s(n) - r(n))$.

What would be a counterexample to this?

# Answer
A lot of counterexamples! $f(n) = n, s(n) = n, g(n) = n, r(n) = n^2$. $f(n) - g(n) = 0 = \Theta(n^2 - n) = \Theta(n^2)$.
> 0 votes

---
Tags: algorithm-analysis
---


# Question
Title: Context free grammar where number of a's is larger than number of b's in any prefix of the string
The prefixes of the string `aabab` are `a, aa, aab, aaba, aabab`. If the number of a's should be greater or equal to the number of b's, the grammar would be

`S -> aS | aSbS | e`,

but I need it with strictly more a's than b's in any prefix. I thought of this grammar, but I'm not sure it is correct.

`S -> aS | aSAbA | a
 A -> aA | aAbA | e`

# Answer
In short, take your grammar for the language having a greater or equal number of $a$'s in every prefix, but rename the startsymbol to $P$, i.e. $$ P \to aP \mid aPbP \mid \varepsilon. $$ Then simply note that your condition requires a word to start with an $a$, hence the following will do the job: $$ S \to aP. $$ For if $S \to w$ then $w = auv$ with $|u|\_a \le |u|\_b$, where $|u|\_a$ denotes the number of $a$'s in $u$ (and analog for $|u|\_b$), hence for the prefixes of $w$ the assertion follows. And conversely it works the same.

For your given grammar, this is correct (but I leave my answer as it seems to be simpler). For a proof note that if the produced word contains at least one $b$, then it must have at least two $a$'s before it, and this is what your production $aSAbA$ takes care of, where from $A$ we can just derive words having at most as many $a$'s as $b$'s in every prefix.

Let me give another approach to think about this. Might be a little bit to much theory, but just for education and reasoning. Note that the famous Dyck language is defined as $$ D := \\{ w \in \\{a,b\\}^{\ast} : |u|\_a \le |u|\_b \mbox{for each prefix $u$ of $w$ and } |w|\_a = |w|\_b \\}. $$ It is quite simple to give a grammar for this language, for example $$ S \to \varepsilon \mid SS \mid aSb. $$ Now if we denote by $\mbox{pref}(L)$ the set of prefixes of some language $L$ then your initial language of words having at most as many $a$'s as $b$'s in any prefix is $\mbox{pref}(D)$. And it is quite easy to derive a grammar from it, just make sure every production could be finished any time on the right (for a general argument see this post), hence we could give the grammar $$ S \to \varepsilon \mid SS \mid aSb \mid aS \mid a $$ where the production $S \to aS$ could also be leaved out. Now simply note that words fulfilling your restriction have to start with an $a$ and proceed as above.
> 5 votes

# Answer
the grammar you have written can't produce string "a".

but for a's strictly more than b's in any prefixes the grammar will be

S -\> aA | aaAbA

A -\> aAbA |aA |e

because if there is less/ equal no of a's is in the production before b's then it will produce error.
> 1 votes

# Answer
One of the possible CFG's:

S-\>aPbPaP/aPaPbP/bPaPaP/PaP P-\>aPbPaP/aPaPbP/bPaPaP/PaP/ε

Even though S and P might look similar, P is required as S shouldn't produce ε by itself. This is because an ε string will be invalid, as number of a's should be greater than number of b's.

This grammar takes care of even those strings that begin with b.

examples of accepted strings: a, baaaaaa, aab,aba, aa, etc.
> -1 votes

---
Tags: formal-languages, formal-grammars
---


# Question
Title: Can we detect perfect matchings in P? in NP? in coNP?
This question concerns the classes P and N P . If you are familiar with them, you may skip the definitions and go directly to the question. Let L be a set. We say that L is in P if there is some algorithm which given input x decides if x is in L or not in time bounded by a polynomial in the length of x. For example, the set of all connected graphs is in P , because there is an algorithm which, given a graph graph, can decide if it is connected or not in time roughly proportional to the number of edges of the graph.

The class NP is a superset of class P . It contains those sets that have membership witnesses that can be verified in polynomial time. For example, the set of composite numbers is in NP . To see this take the witness for a composite number to be one of its divisors. Then the verification process consists of performing just one division using two reasonable size numbers. Similarly, the set of those graphs that have a Hamilton cycle, i.e. a cycle containing all the vertices of the graph, is in in NP. To verify that the graph has a Hamilton cycle we just check if the witnessing sequence of vertices indeed a cycle of the graph that passes through all the vertices of the graph. This can be done in time that is polynomial in the size of the graph.

More precisely, if L is a set in P consisting of elements of the form (x, w), then the set M={x:∃w,|w|≤|x|k and (x,w)∈L},

is in N P . Let G = (V, E) be a graph. G is said to have perfect matching if there is a subset M of the edges of G so that

No two edges in M intersect (have a vertex in common); and Every vertex of G has an edge in M. Let MATCH be the set of all graphs that have a perfect matching. Let ~MATCH be the set of graphs that do not have a perfect matching. Let o(G) be the number of components of G that have an odd number of vertices.

Tutte’s Theorem: G∈MATCH if and only if for all subsets S of V, the number of components in G − S (the graph formed by deleting the vertices in S) with an odd number of vertices is at most |S|. That is, G∈MATCH↔∀S⊆Vo(G−S)≤|S|. Which of the following is true?

1. MATCH∈NP and ~MATCH ∉ NP
2. ~MATCH ∈NP and MATCH ∉ NP
3. MATCH ∈ NP and ~MATCH ∈NP
4. MATCH ∉ P and ~MATCH ∉ P
5. None of the above

How to approach such type of questions ?

# Answer
Edmonds' "blossom algorithm" determines membership in MATCH deterministically in time $O(|E|\\,|V|^2)$.

You answer this kind of question by searching for algorithms that solve your problem as efficiently as possible and, if there don't seem to be any, searching for **NP**-completeness results. If you don't find either, then you need to come up with your own algorithm or your own hardness proof.
> 1 votes

---
Tags: p-vs-np
---


title: Simplifying a boolean expression

text:
# Question
Title: Simplifying a boolean expression
I need to prove:

`XY + ~XZ + YZ = XY + ~XZ`

I cannot think how to do this.

I have tried factorising, but I just don't know of any rule that removes one of the terms like above.

I start with the LHS, naturally:

All I can do is get to:

`Y(X+Z) + ~XZ`

# Answer
> 2 votes
OK, answer is as follows, unsure if there's an easier method:

$XY+X'Z+YZ \\ XY+X'Z+YZ(1) \\ XY+X'Z+YZ(X+X') \\ XY+X'Z+XYZ+X'YZ \\ (XY+XYZ)+(X'Z+X'YZ) \\ XY(1+Z)+X'Z(1+Y) \\ XY(1)+X'Z(1) \\ XY+X'Z$

# Answer
> 2 votes
Here is an ugly solution, found with the Karnaugh table and the equation : A = A.B + A./B

XY + /XZ + YZ

= X.Y.Z + X.Y./Z + /X.Y.Z + /X./Y.Z + X.Y.Z + /X.Y.Z

(removing two redundant terms)

= X.Y.Z + X.Y./Z + /X./Y.Z + /X.Y.Z

= XY + /X.Z

# Answer
> 0 votes
Here is a simple argument:

To prove $XY+X'Z+YZ = XY+X'Z$, we only need to show that $$(YZ = 1) \Rightarrow (XY + X'Z = 1)$$ which is obvious, because $$(YZ = 1) \Rightarrow (Y = 1 \land Z = 1) \Rightarrow (XY + X'Z = 1)$$ no matter whether $X = 0$ or $X = 1$.

# Answer
> 0 votes
Note that $XY+X'Z = Y + Z$.

Intuitively, because if X is true, then the second term must be false, which means whether the entire expression is true depends on $Y$. Likewise for $Z$. Then we get:

$Y + Z + YZ$

This statement is true when $X$ is true, or when $Y$ is true, or when both are true. But that is redundant, and we can reduce to:

$Y + Z$

Recall from earlier that we established that $XY+X'Z = Y + Z$. Thus we get:

$XY + X'Z$

---
Tags: logic
---


# Question
Title: Showing that algorithm has STOP property and finding its computational complexity function
The task is to show that given algorithm has STOP property and to find its computational complexity function.

$\alpha:$ $n \ge 0$

```
void fun(int n) {
    a=0;b=n+1;
    while ((a + 1) != b) {
        p = (a + b)/2;
        if (p ∗ p > n)
            b = p;
        else a = p;
    }
}

```

I have already proven its partial correctness as it was also part of the task, however I do have problem with these things that I have mentioned above.

I think it can be easily seen that it is gonna stop as 'a' is getting bigger and bigger, but I don't really know how to notate or show it in more mathematical way.

Thanks for your help.

# Answer
> 1 votes
You have already proven $a \< b$. Let $g$ be the gap between $a$ and $b$, so $b - a$.

1. Show that the algorithm terminates when $g = 1$.
2. Show that when $g \> 1$ we have as postcondition that the new $g' \leq \lceil g/2 \rceil$ in the loop body, and thus $g' \< g$.
3. Show that it's impossible to skip $g = 1$, and thus the algorithm must terminate.

---
Tags: algorithms, time-complexity, correctness-proof
---


# Question
Title: Time complexity dependent on magnitude of input
I'm trying to analyze an algorithm that looks like this:

```
def foo(L):
    for n in L:
        for x in range(n):
            ...

```

What would be its time complexity? First I thought $O(n)$, where $n$ is the number of elements in $L$, but that seems a little optimistic given that numbers can become very large. Then I thought $O(n^2)$ but that seem quite arbitrary too. $O(nm)$ where $m$ is the maximum value in $L$ perhaps?

# Answer
> 1 votes
Your result of seems correct, assuming none of the omitted operations modify the values of the variables `n`, `L` or `x`.

For a fixed value $k$ of `n`, the inner loop (`for x in range(n):`) loops over the set (or list; it is irrelevant for the analysis) $\\{ 0, \dots, k - 1\\}$, which contains $k$ elements. The outer loop (`for n in L:`) simply loops over each element of $L$ for a total of $|L|$ iterations, $|L|$ being the length of $L$. Thus, assuming the omitted operations are executed in $O(1)$ time, we obtain a time complexity of $O(m|L|)$ (as you propounded), where $m$ is the maximum value in $L$.

Incidentally, if you know the average value for the elements of $L$ you could also use the above reasoning to derive the average time complexity as well. (Just plug in the average value for $k$.)

---

As pointed out by @Raphael in the comments, of course, there is plenty of room for improvements if more assumptions are made about the contents of $L$.

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


# Question
Title: Understanding On-policy First Visit Monte Carlo Control algorithm
I am going through the Monte Carlo methods, and it's going fine until now. However, I am actually studying the On-Policy First Visit Monte Carlo control for epsilon soft policies, which allows us to estimate the optimal policy in Reinforcement Learning.

I am having troubles understanding the step in blue of the algorithm. Is the pair St, At NEVER supposed to appears in the given set of states ? In this case, the following pseudo-code will never get realized ? What is the specific case where St, At appears in the set of Action-States ?

Please feel free to ask more details if my question isn't clear enough.

The algorithm is taken from the reinforcement learning book written by R.Sutton and A. Barto.

# Answer
The highlighted line basically says that time $t$ must be the first occurrence of the pair $(S\_t, A\_t)$ in the complete trajectory from $0$ up to and including $t$. This is why there is "first-visit" in the name of the algorithm; it only runs updates for $(S\_t, A\_t)$ pairs if $t$ is the first occurrence (first "visit") of a particular state-action pair in a trajectory.

This condition:

* Is always trivially satisfied for the pair $(S\_0, A\_0)$ (it's the beginning of the trajectory, so we can't possible have observed that state-action pair before)
* Is satisfied at time $t = 1$ if and only if $(S\_1, A\_1) \neq (S\_0, A\_0)$ (so at least one of the state or the action must be different from the preceding ones)
* Is satisfied at time $t = 2$ if and only if $(S\_2, A\_2) \neq (S\_1, A\_1)$ AND $(S\_2, A\_2) \neq (S\_0, A\_0)$.
* etc.
> 1 votes

---
Tags: algorithms, reinforcement-learning, monte-carlo
---


# Question
Title: Applications of divide-and-conquer outside of merge sort and quicksort
What are other algorithms that use the divide-and-conquer paradigm aside from merge sort and quicksort?

# Answer
There are many algorithms that uses the divide-and-conquer paradigm besides merge sort and quicksort.

"There is no accepted formal definition of the divide and conquer paradigm, and so we must regard this paradigm as an informal concept.", reads an answer by Yuval Filmus. I will use Wikipedia entry on divide-and-conquer as the reference to interpret its meaning.

That Wikipedia entry mentions quite a few examples. Here are some of them.

As Raphael commented, there are probably hundreds of examples in the literature. Here are a few simple or notable ones.

We can also relate many structural decomposition techniques to divide and conquer. Whenever we are using the recursive nature of a tree graph, it could be considered an application of divide and conquer. Whenever we are using the Jordan blocks of a matrix, it could be considered likewise. When you reduce a problem about a graph to each of its connected component, it could be considered likewise. In this sense, divide-and-conquer appears even more pervasive.

There are also many examples that are better classified as decrease and conquer. Some notables of them are binary search, exponentiation by squaring, Johnson–Trotter algorithm that lists all permutations. Whether we or you would like to consider them as divide-and-conquer (proper) is up to our or your preferences. If you do, it may "help you conceptualize the algorithms that you learn in the course. If you don't find this helpful, just ignore it", says Yuval.

---

If you have plenty of time to kill, you may enjoy the following tedious exercise.

Exercise. Check which algorithms in the list of algorithms by Wikipedia use divide-and-conquer.
> 3 votes

---
Tags: algorithms, reference-request, divide-and-conquer
---


# Question
Title: How does a co-NP problem differ from an NP (its complement) one?
I have quite a hard time understanding co-NP problems.

If we can reduce every problem to decision problem. NP problems should accept YES instances -\> instances where the answer is yes. So for example for Traveling Salesman problem, we would ask "Is there a path that visits every city, and is shorter than N" ?

For co-NP problem, they should accept NO instance -\> answer to them is NO. But given this, how would we formulate co-NP problem to Traveling Salesman problem I mentioned earlier? if we formulate it "Isn't there a path that visits every city and is shorter than N"? If there wasn't the path, the answer would be YES -\> so it would be YES problem, if the answer was NO, we would have to try the path which would be same as YES problem.

So what is the difference? Was my co-NP decision problem to said TSP correct?

I have read wiki and tried to find some sources but nothing helped...

Thanks for help!

# Answer
> 1 votes
A **co-NP** problem differs from its complementary **NP** problem *exactly* by being its complement! That's the whole story.

> NP problems should accept YES instances -\> instances where the answer is yes.

I think you've confused yourself. *Every* problem, of any complexity, is a division of all possible instances into "yes" instances and "no" instances. For TSP, the "yes" instances are the maps where the salesperson *can* visit all the cities within the distance requirement and for co-TSP, the "yes" instances are the maps where the salesperson *can't* (i.e., the "no" instances of TSP).

What differs between complexity classes is the amount of resources and model of computation that are required to tell the difference between a "yes" intance and a "no" instance. For **NP**, we use a nondeterministic Turing machine running for a polynomial number of steps and say that the machine accepts if at least one computation path accepts, and rejects otherwise. For **co-NP**, we do the opposite: the machine rejects if at least one computation path rejects, and accepts otherwise.

# Answer
> 0 votes
A YES/NO problem is in NP if for every instance where the answer is "YES", there is a proof that can be verified in polynomial power.

A YES/NO problem is in co-NP if for every instance where the answer is "NO", there is a proof that can be verified in polynomial power.

Of course if you take a problem in NP and just switch the answer from "YES" to "NO" and vice versa, you get a problem in co-NP, but that is rather boring. For example "is a number N composite" is in NP (just start with a non-trivial factor to show it is composite), and the opposite "is a number N prime or equal to 1" is in co-NP (just start with a non trivial factor to show that it is NOT prime or equal to 1).

What's much more interesting is problems that are both in NP and co-NP. "Is a number N composite" is indeed in co-NP but that requires some deep mathematics - whenever N is prime, there is a proof that it is prime which can be checked in polynomial time. Not easy at all.

For the Travelling Salesman problem which is easy to show in NP, nobody has the slightest clue how to prove that it would be in co-NP, and most likely it is false.

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


# Question
Title: Why do AlphaGo and AlphaGo Zero include board history in the input features
Both AlphaGo and AlphaGo Zero include prior board states as input features (the "Turns Since" planes for AlphaGo, and the repeated 8-step history planes for AlphaGo Zero).

What is the purpose of including this history information in the input to the neural networks?

If we ignore the ko rule, the best move at a position should not depend on the history of moves leading up to that position. If we don't ignore ko, a single step of board history should be sufficient in the vast majority of games, so including 8 steps of history seems excessive (and possibly even harmful, since if the same position were reached by two different paths, the learned response might not be shared between those two paths).

This doesn't seem to be discussed in either of the papers, or in any of the media reporting that I have seen.

# Answer
> "This doesn't seem to be discussed in either of the papers, "

Yes, it is discussed in at least one of the papers.

Here is an excerpt taken from Mastering the Game of Go without Human Knowledge - DeepMind by David Silver, Julian Schrittwieser, Karen Simonyan, et al. The emphasis on "repetitions are forbidden" is added by me.

> History features $X\_t, Y\_t$ are necessary because Go is not fully observable solely from the current stones, as **repetitions are forbidden**; similarly, the colour feature $C$ is necessary because the komi is not observable.

The usual case of forbidden repetitions comes with a ko, as mentioned in the question and the other answer. There are other repetitions, such as eternal life and triple ko.
> 2 votes

# Answer
The primary reason for including a history of states is likely indeed the ko rule. Even if having a long history will often be redundant, it's unlikely to hurt either (except that it might take some computation time... but that doesn't appear to be a major concern throughout the entirety of the papers).

I imagine that having a history of states can also help the Neural Network to more easily "focus" on important areas of the board during training (maybe only in the beginning of the training process, maybe for a longer time). You're right that, from a game-theoretic point of view, the current game state should be sufficient (ignoring rare cases). However, the learned components of AlphaGo Zero are not optimal in a game-theoretic sense early on in training (and likely still aren't after training either). **Architectural choices in the Neural Network that may be redundant in a game-theoretic sense may still be beneficial for more rapid learning**.

For example, in early stages of learning when learned components are still performing poorly, I imagine a useful heuristic may be to pay more "attention" to areas of the board where moves have recently been made; these are more likely to be important areas of the board than some different area of the board where nothing is going on (especially for an amateur-level component in the beginning of a learning process). Such areas of the board can easily be identified by subtracting game states in the recent history from each other.

I would not be surprised if this indeed ends up happening to some extent during the learning process. Stochastic Gradient Descent tends to, intuitively, take the path of "least resistance" and greedily optimizes parameters wherever it happens to notice some correlation between inputs and outputs. Of course this whole argument is rather handwavy, and it also may not at all be happening... I suppose the main point is what I put in boldface above. Neural Network-based components are not optimal in a game-theoretic sense, and they're also trained using algorithms (SGD-style) that may take suboptimal paths to global minima or not even find a global minimum at all. Modifications that would not be necessary for an "optimal" solution may still help to more easily or more quickly find good solutions.

---

David Silver, one of the first authors on both of the AlphaGo papers, describes a similar hypothesis to what I described as "focus" (more commonly described as "attention") here (emphasis mine):

> Actually, the representation would probably work well with other choices than 8 planes! But we use a stacked history of observations for three reasons: 1. it is consistent with common input representations in other domains (e.g. Atari), 2. we need some history to represent ko, **3. it is useful to have some history to have an idea of where the opponent played recently - these can act as a kind of attention mechanism (i.e. focus on where my opponent thinks is important)**.
> 2 votes

---
Tags: machine-learning, board-games, features
---


title: Confusion About Min-Cut Probabilities

text:
# Question
Title: Confusion About Min-Cut Probabilities
* Currently going through a video on Counting Minimum Cuts by Tim Roughgarden.
* $(A\_{i},B\_{i}) = \big((A\_{1},B\_{1}), ..., (A\_{t},B\_{t})\big) \forall i \in \Bbb{R}$
* $P\big((A\_{i},B\_{i})\big) \geq \frac{1}{\begin{pmatrix} n \\ 2 \end{pmatrix}} = p$, which I interpret as the lower bound on the probability of having at least one minimal cut.
* In the problem set that follows two answers A and B are highlighted as being correct. **I understand why A is correct; but am puzzled why B is also marked as correct.**
* A: For every graph $G$ with $n$ nodes and every min cut $(A,B)$ (I am assuming same thing as $(A\_{i},B\_{i})$) $P\big((A,B)\big) \geq p$.
* B There exists a graph $G$ with $n$ nodes and a min cut $(A,B)$ (again assuming same thing as $(A\_{i},B\_{i})$) of $G$ such that $P\big((A,B)\big) \leq p$.

# Answer
> 1 votes
I don't understand what you mean by "$(A\_i,B\_i) = ((A\_1,B\_1),\ldots,(A\_t,B\_t))$", an obviously false statement. Perhaps you meant $(A\_i,B\_i) \in \\{(A\_1,B\_1),\ldots,(A\_t,B\_t)\\}$?

I don't quite understand your interpretation of the statement $P((A\_i,B\_i)) \geq p := 1/\binom{n}{2}$. Here is the correct interpretation:

> For any minimum cut $C$, the probability that Karger's algorithm outputs $C$ is at least $p := 1/\binom{n}{2}$.

This is exactly what A states.

For B, you need to give an example of a graph which satisfies $P(C) \leq 1/\binom{n}{2}$ for all cuts $C$. One such example is a cycle, an example you were probably shown in class.

---
Tags: algorithms, probability-theory
---


title: What exactly is transmission time?

text:
# Question
Title: What exactly is transmission time?
Seems very trivial but I'm confused which one of these correctly define transmission time.

* Time taken by a message to reach receiver.
* Time taken to push message on the link by the sender.

Which one is correct one?

# Answer
* Time taken by a message to reach receiver : **Propagation delay or time**
* Time taken to push message on the link by the sender : **Transmission time**

Transmission time is the time from the first bit until the last bit of a message has left the transmitting node. Or, in simple word it's the amount of time required for the **router to push out** the packet.

```
Packet transmission time = Packet size / Bit rate

```

**Reference :**
> 2 votes

---
Tags: computer-networks
---


# Question
Title: Advantages of using prime number as interval during a shell sort?
As I understand it's best practice to always use a prime number during a shell sort for its interval. Why is this the case?

# Answer
It is still an open question what the best gap sequence for shell sort would be; and what the performance of shell sort would be with an optimal sequence.

The "holy grail" for comparison based sorts is O(lg(n!)) ~= n\*lg(n) -n performance.
No one has ever found a gap sequence for shell sort that achieves that.

Here's what we do know-
1= the last gap must always be 1 (insertion sort)
2= there should be no more than lg(n) -1 gaps
(thus the lg(n) -1 gap is always going to be 1)
3= the gaps should at least be relatively prime to each other.
4= the gaps should be between a factor of 2 or 3 of each other
5= the gaps can not be expressed by a closed form math formula if you want worst case performance better than O(n\*lg^2(n)) or O(n^(3/2))

Thus using just primes closest to (n/2)^i for the first lg(n)-2 passes can be a very good choice, but
a= we as of yet can not prove such a gap sequence would be optimal, and
b= figuring out what the gap sequence is for any given size of data set is non trivial if all of our gaps are primes.
> 2 votes

---
Tags: sorting
---


title: Does a Vertex Cover exist?

text:
# Question
Title: Does a Vertex Cover exist?
This should be a simple question, but I am a little bit confused.

A proof on page 556 of Algorithm Design says:

"Let $e=(u, v)$ be any edge of $G$. The graph $G$ has a vertex cover of size at most $k$ if and only if at least one of the graphs $G-\\{u\\}$ and $G-\\{v\\}$ has a vertex cover of size at most $k-1$."

But when I try the following example where the black ball shows a vertex cover, it seems to be faulty statement. Because $k$ remains as $k$ (not $k-1$) even after deletion of vertex $u$. Moreover, if I delete the vertex $v$, there would be no vertex cover left.

What is wrong about my deduction and example?

# Answer
> 2 votes
If you delete the vertex $v$, then there are no edges left at all, and so there is a vertex cover of size $0 \leq k-1$.

Why is the statement true in the first place? Suppose that $G$ has a vertex cover $C$ of size $k$. Since $(u,v)$ is an edge, $C$ must contain at least one of $u,v$, say $v$. I claim that $C \setminus v$ is a vertex cover of $G \setminus v$, from which the statement immediately follows. Indeed, let $(a,b)$ be any edge of $G \setminus v$. Then $(a,b) \in G$, and so $C$ contains one of $a,b$, say $a$. By construction, $a \neq v$, and so $a \in C \setminus v$.

---
Tags: graphs
---


# Question
Title: Is this concatenation of two FA done right?
$r\_3=r\_1r\_2=(a^\*b)^\*(a+ba)^\*bb(a+b)^\*$ comes out to be $r\_3=r\_2=(a+ba)^\*bb(a+b)^\*$ when i generate the resultant FA and its regex after concatenation i.e. it doesn't include $r\_1$
**Details:**
Consider these two FA
$FA\_1$
$FA\_2$
if $r\_1,r\_2$ and $r\_3$ are regex for $FA\_1,FA\_2$ and $FA\_3$ respectively where
$r\_1=(a^\*b)^\*$
$r\_2=(a+ba)^\*bb(a+b)^\*$
then, mathematically, $r\_3=r\_1r\_2=(a^\*b)^\*(a+ba)^\*bb(a+b)^\*$
But $r\_3$ turns out different when I **actually** concatenate $FA\_1$ and $FA\_2$ and use the new transition table (given below) for $FA\_3$ to generate its regex ($r\_3$) and the $TG\_3$ (given below) and then simplify, $r\_3$ becomes $(a+ba)^\*bb(a+b)^\*$ which is the same as $r\_2$ (i.e. $r\_1$ not prefixed). and since $r\_3=r\_1r\_2=(a^\*b)^\*(a+ba)^\*bb(a+b)^\*$ can't be simplified into $r\_2=(a+ba)^\*bb(a+b)^\*$
I am convinced that the problem is in the concatenation/transition table, especially with the circular references to $x\_1$ and $y\_1$, which i don't completely get. That also would mean $TG\_3$ iswrong.

The Transition Table:

$TG\_3$

Now, it'd be very tedious to explain how i created the transition table, it's easier to figure out by looking at it. but key point **i can't quite grasp the "$x\_1$ and $y\_1$ being connected" part**
Sidenotes:
\- This is the only way to concatenating two FA that i know of. I am on a distant learning platform and it's quite low quality material, so links to proper methods are appreciated. \- If you use another method, please keep in mind that the transition table, regex and the TG and all required \- The TG looks like an FA to me (barely know the difference) but the site i used to generate it says it's a TG. what's the difference?

# Answer
You can think of the concatenation of the languages defined by the two automata as the language of the automaton that can be obtained by connecting all final states of the first (in the example, just $x\_1$) with the starting state of the second ($y\_1$), by an empty transition, and then making them non-final.

A transition table can then be used to convert the NFA just generated into a DFA, which is what you did.

In this case, $r\_1r\_2$ is indeed equivalent to $r\_2$, and this is completely normal. A transition graph represents a transition function, which is part of an automaton. If you minimize $TG\_3$, what you get is exactly $FA\_2$, which confirms the equivalence.
> 2 votes

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