# Question
Title: Analysis of komi values for increasing Go board sizes and agents strength
Komi is the additional number of points given to the non-starting player in the game of Go.

For 19x19 board, currently it is 6.5 under Japanese rules, 7.5 points under Chinese rules. In the past it was lower, even 2.5 points.

A question arises: what value it should be so that it is a fair game? Draws allowed.

(This handles the unlikely to me case, in which Go is already fair, without komi. Then one would just discover that komi should be 0. So, I'm not assuming that Go without komi is unfair)

The following idea came to my mind:

Let's take e.g. 5x5 board and an agent A. Let it self-play many games, plot the average of points won by the starting player in the end of the game, stop simulations when the value converges.

Do the same for 6x6, 7x7 board and so on up to 19x19 (or further).

So, for a given agent A, we will have a list of mean scores for a starting player on increasing board sizes, e.g. \[25, 14.2, 9.6, ...\], meaning that on a 5x5 board, on average, the first player wins with 25 points. On 6x6 board, on average, with 14.2 points, and so on. These could be the komi values.

Now, maybe the values in the list will be always decreasing. Maybe they converge to some value as the board size grows. Is it already described somewhere?

The values will probably depend on the agent A. Maybe one could also find a relationship between the strength of the agent A and the values in the list. E.g. maybe the stronger the agent, the values decrease slower.

So, one could start with a weak agent. See what values in the list it produces. Then, improve agent A (using e.g. some reinforcement learning algorithm or giving more time to the search) and produce another list of mean values. And so on.

Maybe the variance of results (or some other function) could be a nice measure of how far the current agent is from the optimal one (because the optimal one vs optimal one will always result in exactly one outcome, variance 0). So e.g. maybe agent who has scores vs himself in \[-2; 2\] is closer to the optimal one than the agent with scores in \[-20; 20\].

Say for the weakest agent A the list would be \[25, 14.2, 9.6, ..., 6.6\] and for the strongest agent A (ideally this agent would play optimally) \[25, 18, 14, ... 8.2\]. Now one knows that the sensible komi for 19x19 is in the range of 6.6 and 8.2.

My questions are:

1) Have you seen something similar done before? I would be happy to read. I've read Solving Go for Rectangular Boards, which solves Go up to 5x5. If such analysis wasn't described, I could do one out of curiosity.

2) Do you see some problems, refinements or other interesting things to check?

# Answer
From my experience of solving some other games, usually there is a huge difference between optimal player and an average player or even state-of-the-art engine. I bet the results for any other player then optimal will diverge from the results of optimal play. For example see what happened with some famous chess positions when endgame tables where developed (see Tablebases, Fermat, Knights and Knightmares \- you might need access to ICGA Journal). Optimal solutions frequently destroy any intuition about a game. I expect that even AlphaGo Zero approach would be not enough even for small boards like 7x7 to approximate the optimal komi value.
> 3 votes

---
Tags: artificial-intelligence, game-theory, board-games
---


title: Complexity Classes UP and US

text:
# Question
Title: Complexity Classes UP and US
According to complexity zoo: Class **UP** (Unambiguous Polynomial-Time) is defined as: The class of decision problems solvable by an NP machine such that

1. If the answer is “yes,” exactly one computation path accepts.
2. If the answer is “no,” all computation paths reject.

Class **US** (Unique Polynomial-Time) is defined as: The class of decision problems solvable by an NP machine such that the answer is “yes” if and only if exactly one computation path accepts.

*In contrast to UP, a US machine can legally have more than one accepting path that just means that the corresponding input is not in the language.*

My question is:

* Is there an example of a problem which is known to be in one class, but not in other? We know that **UP** $\cup$ **coNP** $\subseteq$ **US**.
* It is known that class **US** is a subset of $P^{NP}$. A well-known example is **USAT** which is known to be **US**-hard (and **coNP** hard) but not known to be coNP. **US** is not known to be equal to **coNP**. Also, I know that **coNP** $\subseteq$ **US**. Can one give an intuitive reason for this?
* How can a machine have more than one accepting path, but that input is not in the language? (Maybe I am missing something trivial here)

# Answer
Let me start with your third question. It seems that you don't quite understand the definitions of $\mathsf{UP}$ and $\mathsf{US}$, so let me repeat them here.

> **Definition of $\mathsf{UP}$.** ***Property U.*** A non-deterministic Turing machine has *property U* if every input has at most one accepting path. The language accepted by such a machine consists of all inputs which do have an accepting path.
>
> **The class $\mathsf{UP}$** consists of all languages accepted by non-deterministic Turing machines having property U and running in polynomial time.
>
> **Definition of $\mathsf{US}$.** ***U-acceptance.*** The language accepted by a non-deterministic Turing machine consists of all inputs which have an accepting path. In contrast, the language *U-accepted* by a non-deterministic Turing machine consists of all inputs having exactly one accepting path. Any input having either no accepting path or at least two accepting path does not belong to the language U-accepted by the machine.
>
> **The class $\mathsf{US}$** consists of all languages U-accepted by non-deterministic Turing machines running in polynomial time.

As for your second question, to show that $\mathsf{coNP} \subseteq \mathsf{US}$ it suffices to reduces $\mathsf{coSAT}$ to $\mathsf{US}$. Given a SAT instance $\phi = C\_1 \land \cdots \land C\_m$, let $$\psi = (v \lor C\_1) \land \cdots \land (v \lor C\_m) \land (\lnot v \lor x\_1) \land \cdots \land (\lnot v \lor x\_n),$$ where $v$ is a new variable and $x\_1,\ldots,x\_n$ are the original variables. Then $\psi$ has a unique satisfying assignment (in which all variables are true) iff $\phi$ is unsatisfiable.

As for your first question, if $\mathsf{P} = \mathsf{NP}$ then $\mathsf{P} = \mathsf{UP} = \mathsf{US}$, so no unconditional separation is currently known. If you're interested in conditional separations, I suggest asking a new question focused just on that issue.
> 5 votes

---
Tags: complexity-theory, time-complexity, complexity-classes
---


# Question
Title: Can we convert an NFA to a regular expression of polynomial length?
Can we convert an NFA having $n$ states to a regular expression of length $\mathrm{poly}(n)$?

In contrast, it is well known that a regular expression of length $n$ can be easily converted to an $\mathcal{O}(n)$-state NFA.

# Answer
> 11 votes
Using the concept of star height, Gruber and Holzer showed in Finite Automata, Digraph Connectivity, and Regular Expression Size that there exists a constant $C\>1$ and a sequence of languages $L\_n$ over $\\{0,1\\}$ which can be accepted by DFAs having $n$ states, but for which every regular expression has length at least $C^n$.

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


# Question
Title: How consistent heuristics guarantees A* optimality without adding same node to the frontier twice or more
Taken from Artificial Intelligence A Modern Approach :

Notice how a node doesn't gets added to the frontier twice in Graph-Search, And then take a look at this :

Now obviously this is not true as in the following example :

Bucharest will be added to the frontier first with path sibiu-\>fagaras-\>bucharest, while the second path which is more optimal will be omitted.

Am i missing something or is just a false claim?

# Answer
A\* isn't based on the `GRAPH-SEARCH` algorithm but on the `UNIFORM-COST-SEARCH` one:

```
function UNIFORM-COST-SEARCH(problem) returns a solution or failure
   node ← a node with STATE = problem.INITIAL-STATE, PATH-COST = 0
   frontier ← a priority queue ordered by PATH-COST,
              with node as the only element
   explored ← an empty set

   loop do
     if EMPTY?(frontier) then return failure

     node ← POP(frontier)  /* chooses the lowest-cost node in frontier */
     if problem.GOAL-TEST(node.STATE) then return SOLUTION(node)

     add node.STATE to explored
     for each action in problem.ACTIONS(node.STATE) do
         child ← CHILD-NODE(problem, node, action)
         if child.STATE is not in explored or frontier then
             frontier ← insert(child, frontier)
         else if child.STATE is in frontier with higher PATH-COST then
             replace that frontier node with child

```

Uniform cost search algorithm is identical to the general graph search algorithm (in your question) except:

* for the use of a priority queue and
* the addition of en extra check in case a shorter path to a frontier state is discovered.

A\* is identical to UNIFORM-COST-SEARCH except that uses $g + h$ instead of $g$.

So assuming the following distances (straight-line distance to Bucharest) for the `h` heuristic function:

```
Sibiu          253     Fagaras 176
Rimnicu Vilcea 193     Pitesti 100
Bucharest        0

```

the second path will NOT be omitted. Stages in an A\* search for Bucharest are (numbers show $f = g + h$):

```
(a) Sibiu 0 + 253 = 253
(b) Fagaras = 99 + 176 = 275, Rimnicu Vilcea = 80 + 193 = 273
(c) Pitesti = 177 + 100 = 277
(d) Bucharest (via Fagaras) = 310 + 0 = 310

```

A\* search keeps going, choosing Pitesti for expansion:

```
(e) Bucharest (via Pitesti) = 278 + 0 = 278

```
> 2 votes

---
Tags: algorithms, graphs, artificial-intelligence, search-algorithms
---


# Question
Title: Find biggest K, such that any subset of size less than K is not affecting the array
Let's say we have given array $A = \\{a\_1, a\_2, a\_3,\dots,a\_n\\}$ of size $n$, and integer $L$, we want to find biggest integer $K$, such that the array without any subset of size $x, x\leq K$ will have sum greater or equal to $L$.

**Example**

$A = \\{1, 2,3\\}, L = 2$, in this case $K = 1$, because any subset of size $1$ will not affect the array, or the array sum will be greater or equal to $L$. Note that $K$ cannot be $2$ because the array without the subset $\\{2, 3\\}$ has sum $1$ which is less than $L$.

**What I think for the solution**

I started thinking about solution with dynamic programming, I'm thinking in the following way, if we have $K$ for first $x$ elements and for sum $y$, we could come with relation to solve for $x+1$ elements and for $y+1$ for value of $L$, but I cannot come with the relation.

# Answer
> 1 votes
The worst case will always be, as in your example, a subset that contains the biggest elements of the set. So I would

1. order the set
2. remove the biggest element and check if the condition still holds
3. iterate 2.

The number of iterations will give you your K.

Runtime $O(N\cdot logN)$ or better for the sorting, $O(N)$ for computing the sum of the array, at most $O(N)$ iterations.

---
Tags: dynamic-programming, arrays, subset-sum
---


