title: Adapting neural network

text:
# Question
Title: Adapting neural network
I have on a few occasions trained neural networks (back propagation networks) with some rather complicated data sets (backgammon positions and OCR). When doing this, it seems that a lot of the work involves trying out different configurations of the networks, in order to find the optimal configuration for learning. Often there is a compromise between small nets that are faster to use/learn, and bigger nets, that are able to represent more knowledge.

Then I wonder if it could be possible to make some networks that are both fast and big. I'm thinking that at network where every neuron ain't fully connected ought to be faster to calculate than nets with full connection on all layers. It could be the training that detected that certain inputs are not needed by certain neurons, and therefore remove those connections. In the same way the training could also involve adding new neurons if some neurons seems to be "overloaded".

Is this something that have been tried out with any success ? Does any classes of networks exists with this kind of behavior ?

# Answer
This is roughly an open problem subject to ongoing research with various different strategies and heuristics known. A key word is "neural network *architecture*". The most basic strategy is to iterate through various network topologies and retrain for each one. Another strategy is to start with a relatively larger network and prune connections that have low weight and retrain and look for improvements; years ago this was called "brain damage" in at least one paper \[2\]. Here are some example references. There are many others. There is also a possibility of using GA-like algorithms to determine the network structure \[3\]. Here is part of the abstract from \[1\]:

> The use of ANNs requires some critical decisions on the part of the user, which may affect the accuracy of the resulting classification. In this study, determination of the optimum network structure, which is one of the most important attributes of a network, is investigated. The structure of the network has a direct effect on training time and classification accuracy. Although there is some discussion in the literature of the impact of network structure on the performance of the network, there is no certain method or approach to determine the best structure. Investigations of the relationship between the network structure and the accuracy of the classification are reported here, using a MATLAB tool-kit to take the advantage of scientific visualisation.

\[1\] Determining Optimum Structure for Artificial Neural Networks by Taskin Kavzoglu

\[2\] Optimal brain damage Le Cun, Denker, Solla

\[3\] Finding Optimal Neural Network Architecture Using Genetic Algorithms Britos et al
> 5 votes

---
Tags: machine-learning, neural-networks, learning-theory
---


# Question
Title: How can I show a linear languages are closed against concatenating with regular ones?
This was given as a homework problem but I have already submitted the assignment. I'd like to resolve it at this point for my own satisfaction.

Given that $L\_1$ is a linear language and $L\_2$ is a regular language, show that $L=L\_1L\_2$ is a linear language.

Recall that a linear grammar $G=(\Sigma, V, P, \sigma)$ has productions $A\to yBz$ for some $y,z \in \Sigma^\*$ and $A,B \in V$.

I use the theorem that every regular language can be represented by a right linear grammar.

Then I use the theorem that every right linear grammar is the reverse of a left linear grammar (being a little careful about what I mean by reverse)... $L(rev(G))=rev(L(G))$...

Next each left linear grammar is the reverse of a regular language, but the reverse of a regular language is regular, so left linear grammars also represent regular languages.

So our productions in $L\_2$ are of the form $x \to Ca \mid a$ for some $C \in V\_{L\_2}$ and $a \in \Sigma\_{L\_2}$.

Now on to the show...

What we are looking for is $L = L\_1.L\_2$, $L$ is linear (to show).

So this has the form $S \to yBzCa \mid yBzaa$

So far so good, the second production is linear and within our expectations for set inclusion.

I'm having a devil of a time reducing $yBzCa$ however ...

If I introduce $V\to BzC$ that linearizes $S$ but $V$ is not linear ...

If I give $T\to z$ to get $V\to BTC$ I'm not much better off

If I use $V\_1\to Bz$ (ok linear!) but then $V\to V\_1C$ (not linear)

What is the piece of the puzzle I'm missing?

