# Question
Title: Metagame Paradox: what is wrong with this explanation?
Today I've heard about fascinating metagame paradox. I tried to come up with an explanation via Turing Machines formalization (below). Do you know what is the solution to the paradox? (the post content: definition - proposed solution - conclusion)

Something is a game iff:

```
G1. Two players
G2. Players alternate
G3. The game finally ends.

```

The metagame is:

```
M1. First player picks a game
M2. Second player starts the game
M3. The winner is the winner of the game at step 2.

```

Example of a metagame:

```
1) I pick tic-tac-toe
2) OK, I put X here ..
.. so they play ..
3) .. and let player 2 wins in the tic-tac-toe => player 2 wins the metagame.

```

**Paradox: Is metagame a game?**

If metagame is a game, then at point (M1) both players can always pick a metagame, so the metagame will never end =\> (G3) is violated =\> metagame is not a game =\> contradiction.

(also contradiction for case "metagame is not a game" -- metagame will satisfy the definition of a game)

(see also http://www.math.cornell.edu/~mec/2006-2007/Games/hypergame.html)

**What is the solution to the paradox?**

*UPDATE:* You may want to skip this explanation and go directly to D.W. answer.

I came up with the following explanation:

Lets formalize the problem using Turing Machines notations. Let a game be a finite binary string that describes "somehow" game rules. Let a game simulator be a non-deterministic TM that reads a description from the input (without any sanity checks, so the TM doesn't know if the game finally ends), and then makes non-deterministic moves for the first and second player. Here we assume (A1) that the game-simulator can decide valid next moves.

Now have a look at the description of a meta-game:

```
M1. First player picks a game

```

This sentence means that we can "pick a game", i.e. in the definition we assume (A2) that whether an arbitrarily binary string is a game (satisfies G1,G2,G3) is decidable. (see also note (n1) )

M2 and M3 look decidable.

So, **my suggestion is that metagame is not "defined properly"**, since its definition assumes the existence of a decider "if a given binary string is a game". And then we derive a contradiction, so this assumption is wrong.

**Does it make sense? Is this related with other explanations of the paradox?** (intuitive answers would be great!)

Notes:

1. Assuming "whether an arbitrarily binary string is a game" may be too much. But we need some computable procedure "pick a game" and one that came into mind is "generate random string, check if it is a game".
2. I don't know what is a formal word for "not defined properly"
3. Assumption A1 may also be undecidable, but I believe it should not change the argument..

# Answer
> 4 votes
The flaw is that your definition of "game" is deficient and does not correspond to our intuition. We also need a restriction on the number of moves that are possible at any position in the game. It doesn't really have anything to do about computability, so much as about the notion of what it means for a game to be finite.

---

Usually we define a game as something where at each step there are only finitely many moves that can be played, and where the game is guaranteed to end after finitely many moves (there is no infinite sequence of moves in the game). You forgot to specify the "at each position, there are only finitely many moves possible from that position" in your definition of a game.

If you add that to the definition, then you'll find that the metagame does not meet the definition: the metagame is not a game. In particular, there are infinitely many possible games, so at the beginning of your metagame, there are infinitely many possible moves -- thus the metagame does not qualify as a game. There is no paradox.

---

You *could* have an alternative definition of a game where you say that at each step the number of moves is either finite or countably infinite. This is a bit different from what our intuition would suggest, but let's explore the consequences of defining a game this way.

In particular, the set of all games would now be uncountably infinite.

As a result, the metagame is still not a game: at the beginning of your metagame, there are uncountably infinitely many possible moves -- so does not qualify as a game.

In particular, "pick a game" is not meaningful: Player 1 has to select a game and describe it to Player 2, but there are uncountably infinitely many possible games, so Player 1 cannot describe his choice in any finite amount of time. In particular, you cannot specify a game with a finite string (more precisely: no matter what candidate encoding of games you come up with, there will exist some games that cannot be specified by any finite string). The description of the game is an infinite-length string.

If you like to think of it intuitively: in this case it wouldn't really be fair to think of the metagame as "finite" (even though it only lasts for a finite number of moves, if the first move takes infinitely long to complete, the metagame cannot be considered finite).

In any case, if you define a game this way, there is still no paradox.

(Why is the set of games uncountably infinite, if this is how we defined a game? Well, I'll show an injective map $f$ that maps from a real number $x \in \[0,1\]$ to a game $G\_x$. In the first move of $G\_x$, player 1 chooses a natural number $n \in \mathbb{N}$. After that, there are $n$ more moves, then the game ends. At the $i+1$th move (for $1 \le i \le n$), there are $x\_i$ different moves available to the player whose turn it is to move, where $x\_i$ denotes the $i$th digit after the decimal point in the decimal expansion of $x$. Notice that $G\_x$ qualifies as a game: there are two players, the players alternate, there are finitely or countably infinitely many moves at each possible position of the game, and the game is guaranteed to end after finitely many steps -- there is no infinite sequence of valid moves. But the set $\[0,1\]$ of real numbers is uncountably infinite, and we have an injective map from an uncountably infinite set to a subset of the set of games. Therefore, the set of all games is uncountably infinite, under this definition.)

---

Finally, the last alternative would be to define "game" so there is no restriction on the number of possible moves at each position.

However, this definition of a "game" would no longer correspond to our usual intuition for what a game should involve. In particular, it may not be possible for a player to describe his/her move to the other player in any finite amount of time (since he/she may be choosing from among uncountably infinitely many possibilities). That just ain't right. In particular, such a process can't reasonably be considered finite: it would not complete in any finite amount of time.

---

Intuitively, why does it make sense that our definition of game ought to restrict the number of possible moves at each position to be finite, or at most countably infinite? Because we need the player to be able to select a move *and describe it* to the other player. If there is no finite encoding of the set of possible moves (at a given position), then the player whose turn it is to move has no way to describe the move he chose to his opponent. If there *is* a finite encoding of the set of possible moves (at each possible position), then the number of possible moves must always be finite or countably infinite, by the definition of countability.

# Answer
> 2 votes
This is a set theory paradox, rather than a computability paradox. Let us define: a game is any set $X$. The initial game state of game $X$ is the set $X$ itself; taking a move means moving from a set $Y$ (the current game state) to one of its elements; if the current game state is the empty set, then the game ends (and the player whose turn is to move loses). The set $X$ is well-founded, if it doesn't have an infinite downwards chain of the $\in$ relation - there doesn't exist such an infinite sequence of sets $A$, $B$, $C$, $D$, ... that $B \in A$, $C \in B$, $D \in C$, ... and so on, where $A=X$. (This means that the game is guaranteed to end in finitely many moves.) From axiom of regularity it follows that every set is well-founded; so let's assume that we are working in ZF with the axiom of regularity omitted.

The question whether or not metagame is a finite game becomes: is the set of all well-founded sets itself well-founded? First, observe that a well-founded set can't contain itself. (Otherwise, we could have picked an infinite sequence $X$, $X$, $X$, ...) Now a set which only contains well-founded sets is itself well-founded. (We see that every downwards chain of all the elements of $A$ is finite; the downwards chains of the set $A$ itself are just one element longer, with set $A$ added to its front. We could have run in trouble if the set $A$ contained itself as an element - but in this case the set $A$ is not well-founded and so it doesn't only contain well-founded sets.) Now to the set of all well-founded sets: If the set doesn't contain itself, then it is well-founded, and therefore it isn't the set of all well founded sets (it misses one well-founded set, namely itself). On the other hand, if the set contains itself, then it is not well-founded, and therefore it contains a set which is not well-founded. Either way, we have reached a paradox, so the conclusion is that the "metagame" (set of all well-founded sets) cannot exist - the class of all well-founded sets is a proper class.

(We can prove the result from the other side: Again, observe that 1) a well-founded set can't contain itself; and 2) a set is well-founded if and only if all its elements are well-founded. But this means that any well-founded set necessarily doesn't contain some well-founded set - namely, itself - and therefore there can't exist a set of all well-founded sets.)

# Answer
> 1 votes
Let me to rephrase the answer by D.W. and give my understanding (all credit goes to D.W.!)

We need to formalize what is a game, and D.W. showed different possibilities. All formalizations lead to "meta-game is not a game" (and no paradox!).

One of the possibilities is:

```
Smth is a game iff:
1) two players
2) alternate
3) in each position in the game there is a countable number of possible moves
4) game ends (infinite game-play is forbidden).

```

We need (3) otherwise player1 will not be able to communicate its answer to player2 (the answer becomes an infinite string).

Even for this definition D.W. shows that meta-game is not a game (and no paradox), because in meta-game item (3) is violated. See D.W. answer for explanation.

In the above definition a game description can be an infinite string (and is indeed, see D.W. answer). One of "natural" requirements on the game is to require:

```
5) a game description should be a finite string

```

Is there a paradox now? Not really: now comes into play the meta-game item which says `pick a game`. How to implement it? If meta-game stores all possible games inside and picks one of them, then meta-game description is not finite and so it is not a game (and no paradox). If assume that meta-game just generates some string and then passes it to decider that says 'yes, it is a game, you can pick it', then we get contradictions (just like in paradox), and so the assumption is wrong -- there is no such decider.

---
Tags: computability, turing-machines, game-theory
---


# Question
Title: How do you prove a heuristic is admissible?
How does one prove that a suggested heuristic is admissible? Is this even possible?

For Example: Let's say I have the game Free Cell.
Rules: https://en.wikipedia.org/wiki/FreeCell

How can I prove that the number of cards not in the foundation plus every out of order card is an admissible heuristic?

# Answer
Proving a heuristic is admissible usually means proving two things:

1. it follows the triangular inequality principle
2. given the same preconditions, the heuristic never overestimates the actual solution
> 2 votes

# Answer
In general, it is usually the other way round, i.e., one applies one technique which ensures that the resulting heuristic will be admissible instead of devising an idea and then proving it is admissible. Nonetheless, the question is pretty interesting, but let me please start by introducing the general idea.

There are several techniques to derive admissible heuristics. As mentioned by Emanuele Giona this implies that the heuristic function will never overestimate the cost of an optimal solution from the current node. Thus, all techniques rely in one way or another on the concept of *relaxation*. A problem is said to be *relaxed* if it makes it easier to compute an optimal solution even if the resulting problem is not like the original one. For example, in the sliding-tile puzzle you might relax the condition that the blank tile can only move to adjacent locations and thus, that it can be swapped with any tile on the board; in the Towers of Hanoi you could relax the only operator in the domain to say that it is possible for example to take any disc in any peg and not necessarily the one on the top. Other relaxations are possible. For example, in an instance of an arbitrary cost domain, you could relax the cost of the operators to say that all of them cost one unit (and thus, the cost of the relaxed optimal solution would be its length).

The first idea to derive heuristic functions was proposed by Judea Pearl at the end of the 80s and his technique is known as *Constraint Relaxation* as it relaxes the constraints of the operators. If you want, for example, to relax the cost of the operators, then some heuristics are obtained by solving Linear Programming Tasks. Other slightly more involved ideas are abstractions which map your problem into a relaxed instance where some constants of your problem have been ignored (for example, in the Rubik's Cube by saying that all corner qubies are indistinguishable among them). Examples of abstractions are Pattern Databases and Merge-and-Shrink heuristics ---the latter proven to be a super-class of the former.

So far, if you are facing a new problem, the natural approach consists of applying any or some of these techniques. They all guarantee by design that the resulting heuristic function is necessarily admissible. There are interesting theoretical properties that prove this, e.g., while applying an abstraction it just suffices to prove that the abstraction performed is a *homomorphism*.

Now, to go the other way round (i.e., from an intuition of a possibly admissible heuristic function to prove it is indeed admissible) my suggestion would be to prove that applying any of this techniques, the devised heuristic function results. In your specific case, the number of cards not in the foundation is clearly an admissible heuristic function that results from *Constraint Relaxation* as it is necessary to reveal those cards in order to finish the game. I do not know very well the game of FreeCell and so, I beg your pardon for not delving deeper into your possible heuristic but this is, in general, the way of thinking.

Finally, I'd like to highlight that there are even domain-independent admissible heuristics (obtained automatically with the usage of any of the previous techniques) for the specific case of the game of FreeCell as this is one of the standard domains in the International Planning Competitions.

Hope this helps,
> 1 votes

---
Tags: artificial-intelligence, heuristics
---


# Question
Title: Log-Space Reduction $USTCON\le_L CO-2Col$
I want to show that $USTCON\le\_L CO-2Col$ (Log-Space reduction)

$USTCON$ The $s-t$ connectivity problem for **undirected** graphs is called $USTCON$.

Input: An undirected graph $G=(V,E)$, $s,t \in V$. Output: 1 iff $s$ is connected to $t$ in $G$.

$CO-2Col$ A graph is $2$-colorable if there is a way to color the vertices of $G$ with $2$ colors, such that for every edge the two vertices on the edge are colored differently. $CO-2Col$ is the following problem:

Input: An undirected graph $G$. Output: 1 iff $G$ is NOT $2$-colorable.

I know this can be solved by simply using the $USTCON$ decision algorithm and then output a bipartite or non-bipartite graph accordingly. But is there any other reduction that actually changes the input graph?

# Answer
> 3 votes
Let USTCON2 be the following problem: given a graph $G$ and two vertices $s,t$, decide whether there is a walk from $s$ to $t$ of even length. Let us show first that USTCON2 reduces to co2COL.

Given a graph $G = (V,E)$ and two vertices $s,t$, construct a new graph whose vertex set consists of two copies of $V$. For every $(a,b) \in E$, connect $a$ in the first copy to $b$ in the second copy, and $a$ in the second copy to $b$ in the first copy. So far the graph is bipartite. Now connect $s$ and $t$ in the first copy. The new graph is bipartite iff there is no path of even length from $s$ to $t$ in the original graph.

Now let us reduce USTCON to USTCON2. Given a graph $G = (V,E)$ and two vertices $s,t$, add two new vertices $x,y$, and edges $(s,x),(x,y),(y,s)$. There is a walk from $s$ to $t$ in the original graph iff there is a walk of even length from $s$ to $t$ in the new graph.

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


# Question
Title: Can such a Turing-recognizable language exist?
Suppose $\Sigma = \\{a,b\\}$. Is the following claim correct?

> There exists a Turing-recognizable language $L \subseteq \Sigma^\*$ such as its complement is not Turing-recognizable, and for all $n \in \mathbb{N}$ it contains exactly $n$ strings of length $n$.

I'm kind of lost here. Any help would be appreciated.

# Answer
If $L$ is a recognizable language that contains $f(n)$ strings of length $n$, where $f$ is computable, then $L$ is in fact computable. Given a string $x$ of length $n$, calculate $f(n)$, and then run a recognizer for $L$ on all strings of length $n$. Eventually you will find all $f(n)$ strings recognized by $L$. If $x$ is one of them, accept, and otherwise, reject.
> 4 votes

---
Tags: turing-machines
---


# Question
Title: When and what must be present on the left-hand side of the turnstile in metalogics?
Let me show the problem on an example...

An actual task from one of the former exams:

> Consider a simple functional language:
>
> $$e::= x|n|e\_1e\_2|\lambda x.e$$
>
> With typing rules:
>
> $$\tau ::= \mathtt{int} | \mathtt{foo} | \tau\_1 \rightarrow \tau\_2$$
>
> $$\Gamma \vdash n : \mathtt{int}$$
>
> $$\Gamma (x : \tau) \vdash x : \tau$$
>
> $$\begin{array} {c} \Gamma(x : \tau) \vdash e : \rho \\ \hline \Gamma \vdash \lambda x.e : \tau \rightarrow \rho\end{array}$$
>
> $$\begin{array}{c} \Gamma\vdash e\_1:\tau\rightarrow \rho\quad\Gamma\vdash e\_2:\tau \\ \hline \Gamma\vdash e\_1e\_2 : \rho\end{array}$$
>
> $$\begin{array}{c}\Gamma\vdash e:\tau \\ \hline \Gamma\vdash e: \mathtt{foo}\end{array}$$
>
> Where the environment $\Gamma$ is a partial function from the set of variables into the set of types and $\Gamma(x:t)$ denotes an environment that assignts the type $t$ to the variable $x$ and works like $\Gamma$ for all other variables.
>
> Derive types for the following expressions:
>
> *(omitted for brevity)*
>
> **Example**: Type derivation for $\lambda x.\lambda y.x$:
>
> $$\begin{array}{c}x:\alpha,\\;y:\beta\vdash x:\alpha \\ \hline x:\alpha\vdash \lambda y.x:\beta\rightarrow\alpha \\ \hline \vdash\lambda x.\lambda y. x : \alpha \rightarrow (\beta\rightarrow\alpha) \end{array}$$

It is this example that perplexes me. Why is it necessary to put $x:\alpha$ on the left-hand side of $\vdash$ in the second step of the derivation? My thinking is that $\lambda x.y : \beta\rightarrow \alpha$ results from both $x:\alpha$ **and** $y:\beta$ so there's no reason to put $x:\alpha$ on the lhs of $\vdash$ but not $y:\beta$.

But $\begin{array}{c}x:\alpha,\\;y:\beta\vdash x:\alpha,\\; y:\beta \\ \hline x:\alpha,\\; y:\beta\vdash \lambda y.x:\beta\rightarrow\alpha \end{array}$ is a tautology that brings in nothing, so we should instead simplify this to $\begin{array}{c}x:\alpha,\\;y:\beta \\ \hline \vdash \lambda y.x:\beta\rightarrow\alpha \end{array}$. Note that this is precisely what the third step of derivation seems to be doing: $\begin{array}{c} x:\alpha\vdash \lambda y.x:\beta\rightarrow\alpha \\ \hline \vdash\lambda x.\lambda y. x : \alpha \rightarrow (\beta\rightarrow\alpha) \end{array}$ They simply put nothing on the left-hand side of the $\vdash$.

What am I missing here? Is this related to the form of the axiom that seems to be used here - $\begin{array} {c} \Gamma(x : \tau) \vdash e : \rho \\ \hline \Gamma \vdash \lambda x.e : \tau \rightarrow \rho\end{array}$ \- where the environment used above the vertical line contains the assignment $x:\tau$ while the environment used below the vertical line is devoid of this assignment? Which is why in $x:\alpha\vdash \lambda y.x:\beta\rightarrow\alpha$ the assignment $x:\alpha$ must be present before the $\vdash$, but the assignment $y:\beta$ must not? Is my reasoning correct? But if it is, then why does the third step seem to differ and is of the form $\vdash\lambda x.\lambda y. x : \alpha \rightarrow (\beta\rightarrow\alpha)$ and not $\lambda y.x : \beta\rightarrow\alpha \vdash\lambda x.\lambda y. x : \alpha \rightarrow (\beta\rightarrow\alpha)$?

Or am I splitting hairs here? But my thinking is that I'm not certain what degree of accuratness is required by this professor so I wouldn't like to loose points on something of this sort... Could you clear my confusion?

# Answer
Perhaps what you're missing (although you seem to suspect) is that the left hand side of the $⊢$ is not just for specifying what types variables have. In fact, as you've noted, it doesn't necessarily have all (or only) the variables on the right hand side (although in this situation it does only have variables, not things like $λy.x : α→β$).

What it's doing is keeping track of what are sometimes called the "free variables" on the right hand side, along with their specified types. The idea is essentially that there are actually no free variables in this formalism; variables are either bound by a $λ$ or in the context $Γ$. The lambda introduction rule:

$$\begin{array}{c}Γ(x:τ) ⊢ e : ρ \\ \hline Γ ⊢ λx.e : τ → ρ\end{array}$$

moves a variable from being bound in the context to being bound by a lambda. In some presentations this might even be written $λx:τ.e$ to still be explicit about what type $x$ has, but this is not really necessary when working with a derivation where the type is already recorded in the judgment (and there are other situations as well).

Of course, variables can go in the context even if they *don't* occur on the right hand side, like $y$ in your example. This allowed writing a constant function that doesn't actually use its argument.

One way to think about this is to read the tree bottom to top. We want to verify that $λx.λy.x$ has type $α→β→α$. The way we do this is to start in the empty context, and move upward. We use the lambda introduction rule to push lambda-bound variables into the context with an appropriate type, and eventually verify that $$x:α,y:β⊢x:α$$ holds. This is maybe more obvious if the variable rule has a line above it, allowing you to create a completed tree:

$$\begin{array}{c}\\ \hline x:α,y:β⊢x:α \\ \hline x:α ⊢ λy.x : β→α \\ \hline ⊢ λx.λy.x : α→β→α \end{array} $$

The root of the tree is our goal at the bottom, and the leaves at the top are all empty lines. $Γ$ is the local context in which we are verifying the inner parts of the lambda term, and its content is actually motivated by wanting to move under the lambda and verify the type of its body; it contains the variables and their types that have been brought into scope in that process.
> 1 votes

---
Tags: formal-languages, notation, derivation
---


# Question
Title: Is $ L = \{ a^n\ |\ a^n \not\in L_n \} $ Turing recognizable (recursively enumerable)?
> Say $ \Sigma = \\{a\\} $, $M\_1, M\_2, ... $ is an enumeration of all TMs that recognize languages over $\Sigma$ and $L\_1, L\_2, ... $ are respectively the languages that are recognized by those TMs. We construct the language $ L = \\{ a^n\ |\ a^n \not\in L\_n \\} $. Is $L$ Turing recognizable (recursively enumerable)?

My thought process is this: Say $L$ is recognizable. Then given a string $a^k$, we find $L\_k$ based on the enumeration of $L\_i$'s, and then we run $M\_k$ on input $a^k$ to find if indeed $a^k \not\in L\_k$. We must accept if $a^k \not\in L\_k$, but $M\_k$ is not guaranteed to halt in that case. So $L$ is not recognizable.

Now I have 2 questions: 1) Is my thought correct?, and 2) How can I make this more formal?

# Answer
Your thought falls short of a rigorous proof. It can hardly be considered correct intuition since it does not use the condition that each Turing machine is labelled with some number, although it does use the condition that each $k$ corresponds to a Turing machine. Your "proof" would work equally well if the condition "$M\_1,M\_2$,... is an enumeration of all TMs" is replaced by "$M\_1,M\_2$,... is an enumeration of some TMs"

---

Here is a formal proof.

Suppose $L$ is recognizable. Then by definition, $L$ is the language accepted by some Turing machine $M\_k$ for some $k$. Consider $a^k$.

* If $a^k$ is not in the language accepted by $M\_k$, then by definition of $L$, $a^k\in L$. By the definition of $M\_k$, $a^k$ is accepted by $M\_k$, which is a contradiction.
* If $a^k$ is in the language accepted by $M\_k$, then by definition of $L$, $a^k\not\in L$. By the definition of $M\_k$, $a^k$ is not accepted by $M\_k$, which is a contradiction.

Since we always get a contradiction, our assumption $L$ is recognizable must be wrong.

---

Here is an easier proof, as presented in your comment.

For all $n$, $L\not=L\_n$, since $a^n\in L$ $\Leftrightarrow$ $a^n\not\in L\_n$, i.e, the membership of $a^n$ in $L$ and the membership of $a^n$ in $L\_n$ is different. Since $L\_n$ for all $n$ enumerates over all recognizable languages, $L$ is not recognizable.

In fact, the construction of $L$ uses the classic technique to construct a non-member of a given set, the diagonal argument that was discovered/created by the great mathematician Georg Cantor. "It has been used in a wide range of proofs, including the first of Gödel's incompleteness theorems and Turing's answer to the Entscheidungsproblem. Diagonalization arguments are often also the source of contradictions like Russell's paradox and Richard's paradox." The proof of the undecidability of the halting problem can be considered as an application of the diagonal argument as well.
> 2 votes

---
Tags: turing-machines, undecidability, semi-decidability
---


title: Why are reversible gates not used?

text:
# Question
Title: Why are reversible gates not used?
I was reading the book "The singularity is near" written by Kurzweil and he mentioned the reversible gates like for example the Fredkin gate. The advantage using such gates is that we could get rid of the thermal waste related to computation where bits just disappear into heat, and computation won't need any energy input. Those assumptions make these gates sound like a miracle solution. So the question is what technical hurdles are still preventing their large scale usage.

I also think it is a shame that I never heard about those gates in my electrical engineering bachelor and master studies at a top German university...

# Answer
> 20 votes
I am by no means an expert on this topic, but just from casually reading Wikipedia:

> it relies on the motion of spherical billiard balls in a friction-free environment made of buffers against which the balls bounce perfectly

... this sounds very realistic.

Nobody has actually figured out how to actually make such gates yet, they're merely of theoretical interest. That might explain why you've never heard of them since engineering usually deals with practice.

The premise of Reversible Computing is that when a bit disappears, some amount of heat is generated. By using reversible gates, no bits ever appear or disappear so supposedly computation could be much more efficient with reversible gates.

The theoretical limit Reversible Computing claims to get around is that erasing 1 bit of information generates at least $kT\ln 2$ energy in heat. For a computer running at a toasty $60\\,{}^\circ\mathrm{C}$ with $10^9$ transistors each making bits disappear at a rate of $5\\,\mathrm{GHz}$, that corresponds to $16\\,\mathrm{mW}$ of heat generation. That only accounts for a tiny proportion ($1/10000$) of a computer's energy usage.

Our current-day computers are not limited by heat generation associated with bits disappearing. They are limited by the inherent inefficiency in moving electrons around on tiny copper traces.

# Answer
> 18 votes
The problem with practical reversible gates (gates that can (and have been) fabricated in silicon) is that the actual energy savings are linearly proportional to how *slowly* you run them.

I know that Tom Knight's research group at MIT fabricated a small adiabatic processor in the late 1990s. The practical logic family they developed is called split-level charge recovery logic, and can be implemented using standard (CMOS) fabrication techniques. I believe the work has been continued by Michael P Frank at Florida State University. An example of the work in Tom Knight's group is the following master's thesis (which has a pretty decent section on related work through the early 1990s.) Vieri, C J: *Pendulum: A Reversible Computer Architecture*, Master's Thesis, MIT EECS dept, 1995.

Reversible circuits need to be *adiabatic* (there can't be heat exchanges between the circuit and its environment), which means that they must be in equilibrium at all times. For any process that needs to change something you can only approximate equilibrium by making the change happen as slowly as possible.

If I remember my thermodynamics correctly, you can make the *energy* of a reversible computation arbitrarily small, but the minimum *action* (energy times time) must be a small constant.

# Answer
> 10 votes
The largest hurdle preventing their large scale use is the same as for asynchronous circuits and pretty much any other non-standard circuit design: **Moore's law.**

Moore's law has become something of a self fulfilling prophecy; as seen by the Tick Tock Release Schedule, chip manufacturers see fulfilling Moore's law as a challenge. Because of the need to fulfill Moore's law, we have gotten more and more adept at decreasing the size of chips by advancing lithography (and often by using cheats, like multipatterning).

What does all of this have to do with reversible gates? As foundries race to release newer and smaller transistor sizes, companies that want to print new chips see an easy path towards increasing speed by simply adding more cache and reworking their conventional designs to better use that cache.

The killer of *better* isn't technological hurtles; it's the success of *good enough*.

# Answer
> 4 votes
Fredkin gates are realistic and many have been implemented. There are entire FPGA boards strictly using reversible logic gates that are implemented using Fredkin and Toffoli gate as their LUs.

There are several problems effecting their widespread usage in computer architecture. There are several "advertised" advantages to fredkin gates that do not necessarily work as expected in real circuits. The energy savings of reversible logic gates is due mostly to the fact that they do not require entropy be created when an operation is performed. As stated by Tom van der Zanden, this is the primary reason why reversible logic can be much more efficient. Why this is not the case in real circuits:

1. Currently transistor technology is more what limits computer speed and power consumption, and unfortunately, more transistors are required to make a fredkin gate as opposed to traditional nand or nor gates. This means fredkin gates waste more energy through transistor leakage and require more space on silicon (which means more expensive). This alone is enough to justify using nand/nor over fredkin gates
2. Since the primary form of power loss if from transistors and not entropy creation due to the actual computation, you still need to run power and ground lines to fredkin gates to compensate for this power loss. These large busses are fan-in busses, which also take up a lot of space on silicon. Since there are more transistors in a fredkin gate, this leads to more fan-in, and thus more wasted space on silicon.
3. Although we have reversible fredkin gates, these are built up from non-reversible devices (transistors). This means some of the energy gains are not realized with current gate technology (outside of quantum circuits).
4. Size and speed are related on silicon, the closer together things are, generally the faster you can make them. Since fredkin gates use more transistors and have more connections for power, etc, they tend to be significantly slower.
5. The power consumption advantages and speed advantages are only realized when bits are successfully reused. Most of the algorithms we have are horribly non-conservative. You can see this by researching an implementation of a full adder or shift register using fredkin gates. Since reversible logic does not allow logical fan-in and fan-out, this leads to a lot of bit calculation that does not end up being used to achieve a useful operation. Something such as adding two 8-bit numbers will produce 9-bits or useful information (8-bit result, 1 carry bit), but will require an input bus of many 1 and 0 constants and produce many junk data output bits. Since you have a wider bus, this leads to an even further spread out circuit on silicon.
6. Additionally, The junk bits must be dumped by the processor, and thus would lead to energy loss anyways because they are never used

Summary: Fredkin gates produce a lot of waste computation when implementing real algorithms. waste computation = wasted energy. Because of this, bus sizes increase which spreads things out and slows things down. Additionally, the physical implementation of fredkin gates is the greater concern for current technology. The current implementation spreads things out more by requiring more power and ground lines to compensate for losses in the circuit (which is a much greater concern for energy loss) and uses much more real-estate on silicon (which is a much greater concern for speed)

I realize this is an old thread, but many of the answers focus on the fact that transistors are inefficient. My goal is to show our algorithms are also inefficient and do not handle reversible computing well. I am a computer engineer that enjoys researching reversible and quantum computing

# Answer
> 3 votes
Useful computing devices require feedback, which makes it possible to have one circuit element perform an essentially-unlimited number of sequential computations. Usable feedback circuits must contain sections whose total number of inputs (counting both the ones that are fed back from outputs and those that aren't) exceeds the number of outputs which are fed back to input (the only way the number of inputs wouldn't exceed the number of fed-back outputs would be if the circuits didn't respond in any way to outside stimuli). Since perfectly reversible-logic functions can't have more inputs than outputs, it's not possible to construct from them any of the feedback structures required to perform any non-trivial computing tasks *repeatedly*. Note that with the CMOS technology used in today's computers, feedback is required to ensure that results reported by computations in different parts of a circuit are made available simultaneously to other parts, since if they weren't the relative timing with which the signals arrive would constitute "information" which could not be perfectly passed downstream; other technologies might make it possible to have many gates propagate signals at precisely the same rate while retaining reversibility, but I know of no practical technology for that.

Note that from a CS perspective, it's trivial to make a computing process reversible if one has initially-empty storage medium whose size is essentially proportional to the number of steps times the amount of state that could change in each step. This claim does not contradict the claim of the previous paragraph, since storage proportional to the number of steps will require circuitry proportional to the number of steps, which will imply circuitry proportional to the amount that would be required if all feedback were eliminated.

If one is allowed to have outputs which are ignored if, given proper input conditions, they will never go high, then it might be possible to design a system that would, in theory, benefit from reversible logic. For example, if one had an algorithm that operated on a 256-word chunk of RAM and one wanted to use a "reversible-logic CPU" that performed 1,000,000 operations per second and each operation updated either a register, the program counter, or one word of RAM, one could use a "reversible CPU" which would:

* ran a bunch of instructions and, on each, send whatever was overwritten to a LIFO buffer
* after a bunch of instructions had executed, copy the RAM into an initially-blank "forwarding" buffer
* using the values in the LIFO, run all the computations in reverse
* overwrite the contents of the main RAM with the forwarding buffer, which would be erased in the process.

The above recipe could be repeated any number of times to run the algorithm for an arbitrary number of steps; only the last step of the recipe wouldn't be reversible. The amount of energy spent per algorithmic step in non-reversible operations would be inversely proportional to the size of the LIFO, and thus could be made arbitrarily small if one were building to build a large enough LIFO.

In order for that ability to translate into any sort of energy savings, however, it would be necessary to have a LIFO which would store energy when information was put in, and usefully return that energy when it was read out. Further, the LIFO would have to be large enough to hold the state data for enough steps that the any energy cost of using it was less than the amount of energy it usefully saved. Given that the amount of energy lost in the storage and retrieval of N bytes from any practical FIFO is unlikely to be O(1), it's unclear that increasing N will meaningfully reduce energy consumption.

# Answer
> 3 votes
Practical applied reversible computing is an active area of research and is likely to become more prominent in the future. Most of quantum computing can be seen to be attempting to create reversible qubit gates and it's very hard experimentally to match the theoretical properties of the QM formalism, but steady progress is being made.

Another basic point is that anytime energy dissipation is decreased on a chip, it's essentially moving the gate system to "more reversible", and lower-energy chip dissipation has been a high priority for a long time now in mobile computing (representing a sort of industry-wide paradigm shift). For decades chip performance gains (similar to Moore's law) came about by being somewhat "relaxed" or even "sloppy" with energy dissipation but that reached a point of diminishing returns a few years ago. The leading worldwide chip manufacturer Intel is attempting to pivot into lower-power chips to compete with Arm which has an advantage after never building anything but.

There is some possibly breakthrough recent research using superconducting technology (June 2014), and there are other active research projects in this area.

See e.g. Reversible logic gate using adiabatic superconducting devices / Takeuchi, Yamanashi, Yoshikawa, Nature:

> Reversible computing has been studied since Rolf Landauer advanced the argument that has come to be known as Landauer's principle. This principle states that there is no minimum energy dissipation for logic operations in reversible computing, because it is not accompanied by reductions in information entropy. However, until now, no practical reversible logic gates have been demonstrated. One of the problems is that reversible logic gates must be built by using extremely energy-efficient logic devices. Another difficulty is that reversible logic gates must be both logically and physically reversible. Here we propose the first practical reversible logic gate using adiabatic superconducting devices and experimentally demonstrate the logical and physical reversibility of the gate. Additionally, we estimate the energy dissipation of the gate, and discuss the minimum energy dissipation required for reversible logic operations. It is expected that the results of this study will enable reversible computing to move from the theoretical stage into practical usage.

---
Tags: computer-architecture
---


# Question
Title: Is $\bigcup_{c \ge 1} \mathsf{DTime}(2^{cn})$ closed under polynomial reduction?
It's well known $EXP$ is closed under polynomial reduction. It means $\bigcup\_{c \ge 1} \mathsf{DTime}(2^{c^{n}})$ is closed under polynomial reduction. But what about $\bigcup\_{c \ge 1} \mathsf{DTime}(2^{cn})$? Is it also closed under polynomial reduction?

# Answer
No, this would contradict the time hierarchy theorem. Note that any language in $\mathsf{EXP}$ is polynomial time reducible to some language in $\mathsf{E}$ by padding. Suppose $L\in \mathsf{DTIME\big(2^{n^c}\big)}$, then consider $L'=\big\\{x0^{|x|^c}\big|x \in L\big\\}$. Obviously $L'\in \mathsf{E}$ and $L\le\_p L'$, thus if $\mathsf{E}$ is closed under polynomial time reductions we have $L\in\mathsf{E}$ and consequently $\mathsf{E=EXP}$.
> 2 votes

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


title: Uncomputably coded model of computation

text:
# Question
Title: Uncomputably coded model of computation
There are many different but equivalent models of computation. I assume their equivalence is shown by coding input of one model to the input of the other model and making an argument why should there exists the same algorithm that would solve the problem on that model (e.g. emulation).

I was wondering, if there's a model of computation, that is equivalent to turing machines (the coding translation being just general bijection), but encoding standard input to its input would be an uncomputable problem. In essence making it an model of computation that is cut off from convetional models by it's coding being uncomputable. That would be first part of my question. I

For the second part, if such model exists, let's call it $S$, can you find other models of computations $S\_0, S\_1, \dots$, such that conversion between $S$ and $S\_i$ would be computable by both $S$ and $S\_i$? If $T, T\_0, T\_1,\dots$ were models of turing machine, and other conventional computation models, would $\mathcal{T}=\\{T,T\_0,T\_1,\dots\\}$ and $\mathcal{S}=\\{S,S\_0,S\_1,\dots\\}$ be two seperate "islands" of computation? Both equivalent, but no member of either family would be able to encode it's inputs to the other family? Or maybe only $\mathcal{S}$ would be able to, making some sort of partial order on such families of models of computation, like $\mathcal{T}\<\mathcal{S}$?

note: I'm not sure if it's formal to talk about a model of computation as a mathematcical object, I meant most of the last paragraph mostly informally, but maybe it would suffice to just take set of all instances of such model of computation. Like $T=\\{\text{all Turing machines}\\}$, $T\_0=\\{\text{all Lambda expressions}\\}$ and such .

# Answer
> 1 votes
Consider a standard coding of Turing machine $T\_0$, $T\_1$, $T\_2$, ... Let $b : \mathbb{N} \to \mathbb{N}$ be a *non-computable* bijection. Define a new coding of Turing machines $T'\_n = T\_{b(n)}$. Clearly, the encoding $T'$ can do everything that Turing machines can do (whatever you do with $T$ you can do with $T'$ by composing with $b$ and its inverse), but it is not equivalent to $T$ by a computable bijection (or else $b$ would be computable).

---
Tags: turing-machines, computability, lambda-calculus, computation-models, turing-completeness
---


title: Array subset division with equal sums

text:
# Question
Title: Array subset division with equal sums
Today I stumbled upon a problem which looked like the partition problem but certainly is different.

Given array of positive integers, guaranteed to not be divisible into two continious subsets of equal sum, remove a ceratin continious subset to form two subsets of equal sum.

**Example:**

* Array: 7 5 9 1 3 9 6
* Remove elements 9 and 1 to form array 7 5 3 9 6 that is divisible into two subarrays of equal sum {7,5,3} and {9,6}

**Another example:**

* Array: 1 10 100
* Whichever subset to remove in the second case, it is not possible to split the array into two parts with the same sum.

The limits for the array are 8000 elements and each element can be 1 bilion in size.

I'am just looking for algorithm help as I thought this was a variation of the partition problem and tried for some time to solve it, but i figured out it's beyond my knowledge. Any kind of help would be appreciated.

# Answer
Let S denote the solution sum. Besides the trivial O(1) solution with S=0, other solutions if any can be found by an easy O(n2) method. Let A denote a given array of positive integers. Consider two kinds of partitions of A: (B, C, E, D) and (F, E, G, H), where each letter represents a sequential part of A, with A=B+C+E+D or A=F+E+G+H; C or G possibly empty; with E representing the extracted sequence. We suppose a solution has either S = sum(B) = sum(C+D) = (sum(A)-sum(E))/2 or S = sum(F+G) = sum(H) = (sum(A)-sum(E))/2, and claim that any solution has either an intact prefix or an intact suffix, or both, uninterrupted by extraction E.

To test for a solution of the first kind: Let S be a prefix sum of A. We look for a solution for S by advancing the beginning of E through A, and after each advance, solving (at O(1) amortized cost) for the end of E. With O(n) prefix sums and O(n) beginnings-of-E, overall cost is O(n2).

Testing for solutions of the second kind is analogous. The lightly-tested program shown below does this step by testing reversed(A).

```
#!/usr/bin/env python3
# Program written by James Waldby on 16 June 2019
# re: https://cs.stackexchange.com/questions/101950,
# "Array subset division with equal sums"
# Copyright © 2019 by James Waldby.  Offered without warranty under
# GPL v3 terms as at http://www.gnu.org/licenses/gpl.html

def findPrefixSol(A):
    S=0; U=sum(A); H=U//2; n=len(A); print (A)
    for i in range(n):        # prefix = first i elements
        S += A[i]
        if S>H: break
        Esum = 0                # sum of extract E
        Etarget = U - 2*S       # required size of E
        k = i+1                 # k -> after last element of E
        for j in range(i+1, n-1): # j -> first element of E
            while Esum < Etarget and k<n-1:
                Esum += A[k]
                k += 1
            if Esum > Etarget:
                Esum -= A[j]    # remove first element of E
                continue        # go try next E
            if Esum < Etarget:
                break           # can't extract enough to win; advance i
            print('Sol. for partition {}...{}...:  S={}, Es={}, U={}'.format(A[:i+1], A[j:k], S, Esum, U))
            break

A=[7, 5, 9, 1, 3, 9, 6]
findPrefixSol(A)
findPrefixSol(list(reversed(A)))
print()
A=[7, 5, 9, 1, 5, 9, 1, 3, 9, 9, 1, 5, 9, 1, 3, 9, 6]
findPrefixSol(A)
findPrefixSol(list(reversed(A)))

```
> 1 votes

---
Tags: algorithms, algorithm-analysis, arrays, partitions
---


# Question
Title: Algorithm for selecting a sample that's as spread out as possible?
I have a large database of data with dates. There are large gaps and large chunks of data without gaps. I want to get a sample of this data such that the dates are as spread out as possible (i.e. as close to evenly distributed as possible).

E.g. if the dates are `[1, 2, 3, 4, 100]` and I want to sample 3 elements, the ideal sample would be `[1, 50.5, 100]` and the closest available dates are `[1, 4, 100]`.

Is this a known problem with an existing algorithm?

# Answer
> 1 votes
I assume that for dates $d\_1\leq d\_2\leq\cdots\leq d\_n$ you want $k\>1$ samples of minimal total absolute distance from the ideal sample points $s\_i=d\_1+(i-1)(d\_n-d\_1)/(k-1)$, $i\in\[k\]$.

If you can repeat elements, just sample at $\operatorname{argmin}\_{j\in\[n\]}|d\_j-s\_i|$ for each $i\in\[n\]$.

Without repeating elements the following dynamic program solves your problem in time $O(n^3)$ and space $O(n^2)$: let $M(i,j)$ be the minimal total absolute distance for $k-i+1$ samples chosen from $a\_j,\ldots,a\_n$ from the ideal samples $s\_i,\ldots,s\_k$. Distance $M$ satisfies \begin{align\*} M(i,j) = \begin{cases} \min\_{j\leq j'\leq n} |d\_{j'}-s\_i|+M(i+1,j'+1), & \text{$i\leq k$, $j\leq n$, }\\ 0, & \text{$i\>k$},\\ \infty, & \text{otherwise}, \end{cases} \end{align\*} and $M(1,1)$ is the minimum solution value.

---
Tags: algorithms, optimization, sampling
---


# Question
Title: Is there a LL(K) Grammar which is not LALR(K) Grammar?
It is easy to know that there are LALR(K) grammars which are not LL(K) because any grammar with left recursion which is LALR(K), is not LL(K) because all LL(K) grammar must be left recursion free. And the opposite? Is there a LL(K) Grammar which is not LALR(K) Grammar? Do you have an example?

Related:

1. Are regular expressions $LR(k)$?
2. https://stackoverflow.com/questions/14674912/why-are-there-lr0-parsers-but-not-ll0-parsers
3. https://stackoverflow.com/questions/36652221/relationship-between-lr0-ll0-lalr1-etc

# Answer
Every $LL(k)$ grammar is $LR(k)$, but there are $LL(k)$ grammars which are not $LALR(k)$.

There's a simple example in Parsing Theory by Sippu&Soisalon-Soininen

$$\begin{align}S &\to a A a \mid b A b \mid a B b \mid b B a\\ A &\to c \\ B &\to c \end{align}$$

The language of this grammar is finite, so it is obviously $LL(k)$. (In this case, $LL(3)$.) The grammar is also $LR(1)$. However, the grammar is not $LALR(k)$ for any value of $k$.

The canonical $LR(k)$ machine has two states with $LR(0)$ itemsets $\\{\[A\to c \cdot\], \[B\to c\cdot\]\\}$. These two states have different lookahead sets in each item, corresponding to the two different predecessor states before shifting $c$. The $LALR$ algorithm merges these two states, thereby losing the distinction between the lookahead sets. This produces two reduce-reduce conflicts. Since there is only one token of lookahead at this point, increasing $k$ would make no difference.
> 6 votes

---
Tags: formal-languages, formal-grammars, parsers, lr-k, ll-k
---


# Question
Title: How to find Maximum perimeter of rectangle in a grid with obstacles? (Dynamic Programming)
Can someone tell me what am I doing wrong?

> Problem: https://codeforces.com/contest/22/problem/B
>
> Editorial: https://codeforces.com/blog/entry/507 ( I followed the DP solution O((n\*m)^2) )

Eg:

```
00001
00000
10100     //ans is 12

####1
####0
10100

```

My approach: rectangle with coordinates (x1, y1, x2, y2) is correct if and only if rectangles (x1, y1, x2-1, y2) and (x1, y1, x2, y2-1) are correct, and board\[x2\]\[y2\] = ‘0’.

> ie: dp\[x1\]\[y1\]\[x2\]\[y2\]=(dp\[x1\]\[y1\]\[x2-1\]\[y2\] && dp\[x1\]\[y1\]\[x2\]\[y2-1\] && (board\[x2\]\[y2\]==0))

If it is correct then find it's perimeter (perimeter = 2\*(x2-x1+y2-y1+2)) ie ans=max(ans,perimeter)

And dp\[x1\]\[y1\]\[x2\]\[y2\]=1 for all i,j when board\[x2\]\[y2\]==0. Because from point p1 to point p1, ie the same point always have a perimeter is the base case.

# Answer
> 1 votes
Your approach is basically correct. However, be sure to pay attention to a few boundary cases besides the general cases for x2\>x1 and y2\>y1.

* Initialize the tables on a single square, i.e., dp\[x\]\[y\]\[x\]\[y\] = (board\[x\]\[y\] == 0);
* Compute the case when the table can be on a single column, dp\[x1\]\[y\]\[x2\]\[y\] = dp\[x1\]\[y\]\[x2-1\]\[y\] && (board\[x2\]\[y\] == 0), where x2\>x1.
* Compute the case when the table can be on a single row, dp\[x\]\[y1\]\[x\]\[y2\] = dp\[x\]\[y1\]\[x\]\[y2-1\] && (board\[x\]\[y2\] == 0), where y2\>y1.

For brevity, those boundary cases are not mentioned explicitly in the editorial. Once those cases are included, the algorithm will be fully correct.

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


title: Turing machine and boolean circuits

text:
# Question
Title: Turing machine and boolean circuits
As an example of languages that are in P/poly is the UHALT Problem :

> UHALT = { 1^n: n's binary expansion encodes a pair such that M halts on input x}

We can create a boolean circuit of just AND gates. However, we can create it only for a fixed 'n', not for all n's ...

My question is : when we consider a language like the UHALD problem, do we consider all of the 'n' possible values ,ie for every 'n' we have a different language? or for every n we have a different language ?

In Turing-machines, i think we can loop, but in boolean circuits.. i dont think we can, thus the impossibility (in my point of view) of making, for example, a circuit for the UHALT problem for every n there is.

# Answer
> 1 votes
The Boolean circuits you are referring to are a non-uniform model. This means that, for every input length, you have a different circuit. When we say that Boolean circuits solve a particular problem what is actually meant is that a *family* of circuits does, which is an infinite sequence $(C\_n)\_{n \in \mathbb{N}\_0}$, $C\_n$ being the circuit for inputs of length $n$.

Moreover, Boolean circuits *in general* are intrinsically non-uniform models of computation anyway since the input gates count as part of the circuit. If you insist on an arbitrary number of input gates, then you necessarily end up with a circuit of infinite size (which is a no-no). (In fact, this is why we use the notion of constructability to obtain uniform circuits; any sort of uniformity must be *extrinsic* to the circuit.)

---
Tags: turing-machines, circuits
---


# Question
Title: Is the sum $f+g$ of two one-way-functions a one-way-function?
Since there exists a bijection of sets from $\\{0,1\\}^\*$ to $\mathbb{N\_0}$, we might view one-way-functions as functions $f :\mathbb{N\_0} \rightarrow \mathbb{N\_0}$. My question is, suppose $f,g$ are one-way-functions, is then $(f+g)(n):=f(n)+g(n)$ a one-way-function or can one construct a counterexample? (The length of $n$ is $\text{ floor}(\frac{\log(n)}{\log(2)})=$ the number of bits to represent $n$)

Comment on answer of @Bulat: Suppose $f$ is an owf. If (?) there exists a $k \in \mathbb{N}$ such that for all $x \in \mathbb{N\_0}$ we have $f(x) \le x^k$. Then as @Bulat mentioned, construct $g(x) = x^k-f(x) \ge 0$. Then $g(x)$ is an owf as $f$ is, but $h(x) = g(x)+f(x) = x^k$ is not an owf. So the question is, if there exists such an $k$. The argument would also work considering $k^x$ instead of $x^k$. But the same question remains? Why would such an $k$ exist?

Thanks for your help!

# Answer
The answer is **no**.

Given $f$ one-way, consider $g(x) = -f(x)$. $g$ is then also one-way, because inverting $g$ would imply inverting $f$. In particular, supposing $g$ is not one-way, one can invert $f(x)$ simply by negating it and applying the inverter for $g$ (and the success probability is even equal).

In this setting, $h(x) = f(x) - f(x) = 0$ is not one-way as it can be.
> 3 votes

# Answer
I think your error is that you expect that for OWF each and any `f(x)` computation should be hard to reverse. But it seems incorrect, f.e. modular squaring is easily reversible for `x=0`. EDIT: Wikipedia specifically says "Note that, by this definition, the function must be "hard to invert" in the average-case, rather than worst-case sense."

By using `g(x) = x - f(x)` you will have a pair of functions that are hard to revert, but their sum is identity function.
> 1 votes

# Answer
Let's consider arbitrary one-way function `f(x)`. We want to construct easily reversible `h(x)` with the property `h(x) >= f(x) for any x`.

Let's encode in `h` result value x and then add enough to make sure that `h(x) >= f(x)`. We can do it f.e. in this way - use lower bits of result to RLE-encode `N = bit length of x value`, f.e. if it contains 3 bits then encoding will be `0111`, then encode `N` bits of x value itself, and finally, use higher bits to encode `f(x)` value shifted by `2*N+1` bits. Well, we can put in these bits arbitrary data as far as overall value is larger than the `f(x)`.
> 0 votes

---
Tags: one-way-functions
---


# Question
Title: How to understand the CRC Algorithm from the CAN specification?
I am trying to understand how the cyclic redundancy check (CRC) algorithm from the Controller Area Network (CAN) specification works. Here is the pseudocode.

`CRC_RG = 0; // initialize shift register
REPEAT
CRCNXT = NXTBIT EXOR CRC_RG(14);
CRC_RG(14:1) = CRC_RG(13:0); // shift left by
CRC_RG(0) = 0; // 1 position
IF CRCNXT THEN
 CRC_RG(14:0) = CRC_RG(14:0) EXOR (4599hex);
ENDIF
UNTIL (CRC SEQUENCE starts or there is an ERROR condition)`

I do understand the standard algorithms but not the CAN algorithm. I have calculated it by hand and programmed it and it works fine. I just don't understand why/how it works.

# Answer
CRC(x) is remainder of polynomial division of `x` by some fixed polynomial. Here bits of `x`, as well as bits of result, represents polynomial with binary coefficients, f.e. 0b101 may represent polynomial `1*x^2 + 0*x + 1`.

So, the algorithm you have cited, is the most straightforward one - if `q(x) = p(x) mod f(x)`, then `p(x)*x mod f(x)` is either just `q(x)*x` (if it doesn't contain `x^N` where N is order of f(x) polynomial), or `q(x)*x - x^N + (x^N mod f(x))`. As you may note, the last sum component is some fixed polynomial for given `f(x)`.

So, each step of this cycle do the following:

* shift result by 1 bit left - equivalent to multiplication by `x`
* if result contains `x^N` then xor result by `x^N mod f(x)`

Oh, well, there are some more details. Please read *a painless guide to CRC error detection algorithms* for real explanation.
> 1 votes

---
Tags: crc
---


# Question
Title: If the union and intersection of two NP languages are both in P, prove that the langauges are in co-NP
**Given** $L\_1, L\_2 \in \mathsf{NP}$, $L\_1 \cup L\_2 \in \mathsf{P}$ and $L\_1 \cap L\_2 \in \mathsf{P}$,

**Prove**: $\ L\_1, L\_2 \in \mathsf{coNP}$

What I've done so far is:

$$ L\_1 \cup L\_2 \in \mathsf{P} \Rightarrow (L\_1 \cup L\_2) ^\complement \in \mathsf{P} \Rightarrow L\_1^\complement \cap L\_2^\complement \in \mathsf{P} $$

$$ L\_1 \cap L\_2 \in \mathsf{P} \Rightarrow (L\_1 \cap L\_2) ^\complement \in \mathsf{P} \Rightarrow L\_1^\complement \cup L\_2^\complement \in \mathsf{P} $$

How do I proceed from here?

# Answer
**Hint**: You only need to distinguish between two non-trivial cases: $x\in (L\_1\setminus L\_2)$ and $x\in L\_2\setminus L\_1$. In these cases, membership-certificates for $L\_1$ would be nonmembership-certificates for $L\_2$ and vice versa. Hence, you always have nonmembership-certificates for every input string $x$. And conclude that both $L\_1$ and $L\_2$ are in $\mathrm{co}$-$\mathrm{NP}$.
> 2 votes

# Answer
**Hint**: Construct a poly-time verifier for ${L\_{1}}^{c}$ by using $L\_2$'s verifier, in addition to running some polynomial-time checks.
> 2 votes

---
Tags: complexity-theory
---


# Question
Title: Dimension Reduction - Which feature should remove to reduce the dimension of the matrix
Let's suppose that we have the following 2 tables:

If we want to reduce the dimension by one(in every table) which feature we should remove and why ?

I am confused about the way that i should work generally in this type of problems.

# Answer
In the first table, X2 is an unnecessary feature. You can check that for any row, the value of Y that you obtain after reversing the value of X2 is always unaffected. Instead, X1 and X3 are both individually necessary; this can be seen for example by comparing the first row with the fifth row (for X1) and with the second row (for X3).

In the second table, X1 is an unnecessary feature. The value of Y is solely determined by whether X2 is large or small; say, larger or smaller than 0.5. Hence a linear classifier based on X2 can predict Y with full accuracy. Instead, no linear classifier based on X1 only can correctly predict Y; for example, the value of Y is 1 for X1=0.6931, becomes 0 for X1=0.7465, and becomes 1 again for X1=2.7361.

For the first type of problem, you can look at each feature individually and check whether the results indeed depend on it or not, by comparing corresponding rows as I did in the example.

For the second type of problem, you can look for non-monotonicity (as I did in the example with the X1 feature), in which case you can exclude the non-monotone feature, at least if you are looking for a linear model.
> 0 votes

---
Tags: machine-learning, data-mining, classification, pattern-recognition
---


# Question
Title: What do "patterns, which separately match parts of a page" and "interactions between patterns" mean?
*Database System Concepts* by Abraham Silberschatz, Henry F. Korth and S. Sudarshan says

> Information extraction using **simple patterns, which separately match parts of a page**, is relatively error prone. Machine-learning techniques can perform much more sophisticated analysis, based on **interactions between patterns**, to minimize errors in the information extracted, while maximizing the amount of information extracted.

What do "patterns, which separately match parts of a page" and "interactions between patterns" mean respectively?

# Answer
Simple patterns could mean regular expressions or extended regular expressions, each of which can be used to match parts of a page without considering the impact of other matches.

Interactions between patterns could mean the conditional probabilities among all findings, either the matched patterns or the unmatched patterns. Additionally, they could mean more complicated probabilistic or logical rules.

We could dive a lot deeper and wider into the subject of information extraction. However, the understanding as basic as the above should be suffice for a first-time reading.
> 1 votes

---
Tags: information-retrieval
---


# Question
Title: What impact does the modulo operator have in a for-loop?
Here's an example of what I mean:

```
def complexity(n):
    count = 0
    for x in range(1, n+1):
        for y in range(1, (n*n)+1):
            if y % n == 0:
                for z in range(1, n+1):
                    count += 1
    return count

```

The first for loop is of course θ(n), the second one θ(n^2). But what impact does the modulo operator have? And what would then be the complexity of the whole thing?

# Answer
> 3 votes
It feels like you're trying to think in terms of pre-defined recipes, rather than just figuring it out by reasoning about the situation. The `if` statement triggers every time $y$ is a multiple of $n$. So just work out how many different values in $\\{1, \dots, n^2+1\\}$ are multiples of $n$, and that's how many times the innermost `for` loop runs.

Of course, your code is just an example but, in real life, with something as simple and predictable as the modulo operator, you wouldn't use this approach of "generate every possible value of $y$ and see which ones pass the test". It's much more efficient to just write a `for` loop that directly assigns the values $n, 2n, \dots, n^2$ to $y$.

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


# Question
Title: Finding $k$-th element in prefix of size $i$
Let's say we are given array $A$ of size $n$. We need to answer some numbers of queries. For each query we are given index $i$ and integer value $k$, $k \le i$. If we take the first $i$ elements of the array $A$ and we sort them we should return the one on index $k$ (we assume everything is 1 indexed).

I know that this can be solved in $O(Q\log N)$ if $Q$ is the number of our queries in offline way (we sort all queries by their index) and if we use persistent segment trees we can even make it work in online way (we can answer queries immediately), however I was wondering if there is simpler solution?

# Answer
> 1 votes
I misunderstood the original premise that `A` does not need to change. If you want a solution for that, a good one is to just apply the worst-case linear time selection algorithm on the original array for `0-i`. This is `O(i)`.

Assume `A = [1, 0, 3, 5, 4, 7, 2, 1, 3]` (inserted in that order)

There is a trivial solution to the problem at hand, and that is to store the data as so:

```
1
0 1
0 1 3
0 1 3 5
0 1 3 4 5
0 1 3 4 5 7
0 1 2 3 4 5 7
0 1 1 2 3 4 5 7
0 1 1 2 3 3 4 5 7

```

This is `O(n^2)` space and preprocessing, but is `O(1)` retrieval. It is very fast and simple, and honestly the best solution.

In order to achieve "subquadratic preprocessing", you can store this matrix type array in a sparse manner:

```
1,2
0,0
3,2
    0 1 3
5,4
4,3
7,5
    0 1 3 4 5 7
2,3
1,2
3,5
    0 1 1 2 3 3 4 5 7

```

This is `O(nlog(n))` preprocessing and `O(nlog(n))` space, but `O(log(n))` time. You choose the gaps by computing `floor(log(n))` (or `ceil` it does not matter) and then fill in the gaps with the elements deleted and the index that they were deleted from in the bigger array (not the smaller one). When searching given an `i` and `k`, compute `ceil(i/floor(log(n)))` to determine which array to start from, and then delete items from that array (do not copy it, as that will make this algorithm `O(n)`). When you delete an item to the right of your `k`, you do nothing. Delete an item to the left, and just increment your `k` to the next *undeleted* spot. By keeping track of where the last deleted item was you'll never have to traverse the array. Finally, when you reach your `i`, the `k` will be pointing to the answer. At this point, just unwind and reinsert the deleted values back in to the array.

Example with `i = 7, k = 6`:

1. Start with `0 1 1 2 3 3 4 5 7`, with `k` pointing at `6`
2. Delete at index `5`, increment `k`: `0 1 1 2 3 _ 4 5 7 k=7, i=8`
3. Delete at index `2`, increment `k`: `0 1 _ 2 3 _ 4 5 7 k=8, i=7`
4. `i=i` that we started at, so we return `A[8]` which is `7`, and now unwind:
5. `0 1 1 2 3 _ 4 5 7`
6. `0 1 1 2 3 3 4 5 7`

This next solution was the one I was working on when I came up with the above solution (which I think is the best given the constraints). I will leave it in case if someone finds a use for it.

This solution is overly complicated for minimal gains, but matches the "subquadratic preprocessing" constraint. It is also `O(n^2)` space but is `O(nlog(n))` preprocessing. It is `O(log(n))` time.

Lets look at this problem in the simple `i = n` case: we need a data structure that is responsive to updates and can solve the selection problem fast. Here is such a data structure (sorted array for reference):

```
     1,1
  /       \
0,0       3,3
         /   \
       2,2   5,3
       /    /   \
     1,1  4,2   7,1
          /
        3,1

[0, 1, 1, 2, 3, 3, 4, 5, 7]

```

Let's say you want to find what was at index `2`: start at `1,1` at the top; `1 < 2` so now you subtract `1` from the index you were searching for, and go to the right child. `3 > 1`, so you go to the left child, and don't change your current index value. Same goes for `2,2`, until you reach `1,1`, which is at index `1 + 1` which is `2`.

This structure is a binary tree that stores each value and its position relative to the nearest parent that it the right child of. This allows you to insert an item and have the changes be reflected across nodes you haven't touched during the insert. For example, if you insert `-1` right now, which becomes `0`s left child, you need to touch `1` and `0`, and update their positions to `2` and `1` respectively. This automatically shifts everything to the right of `1` rightwards one as well. You can even balance this tree; just make sure to update the new parent by subtracting its left parent's value from it's value.

Now to solve the general case: instead of storing just one index, we store:

1. A number representing its position in the original `A`
2. A list of "previous indices" that the item was at in the sorted arrays

You build this tree just as you build a normal binary tree, except that every time you touch a node, you update it's relative position at that "time" `i`. Here is an example tree with a small array

`A = [1, 0, 3, 5]`

```
    1,0[0,1,1,1]
   /       \
0,1[0]     3,2[1,1]
              \
             5,3[1]

```

You find the `kth` index at "time" `i` by traversing the tree just as above, except you subtract the index you're looking for from the stored index at that node, then index into the list. Instead of going out of bounds, the list also stores the most recent entry. When you add a new entry, you fill in the most recent value for all `i` up to where you just inserted. If the `i` you're looking for exceeds the `i` stored at that node, just use the value at the array index `0` of the node and compare it to the index you're looking for (this only happens if you balance the tree). If this sounds familiar, it's because this is a type of union-set data structure.

For the above tree, finding `i = 2, k = 2`, you start at the top, subtract your `i` from `1`s `i`, getting `2 - 0 = 2` and checking it's array at `2`, which gives you `1`. This is too small, so we subtract the `k` that we found from our `k` giving us `1`, and move right. Next we encounter `3`, we subtract our `i = 2 - 2 = 0` and check the array at index `0` giving us `1` which matches our `k`, which is the answer.

Overly complex solution, but does manage to satisfy the requirements. Additionally, it can actually handle `A` changing! Balancing the tree is costly, however.

---
Tags: binary-trees, binary-search, search
---


# Question
Title: Is $\lceil\log n\rceil!$ polynomially bounded?
Considering the definition, $f(n) = O(n^k)$, for some constant $k$. If I choose $k = 100$ and plot, it shows $n^{100} \> \lceil\log n\rceil!$ for all $n \> 1$. However, the solutions to *Introduction To Algorithms* (2009) say that $\lceil\log n\rceil!$ is **not** polynomially bounded. What's going on?

# Answer
> 9 votes
Don't trust plots.

By Stirling's approximation (and dropping the ceilings to avoid notational overload),

$$\begin{align\*} (\log n)! &\sim \sqrt{2\pi \log n}\left(\frac{\log n}{e}\right)^{\log n}\\ &= \sqrt{2\pi \log n}\\, e^{(\log\log n - 1)\log n}\\ &= \sqrt{2\pi \log n}\\, n^{\log\log n - 1}\\,, \end{align\*}$$

which grows faster than any polynomial. But you're not going to see that by plotting versus $n^{100}$ unless you consider values of $n$ big enough that $\log\log n$ is more than about $99$, i.e., roughly $n\geq e^{e^{99}}\approx 10^{10^{42}}$, and you probably didn't consider values of $n$ quite that big, because no plotting software is going to display values like $(10^{10^{42}})^{100}$.

# Answer
> 3 votes
Let's choose $n=2^k$, and see if $T(n)=\lceil\log\_2 n \rceil !$ is bounded by a "polynomial of $2^k$" i.e. is $O(2^{mk})$ for some constant $m$. That is, $O({(2^m)}^k)$ for some $m$, or equivalently $O(b^k)$ for some basis $b\>1$. In other words, we want to check if $T(n)=T(2^k)$ is bounded by some exponential of $k$.

We have $$ T(2^k) = \lceil\log\_2 2^k \rceil ! = \lceil k \rceil ! = k ! $$ However $k!$ grows faster than any exponential. Hence, $T(n)$ is not polynomially bounded w.r.t. $n$.

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


# Question
Title: What is the difference between Simulated Annealing and Monte-Carlo Simulations?
What is the difference between Simulated Annealing and Monte-Carlo Simulations? Is Simulated Annealing a specific type of Monte-Carlo simulation, or are they completely separate techniques?

# Answer
Monte Carlo simulation is a method for computing a function. Simulated annealing is an optimization heuristic. Other than that, the only common thread behind these two methods is the use of randomness.

In Monte Carlo simulation, we are aiming at computing some quantity $A$ by finding an easily samplable random variable $X$ whose expectation is $A$. We estimate $A$ by averaging many samples of $X$. More sophisticated versions of this are rejection sampling and MCMC.

Simulated annealing is a heuristic for optimizing an objective function $f$ over a domain $D$. We start with an arbitrary point $x \in D$, and then try making local changes which improve the value of $f$; this is local search. In simulated annealing, we also allow making local changes which worsen the value of $f$, with some small probability. The probability is smaller the more the change makes $f$ worse.
> 6 votes

# Answer
Simulated Annealing is closely related to Markov-Chain Montecarlo, and the Metropolis algorithm. The main difference is that MCMC aims to generate samples that respect and underlying distribution, while SA aims to find the maximum of a function. The similarity is that in both cases you want to visit the parts of the function that have the high values with higher frequency, but in SA you actually want to converge and in a way "get stuck" in a peak, while with MCMC you want sometimes to sample the other parts of the function too as you aim to visit every part of the function with a frequency proportional to the value. Algorithmically this is achieved in SA with the "annealing schedule" which shrinks the movement radius of the random walk over time in order to zero in a local maxima.
> 2 votes

---
Tags: randomized-algorithms, simulation, monte-carlo
---


# Question
Title: Generate all permutations of 1 to n with i stacks
Assume we have **i** stacks. the possible actions are:

1. push to **first** stack form input
2. pop from stack **i** and push it to stack **i+1**
3. pop from **last** stack to output

If we have numbers of **1 to n** starting from 1 in the input, what is the **minimum value** of **i** which can generate all **permutations** of **1 to n** at the output?

The options are:

1. **1**
2. **2**
3. **n-1**
4. **n**

Option **1** obviously is not the answer, and also it's totally possible with **n** and **n-1** stacks witch removes the option **4**.

The real question is "is it possible doing with **2** stacks or we need **n-1**"?

# Answer
> 7 votes
It is not clear in the question what operations are allowed on the input and how to view or access the output. However, since we are dealing with all permutations, the answer is the same whether the input is a stack or queue and whether the output is a stack or a queue. From now on, we will **assume both input and output are stacks**.

---

> What is the minimum value of $i$ which can generate all permutations of 1 to $n$ at the output?
> The options are: 1) 1 $\\;$ 2) 2 $\\;$ 3) $n-1$ $\\;$ 4) $n$

None of the given options is correct.

* All permutations of 1 to 7 can be generated by 3 stacks.
* The permutation 7132465 cannot be generated by 2 stacks.

The above facts can be verified by an exhaustive search by a program easily. So the minimum value of $i$ which can generate all permutations of 1 to 7 is 3. Note that $3\not=2$ and $3\not=7-1$.

---

Let $s\_n$ be the minimum number of stacks (excluding the input stack and the output stack) which can generate all permutations of any given $n$ elements on the input stack.

It is obvious that $s\_n$ is non-decreasing.

We have the following **recurrence inequality of $s\_n$**: $$s\_{2n+1} \le 1+s\_n, \forall n\ge0$$ **Proof**: Suppose we are given $\sigma$, an arbitrary permutation of $1$ to $2n$. Here is an procedure that uses $1+s\_n$ stacks to produce $\sigma$, i.e., move all numbers from $1$ to $2n$ on the input stack to the output stack so that the output stack contains $\sigma(1), \sigma(2), \cdots, \sigma(2n)$.

1. Use the first $s\_n$ stacks to move the numbers from $1$ to $n$ on the input stack to the last stack, the $s\_n$-th stack so that the numbers on the last stack are in the reverse order of $\sigma$.
2. Similarly, we are able to move the remaining numbers on the input stack, numbers from $n+1$ to $2n$ to the last stack in exactly the same way. However, we will tweak the procedure as follows.

When a number is about to push to the last stack, we will pop out all the numbers on the last stack that should be pushed to the output stack, i.e., those numbers that appears later than that number in the sequence $\sigma(1), \sigma(2), \cdots$. Then we will push that number to the last stack. Also immediately, pop it out from the last stack to the output stack.

Now suppose we are given $\sigma'$, an arbitrary permutation of $1$ to $2n+1$. Now we will change the procedure above in the following way. Whenever we see the number $\sigma'(2n+1)$, we will move it all the way to the output stack immediately. The task remains is to move all other $2n$ numbers to the output stack as wanted, which can be done by the procedure above.

$\checkmark$

Facts:

* $s\_1=0$,
* $s\_2=1$,
* $s\_3=s\_6=2$,
* $s\_7=s\_{13}=3$,
* $s\_{27}\le4$,
* $s\_{55}\le5$.

**Proof**. The permutation $\begin{pmatrix} 123\\312\end{pmatrix}$ cannot be generated by 1 stack. $s\_6=2$ can be demonstrated by a short brute-force program in Python within 1 second. The permutation $\begin{pmatrix} 1234567\\7132465\end{pmatrix}$ cannot be generated by 2 stacks. Other facts are either obvious or easily obtained, thanks to the recurrence inequality proved above.

---

I suspect $s\_{14}=3$.

---
Tags: data-structures, permutations, stacks
---


title: distance between histograms

text:
# Question
Title: distance between histograms
I have 2 histograms that represent the height of characters in 2 images. example:

* 1 **\****
* 2 *****\*****
* 3 *****\*******
* .
* .
* .
* 100 *****\*****\****

For these 2 histograms I compute the peaks. And To **check** if these 2 images are **similar** I compute the interseciton between the indices of the 2 images. Example: For image 1 the indices of the peaks are 1, 10 and 13 for image 2 the indices of the peals are 1,10, 14. Image1 Inter Image1 = 2 So these images are similar.

But I feel that the intersection is not enough. I think that i should also use the size of the buckets of the histograms peaks.

Is there a way to use to both of them to measure the similarity in **1 function** So that I can have a stable similarity function?

# Answer
> 1 votes
If you normalize your histograms you then have an empirical pmf. There are numerous methods to calculate distances of pmfs, such as Kullback-Leibler and Jensen-Shannon divergences. If the base-set of the histograms are exactly the same then KL divergence will work fine. If they intersect, but are not exactly the same, then JS divergence will work instead.

Be careful as KL divergence is non-symmetric. That is, given two pmfs $P$ and $Q$, $\text{D}\_{\text{KL}}(P||Q)$ may not be equal to $\text{D}\_{\text{KL}}(Q||P)$. On the other hand $\text{D}\_{\text{JS}}$ is symmetric, but still not a metric.

# Answer
> 0 votes
One possible solution could be the following algorithm:

1. Normalize the histograms h1 and h2, so that both have an area of the same (scalar) size (i.e. the integral of the peak height over all peaks should be the same to compensate for different sample sizes). You receive normalized histograms h1n and h2n.
2. Overlay both normalized histograms h1n and h2n and calculate the intersection for every single peak. You should receive a new histogram that represents a two-dimensional intersection (h3).
3. Integrate the peak height of the new intersection histogram h3.

In summary, you receive a single scalar value that represents the normalized intersection area.

This algorithm requires that h1 and h2 have the same number of peaks.

# Answer
> 0 votes
This article provides a simple and efficient solution to your problem. Basically, it calculates the overlap between the two histograms and then normalizes it by second histogram (you can use first). You can use this function to calculate the similarity between the histograms.

```
def return_intersection(hist_1, hist_2):
    minima = np.minimum(hist_1, hist_2)
    intersection = np.true_divide(np.sum(minima), np.sum(hist_2))
    return intersection

```

---
Tags: machine-learning, probability-theory, statistics
---


# Question
Title: Is CPU Registers part of Primary Memory?
A friend of mine appeared in an exam recently, and one of the question asked was regarding CPU Registers, which has two points:

* (a) CPU Registers are part of Primary Memory
* (b) They are volatile

And the choices given were:

1. Both (a) and (b) are true
2. Only (a) is true
3. Only (b) is true
4. None of the above

They are volatile. So the second and forth options can be avoided. The confusion was regarding whether it was part of Primary Memory. To my knowledge, CPU Caches, RAMs and ROMs can be called as primary memory. But will CPU registers would be called as part of primary memory? Or will it be considered as Level0 caches?

# Answer
> 4 votes
CPU registers are often counted as part of primary memory (since they are directly accessed by the CPU - see Wikipedia) and are often volatile, so it seems likely that the expected answer is (1).

However, this is one of those annoyingly ambiguous questions which depend on the student memorising a very specific set of definitions and ignoring any exceptions.

# Answer
> 0 votes
This depends on actual CPU. Any modern CPU contains its registers, so they aren't a part of memory. Caches by definition cannot be part of memory too - they are hidden (to programmer) structures making memory access faster.

# Answer
> 0 votes
Outside your course, the question would be: How do you define “primary memory” and how do you define “volatile”.

I’ve seen *one* CPU where registers were stored in RAM, so it depends on the CPU as well.

---
Tags: cpu-cache, cpu, memory-hardware
---


# Question
Title: Derandomize MAX-CUT problem using $\log n$ bits
Consider the MAX-CUT problem. We can flip $n$ coins to generate a random cut, and by linearity of expectation we get that with "good probability" our cut we'll be bigger then $\frac{n}{2}$.

Using pseudo random generators (XOR for example) we can generate $n$ pairwise independent bits from $\log n$ random bits. Using that approach, we can de-randomize the MAX-CUT problem with polynomial complexity.

With that algorithm, we are only checking $n$ possible cuts, where there are total of $2^n$. Is it promised that a "good" cut is within these $n$ cuts? Why?

# Answer
> 1 votes
Consider a graph with $n$ vertices and $m$ edges.

Let $\mathcal{D}$ be a pairwise independent distribution over $\\{0,1\\}^n$, and suppose that $x = (x\_1,\ldots,x\_n) \sim \mathcal{D}$. For every edge $(i,j)$, the probability that it is cut in the cut corresponding to $x$ is $$ \Pr\[x\_i \neq x\_j\] = \frac{1}{2}, $$ due to pairwise independence. Therefore the *expected* number of edges cut is exactly $\frac{m}{2}$, by linearity of expectation. In particular, there is at least one realization of $x$ (that is, one point in the support of $\mathcal{D}$) which cuts at least $m/2$ edges.

---
Tags: randomness, max-cut
---


# Question
Title: How to prove $L \notin \texttt{DSPACE}(f)$
I want to prove that a language $L$ is not in $\texttt{DSPACE}(f(n))$, the class of languages that a deterministic Turing machine can decide with fixed tape length of $f(n)$ (wiki). That is, I want to prove:

$$ L \notin \texttt{DSPACE}(f(n)) $$

How would I do this?

My first attempt was to reduce a language $L'$ from $\texttt{DSPACE}$ to the language $L$, but I don't know of any language in $\texttt{DSPACE}$ and I don't know if I can "simply" reduce it. Does anyone have a reduction that I see and try to understand?

---

The exact exercise specifies the language $L$: it is $\\{ w\mid w \in T(M\_w),M\_w \text{ needs space |w|}\\}$.

Also, we are given that $f(n) \in \Omega(\log{n})$.

# Answer
Unfortunately, when you tried to ask a general question to get hints for your homework exercise rather than the solution, you turned the question into something too general to answer. I'll try to come back at some point and write something more useful, now that you've made the question more specific. Diagonalization is the usual technique, similar to how the halting problem is proven undecidable.

---

You're not going to prove that a completely generic language $L$ is not in $\mathrm{DSPACE}(f(n))$ for a completely generic function $f$. Any such proof is going to have to rely on some properties of $L$ and $f$: quite apart from anything else, if you fix a decidable language $L$, then there are infinitely many functions $f$ such that $L$ **is** in $\mathrm{DSPACE}(f)$ and, conversely, if you fix any "reasonable" function $f$, there are infinitely many languages in $\mathrm{DSPACE}(f)$. So you can't hope to prove $L\notin\mathrm{DSPACE}(f)$ as a generic result.

Second, saying "I don't know any languages in $\mathrm{DSPACE}$" is like saying I don't know any people who weigh kilograms (or pounds, if you prefer). It doesn't really mean anything until you specify *how many* kilograms or, correspondingly, what space bound you're talking about.
> 1 votes

---
Tags: complexity-theory, turing-machines, reductions, proof-techniques, space-complexity
---


# Question
Title: What are the benefits of languages that are not Turing complete?
Unfortunately I did a degree in CS without much theoretical computer science. One thing I used to hear is that sub languages, or languages which are not Turing complete, allow for better optimization?

Why is this case? What is the thought process and what are some examples in practice? What are some good resources on the topic?

# Answer
The main advantage of having a Programming Language that is not Turing Complete is that your language can be strongly normalizing, that is, you can ensure that all terms halt with a unique, well formed value.

I've come across non-Turing complete languages primarily with proof assistants. When you're using programs to prove theorems, you need to make sure that all terms halt, since otherwise you can produce non-terminating terms of type False. This also ensures that type checking is decidable with dependent types, since we need to evaluate code with type checking. Agda and Coq are both languages that are not Turing Complete. This also ensures that you can't accidentally write an infinite loop, which is the motivation behind things like the Dhall language.

As for what you mention about program analysis, Rice's theorem means that any analysis of a Turing Complete language is either unsound or incomplete. So if you use restricted languages, you might be able to write analyses that are precise.
> 2 votes

---
Tags: formal-languages, optimization, turing-completeness, operational-semantics
---


# Question
Title: How can maximum number of minimum cuts of a graph be exactly $n \choose 2$?
According to my instructor, $n\choose 2$ is the maximum number of minimum cuts we can have on a graph. To prove this, he showed the lower bound using an n-cycle graph. To prove the upper bound, he drew the argument from two facts:

* Probability of finding $i^{th}$ min cut $\geq\frac{2}{n(n-1)}=\frac{1}{n\choose 2}$
* Event of finding $i^{th}$ min cut is disjoint.

So just adding up the probabilities he proved the upper bound of $n\choose 2$.

Now if we consider a tree, as a graph, with $n$ nodes, then we will be able to conclude $(n-1)$ min cuts which is less than $n\choose 2$ cuts ($ n\geq3)$. Am I missing something here?

# Answer
> 1 votes
"Maximum" here means that no graph can have more than $n \choose 2$ minimum cuts. Obviously, you can come up with graphs (or infinite families of graphs) that have fewer minimum cuts, like say $n-1$. This is less than $n \choose 2$ which is perfectly fine, so this is no contradiction. In other words, the result only means that you can't come up with graphs that have more than the maximum number of minimum cuts.

# Answer
> 1 votes
Some graphs have less than the maximum. This shouldn't be a surprise.

---
Tags: graphs, randomized-algorithms, minimum-cuts
---


# Question
Title: Wikipedia says this grammar is LR(0), but Grammophone says it is not; is it?
```
  E -> E * B .
  E -> E + B .
  E -> B .
  B -> 0 .
  B -> 1 .

```

I am confused because Wikipedia cites this grammar as an example of an LR(0) grammar and constructs an LR(0) parsing table for this grammar, while Grammophone reports shift-reduce conflicts and marks some cells in the grammar's LR(0) parsing table red. (The dots are not terminals; rather, they denote end of production; Grammophone requires this.)

What's going on here?

# Answer
> 1 votes
Before applying the LR algorithm to a grammar, the grammar must be "augmented" by adding the rule

$S' \to S \\$$

where $S$ is the original start symbol and $S'$ and $\\$$ are symbols not in the grammar. $S'$ becomes the start symbol for the augmented grammar, and the string to be parsed is augmented by appending a $\\$$ at the end. A reduce action for this newly added rule is written as "accept", which has the side effect of terminating the parse.

The table shown in the Wikipedia article is for the augmented grammar, as you can see from its parsing table, which includes "accept" actions and the $\\$$ end marker symbol.

For whatever reason, Grammophone does not augment grammars before applying the LR(0) algorithm. The grammar is augmented for the other algorithms. (I would call this a bug, but it could argued that it is an idiosyncratic interpretation of the algorithm.) If you give it an augmented grammar, then you get roughly the same LR(0) table as is found in Wikipedia (although an extra state is produced prior to the accept action.)

Grammophone has other issues. I don't recommend relying on it for grammar analysis.

---
Tags: context-free, formal-grammars, parsers, lr-k
---


title: Is $L(G) \subseteq L(R)$ decidable?

text:
# Question
Title: Is $L(G) \subseteq L(R)$ decidable?
Is the following problem decidable?

> Given a context-free grammar $G$ and a regular expression $R$, is $L(G) \subseteq L(R)$?

It is given that the following problem is undecidable

> Given a context-free grammar G, is $ L(G) = \Sigma ^\*$ ? $\ (1)$

and this problem decidable

> Given a context-free grammar G, is $ L(G) = \emptyset $ ? $\ \ \ (2)$

My thought is this:

$L(G) \subseteq L(R)$ is the same as $ L(G) \cap \overline{L(R)} = \emptyset $. So, since regular languages are closed under complement, and the intersection of a $CFL$ with a $RL$ is a $CFL$, $L(G) \cap \overline{L(R)}$ is a $CFL$. Now, $(2)$ is decidable, so if we can create a context-free grammar for $L(G) \cap \overline{L(R)}$ and give it as input to a decider for $(2)$ we have decided our initial problem.

Is my thought correct? And if yes, how can create such a grammar?

# Answer
> 3 votes
Yes, your thought is correct. The only missing part, as you pointed out, is whether or how we can create a CFL algorithmically for the intersection of a CFL with a RL.

If you take a close look at any proof for the fact that the intersection of a CFL with a RL is a CFL, you will find that the proof is constructive or can be made to be constructive easily, giving that there is an algorithm to construct the CFL for a given PDA. Here "constructive" means the same as "algorithmic". It is just by convention or history, we tend to use the word "constructive" instead of "algorithmic" to describe a proof.

You can check your textbook, or this and this.

**Exercise.** Is the following problem decidable?

> Given a context-free grammar $G$ and a regular expression $R$, is $L(G) \supseteq L(R)$?

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


title: How to prove existence of the language

text:
# Question
Title: How to prove existence of the language
Consider such question:

(*Prove or disprove*) There exists a language in $TIME(2^{n^2})$ that is not in $NTIME(n)$.

I guess that answer is yes because $TIME(2^{n^2})$ and $NTIME(n)$ are totally different classes ($TIME(2^{n})$ and $NTIME(n)$ are the same classes, i guess). How to prove it strictly? (Or my guess is incorrect?)

# Answer
Combine the following two facts:

* $\mathsf{NTIME}(n) \subseteq \mathsf{TIME}(2^{O(n)})$, by deterministic simulation of nondeterminism.
* $\mathsf{TIME}(2^{O(n)}) \subsetneq \mathsf{TIME}(2^{n^2})$, by the time hierarchy theorem.
> 1 votes

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


# Question
Title: "Insensitive" CNF/DNF SAT always satisfying same number of clauses
I came across this paper, which mentions an interesting variation on SAT:

> We call a CNF formula F **insensitive** if every total assignment α satisfies the same number of clauses of F.

I hadn't come across this before. You can easily define the same property for DNF formulae as well.

Which brings me to the following question:

**Given either a DNF or CNF formula, how hard is it to tell if the formula is insensitive?**

It is clear that the decision problem "is this formula insensitive?" for both DNF and CNF is in co-NP, because two assignments satisfying different numbers of clauses serve as a "no" certificate. Its complement, which is "is this formula sensitive?" is in NP. But are these problems complete in their respective classes?

I suspect the answer is "yes," because most variants of SAT turn out to be NP-complete. But I don't know how to prove this, and I cannot find any information on "insensitive" formulas outside of this paper. Does any info on this exist?

# Answer
> 1 votes
Consider a DNF $C\_1 \lor \cdots \lor C\_m$.

For any clause $C\_i$, we can compute the probability that a random assignment satisfies $C\_i$: it is 0 if $C\_i$ contains both a variable and its negation, and otherwise it is $2^{-|C\_i|}$, where $|C\_i|$ is the number of literals in $C\_i$.

For any two clauses $C\_i,C\_j$, we can compute the probability that a random assignment satisfies both $C\_i$ and $C\_j$: it is just the probability that a random assignment satisfies $C\_i \land C\_j$.

Given this data, it is routine to compute the *variance* of the number of satisfied clauses under a random assignment. The DNF is insensitive iff the variance is zero. The corresponding algorithm runs in polynomial time, and so the problem is in $\mathsf{P}$.

If we have a CNF, we can negate it to obtain a DNF which is insensitive iff the original CNF is.

---
Tags: np, satisfiability, co-np
---


# Question
Title: Count number of linearly independent subsets of columns of a binary matrix
I have a binary $m \times n$ matrix of rank $m$ (hence $m \< n$). I need to count how many subsets of its columns form matrices with a full column rank, i.e. columns in the subset are linearly independent.

Straightforward approach would be to iterate over all subsets of columns of size up to $m$ (because column rank cannot be higher than a row rank), and then check corresponding submatrix if it has full column rank. For instance, if $m=25$ and $n=50$, this way one needs to test $$ \binom{50}{1} + \binom{50}{2} + \dotsb + \binom{50}{25} \approx 6.3 \times 10^{14} $$ matrices. Hence one needs a really fast algorithm to test if a particular submatrix has a full column rank.

For example, assume I have 500 cores and I want to calculate the subject in 24h. Then I need to test $1.4 \times 10^7$ submatrices per second per core. Old good Gaussian elimination fails with this task (right?). Can I do something much faster than it?

**Another approach** might be some optimised method like branch and bounds, so that one does not need to check all the submatrices - but only a small portion of them. For example we can build the subsets recursively, and if we encounter a subset of columns that are linearly dependent, we can safely throw away all of the supersets of this subset - as they will never become linearly independent. However, I am not sure about either complexity or running time of this approach. I am to implement it now to see the running time behaviour.

P.S. All operations are over Galois field $\mathbb F\_2$.

P.P.S. Do you think this problem is in NP?

# Answer
Snook, Counting bases of representable matroids shows that counting the number of *maximal* linearly independent subsets of columns is $\mathsf{\\# P}$-complete. Your problem is probably also $\mathsf{\\#P}$-complete. This suggests that you need an enumerative approach.

On the other hand, you can efficiently (in theory) approximate the number of maximal linearly independent subsets arbitrarily well, see for example Anari et al., Log-Concave Polynomials II: High-Dimensional Walks and an FPRAS for Counting Bases of a Matroid (might be an overkill).
> 1 votes

---
Tags: algorithms, algorithm-analysis, np, matrices, linear-algebra
---


# Question
Title: In complexity theory, does polynomial time refer to the big-O notation?
When we are discussing the run time of an algorithm, are we referring to big-O notation or are we saying that the runtime is the same for all cases?

For example; algorithm X runs in polynomial time.

# Answer
> 3 votes
Very rarely we measure the exact running times, and when we do, it's specified quite clearly.

Then, there is the big-O notation and its friends, which give information about the asymptotic behavior of the algorithm.

But different big-O sets (being pedant here, O(n) is actually a set of functions) can be grouped into classes. There are linear algorithms, which run in O(n). Then, there are sublinear algorithms (faster than O(n), such as O(logn)). Polynomial algorithms are quite important, and represent the algorithms with running times bounded by a polynom (e.g. O(n^k)). There are expone ntial algorithms, such as O(k^n), nonpolynomial algorithms, which grow faster than polynomial and include exponential, and so on.

All of these are simply a coarse categorization of the running time, which can be made by looking at the asymptotic behavior of the algorithm.

---
Tags: complexity-theory
---