# Question
Title: Is this book's definition of phrase correct?
I am fairly confident that my textbook (Concepts of Programming Languages 11th edition, international edition, Robert Sebesta) has an error in its definition of what a phrase is in the section on bottom-up parsers. After an infuriating conversation with the professor using that textbook in which I was told that the book's definition was correct, but was given no reason why or why my reasoning was incorrect, I still think it has an error. I haven't been able to find any information about errata in the book online (not the main point of the question, but I'd like to find that also).

Here is the book's definition:

$\beta$ is a phrase of the right sentential form $\gamma$ if and only if $S \Rightarrow^{\*}\gamma = \alpha\_1A\alpha\_2\Rightarrow^{+}\alpha\_1\beta\alpha\_2$.

Here is what I think the definition should be:

$\beta$ is a phrase of the right sentential form $\gamma$ if and only if $S \Rightarrow^{\*}\alpha\_1A\alpha\_2\Rightarrow^{+}\alpha\_1\beta\alpha\_2 = \gamma$

Here is my reasoning: Definitions are mostly arbitrary, so I can't really prove that it's "wrong" without comparing it with a bunch of other books out there (I just have the one, so if those of you with more could check that for me, that'd be great. I can't seem to find any definitions online). But I can prove that it's not consistent with the rest of the book.

The book states that simple phrases are a subset of phrases, that the handle of any rightmost sentential form is its leftmost simple phrase, and that in this example grammar

$\begin{align} E &\to E + T \mid T\\ T &\to T * F \mid F\\ F &\to (E) \mid id \end{align} $

the handle of the sentence "id + id * id" is the first id. Observe that according to the book's definition of phrase, a sentential form consisting entirely of terminals can have no phrases, because the sentential form is never of the form $\alpha\_1{}A\alpha\_2$. This means that there are also no simple phrases of sentential forms consisting entirely of terminals. This means that there are also no handles of sentential forms consisting entirely of terminals. This means that there are no handles in "id + id * id", despite them saying there are. So the definition isn't consistent with what else they say. Based on what I've read elsewhere and heard in class, the definition seems wrong, not the other parts.

Is my reasoning sound? Is the definition of phrase correct / what is the "correct" definition of phrase?

(apologies if I left out anything essential, I lost the first draft when I got to the captcha requirement and filled it out with spyblock enabled)

# Answer
> 1 votes
To be a phrase is to be reducible to a single non-terminal. What you call a definition of phrase is actually the definition of what it is to be a phrase *of a sentential form*.

$\beta$ is a phrase of $\alpha\_{1}A\alpha\_{2}$, because it will be reduced to $A$. There are (obviously) phrases **in** sentential forms consisting entirely of terminals, i.e., sequences of symbols that will be reduced to a single non-terminal. They are not phrases **of that** sentential form, though.

A handle is the simple phrase of the sentential form that will be the *result* of the reduction to be made immediately, at some point. $\beta$ exists as a phrase, because it will be reduced to $A$. A bottom-up parser will usually reduce first its leftmost simple phrase, which will then be the handle of the resulting sentential form.

Definitions are not arbitrary, they serve a purpose.

---
Tags: terminology, context-free, formal-grammars
---


# Question
Title: Grammar types constraint after adding a couple of types (and a statement involving them) to a "typeless" language
*Foreword* : by "typeless programming language", I naively mean "language in which you don't write statements like `type x (=) ...` to declare(define) `x`". Maybe there is an internal typing deduced from what is in `...` but I suppose that this is not the case, as it is not the case in the example interesting me. (If "typeless programming language" already means something, forbid me, but this is not the point.)

Consider the grammar of a "typeless" programming language, python (3.6.3) for instance :

https://docs.python.org/3/reference/grammar.html

I rather used its description here :

https://github.com/erezsh/plyplus/blob/master/plyplus/grammars/python.g

Then I lightened the grammar *a lot* and modified the resulting subgrammar by adding new features, but for the sake of simplicity, one can assume that I add features to the complete python grammar, not to a subgrammar of it.

Here are my modifications :

1) I added a date "type" (I put type in `""` because there's no type in python)

```
date: US_DATE;

```

where :

```
US_DATE: '!(?:(?:(?:(?:(?:[13579][26]|[2468][048])00)|(?:[0-9]{2}(?:(?:[13579][26])|(?:[2468][048]|0[48]))))(?:(?:(?:09|04|06|11)(?:0[1-9]|1[0-9]|2[0-9]|30))|(?:(?:01|03|05|07|08|10|12)(?:0[1-9]|1[0-9]|2[0-9]|3[01]))|(?:02(?:0[1-9]|1[0-9]|2[0-9]))))|(?:[0-9]{4}(?:(?:(?:09|04|06|11)(?:0[1-9]|1[0-9]|2[0-9]|30))|(?:(?:01|03|05|07|08|10|12)(?:0[1-9]|1[0-9]|2[0-9]|3[01]))|(?:02(?:[01][0-9]|2[0-8])))))';

```

(thx to https://stackoverflow.com/a/16088645/1581875)

and I propagated `date` to `atom`.

Then `d = !20171116` produce the following syntax tree :

2) I also added what I call an `underlying`, and this time it's a real type. Namely, I added a

```
UNDERLYING: 'underlying';

```

in the `%unless` part of `NAME` definition, and I introduced an underlying statement :

```
underlying_stmt : UNDERLYING name (COMMA name)*;

```

that I of course propagated to `small_stmt`.

Now one can write :

```
underlying z

```

which produces the following syntax tree :

3) Here comes the tricky (at least for me) part : after what preceeds, I introduced a new use of the `@` symbol, namely a "stamp statement", `stamp_stmt`, as follows :

```
stamp_stmt: name AT (name | date);

```

(that I propagated of course to `small_stmt`)

Namely, I can write

```
z @ d #or
z @ !20171116

```

and this will produce the following syntax tree :

In fact, as I defined the `stamp_stmt`, I can write `name @ date` for any `name` (and `date`).

I cannot write `2 @ !20171116` for instance : this is already a constraint. **I would like to be able, *within the grammar*, to also add the following constraint : `name @ date` could be written only for a `name` of an `underlying`.**

**How could I achieve this ?** I mean, I could still introduce a kind of light "typing" in `name` by refining it by saying that `date` (resp. `underlying`) has `datename` (resp. `underlyingname`) and try to use it to achieve the wanted constraint, but I could also say that `d = !20170823` is not an assignement statement (`assign_stmt`) and introduce a "date assignement statement", same for `underlying`.

Is it anyway a good idea to want to put such a type constraint already in the grammar or not ? (I am really not an expert in languages designing etc ... I am doing all of this because I need a small programming language with the aforementionned features and because around me, no one can help.)

*Remark* : I am doing all of this under windows with plyplus in python and producing syntax trees figures using graphwiz.

# Answer
> 1 votes
There is no way to express that constraint with a context-free grammar. (It is, almost by definition, context-sensitive since the validity of `z @ …` depends on the presence of `underlying z`.)

So you are left with two choices:

1. Perform the validity check as a semantic action.
2. Modify the lexical scanner's categorization of tokens on the fly, by recategorizing `z` after `underlying z` is seen.

Option 2 is usually called the "lexical feedback hack" and that is precisely what it is. Sometimes it cannot be conveniently avoided, but this is not one of them.

---
Tags: formal-languages, formal-grammars, programming-languages, type-theory, python
---


# Question
Title: Is there an equivalence between "does this program halt" and "is this sentence provable"?
It seems, intuitively, that determining if an program halts when running on a TM should be as difficult as determining if a sentence is provable within a finite set of logical rules. Furthermore, there are as many sentences as there are program and there are as many finite set of logic rules are there are TM (there are countably infinitely many of each).

Can we interpret a universal Turing machine executing programs as equivalent, in some way, as finding the proof for all theorems for all finite set of logic rules. If a program halts on a TM then it means that the program is a theorem of some logical system, and vice-versa.

If so, how? If not, why not?

# Answer
> 1 votes
If a Turing machine halts on a given input, then you can prove this in any reasonable propositional proof system. The idea is to list the halting sequence of configurations of the Turing machine, and prove, one by one, that these are the configurations encountered by the Turing machine when run on the given input.

In the other direction, if a sentence is provable in a reasonable proof system, then the Turing machine which goes over all proofs in the system and checks whether they prove the sentence, will halt, and its halting implies that the sentence is indeed provable in the proof system.

What this shows is that Turing machines with an oracle for the halting problem have the same power as Turing machines with a provability oracle for any reasonable proof system.

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


title: Algorithm for finding cliques

text:
# Question
Title: Algorithm for finding cliques
Given an arbitrary undirected graph $G = (V,E)$, I am interested in a low-polynomial time algorithm which can find several moderately large (ideally $O(n^\epsilon)$ vertices per clique for $\epsilon \> 0$) cliques in $G$, provided they exist.

I am aware that the problem of finding the maximal clique is NP-hard. For my purposes, however, I don't need maximality per say. Rather, it would be helpful to have an algorithm which runs relatively quickly and with high probability finds some nontrivial cliques.

I am aware that for fixed $k$, finding a $k$-clique if it exists can be done in $n^k$ time by simply testing all subsets of $k$ vertices. This algorithm appears to be of limited use because of the exponential growth in $k$.

Does there exist an algorithm or multiple which can, with high probability, find multiple moderately large cliques in a general undirected graph?

# Answer
Suppose that there exists a polytime algorithm which finds a clique of size $n^\epsilon$ if there is any. Then you can approximate maximum clique to within $n^{1-\epsilon}$ (assuming $\epsilon \leq 1/2$), which is NP-hard by a classical result of Håstad. Indeed, run your algorithm (stopping it if it exceeds its advertized running time), and check whether its output is a clique of size at least $n^\epsilon$. If so, output $n^\epsilon$, otherwise output $1$.

You might want to look into the planted clique problem, in which the goal is to find a clique "planted" inside a uniformly random graph. This is possible in polytime (with high probability) as long as the clique is large enough, $\Omega(\sqrt{n})$. Your case may be different, but similar ideas might work in practice.
> 3 votes

---
Tags: algorithms, graphs, probabilistic-algorithms, clique
---


# Question
Title: What algorithm to use for this kind of routing optimization?
Let's imagine a situation in order to fully understand the problem : let's say a lone human is walking back home at a very late time. He needs to find the safest path home. He naturally use the GPS with a start point A and a destination point B. Now the data I have may be GPS locations with an information stating the danger of that location, and those datas are usually available for the whole city. How can I actually plot the safest and also (if possible) fastest route from A to B using my datas ?

I actually looked for the way google maps plot it's routes and I understood it used the Dijkstra's algorithm, but it doesn't seem to be adapted to my problem.

I believed google maps could actually send me back every possible routes from A to B, then I could use my datas to calculate the safest route using a TSP algorithm (probably the ACS applied to the TSP) in order to optimize the use of the datas and with edge weights corresponding to the associated safety of the sub-path ?

Or maybe another algorithm should be used ?

# Answer
The answer depends on what you mean by "safest".

According to one interpretation, each short stretch of the route has a "danger" rating, and the overall danger of a route is the *sum* of the dangers of the individual stretches. In this case your problem is just shortest path in disguise – given each edge a weight according to its danger. If you want to consider both the danger level and the length, assign the weights as some linear combination of the two.

According to another interpretation, the danger of a route is the *maximum* of the dangers of the individual stretches. In this case you can use binary search to reduce your problem to shortest path. Given a danger level $D$, you can compute the shortest distance that only goes through edges of danger at most $D$. In this way you can find the minimal $D$ for which it is possible to get from A to B, as well as (for example) the minimal $D$ for which it is possible to get from A to B using a path at most twice the distance from A to B.
> 2 votes

---
Tags: algorithms, graphs, optimization, traveling-salesman
---


# Question
Title: Reconstruct graph of N edges from a matrix of shortest pair distances (N*N) (i.e. result from Floyd-Warshall algorithm)
I want to reconstruct a graph when given the results of a Floyd-Warshall shortest pair distances matrix, similar to the problem being solved in this question:

Is it possible to reconstruct graph if we have given matrix of shortest pairs

The only difference being that, whilst the problem from the linked-to question seeks to find a graph of $N-1$ edges, I want to produce a graph containing $N$ edges.

I've already found a more efficient way of solving the problem from the question linked above. Instead of using the solution offered there, I have found that building a minimal spanning tree also yields the correct result, namely a graph of $N-1$ edges that, when given as input to the Floyd-Warshall algorithm, produces exactly the matrix of minimum distance pairs with which we started.

Now we have one edge left to add. This is the part I am unable to figure out. It boils down to this:

**I have a graph of $N-1$ edges, which is represented by a matrix of shortest pair distances. Out of a list of candidate edges, how can I efficiently (i.e. without brute forcing) find which edge to add that does not change even a single value in the matrix, preserving all minimum distances?**

Thanks!

# Answer
> 0 votes
I've myself found a solution to the problem.

After you have computed the Minimum Spanning Tree, and thus have a graph of $n-1$ edges, you must iterate over the list of remaining edges. This list of edges must be sorted by weight, in nondecreasing order. For every edge, you check whether its weight is equal to the shortest distance between its constituent nodes. If it is, discard the edge and move on to the next in the list. The first edge you find, for which the previously mentioned test does not hold, is the edge that must be added to the graph.

# Answer
> 2 votes
Pick any pair of vertices $u,v$ where it is possible to reach $v$ from $u$. Add an edge $u \to v$ with a length that is really large.

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


# Question
Title: Are $BPP^{BPP^{\oplus P}}$ and $BPP^{NP}$ contained in $BPP^{\oplus P}$?
1. Does $BPP^{NP}\subseteq\Sigma\_k^P\cap P/poly^{NP}\subseteq BPP^{\oplus P}$ hold at some $3\leq k\<\infty$?
2. Also is $BPP^{BPP^{\oplus P}}\subseteq BPP^{\oplus P}$ known?

Note Sipser gives $BPP\subseteq \Sigma\_2P$ and Adleman gives $BPP\subseteq P/poly$ and so I am tempted to say $k=3$ in $1.$ works. I am not sure relativization plays here.

# Answer
> 2 votes
Adelman's theorem relativizes, i.e. for every oracle $O$ we have $\mathsf{BPP^O\subseteq P/Poly^O}$. To see why you have to go over the proof of Adelman's theorem. The proof goes through showing that given a probabilistic machine with exponentially low error probability, there exists a sequence of coin tosses which produces the correct answer for all (fixed length) inputs. This remains true in the relativized world, use that coin sequence as the advice, and query the oracle whenever necessary while simulating the probabilistic machine with the coins given in the advice.

Additionally, $\mathsf{BPP^{\Sigma\_i}}\subseteq \Sigma\_{i+3}$. Again, you have to examine the details in the proof of $\mathsf{BPP\subseteq\Sigma\_2}$. Suppose $L\in\mathsf{BPP^{\Sigma\_i}}$, and $M$ is an oracle probabilistic Turing machine for $L$ with exponentially low error probability. You can use the same idea from $\mathsf{BPP\subseteq\Sigma\_2}$, and claim that if $x\in L$ then the set of coin sequences who lead $M$ to accept is big, and in that case it can cover $\\{0,1\\}^m$ with a small number of shifts, where $m=poly(|x|)$ is the amount of coins used. Similarly, if $x\notin L$ you claim that the set of accepting coin sequences is small and cannot cover $\\{0,1\\}^m$ with a small number of shifts. All this remains true in the relativized world, as you only reasoned about the "BPP part" of $M$, i.e how it behaves with different coin tosses depending on whether or not the input is in $L$.

What's different is that when you find yourself in need to say "some vector $r\in\\{0,1\\}^m$ is obtained by shifting an accepting sequence", the part verifying that a sequence is indeed accepting will add additional $i+1$ quantifiers to the formula, after the initial two who talk about space shifting. To be more clear, your final formula has the form:

"$x\in L$ iff there exist shifts such that every vector $r\in\\{0,1\\}^m$ is obtained by performing one of those shifts on an accepting coin sequence for $x$", this is equivalent to:

"$x\in L$ iff there exists shifts such that every vector $r\in\\{0,1\\}^m$ can be shifted to generate an accepting coin sequence for $x$". Saying some vector $v$ is an accepting coin sequence requires expressing "$M$ accepts $v$" where $M$ is a poly time machine with access to a $\Sigma\_i$ oracle. You can express this using a $\Sigma\_{i+1}$ formula (this is analogous to $\mathsf{P^{\Sigma\_i}\subseteq \Sigma\_{i+1}}$).

The above shows that $\mathsf{BPP^{NP}\subseteq \Sigma\_4\cap P/Poly^{NP}}$. As for your second question, I don't know if there are complete problems for $\mathsf{BPP^{\oplus P}}$, so this might make the class $\mathsf{BPP^{BPP^{\oplus P}}}$ ill defined. One interpretation is asking whether the containment holds for every oracle in that class. I doubt this is known, but no obvious important/terrible implication comes to mind. Note that disproving this containment is out of the question, as it would immediately imply $P\neq \oplus P$.

---
Tags: complexity-theory
---


# Question
Title: Does the 3SAT problems have to have consistent operators?
What are the rules pertaining to 3SAT as to the actual boolean equation?

The main thing I do not understand is in a given boolean expression within a single clause can you have both AND + OR operators i.e. (x1 **&** x2 **|** x3) or do they have to remain consistent i.e. (x1 **&** x2 **&** x3) or (x1 **|** x2 **|** x3)?

That being said when connecting clauses together do the boolean operators have to be consistent?

i.e. (x1 & x2 & x3) **&** (x1 & x2 & x3) **&** (x1 & x2 & x3)

```
or

```

i.e. (x1 & x2 & x3) **|** (x1 & x2 & x3) **|** (x1 & x2 & x3)

or can they be mixed up like

i.e. (x1 & x2 & x3) **|** (x1 & x2 & x3) **&** (x1 & x2 & x3)

```
or

```

i.e. (x1 & x2 & x3) **&** (x1 & x2 & x3) **|** (x1 & x2 & x3)

Can a 3SAT problem just be a huge jumble of different logic operators or do they have to remain consistent throughout the equation? Ever example I have seen has consistent operators and I cant seem to find the answer to the question anywhere.

# Answer
> 1 votes
3SAT is a problem of deciding satisfiability of boolean formula in 3CNF form: this means that

1. Each clause has either exactly 3 different literals in each clause or at most 3 literals in each clause, according to different definitions.
2. Only $\lor$ operators can be used inside clauses (not counting varible negations).
3. Only $\land$ operators can be used outside clauses.

\[General\] SAT problem does not have a limit on number of literals in a clause and Circuit SAT allows any boolean formula.

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


# Question
Title: Find cut vertex in tree with constraint on the size of largest component
I have a connected and undirected graph without cycles (i.e. a tree), and I am trying to find a single cut vertex that, when removed, disconnects the graph into a set of connected components. The largest of these components should not have size greater than some threshold. So if one such cut vertex exists, I need to find an algorithm that returns it (possibly in linear time). The only approach I could think of is the following:

* remove from the graph all vertices that have only one outgoing edge (i.e. one neighbour); these are the leaves of the tree
* on the resulting graph, repeat the process until only one vertex remains; this should be the cut vertex
* take back the original graph and remove the cut vertex. Check the size of the largest connected component

This algorithm should run in linear time, but I am not sure it will work in any situation. What's your opinion? The other thing I could think of is that the cut vertex should always be in the minimum vertex cover of the graph, although I don't really know where to go from here...

# Answer
Given a graph $G$ and a threshold $k$, you are looking for an articulation point whose removal divides the graph into connected components all of size $\le k$. This can be done in linear time.

First, construct the block-cut tree of $G$. This is a tree $T$ that has one node for each biconnected component of $G$ and one node for each articulation point of $G$, with an edge between a biconnected component $c$ and an articulation point $a$ if $a$ is contained in $c$. The block-cut tree can be constructed in linear time.

Now you want to find an articulation node in the tree $T$ whose removal disconnects the tree into connected components all of size $\le k$. This can be done in linear time. In particular, the algorithm problem is the following:

Given a tree $T$ and a threshold tree, we are looking for a node in $T$ whose removal disconnects $T$ into connected components all of size $\le k$.

This can be done in linear time. You pick an arbitrary node to be the root of $T$. With a bottom-up traversal, you annotate each node with the number of descendants it has. Now if we focus on a single node, we can use the annotation on its neighbors to determine the size of all connected components that result if we delete that node, in time proportional to the number of neighbors it has. This lets you check whether deleting that node would leave you with connected components all of size $\le k$. So iterate over all nodes and check whether any qualifies. The total amount of work is proportional to the number of edges in the tree, which is proportional to the number of vertices in the tree.

Thus, the total running time is linear in the size of $G$.
> 1 votes

# Answer
Your algorithm may not work. What you describe, in fact, is an algorithm for computing the center of the tree. The following is a brief theory behind this algorithm.

The *distance*, denoted by $dist(v,u)$, between two vertices $u$ and $v$ is defined as the **shortest** path between $u$ and $v$. The *eccentricity* of a vertex $v$ is defined as $$ \epsilon(v)=\max\_{u \in V}\\{dist(v,u)\\}$$ In simple words $\epsilon(v)$ is the maximum among all distances from the $v$ to a vertex $u$.

We define the *center* of a graph $G$ is the set of vertices with minimum eccentricity. Observe that step-by-step leaf removal in your algorithm does not change the eccentricity of the center.

Your algorithm essentially computes the center of the tree but the following is a counterexample. This tree

has the center $v\_c$. Your algorithm will return $v\_c$ as the cut vertex. But if your threshold is $3$ then the optimal cut vertex would be the vertex $u$.
> 2 votes

---
Tags: algorithms, graphs, searching
---


# Question
Title: Decidability of CFG that accepts at least one odd length string
> Let $L$ be the language$\\{\langle G \rangle : G\text{ is a CFG and L(G) accepts at least one odd-length strings}\\}$.
>
> Prove that $L$ is decidable or undecidable.

Here is my attempt:

$L$ = On input $\langle G \rangle$, where $\langle G \rangle$ is a CFG:

1. Construct CFG, such that $L(O)$ contains only odd length strings.
2. Construct CFG $\langle H \rangle$ such that $L(H) = L(O) \cap L(G)$
3. Input $\langle H \rangle$ to the decider $E\_{\text{cfg}}$
4. If it accepts, $reject$.
5. Else, $accept$.

Is my proof correct? In the first step, can I construct a DFA, $O$ such that $L(O)$ consists of only odd length strings instead of a CFG?

# Answer
You cannot compute the intersection of two context-free grammars, at least not if you expect the answer to be another context-free grammar. The reason is that context-free languages are not closed under intersection (consider $a^nb^nc^m \cap a^mb^nc^n = a^nb^nc^n$).

However, context-free languages are closed under intersection with a regular language, and moreover there is an efficient algorithm that, given a context-free grammar $G$ and an NFA $A$, computes a new context-free grammar for the language $L(G) \cap L(A)$. You should use this algorithm in your second step.

Another problem with your solution is that it's not clear what you mean by "$L(O)$ contains only odd length strings". There are many languages that contain only odd length strings, for example the empty language. You want $L(O)$ to contain *only* and *all* odd length strings, that is, you want it to be the language of odd length strings.
> 3 votes

---
Tags: computability, turing-machines, context-free
---


# Question
Title: Is the set of languages recognized by a Turing machine with an oracle countable?
I am currently taking a class in complexity theory and I am struggling with this question.

We define a TM with Oracle per. Sipser 6.18 as:

"An oracle for language $B$ is an external device that is capable of reporting whether any string $w$ is a member of $B$. An oracle Turing machine is a modified Turing machine that has the additional capability of querying an oracle. We write $M^b$ to describe an oracle Turing machine that has an oracle for language B."

I think that the answer is potentially false. We know that the set of languages is uncountable and suppose we had a Oracle Turing machine that accepts if the oracle answers YES, reject otherwise. Wouldn't that mean that then the set of languages recognized by TM with an oracle be uncountable?