I have a suspicion that my woes are because I failed to have a production that is $B\implies^\*a$ for some terminal $a \in \Sigma\_{L\_1}$ but I haven't observed that in the definitions thus far... and further unless B only goes to a terminal I'm in the same mess (if $B\to t$ where $t \in \Sigma\_{L\_2} \bigcup {\epsilon} $ then I think I'm finished but how do I justify it?

# Answer
> 2 votes
The piece of the puzzle is not to start $L\_1$ and $L\_2$ in parallel, but to *first* generate the regular suffix (strings in $L\_2$), then (when the left-linear grammar finishes) continue with the linear prefix (strings in $L\_1$).

(*added, deadline closed*) Thus we assume we have grammar $G\_i = (\Sigma,V\_i,P\_i,S\_i)$ for language $L\_i$, where $G\_1$ is linear, and $G\_2$ is left-linear, following your own suggestion, and generates the regular language "in reverse". Given two strings $w\_1$ and $w\_2$ in the respective languages, having derivations $S\_1 \Rightarrow^\*\_{G\_1} w\_1$ and $S\_2 \Rightarrow^\*\_{G\_2} B w' \Rightarrow\_{G\_2} w\_2$, we glue these together as $S\_2 \Rightarrow^\*\_{G\_2} Bw'\Rightarrow S\_1 w\_2 \Rightarrow^\*\_{G\_1} w\_1 w\_2 $. Thus, first generate $w\_2$, in the last step switching to the axiom $S\_1$ of $G\_1$, then generate $w\_1$.

Technically this is achieved by requiring $V\_1 \cap V\_2 = \varnothing$, choosing all productions in $P\_1$ and $P\_2$ except that "final" productions $A\to a$ with $a\in\Sigma$ in $P\_2$ are changed into $A\to S\_1a$.

---
Tags: formal-languages, context-free, closure-properties, check-my-proof
---


# Question
Title: Regular expression for odd binary numbers without leading zeros
I have to write a regular expression that accepts any odd binary number not preceded by a 0. the best I can come up with is $1(0\cup1)^\*1$, but that doesn't match just 1. The best it matches is 11.

# Answer
> 1 votes
First you might just add that single $1$ to your expression as an alternative to what you already have. One obtains $1 \cup 1(0\cup 1)^\*1$.

An alternative is $1(0^\*1)^\*$. That one is shorter, but not necessarily better.

Actually that expression I obtained by starting with the FSA below, and realizing that the rightmost two states could be replaced by iterating $0^\*1$.

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


# Question
Title: Push relabel algorithms in flow networks
In the CLRS book (http://en.wikipedia.org/wiki/Introduction\_to\_Algorithms) Chapter 26 (Maximum Flow) page 744 (third edition), there is the following equation -

$$ \sum\_{u \in U}e(u) \\;=\\; \sum\_{u \in U}\\;\sum\_{v \in U}f(v, u) \\;+\\; \sum\_{u \in U}\\;\sum\_{v \in \bar{U}}f(v, u) \\;-\\; \sum\_{u \in U}\\;\sum\_{v \in U}f(u, v) \\;-\\; \sum\_{u \in U}\\;\sum\_{v \in \bar{U}}f(u, v) $$

where $f(u, v)$ is the flow between vertices $u$ and $v$, $e(u)$ is the excess flow at a particular vertex, $U$ is the set of vertices which are reachable from the source, and $\bar{U}$ is the set of remaining vertices.

In the next line, the first and third terms disappear. I don't understand why that holds. I do realize that those are flow values from vertex $u$ to vertex $v$ where both of them are in the same set $U$, but I don't understand why they cancel out to zero.

# Answer
> 2 votes
You just have to reorder the elements of $U\times U$, because the double sum contains each edge $(u,v) \in U\times U$ exactly once:

$$\sum\_{u \in U}\sum\limits\_{v \in U}f(v, u) = \sum\_{(u,v) \in U\times U}f(v, u) = \sum\_{(u,v) \in U\times U}f(u, v) = \sum\_{u \in U}\sum\limits\_{v \in U}f(u, v)$$

The fist sum sorts the edges by their first vertex, the third sum (of the question's equation) sorts the edges by their second vertex. This is the simplest imaginable form of a double counting argument.

---
Tags: algorithms, graphs, network-flow
---


# Question
Title: Difference between a TM with an empty language and the one accepting empty string
If a TM(Turing Machine) accepts NO input string(even the blank), then its language is empty.

If a TM ONLY accepts the blank string(meaning that there is nothing on the tape except for the default blank characters), then its language has only one item and it is the blank string.

Are these definitions correct?

Could you describe the TM for each?

Also, this might be irrelevant but let me ask: I saw somewhere that there must be at least two states for a TM. Which states must be there all the time in a TM?

# Answer
> 8 votes
The definitions (well, descriptions) look correct, more or less.

A TM accepting the empty language may move directly into the halt reject state, regardless of what may or may not be on the input tape.

A TM accepting the language consisting of only the empty string may examine the first tape symbol. If the symbol is a blank, it could move to the halt accept state. Otherwise, it would move to the halt reject state. We don't have to worry about the user providing an input that starts on some later position in the tape since the blank symbol is not allowed in the input alphabet.

To summarize:

A TM for $\\{\epsilon\\}$ has pseudocode:

```
if tape[1] is blank then accept else reject

```

A TM for $\emptyset$ has pseudocode:

```
reject

```

or, if it helps you make the difference even clearer:

```
if tape[1] is blank then reject else reject

```

As Yuval points out in the comments, there are infinitely many TMs accepting one or the other of these languages; the two suggested here are for illustrative purposes only.

\[EDIT\]Some additional discussion motivated by recent comments.

(1) Depending on what your definition of a TM is and/or how explicit you want to be, there are two possibilities. If you want your machine to explicitly enter a halting state for every input tape, then yes, you will have a transition to the halt reject state on every symbol of the input alphabet. If you allow your Turing machine to reject strings by "crashing" (reaching a configuration for which there is no defined transition), then these transitions aren't necessary; simply transition to halt accept on blank, and let the machine crash in all other cases.

(2) Yes, the machine which accepts the empty language always rejects. Notice that it is perfectly acceptable to define automata with accepting states which are never reached (depending upon your definition, of course). In particular, we could take any arbitrary TM and change it to accept the empty language by changing all transitions from the initial state to lead to the halt reject state.

(3) Typically, TMs are understood to have two special states in addition to any "user-defined" states: the halt accept and halt reject states, which the TM enters to explicitly accept or reject, respectively, some input. In addition to these two states, an initial state is required from which to begin processing the input. By my reckoning, this means that every TM has at least three states. Notice, though, that not all of these states needs to be used by any given TM. In particular, a valid TM might endlessly loop on the initial state for all inputs; this TM will accept the empty language (although it doesn't decide it; to decide it, it needs to enter one of the halting states for each input).

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


# Question
Title: Algorithms with polynomial time complexity of higher order
I was learning about algorithms with polynomial time complexity. I found the following algorithms interesting.

* Linear Search - with time complexity $O(n)$
* Matrix Addition - with time complexity $O(n^2)$
* Matrix Multiplication - with time complexity $O(n^3)$

Is there any algorithm with a higher complexity like $n^4$, $n^5$ etc? I would like to know about practical algorithms with polynomial time complexity only.

(I am familiar with algorithms having exponential complexity and class NP algorithms. My doubt is not about them.)

# Answer
> 9 votes
The AKS primality test runs in time $\tilde{O}(n^6) \subseteq O(n^7)$, $n$ the length of the input number (in binary). This is the best known bound; as far as I know, there is no proven lower bound.

---
Tags: algorithms, complexity-theory, asymptotics
---


# Question
Title: When two siblings in a heap are equal, how do you bubble down?
I have a heap where both child nodes of the root are 10, and I'd like to perform an operation to remove the min value 9.

I proceed to replacing the root with its next of kin, 18. However when I bubble down, I am unsure of which direction to take.

# Answer
> 2 votes
Picking either should work. The heap property (assuming you have changed it to mean parent $\le$ children) will not be violated.

---
Tags: data-structures, heaps
---


# Question
Title: How to interpret this formal language definition?
I am asked to construct a PDA to accept the language:

$\qquad \\{w \in \\{0, 1\\}^\* : \\#\_{0}(w) \ge \\#\_{1}(w)\\}$

I am wondering how to interpret the $\\#$ symbols and everything. Could someone please explain what exactly this means and how to construct it?

# Answer
> 2 votes
This is pretty standard notation for

$\qquad \\#\_a(w) = |w|\_a = $ number of occurrences of $a$ in $w$.

Building a PDA for this language is straight-forward. Find a hint below.

> Use the stack to count $\\#\_0 - \\#\_1$ in the processed prefix of the input. Figure out how to model negative numbers.

---
Tags: formal-languages, terminology
---


# Question
Title: Give CFG and PDA for the words that start and end with the same symbol
I need to give a PDA and CFG for a language that contains all binary strings that start and end with the same symbol. I've created the CFG with no problem, but I'm stuck with the PDA and don't quite know how to accomplish it.

The best I can figure is that I need to use non-determinism, but I don't quite know how to apply it in this circumstance.

Here's the CFG that I came up with:

\begin{align\*} A &\to 1B1 \mid 0B0 \mid \epsilon\\ B &\to 1B \mid 0B\mid \epsilon \end{align\*}

The PDA, insofar as I managed to come up with:

The notation here, just in case it's not universal: $a,b \to c$ means "When you see symbol $a$, pop symbol $b$ off the stack and push symbol $c$ onto the stack."

Any pointers on how to accomplish this?

# Answer
> 6 votes
A DFA is simple: From start state $A$ on 0 go to $B$, from $B$ with 0 go to $C$ (final), from $B$ with 1 stay in $B$, from $C$ with 0 stay in $C$, from $C$ with 1 go to $B$. Use a mirror for 1.

The PDA is just the DFA which essentially ignores the stack (rewrite the stack start symbol with itself on each move).

A CFG is just: $$ \begin{align\*} S &\rightarrow 0 A 0 \mid 1 A 1 \mid 0 \mid 1 \\ A &\rightarrow 0 A \mid 1 A \mid \epsilon \end{align\*} $$ A CFG more in line with the DFA is: $$ \begin{align\*} S &\rightarrow 0 A \mid 1 B \mid 0 \mid 1 \\ A &\rightarrow 0 A \mid 1 A \mid 0 \\ B &\rightarrow 0 B \mid 1 B \mid 1 \end{align\*} $$

# Answer
> 3 votes
Your grammar is wrong: you don't generate $0$ and $1$ which are certainly in the language, and you generate $\varepsilon$ which may or may not be in it, depending on the exact formulation. Both are easy to fix and the rest looks fine to me. Can you *prove* correctness?

In order to get a PDA, there are multiple strategies.

1. Use the canonical construction from your grammar.
2. Construct a PDA (with smarts).
3. Note that the only thing you need to remember is the first symbols. Thus, finite memory is sufficient; the language is regular. See vonbrand's answer.

When you construct automata, note the following rules of thumb:

* You need a starting state.
* If your language is not empty, you need (reachable) accepting states.
* If your language is not finite, you need loops.

Your automaton already fails on these counts. Instead of succumbing to the formal model, try this: write a regular program that accepts the language, with the following restrictions:

* You can only use one `while` loop, no recursion.
* You have one stack (with `push`, `pop`, `isempty?`, nothing else)¹.
* You have one pointer in the input string, and it can only move to the right.
* You can only have a fixed (i.e. independent of the input) number of boolean auxiliary variables.

If you have this, rewrite the program in automaton form; the main task will be to figure out the states from the possible values of your variables.

Be aware that this strategy only works to obtain *deterministic* automata. Non-deterministic ones are often smaller/simpler, or even necessary (e.g. for inherently ambiguous context-free languages), so you have to become comfortable in the model at some point. This is merely a stepping stone.

---

1. If you disallow the stack, too, the same works for DFA.

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


# Question
Title: Constructing a binary tree with given traversals
I have given a post order & in order traversal a BST & I need to construct it. I want to know how to do this.

for eg.

Post Order : DCBGFEA

In Order : BDCAFGE

This is how I am trying to do :

* From POST order it is clear that A is root. So in IN order, I consider everything right to A is at it's right sub tree & so for left.
* Now, I consider A's left sub tree. It has BDC. Again from POST order, I conclude that B is root.
* Now, again consider B's sub tree. It has contents DC & POST order, C has to be at root. So now I get C at root. But where to place C, at B's left or right ? It's where I am getting stuck now.

Same happening with A's right sub tree also. I place E as root of A's right sub tree. Then I conclude element below should be F, but does it come at right or left of E ?

I want to know how to tackle this problem & also is there any better approach for this to do.

# Answer
> 1 votes
You are doing well. From the postorder determine the root, from the inorder determine which letters are in the left and right subtrees. Once you have done that, you can proceed in the same way for the subtrees.

In the example you start with postorder DCBGFE A and inorder BDC A FGE.

Using postorder you determine the root as A, and using inorder split the letters into left BDC and FGE. Thus (1) the left subtree has postorder DCB and inorder BDC while (2) the right subtree has postorder GFE and inorder FGE.

Let us look at left subtree (1) which you mention in your question. The root is B, and *both* DC follow to B in the inorder and thus are *right* from B. How to place them. This tiny subtree has postorder DC and inorder DC. Hence its root is C, and D is before C in the inorder, and is in the left subtree of C.

---
Tags: binary-trees
---


title: What is prefix monotonicity?

text:
# Question
Title: What is prefix monotonicity?
I have a background in computer architecture and only cursory understanding of process networks. For a paper I am writing I need to understand prefix monotonicity properly.

For now I have "a stream transformer is prefix monotonic if its output for a given input record r is dependent only on the input stream up to and including r, and independent from whether r is the last record in the stream". But this was gathered by word-of-mouth and I am not sure it is the proper approach.

I would welcome suggestions for:

* proper formal background and definitions;
* useful analogies to explain the concept to a newcomer (the audience of the paper needs to understand prefix monotonicity but may not be knowledgeable with TCS).

# Answer
This publication provides a definition of prefix monotonicity: link

Definition:

*"Prefix monotonicity reflects a basic property of communicating systems: assume we have observed a finite sequence of output messages for a corresponding finite sequence of input messages. Then if we observe additional input (thus the old input sequence is a prefix of the extended one) we may just observe additional output (thus the old output sequence is a prefix of the extended one). Prefix monotonicity provides a notion of causality between input and output. It reflects the stepwise consumption of input and production of output and guarantees the existence of least fixed points, which is mandatory for giving meaning to communication feedback loops."*
> 1 votes

---
Tags: reference-request, terminology, nondeterminism
---


# Question
Title: Regularity of the exact middle of words from a regular language
Let $L$ be a regular language.
Is the language $L\_2 = \\{y : \exists x,z\ \ s.t.|x|=|z|\ and\ xyz \in L \\}$ regular?

I know it's very similar to the question here, but the catch is that it's not a simple substring of a word in a regular language, but rather an "exact middle" - we have to count the prefix and suffix length.

Therefore, I assume it's not regular, but I couldn't find a way to prove it. I also couldn't think of any way to modify the NFA of $L$ to accept $L\_2$.

# Answer
> 6 votes
Hint: Consider some DFA for $L$. For every $n \geq 0$, let $A\_n$ be the set of states $s$ such that there is *some* word of length $n$ which leads the DFA from the initial state to $s$. Let $B\_n$ be the set of states $t$ such that there is *some* word of length $n$ which leads the DFA from $t$ to an accepting state. Finally, for any two states $s,t$, let $R\_{s,t}$ be the (regular) set of words leading the DFA from $s$ to $t$. We have $$ L\_2 = \bigcup\_{n \geq 0} \bigcup\_{\substack{s \in A\_n \\ t \in B\_n}} R\_{s,t}. $$ Since there are only finitely many possibilities for $s,t$, the union is in fact finite, and so regular.

# Answer
> 3 votes
Let $D = (Q, Σ, δ, q\_0, F)$ be a DFA for $L$. Without loss of generality, assume $q\_S, q\_F \notin Q$. We construct a ε-NFA $N = (Q ∪ \\{q\_S, q\_F\\}, Σ, Δ, q\_S, \\{q\_F\\})$ for $L\_2$ the following way:

Find each path in $D$ from $q\_0$ to any $f ∈ F$. For each such path $p\_k: q\_0 = q\_{k,0} \xrightarrow{α\_{k,1}} q\_{k,1} \xrightarrow{α\_{k,2}} … \xrightarrow{α\_{k,i}} q\_{k,i} \xrightarrow{α\_{k,i+1}} … \xrightarrow{α\_{k,n\_k}} q\_{k,n\_k}$ construct the paths $p\_k^{(i)} : q\_{k,i} \xrightarrow{α\_{k,i+1}} q\_{k,i+1} \xrightarrow{α\_{k,i+2}} … \xrightarrow{α\_{k,n\_k-i}} q\_{k,n\_k-i}$ for $0 \le i \le \frac{n\_k}2$ (i.e. constuct all “middle parts“ of the path). This can be done effectively. Construct $Δ$ by combining all these paths, together with:

* $(q\_S, ε, q\_{k,i})$ for all $i$ as above
* $(q\_{k, n\_k-i}, ε, q\_F)$ for all $i$ as above

$L(N)$ is regular by construction.

Proof sketch that $L(N) = L\_2$: Let $w ∈ L(N)$. By construction we know that $w$ must match at least on of the paths $p\_k^{(i)}$ above. Each of this path belongs to a path in $D$, which contains an additional prefix and suffix of length $i$. Choose $x$ as the word described by this prefix and $y$ the one described by the suffix. We find that $xwy ∈ L$, with $|x| = |y| = i$. With similar reasoning we find for each $w ∈ L\_2$ a path in $N$. Let $i$ be the length of $x$ and $y$ belonging to $w$. $p\_k^{(i)}$ for some $k$ forms $w$.

Thus $L(N) = L\_2$.

---
Tags: formal-languages, regular-languages, closure-properties
---


# Question
Title: Giving a regular grammar for the language
I am trying to brush up on my regular grammar knowledge to prepare for an interview, and I just am not able to solve this problem at all. This is NOT for homework, it is merely me trying to solve this.

I want to give a regular grammar for the language of the finite automaton whose screenshot is below, please help me, and if you can, a step by step answer would be of great assistance. Thank you!

# Answer
> 4 votes
That's fairly easy. Just take a non-terminal X and add the rule $X\to aY$ where $a$ is the label on the arrow from $X$ to $Y$ if $X$ is not final; if it's final add a rule like: $X\to \epsilon$ as well. Do that for every non-terminal and you get a right-regular grammar.

Here is a right-regular grammar for the given automaton:

$A \to 1 A$

$A \to 0 B$

$B \to 1 A$

$B \to 0 C$

$C \to 0 C$

$C \to 1 C$

$C \to \epsilon$

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


# Question
Title: How to generate a pushdown automata for accepting a language?
I have an exercise in my book to come up with a pushdown automaton accepting a language.

The exercise is to come up with a state diagram for the PDA accepting the language of all odd-length strings over $\\{a, b\\}$ with middle symbol $a$.

Here's what I have so far...

I wasn't sure how many states I needed, but I was thinking 3. State $q\_0$ for pushing symbols onto the stack until reaching the middle symbol, $q\_1$ for after middle symbol is found, and state $q\_2$ the accepting state. I think in $q\_1$ I need to cancel out input symbols from the stack with the input. I don't know how to account for the string being odd length, also.

Is there a smart, systematic way to do this?

# Answer
Designing an PDA (or a NFA, DFA, or any other automaton) is essentially *programming* (in a weird, extremely limited language). Just as there is no sure-fire way to write a program from some description, there isn't for automata either. The only way of becomming proficient is to practice. You'll find plenty examples here...

For some cases there is a way of translating a more human-readable description of the language into an automaton, like starting with a regular expression and getting an NFA, massage that one and you'll finally get the minimal DFA; or starting with a context free grammar and constructing a PDA. The results aren't always exactly pretty, but guaranteed to work.
> 1 votes

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


# Question
Title: Is induced subgraph isomorphism easy on an infinite subclass?
Is there a sequence of undirected graphs $\\{C\_n\\}\_{n\in \mathbb N}$, where each $C\_n$ has exactly $n$ vertices and the problem

> Given $n$ and a graph $G$, is $C\_n$ an induced subgraph of $G$?

is known to be in class $\mathsf{P}$?

# Answer
> 2 votes
This question has been answered on cstheory.

Digest: Chen,Thurley and Weyer (2008) prove that this problem is $W\[1\]$-hard for every infinite class of graphs.

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


# Question
Title: complexity of finding the hampath of length $k$ in a graph with $n$ vertexes where $k < n$
A simple question:

What would be the complexity of finding whether a hampath of length $k$ exists in a graph with $n$ vertexes where $k \< n$?

Would this be in NP-complete or just NP?

# Answer
> 2 votes
Purely for clarity I'll lay out the definitions first, then give a reduction for your problem, so skipping a little ahead shouldn't cause a problem (if it does, start a bit earlier ;) ).

The two problems:

> **Hamiltonian Path (HP)**
> *Input:* A graph $G$.
> *Question:* Does $G$ contain a path with $|V(G)|$ vertices?
>
> **Not Quite Longest Path (NQLP)**
> *Input:* A graph $G$ and an integer $k \< |V(G)|$.
> *Question:* Does $G$ contain a path on $k$ vertices?

Now, what we want to prove:

> **Lemma 1:** NQLP is $\mathcal{NP}$-complete.

Of course this has two parts, membership and hardness.

> **Proposition 2:** NQLP $\in \mathcal{NP}$

*Proof:* Given an order set of vertices we can easily check that it is of length $k$ and forms a path in $G$. $\Box$

> **Proposition 3:** HP $\leq\_{m}$ NQLP

*Proof:* Let $G$ be an instance of HP and for convenience let $n = |V(G)|$. We construct an instance $(G', k)$ of NQLP by taking $G'$ as $G$ with an additional, disconnected vertex $v$, i.e. $V(G') = V(G)\cup \\{v\\}$ and $E(G') = E(G)$. Thus $|V(G')| = n' = n+1$. We choose $k = n \< n'$. This construction is clearly computable in polynomial time.

Claim: If $G$ has a Hamiltonian path, $G'$ has a path of length $k$.

By definition, the Hamilton path includes all vertices of $G$, as $G'$ has $G$ as an (induced) subgraph, this path exists in $G'$. Moreover it is of length $n = k$.

Claim: If $G'$ has a path of length $k$, $G$ is has a Hamiltonian path.

If $G'$ contains a path of length $k$, it cannot include the added vertex $v$, as it has no incident edges (except the trivial case where $G$ was one vertex, but then we have a symmetry which does our work for us). Therefore it must include every other vertex in $G'$ (as $k = n' -1 = n$), as $G' - v$ is simply $G$, $G$ must be Hamiltonian. $\Box$

*Proof of Lemma 1:* As HP is $\mathcal{NP}$-complete, Prop. 3 proves that NQLP is $\mathcal{NP}$-hard. Then combining Propositions 2 & 3, we have proved Lemma 1. $\Box$

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


# Question
Title: What is the relation between P vs. NP and Nature's ability to solve NP problems efficiently?
I was thinking about how nature can efficiently compute ridiculous (i.e. NP) problems with ease. For example, a quantum system requires a $2^n$ element vector to represent the state, where $n$ is just the number of particles. Nature doesn't need any extra time despite the exponential nature of "solving" this $n$-particle system.

This may not be a wholly valid assumption, but the action principle in physics makes me think that nature always wants to do things the easiest way. If that's not true, then this question is probably moot.

If we found that nature was NOT capable of solving some problems efficiently, does this mean we are doomed in terms of being able to solve NP problems in polynomial time? Are the laws of physics a strong enough weapon for tackling P vs. NP? Is the converse of the first question/assertion also true (if nature can do it, then there must be a way for us to as well)?

# Answer
Here are five remarks that might be helpful to you:

1. The current belief is that, despite the exponentiality of the wavefunction, quantum mechanics will *not* let us solve NP-complete problems in polynomial time (though it famously *does* let us solve certain "special" NP problems, like factoring and discrete logarithms). The basic difficulty is that, even if a solution to an NP problem is "somewhere" in the wavefunction, that isn't useful if a measurement will only reveal that solution with exponentially-small probability. To get a *useful* quantum algorithm, you need to use quantum interference to make the correct answer observed with high probability, and it's only known how to get an exponential speedup that way (compared to the best-known classical algorithm) for a few special problems like factoring.
2. The action principle doesn't imply that Nature has any magical minimization powers. The easiest way to see that is that any physical law formulated in terms of the action principle, can *also* be formulated in terms of the ordinary time-evolution of a state, without reference to anything being minimized.
3. If P=NP, then certainly NP-complete problems can be solved in polynomial time in the physical universe, since universal Turing computers exist (you're using one now). However, the converse direction is far from obvious! For example, even if you assume P≠NP, it's still *logically* possible (if very unlikely) that quantum computers could solve NP-complete problems in polynomial time.
4. The mere assumption that there are *some* problems that we can't solve efficiently, certainly doesn't imply that NP-complete problems have to be among those problems! (Maybe it will turn out that quantum gravity lets us solve NP-complete problems in linear time, but the *PSPACE*-complete problems still take exponential time... :-D )
5. For whatever it's worth, my money is firmly on the conjecture not only that P≠NP, but also that NP-complete problems are intractable in the physical universe---using quantum computers, analog computers, "black hole computers," or any other resource. For more about my reasons why, you might enjoy my old survey article NP-complete Problems and Physical Reality
> 21 votes

# Answer
this question is basically asking about the field of natural computing which has many interesting angles/directions. here's a nice survey article: Fundamentals of natural computing: an overview by de Castro.

also these areas are basically open questions in the field of computing and physics and subject to an inherent "uncertainty principle" in that they may conceivably never be definitively answered for various reasons. there are many different physical computation systems, new ones are discovered over time (eg DNA computing is a relatively young area), and we cant be sure that we've found them all \[and from experience/history its unlikely that we have\].

also the extreme limits of physics are applicable \[eg wrt black holes etc\] and these stretch the theories of physics to the limits! (see eg "what is the volume of information") theoretical physicists generally acknowledge that there are aspects of physical reality that are not covered by human knowledge and \[mathematical\] models esp at the extremes.

there are some strongly held/defended, possibly unprovable beliefs however among researchers such that they might be called "theses" in the same sense of the Church-Turing thesis.\[1\] some authorities refer to a "polynomial-time" Church-Turing thesis related to your question(s). there are also references to the Strong CT thesis:

> any computing device can be simulated by TMs with at worst a polynomial slowdown.

or the Extended CT thesis \[Parberry\] \[3\]:

> Time on all "reasonable" machine models is related by a polynomial.

in short the research and writing in this general area is not settled; its active/ongoing and subject to high controversy. there is some reference on wikipedia\[4\] but otherwise have not seen a nice survey article on the subject, only many different papers that tend to advocate certain points of view. also note there is very strong current debate/controversy in QM computing field on feasibility (wrt inherent noise) & viability etc.\[5\]

\[1\] Physics and the Church-Turing thesis mathoverflow

\[2\] what would it mean to disprove the CT thesis cstheory.se

\[3\] extended CT thesis cstheory.se

\[4\] Church-Turing thesis variations, wikipedia

\[5\] State of the art and prospects for QM computing Dyakonov
> 3 votes

# Answer
I had a neural computation professor once that pointed out an excellent example of how "analog" techniques could be used on embarrassingly parallel problems to reduce the asymptotic bound of a computation:

Take a bundle of sticks of different sizes. There are many algorithmic ways to sort that bundle of sticks from longest to shortest with O(n\*log(n)). An "analog" way to sort that bundle of sticks would be to stand them on end and let the sticks rest one end on a table (1 step). Now you have all the sticks with one end at the same level against the table. Take your hand and place it on top -- it will hit the longest, remove that stick and repeat for N steps. This process is O(N + 1) which is O(N). The key here was stacking the sticks on end -- a massively parallel solution to order the other ends of the sticks along the z-axis (up).

This is a neat thought experiment and can give an idea how analog solutions can reduce the asymptotic bound of an algorithm in a simple manner. Two huge caveats here:

1) We haven't taken an NP problem to a P problem with this example (more on that later) and

2) if you used N processors to sort N items you could sort the numbers in O(log n) time (with a big constant), so the reduction is not magical. Sometimes the analog resources needed solve a problem in a highly parallel manner are cheap. Another example of a cheap resource would be neurons (biological) for complex learning and pattern recognition.

Neurons can also put the apparent NP =\> P into perspective. NP problems are NP to find the *optimal* solution. You can find a "good enough" solution in P time that will work fine in nature. Evolution selects for highly efficient solutions that are "good enough". Think about how good the average person is at identifying objects in almost O(1) time. That's because there is a lot of parallel processing going on, and your brain still doesn't always come up with the optimal solution. For example, optical illusions, or forgetting where you put your keys (which would easily be O(1) for a computer!).

Another point with NP vs P in nature: solving NP to find the optimal solution is not the same as identifying the optimal solution. Identification of an optimal solution to an NP problem can be done in P time. Again recognition of a "good enough" solution will work rather than an optimal solution. Take the example of protein folding -- this is an example of nature doing all of the above. It takes advantage of molecular interaction forces that all work in parallel (no need for the natural folding "algorithm" to address one atom at a time as a computational algorithm does). Also, there is no guarantee that the (functionally) optimal solution to the protein folding will be found.

There are many examples of diseases due to protein misfolding. As @PeterShor pointed out sometimes the "natural" algorithm doesn't work at all (leading to a thermodynamically optimal solution, but not a functional one). That is where chaperone proteins come in -- they guide the folding into the correct functional form (a thermodynamic *local* minimum). Correctly formed proteins also interact with other proteins for transport to the right location so the "bad" ones (where the heuristic algorithm didn't actually solve the NP problem) are often degraded without being transported anywhere. All of these transports and folding mechanisms are happening with massive parallel pipes. Multiple transcription and processing mechanisms are simultaneously converting DNA-\>RNA-\>Protein at different points on a gene sequence. Every cell in your body is doing the same (but with different chemical messages about what to produce).

So, in short: How does nature do it? Tricks and Parallelism. Generally it's not actually turning an NP problem into P, it's just making it look easy.
> 2 votes

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


# Question
Title: Does $O(1) * o(1)$ equal a $o(1)$ function?
Say I have two functions $f(x) = O(1)$ and $g(x) = o(1)$. Let $h(x) = f(x)g(x)$. Is $h(x) = o(1)$?

By definition of small-o $g(x)$ must approach 0 as $x \rightarrow \infty$, so I think yes. However, how can I formally prove it? Is my intuition correct?

# Answer
> 5 votes
The formal proof would proceed along these lines: Let $C$ be a constant such that $f(n)\le C$ for all $n$ (such a constant exists since $f(n)\in O(1)$). Then $$\lim\_{n\to \infty}f(n)\cdot g(n)\le C\cdot \lim\_{n\to \infty}g(n)=0$$ So $f(n)g(n)\in o(1)$.

---
Tags: asymptotics
---


# Question
Title: Why S=1, R=1 Is forbidden in RS-Flip Flop
I have come across about RS Flip Flop & I have tried implementing that on a simulator & using actual logic gates. But I'm still not sure whether I have correctly understood the case unstable or the forbidden case S=1, R=1 in Flip flop. Can anyone tell me what exactly is that?

By the way I have used 2-INPUT NAND Gates to implement the flip Flop. What is the difference between the NAND Gate Flip Flop & NOR Gate Flip Flop, ?

# Answer
> 0 votes
This question has an accepted answer on another site.

Digest: If you had both inputs set to $1$, both outputs would be $0$ but they are supposed to be complementary.

---
Tags: logic, circuits, sequential-circuit
---


# Question
Title: WP pseudocode for Dijkstra does not work
I mean Dijkstra's algorithm for the shortest path.

In all descriptions that I saw (including wikipedia), on every step, it always selects the nearest neighbor based on examining their weights.

Imagine that we have following paths from source A to destination B (I will list weights of different paths, not full graph - for brevity):

# 1: $$A {19\atop\longrightarrow} A\_1 {2\atop \longrightarrow} A\_2{2\atop \longrightarrow} A\_3{10\atop \longrightarrow} B$$

# 2: $$A {5\atop\longrightarrow} A\_4 {10\atop \longrightarrow} A\_5{10\atop \longrightarrow} A\_6{5\atop \longrightarrow} B$$

# 3: $$A {2\atop\longrightarrow} A\_7 {15\atop \longrightarrow} A\_8{15\atop \longrightarrow} A\_9{10\atop \longrightarrow} A\_{10} {10\atop \longrightarrow} B$$

If Dijkstra always select the neighbor with smallest weight, it will always go for #3 - although it is the heaviest path!

Where am I wrong? Does anybody has a 'working' pseudo-code for Dijkstra algorithm?

# Answer
> 2 votes
What's wrong with the Wikipedia pseudo code?

The Dijkstra algorithm according to their pseudo code just looks at $A\_7$ **first** , then $A\_4, A\_5 \dots$

The rule of choice expresses a **priority**. If necessary every vertex of $G$ is considered. It takes some time until $A\_1$ is considered, but it eventually happens:

1. $A$ is considered (Line 12)
2. New distances for $A\_1,A\_4,A\_7$ are $19,5,2$ (Lines 20 and 24)
3. $A\_7$ is now minimal and the next vertex (Line 12)
4. The new distance for $A\_8$ is $17$ (Line 20 and 24)
5. $A\_4$ is now minimal (Line 12)
6. The new distance for $A\_5$ is $15$ (Line 20 and 24)
7. $A\_5$ is now minimal (Line 12)
8. The new distance for $A\_6$ is $25$ (Line 20 and 24)
9. $A\_8$ is now minimal (Line 12)
10. The new distance for $A\_9$ is $32$ (Line 20 and 24)
11. **$A\_1$ is now minimal (Line 12)**
12. $\dots$

---
Tags: algorithms, shortest-path
---


# Question
Title: Two-State Turing Machine for Parenthesis Matching
In college we have been learning about theory of computation in general and Turing machines more specifically. One of the great theoretical results is that at the cost of a potentially large alphabet (symbols), you can reduce the number of states down to only 2.

I was looking for examples of different Turing Machines and a common example presented is the Parenthesis matcher/checker. Essentially it checks if a string of parentheses, e.g `(()()()))()()()` is balanced (the previous example would return 0 for unbalanced).

Try as I may I can only get this to be a three state machine. I would love to know if anyone can reduce this down to the theoretical minimum of 2 and what their approach/states/symbols was!

Just to clarify, the parentheses are "sandwiched" between blank tape so in the above example `- - - - - - - (()()()))()()() - - - - - - -` would be the input on the tape. The alphabet would include `(`,`)`,`1`,`0`,`-`, and the `*halt*` state does not count as a state.

For reference the three state approach I have is as follows: Description of states:

```
 State s1: Looks for Closing parenthesis

 State s2: Looks for Open parenthesis

 State s3: Checks the tape to ensure everything is matched

 Symbols: ),(,X

```

Transitions Listed as:

```
Action: State Symbol NewState WriteSymbol Motion

```

```
// Termination behavior
Action: s2 - *halt* 0  -
Action: s1 -  s3    -  r

//Transitions of TM
Action: s1 (  s1  (   l
Action: s1 )  s2  X  r
Action: s1 X  s1  X  l
Action: s2 ( s1 X  l
Action: s2 X  s2 X r
Action: s3 (  *halt* 0 -
Action: s3 X  s3     X r
Action: s3 -  *halt* 1 -

```

Forgive the informal way of writing all this down. I am still learning the theoretical constructs behind this.

# Answer
> 8 votes
Dumb answer: your result promises that there is a *universal* Turing machine with two states. Construct *any* TM for the Dyck language, compute its index and hardcode it into the universal machine.

But that's of course not very satisfying. Your approach actually works if you "trick" the difference between moving left and moving right while matching pairs of parenthesis into an extension of the alphabet. We need $\\{\\#,(,),x\\}$ and marked versions $\hat{a}$ of all symbols $a$.

* The initial state $q\_0$ works as follows.

When finding unmarked symbols, move to the right until the first $)$ is found. While doing so, overwrite all symbols $a$ with $\hat{a}$. Overwrite the found $)$ with $\hat{x}$.
If there is no $)$, i.e. we hit the gap symbol $\\#$, overwrite it with $\hat{x}$ and switch to $q\_1$.

When finding marked symbols, move to the left until the first $\hat{(}$ is found, overwriting all passed (marked) symbols with their unmarked variants. Overwrite the found $\hat{(}$ with $x$.
If we find a $\hat{)}$ or $\\#$ first, loop/reject¹.
* In $q\_1$, we check that everything has been matched; there may still be prefixes of the form $\hat{(}^+$ on the tape. That is, move to the left as long as we finde $\hat{x}$. If we thus find $\\#$, accept; if we find any other symbol but $\hat{x}$ first, loop/reject.

---

1. This is correct since the machine matches inside-out; in a legal input, there are only $x$ between the pair of parentheses currently being matched.

# Answer
> 8 votes
Just a "source code" compendium of Raphael's answer: this a working version that uses the same trick (on state q1) and has tape alphabet:
`_ ( ) [ { / \`  (where $\\\_$ is the initial blank symbol)

```
q0:  _ -> accept  // accept on empty string and on balanced parenthesis
     ( -> {,R,q1  // mark the first open "(" with "{" and goto q1
     ) -> reject  // reject if found unbalanced ")"
     \ -> /,L,q0  // go left
     / -> \,R,q0  // go right

q1:  ( -> [,R,q1  // replace "(" with "[" and continue ...
     ) -> /,L,q1  // ... until first ")", replace it with "/" and goto left
     [ -> \,R,q1  // found matching "(" bracket, goto right and search for another ")"
     _ -> reject  // no ")" found for the first "{", reject
     { -> \,R,q0  // this must be the last match, goto q0 and check if it is true
     \ -> /,L,q1  // go left
     / -> \,R,q1  // go right

```

You can see it at work using a Turing machine online simulator; the source code is:

```
0 _ Y r halt
0 ( { r 1
0 ) N r halt
0 \ / l 0
0 / \ r 0
1 ( [ r 1
1 ) / l 1
1 [ \ r 1
1 _ N r halt
1 { \ r 0
1 \ / l 1
1 / \ r 1

```

A final note: if you want to see how this technique can be pushed to the limit, read (and try to understand :-) the construction of the Universal Turing machine with 2 states and 18 symbols by Y. Rogozhin in "Small universal Turing machines"

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


# Question
Title: Program synthesis, decidability and the halting problem
I was reading an answer to a recent question, and sort of a strange, ephemeral thought came to mind. My asking this might betray either that my theory chops are seriously lacking (mostly true) or that it's just too early for me to read this site. Now, with the disclaimer out of the way...

It is a well-known result it computability theory that the halting problem cannot be decided for TMs. However, this doesn't exclude the possibility that there exist machines that can solve the halting problem for certain classes of machines (just not all of them).

Consider the set of all decidable problems. For each problem, there exist infinitely many TMs which decide that language. Could the following be possible

* There is a TM that decides the halting problem for a subset $S$ of Turing machines; and
* All decidable problems are decided by at least one Turing machine in $S$?

Of course, finding the Turing machine in $S$ may not be computable itself; but we ignore that problem.

EDIT: Based on Shaull's answer below, it seems that either (a) this idea is too ill-specified to be meaningful or (b) my previous attempt wasn't quite on the mark. As I try to elaborate in the comments to Shaull's answer, my intent isn't that we're guaranteed that the input TM is in $S$. What I really meant by my question is whether there could exist such an $S$, *such that membership in $S$ is a decidable problem*. The program to solve the halting problem for $S$ would, presumably, write "invalid input" on the tape or something when given an input that it recognizes as not being in $S$. When I formulate it like that, I'm not sure whether this allows us to solve the halting problem or not, or whether Rice's theorem applies (is decidability a semantic property of a language w.r.t. Rice's theorem?)

# Answer
> 8 votes
I think there may be a problem with the formulation of the problem.

Consider the set $S=\\{M: M $ is a decider of its language $\\}$. The halting problem is decidable for this set (that is, if we are promised that the input is in this set). In fact, it is trivial (the machines in $S$ always halt).

Also, clearly every decidable language is in $S$.

EDIT: Based on the changes in the question - indeed, membership in $S$ would be undecidable: if $S$ contains a machine for each decidable language, then $S\neq \emptyset$. Thus, by Rice's theorem, if $S$ is decidable then $S$ contains every machine, but then the halting problem is undecidable on $S$.

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


# Question
Title: Chomsky form for language of single alphabet member
I'm a bit confused as to how to represent the Chomsky form for the language L that generates all strings with the alphabet {a}

My approach was

```
S -> AB | e
A -> a

```

Now here's the part I'm confused, how do I represent B? If B -\> a then I get only even strings, if B -\> e then it's not in normal form. :| Any help would be appreciated.

# Answer
The grammar is similar to what you say: $$ S \rightarrow S S \mid a $$ This can't generate $\epsilon$, which any true CFG can't.
> 2 votes

---
Tags: formal-languages, regular-languages, formal-grammars, normal-forms
---


# Question
Title: VAR autoincrement with constant space consumption for super large tables
Assume there was a database system that had a data type called `VARINT` or some variant that allowed instead of fixed-length `INT`s regardless of value, a `1` would only take 1 `BIT` (`1`), `2` would take 2 `BIT`s (`10`), etc.

In this perfect world, a `VARINT` could be used to `autoincrement` a `PRIMARY` column. However, there's still the issue of the field growing in size, so the "older" parts of this `TABLE` would be very fast, but the "younger" parts would get slower and slower.

What counting system could be used to hold the space consumed constant and small or at least grow at a much slower rate?

# Answer
> 0 votes
If you want an ID (i.e. unique label, whether number or not) which is stored as a binary (or $k$-ary) string you will have at least logarithmic growth, because with $o(\log n)$ bits you can't identify more than $k^{o(\log n)}=o(n)$ objects. So you can't do much better.

You could however map the old IDs to new IDs every time the size of the table doubles. If the entry #$2^m$ is inserted, the old IDs become $\mathrm{id}'=2^{m+1}+\mathrm{id}$ and the younger elements get shorter IDs. This only works if you don't use the IDs elsewhere (major drawback for a `PRIMARY`) and you have a reason to believe that newer entries get requested more often than older ones.

Finally one may ask whether you really need `big integers` for some kind of ID. According to this there are $\approx 10^{80}\leq 2^{267}$ atoms in the observable universe, so a kilobit sized ID will do for most purposes.

---
Tags: integers, database-theory, performance
---


title: How to detect sunshine on a photo

text:
# Question
Title: How to detect sunshine on a photo
How would you algorithmically detect for any given photo whether the sun was shining when the picture was taken?

**Examples**

A sample from this webcam at a mountain top:

Clearly the sun is shining.

In this other sample it's far less obvious:

One could probably detect fairly easy whether it's foggy by trying to identify the tiny church spire on the chapel in the center. However, knowing very little about image processing I'd be surprised if there was a (combination of) algorithm that could reliably tell if there's sunshine or not.

# Answer
If you can access the **meta-data** you could apply a number of heuristics:

1. Check the **white-balance** setting, the camera has chosen for the photo. Basically it indicates the color temperature of the light at the time the photo was taken. Usually sunlight is around 5500 Kelvin. Indoor lighting or cloudy days, usually have different temperatures.
2. Check the **exposure settings**. Usually when the sun shines, there is more light available, so this influences the following settings:

1. A lower shutter speed
    2. A lower ISO setting
    3. A higher f-value

In the old days of photography, the Sunny 16 rule was used to estimate exposure. And you could use it, together with the information in the list above, to check if the photo was taken during the day.
3. Check if a **flash** fired or not.
4. Check the time the **photo was taken**. Assuming the user has configured the clock, you might immediately remove photos shot at night.

If however you want to approach this problem simply from an image-processing point of view. I can say that sunlight has usually **higher contrast**, and harsher edges. Therefore **histogram analysis** and finding **harsh edges** might give a good indication.

Assuming the photos you are processing are in a **Raw Image Format** you could apply the same **white-balance** trick described above. This however *does not work* for standard images like **jpeg** or png. This because the image processor on the camera already compensates for the shift in color temperature, and bakes the result into the final image, merely recording the *wb-setting* it in the metadata.
> 10 votes

---
Tags: algorithms, image-processing
---


title: Prize collecting steiner tree

text:
# Question
Title: Prize collecting steiner tree
I'm reading about the **prize collecting steiner tree** problem and an approximation algorithm that uses randomization to set a lower bound on the optimal solution (see Chapter 5.7 in The Design of Approximation Algorithms by Williamson and Shmoys). I don't understand the second line in the proof for Lemma 5.16: .

It seems to me that $V-V(T)$ is a much larger set than $U$. So, how can the total penalty for this set be upper bounded by the total penalty of a set that is much smaller?

# Answer
$T$ is a tree that connects the chosen subset of terminals $U$. Thus $U$ is a subset of $V(T)$, and $V \setminus V(T)$ is a subset of $V \setminus U$ (we're summing $i$ not in $U$).
> 4 votes

---
Tags: algorithm-analysis, optimization, approximation, trees
---


# Question
Title: Prove that if $\mathsf{P^k}=\mathsf{NP}$ then $\mathsf{NP}=\mathsf{co\text{-}NP}$
Prove if a oracle machine $K$ is given with $\mathsf{P^k}=\mathsf{NP}$ then $\mathsf{NP}=\mathsf{co\text{-}NP}$.

---

Lets assume that $\mathsf{P^k}=\mathsf{NP}$ then $\mathsf{co\text{-}P^k}=\mathsf{co\text{-}NP}$. I am stuck here, I don't know how to prove this. Can someone help?

I know that $\mathsf{P}=\mathsf{co\text{-}P}$ but can I also say $\mathsf{P^k}=\mathsf{co\text{-}P^k}$ or do I have to prove it ?

# Answer
> 5 votes
Hint: The proof that $\mathsf{P}=\mathsf{co\text{-}P}$ relativizes. That means that if the machines in question are allowed access to some oracle, then the proof goes through. The reason is that the proof just works even when you add the oracle - go over the proof carefully and convince yourself.

"Can I also say that ... or do I have to prove it?" You should be able to answer this yourself. If you can't, go over the definitions a few more times until you really understand what they mean, and then, at the very least, you can say whether "..." follows directly from something that you saw in class, or whether it does not. In the latter case, you should prove it.

In this specific case, given that you already saw a proof of a similarly looking result $\mathsf{P}=\mathsf{co\text{-}P}$, it should seem reasonable to try and see if that same proof generalizes to give $\mathsf{P}^K = \mathsf{co\text{-}P}^K$. In this case it does; in other cases it might not, and then you have to work harder.

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


title: Negligible Function in Cryptography

text:
# Question
Title: Negligible Function in Cryptography
In the field of Cryptography and Computation Complexity there is a notion of negligible function.

I have some difficulties in understanding intuition behind this notion. The following are some definitions from Chapter 9. Cryptography from the textbook Computation Complexity. A modern approach by Arora and Barak with extensive use of negligible function. There my question after every definition about negligible function.

> Before proceeding further, we make a simple definition that will greatly simplify notation throughout this chapter.
>
> **Definition of negligible function**. a function $\epsilon : \mathbb{N} \rightarrow \[0,1\]$ is called negligible if $\epsilon(n)=n^{-\omega(1)}$.
>
> Because negligible functions tend to zero very fast as their input grows, events that happen with negligible probability can be safely ignored in most practical and theoretical settings.

So far so good, it's just the definition of negligible function, the only point is why do we need to care about this function if it *"can be safely ignored".*

> **The notion of computational secure function**.$k \in\_R \\{0,1\\}^n, x \in\_R \\{0,1\\}^m, Pr \[A(E\_k(x))=(i,b) s.t. x\_i=b\] \leq \frac{1}{2}+\epsilon(n)$.

Less intuitive usage of negligible function. As I understood, in general, $A$ can with probability 0.5 guess uniformly distributed $x\_i$, therefore it makes sence to expected lower bound of success to be $\leq \frac{1}{2}$, however it's $\leq \frac{1}{2} + \epsilon(n)$, it we can "safely ignore" $\epsilon(n)$ why to mention it, and the second point is it possible to run $A$ some fixed finite number of times to get probability infinitely close to 1?

> **Definition of one-way function**. $x\in\_R\\{0,1\\}^n, y=f(x), Pr\[A(y)=x' s.t. f(x')=y\] \< \epsilon(n)$

In this case, the usage of negligible function is very intuitive, the success probability is upper bounded by negligible function $\epsilon(n)$. I am not sure how it's correlated with existence of computationally secure encryption scheme (of course =0 is preferable by encryption scheme), however if $\epsilon(n)$ can be safely ignored than it's ok.

The problem is I am not quite understand why do we need negligible function. By mentioning few definition I tried to be more specific about what exactly I don't understand.

I would appreciate if anyone can shed the light on the usage of negligible function

# Answer
If you repeat an Algorithm $A$ with negligible probability $\epsilon(n)$ of success for an input of length $n$ the number of times until the first success happens is a geometrically distributed random variable $S$. The expected value of $S$ is

$$\mathbb{E}(S) = \frac{1}{\epsilon(n)} = n^{\omega(1)} \quad .$$

So an attacker using $A$ polynomial many times (say $p(n)$) can't have non negligible probability of success, which we'll see by comparing expected values. Let $A'$ be the algorithm which repeats $A$ $p(n)$ times and the random variable which represents the number of times $A'$ has to be repeated until the first success shall be named $S'$. Then:

$$\mathbb{E}(S) \leq p(n) \mathbb{E}(S')\quad,$$

so a non negligible success probability for $A'$ would mean a non negligible probability for $A$, since the product of two polynomials is again polynomial. So allowing negligible probabilities does no harm (at least for polynomial bounded adversaries).

This is essentially contains an indirect proof that $p(n)\epsilon(n)$ is still negligible for any polynomial $p$, which can also be proven directly: $p$ is dominated by its largest exponent, so $p(n)\in \mathcal O(n^c)$ for some $c \in\mathbb{N}$. On the other hand $\epsilon(n)\in o(n^{-d})$ for all $d\in\mathbb{N}$. Define $d'=d-c$ and you'll get $\epsilon(n)\in o(n^{-(d'+c)})$ for all $d'\in\mathbb{N}$. So $p(n)\epsilon(n)\in o(n^{-(d'+c)})\mathcal O(n^c)=o(n^{-d'})$ for all $d'\in\mathbb{N}$, which is again negligible.

If you insist on a probability of $0$ (or $\frac{1}{2}$ in the case of distinguishers) many applications become (nearly) impossible. Consider a cryptographic hash function $h$ and an unknown argument $x$. The probability of finding a preimage $x'$ s.t. $h(x')=h(x)$ taken over all $x$ can't be $0$, because testing all possible inputs will lead to success eventually. You could however choose to limit the probability with $2^{-n^{\Omega(1)}}$ or similar and call only those functions negligible. But most of the time only unbounded adversaries or efficient (i.e. polynomially bounded) adversaries are considered, so the different notions wouldn't matter, as an efficient adversary can break none and and unbounded can break both.
> 5 votes

---
Tags: complexity-theory, probability-theory, cryptography
---


title: CFG for $\{a^i b^j : 2 i<j\}$

text:
# Question
Title: CFG for $\{a^i b^j : 2 i<j\}$
So I have a question:

Give a CFG for $\\{a^i b^j : 2 i\<j\\}$

And this is my approach:

$S\to AB$

$A\to aAb\mid \varepsilon$

$B\to b \mid bB$

A confirmation, or correction, along with how you tested(and tips for testing future of my problems) will be greatly appreciated thanks.

# Answer
You can derive $aabbb$ which is not in the language, so your grammar is wrong.

How did I find this? I observed that $A \Rightarrow^\* a^ib^i$ and $B \Rightarrow^\* b^j$ for all $i \geq 0$, $j \> 0$. It's clear that this is wrong, and I looked for the smallest counter-example.

You need to ensure that more than double as many $b$'s as $a$'s are generated.
> 0 votes

---
Tags: context-free, formal-grammars, check-my-answer
---


# Question
Title: Mathmatical way to represent an image kernel?
How to represent the calculation in this image mathematically?

For example: With the discrete convolution $(f * g)\[n\]\ \stackrel{\mathrm{}}{=}\ \sum\_{m=-\infty}^\infty f\[m\]\\, g\[n - m\]$ and Fourier transform.

# Answer
> 2 votes
Applying the filter corresponds to two-dimensional convolution: $$ (f \ast g)(x,y) = \sum\_{i=-\infty}^\infty \sum\_{j=-\infty}^\infty f(i,j) g(x-i,y-j). $$ In our case, $f$ is the filter, $g$ is the image, and $f \ast g$ is the filtered image. Since the support of $f$ (the number of non-zero entries) is finite, the sums in question are finite, and the convolution is well-defined. More explicitly, we have $f(0,0) = 5$, $f(-1,0) = f(1,0) = f(0,-1) = f(0,1) = -1$, and $f(i,j) = 0$ otherwise.

Edit 1: Here is another way of viewing it. This time, $f$ is the image and $g$ is the filter, defined by $g(0,0) = 5$, $g(-1,0) = g(1,0) = g(0,-1) = g(0,1) = -1$, and $g(i,j) = 0$. The same formula for filtering, $f \ast g$, works before, since $f \ast g = g \ast f$. In other words, the filtered image $h$ is given by the formula $$ h(x,y) = \sum\_{i=-\infty}^\infty \sum\_{j=-\infty}^\infty g(i,j) f(x-i,y-j). $$

Edit 2: We can rewrite the convolution as a product of generating functions. Suppose the original image is given by $$ F = \sum\_x \sum\_y f(x,y) X^x Y^y. $$ The filter $G$ in your case is given by $$ G = 5 - X - X^{-1} - Y - Y^{-1}. $$ Filtering the image corresponds to the multiplication $H = FG$, and the filtered image $h$ can be extracted as $$ H = \sum\_x \sum\_y h(x,y) X^x Y^y. $$

Edit 3: Going back to the notation of Edit 1, in terms of the two-dimensional Fourier transform, we have $$ \hat{h} = \hat{f} \hat{g}, $$ where the multiplication on the right is pointwise. So filtering corresponds to multiplying each Fourier coefficient by some fixed amount, which depends on the filter.

Edit 4: In this particular case, the relation between the original image $f$ and the filtered image $h$ is $$ h(x,y) = 5f(x,y) - f(x-1,y) - f(x+1,y) - f(x,y-1) - f(x,y+1). $$

Edit 5: The image you posted handles the boundary issue by extending the first and last rows and columns past the boundary. For example, $f(x,-1) = f(x,0)$, $f(-1,y) = f(0,y)$ and $f(-1,-1) = f(0,0)$.

# Answer
> -1 votes
it seems a classical image filtering technique, should be in textbooks, try fundamentals of digital image processing by Anil K Jain

the depicted filter seems like a discrete laplacian (altough the central number is 5 instead 4), have a look at http://en.wikipedia.org/wiki/Discrete\_Laplace\_operator

---
Tags: image-processing
---


# Question
Title: What is the exact difference between a latch & a flipflop?
From what I have understood :

1. A Flip Flop is a clocked latch i.e. flip flop = latch + clock
2. Latch continuously checks for inputs & changes the output whenever there is a change in input
3. Flip Flop also continuously checks input, but changes the output time determined by clock. \[so, even though if inputs are changed, it may not change the output at the same time\]
4. A latch with enable \[i.e. gated latch\], is different from that of clocked latch.

I am reading from Digital Logic by Morris Mano & Wikipedia.

# Answer
> 7 votes
As far as I understand, the difference is indeed the clock/enable.

A flip-flop samples the inputs only at a clock event (rising edge, etc.)

A Latch samples the inputs continuously *whenever it is enabled*, that is, only when the enable signal is on. (or otherwise, it would be a wire, not a latch).

---
Tags: computer-architecture, sequential-circuit, digital-circuits
---


# Question
Title: Free and bound variables in a lambda-calculus term
For this term: $\lambda x.(f (g x))$, what are the free and bound variables?

I'm confused as to how to expand this so it will be easier to see. If I expand this will it be $\lambda x. \lambda f. \lambda g$?

# Answer
The free variables in the term you give are $f$ and $g$, $x$ is bound by the $\lambda$-binder.

I am also confused what you mean by "expanding"? But I guess you want to abstract away those free variables. If that is true, then you will get $\lambda x . \lambda f . \lambda g . f\ (g\ x)$ (or with the parameters permuted in another way.)
> 1 votes

---
Tags: terminology, lambda-calculus, variable-binding
---


title: Assign unique integer keys to sets

text:
# Question
Title: Assign unique integer keys to sets
I am given a list of $n\>1$ arrays, where each array has fairly small number of elements (rarely above $5$). Also $n$ is quite small in practice (around $6$).

My problem is that I would like to efficiently map each element product to unique integer. Also, I would like to efficiently compute the integer, when I change the order of the arrays in the list.

I was thinking something in the line of integer factorization.

Take first $n$ primes ($p\_1, p\_2, ..., p\_n$) and remeber the index of the array in the original list with $ind: A \rightarrow \mathbb{N}$. So the initial function would be $ind(A\_i)=i$.

Also we denote with $a\_{i,j}$ the $j$-th element of the $i$-th array in the list. So the function $F:A\_1 \times A\_2 \times \ldots \times A\_n \rightarrow \mathbb{N}$ would be:

$$F(a\_{1,i\_1}, a\_{2,i\_2}, \ldots, a\_{n,i\_n})=\prod\_{j=1}^{j=n}p\_{ind(A\_i)}^{i\_j}$$

In more common words, we initially assign a prime number $p\_i$ to array $i$ and raise $p\_i$ to the index of the element in array $i$.

This guarantees us the uniqueness and also if we change the order of the arrays in the list, we just need to change the $ind$ function. But the problem here is that these products are fairly large and will overflow soon enough (even with using doubles).

Do you have any better idea how to enumerate these products without the large number constraint? I am implementing this in Java and I really would not like to use BigInteger implementation.

# Answer
Based on your description, I take it that an element product is taking one element from each array and multiplying?

You don't really need to multiply or use prime numbers which might overflow (but not too much for your constrains I suppose, and is a cute solution :-)).

Suppose the arrays were of fixed size $k$ (You can pad the arrays to achieve this, and based on your constraints, won't be too much of a problem).

Then you want to map all possible tuples $(x\_1, x\_2, \dots x\_n)$ where $0 \le x\_i \lt k$ to unique integers.

The mapping you need: Interpret the tuple as an integer in base-$k$.

If arrays are shuffled you can still change the $ind$ function and remap the digits according to that.

(or did you try that and didn't work for some reason?)
> 1 votes

# Answer
You want an injection between your element space and the naturals. Why not take the oldest one that happens to be a bijection, the Cantor pairing function.

Its basic form is defined to map $\mathbb{N^2}$ to $\mathbb{N}$:

$\qquad\displaystyle \pi(k\_1,k\_2) = \frac{1}{2}(k\_1 + k\_2)(k\_1 + k\_2 + 1)+k\_2$.

It readily extends to $\mathbb{N}^k$:

$\qquad \pi^{(n)}(k\_1, \ldots, k\_{n-1}, k\_n) = \pi ( \pi^{(n-1)}(k\_1, \ldots, k\_{n-1}) , k\_n)$.

The Wikipedia article explains how to invert the function.

Now, in your case, $n$ is unknown. That's not a problem; we can extend above $\pi$ easily to enumerate $\mathbb{N}^+ = \bigcup\_{n \geq 1} \mathbb{N}^n$ by encoding $n$ -- here the array's length -- as well:

$\qquad \pi^+(a\_1,\dots,a\_n) = \pi^{(n+1)}(a\_1, \dots, a\_n, n)$.

Since it's a bijection into $\mathbb{N}$, values are arguably as small as possible. Also, computing either direction is efficient.

When implementing it, be very carful either way. If you consider arrays over some finite set $A$, there are

$\qquad\displaystyle \sum\_{i=1}^n |A|^i = \frac{|A|^{n+1} - |A|}{|A| - 1}$

many arrays of size at most $n$. $\pi^+$ has to encode them all, so the integers might overflow quickly if $|A|$ and $n$ are not both small.
> 1 votes

---
Tags: enumeration, primes
---


# Question
Title: Proving correctness of the algorithm for convex polygon minimum cost triangulation
I have read many solutions for the minimum cost of triangulation problem and intuitively get the idea , however I am struggling to figure out how to prove it formally. I kind of feel that it has to be proven by induction but I struggle at choosing the right quantity to look at and also at the inductive step portion of the proof.

For example, can you provide a formal proof for the algorithm described here (page 5 problem 6.12).

# Answer
> 1 votes
There are two parts to understanding here.

1. The algorithm is a straight-forward implementation of equation (5) using memoisation.
2. Equation (5) is correct, that is $A\[i,j\]$ is

> the minimum cost triangulation of the polygon spanned by vertices $i,i+1,...,j$

as the author claims. They give a reasoning right there:

> Formulating the subproblem this way we are enumerating all the possible diagonals such that the diagonals do not cross each other. Since we are only considering in clockwise directions, diagonals generated by the subproblems can not cross each other.

They argue that

* all feasible solutions are considered and
    * all considered solutions are feasible.

If this is true, then choosing the minimum out all considered solutions is clearly the correct answer. Proving the bullets now needs insight into the problem, and the author gives the basic idea.

In terms of an induction, what I sketch above amounts to the inductive *step*. The anchor is trivial and covered in the text. The induction hypothesis has to be phrased such that you know for $i,j$ fixed that *all* $A\[i,k\]$ and $A\[k,j\]$ for $k=i,\dots,j$ are optimal.

---
Tags: algorithms, algorithm-analysis, dynamic-programming, recursion, correctness-proof
---


# Question
Title: Optimized algorithm to compare templates of two websites
My task is to compare templates of two websites. I am ready with my algorithm. But it takes too much time to give a final answer. Here, "template" means the way any page presents its contents.

**Example:**

Any shopping website have page of any Shoes, that contains,

```
Images in the left.
Price and Size in the right.
Reviews in the bottom.

```

If two websites are of any specific product, then it returns "Both are from same templates". Example, this link and this link have the same template.

If one website shows any product and another website shows any category, then it shows "No match". Example, this link and this link are from different template.

I think that this algorithm requires some optimization, that's why I am posting this question in this forum.

**My algorithm**

1. Fetch, parse two input URLS and make their DOM trees.
2. Then if any page contains , UL and TABLE , then remove that tag. I done this because, may be two pages contains different number of items.
3. Then, I count number of tags in both URLS. say, initial\_tag1, initial\_tag2.
4. Then, I start removing tags that have same position on corresponding pages and same Id and their below subtree, if that tree has number of nodes less than 10.
5. Then, I start removing tags that have same position on coresponding pages and same Class name and their below subtree, if that tree has number of nodes less than 10..
6. Then, I start removing tags that have no Id ,and No Class name and their below subtree, if that tree has number of nodes less than 10.
7. Steps 4, 5, 6 have (N\*N) complexity. Here, N, is number of tags. \[In this way, in every step DOM tree going to shrink\]
8. When it comes out from this recursion, then I check final\_tag1 and final\_tag2.
9. If final\_tag1 and final\_tag2 is less than initial\_tag1\*(0.2) and initial\_tag2\*(0.2) then I **can** say that `Two URL matched`, otherwise `not`.

I wrote my code in *Java* using *Jsoup* and *Selenium*. I asked before on Stack Overflow, but the answers did not help me.

I think a lot about this algorithm, and I found that removing node from DOM tree is pretty slow process. This may be the culprit for slowing this algorithm.

I discussed with some geeks, and

> they said that use a score for every tag instead of removing them, and add them , and at the end return (score I Got)/(accumulatedPoints) or something similar, and on the basis of that you decide two websites are either similar or not.

But I didn't understand this. So can you explain this statement, or can you give any other algorithm that solves this problem efficiently?

# Answer
> 2 votes
Reading between the lines, here is what I propose. I assume that you are interested in the *structure* of websites, so the first step is to expose this structure.

1. Throw away all non-structure tags as well as attributes (maybe keep `class`) and text. I imagine we would be left with `<div>`, `<table>`, `<ul>`/`<ol>`¹, HTML5 structure tags and little else, depending on coding style.
For the sake of efficiency, use a SAX-style parser for this step.
2. Create a tree of the remaining tags, either directly or in a second run. The structure of this tree should hold the information you want. You may want to cut everything that is nested deeper than some level; the overall structure of some website is likely to be clear from the first five to ten levels.
3. Compare the trees. What is useful here depends heavily on the kind of similarity you want and on the degree of sophistication the used websites display.

Equality of trees would be simplest measure but also coarse. There has been work on tree similarity measures, see e.g. here. Some research may unearth a measure that suits your purpose.

Finetuning the steps will require experiments and will most likely depend on the class of websites you compare.

---

1. You say you remove lists and tables because the may contain different numbers of elements. While that is true, the action is overcompensating since the *occurrence* of a list or table can be significant. Instead, remove all contained tags but keep the main ones. But then again, maybe the templates differ in the amount of columns in some table?

---
Tags: algorithms, efficiency
---


title: Is this graph a hamiltonian graph?

text:
# Question
Title: Is this graph a hamiltonian graph?
I (will, at the end) have a connected, undirected graph with N nodes and 2N-3 edges. You can consider the graph as it is built onto an existing initial graph , which has 3 nodes and 3 edges, iteratively. Every node added onto the graph and has 2 connections with the existing nodes (not necessarily with the initial 3 only) in the graph. When all nodes are added to the graph (N-3 nodes added in total), the final graph is constructed.

I'm asked, what is the maximum number of nodes in this graph that can be visited exactly once (except for the initial node), i.e., what is the maximum number of nodes contained in the largest Hamiltonian path of the given graph. *(Okay, saying largest Hamiltonian path is not a valid phrase, but considering the question's nature, I need to find a max. number of nodes that are visited once and the trip ends at the initial node. I thought it can be considered as a sub-graph which is Hamiltonian, and consists max. number of nodes, thus largest possible Hamiltonian path).*

I tried to apply Ore's Theorem but even for a small example graph, the Ore's Theorem might not be sufficient to tell if the graph is Hamiltonian even though it strikes you directly that it is Hamiltonian.

I thought I might use BFS since It's used to detect cycles in a graph: I needed to find the largest cycle which contained all the nodes in that cycle but given a large number of nodes, this approach might be slow and not desirable in my case since the timing will be crucial. For now this option is the last option if I can't come up with a solution.

After some thinking, I thought whatever the number of nodes will be, the graph seems to be Hamiltonian due to node addition criteria. The problem is I can't be sure and I can't prove it. Does adding nodes in that fashion, i.e. adding new nodes with 2 edges which connect the added node to the existing nodes, alter the Hamiltonian property of the graph? If it doesn't alter the Hamiltonian property, how so? If it does alter, again, how so? Thanks.

**EDIT**

I, again, realized that building the graph the way I described might alter the Hamiltonian property. Consider an input given as follows:

```
1 3
2 3
1 5
1 3

```

these input says that 4th node is connected to node 1 and node 3, 5th to node 2 and node 3 . . .

4th and 7th node are connected to the same nodes, thus lowering the maximum number of nodes that can be visited exactly once, by 1. If i detect these collisions (including an input such as 3 3) and lower the maximum number of nodes, starting from N, I believe I can get the right result.

See, I do not choose the connections, they are given to me and I have to find the max. number of nodes.

I think counting the same connections while building the graph and subtracting it from N will give the right result? Can you confirm this or is there a flaw with this?

# Answer
Let $k\_P$ and $k\_C$ be the maximum length of a Hamiltonian path and cycle, respectively, in the resulting graph $G$ (with $n$ vertices, $n\geq 5$). If the input is given to you, then $4\leq k\_P\leq n-1$ and $4\leq k\_C\leq n$.

The lower bound can be achieved when vertices $4,\ldots,n$ are all joined to vertices $1$ and $3$. In this case $C=(1,2,3,4)$ and $P=(2,1,4,3,5)$ are longest cycle and path, respectively.

The upper bound can be achieved when vertex $i$ is joined to vertices $i-1$ and $i-2$, $4\leq i\leq n$. In this case you get an outerplanar 2-connected graph, which is Hamiltonian, so $k\_P=n-1$ and $k\_C=n$.

Not sure how to find $k\_P$ and $k\_C$ in general since, during the construction, the property that the graph is Hamiltonian (and therefore the length of the longest path/cycle) is changing depending on how edges are added.
> 2 votes

---
Tags: graphs
---


# Question
Title: Reconstructing a data table from cross-tabulation frequencies
Say there is a data table $D$ that we cannot see, with $M$ columns. We are given exact cross-tabulation frequencies for all ${M \choose 2}$ pairs of columns, that is how often each combination of two values occurs.

From the cross-tabulations, we can derive a set of possible rows $R$ of $D$ and maximum frequencies for each possible row.

How can we reconstruct the original table $D$? If there is not enough information to do so, how can we construct a possible table $D'$ that has the same cross-tab frequencies? In this case, is it possible to count the number of possible tables?

(Edit: As Vor noted, define a table as an unordered collection of rows. A permutation of the rows of a table yields the same table.)

---

For example, if $D$ has rows:

```
X  A  j
Y  A  k
X  B  j
X  B  j

```

We have three sets of cross-tab frequencies:

```
X  A  1
X  B  2
Y  A  1
Y  B  0

X  j  3
X  k  0
Y  j  0
Y  k  1

A  j  1
A  k  1
B  j  2
B  k  2

```

I would like an algorithm which will take the cross-tab frequencies as input and output the original table or a possible original table.

# Answer
> 2 votes
We have $M$ columns $C\_1, \dots, C\_M$ in the original table, each with a finite set of distinct values $V\_1, \dots, V\_M$.

Given the cross-table frequencies $c\_{i,j}(a,b)$ (frequency of $a$ in $V\_i$ and $b$ in $V\_j$ occurring together), proceed as follows:

1. Determine $V\_1, \dots, V\_M$ and denote $V\_i = \\{v^{(i)}\_j \mid j \in \[1,n\_i\] \\}$ where $n\_i = |V\_i|$.
2. Solve the following integer program:

$\qquad\displaystyle \min \sum\_{i\_1 = 1}^{n\_1} \cdots \sum\_{i\_M = 1}^{n\_M} x\_{(i\_1,\dots,i\_M)} \\ \qquad \begin{align} \text{s.t. } \sum\_{i\_1 = 1}^{n\_1} \cdots \sum\_{i\_{l-1} = 1}^{n\_{l-1}} \sum\_{i\_{l+1} = 1}^{n\_{l+1}} \cdots \sum\_{i\_{r-1} = 1}^{n\_{r-1}} \sum\_{i\_{r+1} 1}^{n\_{r+1}} \cdots \sum\_{i\_M = 1}^{n\_M} x\_{(i\_1, \dots, i\_M)} &= c\_{(l,r)}(i\_l,i\_r) \\ \qquad \text{for all } 1 \leq l \< r \leq M, i\_l \in \[1,n\_l\], i\_r \in \[1,n\_r\], \\ x\_{(i\_1, \dots, i\_M)} &\in \mathbb{N} \\ \qquad \text{for all } i\_1 \in \[1,n\_1\], \dots, i\_M \in \[1,n\_M\] \end{align}$

The $x\_{(i\_1, \dots, i\_M)}$ now indicate which row should occur how often, and we get a solution with the minimum number of rows possible. If we can influence the search, we can abort as soon as we find any feasible solution.

This is not likely to be efficient, but there are honed solvers for integer programs around so it's simple to implement. It may be possible to use an LP-solver and round to a feasible solution.

---
Tags: algorithms, complexity-theory, combinatorics, statistics
---


# Question
Title: How to find max number with a single-tape turing machine?
I'd appreciate hints for this problem

I'm trying to design a Turing Machine which calculates $\max \\{x\_1, x\_2,..,x\_k \\}$.

Assuming $1 = 1^1; 2=1^2; n=1^n$ and all numbers/strings are separated by a blank character $B$.

# Answer
> 9 votes
There are many ways to tackle this. This is just one suggestion. I assume you need a single-tape machine, and that you actually need to write it down formally, so you need a very simple solution, not something like "just compare the numbers".

Start by finding $\max\\{x\_1,x\_2\\}$, and replacing $x\_1,x\_2$ with this new number. To do this, you can take to new symbols $X,Y$, and erase one letter from each number using one of $X,Y$. After one of the numbers is erased, you remain with the second number. You can then erase the smaller number, and restore the bigger one to $1$'s.

Then, simply repeat the process until you are left with a single number. It requires several states, but it shouldn't be too huge.

---
Tags: turing-machines
---


# Question
Title: Why isn't the class of Turing-Recognizable languages closed under Complement?
I'm studying Turing Machines and I've already showed how Turing-Decidable is closed for the operations of Union, Intersection, Concatenation, Complement and Kleene Star. Next I did some demonstrations to show how T-Recognizable languages are closed for Union, Intersection, Concatenation and Kleene Star.

Now I'm trying to answer a question to show why the classe of T-Recognizable languages are not closed for the operation of Complementation, but I cannot understand it. Could someone please explain this?

# Answer
Hint: Suppose it was. Let $L$ be a recognizable language and let $\overline{L}$ be its complement. If $\overline{L}$ was recognizable as well, let $M\_1$ and $M\_2$ be recognizers of $L$ and $\overline{L}$, respectively.

Can you now use $M\_1$ and $M\_2$ to construct a *decider* for $L$? What does this mean for undecidable and recognizable problems like the halting problem?
> 12 votes

# Answer
Intuitively, a TM $M$ can recognize $L$ if you run it on $\sigma \in L$ it will eventually halt and say "Yes"; there is no way of knowing if when run on $\sigma' \not\in L$ it will ever halt.
> 5 votes

---
Tags: computability, undecidability, closure-properties
---


# Question
Title: Closure under intersection of context free binary trees
Some sets of ordered binary trees can be represented as a CFG with rules of the form

```
A -> aBC
A -> b

```

Where `A,B,C` are nonterminals and `a` and `b` are terminals representing internal nodes and leaf nodes respectively. The tree can be recovered from any word in the language by a preorder traversal.

The set of all such grammars forms a class of languages which is a subset of context free languages but isomorphic to a superset of regular languages (by unary encoding the alphabet and adding a dummy terminal for the second nonterminal in every production). It is obviously closed under union as you can simply concatenate the lists of productions to get a new tree grammar.

My question is whether this class is closed under intersection. I have been unable to prove that is either closed or not closed, and I figured I should see if anyone else can see how to do this.

# Answer
> 4 votes
If I correctly read your question there are two types of terminal symbols, disjoint sets for internal labels and leaf labels. In that way the structure of the tree is uniquely determined by the string.

Then your formalism is known as regular tree grammars. A production $A \to a BC$ seems to label a tree node by $a$ while attaching children $B$ and $C$. This formalism is closed under intersection. This can be proved precisely as for finite state automata or right-linear grammars. Simulate the two in parallel, as a product construction. With productions $A \to\_1 a BC$ and $P\to\_2 a QR$ we join them to $(A,P) \to a (B,Q)(C,R)$ and $A \to\_1 a$ and $P\to\_2 a$ are joined to $(A,P)\to a$.

---
Tags: context-free, formal-grammars, closure-properties
---


# Question
Title: Why does a polynomial-time language have a polynomial-sized circuit?
I wish to understand why P is a subset of PSCPACE, that is why a polynomial-time langauge does have a polynomial-sized circuit. I read many proofs like this one here on page 2-3, but all the proofs use the same technique used in the Cook-Levin theorem to convert the computation of M on an n-bit input x to a polynomial sized circuit.

What I don't understand is that the resulting circuit is dependent on the input x, because what is being converted into a circuit is the computation of M on the specific input x. By definition of PSIZE, the same circuit must work for all the inputs in a fixed length, and thus is not dependent on one specific input.

So how is the process of creating a poly-sized circuit family for a poly-time deterministic Turing machine works exactly?

# Answer
> 4 votes
Cook-Levin gives one circuit for all inputs of a given size. So although the circuit depends on the input $x$, it only depends on the size of the input. So given TM $M$ with running time $t$, and a number $n$ (the size of input), Cook-Levin gives a circuit $C\_n$ of size roughly $t^2$ that solves the problem on all inputs of size $n$. The circuit $C\_n$ does not depend on what are the bits of the input for $M$, however we need to know the numbers of input bits as that is going to be the number of input bits for the circuit.

# Answer
> 1 votes
Intuitively, a polynomial size problem needs at least a polynomial sized circuit because each step in the algorithm/circuit requires a certain amount of time. If the circuit could verify an element of the language in less than polynomial time, then an algorithm could be made to do so too.

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


title: Accurate definition of BPP

text:
# Question
Title: Accurate definition of BPP
I'm a bit confused about the definition of BPP. The way BPP is defined in typical text books (Arora/Barak for example) is that if M(x) is a Probabilistic Turing Machine (PTM) that recognizes a language $L(x)$, then $Pr\[M(x)=L(x)\]\> 2/3$. My question is, what is the probability taken over? Arora/Barak remark (7.2) that the probability is taken over internal coin tosses of $M(x)$, i.e., fix a value of $x$, and run all possible $2^{T(|x|)}$ experiments of internal coin tosses, and compute the majority of accept state. But if this is true, then Amplification theorem cannot hold because by definition if the probability is computed by executing all $2^{T(|x|)}$ possible coin-flips, then no matter how many times I run the algorithm, the probability is not going to change. (For example, if I have a bag with 2 red balls and 1 blue ball, then no matter how many times I pick a ball from the bag (and return it), the probability of picking a red ball is going to remain 2/3.)

Basically, a PTM is a random process in two variables: The input string $x \in \\{0,1\\}^\*$ and random coin tosses $ r \in \\{0,1\\}^{T(|x|)}$. For the amplification theorem to hold, I think one needs to fix a value of $r$ and run the machine on all values of $x$, and compute $Pr\[M(x) = L(x)\]$. Then for a fixed $x$, running $M(x)$ multiple times will have amplification effect, but if the probability is computed over internal coin tosses, then the Amplification theorem cannot hold.

What am I misunderstanding here?

# Answer
Repeating what MCH said, every time you run the algorithm, you use fresh random bits.

As an example, here is a BPP algorithm that computes the number $1$:

```
Toss a biased coin (heads w.p. 2/3, tails w.p. 1/3). If heads, output 1, else output 0.

```

The algorithm "succeeds" with probability $2/3$. The amplification procedure amounts to tossing $n$ biased coins, outputting $1$ if the majority of them were heads, and $0$ otherwise. Since we expect roughly $(2/3)n \> n/2$ of the coins to be heads, it is very likely that the amplified algorithm is successful (outputs $1$).

In other words, when you run your algorithm $n$ times, each time you run it, you re-toss all the coins. So the amplified algorithm tosses $n$ times as many coins, and the probability is taken over all these coin tosses.
> 6 votes

---
Tags: complexity-theory, terminology, complexity-classes, randomness
---


# Question
Title: Can one show NP-hardness by Turing reductions?
In the paper Complexity of the Frobenius Problem by Ramírez-Alfonsín, a problem was proved to be NP-complete using Turing reductions. Is that possible? How exactly? I thought this was only possible by a polynomial time many one reduction. Are there any references about this?

Are there two different notions of NP-hardness, even NP-completeness? But then I am confused, because from a practical viewpoint, if I want to show that my problem is NP-hard, which do I use?

They started the description as follows:

> A polynomial time Turing reduction from a problem $P\_1$ to another problem $P\_2$ is an algorithm A which solves $P\_1$ by using a hypothetical subroutine A' for solving $P\_2$ such that, if A' were a polynomial time algorithm for $P\_2$ then A would be a polynomial time algorithm for $P\_1$. We say that $P\_1$ can be Turing reduced to $P\_2$.
>
> A problem $P\_1$ is called (Turing) NP-hard if there is an NP-complete decision problem $P\_2$ such that $P\_2$ can be Turing reduced to $P\_1$.

And then they use such a Turing reduction from an NP-complete problem to show NP-completeness of some other problem.

# Answer
There are (at least) two different notions of NP-hardness. The usual notion, which uses Karp reductions, states that a language $L$ is NP-hard if every language in NP Karp-reduces to $L$. If we change Karp reductions to Cook reductions, we get a different notion. Every language which is Karp-NP-hard is also Cook-NP-hard, but the converse is probably false. Suppose that NP is different from coNP, and take your favorite NP-complete language $L$. Then the complement of $L$ is Cook-NP-hard but not Karp-NP-hard.

The reason that $\overline{L}$ is Cook-NP-hard is the following: take any language $M$ in NP. Since $L$ is NP-hard, there is a polytime function $f$ such that $x \in M$ iff $f(x) \in L$ iff $f(x) \notin \overline{L}$. A Cook reduction from $M$ to $\overline{L}$ takes $x$, computes $f(x)$, checks whether $f(x) \in L$, and outputs the converse.

The reason that $\overline{L}$ is not NP-hard (assuming NP is different from coNP) is the following. Suppose $\overline{L}$ were NP-hard. Then for every language $M$ in coNP, there is a polytime reduction $f$ such that $x \in \overline{M}$ iff $f(x) \in \overline{L}$, or in other words, $x \in M$ iff $f(x) \in L$. Since $L$ is in NP, this shows that $M$ is in NP, and so coNP$\subseteq$NP. This immediately implies that NP$\subseteq$coNP, and so NP=coNP.

If some Cook-NP-hard language $L$ is in P, then P=NP: for any language $M$ in NP, use the Cook reduction to $L$ to give a polytime algorithm for $M$. So in that sense, Cook-NP-complete languages are also "hardest in NP". On the other hand, it is easy to see that Cook-NP-hard=Cook-coNP-hard: a Cook reduction for $L$ can be converted to a Cook reduction for $\overline{L}$. So we lose some precision by using Cook reductions.

There are probably other shortcomings to using Cook reductions, but I'll leave that to other answerers.
> 19 votes

# Answer
That's fine. A polynomial-time Turing reduction is a Cook reduction (as in Cook-Levin theorem) and reducing an NP-complete problem to the new problem gives NP-hardness (as does a polynomial-tiem many-one reduction, AKA Karp reduction). Indeed, Karp reductions are just restricted Turing reductions anyway.

Where they differ (with regards to this question) is in showing membership. A Karp reduction from a problem to a problem in NP shows the first is in NP. A Cook reduction in the same direction doesn't.
> 7 votes

---
Tags: complexity-theory, time-complexity, np-complete, reductions
---


title: How to master Dynamic Programming?

text:
# Question
Title: How to master Dynamic Programming?
I am having hard times learning Dynamic Programming.

I looked around the web and found many tutorials with examples.

Each time I tried to figure out how to solve a new problem before looking at the solution my mind locked up and I could not continue trying...

I do not where to start!! For example, in divide and conquer I know how to start but In dynamic programming there is no a fixed starting point or at least (technique).

Last try I moved forward but I found that the solution was in a completely different direction.

# Answer
Not sure why I can't just comment. All I want to do is share a link:

http://people.csail.mit.edu/bdean/6.046/dp/

Or better yet: Deciding on Sub-Problems for Dynamic Programming

This is a duplicate.
> 4 votes

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


# Question
Title: Independent set where two vertices need to have distance >= c
An independent set (IS) in a graph is a set $V' \subseteq V(G)$ of pairwise non-adjacent vertices.

I am interested in the generalization $c$-IS where two nodes in $V' \subseteq V(G)$ need to have distance at least $c$ to any other vertex in $V'$.

Has this problem been studied before?

# Answer
> 7 votes
Yes, this is called *ruling set*. An $(\alpha,\beta)$-ruling set is a set $S$ such that any two nodes in $S$ are at distance at least $\alpha$ from each other, and, for any node $v \notin S$, there exists a node $u \in S$ such that the distance between $u$ and $v$ is at most $\beta$. So a maximal independent set is a $(2,1)$-ruling set. (This is defined in \[1\] but there might be prior references.)

\[1\] Korman et al. Toward more localized local algorithms: removing assumptions concerning global knowledge. PODC '11 Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing Pages 49-58

---
Tags: algorithms, reference-request, graphs
---


title: Comparing variations of A*

text:
# Question
Title: Comparing variations of A*
I am running some experiments with a maze, and trying different variations of A\*. Based on my experiments, I have been able to form some opinion (that at least in those cases, graph checking is better than IDA).

I am looking for online articles that have done similar experiments, comparing variations of A\* with respect to expanded nodes, but have not come across anything concrete.

# Answer
Well, there is a lot of bibliography on whether one algorithm is better than the other. In particular, the main insight is: "*in the presence of duplicates (e.g. grids), A$^\*$ should be preferred, whereas in other cases IDA$^\*$ should be in general preferred*". For example, heuristic planners usually prefer best-first search strategies such as A$^\*$ instead of IDA$^\*$ (just because duplicates occur in many domains). For example, to solve the $N$-Puzzle, the $N$-Pancake, or the TopSpin, IDA$^\*$ is the current algorithm of choice. For other cases, such as Rubik's Cube or Towers of Hanoi, IDA$^\*$ is still the algorithm of choice but be careful and try to implement a good strategy for handling symmetries. In the case of grids, A$^\*$ is the right choice.

There is a wonderful paper about how to implement A$^\*$ and makes a lot of considerations that, I think, fit your question: Ethan Andrew Burns, Matthew Hatem, Michael J. Leighton, Wheeler Ruml. Implementing Fast Heuristic Search Code

Let me know, please, whether this helps or not,
> 3 votes

---
Tags: algorithms, reference-request, artificial-intelligence, search-algorithms, empirical-research
---


# Question
Title: Decidability of a Turing machine which always halts in at most ten steps
I have an exam coming up soon and I need help with this. Consider the problem:

> Given a Turing machine $M$, determine if $M$ halts in at most ten steps on every input.

Is this decidable? Prove your answer.

# Answer
Consider the following hint:

If $M$ is a TM, and it is given an input of length $12$ (for example), but you only allow $M$ to operate for $10$ steps, what can it do with the input?
> 13 votes

---
Tags: turing-machines, undecidability
---


# Question
Title: Given an NFA A and a regular expression B, is the problem of determining L(A) = L(B) decidable?
I have having trouble with the following question:

> Given an NFA $A$ and a regular expression $B$, consider the problem of determining if $L(A) = L(B)$. Is this decidable? Prove your answer.

# Answer
Yes. Transform both into DFAs $M\_1$ and $M\_2$; from them construct DFAs for $L\_1 \cap \overline{L\_2}$ and $\overline{L\_1} \cap L\_2$, and check that neither accepts anything.

As noted in the comments, the NFA to DFA construction can give an exponential increase in number of states, same for regular expression to DFA, so this doesn't prove the problem is in NP. Luckily you weren't asked about that ;-)
> 8 votes

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