# Question
Title: Given a TM $T$ does $T$ ever leave the initial state when start tape is blank?
I want to determine whether this decision problem is decidable. I have tried to establish reductions from Halt and "Accepts empty-string", but I've not yet found a solution.

Can someone help me out?

# Answer
I would say it is decidable.

If I understood correctly, here's what I think.

First of all a TM starts from some initial state $s\_0$. How can it change the state? In your transition function you have something like $(s\_0, x) \to (s\_i, y, m)$ where $s\_i$ is a state and $x$, $y$ are symbols and $m$ is the head move (left right or stay). So, if it leaves the initial state there should be a transition from $(s\_0, \\\_)$ to some state not $s\_0$. Easy to see that it is if and only if. Thus, you can construct another Turing machine which has the input as a TM in some encoding, goes through the transition function and checks the condition above, and the problem is decidable.
> 4 votes

# Answer
Trivially decidable. Given the tape is truly blank, then T in state $s\_0$ must change the currently-scanned tape cell and do one of three things: (1) Transition to a different state and move left or right (or halt); (2) Transition back to $s\_0$ and move one cell left; (3) Transition back to $s\_0$ and move one cell right. For both (2) and (3) the TM head has moved away from the original tape cell and is now scanning a blank cell; therefore it is now in the same situation that it started in, and will act the same way. So for (2) or (3) the TM behavior on a blank tape is to move forever in one direction, leaving a trail of (probably) altered cells. So this property can be checked by inspecting the contents of a single row of the TM's 'program' (i.e the transition rule for $s\_0$ scanning blank) - if the new state is NOT $s\_0$ (including 'halts') the answer is YES, otherwise the answer is NO.

I am also reasonably certain that the problem is still decidable given arbitrary input - you just have to pay closer attention to which direction the tape head moves depending on the current cell contents.
> 3 votes

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


# Question
Title: Write the conjunctive or disjunctive normal form of an expression $f$
Write the conjunctive or disjunctive normal form of an expression $f$ that is true if the number $t=(xyz)\_2$ is a zero of the following polynomial:

$$p(t)=(t-6)(t-5)(t-4)(t-2)t(t+1)(t+3)(t+7)$$

The zeros of this polynomial are $-7,-3,-1,0,2,4,5,6$. So $t$ has to be $(000)\_2$ or $(010)\_2$ or $(100)\_2$ or $(101)\_2$ or $(110)\_2$ or... But now I don't know how to represent these negative numbers in binary? In other words how do I write $-7,-3,-1$ in the form $(xyz)\_2$?

# Answer
As @DavidRicherby said, it's best if you ask who-gave-you-the-question what he meant by $(xyz)\_2$. But if you absolutely can not do that, then you look at the situation mathematically as...

$(xyz)\_2$ here is a set $\\{000,001,010,011,...,111\\}$ of $8$ elements which forms a ring. In particular, it supports two binary operation $+$ and $\times$ where both operation has identity element, the addition has inverses...

If you can decide the addition table and multiplication table that makes sense in your context, then you're set. As long as it's a ring, then that polynomial equation makes sense.
> 4 votes

---
Tags: normal-forms
---


# Question
Title: Proof Complexity of a Proof or Disproof of P = NP
Has there been any research on the proof complexity of a resolution to the P=NP problem? If not, given the lack of progress on the problem, would it be unreasonable to conjecture that any proof that resolves the P=NP problem will require a super-polynomial number of steps?

# Answer
> 14 votes
It is known that any proof of super-polynomial circuit lower bounds (which are slightly stronger statements than $P\neq NP$) require super-polynomial, even exponential size proofs in weak proof systems like resolution. Generalizing this to stronger proof systems is a well known open problem.

See section 5 of this survey by A. Razborov where these things are shown.

# Answer
> 24 votes
Proof complexity only makes sense when there is a sequence of statements depending on a parameter $n$. For example, the proposition $\mathsf{PHP}\_n$ states (informally) that there is no bijection $\[n+1\] \to \[n\]$. This sequence of propositions is hard for certain propositional proof systems.

The statement $\mathsf{P} \neq \mathsf{NP}$ is a single statement, so you can't apply proof complexity to it directly. However, the following sequence of statements does make sense, for particular functions $s(n)$: "there is no circuit of size $s(n)$ correctly solving SAT for instances of length $n$". This has been considered in the literature, for example by Razborov (who considered the setting of uniform proof complexity, i.e., bounded arithmetic).

# Answer
> 5 votes
We have 3 cases:

* There exists a proof that $P = NP$. Than there's an algorithm solving the problem "Emit a proof that $P=NP$" that runs in $O(1)$ time. It hard-codes the proof in the Turing Machine itself, and emits it. It runs in the same time no matter its input.
* Similarly, if there exists a proof that $P\neq NP$, than we can write an algorithm emitting this proof in $O(1)$ time.
* If there exists no proof of either case, than the minimum complexity of finding a proof for either is $O(\infty)$: no Turing Machine can ever halt and emit a proof of either, since no such proofs exist.

Just because we haven't found any proof doesn't mean that it doesn't exist, and the complexity classes are defined in terms of what exists.

More precisely, we can't know precisely how hard it is to find a proof of $P=NP$ or the converse until we know the result, which kind of defeats the point.

What we do know is that, in general, the problem of "Take a statement in Predicate logic and determine if there's a proof for it" is undecidable. So there are no generic proof-generating procedures that we can plug P vs NP into, that are guaranteed to produce a result.

# Answer
> -1 votes
If P = NP then all you need to do is to create a polynomial time algorithm for solving some NP-complete problem, and prove that it is indeed polynomial (which might be hard, for example the Simplex algorithm usually runs very fast but *proving* that it runs fast seems incredibly difficult).

Ok, this might be very difficult. Assume we find an algorithm that supposedly solves the Traveling Salesman problem in O ($n^{100}$). Tough. We can't even measure the execution time for a problem with two cities.

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


# Question
Title: Is there a Tree with deterministic traversal, but which nodes can vary?
I have a dynamic closest-pair problem. In my problem though, the points never move, but instead disappear and reappear.

That is, I would like to find for a point $p$ (where $p\in\mathbb{R}^3$)\* in a set of points $P$, the closest point in $S$ where $S\subset P$. The catch its, while $S\subset P$, which elements of $P$ it contains can change at any time.

I was thinking of pre-computing a kd-tree where each leaf contains exactly one element of $P$, and each node/cell has an 'active' property. Then when I get a new $S$ I can recursively 'turn on' the levels of the tree which lead to active leaves. The active branches can then be traversed very quickly, ignoring nodes and leafs which do not contain active points.

The problem with this though is as particles are deactivated the bounding volumne goodness-of-fit will change and its no longer trivial to determine which branch should be traversed when there is a choice.