# Answer
Every language can be accepted by a Turing machine with an appropriate oracle, for example an oracle for the very language you want to accept. So if you understand "languages recognized by a Turing machine with an oracle" in this way, then certainly their number is uncountable.

Another way to understand this phrase is the you *fix the oracle* and then ask how many languages are recognized by a Turing machine with access to this specific oracle. In this case the number of languages is countable, since there are countably many ways to specify a Turing machine.
> 4 votes

---
Tags: complexity-theory, turing-machines, oracle-machines
---


# Question
Title: What is a good example of an NL-complete context free language?
**Setting** Exactly as the title stated:

> Give an example of an $\mathsf{NL}$-complete context free language. $\newcommand{\angle}\[1\]{\langle #1 \rangle}$

**Current Solution**

Recall in the past we proved that $E\_{DFA}$ is regular, so it is also context free. $E\_{DFA}$ is in $\mathsf{NL}$ since given DFA $\mathcal M$ over $n$ states, we can start at the initial state and nondeterminstically traverse through states of $\mathcal M$ for at most $n$ steps, storing only the current state ($\log n$ space). Note if there is a path to an accept state, then it must be $\le n$ steps long. So if there is no path to an accept state within $n$ steps, then $\mathcal M$ does not accept any string, thus $\mathcal M \in E\_{DFA}$.

Now we show $\overline{PATH} \le\_l E\_{DFA}$ and since $PATH$ is $\mathsf{NL}$-complete and $\mathsf{NL} = \mathsf{coNL}$, it follows that $E\_{DFA}$ is also $\mathsf{NL}$-complete. Given an instance $\angle{G,s,t}$, we construct a DFA $\mathcal M$ by letting $s \in G$ be $q\_{initial}$, and $t \in G$ be $q\_{accept}$. We label the edge arbitrarily from $\\{0,1\\}$. Clearly this can be done in log-space. So now we show $$\angle{G,s,t} \in \overline{PATH} \Leftrightarrow \mathcal M \in E\_{DFA}.$$

Suppose $\angle{G,s,t} \in \overline{PATH}$, then there is no path from $s$ to $t$, so there is no path from $q\_{initial}$ to $q\_{accept}$ in $\mathcal M$, then $\mathcal M$ does not accept any strings so it is in $E\_{DFA}$. Conversely, suppose $\angle{G,s,t} \not\in E\_{DFA}$, then there is a path from $s$ to $t$, taking this path in $\mathcal M$ correspond to a $\mathcal M$ accepting some string, so $\mathcal L(\mathcal M) \ne \emptyset$ and $\mathcal M \not\in E\_{DFA}$.

**Problem**

I don't think my algorithm for proving $E\_{DFA} \in \mathsf{NL}$ is correct.

# Answer
In other words, you are asked to find an $\rm NL$-complete language $A$ and a context-free language $B$ such that $A \equiv\_{\rm{L}} B$. We choose $A = \it{PATH}$ and $\\{{\tt{0}, \tt{1}， \tt{\\#}}\\}^\* \supseteq B = f(A)$, in which $f: A \to B$ is defined as follows. $$ \newcommand{\Bra}\[1\]{\langle #1 \rangle} f(\Bra{G, s, t}) = \Bra{s}^{\mathcal{R}}({\tt{\\#}} \Bra{e\_1} \Bra{e\_2} \cdots \Bra{e\_m} {\tt{\\#}} )^n\Bra{t}, $$ where $G = (V, E)$, $|V| = n$, $E = \\{e\_1, \dots, e\_m\\}$, $\Bra{e\_i} = {\tt{\\#}}\Bra{u\_i}{\tt{\\#}}\Bra{v\_i}^{\mathcal{R}{}}{\tt{\\#}}$ if $e\_i = (u\_i, v\_i)$.
> 2 votes

---
Tags: complexity-theory, context-free, space-complexity
---


title: Proof of existence of prefix in NFA

text:
# Question
Title: Proof of existence of prefix in NFA
Let $$A= (Q,Σ,δ,s,F)$$ be a NFA. Prove the following statement:

$∀q ∈ Q: (∃ w\_2 ∈ Σ^\* :δ (q, w\_2) ∩ F \ne ∅ ⇒ ∃w\_1 ∈ Σ^\*:w\_1w\_2 ∈ L(A))$

I figured out that it means that if all the states have a path to the final state, that the **word** describing their path is a suffix of a word that is accepted from the NEA.

The thing is: How can I be sure that the NEA accepts all words with that suffix if it doesn't start from the **s** state.

Any leads?

# Answer
> 1 votes
The statement is false. Consider the NFA on the alphabet $\\{a\\}$ having two states: an initial state $q\_0$, and the unique final state $q\_f$. The transition function is given by $\delta(q\_0,a) = \\{q\_0\\}$ and $\delta(q\_f,a) = \\{q\_f\\}$. For every word $w\_2$ it is the case that $\delta(q\_f,w\_2) \cap F = \emptyset$, yet $w\_1 w\_2 \notin L(A)$ for all $w\_1$.

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


title: Register model of computation

text:
# Question
Title: Register model of computation
It consists of one read only input memory and write only output medium. The computation proper takes place in a working memory of limited size. When stating that a problem can be solved with a certain number of bits, what we mean is that the working memory consists of that many bits. The input and working memories are divided into words of $w$ bits for a fixed parameter $w$. Random access to to input and working memory is provided. In the context of $n$ words, assume as is common , that $w = \theta(\log{n})$.

**Question :** What it means "In the context of $n$ words, assume as is common , that $w = \theta(\log{n})$. "

**Link :** " Space-efficient Basic Graph Algorithms Link"

# Answer
> 3 votes
The word RAM is a model of computation in which basic operations operate on words. For example, adding two words costs $O(1)$ in this model. In algorithms class, it is often tacitly assumed that basic operations on indices and on data cost $O(1)$. For example, consider the following program for computing the maximum of an array:

```
calculate-max(A, n):
max = A[1]
i = 2
while i <= n:
  if A[i] > max:
    max = A[i]
  i = i + 1

```

This program is usually assumed to run in $O(n)$. This means that the following operations should all cost $O(1)$:

* Assignment of data points (`max = A[1]`, `max = A[i]`)
* Assignment of indices (`i = 2`, `i = i + 1`)
* Comparison of indices (`i <= n`)
* Comparison of data points (`A[i] > max`)
* Arithmetic on indices (`i + 1`)

In order to accommodate this in the word RAM model, we need to assume that words have length at least $\Omega(\log n)$, since this is the length of indices such as `i` above. Usually words of length $\Theta(\log n)$ are enough for performance of an algorithm in the word RAM to match its performance as perceived by the algorithm designer. Therefore the most common word RAM model is the *logarithmic cost word RAM*, in which words have length $\Theta(\log n)$ (the constant doesn't matter since it only affects the running time by a constant factor).

The only remaining question is – what is $n$? It is usually assumed that $n$ is such that the input is $n$ words long. This definition is a bit circular (since the length of a word depends on $n$), but usually works out nevertheless.

---
Tags: computation-models
---


title: Infinite sequence of graphs

text:
# Question
Title: Infinite sequence of graphs
http://jgaa.info/accepted/2011/HasheminezhadMcKayReeves2011.15.3.pdf
Hello I stumbled upon this paper. On page $4/20$ the figure shows an infinite sequence of $5-$regular, connected planar graphs. But they do not define it rigorously. The first graph of the sequence is clearly the icosahedron, and I feel that the next ones are constructed by "gluing" copies of $D\_1$ but the only way I thought of constructing $D\_k$ from $D\_{k-1}$ and an icosahedron, would be removing a vertex from the border of its outer face. Then we remove a vertex from the border of the outer face of a copy of icosahedron and then we connected the vertices of degree $4.$ But this would leave us with less vertices than the graphs shown there.
Is my construction ok? Also which procedure gives us the sequence shown on the article?
thanks in advance.

# Answer
> 0 votes
Take the graph $D\_1$, and cut the bolded edge in the middle, so that each of its two halves has degree 3 (including the bolded edge). Take $k$ copies of this, and paste them along bolded edges in a cyclic fashion. You get $D\_k$.

---
Tags: graphs, planar-graphs
---


# Question
Title: When solving dynamic programming in a grid, how do you recognize whether the solution should start at the bottom-right of the table or top-left?
Example of start top-left, Coin Collecting problem in grid: https://www.youtube.com/watch?v=94FEC\_uNwVM

Example of start bottom-right, Dungeon Game problem in grid: https://leetcode.com/problems/dungeon-game/description/

I knew the Coin Collecting problem, so I started trying to solve Dungeon Game the same way, starting from the top-left (although it can also be solved bottom-right). Turns out Dungeon Game is solved from the bottom-right. How do I recognize this earlier?

```
function initTable(m, n, f) {
  var T = [];
  for (var r = 0; r < m; r++)
    T.push(Array(n).fill(f));
  return T;
}

var grid = [
  [-2,-3,3],
  [-5,-10,1],
  [10,30,-5],
];

function calculateMinimumHPFromTopLeft(dungeon) {
    var M = dungeon.length;
    var N = dungeon[0].length;

    var hp = initTable(M+1, N+1, Number.POSITIVE_INFINITY);
    hp[0][1] = 1;
    hp[1][0] = 1;

    for (var i = 1; i < M+1; i++) {
        for (var j = 1; j < N+1; j++) {
            var need = Math.min(hp[i-1][j], hp[i][j-1])-dungeon[i-1][j-1];
            hp[i][j] = need <= 0 ? 1 : need;
        }
    }

    return hp[M][N];
}

function calculateMinimumHPFromBottomRight(dungeon) {
    var M = dungeon.length;
    var N = dungeon[0].length;

    var hp = initTable(M+1, N+1, Number.POSITIVE_INFINITY);
    hp[M][N-1] = 1;
    hp[M-1][N] = 1;

    for (var i = M-1; i >= 0; i--) {
        for (var j = N-1; j >= 0; j--) {
            var need = Math.min(hp[i+1][j], hp[i][j+1])-dungeon[i][j];
            hp[i][j] = need <= 0 ? 1 : need;
        }
    }

    return hp[0][0];
}

console.log(calculateMinimumHPFromTopLeft(grid))   // 6 (wrong)
console.log(calculateMinimumHPFromBottomRight(grid))  // 7 (correct)

```

# Answer
If a cell depends on cells to its left and bottom, the solution should start at the bottom-left. And so on for all other combinations of left/right and top/bottom.
> 3 votes

---
Tags: algorithms, dynamic-programming
---


title: A several equivalent NP definitions

text:
# Question
Title: A several equivalent NP definitions
There are two definitions of NP I found:

1) NP is a set of problems that have poly-size certificates, and with a given input, there is a poly-time certifier that checks the proposed solution.

2) NP is a set of problems that can be solved by non-deterministic algorithm in polynomial time.

I think (1) is a standard definition that appears everywhere, but I found (2) from one of the lecture videos, but to the best of my knowledge, I think the reason why they're equivalent is that, a non-deterministic algorithm can make a lucky guess out of polynomially many options in constant time, and a result of these guesses would be our certificate.

But why (2) is restricted to guess one out of polynomially many options? Why can't it guess one out of exponentially many options? I don't have any knowledge about how non-deterministic algorithm or turing machine works.

# Answer
> 5 votes
The standard definition you'll usually find is the second one, but it makes no difference since they're indeed equivalent, and you can prove both arrows, I'll give a sketch of proof:

To see that (1) $\Rightarrow$ (2), consider a machine that non-deterministically guesses a certificate and then acts as a poly-time certifier.

On the other hand, to see (2) $\Rightarrow$ (1), observe that if a nondeterministic Turing machine decides $x \in L$ in polynomial time, then the set of nondeterministic choices it made in the path towards the accepting state is a certificate for $x$, and it must have polynomial size because by hypothesis every branch of the computation must terminate in polynomial time.

As for your second question, it is not true that a nondeterministic Turing machine can only guess out of polynomially many options (if it were the case, it could be simulated by a polynomially related deterministic machine). The limitation is that every computational branch must terminate in polynomial time. For instance, consider a nondeterministic machine for $\textsf{SAT}$: the number of valuations is exponential in the number of variables.

The reason why we give the characterization you cite in (1) is that we want to prove that $\textsf{NP}$ is the class of problems for which you can "guess" a solution and verify it in polynomial time, but a certificate that is more than polynomial in size cannot be "guessed" in polynomial time.

# Answer
> 1 votes
In fact a NTM can make a lucky guess out of *constant* possible many options in constant time. But each branch of computation takes polynomial time when it comes to the definition of the NP class. This is a post related to how a NTM works.

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


title: Lower bounding DFA

text:
# Question
Title: Lower bounding DFA
If the regular language $L$ is defined as $\\{ w \in \Sigma^\* \mid |w| \leq 140 \\}$. Why does any DFA for it must have at least 142 states? Why not only 140 states?

# Answer
Because $140$ states are not enough.

For any $n\>0$, if you have the constraint $|w| \leq n$ then you will have $n+1$ accept states and one additional "dead" (reject) state in case the length of the input is greater than $n$. So in total you have $n+2$ states. For example if $|w| \leq 2$ then you have 4 states: (1), (2), (3), (dead), where states from 1 to 3 are accept states.

```
 -->(1)--a,b-->(2)--a,b-->(3)--a,b-->(dead)

```

The "dead" state loops on itself for any input.

But we still need to prove it formally. We could show that the minimum DFA accepting the language $$L =\\{ w \in \Sigma^\* \mid |w| \leq n \\}$$ has $n+2$ states. Let's assume that $x$ and $y$ are strings of different length not greater than $n$. Then each such string corresponds to a single state of the minimum DFA because $x$ and $y$ are distinguishable. To prove it WLOG assume $x$ is the shorter string. Let's choose any string $z$ of length $n-|x|$. Then it follows $\delta(xz) \in F$ while $\delta(yz) \notin F$ since $|yz| \> n$. But there are exactly $n+1$ strings of distinct length no greater than $n$ $(\text{namely } 0,1,\dots, n)$, and there must be a single non-accept state. So, the minimum DFA must have $n+2$ states.
> 2 votes

---
Tags: finite-automata
---


# Question
Title: If a problem is Cook-NP hard, and this problem is in NP, does it prove that the problem is Karp-NP-complete?
I got recently confused when I noticed that there exists 2 types of polytime reductions, which lead to 2 different concepts of NP-hardness.

This is well explained in the answer to this question: Can one show NP-hardness by Turing reductions?

While a Karp reduction is required to show whether a problem is NP-Hard or co-NP-Hard, with Cook (aka Turing) reductions one only shows that a problem is "Cook-NP-hard", in a sense which does not distinguish NP-hardness from co-NP-hardness. More precisely,

* In a Karp reduction, you map each instance $I$ of Problem $A$ to an instance $f(I)$ of Problem $B$, where $f(I)$ can be computed in polytime, and such that $$I \text{ is a Yes-instance for $A$} \iff f(I) \text{ is a Yes-instance for $B$}.$$ If $A$ is (Karp-)NP-Hard, this shows that $B$ is (Karp)-NP-Hard, too. And if $A$ is (Karp-)co-NP-hard, this shows that $B$ is (Karp)-co-NP-Hard, too.
* In a Cook-reduction, you assume that there exists a polytime procedure $F$ to solve Problem $B$, and you show that Problem $A$ could be solved by calling this procedure a polynomial number of times. If Problem $A$ is known to be NP-hard, this shows that $B$ is (cook)-NP hard, but this does not tell us anything about the membership of $B$ in (Karp)-NP-Hard or (Karp)-co-NP-Hard.

1) In my understanding, Karp reductions only apply to decision problems, while we can show that any kind of problem is Cook-NP-Hard, is that correct?

2) If I want to prove that a problem is NP-complete, is it enough to show that this problem is Cook-NP-hard, and then to show that this problem is in NP? Similarly is a problem is Cook-NP-hard and in co-NP, does it prove that this problem is co-NP-complete?

3) A perhaps equivalent formulation of this question is as follows: *While there is a distinction between the notions of Cook- and Karp-NP-Hardness, is there a real distinction between the notions of Cook- and Karp-NP-Completeness?*

# Answer
> 1 votes
NP-hardness is a property of decision problems. It doesn't matter whether you define it using Karp reductions or Cook reductions.

NP-hardness and NP-completeness are defined using Karp reductions. If you prove that a problem is Cook-NP-hard, then it doesn't imply that it is Karp-NP-hard. Indeed, coSAT (the collection of unsatisfiable CNFs) is Cook-NP-hard but probably not Karp-NP-hard. Under reasonable hardness assumptions, there are even problems in NP which are Cook-NP-hard but not Karp-NP-hard. See for example Mandal, Pavan, and Venugopalan, Separating Cook Completeness from Karp-Levin Completeness under a Worst-Case Hardness Hypothesis.

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


# Question
Title: Looping through random integers - will it halt with probability 1?
Say I have a simple program that has the pseudocode like this:

```
min = 1
max = 100
c = 5
random = randomInt(min,max)
while(c != random):
    random = randomInt(min,max);

```

Theoretically, from what I understand, I cannot guarantee this will halt. However, is this true for both PRNGs and say, random integers generated using atmospheric noise? Is there a difference? And by convention, can I say this will "almost surely" halt (probability 1), but still cannot guarantee this? I'm still trying to wrap my mind around the edge case of a program with an almost sure chance of halting, and how this is viewed from a computational perspective.

# Answer
> 2 votes
For deterministic algorithms, the statement "Algorithm $A$ halts on input $x$" is well defined. However, when $A$ is randomized (i.e. has access to some random source during its computation) this question becomes meaningless, as you need to know what was the outcome of the random source in order to answer it.

You can ask "does $A$ always halt on $x$", i.e. does it halt for every possible output of the random source. In your case, assuming the source produces uniformly distributed elements in the given range, the answer is no, since e.g. the infinite sequence "444..." is a possible outcome of the source, and this will cause $A$ to never halt.

However, "Algorithm $A$ halts on input $x$" is now an event, i.e. it is a subset of your sample space (we associate this event with the set of random outputs who cause $A$ to halt). Events have probabilities, so you can ask "What is the probability that $A$ halts on $x$"? If your source is uniform, then the probability that your algorithm doesn't halt is $p=\prod\limits\_{i=1}^\infty\left(\frac{99}{100}\right)^i=0$. So in your case it is correct to say that the algorithm halts with probability $1$, but it is incorrect to say it always halts.

As for whether or not the randomness source matters, the answer is definitely yes. Consider the source which first chooses a number from the range uniformly at random, and then remembers it and outputs it to you in any later request (i.e. the source has memory, and different outcomes are not independent). In that case, your algorithm does not halt with probability $\frac{99}{100}$. For a source which always outputs $5$, it is true to say the the algorithm always halts (and not only with probability $1$, which is a weaker statement).

---
Tags: halting-problem, randomness, pseudo-random-generators
---


title: 3 blocks CBC-MAC

text:
# Question
Title: 3 blocks CBC-MAC
Let $M=(m\_1, m\_2)$, $M'= (m\_0', m\_1')$ be two two-block messages.

In other words, $|m\_1|=|m\_2|=|m\_1'|=|m\_2'|=n$.

We say that $M, M'$ **collide** for key $k$ if