**Is there a tree or spatial subdivision structure that will retain its deterministic traversal property even as points are added and removed (so long as they don't change position)?**

The tree should be suitable for traversing on the GPU; primary consideration is performance.

\*I've specified $p$ as having three dimensions, but it may have/be able to have 2 or even 1, if it is significant for the tree. Getting into details, $P$ will be an isomap of a 3D triangle mesh, but the mesh will not be simple, therefore its hard to say right now whether the isomap will have less than three dimensions or if the error will be too large if I try to fit it in 1 or 2. Three dimensions will be the worst case.

# Answer
> 3 votes
You can do this with any binary space partitioning tree, such as a k-d tree or an octree.

Your basic approach can actually be made to work. The reason you think it won't work is because you have a misunderstanding about how nearest-neighbor search is done in these trees. Let me show you how they work and how to adapt them to your situation: you'll see that your idea does work fine and is quite a nice approach.

---

The basic principle of nearest-neighbor search is:

* Each subtree represents a (rectangular) region of space.
* You'll keep track of the closest point to $p$ found so far.
* For each subtree T, you'll figure out whether it's *possible* that any point in the region corresponding to T could be closer to $p$ than the closest found so far. If not (if it's impossible), then you won't look at T or any subtree of T. Otherwise, you'll recursively test each child of T.

This yields a recursive algorithm that explores some subset of the nodes in the tree.

The basic point is that nearest-neighbor search doesn't explore just one path through the tree. Rather, it might "fork" and explore multiple paths. However, it's still faster than looking at every leaf, because they're able to prune some (but not all) subtrees.

---

For example, build an octree representing $P$, the set of all points. Each leaf of the octree corresponds to one point in $P$. Each internal node of the octree corresponds to an "octant" (a rectangular volume of 3D space).

Next, augment the octree as follows: each internal node $x$ has a bit that indicates whether any of the leaves under $x$ are active (whether any of them correspond to points in $S$). Call the octant "active" if it contains at least one point of $S$, so the bit for node $x$ indicates whether the corresponding octant is active. You can update these active bits efficiently: adding or removing a point to $S$ can be done in $O(\log |P|)$ time.

Now, to find the neighbor nearest to point $p$, invoke $\text{Closest}(p, r)$, where $r$ is the root node of the octree and the procedure Closest is defined as follows:

$\text{Closest}(p, x)$:

1. If $x$ is not active, return $\infty$.
2. If $x$ is a leaf, return $d(p,x)$.
3. Otherwise, set $\text{curBest}$ to $\infty$.
4. For each child $y$ of $x$, do:

* If $y$ is active and $d(p,y) \< \text{curBest}$, set $\text{curBest} := \min(\text{curBest}, \text{Closest}(p, y))$.
5. Return $\text{curBest}$.

Here we define $d(p,y)$ (the distance from $p$ to an octant $y$) to be the distance from $p$ to the nearest point in $y$, i.e., the minimum of $d(p,z)$ where $z$ ranges over all points in $y$. Notice that this can be computed efficiently through a straightforward but ugly case analysis.

Notice that the structure of the octree depends only on $P$, but not on which points are active. Thus, you don't need to adjust the partitioning or split points as you change which points are active.

You can do the same with a k-d tree instead of an octree.

There is no guarantee about what the worst-case running time of this procedure will be. However, in practice, I would expect this to be pretty efficient, as large swathes of the octree can be "pruned". In particular, I would expect it to be faster than the naive algorithm of computing $d(p,s)$ for each $s \in S$, if $S$ is large.

# Answer
> 1 votes
You could use a tree that uses a space filling curve, such as the PH-Tree (z-ordered) or a critbit tree (for example z-ordered or hilbert-ordered). The space filling curve ensures that:

* the order of the entries never changes, unless the entries change their geometric position. In other words, the order of traversal depends only on geometric properties of the entries, not on the order of insertion (or deletion); insertion or deletion will not affect the ordering; if a deleted point is reinserted, it will be inserted in the same location as it was before. In your terms, the ordering can be called deterministic.
* entries that are close in space *tend* to be close in the linear ordering

Hilbert ordering has a better mapping of spatial proximity to proximity in the linear ordering, but it is slower and much more complicated.

Critbit (Java) is quite simple compared to a PH-Tree (Java), but it is much slower for range queries or kNN-queries. The PH-Tree is essentially a quadtree where the ordering inside every node follows the z-ordering of the node's entries and sub-nodes. The critbit tree is a binary tree (prefix sharing trie), that stores entry ordered by their z-value.

---
Tags: graphs, trees
---


# Question
Title: Performance gain by implementing streamlined simplex
I have to solve linear transportation problems for a research project. Ideally, I should design an application that will recieve the problem data as an input and then show some results. The size of the problems are in the order of N=10.000 sources and N=10.000 destinations, and 2N=20.000 restrictions of equality, one for each source and one for each destination.

I've been using Python's PuLP with the standard solver(COIN-OR) and with GLPK. As a general rule, the performance of COIN-OR is superior than that of GLPK, but even with COIN-OR the problems are taking too long to be solved. As far I as know, there's a streamlined version of the simplex algorithm for transportation problems, but I ignore the magnitude of the improvement in performance I should expect by using that streamlined version of simplex algorithm.

So, my first question is if those solvers identify the transportation problem structure of the problems I'm dealing with and act accordingly.

If the answer turns out to be no, then my second question is if I can exploit that particular structure of the transportation problems with a free solver that has a Python interface.

Also, will I note some improvement if I implement myself the streamlined version of the simplex algorithm? Or implementations must be too far from naive to really beat a well-established simplex solver like the ones I mentioned before?

# Answer
> 3 votes
By "streamlined", I assume you are talking about a minimum cost flow algorithm, and you have been using the standard LP solver from Coin-OR. Then I would advise using the solver from the Lemon library (from Coin-OR as well). It has Python bindings.

As for the performance, I never benchmarked it myself. Given the algorithms involved, however, just the datastructure specialization may well be a 10x improvement. For some problems, I guess the difference may well be orders of magnitude.

I don't think Coin-LP detects the network structure - I'm pretty sure neither it nor GLPK does.

There are algorithms specialized for transportation problems (even more specific than MCF), but here you'd probably have to reimplement them, and not gain as much as going from generic simplex to minimum cost flow.

While looking for benchmarks, I just found two other solvers linked from this blog post, with performance claims: Google OR-tools and PyMCFSimplex.

---
Tags: optimization, linear-programming
---


# Question
Title: Would time travel be useful for optimization?
Let's say we have circuitry that can send pieces of data to the past state of the program through literal time travel. Said time travel takes 1-5 clock cycles (I cannot assume the nature of time travel so I am giving slight lee-way) and sends one byte to some byte in the past programs memory along with a check bit to some other location so that the time travel can be detected. The general purpose would be for the program to basically run once and then essentially bootstrap paradoxing the original calculation, thereby in essence only taking the amount of time it took to send the data back to the program's past state.

Would it actually be realistic for a user level or utility program to use this as a fast/cheap way to optimize a program? My guess is that it is only good for extremely complex calculations such as prime number searches, framebuffer generations for 3D graphics, etc. but I cannot be entirely sure.

Assuming this were in the C language, the syntax for code to be bootstrapped would look like this (in case one wishes to write examples of cases they find contradictory)

```
bootstrap (<checkbit to see if time travel has occurred>)
{
    <code to process and create the original data>

    send: <list of addresses to be sent back separated by commas>
    to: <list of addresses of where the data should be sent to separated by commas>
}

```

Assume energy/radiation/side effects of time travel are irrelevant. This assumes that it is literally as easy to time travel as it is to run an adding circuit. Also, assume that people have worked out all the "bugs" from the system. The circuit works correctly without fail.

***I apologize if this is the wrong stack exchange site. I wish to speak scientifically regarding this in a real theoretical sense and this seemed like the more theoretical CS stack exchange site.***

# Answer
> 2 votes
Yes. If time travel were possible, it would be a huge win for optimization and computation: it would enable us to solve computational problems that today seem very hard to solve with existing computers.

To formalize this, we must first agree on a model of physics that allows time travel and that describes what happens when you try. There are various plausible ways to do that. Under one plausible set of assumptions about the physics, the set of problems you can solve in polynomial time using time travel is all of PSPACE. (If you're not familiar with it, PSPACE is the set of problems solvable by classical no-time-travel computers in any amount of running time you want, subject only the restriction that the space usage must be polynomial.) For instance, every problem in NP could be solved in polynomial time if time travel were possible.

For instance, there are problems that today seem to require exponential time to solve (with classical no-time-travel computers), but could be solved in polynomial time if time travel were possible.

To learn more about this subject, I suggest you take a look at Scott Aaronson's lecture notes: http://www.scottaaronson.com/democritus/lec19.html

---
Tags: programming-languages, operating-systems
---


# Question
Title: Proving using Beta Reductions (Lambda Calculus)
I am working on proving something by using Lambda Calculus and Beta Reductions, and I was following along a tutorial on another problem and attempted to carry over the knowledge onto a different problem and I am a little confused on the last step.

The problem is to prove $\textbf{or true false}$.

Here are my steps: (if there are any improvements or errors please let me know)

Step 1: Begin writing the identity for **OR** along with the parameters **true** and **false**.

$(\lambda x. \lambda y.(x ~ true ~ y)) ~ true false$

Step 2: Replace the $x$ terms with true.

$(\lambda y.(true ~ true ~ y)) ~ false $

Step 3: Replace the $y$ terms with false.

$ true ~ true ~ false \equiv (true ~ true) false $

Step 4: (I am a little shaky on this step, however I saw it done this way). Expand on one of the terms by replacing with it's identity. So we break true into:

$ (\lambda x. \lambda y. x) true ~ false $

Step 5: Again, replace x with true.

$(\lambda y.true) ~ false$

Step 6: $\textbf{this is the step i am most confused on}$ It looks as if since there is no way we can distribute the false to the y we simply just drop both of them since it is not an applicable function. Which then returns you with **true**, which stands to reason that true or false is true.

Can anyone shed light on Step 6? Or if I am correct and thats the rationale please let me know!

# Answer
> 1 votes
First let: $$ true = \lambda x ~ y . x $$ $$ false = \lambda x ~ y . y$$ $$ or = \lambda x ~ y .((x ~ true) y) $$

So this is what you wrote:

$$or ~ true ~ false \rhd\_{\beta} true$$

$$ \Bigg ( \Big( \lambda x ~ y . (x ~ true) y \Big) true \Bigg) ~ false $$ $$ \Bigg ( \lambda y. \Big ((true ~ true) y \Big) \Bigg) false $$ $$ ((true ~ true) ~ false) $$

Unwrap $true$.

$$ \Big( (\lambda x ~ y . x) ~ true) \Big) ~ false $$ $$ \color{red}{(\lambda y . true) ~ false } \rhd true $$

In the red step, which is what's burdening you, you're just consuming the $false$, why? Because there are no free $y$ variables in $true \equiv (\lambda x~ y. x)$. This is rule-(e) for substitution.

> **Definition 1.12 (Substitution)** For any $M, N, x$, define $\[N/x\]M$ to be the result of substituting $N$ for every free occurrence of $x$ in $M$, and changing bound variables to avoid clashes. The precise definition is by induction on $M$, as follows ***(after \[CF58, p.94\])***.
>
> (a) $\[N/x\]x \equiv N$
>
> (b) $\[N/x\]a \equiv a$ for all atoms $a \not \equiv x$
>
> (c) $\[N/x\](PQ) \equiv (\[N/x\]P)(\[N/x\]Q)$
>
> (d) $\[N/x\](\lambda x.P) \equiv (\lambda x.P)$
>
> **(e) $\[N/x\](\lambda y.P) \equiv P$ if $x \not \in FV(P)$.**
>
> (f) $\[N/x\](\lambda y.P) \equiv \lambda y. \[N/x\]P$ if $x \in FV(P)$ and $y \not \in FV(N)$.
>
> (g) $\[N/x\](\lambda y.P) \equiv \lambda z. \[N/x\]\[z/y\]P$ if $x \in FV(P)$ and $y \in FV(N)$.

Note: $FV(P)$ stands for the set of **free variables** of $P$.

---
Tags: lambda-calculus
---


# Question
Title: Construct a Turing Machine that recognizes the set $\{0^{2n}1^n|n\geq 0\}$
The full question is: Construct a Turing machine that recognizes the set $\\{0^{2n}1^n \mid n\geq 0\\}$. The Turing machine starts with the input on the tape and the head over the leftmost symbol of the input. The symbols to the left of the input are blanks out to infinity, as are the symbols to the right of the input. If the string is accepted, the machine should halt with 1 on the tape (the rest of the tape should be blank). If the string is rejected, the machine should halt with 0 on the tape.

Yes, this is a homework question, but I think I just need some help understanding the problem. We have not gone very in depth into Turing Machines, and he suggested we should just write the answer graphically like a Deterministic Finite State Machine with read, write, and direction in the transitions.

I am getting stuck because I can only think about it in terms of 3 different paths (being 001, 100, 010), but I know this is most likely not correct, and I do not know how to recognize if the string is not in the set. I understand that the machine know the string has ended when it reads a blank, and then it will move right one and write either a 1 or 0 depending on if the string is accepted or not, but I can only think about it as 3 different paths.

Help would be appreciated! Thanks!

# Answer
Here is a Turing machine on the online simulator I found here.

```
name: Recongnize 0^2n 1^n
init: s0
accept: acc

s0, 0
s1, _, >

s1, 0
s2, _, >

s2, 0
s2, 0, >

s2, 1
s2, 1, >

s2, _
s3, _, <

s3, 1
s4, _, <

s4, 0
s4, 0, <

s4, 1
s4, 1, <

s4, _
s0, _, >

s0, _
acc, _, -

```

The idea is to delete the two zeroes on the left, got to the end on the right, delete one, go to the way to the left, repeat. Accept only when after deleting 1 on the right the tape is empty.
> 2 votes

# Answer
You have two main steps. You first have to verify that the input is in the language. If so, erase it all and write a $1$, otherwise erase it all and write a $0$. I'm assuming the input alphabet is $\left\\{0,1\right\\}$ and the tape alphabet is $\left\\{0,1,x,␣\right\\}$.

Roughly, you're going to want to pair up the first half of $0$s with $1$s, by crossing off a $0$ then a $1$ with $x$s, moving the tape head back and forth across the tape, until you run out of $1$s. If you run out of $0$s to cross off before $1$s, you should reject since there's less $0$s than $1$s.

Then you should pair up the rest of the $0$s with the crossed off $1$s, crossing and uncrossing them respectively, one at a time, moving back and forth like before. If you run out of $0$s to cross off before uncrossing all of the $1$s, you have less than twice as many $0$s as $1$s, so reject. If you uncross the rest of the $1$s before crossing off the rest of the $0$s, you have more than twice as many $0$s as $1$s.

If you end up crossing off the rest of the $0$s along with uncrossing all of the $1$s, you have twice as many $0$s as $1$s and should accept, but first you need to clear the tape and write your output. If you have already rejected, do the same.

After you have constructed a TM, I highly urge you to test it with varying inputs, like $\epsilon$, $0$, $1$, $10$, $01$, $001$, $0010$ to verify it's accepting and rejecting the appropriate inputs.
> 0 votes

---
Tags: turing-machines
---


# Question
Title: Why do we prove X is in NP to prove it is NP-complete?
The steps to show something is NP-complete is to show it is a member of NP, and then show an NP-complete problem reduces to it in polynomial-time. Why is the first step necessary? Is it possible to reduce an NP-hard problem to an NP-complete problem in polynomial time? Because that would be the only instance in which this is important.

# Answer
> 6 votes
The short answer is that it's because that's the definition of being $\mathsf{NP}$-complete.

Recall that for a problem $\Pi$ to be $\mathsf{NP}$-complete we need the following:

1. $\Pi \in \mathsf{NP}$.
2. There exists an $\mathsf{NP}$-hard problem $\Phi$ such that $\Phi \leq^{P}\_{m} \Pi$ (where $\leq^{P}\_{m}$ is a polynomial time many-one mapping).

What happens then if we leave out condition 1?

In that case "all" we've shown is that $\Pi$ is $\mathsf{NP}$-hard.

Even if we restrict $\Phi$ to being an $\mathsf{NP}$-complete problem, we can still reduce it to problems that are much harder. For example it's trivial to map 3-SAT to QBF-SAT, but QBF-SAT is compete for $\mathsf{PSPACE}$, so definitely not $\mathsf{NP}$-complete unless there's a rather large collapse (at least $\mathsf{NP} = \mathsf{PSPACE}$).

Going further (and thanks to David Richerby for being sensible), there are versions of $\mathsf{NP}$-complete problems that are $\textsf{NEXP}$-complete, for example SUCCINCT 3-SAT is a generalisation of 3-SAT (the reduction from 3-SAT to SUCCINCT 3-SAT is less obvious, but not tricky). However we know unconditionally that $\mathsf{NP}\neq \mathsf{NEXP}$, so SUCCINCT 3-SAT is not in $\mathsf{NP}$.

As you note, it is unlikely that we can reduce, in polynomial time, an $\mathsf{NP}$-hard problem that's unlikely to be in $\mathsf{NP}$ to a problem in $\mathsf{NP}$ (again, it would imply some collapse in complexity classes). Where you went off track is identifying this as the only important case.

# Answer
> 1 votes
By definition a problem is NP-Complete when it is in NP and it is NP-hard. Obviously, you need to proove these two conditions to coincide with the definition.

Why do we have belonging to NP in the definition? By calling a problem NP-Complete we want to show that this problem is the hardest among all NP problems. If you proved only hardness, it could be just a problem from a harder class than NP.

Is it possible to reduce NP-hard problem to NP-complete? This would mean that the NP-complete problem is harder than NP-hard one. Still the question why this NP-hard one is the hardest among all NP problems remains.

---
Tags: algorithms, time-complexity, np-complete, np
---


# Question
Title: Does a multi-agent system have to have a synchronous component in order for the agents to cooperate?
During my programming assignments in multi-agent systems, I noticed that it feels impossible to get distributed agents to cooperate without a synchronous component. Let me explain what I mean by these terms:

**Cooperation**: I would loosely define this as any process which a single agent cannot solve without receiving non-static information from one or more other agents.

**Example**: Consider a system where two identical agents are needed to change a lightbulb. One agent needs to change the lightbulb itself, and one needs to hold the ladder.

Naturally, the problem is how to decide which agent is going to be the lightbulb changer and which the ladder holder. I have somehow arrived at the conclusion that this is impossible without the presence of a synchronous component in the system.

Without such a component, the agents could always get into an inconsistent state - for example, both would consider themself the holder, no matter how you decided how to assign those roles - if you were to choose, for example, a message sending system, where an agent would send to another "I will change the bulb, you hold the ladder", they could still send such a message at the same time. Similarly, if there was to be a "Leader" of those agents who would assign those roles, how would you decide which one was to be the leader? You just move the problem up a level.

Therefore, such problems are normally solved by methods such as assigning an unique integer identifier to each agent, and deciding based on this value (agents with higher value will become the leader, etc). Similarly, I have seen people use things like the time of the agent's entry into the system, the position of the agent in the environment, and so on.

However! All of those things are what I consider to be a **synchronous component**. Some entity has had to synchronously decide them - there is only a single time, a single person who assigns the identifiers, a single universe by which the agents' locations are defined, and so on.

I am pretty sure this statement holds. My question is: does there exist a theorem which states this or something similar (one that has been formally proven)?

# Answer
You're asking about a problem known as leader election. There are various computational models one can consider, based on what we assume about how the network works and what agents are allowed to do.

The Wikipedia article claims there are no *deterministic* algorithms for leader election in a setting where all agents start from the same state (have no identity) and are situation in a ring (so connectivity is symmetrical); see https://en.wikipedia.org/wiki/Leader\_election#Anonymous\_rings.

At the same time, there *are* randomized algorithms for leader election that work if we make some assumptions about network delay (e.g., that messages won't be delayed forever), and if you're willing to accept algorithms with a finite *expected* running time. For instance, a very simple starting point is for each node to pick a random number and broadcast it, and then select the agent with the lowest number as the leader. In case of ties, repeat the entire procedure. There are additional details one must work out, depending on the model of computation and the assumptions about communication.

There's lots of research on this topic in the distributed systems literature. You might want to spend some time reviewing the papers that have been published in that field, to see what you can find.
> 2 votes

---
Tags: distributed-systems, concurrency, synchronization
---


title: Domino and Tromino Combined Tiling

text:
# Question
Title: Domino and Tromino Combined Tiling
If I have a nx2 grid which I need to fill using 2x1 dominoes and L shaped trominoes in any combination, how many different combinations are possible?

I am aware that when only 2x1 dominoes are used then the cell definition using dynamic programming is: $$ f\left \[ 0 \right \]= 0 $$ $$ f\left \[ 1 \right \]= 1, i=1 $$ $$ f\left \[ 2 \right \]= 2, i=2 $$ $$ f\left \[ i \right \]= f\left \[ i-2 \right \]+ f\left \[ i-1 \right \], \forall i\>2 $$

When L shaped trominoes are added to consideration, we (assume) can use them only in pairs since using odd number L shaped trominoes will leave one 1x1 grid unfilled. so when a pair of such trominoes combine it is equivalent to using a single 3x2 rectangular piece. Everytime we use $\ num=\lfloor n/3 \rfloor $ rectangular pieces and the rest are filled with 2x1 dominoes. Also the total number of combinations would be sum of twice the $\ num$, $\ f\[i\] $ and number of 2x1 domino combinations of the rest of the grid when the 3x2 piece is used. Is this assumption right? This is how far I have gotten through. If any of you have any hints it would be appreciated. Thank You in advance.

Note: Tile Rotations are allowed

# Answer
> 7 votes
There is a mutual recursion in two variables $f(n)$ for the $n\times 2$ grid and $g(n)$ for the $n\times 2$ grid with a single square sticking out. It does not matter where the square sticks out (first or second row) because their number of tilings is the same.

Note the trominos indeed come in pairs, but they do not need to form a $3\times 2$ block. You can place horizontal dominoes in between. Now that I look at it, it seems there is a recursion with one $f(n)$ if you look at a tromino and its matching partner. This picture suggests $f(7) = f(6)+f(5)+2f(4)+2f(3)+ \dots +2f(1)+2f(0)$. Sounds like a promising recursion to me.

If my initial computations are right, this suggests 1,1,2,5,11,24,53,117, ... which is OEISA052980. This lists another recurrence however. Would be fun if they match.

PS. Yes! Recursions are the same. $f(n) = f(n-1) + f(n-2) + 2\sum\_{k=0}^{n-3} f(k)$. Then subtract $f(n)-f(n-1) = f(n-1)+f(n-3)$. Thus $f(n) = 2f(n-1)+f(n-3)$, which is in the OEIS.

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


title: Running time of naive primality tester

text:
# Question
Title: Running time of naive primality tester
A naive approach to checking if $n$ is prime is:

```
Prime(n):
    for i=2, 3, ..., sqrt(n):
        if i divides n then return "composite"
    return "prime!"

```

I remember something about how measuring the complexity of this algorithm must be done in terms of the number of bits in $n$. In that case, I think that we also can't assume that checking whether $i$ divides $n$ can be done in $O(1)$ time.

So, I don't think this algorithm runs in $O(\sqrt n)$ time. What is its complexity?

# Answer
> 1 votes
Firstly, you need to figure out what is the length of your input. Your input is $n$ so you need log(n) bits. Denote this number as $m$ not to get confused. Division takes either linear of m or constant time, depending on your model. So the question is how many time you gonna run it. Clearly, sqrt(n) times where $n=2^m$ so this algorithm runs in $O(2^{\frac{m}{2}})$ time.

---
Tags: algorithms, complexity-theory, time-complexity
---


# Question
Title: Is the Backus-Naur Form a type 2 grammar? If So why?
I understand that the Backus-Naur Form is utilized to assess and specify type 2 grammar, but is it in itself a form of type 2 grammar?

# Answer
Backus-Naur Form is a *conventional notation* for writing Context-Free Grammars.

Its usefulness comes from the need to distinguish the character encoding standards that are used to write texts in various computer languages from the higher-order alphabets of terminal and non-terminal symbols (corresponding to lexical units and syntactical variables, respectively) used in the definition of grammars.

The very idea of using CFGs to define the syntax of high-level programming languages was remarkably precocius, which is another reason why the work of John Backus and Peter Naur was so appreciated at the time.
> 3 votes

---
Tags: formal-grammars, discrete-mathematics
---


# Question
Title: Is there an NP-complete problem, such that the decision version of its counting problem is not PP-complete?
Once we fix a polynomial time deterministic verifier V(input, certificate), its corresponding NP problem is the question: For this input, does a (polynomial size) certificate exist such that V(input, certificate) returns True?

The associated counting problem (#P class) is: How many certificates exist such that V(input, certificate) returns True?

#P is not a "decision problems" class, but a class of counting problems. The closest traditional "decision problems" class is PP, which has problems of the form: Do the majority of the certificates result in V(input, certificate) returning True?

I am interested in the decision version of the counting problem associated with a certain NP-complete problem + verifier, which would be: Given the input instance and a positive integer number K: Are there at least K different certificates such that V(input, certificate) returns True?

This decision problem is clearly equivalent to the counting version (via a Binary Search). If I am not mistaken, the class of all these "decision versions of the counting problems associated to NP problems" is exactly as hard as PP since:

1) Any of these "counting-decision" problems can be reframed as some other majority problem, by choosing an ad-hoc verifier definition where a lot of certificates are manually deemed to be True or False such that there are at least K True certificates in the original if and only if the majority is True in the resulting problem. Just as a simple example to illustrate the reduction idea, if there where 8 possible certificates, and we want to know whether there are at least 3 True ones, we might propose a different verifier having 11 possible certificates: for the 8 original ones it just checks normally, and for the other three it immediately returns True without looking at the input. Since the majority of 11 is 6, this new verifier accepts a majority of certificates exactly if the original one accepts at least 3.

Thus, all of these problems are in PP.

2) The corresponding "counting-decision" version for any PP-complete problem will obviously be PP-hard, since solving the original majority problem is simply solving the $(input, \left \lfloor \frac{ totalCertificates}{2} \right \rfloor + 1)$ problem. Thus, such problems are PP-complete.

So now, at last, can I clearly state my question, which is a "more sofisticated version" of the same idea shown in MAX,MAJ variants of NP complete problems:

Is there any NP-complete problem such that the decision version of its counting problem (which is in PP) is not PP-complete?

For example, in the case of Subset-Sum the associated decision problem I'm interested in would be: Are there at least K nonempty subsets of zero sum?

Since K is free and not limited to be near half of the certificates, the argument of the other answer does not apply.

# Answer
> 3 votes
Putting your question in more precise terms, you ask whether the following claim holds:

$\* \hspace{1mm} R(x,y) \text{ is an NP-complete relation}\Rightarrow count\_R \text{ is PP-complete}$

Where $count\_R$ is defined as follows:

$count\_R=\left\\{(x,k) \big| \hspace{1mm} \left\lvert\left\\{y : R(x,y)\right\\}\right\rvert\ge k\right\\}$.

We call a relation $R(x,y)$ NP-complete if it is computable in polynomial time, and the language it defines $L\_R=\left\\{x | \exists y \hspace{1mm} R(x,y)=1\right\\}$ is NP-complete.

We talk in terms of relations, since as you mentioned, the counting version has to be defined relative to some specific verifier.

It seems that this is an open question, as (\*) implies:

$\** \hspace{1mm} R(x,y) \text{ is an NP-complete relation}\Rightarrow \\#R\text{ is #P-complete}$

Where $\\#R(x)=\left\lvert \left\\{y : R(x,y)\right\\} \right\rvert$.

To see why * implies the above, let $R(x,y)$ be some NP-complete relation. Using (\*), $count\_R$ is PP complete, so $count\_{\text{SAT}}\le\_p count\_R$. In that case, $\\#SAT\in\mathsf{FP}^{\\# R}$ and thus $\\#R$ is $\\# P$-complete (use binary search, where in each cutoff you apply the reduction from $count\_{\text{SAT}}$ to $count\_R$ and query the $\\#R$ oracle on the result).

To my knowledge, (\**) is currently open. See this related question from cstheory. Also related.

---
Tags: complexity-theory
---


# Question
Title: Enumerate all greedy choices of maximum independent set
Following what is stated in the question Why is greedy algorithm not finding maximum independent set of a graph?, I have the following question:

Even enumerating and testing all possible choices of the greedy algorithm (namely, when there are two possible choices, test both) and verifying which returns the highest value, can it return an approximate result? (ignoring the computational cost)

# Answer
> 1 votes
Take the graph in the answer you linked to, and add another vertex G that has an edge to every other vertex except C. Now C has the unique fewest number of neighbours, so it will necessarily be chosen first; then you can choose at most one of A, E, F or the new vertex G since each of these 4 vertices is linked to each of the others by an edge, so the algorithm forces you to produce an independent set of size 2 (either {C, A}, {C, E}, {C, F} or {C, G}). But the same size-3 independent sets as before still exist (e.g. {B, D, F}).

---
Tags: algorithms, graphs
---


# Question
Title: Difference between page table and inverted page table
I do not understand the difference between page table and inverted page table. I know that both are used to translate the logical addresses into physical addresses produced by the processes necessary to store data in memory.

This is what I know on the **page table**.

Generally each page table contains an element for each virtual page and a table exists for each process. This can lead to huge tables (programs with many pages).

I can imagine a page table like this:

Instead, this is what I know on the **inverted page table**.

It has only one page table for all processes. This table has an entry for each real page (block of physical memory). Each element contains the virtual address of the page stored in that physical location, with information about the process that owns that page.

So I represent the inverted page table like this:

Am I doing it right? Did I get it right?

Thank you

---

I don't understand if the information I have learned theoretically then I understood well.

I do not think that is more efficient an interved page table than a normal page table, indeed I find it most confusing.

As I understand it, each frame of the physical memory has a corresponding entry in the inverted page table. I suppose that the memory has a large number of frames, then the inverted page table is huge and how do I keep it in RAM? While if you use the page tables "normal", I do not keep all of them in memory at the same time, you just keep those of the currently active processes, or not?

And it is reversed (the arrows are reversed), as I map a logical address into a physical?

# Answer
> 7 votes
An inverted page table is just a hash map. An inverted page table *always* fits in DRAM because it is proportional in size to the DRAM.

A DRAM total space is divided into $N$ page frames. If the size of a page frame is 4096 bytes, then the DRAM is of size 4096 $N$ bytes.
Assuming that an inverted page table entry is 16 bytes, and considering that there is an entry for each physical memory frame, then the page table is of size 16 $N$. This corresponds to 16/4096 = 1/256 $\approx$ 0.4% of the memory.

Your picture of the inverted page table is not correct. Here is the picture from the original paper about inverted page tables (Huck, Jerry; Hays, Jim: Architectural Support for Translation Table Management in Large Address Space Machines, Int'l Symp Comp Arch (ISCA-20):39-50, 1993. doi:10.1145/165123.165128.)

It's a hash table. Each entry of the hash table needs to store both a virtual address and a physical address. The virtual address is there to check for hash conflicts.

The reason you can guarantee the total number of entries for the HPT (hash page table) plus the collision resolution table is just $N$ (the number of physical pages), is that there can be only one entry in the tables for each physical page.

---
Tags: operating-systems, virtual-memory
---


title: Are "method" and "function" synonyms?

text:
# Question
Title: Are "method" and "function" synonyms?
Would saying "Call the printf function" be the same as "Call the printf method"?

# Answer
> 7 votes
These are a different level classifications:
A method is a function (or procedure) associated with object – a concept from Object Oriented Programming.

A function is the logical unit (a piece of reusable code called by name) independent of any objects (those might not even exist in particular language). So the method is a function, but a function exists also in non-OO languages, so the reverse is not true.

---
Tags: terminology
---


# Question
Title: Prove that every undirected connected graph with $|V | > 2$ results in a connected graph if two vertices removed..
How do I go about proving this?

Prove that every undirected connected graph with $|V | \> 2$ has at least two vertices such that if one or both are removed (along with their incident edges) the resulting graph is still connected, and describe an efficient algorithm to find two such vertices.

# Answer
> 4 votes
**Hint:** Find the connected graph's spanning tree (using an algorithm like breadth-first search). Consider the endpoints of a longest path in this spanning tree.

---
Tags: combinatorics, discrete-mathematics, graphs
---


# Question
Title: CFG to generate $L = \{a^{2n}b^n\} \bigcup \{a^mb^{2m}\}$
I've been struggling to find the grammar to generate the language

$$L = \\{a^{2n}b^n : n \text{ is natural}\\} \cup \\{a^mb^{2m} : m \text{ is natural}\\}.$$

I've considered

$$S \to aS|Sb|ab,$$

which works in some cases, but not all (we can derive $a^{k}b$ for example).

What considerations am I not taking into account? There first is the requirement that in a degenerate case we generate $abb$ or $aab$, and there's the consideration that we need to double the number of respective symbols each time.

A promising alternative seems to be

$$S \to aSb|a|b,$$

which balances the left and right sides such that one is always greater than the other by one, but not by a factor of two.

# Answer
In this case you have the union of two trivially CGF languages and usually that is achived by the following trick. You write some $S\_1$ grammar for the first one, $S\_2$ grammar for the second one and just "or" them somewhere at the top level (here it's $S$). Your approach was just to use single recurrent literal, if I can say like that, and thus it was difficult to come up with CGF rules.

You would get something like this:

> $S \to S\_1 | S\_2 $
> $S\_1 \to a^2 S\_1 b | a^2 b$
> $S\_2 \to a S\_2 b^2 | a b^2$
> 6 votes

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


# Question
Title: optimal lifted phylogenetic alignment - how to improve time complexity?
optimal lifted alignment \- is a dynamic programming algorithm. Its input is a tree $T$ with $k$ strings assigned to its leaf nodes (their length is $n$).

The algorithm then assigns strings to the internal nodes s.t. the sum of distance (global alignment distance) on all the edges would be minimal, under the constraint that the string assigned to each node is one of the strings of its immediate children (hence the name "lifted").

The algorithm first computes distances $D$ between all pairs $O(k^2n^2)$. For each leaf node $v$ assigned $S\_v$ we initialize: $d(S, v) = 0 | S = S\_v$ and $d(S, v) = \infty | S \neq S\_v$.

We then traverse post-order and for each internal node $v$, for each string $S$ assigned to one of its leaf descendants (all strings in its subtree) does $d(v,S) = \sum{\min(D(S,T) + d(w,T))}$ where $w$ are $v$'s immediate children. Overall = $O(k^2n^2 + k^3)$.

I've been told its possible to improve the complexity to $O(k^2n^2 + k^2)$ but I can't see how? Would appreciate any hint.

# Answer
> 2 votes
Consider a node $x$ with children $x\_1,\ldots,x\_d$, and denote by $N(v)$ the number of leaves in the subtree $T(v)$ rooted at $v$. We can implement the processing of $x$ as follows:

* Go over $1 \leq i \leq d$:
* + Choose a leaf $f\_i \in T(x\_i)$ as the label of $x$ and $x\_i$.
* + For all $j \neq i$, choose the leaf $f\_j \in T(x\_j)$ that minimizes $D(f\_i,f\_j) + d(x\_j,f\_j)$.
* + Store $d(x,f\_i) = \sum\_{j \neq i} \[D(f\_i,f\_j) + d(x\_j,f\_j)\]$.

The processing time of $x$ is proportional to $$ \sum\_{i=1}^d N(x\_i) \times \sum\_{j \neq i} N(x\_j) = \left(\sum\_{i=1}^d N(x\_i)\right)^2 - \sum\_{i=1}^d N(x\_i)^2 = N(x)^2 - \sum\_{i=1}^d N(x\_i)^2. $$ Summing over all nodes $x$ up to the root $r$, we see that the total processing time is proportional to $N(r)^2 = k^2$.

---
Tags: algorithms, time-complexity, trees, strings, bioinformatics
---


# Question
Title: What is the time complexity of this randomized algorithm?
Let's start with a problem statement:

> given an array of length $n$ with numbers $1$ through $n$ (inclusive), consider the following steps:
>
> 1. Select a random number $k$ in range $\[1, n\]$.
> 2. Set $a\[k\] = q$.
> 3. If there exists element $p$ in $a$ such that $p \ne q$, go to step 1, otherwise end.

So, basically we are going to randomly pick elements in the array and set them to some predefined value until every element in the array is set to this value. What is the time complexity of such algorithm? please explain your answer.

# Answer
This is the coupon collector's problem. You can find its analysis in introductory textbooks on probability theory, among other sources.
> 3 votes

# Answer
The complexity is non deterministic. It depends on how the random value is being picked. In this case we can only determine the expected value to complete the task but not complexity.
> 1 votes

---
Tags: algorithms, algorithm-analysis, runtime-analysis, randomized-algorithms
---


# Question
Title: Find a sequence of $n$ integers with $\Omega(n^2)$ inversions
So right off the bat, this is in fact a homework question. I've been banging my head on this problem for hours. From my naive understanding of inversions, I feel that this is not possible.

Considering for $n=1$ elements, there are no inversions, it already seems like this won't work, but maybe it's just for $n \> 1$, so we try $n = 2$. And the best I can seem to get is $1$ inversion, where the set is $\\{2,1\\}$, thus there is one inversion, since $0 \< 1$ but $S\[0\] \> S\[1\]$. The best I can seem to get is $\\{n, n-1, \dots, 2, 1\\}$, where there are $n(n-1) - 1$ inversions.

Am I missing something in my approach?

# Answer
Sorta answered my own question in the comments, so I decided to put this here:

If we take any sequence of $n$ integers, in reverse order like $\\{n,n-1,\dots, 2, 1\\}$. Then each digit $S\[i\]$ will have $(i-1)$ inversions, and there are $n$ digits.

Thus $I(n) = \displaystyle\sum\_{0}^{n-1} n = 0 + 1 + 2 + \dots + (n-1)$. So the total number of inversions will be $I(n) = \dfrac{n(n-1)}{2}$.

Then see, since $n^2 = O\left(\dfrac{n(n-1)}{2}\right)$, $\dfrac{n(n-1)}{2} = \Omega(n^2) $.

Thus $I(n) \in \Omega(n^2)$, and we have a sequence of $n$ digits with $\Omega(n^2)$ inversions.
> 3 votes

# Answer
A random permutation will work.

Let $\pi \in S\_n$ be a uniformly random permutation. For $i \< j$, denote by $E\_{ij}$ the event that $\pi(i) \> \pi(j)$, let $X\_{ij}$ be the corresponding indicator variable, and let $X=\sum\_{i\<j} X\_{ij}$ be the number of inversions. Since $\Pr\[E\_{ij}\] = 1/2$, linearity of expectation shows that the expected number of inversions is $$ \mathbb E\[X\] = \frac{1}{2} \binom{n}{2} = \Omega(n^2). $$

With a bit more work, we can also compute the variance. If $\\{i,j\\} \cap \\{k,\ell\\} = \emptyset$ then $$\Pr\[E\_{ij} \land E\_{k\ell}\] = \frac{1}{4}.$$ If $i \< j \< k$ then $$ \Pr\[E\_{ij} \land E\_{jk}\] = \frac{1}{6}, \qquad \Pr\[E\_{ik} \land E\_{jk}\] = \Pr\[E\_{ij} \land E\_{ik}\] = \frac{1}{3}. $$ This shows that $$ \mathbb E\[(X\_{ij}-1/2)^2\] = \frac{1}{4} \\ \mathbb E\[(X\_{ij}-1/2)(X\_{k\ell}-1/2)\] = 0 \\ \mathbb E\[(X\_{ij}-1/2)(X\_{jk}-1/2)\] = -\frac{1}{12} \\ \mathbb E\[(X\_{ij}-1/2)(X\_{ik}-1/2)\] = \mathbb E\[(X\_{ik}-1/2)(X\_{jk}-1/2)\] = \frac{1}{12} $$

Therefore $$ \mathbb V\[X\] = \frac{1}{4} \binom{n}{2} + \frac{1}{6} \binom{n}{3} = O(n^3). $$ Chebyshev's inequality then shows that $$ \Pr\left\[X \< \frac{1}{4}\binom{n}{2}\right\] \leq \frac{\mathbb V\[X\]}{\frac{1}{16} \binom{n}{2}^2} = O\left(\frac{1}{n}\right). $$ In other words, a random permutation will have $\Omega(n^2)$ inversions with high probability.
> 2 votes

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


# Question
Title: How do I prove that a language is regular?
In order to prove that the following language is regular, would I use a pumping lemma?

The set $A$ of all strings that are substrings of some string in $L$, where $L \subseteq\Sigma^\*$. $L$ Must be regular.

# Answer
> 2 votes
Here's a **hint**. Since $L$ is regular, there is a finite automaton $M$ that accepts all and only those strings in $L$. Suppose you only wanted those substrings that start with the same character as a string in $L$. Could you somehow modify $M$ (perhaps by making some states final) so that it would accept all substrings starting with the same character as a string accepted by $L$?

Having done that, could extend this (perhaps with $\epsilon$-moves) so that you could jump from the start state of $M$ to a string along an accepting path in $M$?

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


# Question
Title: In automata theory, why is a machine classified based on the languages it recognises?
Automata Theory is a subject where we mathematically model a computing device and study the theory behind it. Here we group the computing devices based on the number of languages they can accept. Based on that we say :

Finite Automata's Power \< Push Down Automata's Power \< Linear Bounded Automata's Power \< Turing Machine's Power

and hence forward it is a widely known fact that Turing Machine is the most powerful machine.

But my question is why do we say machine A is more powerful than machine B based only on its language accepting capability? I mean there are lots of other things that a general machine can do. Why not base the concept of power on those other things? In that sense a TM can do nothing more than accept a language!! Can a TM wash clothes? No. Because it has no capability of accepting the input (i.e clothes) on its tape. Can it produce heat energy? No. Because its output is fixed on pencil and paper.

At max, a Turing Machine can do all the possible mathematical problems. Leave alone the other ones like Finite Automata or the Linear Bounded Automata.

So what effectively do we gain by classifying the machines based on this particular property of expressive power excluding all the other properties?

# Answer
> 5 votes
The main reason we base our judgements of an abstract machine's "power" on the languages it accepts is that a lot of computational tasks can be equally well expressed in terms of language recognition.

Here's an example: a perfectly reasonable computational task is, "Given an integer $n$ (say in decimal representation), is $n$ a prime number? We could translate that into an exactly equivalent language recognition problem by saying "Is an integer $n$ in the language $\\{2,3,5,7,11,13,17,\dotsc\\}$?" In general terms, any computational task that requires only a "yes" or "no" answer is equivalent to the problem of determining whether the related language is decidable. We can do similar correspondences for other problems like, "How many primes are there less than $N$?"

By the way, it's not quite correct to say "a Turing Machine can do all the possible mathematical problems". That's roughly the **Church-Turing Thesis** (look it up), a statement of confidence which can't be either true or false until you can rigorously specify what "all possible mathematical problems" means.

---
Tags: formal-languages, computability, automata, computation-models
---


# Question
Title: Decidability of the language of DFAs accepting only odd-length strings
> Let $L$ be the language $\\{\langle M \rangle : M\text{ is a DFA that accepts only odd-length strings}\\}$.
>
> Prove that $L$ is decidable.

How wrong is my answer?

Create a TM $T$ that decides $L$:

1. Create an equivalent input string $v$ that is in the language $L(M)$.
2. Give encoding to $T = \langle M, v \rangle$.
3. TM $T$ simulates $M$ on input $v$.
4. If TM $T$ halts and accepts, accept. Otherwise, reject.

I would like to know how off I am with my answer.

# Answer
> 0 votes
Every DFA can be simplified by a Turing Machine, so you can simplify the DFA you receive as input and compare it to the simplified DFA that accepts odd-length strings.

On input $M$:

1. Simplify $M$. Remove every unreachable state and transition from $M$ (disjoint from start state)
2. If the start state of $M$ is **reject**, and the only other state in $M$ is **accept**, and for every $w \in \Gamma, \exists$ a $w-arrow$ from **accept** to **reject** and from **reject** to **accept**, then *accept*. Otherwise *reject*.

# Answer
> 0 votes
Forget TMs here, all you need is a decision algorithm, so do this

1. Create a DFA, $N$ that accepts only odd-length strings (a two-state DFA will do it).
2. On input $M$, determine whether $L(M)=L(N)$, using known results about regular language closure properties (for example, for any sets $A, B$ we know $A=B$ if and only if their symmetric difference, $(A\cap \overline{B})\cup (\overline{A}\cap B)$ is empty). If $A, B$ are regular, then their symmetric difference is regular (by closure properties of regular languages).
3. Test the symmetric difference for emptiness. There's a well-known result about how to do that for regular languages.
4. If the difference is empty, answer "yes" else answer "no".

There's your decider.

---
Tags: turing-machines, finite-automata, decision-problem
---


title: Direct-mapping cache

text:
# Question
Title: Direct-mapping cache
I had this question on a previous homework assignment and was unable to answer it. I've done some research and am not really able to find anything that clears this up for me. Would appreciate any help or explanation.

Q2. Consider a direct-mapping cache of 128 lines and a main memory block size of 8 bytes. What cache line number does byte address 120010 map to?

# Answer
The address generated by the CPU is divided into 3 parts for the identification of its position in the cache. These three field as you mus be knowing are : BYte Offset , Index and TAG . The index bits determine the line number in the cache. You need to find the number of bits present in the index field.
> 1 votes

---
Tags: cpu-cache, memory-access
---


# Question
Title: Preventing multiple threads from racing on a queue while not wastefully polling its size
I have a queue with 50 ints in it, and I have 3 threads that want to race at the queue to print the values in it, with a 2 second delay before trying to get the next int.

The queue is not thread safe, and the semaphore protecting is is decoupled from the number of items inside the queue(the number of items in the queue are checked by calling `.size()` for the queue, but the lock is obtained by blocking on the semaphore until its owner unlocks it.

I am trying to understand how to prevent the three threads from accessing the queue at the same time, but at the same time not trying to access the queue if the queue is empty.

If the queue is empty, but unlocked, i will have a bunch of threads locking the queue, checking its size, and unlocking it, until something is added to the queue. This seems silly and wasteful; Is there a solution to this?

# Answer
You wouldn't have just your queue and your semaphore. You would also have a global atomic variable where "false" means "I can guarantee one hundred percent that there is no data in the queue", and "true" means "There is probably some data in the queue, but maybe not".

Any code that modifies the queue would very carefully update the global variable. You need an operating system that makes it possible that code using locking can change such a variable as you need it.

For some interesting reading, google for "dispatch\_once implementation".
> 2 votes

---
Tags: data-structures, concurrency, queues
---


title: Plow a 2D polygonal area

text:
# Question
Title: Plow a 2D polygonal area
I have a problem that is similar to this that I am trying to solve: "Given a randomly-shaped field, what is the best (fastest I guess) way to plow it? Every part of the field must be plowed, plowing outside the area is not a problem, and turning around is slower than going straight."
Basically, I'm in the situation of a farmer that wants to plow as fast as possible a weirdly-shaped field with no obstacle.

As far as I can tell, this is a covering problem for a simply-connected 2D space, but with some special restrictions.

It seems like it should be a common enough problem, but I can't seem to be able to find anything. I guess most fields have a shape similar enough to a rectangle and thus it is not an issue.
Is there any algorithm or numerical method that allows to solve this problem?

Thanks.

# Answer
> 0 votes
Even for a near rectangular field, plowing along the long sides should be more efficient than along the short ones, but the solution isn't trivial I think. When the field slightly deviates from being perfectly rectangular, naive plowing will leave you with a triangular patch that will require a lot of turning to finish.

We could observing that all furrows need to be parallel, both in practice as well as from an optimization perspective. Then a mathematical description of the problem would be that you have a set of evenly spaced parallel lines in the plane and you want to fit (i.e. rotate and translate) the polygon so that the number of intersections between it and the lines is minimized. Note that there are infinitely many infinitely long lines in this description, think drawing the polygon on lined paper.

I don't see a quick archetypal problem for this myself, but I think you could try brute-forcing it by rotating the polygon over the lines and computing the lines-polygon intersections at each turn.

# Answer
> 3 votes
You'll find plenty of literature on this widely-studied problem, which is called complete coverage path planning. Many techniques have been applied with more or less success (genetic algorithms, etc.) but in the end the only viable technique is some variant/improvement on the boustrophedon decomposition algorithm, which is in the class of Morse decompositions.

Choset's paper is the founding document, but I found Xin Yu's PHD dissertation to be the best practical description. The problem is that Boustrophedon decompositions find only a single 'best' ploughing angle for all trapezoids, when some may certainly be better ploughed at some other angle.

Bochkarev and Smith recently described a way to minimize turns by exploiting the minimum altitudes of the polygons, but I found it difficult to grasp with my limited high-school maths.

I am currrently trying out an alternative approach, by taking a Boustrophedon decomposition at all the angles of the polygon and then layering all the resultant trapezoids sorted by a score based on area and minimum altitude. If it works out I'll try and remember to come back here to post the results.

**Citations**

Choset, Howie. "*Coverage of Known Spaces: The Boustrophedon Cellular Dercomposition*" Autonomous Robots 9, 247-253, 2000.

Xin, Yu. "*Optimization Approaches for a Dubins Vehicle in Coverage Planning problem and Traveling Salesman Problems*" PhD Dissertation, Auburn, Alabama, 2015.

Bochkarev, Stanislav and Smith, Stephen L. "*On Minimizing Turns in Robot Coverage Path Planning*" Automation Science and Engineering, 2016

---
Tags: algorithms, optimization, computational-geometry
---


# Question
Title: Can bar codes theoretically be considered a type of digital memory?
Bar codes act just like any other device that contains data that you can read from. Can bar codes thus be considered a type of computer memory?

I believe the principle is quite similar to the optical discs like CDs or DVDs.

They work just like an SD memory card but instead of a card reader we use barcode scanner to read the digital data stored in the bar code.

Can bar codes be useful in other types of applications instead of identifying products? Can barcodes or similar technology be used in computers?

# Answer
There is no god-given definition of (read-only) digital memory. We can think of several reasons for a writing system to be considered digital:

* Can be read by a computer.
* Cannot be read by a human.
* Has high density.
* Designed for use by computers.

Barcodes satisfy the first two properties, but not the third one: their density is rather low. Nevertheless, both traditional barcodes and modern QR codes were designed to be read by machines, and this gives credence to your claim.
> 2 votes

---
Tags: memory-hardware, digital-circuits
---


# Question
Title: Is there any undecidable language that is countable?
All we know is that if a language is countable than it must be recognizable. However, a recognizable language may or may not be decidable.

# Answer
Your premise is incorrect. The set of all words, $\Sigma^\*$, is countable (as long as the alphabet is countable, and we usually refer to finite alphabets anyway).

Every language is a subset of $\Sigma^\*$, and thus every language is countable. In particular, there are undecidable and unrecognizable languages.
> 2 votes

---
Tags: formal-languages, undecidability, uncountability
---


title: Reduce $SAT$ to $3SAT$

text:
# Question
Title: Reduce $SAT$ to $3SAT$
I was reading this that details a polynomial reduction from $SAT$ to $3SAT$.

In case $k = 1$ or $k = 2$, why don't we just replace those clauses with $C\_i' = \\{{z\_1, y\_{i, 1}, y\_{i, 2}}\\}$ and $C\_i' = \\{{z\_1, z\_2, y\_{i, 1}}\\}$ respectively? Instead, it suggested to replace them by $C\_i' = \\{(z\_1, y\_{i, 1}, y\_{i, 2}), (z\_1, y\_{i, 1}, \overline{y\_{i, 2}}), (z\_1, \overline{y\_{i, 1}}, y\_{i, 2}), (z\_1, \overline{y\_{i, 1}}, \overline{y\_{i, 2}})\\}$ and $C\_i' = \\{(z\_1, z\_2, y\_{i, 1}), (z\_1, z\_2, \overline{y\_{i, 1}})\\}$ respectively.

# Answer
> 1 votes
Let's take the case $k = 1$. Consider the CNF $z\_1 \land \lnot z\_1$. You suggest replacing it by $$ (z\_1 \lor y\_{1,1} \lor y\_{1,2}) \land (\lnot z\_1 \lor y\_{2,1} \lor y\_{2,2}). $$ Hopefully you see the problem now.

---
Tags: np-complete, reductions, polynomial-time
---


# Question
Title: If $L$ is a regular language then so is $\sqrt{L}=\{w:ww\in L\}$
I am interested in proving that $\sqrt{L}=\\{w:ww\in L\\}$ is regular if $L$ is regular but I don't seem to be getting anywhere. If possible I was hoping for a hint to get me going in the right direction. Thank you for your help.

My idea for demonstrating regularity of the square root language was to try to consider two machines running in tandem. One of them accepts the original language $L$ and the other runs the same machine backwards (I expect that this will be an NFA). I then wanted to accept words that met in the middle (i.e ${(q,q):q∈Q}$ where $Q$ are the states of the DFA accepting $L$ ). However, I do not think this will work.

# Answer
> 7 votes
Here is how to implement your solution. Let $A = \langle Q, q\_0, F, \delta \rangle$ be a DFA for $L$. We will construct an NFA $A' = \langle Q', q'\_0, F', \delta' \rangle$ as follows:

* $Q' = \\{q'\_0\\} \cup Q^3$. The state $(q\_1,q\_2,q\_3)$ means that we have guessed that when $A$ finishes reading the first copy of $w$, it will be in state $q\_1$; the first copy of $A$, started at $q\_0$, is at state $q\_2$; and the second copy of $A$, started at $q\_1$, is at state $q\_3$.
* $F' = \\{(q\_1,q\_1,q\_2) : q\_1 \in Q, q\_2 \in F\\}$. Thus we accept if the first copy of $A$ is in the guessed state, and the second copy of $A$ is at an accepting state.
* $\delta'(q'\_0,\epsilon) = \\{(q,q\_0,q) : q \in Q\\}$. This initializes the simulation of the two copies of $A$.
* $\delta'((q\_1,q\_2,q\_3),a) = \\{(q\_1,\delta(q\_2,a),\delta(q\_3,a))\\}$. This simulates both copies of $A$, while keeping the guessed state.

We leave the reader the formal proof that $L(A') = \sqrt{L(A)}$.

---

Here is another solution, which creates a DFA. We now run $|Q|$ copies of $A$ in parallel, starting at each state of $A$:

* $Q' = Q^Q$.
* $q'\_0 = q \mapsto q$, the identity function.
* $\delta'(f,a) = q \mapsto \delta(f(q),a)$.
* $F' = \\{ f \in Q' : f(f(q\_0)) \in F \\}$.

What is the meaning of the condition $f(f(q\_0)) \in F$? After reading a word $w$, the automaton $A'$ is in a state $f$ given by $f(q) = \delta(q,w)$. Thus $f(f(q\_0)) = \delta(\delta(q\_0,w),w) = \delta(q\_0,w^2)$.

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


# Question
Title: Determine the smallest $3$ numbers in a set using comparisons
Given a set of $n$ distinct numbers, we would like to determine the smallest $3$ numbers in this set using comparisons. The elements can be determined using $n+O(\log n)$ comparisons.

This was the answer given in a multiple choice question. Now, we can easily do this using $3n\in O(n)$ comparisons. However I have been thinking about it and I can't do it in $n+O(\log n)$ comparisons.

They might be thinking about making a heap and using heapify which takes $O(n)$ time. However in heapify, the comparisons are $O(n)$ but not like $n+O\log(n)$ because every step in the heapify needs finding the minimum among $3$ numbers which takes $3$ comparisons so making a heap and finding the three minimums should be $3n$ comparisons.

So, can anyone tell me how to find three minimums in $n+O(\log n)$ comparisons or am I messing up somewhere in the heapify logic?

# Answer
> 4 votes
I can show you how to get the two smallest elements in $n + O( \log n)$ comparisons, the extension to the three smallest elements should not be difficult.

Build the following tree. Start with your array, then for each pair of neighboring elements (non-overlapping), promote the smaller one level up. Do the same for the new level, until the tree has a root.

This tree is built using less than $n$ comparisons ($n / 2 + n / 4 + \dots$). The smallest element is obviously the root. The second smallest element must be one of of the siblings of all the nodes that are equal to the root along the path down the tree to the array level. There are at most $\log n$ such nodes.

You should also convince yourself of the bound when the number of nodes on a level is not even.

# Answer
> -1 votes
I'd suggest to look at the following classical algorithm of finding the k-th smallest element in linear time.

https://en.m.wikipedia.org/wiki/Median\_of\_medians

---
Tags: algorithms, complexity-theory, sorting
---


# Question
Title: How many restricted length strings are there without significant repetitions
Let us fix an alphabet $\Sigma$ of size $c$, then we have the finite language $\Sigma^n$ which is the set of all $n$ length words. For each $N,M$ how many words are there in $\Sigma^n$ such that no sequence of $N$ characters repeats $M$ times in a row?

For instance with N=2 and M=3 `101010` would not be counted, but `111010` would be

Here is some data I found on it with a simulation:

```
c n N M total percent
2,4,2,2,10,0.625
2,5,2,2,16,0.5
2,6,2,2,26,0.40625
2,6,3,2,48,0.75
2,6,2,3,48,0.75
2,7,2,2,42,0.328125
2,7,3,2,88,0.6875
2,7,2,3,88,0.6875
2,8,2,2,68,0.265625
2,8,3,2,162,0.6328125
2,8,4,2,216,0.84375
2,8,2,3,162,0.6328125
2,8,2,4,216,0.84375
2,9,2,2,110,0.21484375
2,9,3,2,298,0.58203125
2,9,4,2,416,0.8125
2,9,2,3,298,0.58203125
2,9,3,3,416,0.8125
2,9,2,4,416,0.8125
2,10,2,2,178,0.173828125
2,10,3,2,548,0.53515625
2,10,4,2,802,0.783203125
2,10,5,2,928,0.90625
2,10,2,3,548,0.53515625
2,10,3,3,802,0.783203125
2,10,2,4,802,0.783203125
2,10,2,5,928,0.90625
3,4,2,2,66,0.8148148148148148
3,5,2,2,180,0.7407407407407407
3,6,2,2,492,0.6748971193415638
3,6,3,2,666,0.9135802469135802
3,6,2,3,666,0.9135802469135802
3,7,2,2,1344,0.6145404663923183
3,7,3,2,1944,0.8888888888888888
3,7,2,3,1944,0.8888888888888888
3,8,2,2,3672,0.5596707818930041
3,8,3,2,5676,0.8651120256058528
3,8,4,2,6318,0.9629629629629629
3,8,2,3,5676,0.8651120256058528
3,8,2,4,6318,0.9629629629629629
3,9,2,2,10032,0.509678402682518
3,9,3,2,16572,0.8419448254839201
3,9,4,2,18792,0.9547325102880658
3,9,2,3,16572,0.8419448254839201
3,9,3,3,18792,0.9547325102880658
3,9,2,4,18792,0.9547325102880658
3,10,2,2,27408,0.4641568866534573
3,10,3,2,48384,0.819387288523091
3,10,4,2,55896,0.9466036681400193
3,10,5,2,58158,0.9849108367626886
3,10,2,3,48384,0.819387288523091
3,10,3,3,55896,0.9466036681400193
3,10,2,4,55896,0.9466036681400193
3,10,2,5,58158,0.9849108367626886
4,4,2,2,228,0.890625
4,5,2,2,864,0.84375
4,6,2,2,3276,0.7998046875
4,6,3,2,3936,0.9609375
4,6,2,3,3936,0.9609375
4,7,2,2,12420,0.758056640625
4,7,3,2,15552,0.94921875
4,7,2,3,15552,0.94921875
4,8,2,2,47088,0.718505859375
4,8,3,2,61452,0.93768310546875
4,8,4,2,64704,0.9873046875
4,8,2,3,61452,0.93768310546875
4,8,2,4,64704,0.9873046875
4,9,2,2,178524,0.6810150146484375
4,9,3,2,242820,0.9262847900390625
4,9,4,2,258048,0.984375
4,9,2,3,242820,0.9262847900390625

```

The values seem to go to $c^n$ as $N,M$ increase and appear to be a function of $c$, $N+M$. It also seems to decrease as you increase $n$ and increase as you increase $c$. This all makes intuitive sense to me. If I had to guess I would say it is exponential in $n$, polynomial in $c$, and exponential in $N+M$

A secondary question I have is how would you represent the language defined by just the strings counted.

# Answer
For each particular $c,N,M$, this can be solved explicitly by constructing a DFA accepting the language. The general case may also be approached heuristically, though the dependency structure makes heuristic estimates harder to make.

The case $N = 1$ can be solved explicitly. Suppose that the alphabet is $\\{0,\ldots,c-1\\}$. Represent each word $w\_1\ldots w\_n$ as the sequence of differences $x\_1\ldots x\_n$, where $x\_1 = w\_1$ and $x\_i = w\_i - w\_{i-1} \pmod{c}$ for $i \> 1$. Your language then becomes $$ \epsilon + \\{0,\ldots,c-1\\}((\epsilon + 0 + \cdots + 0^{M-1})\\{1,\ldots,c-1\\})^\*(\epsilon + 0 + \cdots + 0^{M-1}). $$ The corresponding generating function is $$ 1 + cx \cdot \frac{1}{1-\frac{x^M-1}{x-1}\cdot(c-1)x} \cdot \frac{x^M-1}{x-1} = \frac{x^{M+1}-1}{cx-1-(c-1)x^{M+1}}. $$ The asymptotic growth of the number of words is controlled by the smallest (in modulus) root of $(c-1)x^{M+1}-cx+1$. If this modulus is $\alpha$, then the growth rate of the sequence (under reasonable assumptions) is $\Theta((1/\alpha)^n)$.

Plotting a few of the polynomials $(c-1)x^{M+1}-cx+1$ reveals that there are two real roots in $\[0,1\]$. We are interested in the one near $1/c$. Suppose that $x=(1+\epsilon)/c$ is a root. Then $$ 1 = cx - (c-1)x^{M+1} = 1+\epsilon - \frac{c-1}{c^{M+1}} (1+\epsilon)^{M+1}, $$ and so $$ \epsilon = \frac{c-1}{c^{M+1}} (1+\epsilon)^{M+1}. $$ This shows that $\epsilon$ is exponentially small in terms of $M$, and so we can approximate $(1+\epsilon)^{M+1}$ by $1+(M+1)\epsilon$ to obtain the equation $$ \epsilon \approx \frac{c-1}{c^{M+1}}(1 + (M+1)\epsilon) $$ whose solution is $$ \epsilon \approx \frac{\frac{c-1}{c^{M+1}}}{1-(M+1)\frac{c-1}{c^{M+1}}} = \frac{c-1}{c^{M+1}-(c-1)(M+1)} \approx \frac{c-1}{c^{M+1}}. $$ Since $1/x = c/(1+\epsilon) \approx (1-\epsilon) c$, altogether we obtain that the number of words of length $n$ in which no symbol repeats $M$ times is $\Theta(\alpha^n)$, where $$ \alpha \approx c - \frac{c-1}{c^M}. $$

Carrying this sort of analysis for $N \> 1$ seems significantly more difficult.
> 2 votes

---
Tags: formal-languages, word-combinatorics
---


# Question
Title: Is there a name for this graph transformation (remove a 'thru' node)
I have a directed graph, eg:

$$A\to B\to C$$

$A$ and $C$ may have multiple in- and out-edges, but B has exactly one in- and one out-edge.

I want to remove node $B$ and replace the edges $(A,B)$ and $(B,C)$ with a single edge $(A,C)$.

Is there a name for this operation? In particular a name or algorithm for finding all nodes such as $B$ and removing them from the graph.

# Answer
> 3 votes
You're *contracting* the edge $(A,B)$ (or, equivalently, $(B,C)$).

To contract an edge $(x,y)$ is to delete the vertex $y$ and make all its neighbours except $x$ itself be neighbours of $x$ instead.

---
Tags: graphs
---


title: Undecidable/Decidable Language

text:
# Question
Title: Undecidable/Decidable Language
This question might sound stupid but, can the language of a TM be not recursively enumerable ?

Thank you ~

# Answer
No, because A TM has 3 possibilities: run forever, accept, or reject. So the language of a TM is recursively enumerable as the TM M either accepts some input x, which means x is in L(M), or otherwise rejects or runs forever.

A language can be non-recursively enumerable, but the language of a concrete TM is always recursively enumerable.
> 7 votes

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


# Question
Title: How can image processing neural networks be effectively trained?
I was just thinking about image processing neural networks and how to effectively train them in regard of the available dataset.

Let's say you'd want to build a neural network which can distinguish between pictures showing a cat or a dog. I do not have much experience in the field, but I think it would take a pretty big dataset until the network comes to an acceptable success rate.

How could a big enough dataset be acquired? You can't just automatically generate pictures showing a cat or a dog. This means a human would be needed to catagorize thousands and thousands of pictures before the data could be fed to the untrained neural network.

How is it done in practice? Are small datasets (say 100 pictures) ran over and over again? Or is there an completely different, more effective approach?

# Answer
> 4 votes
Yes. Typically a very large data set is required: tens or hundreds of thousands of labelled images, or perhaps even more. No, 100 images almost certainly won't be enough.

Just running over the same 100 images won't help. Doing that won't provide the machine learning algorithm any new information that it doesn't already have.

Where do we get these large data sets from? Basically, through tedious human effort. There are many variants of this:

* Sometimes it involves people manually, tediously labelling images one by one.
* Sometimes one can find an existing data set that someone else has already labelled for you (e.g., ImageNet).
* Sometimes you can pay other people to do the labelling for you (e.g., crowdsourcing on Mechnical Turk or something like that).
* Sometimes you can find images that are already labelled: for instance, if you do a Google Image search on "cat" it will find many, many images of cats for you. Well, most of them will be cats; there may be a few other images in there (e.g., a picture of a tiger, a picture of someone named Cat), but the overwhelming majority will be cats. How does Google Image search know to return these images, when you search for "cat"? Google might be looking at the keywords on the same page where the photo is found. So, basically, this is a case where we already have images on the Internet that have already been labelled by whoever made them available, so it's a particularly interesting special case of the above.

That's the basic idea. There are variations, of course, but I hope it gives you the basic idea. As you can see, coming up with the training set can be extremely tedious and/or expensive, and the availability of labelled data to use for training a machine learning classifier can be one of the main limiting factors on our ability to build better classifiers. This is one of the reasons behind the current hype around "big data": labelled data is valuable (because it can be used to train interesting classifiers), so companies that already have lots of (labelled) data have a valuable asset.

---
Tags: artificial-intelligence, neural-networks
---


# Question
Title: Machine learning: do the benefits of more data plateau after a certain point?
This question is both general in nature and also specific to computer vision. If this is the wrong forum, apologies in advance and suggestions on where to post would be much appreciated.

After a certain point, do the benefits of more data plateau for machine learning algorithms?

For instance, let's say the goal is object recognition of a basketball. Is there a plateau, say, after training on 1M images of basketballs? Or is the plateau lower at like 100K images? Or is there no plateau at all?

More concretely, can you detect basketballs with 99% accuracy after 100K samples, meaning the next 900K samples only nets an additional 1% in accuracy at most?

How about for non-image domains such as speech recognition of all words related to the weather in the English language?

It seems that if there is a plateau, it would hinge on the complexity of the domain. Assuming the data plateau exists, is there a principle for generalizing what the plateau is for a given domain (e.g., to recognize one type of object with no variations, you need about 100K images from every angle and under different lighting conditions)?

# Answer
> 5 votes
Yes, typically there will be a plateau. There's usually no way to guess exactly where the plateau will be, a priori; the only way to find out is to build larger and larger data sets and see what happens.

The size of the data set needed to reach a "plateau" is dependent on many factors, including the specific classification task you're trying to solve, the machine learning algorithm you're using, the set of features you've chosen, and maybe other considerations. For some tasks, a fairly small training set might be sufficient to reach the "plateau". For others, you might need an incredibly enormous training set -- so large that you'll never reach it in practice, so effectively you'll never hit a plateau in practice.

There's absolutely no way to answer your specific questions about how many images are needed for particular domains. I know you're hoping there will be some rule of thumb that'll help you predict how many images you need for some new classification task, but I've got bad news for you; there's not really any useful rules of thumb that I'm aware of. The only way to find out is to try it, or to read research papers or experience reports from others who have tried to solve the same task or a similar task.

It's also worth keeping in mind that the notion of a plateau should not be taken too seriously. Rather, you should think of it as *diminishing returns*. After some point, increasing the size of the training set will give diminishing returns in accuracy. It's not to say that there's necessarily a point where you get literally zero improvement; it's just that the improvement available from a larger training set might be extremely small, i.e., where the accuracy curve starts to become nearly horizontal, when graphed as a function of the size of the training set.

In the comments you separately talk about "the point when a classifier reaches 95% of human accuracy". That's *not* the same thing as a plateau; that's a totally different measure. For some classification tasks, humans are way better than any classifier we know of; we don't know of any machine learning approach that will get anywhere near human accuracy, let alone 95% of human accuracy, no matter how large a training set you have. For other classification tasks, machine learning can do *better* than any human -- so the classifier gets not just 95% of human accuracy, but maybe 200% of human accuracy. Comparing a classifier's accuracy to human accuracy is unrelated to the existence and location of a plateau (i.e., diminishing returns as you increase the size of the training set).

---
Tags: machine-learning, computer-vision
---


title: Is Maximum Independent Set in coNP

text:
# Question
Title: Is Maximum Independent Set in coNP
I need to determine whether the following problem $X$ is in coNP:

> Given a graph $ G=(V,E) $ and a positive integer $s\leq|V| $, is there an independent set that is the largest for $G$ of size at least $s$?

My solution for this was that in fact the above problem is in coNP because we can provide an NP solution for $\overline{X}$ which has the following certificate and certifier.

The certificate being a set of vertices $V'$.

The certifier does two things:

1. Checks if $V' \subseteq V$.
2. Checks for each pair of vertices in $V'$ if there exists no edge.
3. Checks if $|V'|\<s$.

The certifier computes this in $O(V+E)+O(1)$.

Is this the right way to show if X is in coNP?

Edit: The independent set is required to be the largest possible for graph $G$.

# Answer
> 2 votes
Independent set is NP-complete, so it's unlikely to be in coNP.

Moreover, the complement problem would sound like "all independent sets have size at most $s$".

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


# Question
Title: Termination of a composition of terminating functions
Suppose there are two functions:

$ f : X \rightarrow Y $ and $g : Y \rightarrow Z$

Both $g$ and $f$ can be implemented as algorithms that yield the correct result in a finite amount of time.

It appears to be obvious, that there is also a correct and terminating algorithm that computes the composition of the two $g \circ f$.

But why is that so? Do I need to argue that for both functions, there is a representation in the lambda calculus and in that calculus (with a small-step semantics), there is a trivial implementation of $\circ$? Doesn't that require an encoding of $X$,$Y$ and $Z$? Is there a more fundamental theorem?

# Answer
> 2 votes
Indeed this is obvious. Now you need to "prove" it. The difficulty will depend on what definitions (and axioms) you assume when you say that "$f$ and $g$ can be implemented". Start by making these definitions explicit.

---
Tags: termination
---


# Question
Title: How to use succinct circuits to construct an EXPTIME complete problem?
When reasoning with NP-completeness, I find SAT and k-clique more convenient to reason with than generalized games that are NP-complete or the Turing machine model. I'm looking for something similar for EXPTIME-completeness. Wikipedia mentions:

> Another set of important EXPTIME-complete problems relates to succinct circuits. Succinct circuits are simple machines used to describe some graphs in exponentially less space. They accept two vertex numbers as input and output whether there is an edge between them. For many natural P-complete graph problems, where the graph is expressed in a natural representation such as an adjacency matrix, solving the same problem on a succinct circuit representation is EXPTIME-complete, because the input is exponentially smaller; but this requires nontrivial proof, since succinct circuits can only describe a subclass of graphs.\[8\]
>
> 8: Papadimitriou (1994), section 20.1, page 492.

I understand the concept that you can describe some graphs using exponentially less space and use that as input, but I can't find the mentioned resource or find out how succinct graphs work exactly or how to construct an EXPTIME-complete problem.

# Answer
Since you're having trouble getting hold of Papadimitriou's classic textbook *Computational Complexity*, let me suggest another resource: Papadimitriou's paper with Yannakakis, A note on succinct representations of graphs. They prove the following general result:

> Suppose that $L$ is a P-complete problem, and that there is a polytime reduction $f$ from the Circuit Value Problem to $L$ in which, given an input $x\_1\ldots x\_n$ of size $n$, the $j$th bit of $f(x)$ is, *irrespective of $x$*, either constant of equals some input bit or its negation. Then the succinct version of $L$, which consists of pairs $\langle n,C \rangle$, where $C$ is a circuit on $\lceil \log\_2 n \rceil$ inputs, such that $C(0) \ldots C(n-1) \in L$, is EXPTIME-complete.

The hard part of the proof uses the construction in the Cook–Levin theorem.
> 3 votes

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


# Question
Title: Difference between graph-partitioning and graph-coarsening
What is the difference between graph-partitioning and graph-coarsening with respect to scale-free networks? I am trying to analyze graphs generated using the data from social networks. Do both the terms mean the same or are they different?

# Answer
> 6 votes
They are different because... :

Graph Partitioning:

Giving a graph $G=(V,E)$, it is possible to *partition* $G$ into smaller components with specific properties.
e.g. the *k-way graph partitioning* is the problem to divide the vertex set $V$ into $k$ disjoint partition $P\_1, P\_2,...,P\_k$ such that the number of the edges $e = (u,v) \in E, s.t. u \in P\_i , v \in P\_j, i \neq j $ is minimum.

Graph Coarsening:

Graph Coarsening is the first phase of a Multi-level Method, a method that partitions a graph applying one or more stage. Usually the first phase is the Graph Coarsening. This works by collapsing pairs of nodes and edges using a determinate criteria. Graph Coarsening takes as input a graph $G$ and gives as output a smaller graph $G^{'}$.
We use the Graph Coarsening because the size of the graphs may be too big to be partitioned using well known algorithms (i.e. FM, KL) in an acceptable time.
e.g. METIS uses multi-level methods and, in this Coarsening Phase, merges pairs of nodes having a matching.

In your analysis you can use Graph Partitioning Software (METIS, Chaco, etc) in order to divide you graph and (for example) put each partition on a different node and doing distributed computing.

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


# Question
Title: PDA for { xy : |x| = |y|, x ≠ y} from its grammar, and intuition behind it
I know the grammar for the language $\\{ xy : |x| = |y|, x ≠ y \\}$ if $\Sigma=\\{a,b\\}$:

$$ \begin{align\*} &S→AB∣BA \\ &A→a∣aAa∣aAb∣bAa∣bAb \\ &B→b∣aBa∣aBb∣bBa∣bBb \end{align\*} $$

I know this is a grammar, but I need a PDA for this language, and intuition how $\\{xy: |x|=|y|,x \neq y\\}$ is a CFL while $\\{xy: |x|=|y|,x=y\\}$ is a CSL but not a CFL. How is this possible?

# Answer
You are asking two questions: how to construct a PDA for the language, and why this language is context-free while the same language with the condition $x \neq y$ replaced by the condition $x = y$, is not. I will only answer the second, since for the first question there are known algorithms.

The reason that your language is context-free is that we can rewrite it as follows: $$ \\{ \Sigma^i a \Sigma^i \Sigma^j b \Sigma^j : i,j \neq 0 \\} \cup \\{ \Sigma^i b \Sigma^i \Sigma^j a \Sigma^j : i,j \neq 0 \\}. $$ This gives a different description of the language as the union of concatenations of context-free languages. A similar trick just doesn't work for the language $\\{ xy : x=y \\}$.

Here is a different example. Consider the following two collections of natural numbers (without zero):

* $A = \\{ x \cdot y : x \neq y \\}$.
* $B = \\{ x \cdot y : x = y \\}$.

The set $A$ consists of all natural numbers other than $1$, whereas the set $B$ consists of all squares. Even though we defined them in a similar way, the set $A$ has a much simpler description, while $B$ doesn't.
> 5 votes

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


# Question
Title: Proof that the language $ww^R$ is not regular without using the pumping lemma
I am breaking my head over this. Let the alphabet $A$ be given by $A = \\{a,b,c\\}$ and let

$$L = \\{ww^R \mid w \in A^\* \\}.$$

Prove that the language $L$ is not regular **without using the pumping lemma**, but using:

* The fact that $\\{a^nb^n \in A^\* \mid n \geq 0 \\}$ is not regular.
* The fact that $\\{w \in A^\* \mid w \text{ is a palindrome} \\}$ is not regular.
* Closure properties of the class of regular languages (such as if $L\_1$ and $L\_2$ are regular, then $L\_1 \cup L\_2$ is also regular, etc.).

# Answer
> 1 votes
Let

$$ L\_1 = \\{\ \omega\omega^r \ | \ \omega \in \Sigma^\* \\} $$ $$ L\_2 = \\{\ a^nb^n \ | \ n \in \mathbb{N}\ \\}$$

Because $\Sigma = \\{a, b, c\\}$ is finite, $\Sigma^\*$ must be countable.

This means we can define a function $f : \Sigma^\* \rightarrow \mathbb{N}$ which returns the position of a word $\omega \in \Sigma^\*$ in an arbitrary ordering defined by $f$. $f$ is invertible, we define $f^{-1} : \mathbb{N} \rightarrow \Sigma^\*$, which returns the word $\omega$ at position $n$ in the enumeration of $\Sigma^\*$ as defined by $f$.

Now, since every word $\omega$ is uniquely defined by a natural number $n$, and every word $\omega$ has exactly one unique reverse $\omega^r$, we can define an isomorphism between $L\_1$ and $L\_2$:

$$ g \colon\ L\_1 \rightarrow L\_2; \quad \omega\omega^r \mapsto a^{f(\omega)}b^{f(\omega)} $$

$$ g^{-1} \colon \ L\_2 \rightarrow L\_1; \quad a^nb^n \mapsto f^{-1}(n) f^{-1}(n)^r $$

Since $L\_2$ is not regular and we have a bijection between $L\_1$ and $L\_2$, $L\_1$ must not be regular.

This proof works for any finite alphabet $\Sigma$ because the transitive closure of a finite alphabet is always countable.

# Answer
> 1 votes
Suppose that $L$ is regular. Then $L' = L \cap (a+b)^\*c^2(a+b)^\*$ is also regular. Another description for $L'$ is $$ L' = \\{ wccw^R : w \in (a+b)^\* \\}. $$ Consider now the regular substitution $\sigma$ given by $$ \sigma(a) = \\{a\\}, \sigma(b) = \\{b\\}, \sigma(c) = \\{a,b,\epsilon\\}. $$ Then $L'' = \sigma(L')$ is also regular. But $L''$ is the language of palindromes.

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


# Question
Title: Multiple neural networks or multiple outputs?
Suppose you have data of the form input a matrix A, and output a matrix B, where each row of each is one datapoint. Should you create multiple neural networks, one for each column of B, or one NN with multiple output neurons, one for each column of B?

# Answer
> 2 votes
You can do either.

If the learning tasks are related at all (i.e., the meaning of the columns of B are related), it's probably better to have one neural network with multiple outputs. This is often more effective, because the first few stages of that neural network might do some processing that is relevant to all of the outputs -- e.g., it might look for some local patterns or properties of the input that can then be useful for predicting all of the outputs. The network might take a bit longer to train if you use one big network rather than many smaller networks, but usually this is worth it if it leads to better accuracy.

But if you're not sure, you can always try both approaches and see which works better.

---
Tags: neural-networks
---


# Question
Title: Solving or estimating the recurrence $T(n) = x + T(n-\log_2 n)$
I am trying to either solve or find a tight bound $\Theta$ for the following recurrence relation:

$$T(n) = x + T(n-\log\_2 n)\\,.$$

For some nonzero constant $x$ (we can suppose it to be 1, for simplicity). Thus far, I have been able to prove the following:

\begin{align\*} T(n) &\in O(n)\\ T(n) &\notin \Omega(n)\\ T(n) &\in \Omega (n^p)\quad \forall p \in (0,1)\\,. \end{align\*}

But I am now stuck, I cannot figure how to either solve the recurrence or find a $g(n)$ to prove a tight bound: $T(n) \in \Theta(g(n))$. May somebody know how to solve this?

If you want to know, this recurrence arises in the following context: in *maxiphobic* heaps\[1\] where the "weight" of the heap is its number of nodes, the `merge` operation is recursive, but its complexity is $\Theta(\log n)$, even in the worst case. If the meaning of the weight is changed to mean the height of the heap, the complexity for average random inputs remains $\Theta(\log n)$, but you can construct a worst-case pathological input where in each step `merge` calls recursively itself with almost all of its input, minus a degenerate subtree of at most $\log\_2 n$ elements, approximately. I want to find a tight bound for the complexity of that worst case.

\[1\] C. Okasaki, 2005. *Alternatives to Two Classic Data Structures*. In *Proceedings of 36th SIGCSE Technical Symposium on Computer Science Education*, pp. 162–165. ACM. (ACM Digital Library)

# Answer
> 8 votes
Assuming an appropriate base case, it is easy to see that $T(n) \geq (n/\log\_2 n) \cdot x$, since at each step we subtract at most $\log\_2 n$, and thus it takes t least $n/\log\_2 n$ steps to reach zero.

In the other direction, denote by $m$ the current input ($n$, $n-\log\_2n$, and so on). As long as $m \geq n/2$, the input decreases by at least $(\log\_2 n)/2$ at each step, and so it takes at most $2n/\log\_2 n$ steps to reach $n/2$. Then it takes at most $4\sqrt{n}/\log\_2 n$ steps to reach $n^{1/4}$, and so on. After $\log\log n$ such phases, $m$ will be $O(1)$. This gives an upper bound proportional to $x$ times $$ \frac{2n}{\log\_2 n} + \frac{4\sqrt{n}}{\log\_2 n} + \cdots \leq \frac{2n}{\log\_2 n} + 4\sqrt{n} + 8n^{1/4} + \cdots + 2\log n \cdot n^{1/\log n} = \\ O(n/\log n + \sqrt{n} \log\log n) = O(n/\log n). $$ Thus $T(n) = \Theta(xn/\log n)$.

---
Tags: asymptotics, recurrence-relation
---