$$E\_k(E\_k(m\_1)⊕m\_2) = E\_k(E\_k(m\_1')⊕m\_2').$$

How many two-block messages should one sample from $\\{0, 1\\}^{2n}$ s.t. with probability $≥ 1/2$ two (distinct) sampled messages collide?

I tried this approach:

Let $r$ be the number of samples.

Let $M,M'$ be two samples, since $E\_k$ is a bijection:

$$\text{P}\[E\_k(E\_k(m\_1)⊕m\_2) = E\_k(E\_k(m\_1')⊕m\_2')\]=\text{P}\[E\_k(m\_1)⊕m\_2=E\_k(m\_1')⊕m\_2'\]=\text{P\[two random strings are equal\]}=2^{-n}$$

So, $\text{P}\[E\_k(E\_k(m\_1)⊕m\_2) \neq E\_k(E\_k(m\_1')⊕m\_2')\]=1-2^{-n}$.

Therefore, $\text{P\[two samples of the $r$ samples collide\]}=1-\big(1-2^{-n}\big)^{\binom{r}{2}}$.

Now, we need to take a minimal $r$ s.t. $1-\big(1-2^{-n}\big)^{\binom{r}{2}}\geq\frac{1}{2}$.

Is it true? I suspect not because afterwards we need to use $r$ to prove that a $\text{CBC-MAC}$ with $3$ blocks is not secure.

# Answer
If $E\_k$ is a permutation, then this is a case of the birthday problem, with number of elements $d=2^n$. The probability of not finding a collision in $r$ uniformly distributed independent samples is $p(r)=\prod\limits\_{k=1}^{r-1}\left(1-\frac{k}{d}\right)\le \prod\limits\_{k=1}^{r-1}e^{-\frac{k}{d}}=e^{-\frac{1+2+...+(r-1)}{d}}\le e^{-\frac{r^2}{d}}$, thus:

$\Pr\left\[\text{finding a collision}\right\]=1-p(r)\ge 1-e^{-\frac{r^2}{d}}\ge\frac{1}{2}$ for $r\ge\sqrt{\ln 2 \cdot d}$.

It seems that you have lower bounded the probability of an intersection by the product of the probabilities, which is not necessarily true, so you probably want to recheck your derivation.
> 2 votes

---
Tags: cryptography
---


# Question
Title: ${L^*}$ the Kleene star language is decidable then is $ {L}$ decidable
let ${L^\*}$ be the Kleene star language which is definded like that : $${L^\*}=\\{w\_1,w\_2, \dots ,w\_n\mid n \geq0 \text{ and each $w\_i \in L$}\\}$$

I have to show of this correct or not ! $$ {L^\*} \text{is decidable } \Rightarrow {L} \text{ is decidable} $$

$\textbf{my idea was to use the reduction function }$

let $f\_k$ a calculatable function ; $$ f\_k :{L} \rightarrow {L^\*}$$ $$w \mapsto w\_1w\_2\dots w\_k \text{ with each $w\_i =w \text{ for all i}\in \[1,k\]$ }$$ $$ \text{for all w $\in{L}$} \Leftrightarrow f\_k(w)= w\_1w\_2\dots w\_k \in{L^\*} $$ then we have ; $$\text{for all w $\in{L}$} \Leftrightarrow f\_k(w) \in {L^\*} \Rightarrow {L}\leq {L^\*} \rightarrow {L} \text{ is decidable}$$

$\textbf{Is that correct ? }$

# Answer
> 1 votes
$w\in L$ indeed implies that $f\_k(w)\in L^\*$, where $f\_k(w)$ consists of $k$ copies of $w$. But how do you obtain the opposite implication? You might be able to decompose $f\_k(w)$ into words in $L$, while $w\notin L$.

In general, the implication is not true. Think about what happens when $L$ contains every singleton from the alphabet.

---
Tags: turing-machines, undecidability, decision-problem
---


# Question
Title: Why is $L= \{ 0^n 1^n | n \geq 1 \}$ not regular language?
I'm looking for intuition about when a language is regular and when it is not. For example, consider:

$$ L = \\{ 0^n 1^n \mid n \geq 1 \\} = \\{ 01, 0011, 000111, \ldots \\}$$

which is not a regular language. Intuitively it seems a very simple language, there doesn't seem to be anything complicated going on. What is the difference between $L$ and a regular language like:

$$L' = \\{ w \mid w \text{ does not contain } 11 \\} = \\{0,10\\}^\*\cdot (1 \mid \varepsilon).$$

I know how to prove that $L$ is not regular, using the Pumping Lemma. Here I am looking for **intuition** about what makes a language regular.

# Answer
To expand on Artem's comment, note that if we have an $m$ state automaton, at each point we can remember at most $\lg m$ bits of information about the part of input we have read so far. Based on this finite amount of information about the the previous bits of the input, you should be able to end up in the right accepting/rejecting state for all possible ways that the input can continue. If this amount of information is not sufficient to answer correctly then the language is not regular.

For this language we may need $m$ bits of information to be able to correctly answer where $m$ is an arbitrary large number (and therefore can be taken to be larger than $n$ which is fixed since the same atuomaton should work for all inputs).

One way to formally show this is pumping lemma. A more general way that is harder to use is to directly show that the number of equivalence classes of strings w.r.t. the language is not finite (we say strings $x$ and $y$ belong to the same class and write $x\sim y$ if for all strings $w$, $xw \in L$ iff $yw \in L$) which is the same as saying the amount of information that the machine needs to remember is not finite (constant w.r.t. to inputs).
> 6 votes

# Answer
Simple rule: Regular expressions can't count. That said, sometimes you are given languages that look like they need counting, but it turns out they actually don't. An example is that language over (0, 1) which contains equal numbers of substrings 001 and 100 and it turns out you cannot possibly have two more of one than of the other.

A regular language is a language that can be defined by a regular expressions. When "regular expressions" were defined, they were intentionally defined so that the languages can be parsed by a finite state machine. "regular expressions" could have been defined differently, to be more powerful, but they were not. I'd focus on languages recognised by finite state machine.

If you have a string X, then there will be some set of strings Y such that XY is in L. If you parse using a finite state machine, in each state there will be some set of strings Y so that parsing Y from that state will end up in an accepted state. And parsing any string X from the initial state will end up in some state.

So your language can be parsed by a finite state machine if for all initial strings X, there is only a finite number of *different* sets of suffix strings that create a string in L.

Look at your language: After parsing nothing, you need to parse $0^n1^n$. After parsing 0, you need to parse $0^n1^{n+1}$. After parsing 00, you need to parse $0^n1^{n+2}$. And so on. So there is an infinite number of sets that would be required, and a finite state machine would need an infinite number of states.
> 1 votes

# Answer
Another look at parsing using a finite state machine (equivalent to regular language): If you have a finite number of states, then there must be n, m such that parsing $0^n$ and $0^m$ leaves you in the same state. Parsing $0^n1^n$ leaves you in the accepted state. Since the state after parsing $0^m$ was the same, parsing $0^m1^n$ must also end in the accepted state.
> 0 votes

# Answer
You can not pump $0^n1^n$, the pumping lemma defines a regular language as those where given a word in the language of the form $xyz$, all expressions $xy^iz$ are also in the language.

You can't do this with any $0^n1^n$.

Since it fails the pumping lemma it's not regular.
> -3 votes

---
Tags: formal-languages, regular-languages, intuition
---


title: Pairs of Integers

text:
# Question
Title: Pairs of Integers
How to solve this problem efficiently?

You are to find all pairs of integers such that their sum is equal to the given integer number N and the second number results from the first one by striking out one of its digits. The first integer always has at least two digits and starts with a non-zero digit. The second integer always has one digit less than the first integer and may start with a zero digit.

Input: A positive integer on a line on its own giving the number of problems. Then, for each problem, single integer N, 10 ≤ N ≤ 10^9. Output: For each problem set, on the first line write the total number of different pairs of integers that satisfy the problem statement. Then, on the following lines, write all those pairs. Write one pair on a line in ascending order of the first integer in the pair. Each pair must be written in the following format: X + Y = N Here X, Y, and N, must be replaced with the corresponding integer numbers. There should be exactly one space on both sides of ’+’ and ’=’ characters.

Example Input:
1
302
Example Output:
5
251 + 51 = 302
275 + 27 = 302
276 + 26 = 302
281 + 21 = 302
301 + 01 = 302

# Answer
> 3 votes
This answer is but a hint, not a complete solution.

Equivalently, the question is to find natural numbers $a,b,c,p \in \mathbb{N}$ for a given $N \in \mathbb{N}$ such that $$(11a+b) \times 10^p + 2c = N$$ where

* $0 \leq b \< 10$
* $2c \< 10^p$

From this perspective, we can choose how best to iterate our choices. You should derive the possible range of each variable and their relation to each other. To reduce search time, it is recommendable to iterate from the variable that was smaller search range and will limit the range of other variables.

For example, try starting the search by iterating through possible values of $p$ which $0 \leq p \leq \lfloor \log\_{10}N \rfloor$

# Answer
> 3 votes
Suppose that the right-hand number results from erasing the $d$th digit from the right (starting to count at 0). We can write the left-hand number as $10^d(10a+b)+c$, where $0 \leq b \< 9$ and $c \< 10^d$, and then the right-hand number is $10^da+c$. The sum of both numbers is $$ 10^d(10a+b)+c + 10^da+c = 10^d(11a+b)+2c. $$ Given $d$, there are two options for $c$, differing by $5 \cdot 10^{d-1}$. Given $c$, we can calculate $11a+b$, say it needs to be equal to $m$. Then $b \equiv m \pmod{11}$, and this determines $b$ (we might get $b \equiv 10$, in which case we're stuck). Given $b$, we can calculate $a$.

Here is how all of this works out in your case of 302. We know that $0 \leq d \leq 2$, and we proceed to check all options:

* $d = 0$: then $c = 0$ and $11a+b = 302$, which means that $b \equiv 5 \pmod{11}$, and so $b = 5$. We calculate $a = 27$. The corresponding answer is $275 + 27 = 302$.
* $d = 1$: then $c=1$ or $c=6$. If $c=1$ then $11a+b = 30$, which means that $b \equiv 8 \pmod{11}$, and so $b = 8$ and $a = 2$. This corresponds to the solution $281 + 21 = 302$. If $c=6$ then $11a+b = 29$, which means that $b \equiv 7 \pmod{11}$, and so $b = 7$ and $a = 2$. This corresponds to the solution $276 + 26 = 302$.
* $d = 2$: then $c=1$ or $c=51$. If $c=1$ then $11a+b = 3$, which means that $a = 0$ and $b = 3$, corresponding to $301 + 01 = 302$. If $c=51$ then $11a+b=2$, which means that $a = 0$ and $b = 2$, corresponding to $251 + 51 = 302$.

The reasoning above shows that if $N$ is $k$ digits long then there are at most $2k$ solution, and it shouldn't take too much time to sort them.

---
Tags: algorithms
---


# Question
Title: Equivalence classes of regular languages
One used equivalence relation in regular languages is that for a language $L$ over alphabet $\Sigma$, $(x\sim^Ly)\Leftrightarrow (\forall w\in \Sigma^\* xw\in L \Leftrightarrow yw\in L)$.

That means, if two words $x,y$ are not in the same class, there exists $w\in \Sigma^\*$ such that $xw\in L$ but $yw \notin L$.

It is implied by Myhill–Nerode theorem, that if we have infinitely many equivalence classes for a language $L$, that $L$ is not a regular language.

My question is this: Is it correct to say that if we have an infinite amount of equivalence classes then there are infinitely many different $w\in \Sigma^\*$ that "breaks" such equivalence relation between those classes? If so, how do we prove it? If not, is there a counter-example?

# Answer
> 2 votes
Let $L$ be a non-regular language, and suppose that there were only finitely many separating words, say $n$. Construct a graph in which vertices are equivalence classes and the edge $(\[x\],\[y\])$ (where $x,y$ are the lexicographically first words in their equivalence classes, and $x\<y$) is colored by the set of words separating $\[x\]$ from $\[y\]$, where for each word $w$ we additionally indicate whether $xw \in L$ ("$w\<$") or $yw \in L$ ("$w\>$").

Ramsey's theorem states that there exists an infinite monochromatic clique $A$ colored $\chi$. Let $\[x\],\[y\],\[z\] \in A$, where $x \< y \< z$. We consider two possibilities:

* If $w\< \in \chi$ then we get a contradiction since due to $(x,y)$ we should have $yw \notin L$, whereas due to $(y,z)$ we should have $yw \in L$.
* If $w\> \in \chi$ then we reach a similar contradiction: considering the same edges as before, we should have $yw \in L$ and $yw \notin L$.

The finitary version of Ramsey's theorem shows that for each $n$, there is $N$ such that every language with at least $N$ equivalence classes must have at least $n$ separating words.

# Answer
> 1 votes
The answer is no. Consider the language $L=\\{0^n1^n | n\in\mathbb{N}\\}$. The language is not regular and hence $\\{0,1\\}^\*$ has infinitely many equivalence classes under the relation $\sim^L$. Let $C\_1$ be the equivalence class of $01$, and $C\_2$ be the equivalence class of $010$, then $\epsilon$ is the only separating suffix between them, since for all $w$ with $|w|\>0$ we have $01w,010w\notin L$.

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


# Question
Title: Increasing every starting edge by a constant, then the shortest path tree remains the same?
> Consider a directed graph `G = (V,E)` with non-negative costs on each edge. With `s` being a starting vertex. Prove that by adding a constant `k` to each edge `(s,u) ∈ E` such as `u ∈ V`, the shortest path tree starting from `s` will remain the same.

In an attempt to solve the above question (with a proof) I thought that if we add the same constant factor to every edge the relative order of path weights is preserved.
However, I am not sure how to state the proof correctly.

I have searched a lot, any help would be greatly appreciated.

# Answer
I think you can prove it by counter-example.

Assume your SPT (shortest path tree) from the original graph is no longer a valid SPT in the new graph. That means there's a node $f$ s.t. the path $(s, n\_1, n\_2, ..., f)$ in your SPT is no longer a shortest path, meaning some other path $(s, v\_1, v\_2, ..., f)$ *(whose length wasn't shorter before)* now has a shorter length.

Now show that's impossible by calculating how much the lengths of those two paths have increased.
> 3 votes

---
Tags: graphs, trees, shortest-path
---


# Question
Title: Give an example of a language whose Myhill-Nerode equivalence relation is such that if $x,y \in \{0,1\}^*$ with $x \neq y$, then $[x] \neq [y]$
Suppose $\Sigma = \\{0,1\\}$. Provide an example of a language $L \subseteq \Sigma^\*$ with the property that its associated Myhill-Nerode equivalence relation, $R\_L$, is such that every one of its equivalence classes is a singleton set; that is, if $x,y \in \Sigma^\*$ with $x \neq y$, then $\[x\] \neq \[y\]$, where $\[x\]$ and $\[y\]$ are equivalence classes with representative elements $x$ and $y$, respectively.

I suspect that this language cannot be regular, since the index of $R\_L$ is infinite.

# Answer
Consider the language $L$ consisting of words $w a 0 1^n$ where $w$ is an arbitrary word, $a$ is either 0 or 1, $w$ has at least $n$ letters and the $n$-th letter of $w$ is $a$. Clearly, given a word in $L$ there exists exactly one decomposition to this form (define $n$ to be the number of trailing ones in the string).

If $w \neq u$ then without loss of generality $w\_i = 0, u\_i = 1$ for some $i$. But then $w 0 0 1^i \in L$ while $u 0 0 1^i \notin L$. If $w$ is a prefix of $u$, then you can take $n$ which is larger than the length of $w$ but smaller than length of $u$.

In other words $L=\\{v a u a 0 1^n : |v| = n-1, |a| = 1\\}$; clearly this is a CFL.

(This is a variant of my answer from Can a language have $\Sigma^{\*}$ as its syntactic monoid?)
> 5 votes

# Answer
A random language $L$ satisfies this property almost surely. Indeed, consider any two $x,y \in \Sigma^\*$. For every $z \in \Sigma^\*$, the probability that $xz \in L \Leftrightarrow yz \in L$ is $1/2$, so almost surely $xz \in L \not\Leftrightarrow yz \in L$ for some $z$. That is, any two $x,y \in \Sigma^\*$ are inequivalent modulo $L$ almost surely. Since there are only countably many pairs $x,y \in \Sigma^\*$, all of them are inequivalent modulo $L$ almost surely.

We can "derandomize" this construction using diagonalization. Let $(x\_1,y\_1),(x\_2,y\_2),\ldots$ be some enumeration of all pairs of different words in $\Sigma^\*$. We define sets of words $A\_n,B\_n$ inductively; for each $n$, $A\_n$ and $B\_n$ will be disjoint finite sets, and $A\_n \supseteq A\_{n-1}$, $B\_n \supseteq B\_{n-1}$. The base case is $A\_0 = B\_0 = \emptyset$. Given $A\_{n-1},B\_{n-1}$, let $w$ be some word such that $x\_nw \notin B\_{n-1}$ and $y\_nw \notin A\_{n-1}$, and define $A\_n = A\_{n-1} \cup \\{x\_nw\\}$ and $B\_n = B\_{n-1} \cup \\{y\_nw\\}$; such a word $w$ exists since $A\_{n-1},B\_{n-1}$ are finite. Let $A = \bigcup\_{n \geq 0} A\_n$ and $B = \bigcup\_{n \geq 0} B\_n$, and note that $A,B$ are disjoint. The language $L = A$ separates every pair of words.
> 2 votes

# Answer
The language of palindromes over a non-unary alphabet is a nice example. See for example this question.
> 0 votes

---
Tags: formal-languages
---


# Question
Title: On graph isomorphism for weighted graphs
Is there a $O(n^2)$ algorithm to resolve isomorphism between two weighted $n$-vertex graphs? This is a much easier problem than graph isomorphism.

Basically take an real edge weight set $\\{w\_1,\dots,w\_s\\}$

All weights on the graph edges are from this set.

# Answer
This on contrary appears to be a problem of greater difficulty than graph isomorphism. If you had a polynomial time solution to this problem,you can reduce graph isomorphism to it by keeping each edge weight say equal to some constant $c$. Also graph isomorphism is not known to have a polynomial time solution. It is a still an open question.
> 7 votes

# Answer
As sasha mentions, your problem is actually a generalization of the usual graph isomorphism. To put it differently, graph isomorphism is a special case of your problem, in which all weights are the same. Therefore your problem can only be more difficult.

On the other hand, it is easy to reduce your problem to the usual graph isomorphism. Assuming that only edges have weights, the idea is to split each edge into a path of length two, and to attach to the middle node a clique whose size depends on the weight (we only need that different weights have different clique sizes, and that the cliques be large enough). So your problem is GI-complete, i.e., equivalent to graph isomorphism.
> 5 votes

# Answer
As others pointed out already, graph isomorphism is a special case of weighted graph isomorphism, where all edges have the same weight. And on the other hand, weighted graph isomorphism can be reduced to graph isomorphism.

In fact, most isomorphism problems for finite structures turn out to be essentially equivalent to graph isomorphism. A theoretical construction showing this which tries to keep the valence of the resulting graphs as small as possible is given in *Graph Isomorphism, General Remarks* by Gary L. Miller. The presentation *Practical Graph Isomorphism, II* by Brendan McKay and Adolfo Piperno uses a more practical approach to convey the same message. They first highlight the *Ubiquity of graph isomorphism* with concrete examples, and then mention *Permutation equivalence of linear codes*, which is a rare example of a finite structure whose isomorphism problem is not known to be reducible to graph isomorphism. Very efficient practical reductions of the mentioned examples to the (vertex) colored (di)graph isomorphism problem solved by nauty and Traces can be found in section "14 Variations" of the *nauty and Traces User’s Guide (Version 2.5)*:

> If the original graph has $n$ vertices and $k$ colours, the new graph has $O(n \log k)$ vertices. This can be improved to $O(n \sqrt{\log k})$ vertices by also using edges that are not horizontal, but this needs care.
> 3 votes

# Answer
The problem is in fact easier than graph isomorphism for a **directed graph when the weights are all distinct**. I wonder if this was the original intent of the question.

For distinct-weighted directed graphs A and B with same number of vertices $n$ and edges $e$, do the following:

* Sort the edge weights of A and B in decreasing order.
* Maintain a labeling $\theta$ of vertices of graph B, initialized to the empty set $\phi$. We will fill this labeling in our algorithm and check if we get any contradictory labels. Let us call the label of a vertex $u$ under the labelling $\theta$, $\theta(u)$
* iterate over edges $e\_i=(u\_i, v\_i)$ in A and corresponding edge $e\_i' = (u\_i', v\_i')$ in B in the sorted order
    + if $weight(e\_i) \neq weight(e\_i')$ then graphs are not isomorphic. Terminate
    + if $\theta(u\_i') == \phi$, then $\theta := \theta\ \cup (u\_i', u\_i)$
    + if $\theta(v\_i') == \phi$, then $\theta := \theta\ \cup (v\_i', v\_i)$
    + if $\theta(u\_i') \neq \phi$ and $\theta(u\_i') \neq u\_i$ then graphs are not isomorphic. Terminate
    + if $\theta(v\_i') \neq \phi$ and $\theta(v\_i') \neq v\_i$ then graphs are not isomorphic. Terminate
* if not terminated yet, then graphs are isomorphic. Terminate and enjoy a cup of tea :-)

The running time is $O(e.log(e))$ for sorting edges and $e$ for the single pass over the edges.

The problem is not as useless as it sounds. For example, directed, distinct edge-weighted graph isomorphism can be used to find out if two given Bayesian Networks are isomorphic or not. This can be used to transfer knowledge from one domain to another.

EDIT: I took a look at some comments by the OP and it looks like he is talking about a probabilistic case. So my answer does not apply. I'll leave it here for reference.
> 3 votes

# Answer
For the unweighted case, it has recently been shown that there is a quasi-polynomial time algorithm. It is a fresh of the oven result though, you can find a sort of non-expert kind of friendly description of it here or here. And the original paper and even a video of the talk in which Lazlo Babai presented his results.

As mentioned in other answers, it is a hard problem and I have never implemented the solution myself.

Edit: I am not very familiar with Babai's new algorithm and I cannot tell if using a weighted graph is feasible.
> 0 votes

---
Tags: algorithms, complexity-theory, graph-isomorphism
---


# Question
Title: Removing epsilon transition from the grammar. What's the difference between accepting languages?
I want to remove the epsilon transition from following grammar: \begin{eqnarray} S & \rightarrow & A | B \\ A & \rightarrow & \epsilon \\ B & \rightarrow & aBa \\ B & \rightarrow & b \\ \end{eqnarray} This is the result of removing $\epsilon$ transition: \begin{eqnarray} S & \rightarrow & \epsilon | B \\ B & \rightarrow & aBa \\ B & \rightarrow & b \end{eqnarray}

My question is what's the difference between languages that accept these two grammars?

# Answer
There is no difference. Both grammars describe the same language $$L = \\{ \epsilon \\} \cup \\{ a^nba^n | \forall n \> 0\\}.$$
> 1 votes

# Answer
No difference. You can't *re-choose* the terminal $A$ after choosing it even once in your example.
> 0 votes

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


# Question
Title: How to eliminate context-free grammar's ambiguity
I want to write a CFG that generates the words over {a,b} with the same number of ocurrences of a's and b's.

I have come up with a couple of possibilties so far. I think they're correct but they're all ambiguous, and I want the grammar to be non-ambiguous, this is one option:

```
S -> aX | bY | ε

X -> bS

Y -> aS

```

This is another one:

```
S -> aSb | bSa | SS | ε

```

And another one:

```
S -> aSb | bSa | abS | baS | ε

```

These grammars can generate the word ab in at least two different ways, for example, so they are ambiguous.

Is there any "tip" or "way" to eliminate ambiguity in a context free grammar such as this one?

Thanks for your time and have a nice day! :D

# Answer
There is no general trick — indeed, given a context-free grammar, it is undecidable to determine whether it is ambiguous or not, and it is also undecidable to determine whether the language it generates is inherently ambiguous or not, see for example this answer on cstheory.

In your case, one way to go is to think of $a$ as corresponding to $\nearrow$ and of $b$ as corresponding to $\searrow$. We are interested in paths that start and end on the $x$ axis, for example $$ \begin{array}{cccccc} & \nearrow & \searrow \\ \nearrow & & & \searrow \\\hline & & & & \searrow & \nearrow \end{array} $$ We can decompose every such non-empty path into a first part, which ends the first time that the path reaches back to the $x$ axis, and the rest. If the first part starts with $\nearrow$, then it ends with a $\searrow$ and in between there is a path which never dips below where it started. We can denote such a path by $\top$. Any such path is either empty, or can be decomposed into a first part ending when the path reaches back to the initial level, followed by another $\top$ part. Putting everything together (and consider also the case in which the first part starts with $\searrow$), we obtain the following unambiguous context-free grammar (which for brevity is over $\nearrow,\searrow$): $$ \begin{align\*} & S \to \epsilon \mid \color{red}\nearrow \top \color{red}\searrow S \mid \color{red}\searrow \bot \color{red}\nearrow S \\ & \top \to \epsilon \mid \color{red}\nearrow \top \color{red}\searrow \top \\ & \bot \to \epsilon \mid \color{red} \searrow \bot \color{red}\nearrow \bot \end{align\*} $$
> 5 votes

---
Tags: context-free, formal-grammars, ambiguity
---


# Question
Title: How can I find the center character of a two-tape Turing Machine in n transitions?
The problem I have been given is to find a two-tape ND Turing Machine over {a,b,c} that only accepts odd length strings with a c in the middle position. The problem with this is that the question specifies that it must be done in n+2 transitions.

I can figure out how to do it in 1.5 * n transitions, by iterating over the tape and writing every other character to the second tape, then reversing at a space input and going back the same number of characters that are on the second tape. There are some other methods I thought of, but the lowest number of transitions I can get to is 1.5 * n which is not low enough.

This is homework so I am not looking for a full resolution or a walkthrough, but if anyone can point be in the right direction I would be very grateful as this has been irritating me for half a day now.

# Answer
> 0 votes
You explicitly try to find the middle position and then check whether it has a $c$ at that position. You can save some time by using the power of nondeterminism here. Choose *any* $c$ and check whether the number of symbols after that position matches the number before that position.

When the computation makes a wrong choice it will not accept. If there is indeed a $c$ at the middle position there is a guess that will accept.

---
Tags: formal-languages, turing-machines
---


# Question
Title: Whats the point of caching if the minimum single clock cycle time is the prorogation delay of the slowest component (fetching from DRAM)?
I know that the clock speed is determined by the slowest stage within the processor (usually fetch) because one clock cycle will take as much time as the slowest pipeline stage to ensure everything is synchronized.

So as fetching from DRAM is usually the slowest stage (for example during LDR instruction to memory which isn't in the cache) the time it takes for this should be the time for one clock cycle. So whats the point of caching?

I mean the processor has to wait anyway for the next clock cycle so even though the processor has fetched memory from cache very quickly wouldn't it have to wait anyway for the end of the clock cycle?

# Answer
You are right that the clock speed is determined by the slowest stage.

But on most architectures, it is not true that fetching (or any kind of memory access) takes one cycle. This is an illusion provided by the CPU to make things manageable.

In practice, if your CPU tries to fetch, and the operation cannot be completed in one cycle, then it will stall (on pipe-lined processor it will introduce a "bubble"), until it gets the memory content.

Thus, if your memory takes 100 cycles to read, then the CPU will stall 100 times in the fetching stage. The same applies to read(and to some extent write) stages.

This is why caching is so important: by caching, the processor can reduce the fetch/read/write delay and maintain this illusion that it takes one cycle when really it does not. Example latencies for memory read are:

* L1 cache: 1 cycle
* L2 cache: 10 cycles
* DRAM: 100 cycles

Do not take those figures literally, it is very architecture dependent. But you can see that without caching, your CPU would take 100 cycles to fetch each instruction, this is obviously unacceptable.
> 2 votes

# Answer
When some stage is quite slow, it is divided up into multiple cycles. RAM access can take \> 100 cycles. So the processor may do 100 accesses to cache in the time it takes to read one item from RAM.
> 0 votes

---
Tags: cpu-cache, cpu, cpu-pipelines, clocks, caching
---


# Question
Title: How is it possible to compare $P$ class with $BQP$?
**BQP :** (bounded-error quantum polynomial time) is the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances.

**Question :** We know that $\mathsf{P}$ and $\mathsf{NP}$ classes are defined on Turing model of computation where as $\mathsf{BQP}$ is defined over quantum model of computation. When there model of computation are different how we can say that $\mathsf{P} \subseteq \mathsf{BQP} $?

# Answer
$\mathsf{P}$ and $\mathsf{BQP}$ are classes of languages, *not algorithms*. Namely, a language belongs to $\mathsf{P}$ if there exists a Turing machine that decides it in polynomial time, and to $\mathsf{BQP}$ if there exists a quantum Turing machine that decides it in polynomial time with up to $1/3$ two-sided error.

Although their definitions invoke different computational models, both $\mathsf{P}$ and $\mathsf{BQP}$ are sets of languages, we compare them as we would compare any other pair of sets.
> 3 votes

# Answer
BQP is simply a set of languages, i.e. $\mathsf{BQP}\subseteq 2^{\Sigma^\*}$, and in that sense it can be compared with any other set of languages, such as $\mathsf{P, NP}$. It doesn't matter how those sets are defined, as we can always ask whether they are comparable under the inclusion relation.

You can ask why does it make sense to compare classes obtained from different models of computation (e.g. uniform polynomial size quantum circuits vs polynomial time Turing machines). The idea is to try and capture the notion of "efficiently computable" relative to each model. If you agree that efficiency in quantum/classic computation is captured by BQP and P, then the question "can quantum computers solve more problems efficiently" translates to whether or not $\mathsf{P\subsetneq BQP}$.
> 3 votes

---
Tags: algorithms, complexity-theory, quantum-computing
---


# Question
Title: Weakly NP-complete problems and strongly NP-complete problems
I'm still confused with the terms **Weakly NP-complete** and **strongly NP-complete**. Many people states that **weakly NP-complete problems** are the problems with time complexity growing as a polynomial in the **magnitude** of the input, while **strongly NP-complete problems** are the problems with time complexity growing as a polynomial in the **size** of the input.
Does this make **checking whether a number is prime or not** (which is always considered as polynomial-time problem) a ***weakly NP-complete problem*** since its time complexity is growing as a polynomial in the magnitude of the input but as an exponential in the size of the input?

# Answer
Many problems involve *integers*, for example in the form of integer weights. There are two common ways to encode integers:

1. Binary encoding, or more generally base B encoding for some constant B.
2. Unary encoding, in which (ignoring signs) $n \geq 0$ is encoded as $0^n1$.

A problem is weakly NP-complete if it is NP-complete when weights are encoded in binary. It is strongly NP-complete if it is NP-complete when weights are encoded in unary. For example, SUBSET SUM is weakly NP-complete but not strongly NP-complete, whereas BIN PACKING is strongly NP-complete.

Every strongly NP-complete problem is also weakly NP-complete since the reduction which changes the encoding of integers from unary to binary runs in polynomial time. The reduction in the other direction, in contrast, could run in exponential time.

Primality testing can be done in polynomial time in both unary and binary encodings, though in the latter case it's a highly non-trivial result known as the AKS primality test.
> 7 votes

---
Tags: complexity-theory
---


# Question
Title: If a CNF contains only Horn and Xor clauses, then what is the complexity of determining Satisfiability?
If a CNF contains only Horn and Xor clauses, and does not contain clauses of other types, then can its Satisfiability be determined in polynomial time?

# Answer
Hint: Using XOR clauses you can express "$x = \lnot y$", and this allows you to simulate general clauses by Horn clauses.
> 3 votes

---
Tags: complexity-theory, time-complexity, satisfiability, sat-solvers
---


# Question
Title: Why is log(n) a space-constructible function?
According to "Constructible function", Wikipedia:

> In complexity theory, a time-constructible function is a function *f* from natural numbers to natural numbers with the property that *f*(*n*) can be constructed from *n* by a Turing machine in the time of order *f*(*n*).

But $\log\left(n\right)$ doesn't map onto natural numbers but to real numbers.

Why is $\log\left(n\right)$ nevertheless a space-constructible function?

# Answer
Because when we write $\log n$ it's either in a context where it doesn't matter (e.g. Landau bounds) or with the implicit meaning of $\lfloor \log n \rfloor$ or $\lceil \log n \rceil$.

It certainly doesn't make sense to talk about constructible functions with real range, I would assume your source is talking about $\lfloor \log n \rfloor$ or $\lceil \log n \rceil$.
> 12 votes

---
Tags: time-complexity
---


# Question
Title: Given a Turing Machine M, are there infinitely many Turing machines that recognize L(M)?
I want to show this problem is decidable by describing a TM that answers the question.
I originally thought this was quite simple, and that the answer would just be a TM that outputs "yes" for any valid input of a TM *M*. My reasoning was that given any TM *M*, we can just add a new unreachable state to it and the new machine *M'* will still recognize the same language as *M*.
However, a Turing machine can only have a finite set of states so now I'm unsure if this reasoning is correct in order to produce infinitely many Turing machines and I'm unsure where to go from here.

Any help would be much appreciated.

# Answer
> 5 votes
Your attempt is fine. Yes, a Turing machine can only have a finite number of states, but you can add $i$ unreachable states for any natural number $i$ and there are infinitely many natural numbers, even though each one of them is finite.

---
Tags: turing-machines
---


# Question
Title: Does approximation ratio depend on the input size $n$?
I have started study of approximation algorithms and have confusion about the definition of *approximation algorithm*. I have two textbooks: by Cormen and the second one by Williamson.

Cormen's textbook says

> If an algorithm achieves an approximation ratio of $\rho(n)$, we call it a $\rho(n)$-approximation algorithm.

Williamson's say

> An $\alpha$-approximation algorithm for an optimization problem is a polynomial time algorithm that for all instances of the problem produces a solution whose value is within a factor of $\alpha$ of the value of an optimal solution.

So, the first definition defines approximation factor depended on $n$, while the second one does not mention of dependence of $\alpha$ on $n$.

Also I have never seen (yet at least) something like for example $(n/10)$-approximation algorithm, but seen $2$-approximation, or $3/2$-approximation.

My question: could someone clarify the precise definition of the approximation algorithm? (Wikipedia didn't help much). In particular, why do we need the dependence on $n$ if all ratios seem to be constant?

# Answer
Not all NP-hard problems admit constant factor approximation algorithms (in polynomial-time). One such well-known example is the problem of finding a maximum clique, which cannot be approximated within a factor of $n^{1-\varepsilon}$ for any $\varepsilon \> 0$ unless P = NP (see Wikipedia, though this is also mentioned in the introduction of Williamson & Shmoys).
> 4 votes

---
Tags: algorithms, approximation
---


# Question
Title: Is Timsort more efficient than merge sort and why?
I was just wondering, I think merge sort is more efficient but not sure if that is true. I know it's to do with the complexities but am still struggling to understand.

# Answer
In terms of asymptotic complexity, timsort and merge sort have the same worst-case complexity: they both make $O(n \log n)$ comparisons to sort a list of $n$ elements.

Given a particular input, a particular implementation of timsort may or may not be faster than a particular implementation of merge sort.

Timsort is designed to have a maximum overhead over merge sort, i.e. it won't be more than a certain constant factor slower than merge sort, because it's based on merge sort, and only uses other techniques for small parts of the data.

Timsort uses insertion sort for very small amounts of data; this is typically more efficient than a pure merge sort because the benefits of merge sort over insertion sort are asymptotic. Merge sort is asymptotically faster than insertion sorts, which means that there is a threshold $N$ such that if $n \ge N$ then sorting $n$ elements with merge sort is faster than with insertion sort. The numerical value of threshold depends on the specific implementations though. With typical optimized implementations, insertion sort beats merge sort for a small amount of data. Most sort routines in the real world are hybrid, using an $O(n \log n)$, divide-and-conquer technique for large amounts of data and using a different technique (usually insertion sort) when they've broken down the data into small enough pieces. Thus a properly implemented timsort is faster on average than a pure merge sort.

Timsort is furthermore optimized to deal well with real-world data. Real-world data is not randomly distributed: it's common to have sorted runs in the data to be sorted. Compared with a basic merge+insertion sort, timsort attempts to detect and make use of such runs. This adds a small overhead of checking whether parts of the data are already sorted, but with typical real-world data this saves some actual sorting work which more than compensates.
> 8 votes

---
Tags: algorithms, time-complexity, sorting, performance, mergesort
---


# Question
Title: Do Kruskal's and Prim's algorithms yield the same minimum spanning tree?
Assuming the edges are undirected, have unique weight, and no negative paths, do these algorithms produce the same Minimum Spanning Trees?

# Answer
Found this which states that if all the conditions I mentioned above are met, a graph necessarily has a unique MST. Therefore, in terms of my question, Kruskal's and Prim's algorithms necessarily produce the same result.
> 14 votes

# Answer
If the MST is unique, all algorithms will perforce produce it.

If the MST is not unique, the outputs might differ due to different node processing orders (even two distinct implementations of the same algorithm can), but the total weights will be identical. In this case, *the* MST is a misnomer.
> 7 votes

# Answer
To add upon Yves Daoust's answer, the following graph

In this graph, we have 3 nodes and 3 edges, each has the same weight. Obviously any 2 edges will form a MST for this graph. However, which two edges are chosen will depend on not only the algorithm, but the implementation of the algorithm. For instance, if I store the nodes in a list, I may visit them in a different order than if I stored the nodes in a set, even if I use the same MST algorithm from that point on.

In fact, if my implementation relies on pointer arithmetic (which some containers in some languages do), I may even pick a different MST each time I run the algorithm!
> 3 votes

---
Tags: graphs, trees, minimum-spanning-tree
---