# Question
Title: Meaning of ⟨_⟩ in the context of verifiers
> A verifier for a language A is an algorithm V, where $$A = \\{w \mid V \text{ accepts $\langle w,c \rangle$ for some string $c$}\\}$$ ($c$ is called a certificate or proof)

What's the definition of $\langle , \rangle$ here?

# Answer
Any reasonable definition would do (I'll provide a formal definition later on). One simple definition, when $w,c$ are strings over some alphabet $\Sigma$ which doesn't contain the space character, is that $\langle w,c \rangle$ consists of $w$, a space, and $c$.

More generally, suppose that $\langle w,c \rangle\_1$ and $\langle w,c \rangle\_2$ are two definitions of the pairing function such that:

1. There exists a polytime function $f$ such that $f(\langle w,c \rangle\_1) = \langle w,c \rangle\_2$.
2. There exists a polytime function $g$ such that $g(\langle w,c \rangle\_2) = \langle w,c \rangle\_1$.

Then if we define NP using $\langle,\rangle\_1$ and $\langle,\rangle\_2$ we obtain the same class. A *reasonable definition* is one that satisfies (1) and (2) for the pairing function I described above.

This sort of situation happens often in complexity theory. When the details of the input representation don't make a difference, we don't bother specifying them exactly. That's because we never actually refer to these details, so they are "too much information". You only need to worry about such details when you're actually programming, or when you're dealing with very weak complexity classes, for which converting between different input representations can be difficult.
> 1 votes

---
Tags: complexity-theory, notation
---


# Question
Title: Do poly-time algorithms exist whose time complexity is unprovable?
If not, is there a decision procedure that successfully classifies any polynomial time algorithm as poly-time within a time polynomially bounded by the length of the input algorithm?

# Answer
> 5 votes
Here is an example. Suppose that you're working within axiom system A, say ZFC. Gödel showed that if A is consistent then A can't prove that A is consistent. Consider the following program:

> On input $x$, go over all strings of length $\log |x|$, and check if one of them is a proof of the consistency of A. If so, loop for $2^{|x|}$ iterations. Otherwise, halt.

This is polynomial time if and only if A is consistent. If A could prove that this algorithm terminates in polynomial time then A has just proved that A is consistent, which is impossible if A is indeed consistent. Yet if we believe that A is consistent, then the machine *does* run polynomial time; but A unfortunately isn't strong enough to prove it.

Your second question asks whether there is an algorithm that, given a Turing machine $T$, answers in polynomial time whether $T$ is a polynomial time Turing machine. Unfortunately, this is undecidable. Suppose that we only consider Turing machines which don't depend on their input (say the first thing they do is erase their input). Such a machine $T$ runs is polynomial time if and only if it halts on the empty tape. Deciding whether a Turing machine halts is impossible.

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


title: Why is $P \subseteq NP$?

text:
# Question
Title: Why is $P \subseteq NP$?
The Clay paper gives a short proof on this in page 2: http://www.claymath.org/sites/default/files/pvsnp.pdf

However,

Where does it come from that these are inclusive sets and not separate?
Or that $|P| ≤ |NP|$?

# Answer
One definition of NP is "the set of languages accepted by non-deterministic Turing Machines in polynomial time."

There's a trivial transformation that lets us convert any deterministic Turing Machine into a non-deterministic one, which will have the exact same running time. Basically, you just take the same deterministic TM, rename it as non-deterministic, and don't use any non-determinism.

In short, any deterministic TM is also a non-deterministic TM (but the converse is not true).

So, suppose there's a language $L$. If we can accept $L$ in polynomial time with a deterministic TM, then we just make the trivial non-deterministic TM which runs identically, and we can now accept $L$ in polynomial time with a non-deterministic Turing Machine.

We know that $|P| = |NP|$ because both sets are infinite and countable. There are countably many Turing Machines, since each Turing Machine can be represented as an integer. There is at least one Turing Machine for each language in $NP$, and likewise, at least one Turing Machine for each language in $P$. Since both of these sets are infinite, they must be infinite countable.
> 6 votes

# Answer
P is the set of languages $L$ for which there exists a polytime function $f$ such that $$ x \in L \Longleftrightarrow f(x)=Yes. $$ NP is the set of languages $L$ for which there exists a polytime function $f$ and an integer $k$ such that $$ x \in L \Longleftrightarrow f(x,y)=Yes\text{ for some $y$ of length $|y| \leq k|x|^k$}. $$ (Here $|x|$ is the length of $x$.)

Hopefully you can now show that P$\subseteq$NP on your own.
> 3 votes

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


# Question
Title: The theory behind backpropogation, gradient calculation
I am reading a book about Neural Networks, that explains the backpropagation algorithm. It explains that the error function is the sum of error of all inputs, and that the algorithm minimizes this sum, which makes perfect sense to me, but than in goes on stating that to achieve that the gradient is calculated for each input, and then summed up. This last step is not understable to me.

Is it implying that the gradient of the sum of all errors (from all inputs) is equal to sum of gradients (from all inputs), that is - that the sum of gradients equals the gradient of sum?

This seems to me like an non trivial step, but it is not explained in the book.

# Answer
The gradient, just like the derivative, is linear: for functions $f,g$ on the same variables and scalars $\alpha,\beta$: $$ \nabla(\alpha f + \beta g) = \alpha \nabla f + \beta \nabla g. $$
> 5 votes

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


title: Quantum computer memory size

text:
# Question
Title: Quantum computer memory size
Quantum computers are going to have enormous number of operations per second (in some situations exponentially more than classic computers).

Does it also hold for memory size? Are QC going to have exponentially increased memory?

# Answer
No, quantum computers are not going to have an enormous number of operations per second, in fact they are probably going to be much slower in the foreseeable future. The situation with memory seems even bleaker – so far only a handful of bits.

The big advantage of quantum computers is that they can run quantum algorithms, which work rather differently from classical algorithms. Very informally, they provide a way of going through many possibilities at the same time. This gives an exponential speed up for some tasks, and a polynomial speedup for others – in terms of the number of operations. Even though each individual operation is going to be slower, since you need to run drastically fewer, the overall algorithm would run much faster.
> 7 votes

---
Tags: computation-models, quantum-computing
---


# Question
Title: Why is the running time of heapsort $O(n\log n)$?
```
Heapsort(A)
1 BUILD_MAX_HEAP(A)
2 for i=A.length downto 2
3    exchange A[1] with A[i]
4    A.heapsize=A.heapsize-1
5    MAX_HEAPIFY(A,1)

```

In the book on algorithms by CLRS the running time of this algorithm is given to be $O(n\lg n)$ as the for loop is executed $n-1$ times and each call of MAX\_HEAPIFY takes $O(\lg n)$.

But my question is does MAX\_HEAPIFY not depend on height of subtree at which it is called? Why then should it still be the same for all $n-1$ calls as $h$ will obviously differ?

# Answer
Each call of MAX\_HEAPIFY takes time $O(h) = O(\log n)$, where $h$ is the depth of the heap. Note that big O is an *upper bound* on the running time, not the exact running time. It is also true that the running time of MAX\_HEAPIFY is $O(n)$, for example.
> 6 votes

# Answer
The underlying datasctructure of heapsort is -like the name suggests- a heap. A heap has the property, that it is always complete except for the lowest level of the tree. That means, if you have $n$ Nodes, the maximum height of the tree is $logn$. Since heaps are usually implemented as Arrays you can easily compare parent and child nodes (e.g. let i be an index in the array, then the left child of any given node has the index $2i$, the right child has the index $2i+1$) and therefor you dont need to worry about any other complexity then the $logn$ element-comparisions and potential swaps you have to do, when running MAX\_HEAPIFY.
> 1 votes

# Answer
**Hint**:

The height indeed varies, so that the total count is $n$ times the **average** height.

Depending on how fast the height decreases, the average height can range from **a fraction** of the maximum height, to a constant !
> 1 votes

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


# Question
Title: Recursive definition of the set of strings over an alphabet
The problem is the following: Write the recursive definition for the set of all Strings Q over the alphabet {a, b} (i.e. the set of strings consisting of a's and b', for example a, baba, abbbabababba...)

I somewhat get the gist of what recursion definitions consist of, but this one has gotten me stumped a little bit, since we didn't really go into much detail about string recursion in my most recent class.

# Answer
> 1 votes
The recursive definition of a string goes roughly as follows.

A string is:

1. The empty string, or
2. $sa$, where $s$ is a string, or
3. $sb$, where $s$ is a string.

Presumably you're supposed to use some specific formalism to express this definition, which you'll have to figure out on your own. One possibility is $$ Q = \epsilon | Qa | Qb, $$ but this is just a guess.

---
Tags: recursion
---


# Question
Title: Efficient algorithm for determining if $\pm c_1 \pm c_2 \dots \pm c_n = 0$
> Suppose that we're given $n$ integers $c\_1, c\_2, \dots, c\_n$. We want to know if there is any assignment of $+$ and $-$ signs such that
>
> $$ \pm c\_1 \pm c\_2 \dots \pm c\_n = 0. $$

Does anyone know of a polynomial-time way to do this? Since there are $n$ integers, there are $2^n$ assignments of signs to consider, which grows rather quickly.

I've tried to phrase this problem in such a way that I can make use of dynamic programming, but DP usually lends itself to optimization sorts of problems, and this problem does not fall into that category (at least as stated).

# Answer
Hint: This is just the well-known NP-complete problem PARTITION.
> 7 votes

---
Tags: algorithms, decision-problem
---


# Question
Title: Why not use the channel capacity as the sliding window size?
In a sliding window protocol, if we use the maximum possible capacity of the channel as the size of the sliding window, efficiency will be theoretically 100%. What is the logic behind not doing this?

My guess is that this is done for throttling. Are there any other reasons?

**EDIT:** After reading the answer by bakuriu, I come to the conclusion that using the capacity as the sliding window size can make the system unreliable:

1. The receiver buffer may fill up and the increased transfer rate at the sender side will become useless.
2. Congestion and packet loss may increase. Reasons are pointed out in the linked answer.

But what if it is an Ethernet (preferably a LAN) using the `Selective Repeat` protocol for the data flow and `CSMA/CD` for choosing the sending station.

1. The receiver window would be of the same size as the sender window. So, filling up the receiver buffer should not be a concern.
2. There wouldn't be multiple stations competing for data transfer once the transfer has started (because of how CSMA/CD is defined).
3. In a wired connection (and preferably being a LAN), packet loss would be less.
4. Sender doesn't have to resend the whole window in case of packet loss or corrupted packet (because of Selective Repeat).

Do we usually try to use the `channel capacity` as the `sliding window size` in such (highly customized) cases?

# Answer
> 4 votes
Sliding windows are used to:

* Keep track which packets were sent and received, hence the data transmission is *reliable*
* Keep track of the memory available to the receiver. The receiver may fill its buffers and tell to the sender to slow down (because more packets will simply be dropped, causing the sender to re-send them with a probably bigger delay)

When multiple data streams pass through the same link you wont be able to use 100% of the capacity anyway, and probably more packets will be lost. In this situation sending more data simply means having to re-send the data later. That's why you want to avoid congestion and throttle the speed.

In summary: it is *not* true that sending data at the possible speed you can will result in the data being correctly transferred in a smaller time. It often simply means that you have to resend the same packets over again because they continue to get lost/dropped by congestioned routers/dropped by congestioned receiver. Sliding window are a way to control this and provide better overall performance.

Note: if you do *not* want a reliable transmission then sending at the maximum speed *is* better. However the amount of data that arrives correctly at the receiver may get quite small compared to what was sent.

---
Tags: computer-networks, network-flow
---


# Question
Title: Why do we use stacks and not queues on system-level?
From low OS-level function calls, to memory allocated to an application, all will primarily take a stack to perform LIFO operations.

Why don't we use queues and FIFO operations? It's just a matter of moving pointers anyway.

# Answer
> 5 votes
Because some things need to be done LIFO and some things FIFO.

For example, when a function call returns, it needs to return to the *last* item on the call *stack*, i.e., the function that called it. It would make no sense to return to the first item on the call-stack. Conversely, if you're serving requests, the next request you serve is the *first* one to enter the service *queue*. (It turns out that, actually, serving queues from the back can be more efficient but that has the obvious disadvantage that it risks starvation for things at the front of the queue and, in real-life queues of people, it just gives people a huge incentive to leave the queue and re-join.)

---
Tags: operating-systems, stacks
---


# Question
Title: Implementing a Boolean function with NOR gates
> Implement f(a, b, c, d) = Σ m(3, 4, 5, 6, 7, 11, 15) as a 2-level gate circuit
> (a) Using OR gates and NOR gates.
> (b) Using NOR gates only.

I have found that F=ab+d using Karnaugh map. I have also been able to construct the logic expression using OR gates and NOR gates as in part a of the question.

Can you please provide me some idea on how to construct the logic expression ab+d using NOR gates only?

***Please do not say this is a homework help question and close this thread. I'm not asking to do the entire homework, I have only asked for some idea on how to do part b.***

# Answer
Hint: you know it's a two-level circuit using only NOR gates. There is only one such circuit:

```
  OUT
   |
  NOR
  / \
 |   |
NOR NOR
/ \ / \
? ? ? ?

```

Can you now figure out where to place a, b and d to correctly construct the circuit? Since you have to repeat (at least) one input, does looking at symmetry help?
> 2 votes

---
Tags: logic, boolean-algebra, digital-circuits
---


# Question
Title: BIT: range updates, point queries; true meaning of tree[x]
for the past few days I've been studying Binary Indexed Tree (aka. Fenwick tree) data structure.

I understand the basic form of BIT (*point update, range query*), and I see the intuition behind it, but when it comes to *range update - point query* BIT I don't see the intuition behind it.

Let me be more specific:

1. let *tree* be an array where we represent our BIT
2. let *A* be an ordinary array where our array values are stored. both *tree* and *A* are initially zero

For the ***point update - range query***, we know that *tree\[x\]*, where *x* is some index, stores cumulative frequency for elements(values) *\[x - 2^r + 1, ... , x\]*, where *r* is position of the *last non-zero bit* (looking from left to right in binary notation of number *x*)

Example:

* array A: 1 3 6 7 5 5 2
* x: ------ 1 2 3 4 5 6 7 8
* tree(x): 1 2 1 3 2 3 1 7
* tree(6) = 3 (6 in binary is 110, r=1, 6 - 2^1 + 1 = 5; so tree(6) stores frequencies for 5 and 6; in our example, number 5 appears 2 times and number 6 appears only once)

But, for the ***range update - point query*** i don't know the following:

a) what tree\[x\] represents. What is the true meaning for the value that is stored in tree\[x\] (for *range update - point query*).

b) To update range, say from *a* to *b* with value *v*, we will do the following operations:

* *update(a, v)*
* *update(b + 1, -v)*
* and then *query(x)* returns value of A\[x\]

Why does the query(x) returns value of A\[x\], what is the proof(please give some example or resource with example) for that.

In quest for the answer i found the following resources but none of them helped for the questions above:

1: https://programmingcontests.quora.com/Tutorial-Range-Updates-in-Fenwick-Tree

2: http://apps.topcoder.com/forums/;jsessionid=1749A5CAC2EA52B51F5509E8355A2CD3?module=Thread&threadID=715842&start=0&mc=8#1407869

# Answer
For BIT and its variants, I recommend this article: http://coutcode.com/blog/binaryindexedtree/

The core of BIT is **point update - range query**, ie. for array $A\[1 \dotsc n\]$, BIT supports following operations:

1. $A\[k\] \leftarrow A\[k\] + d$ (**Point update(k,d)**)
2. query partial sum $S\[k\] = A\[1\] + A\[2\] + \dotsb + A\[k\]$ (**Range query(k)**)

Other variants are just converting to 1 or more of this case.

For **range update - point query**, it requires support following operations for array $A\[1 \dotsc n\]$:

1. $A\[i\] \leftarrow A\[i\] + d$ for all $a\le i \< b$. (**Range update(a,b,d)**)
2. query value of $A\[k\]$. (**Point query(k)**)

First, noting that after range update $A\_1\[i\] \leftarrow A\[i\] + d, (a \le i \le b)$, we have $$\begin{align}A\_1\[a\]-A\_1\[a-1\]=&A\[a\]-A\[a-1\]+d\\A\_1\[b+1\]-A\_1\[b\]=&A\[b+1\]-A\[b\]-d\\A\_1\[i\]-A\_1\[i-1\]=&A\[i\]-A\[i-1\]\ (i\notin\\{a,b+1\\})\end{align}$$ Taking $$D\[i\] = \begin{cases}A\[i\],&i=1\\A\[i\]-A\[i-1\],&1\<i\le n\end{cases}$$ then there are only 2 updates $$D\[a\]\leftarrow D\[a\]+d\\D\[b+1\]\leftarrow D\[b+1\]-d$$ and $$\begin{align}A\[k\]=&A\[1\]+(A\[2\]-A\[1\])+\dotsb+(A\[k\]-A\[k-1\])\\\=&D\[1\]+D\[2\]+\dotsb+D\[k\]\end{align}$$

Thus building BIT on $D\[1\dotsc n\]$, we convert the range update$(a,b,d)$ on $A$ to 2 point updates $(a,d)$ and $(b+1,-d)$ on $D$, and the point query $(k)$ on $A$ is just the range query $(k)$ on $D$.
> 3 votes

# Answer
There is a simple duality between the two variants: Say you have a data structure that supports point updates and range queries A. Then we can easily turn it into a data structure B that supports range updates and point queries:

For each range update (\[1..x\], a) in B, do a point update (x, a) in A. For a point query x in B, do a range query \[x..infinity\] in A.

That's why the two versions are basically exactly the same, with the loop conditions swapped.
> 1 votes

---
Tags: algorithms, data-structures
---


# Question
Title: Difference between First Order Logic and Predicate Calculus
I see the two used interchangeably. Is one the subset of the other or are they both the same thing?

# Answer
First-order logic and first-order predicate calculus are the same thing, which is exactly why the terms are used interchangeably. See, for example, Wikipedia:

> First-order logic \[...\] is also known as first-order predicate calculus, the lower predicate calculus, quantification theory, and predicate logic.
> 4 votes

---
Tags: first-order-logic
---


# Question
Title: Does the databus size matter for determining the range of the memory addresses?
If you have byte addressable memory, does it matter if you have a 32 bit or 64 bit databus for the range of the memory addresses for the words of the memory?

E.g. : Assume a 32-bit word. If you have a processor connected to a byte addressable $2^{32}$ byte memory,

Would the address of the lowest word be 0 and the address of the highest word simply be $2^{32}-4$ (0xFFFFFFFC), regardless of whether your databus size is 32 bit or 64 bit?

What difference would it make when you assume a 64-bit word or a 16-bit word?

# Answer
> 1 votes
On most general purpose CPUs since the '70s, addresses are byte addresses. This includes 6800, 680X0, PowerPC, x86, ARM, MIPS, SPARC, SuperH, Z80, PA-RISC...

* There are sometimes exceptions with DSPs that are not meant for processing bytes. (example : Analog Devices SHARC)
* Some small embedded CPUs may also have different addressing, or separate address spaces for instructions (example : Microsemi PIC)
* Some CPU support address spaces where data is aliased and expanded. For example mapping each bit at a different byte address (example : Some ARMs)

The actual width of the data bus is not directly related to the CPU internal architecture, wether it is a 8bits, 16bits or 32bits CPU.

For example:

* The MC68008 was a 16/32bits CPU with a 8 bits bus.
* The G3/G4 PowerPCs (PPC603, MPC755, MPC7450...) are 32bits CPUs with a 64bits data bus.

With a 32bits CPU, aligned 32bits word adresses are 0000\_0000, 0000\_0004, 000\_0008 ... to ... FFFF\_FFF0, FFFF\_FFF4, FFFF\_FFF8, FFFF\_FFFC.

Some CPUs can do unaligned accesses, usually slower than aligned ones. An example : x86.

In that case, you could access a 32bits value at address 0000\_0001.

---
Tags: computer-architecture, memory-hardware
---


# Question
Title: For tiling simply connected regions with shapes beyond just rectangles, is there a lower # of tile shapes needed for NP-completeness?
In "TILING SIMPLY CONNECTED REGIONS WITH RECTANGLES" by Igor Pak and Jed Yang, they show there is a set of "no more than $10^6$ rectangles" such that the problem of tiling an arbitrary simply connected region with these rectangle shapes is NP-complete. However the number of rectangle shapes $10^6$ seems pretty extreme. Maybe it's hard to close the gap on P vs. NP-complete for tiling in terms of the number of rectangle shapes available, but what if we allow more complex pieces such as non-rectangular Tetris pieces and larger non-rectangular pieces? (We could insist the piece shapes are all simply connected, but I'm not adamant about that).

Can we show NP-completeness for tiling a simply connected region with a much smaller set of (potentially non-rectangular) pieces available, compared to $10^6$?

The authors mention and rely upon an NP-completeness result for tiling with "Generalized Wang Tiles" that seem to use coloring as well as shape, and claim that NP-completeness can be achieved with a fixed set of 23 generalized Wang tiles. However I wasn't able to decipher this result to figure out how many ordinary non-colored (and e.g., perhaps also simply connected) tile shapes are needed to establish NP-completeness.

# Answer
Found their paper on ArXiv. It is quite easy to go from coloured Wang tiles to uncoloured shapes by introducing zig-zag boundaries, like a jig-saw, as illustrated in their Figure 3. So then still 23 tiles are needed, as colours are simply replaced by boundaries.

Their contribution is to move from boundaries to only rectangular tiles. The authors state in Lemma 3.3 how many rectangles are needed to replace coloured Wang tiles, and a long Section 5 is devoted to the proof of that lemma.
> 3 votes

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


title: Show that a function is not a PRFs

text:
# Question
Title: Show that a function is not a PRFs
I am studying cryptography and having some trouble with the PRFs How do I show that $f\_{k}(x) =x+k^2$ mod $2^n$ is not a Psuedo Random function? I know that I need to show that the distignuisher can tell this is not random with a better then $\frac{1}{2}$ probability but how would it do that? (I don't just want an algorithm but a means to find such an algorithm for a query attack) Thanks

# Answer
> 1 votes
Any known plaintext attack instantly reveals the key: $$f\_k(x) - x + 2^n \equiv k^2\mod 2^n$$

On top of that, even without knowing the key or the plaintext, here's a property that no random function should have:

$$f\_k(x + 1) \equiv f\_k(x) + 1 \mod 2^n$$

# Answer
> 0 votes
The way you show $f$ is not a PRF is by going back to the definition. You say you are a pure math guy, so you should be used to this. It's the standard dance: you look at the definition, and expand it out.

In this case, the definition of what it means for $f$ to be a PRF is: there is no adversary $A$ such that (blah). So, the way you prove that $f$ is *not* a PRF is by demonstrating the existence of an adversary $A$ such that (blah). How do you demonstrate that? By exhibiting an example of such an adversary.

---
Tags: proof-techniques, cryptography, randomness
---


# Question
Title: Register images containing objects with varying distance to the cameras
I'm learning about using image registration to align two images, e.g., two photographs of the same scene taken from a slightly different location. What factors influence how well we can align the images? Does the distance to the objects in the image influence its effectiveness of alignment, and if so how? What about the amount of variation in the distances to the objects in the images: how does that influence the effectiveness of the alignment?

---

Background: I came across the notion of "global image registration" when reading the paper

> "Mutual information based registration of multimodal stereo videos for person tracking", by Stephen J Krotosky and Mohan M Trivedi, in Computer Vision and Image Understanding 2007.

I believe "global image registration" means to use *one* transformation function for the registration. The authors state that global image registration is accurate when all objects of interest are in the same plane. I am trying to figure out exactly what they mean.

At first, I assumed that the authors mean objects across different frames (then needed to have a similar distance to the camera across the frames), where the previously calculated registration is supposed to work for each frame.

Then I thought that they maybe mean the registration of a single image pair and that objects of interest must be in similar distance to the camera.

To check this, I registered two pairs of image. The first pair has a lot of depth, the second pair does not, i.e., the first pair contains objects of varying distances to the cameras. It can be seen that the latter is much better registered than the former. This suggests that my second statement is correct: an image registration based on one transformation function is not able to register an image well if there is a lot of variation in the distances to the objects in the image. Is this correct?

First image pair:  First image pair registered:  Second image pair:  Second image pair registered:

# Answer
> 3 votes
Yes, if there is a lot of variability in the distance to the objects in the scene, then global registration will work poorly.

Let me back and give some background on how global image registration works. It tries to align the two images. In its simplest form, the only transformation that is allowed is translation: it tries to find a way to shift all the points in the left image in a constant direction, to make it match the right image as much as possible. In other words, it looks for a translation $T$ such that $T(I\_1)$ matches $I\_2$ as much as possible, where $I\_1,I\_2$ are the two images.

With this background, you can see why global image registration won't work well for scenes with objects at multiple distances, when you have two pictures taken from a different point. Imagine taking one picture, then moving left one mile, then taking another picture. Objects that are far away won't shift their location in the image very much, but images that are close will shift to the right a lot in the second image. Global image registration tries to find a constant translation that makes everything match up in the two images, but there is no single translation that will work well. To make the distant objects match up, you'd need a small translation; to make the nearby objects match up, you'd need a large translation; and there is no way to reconcile these differences.

This is the major problem you're seeing. There are other problems as well, due to the fact that the image is only a 2D representation of a 3D scene. For instance, if you take two photographs from two different positions, then not only will the location of the objects in the images shift, but also you'll be viewing them from two different angles. Global image registration can't un-do that, because it can't see around corners. Look at the two images of the statue. Imagine that the statue had a little bit of bird dropping on the left side of the person's nose (our left; the person's right). Then the bird dropping might be visible from the second photograph, which is taken straight-on, but might not be visible from the first photograph, which is taken from an angle. Alignment can't fix this, as it can't magically make up for things that aren't visible in the photograph.

---

This answer talks about global image registration based purely on translation. In general global image registration typically allows a broader set of transformations: a typical example might be something that allows translation, scaling (zoom in or out), and rotation; or translation, scaling, and skew; or an arbitrary linear/affine transformation; or an arbitrary homography / projective transformation. Unfortunately, none of these really help with the problems outlined above. In general, no rigid transformation will eliminate the problems I've sketched in this answer, so this answer is pretty general. In principle, non-rigid transformations might be more effective at handling variation in depth; I don't have any experience with that form of image registration.

---
Tags: image-processing, computer-vision
---


# Question
Title: Are nearly all natural numbers compressible?
A simple counting argument shows most strings can't be compressed to shorter strings. But, compression is usually defined using Kolmogorov complexity. A string is compressible if its Kolmogorov complexity is less than its length, $K(s) \< |s|$. The Kolmogorov complexity of a string is defined as the size of the smallest Turing machine (TM) that writes the string and halts when given a blank tape. I want to define the size of a TM as the number of states the machine has. I want to use a simple type of TM known as a Busy Beaver. BB's use two symbols, 0 and 1. A BB blank tape is initialized to all 0's and is unbounded in both directions.

Let the Kolmogorov complexity of natural number $n$, $K(n)$, be the number of states in the smallest BB that writes $n$ 1's and halts when given a blank tape. I use this definition so I can use known results about busy beavers, particularly Rado's sigma function, $\sum(n)$. $\sum(n)$ is defined as the maximum number of 1's an n-state BB can write and halt when given a blank tape. It is known $\sum(n)$ grows faster than any recursive function. This shows there is no recursive limit on how much a natural number can be compressed.

$\sum(2)=4$ so $K(4)=2$. This means 4 is a compressible number. This is the definition of the BB:

A0: 1RB / B0: 1LA

A1: 1LB / B1: 1RHalt

"A0: 1RB" means in state A on input 0 write 1, move one position right, and switch to state B. We can "extend" this machine to create new machines that compress natural numbers. To extend this machine replace the halt state with a new state. On input 0 this state writes 1 and halts. On input 1 it writes 1, moves one position right, and stays in the same state.

A0: 1RB / B0: 1LA / C0: 1RHalt

A1: 1LB / B1: 1RC / C1: 1RC

This 3 state machine writes 5 1's and halts. This proves $K(5) \leq 3$ and 5 is a compressible number. In fact, all numbers greater than 3 are compressible by at least 2 because we can write the first 4 1's using only 2 states. $\forall n(n\>3 \rightarrow K(n) \leq n-2)$

We know natural number $n$ can be represented as a binary number with $log\_2(n)+1$ bits. Let a number be super compressible if $K(n) \< log\_2(n)+1$. We see 4 is super compressible because $K(4)=2 \< log\_2(4)+1 = 3$. It is known $\sum(5) \ge 4098$. This means $K(4098) = 5$ and 4098 is super compressible. By extending this 5-state machine we can show 4099 through 4107 are also super compressible. In general, the range $\sum(n)$ through $\sum(n)+log\_2(\sum(n))-n$ will be super compressible. For example, it is known $\sum(6) \ge 3.515 * 10^{18267}$. This proves the range $3.515 * 10^{18267}$ through $3.515 * 10^{18267} + log\_2(10^{18267})$ is super compressible.

Are all large enough natural numbers super compressible? If not, why not?

Note there are lots of machines besides the ones defined by $\sum(n)$. There are probably lots of halting 5-state machines that write more that $2^5$ 1's and less than 4098 1's. All such machines define ranges of super compressible numbers. I previously asked a similar question without getting an adequate answer.

# Answer
I'm not entirely sure what you're scheme is. However, given the information in your question, I should be able to simply answer the question in your title.

It seems that in your scheme the asymptotic growth of the range of numbers that are "super compressible" is:

$$\[10^n, 10^n+log(10^n)\] = \[10^n, 10^n+n\]$$

However, $\lim\_{n\to\infty} {n \over 10^n} = 0$, so I'm afraid that when the numbers get big nearly no numbers are super compressible. Additionally, since $\lim\_{n\to\infty} {cn \over 10^n} = 0$ for any constant $c$, this result is irrespective of how many sequences of precomputed 'super compressible' numbers you find.

---

It's hard (at least for me, give a call to our friend Shannon) to show this rigorously, but even if you add more and more sequences of 'super compressible' numbers, you will never be able to represent more than double the range using one extra bit of information.
> 3 votes

# Answer
For every $n$ there is a "busy beaver" machine (i.e., a Turing machine on the tape alphabet $\\{0,1\\}$ run on the empty tape) which outputs $1^n$ using $O(\log n/\log\log n)$ states, which is asymptotically optimal (up to constants).

Here is how this machine works. For every $C$, we will construct such a machine having $O(\log n/C) + O(C2^C)$ states. The machine will first write the binary representation of $n$, and then use $O(1)$ states to convert it to its unary representation (that is, $1^n$); we will only describe the first phase.

The machine runs in $\log n/C$ rounds, maintaining a unary counter whose value at round $r$ is $1^r$ (after all the rounds finish, we erase the counter). At each round, we write $C$ bits of the binary representation of $n$. This is accomplished using $O(C2^C)$ states which implement adding $C$ bits (for which choice of $C$ bits), and $O(\log n/C)$ states for control (we use the unary counter to switch control to the correct state). This completes the description of the machine.

A machine with $S$ states on the binary tape alphabet has description size $O(S\log S)$. Hence we expect that the optimal answer be $O(\log n/\log\log n)$. Indeed, if we choose $C$ very carefully to be $\log (\log n/(\log\log n)^2)$, then the construction above gives a "busy beaver" machine with $O(\log n/\log\log n)$ states, which is optimal up to constants.

If the tape alphabet is allowed to grow with $n$, then $O(1)$ states suffice to output $1^n$: the alphabet will be of size $n + O(1)$, and we will use a certain cell as a counter. This construction shows that it is important to limit the tape alphabet.
> 6 votes

---
Tags: integers, kolmogorov-complexity
---


title: Ternary Search Recurrence Relation

text:
# Question
Title: Ternary Search Recurrence Relation
I am trying to work out the recurrence relation for Ternary Search. This is what I came up with:

```
C(n) = C(n/3) + 2

```

However, I talked to my professor and he said it's not correct. He says that we need to take all of their cases into account. This part confuses me a little bit, can you please clear it for me?

Thank you.

# Answer
Hint: Recall what you are actually doing in ternary search - you basically partition the list into 2 parts, on of roughly $n/3$ elements, and the other of $2n/3$ elements.

So, on a bad day (worst case) you do $2n/3$ recursive calls.

Then the recurrence relation is $$T(n) = T(2n/3) + c $$

I'll cheat a bit here and use the master theorem to jump to the conclusion that $T(n) \in \Theta(log\ n)$
> 2 votes

# Answer
Ternary search (a)-\> If you divide the array into 3 subsets of equal size and consider 3 cases key lies in left,middle, right tree, Then the recurrence : T(n)=T(n/3)+O(1) must be correct, because you are searching in an array of size(n/3).

Ternary search (b)-\> If partitioned in size (n/3) and (2n/3) 2 partitions then the recurrence T(n)=T(2n/3)+O(1) holds.

Both are different variations of ternary search
> 0 votes

---
Tags: algorithms, recurrence-relation
---


# Question
Title: Shortest-Path for Weighted Directed Bipartite Graphs
I did a research project in which I seek to move a car through zones from origin to destination. This allows for the formulation of a bipartite graph because only adjacent zones can be connected. Each edge has a non-negative weight of time. I look to find the shortest path between source and sink, given the weights and directions of the edges. The structure of the graph is quite simple, all adjacent zones are connected. The bipartite graph looks this this.

My question is what is the best shortest-path algorithm for such a graph?

# Answer
> 1 votes
Merge every zone into one vertex. You now have a linear path, with one or multiple edges between each vertex. Since this graph does not branch, you can simply choose the cheapest edge between every vertex directly.

A small illustration I made:

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


# Question
Title: Graph Has Two / Three Different Minimal Spanning Trees?
I'm trying to find an efficient method of detecting whether a given graph G has two different minimal spanning trees. I'm also trying to find a method to check whether it has 3 different minimal spanning trees. The naive solution that I've though about is running Kruskal's algorithm once and finding the total weight of the minimal spanning tree. Later , removing an edge from the graph and running Kruskal's algorithm again and checking if the weight of the new tree is the weight of the original minimal spanning tree , and so for each edge in the graph. The runtime is O(|V||E|log|V|) which is not good at all, and I think there's a better way to do it.

Any suggestion would be helpful, thanks in advance

# Answer
> 7 votes
Kapoor & Ramesh (proper SIAM J. Comput. version, free(?) personal website version) give an algorithm for enumerating all minimum spanning trees in both weighted and unweighted graphs.

My understanding of the basic idea is that you start with one MST, then swap edges that lie along cycles in the graph (so as long as the weights are okay, you're replacing one edge with another that you know will reconnect the tree).

For the weighted case they give a running time to list all minimum spanning trees of $O(N\cdot|V|)$ where $N$ is the number of such spanning trees. It enumerates them in order of increasing weight, and my current (cursory) understanding suggests that it's perfectly feasible to terminate the algorithm after it has generated a given number of trees (as it just starts with the MST and produces them sequentially).

# Answer
> 2 votes
One can show that Kruskal's algorithm can find every minimal spanning tree; see here.

Therefore, you can execute Kruskal and whenever you have multiple edges to choose from, branch. Once you have branched $k$ times, you know that there are at least $k$ different minimal spanning trees. Unfortunately, multiple branches may result in the same tree by adding edges of same weight in different orders, so this does not help much without further work/insight.

# Answer
> 1 votes
To see if there is more than one MST, consider e.g. Kruskal's algorithm. The only way it could construct different MSTs is by leaving out edges by choosing another one when there are several with the same weight. But those same-weight edges might have been ruled out because they formed a cycle with lighter edges...

So you should run Kruskal's algorithm, and when there are several edges with the same weight to consider, add all of them that can be added without creating cycles. If there is an edge of this weight left over, and it doesn't close a cycle with any of the edges with lower weights (which were added before), there is more than one MST. Checking if there are exactly 2 or 3 or more, etc looks much harder...

# Answer
> 0 votes
Modidying Kruskal's algorithm: While ordering the edges, cluster edges with equal weight. Now, at the point where you process the edges in order, each time you reach a new cluster, first check all edges separately and remove from the cluster those that would close a cycle, given what was built before the cluster. Then run all the remaining edges in the cluster now trying to add them to the MST. If any of them closes a cycle, then that was necessarily because of other edges of the same cluster inserted before, meaning that you have more than one MST.

That solution preserves the complexity of Kruskal's algorithm, only it increases the time for each edge processed.

---
Tags: algorithms, graphs, spanning-trees
---


# Question
Title: Restrictions that set binary variable to 1 when integer variable equals x, 0 otherwise
I have this problem: I'm building an integer linear program, which I'm going to give to an ILP solver. I have a binary variable Y which can be either 1 or 0 and an integer variable MONTH which takes integer values 1-12.

I have to give restrictions such that Y = 1 if MONTH = 1, and Y = 0 otherwise.

I don't know how to do this. I can think of a way to make Y = 1 when MONTH = 1, like Y + MONTH \> 2, but I can't think of a restriction to make Y = 0 otherwise.

# Answer
> 1 votes
In this case (where the possible sets of values are finite) a graphical approach can work nicely for determining a suitable set of constraints. Draw the points in the set $\\{1,\dots,12\\}\times\\{0,1\\}$ in the plane, using $+$ for allowed and $-$ for disallowed combinations:

$\begin{array} & & + & - & - & - & - & - & - & - & - & - & - & - \\ & - & + & + & + & + & + & + & + & + & + & + & +\end{array}$

Can you find a set of lines separating the $+$s from the $-$s? Note that $Y+MONTH\ge 2$ already take care of the $-$ in the bottom left corner.

---
Tags: linear-programming
---


# Question
Title: Intuitive description for training of LSTM (with forget gate/peephole)?
I am a CS undergraduate (but I don't know much about AI though, did not take any courses on it, and definitely nothing about NN until recently) who is about to do a school project in AI, so I pick a topics regarding grammar induction (of context-free language and perhaps some subset of context-sensitive language) using reinforcement learning on a neural network. I started to study previous successful approach first to see if they can be tweaked, and now I am trying to understand the approach using supervised learning with Long Short Term Memory. I am reading "Learning to Forget: Continual Prediction with LSTM". I am also reading the paper on peephole too, but it seems even more complicated and I'm just trying something simpler first. I think I get correctly how the memory cell and the network topology work. What I do not get right now is the training algorithm. So I have some questions to ask:

* How exactly does different input get distinguished? Apparently the network is not reset after each input, and there is no special symbol to delimit different input. Does the network just receive a continuous stream of strings without any clues on where the input end and the next one begin?
* What is the time lag between the input and the corresponding target output? Certainly some amount of time lag are required, and thus the network can never be trained to get a target output from an input that it have not have enough time to process. If it was not Reber grammar that was used, but something more complicated that could potentially required a lot more information to be stored and retrieved, the amount of time need to access the information might varied depending on the input, something that probably cannot be predicted while we decide on the time lag to do training.
* Is there a more intuitive explanation of the training algorithm? I find it difficult to figure out what is going on behind all the complicated formulas, and I would need to understand it because I need to tweak it into a reinforced learning algorithm later.
* Also, the paper did not mention anything regarding noisy **training** data. I have read somewhere else that the network can handle very well noisy testing data. Do you know if LSTM can handle situation where the training data have some chances of being corrupted/ridden with superfluous information?

# Answer
LSTM is designed to process a stream of data chunks (each chunk being the set of inputs for the network at this point in time) that arrive over time and observe features occurring in the data and yield output accordingly. The time lag (delay) between the occurrence of features to recognize may vary and may be prolonged.

One would then train the network by streaming training examples in randomized ordering which should also have some timeshift noise added in the form of idle passes (have the network activate when inputs are at default idle values eg: when no audio in the case of a speech processor) \[exception: if any training data should obey periodic timeshift patterns such as music then the timeshift noise should keep the timeshifting synchronized eg: in music making sure a start-of-measure training example isn't shifted to mid-measure and so forth\]

It is possible also to have a semi supervised setup where the network is always in a training configuration and it's trained with examples that expect output of an idle value when no feauture is present or the appropriate expected value when a feature is presented to train).

If feedback format training is desired it can be emulated by:

1. saving the internal state (time t)
2. activating the network on current inputs (now at t+1)
3. supervisory process evaluates the output obtained at t
    * 3a if correction is needed first rewind to the saved state (rewinds network back to t)
    * 3b generate a training example with the correction
    * 3c run a train (backprop) pass for this slice rather than an activation

thus one implements a feedback style system since training examples are basically only created while the network is "getting it wrong." The feedback format is useful if one wants the network to attempt improvisation (like Schmidhuber's music example).

* it should be pointed out that part of the correction feedback (and thus training examples) necessarily includes those that enforce idle valued output when features are not present at the current time

It was mentioned by the OP that \[there is no separation of inputs\] except that actually there is. If one thinks of a voice recognition scenario one has periods of utterances (features the LSTM should detect) interspersed with long periods of silence. So to address the concern it would be fair to say those periods of silence are in fact separating the sequenced groups of inputs (those silences too are actually a feature the network needs to detect and learn to respond with idle valued outputs ie: learn to do nothing when silence).

## A note about resetting of the network

Any reset or recalling of a saved network state in the LSTM sense has a meaning of "go back in time" thus undoing any learning the LSTM performed prior to the reset.

Thus you were correct in stating LSTMs are not reset prior to each training sample nor tranining epoch. LSTMs want their data streamed, or provided in an 'online' manner, so-to-speak.
> 1 votes

---
Tags: formal-languages, machine-learning, artificial-intelligence, neural-networks
---


# Question
Title: What is the difference between complexity theory and computability theory?
What is the difference between complexity theory and computability theory? Is there any overlap between the two or are they completely different? Or is one a subset of the other?

# Answer
Put succinctly, computability theory is concerned with what can be computed versus what cannot; complexity is concerned with the resources required to compute the things that are computable.

As such, the fields are somewhat disjoint. Complexity theory is interested in a fine-grained classification of computable problems, with "it's uncomputable" as a worst-case scenario where we throw up our hands and give up. Computability theory (though one wouldn't realise this from an undergrad course) is interested in a fine-grained classification of uncomputable problems, with "it's computable" as the case at the bottom that's left to others to deal with.

However, there is some overlap of techniques, at least at a high level. In both cases, one typically uses the existence of an algorithm to demonstrate membership in a class and proofs of hardness are usually by reductions. Diagonalization also plays a role in both, proving things like the time and space hierarchy theorems in complexity, and the undecidability of halting problems in computability.
> 4 votes

# Answer
Computability is about what *can* be computed.

Complexity is about *how efficiently* can it be computed.
> 2 votes

---
Tags: complexity-theory, terminology, computability
---


# Question
Title: Does solving mathematical equations with Cellular Automata structures means it is universal?
I'm working on a research about Elementary Cellular Automata (ECA), and i found a method to build a system that can solve mathematical equations by using a specific cellular automaton structure.

The system is about encoding the equation into numbers and by applying some rules, these numbers are transferred to a Cellular Automaton structure.

For example =\> x^3-81=0 , after encoding it to numbers, it showed a structure contains 3 triangle, which is the answer of the equation encoded ===\> (x^3-81=0) ==\> (x^3=81) =\> (x=3).

---

So, i have read the article about turing-complete:

> a system of data-manipulation rules (such as a cellular automaton) is said to be Turing complete or computationally universal

What i want to say is, the equation was transferred to numbers {data-manipulation rules} and it computed the input (the equation), then showed the answer (output).
Does that makes the system a turing complete ?

---

I have also tested other equations:

1. x^2-25=0
2. x^3-27=0
3. x^4-16=0

And the system always shows the right answer as triangles.

---

# Answer
If you can solve arbitrary equations involving an arbitrary number of unknowns, then you have shown universality, as explained below. So there is a sense in which your broad question "solving mathematical equations means universality" is actually true -- but we have to precisely define what "mathematical equations" mean here. From your actual examples it seems you are not at the final goal of showing universality: it is not sufficient to solve ploynomial equations in a single variable.

If the equations you can solve are so-called Diophantine equations, then your system is universal. That is, polynomials with multiple variables and integer coefficients, and solved with solutions in the natural numbers. According to the solution of Hilbert's tenth problem such equations encode recursively enumerable sets (of natural numbers). The question whether the polynomial can have value $0$ with fixed \`input' value of the first variable codes membership of that value in the set we compute. Or as wikipedia states: "*Every recursively enumerable set is Diophantine*". This seems universal to me.

To see how complicated these polynomials can be, have a look at this Formula based on a system of Diophantine equations for the prime numbers. (This example generates prime numbers, so is slightly different, but can be tweaked.)

The right definition of universality is not always clear. We must encode input and output in a way suitable to the machine at hand (here the cellular automaton) without giving away parts of the solution. I remember some controversy concerning this.
> 4 votes

---
Tags: turing-machines, computation-models, cellular-automata
---


title: Convex Hull in no particular order

text:
# Question
Title: Convex Hull in no particular order
The proof for the $\Omega(n\log n)$ lower bound for calculating the convex hull by using order-type predicates that I have come across uses the fact that if there was possible to calculate the convex hull in time better than this, then we could do sorting using the same technique, but as it is known that sorting has an lower bound of $\Omega(n \log n)$, hence the lower bound for calculating the convex hull is also the same.

My question is, what if we don't want the convex hull in a cyclic order (clockwise or anticlockwise)? What if we just want the points lying on the convex hull. Surely, in such a case, we can't reduce sorting to this problem and hence the logic for lower bound does not hold. Do there exist any such algorithms? Or some alternative proof that still makes the previous lower bound hold true for this problem?

# Answer
The generalization of comparison sorting you're looking for is algebraic decision trees. In this model, element distinctness is the standard problem with an $\Omega(n\log n)$ lower bound. The reduction to convex hull is straightforward: $n$ input numbers $x\_1,\ldots, x\_n$ are distinct if and only if the convex hull of $(x\_1,x^2\_1), \ldots, (x\_n,x^2\_n)$.

These lower bounds depend crucially on the decision tree model. For the word RAM, it is a famous result of Chan and Pătraşcu that $o(n\log n)$ is possible.
> 1 votes

---
Tags: complexity-theory, time-complexity, computational-geometry, sorting
---


# Question
Title: Star-free decomposition of regular language given by regular expression
I was wondering: is there an algorithm to decompose any regular expression, provided it doesn't use complementation, into one or more regular expressions which don't use Kleene star (only catenation and union).

Right now I'm reading On the Decomposition of Finite Languages by A. Mateescu, A. Salomaa and S. Yu, but this paper doesn't seem to discuss this problem, but that's where I get the idea.

# Answer
> 3 votes
No. If the regular expression encodes an infinite language, then there is no way to decompose it that way. Without the Kleene star, regular expressions can only express finite languages.

I realize this is a rather trivial answer, and it begs the next question: what if we are promised that the language is finite? In that case, the answer is yes. Here are two ways to see that the answer is yes:

Approach #1: Since the language is regular, we can find a DFA that recognizes it -- let's choose the minimal DFA. Since the language is finite, this DFA will not have any loops in it. Now if you apply the standard algorithm for converting a DFA to a regular expression, the result is a star-free regular expression. In fact, you get out only a single regular expression.

Approach #2: If the language is finite, then you can enumerate all of the words in the language, say $L=\\{w\_1,w\_2,\dots,w\_n\\}$. Therefore $w\_1 + w\_2 + \dots + w\_n$ is a regular expression for $L$.

Credit: The answer for the case where the language is finite is due to @J.E. Pin.

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


title: The 50 value problems in TAoCP

text:
# Question
Title: The 50 value problems in TAoCP
This is just a question for fun and specifically for those who have read the reference pervasively.

I have been reading the work of Knuth's The Art of Computer Programming and struggling and having a lot of fun with its exercises. I was very impressed that Fermat's Last Theorem had a difficulty of 45 in Knuth's difficulty scale.

I was wondering, if anyone of you have seen exercises with rank ≥50.

Perhaps a more interesting question, what is the current status of such problems nowadays!?

# Answer
Knuth's scale goes up to 50 (for "unsolved research problems"). Note that the scale is meant to be (roughly) logarithmic, i.e., adding 10 to the number multiplies the work required by a factor, with 50 meaning some so ridiculously large amount of work to be done that it can be taken practically as "infinite".

Fermat's Last Theorem used to be 50 as an example in the preface, with Wiles' proof it is now "just" extremely hard, i.e., it got demoted to 45 in later editions.

So the answer to the question is "no". By *definition* 50 is the highest value on the scale.
> 5 votes

---
Tags: research
---


# Question
Title: use of Hamming Distance in Communication Networks
I am trying to put things in places on the use of Hamming Distance (HD) in error detection and correction in Computer Networks. I'm looking for correction/verification on the following:

HD is a measure of how well the error-detection/correction can/did perform. It is not an error detection or correction method by itself.

Part of the input to HD is the code-words-- the set of valid codes, say set $C$ that are to be transmitted. With this code-set at hand, $d\_{min}$, is the minimum of HDs between any two word pairs in $C$.

What HD tells is,

In this code set $C$, the best that an error detection algorithm can do is

* to detect ($d\_{min}-1$)-bit errors, i.e., errors in which $d\_{min}-1$ of the bits are flipped,

and

* to correct ($(d\_{min}-1)/2$)-bit errors.

Hamming Distance is a method to set the boundaries how well an error-detection/correction scheme can do on a specific case (specific set of messages transmitted). HD itself isn't an error-detection/correction scheme by itself.

Am I missing anything here?

TIA.

Please note: I've seen some useful discussions including Hamming distance required for error detection and correction and Hamming distance necessary for detecting d-bit error and for correcting a d-bit error.

//==================================

EDIT:

HD is a scheme that has use in many contexts that the coding theory applies.

***This Q is about the use of Hamming Distance in error detection/correction in Communication Networks.***

More specifically-- consider a stream of bits transmitted by a node on one end of a link to the node on the other end of that link.

What use is it here? Other than telling how well a particular detection/correction method can do on an assumed set of messages transmitted in that stream.

//===================================

EDIT 2:

Figured this -- this was an early Q in not-enough-time.

Not letting me to delete the Q.

Thanks all.

# Answer
> 1 votes
Your terminology is a bit off. *Hamming distance* is a metric on words given by the number of different symbols. The *minimal distance* of a code is the minimal (Hamming) distance between two different codewords, and enjoys the properties you listed.

---
Tags: computer-networks, coding-theory, error-correcting-codes, hamming-code
---


# Question
Title: Minimizing inversions in an array with a single swap
This was asked in the (very) recently concluded Hackerrank Worldcup. Paraphrased:

> Given a permutation $a$ of integers from $1$ to $N$, how can I minimize the number of inversions by a single swap of any two integers?
>
> An inversion is a pair of indices $(i, j)$ such that $i \< j$ but $a\[i\] \> a\[j\]$.

I think that this can be achieved by swapping the numbers which have been shifted the most from their position. That is:

If $n\_{inv}(a)$ is the number of inversions in a permutation $a$, and $swap\_a(i, j)$ is the permutation obtained by swapping the integers at $i$, $j$, then:

$$ \underset{i, j}{argmin} \\{n\_{inv}(swap\_a(i, j))\\} = \underset{i}{argmax} (a\[i\] -i), \underset{j}{argmin} (a\[j\] - j) $$

In pseudo-code:

```
leftmost = [-1, -1]        # The first value is the displacement
rightmost = [1, -1]        # The second the index where it occurred
for i in 1..n
    d = N[i] - i           # N being the array of numbers
    if d > leftmost[0]
        leftmost[0] = d
        leftmost[1] = i
    else if d < rightmost[0]
        rightmost[0] = d
        rightmost[1] = i
return leftmost[1], rightmost[1]

```

---

The thing is, I have no idea *why* this is correct, or even if it is. How can I prove that this works? Or determine the conditions for which it will work?

---

I have been struggling to understand how I reached this idea and feel that proving it would help me.

To be clear, I am not looking for a solution to the minimizing inversions problem, but only a way to prove that the solution I came up with is correct or incorrect.

# Answer
Let's calculate the difference in number of inversions given that you swap $a\_i$ and $a\_j$. We can assume that $i \< j$. There are three kinds of pairs of indices whose status (being inversions or not) could change as a result of the swap: $(i,j)$ and, for $i \< k \< j$, $(i,k)$ and $(k,j)$. We can distinguish two cases: $a\_i \< a\_j$ and $a\_i \> a\_j$.

If $a\_i \< a\_j$ then the pair $(i,j)$ becomes an inversion, and for every $i \< k \< j$, there are three possible cases:

1. $a\_k \< a\_i \< a\_j$: number of inversions stays the same.
2. $a\_i \< a\_j \< a\_k$: number of inversions stays the same.
3. $a\_i \< a\_k \< a\_j$: number of inversions increases by 2.

This is clearly not a good idea if you can avoid it. If you must (when the permutation is monotone increasing), it's best to switch a pair $a\_i,a\_{i+1}$.

In contrast, if $a\_j \< a\_i$ then the number of inversions decreases by one plus twice the number of indices $i \< k \< j$ such that $a\_j \< a\_k \< a\_i$. As a consequence, if the permutation is not monotone increasing, your goal is to choose a pair $(i,j)$ such that $a\_j \< a\_i$ and the number of indices $i \< k \< j$ satisfying $a\_j \< a\_k \< a\_i$ is maximal. You take it from here.
> 5 votes

---
Tags: algorithms, optimization, correctness-proof, permutations
---


# Question
Title: Why is the probability used in the definition of RP complexity classes, arbitrary?
I was looking at the following wikipedia article on the RP complexity class:

https://en.wikipedia.org/wiki/RP\_(complexity)

In its definition it states:

* If the correct answer is NO then it always returns NO
* If the correct answer is YES then it returns YES with a probability of 1/2

At the end of the introduction it says:

> The fraction 1/2 in the definition is arbitrary. The set RP will contain exactly the same problems, even if the 1/2 is replaced by any constant nonzero probability less than 1; here constant means independent of the input to the algorithm.

What I don't understand is why this 1/2 is arbitrary? If you change it to 1/3 does it really still contain the same set of decision problems as with 1/2?

# Answer
> 8 votes
Yes, the constant is entirely arbitrary. Call an algorithm a $p$-algorithm if:

* When the correct answer is NO, it always answers NO.
* When the correct answer is YES, it answers YES with probability at least $p$.

Note that the probability in the YES case is only over the algorithm's coin tosses.

Given a $p$-algorithm and a constant parameter $m$, we construct a new algorithm which runs the original algorithm $m$ times (with independent coin tosses) and takes the OR of the result. This algorithm is a $1-(1-p)^m$-algorithm (exercise). For every constant $q \< 1$ you can find a constant $m$ such that $1-(1-p)^m \geq q$. Hence if a problem admits a $p$-algorithm it also admits a $q$-algorithm, for every $0 \< p,q \< 1$.

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


# Question
Title: count number of different DFS tree of specific graph - ladder
It is given graph. It isn't ordinary graph, it is ladder. We say that our ladder has order $n$, because of number of nodes. Look at picture:

**My problem is**: *Let's start DFS on node number $1$. How many different DFS tree exist*?

From my point of view I should count number of possible adjency lists. For example, for node number $1$ we have to possible adjency lists: $\[2, 3\]; \[3, 2\]$.

Is my approach ok ? What's your opinion ?

# Answer
> 1 votes
You are close. Also remember the order of non-tree edges does not matter.

There are actually 2 cases for node 1:

1. $$1 \to 2 \to 4 \to \dotsb$$ Start from node 4, it's just a DFS traversal of ladder of order $n-1$ rooted at node 4.
2. $$1 \to 3 \to \dotsb $$ Start from node 3, it's just a DFS traversal of ladder of order $n-1$ rooted at node 3, with one extra branch from 4 to 2. And there are 2 ways to insert branch 2, since node 4 in ladder of order $n-1$ rooted at node 3 is of degree 2, having exactly 1 parent and 1 child.

---
Tags: graphs, counting
---


title: What is a swap-with-memory instruction?

text:
# Question
Title: What is a swap-with-memory instruction?
I am reading an article on algorithms for parallel computing and came across the following sentence. What do they mean by a swap-with-memory instruction?

> Our algorithm provides reasonable latency in the absence of contention, requires only a constant amount of space per lock, and requires no hardware support other than a **swap-with-memory instruction**.

J. M. Mellor-Crummey and M. L. Scott, *Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors*. ACM Transactions on Computer Systems, 9(1):21–65, 1991. (PDF)

# Answer
A swap-with-memory instruction swaps a register's value with that of a memory location. An example of such an instruction would be the Intel 8086 **XCHG** instruction which can swap a register value with memory or swap two register values. Another example would be the indirect modes of the Zilog Z80 **EX** instruction, which swapped register values with memory locations at the top of the stack.
> 3 votes

# Answer
I would assume the `fetch_and_store` instruction is meant. Look at the footnotes on page 2:

> 1) `Fetch-and-store` exchanges a register with memory.

Keep in mind that this paper is over 20 years old, so the terminology can seem unfamiliar. However, often the semantic of the operations/instructions used in such papers are described in detail somewhere in the text.
> 3 votes

---
Tags: parallel-computing, memory-hardware
---


title: Number of DFAs of only one state

text:
# Question
Title: Number of DFAs of only one state
If I have a DFA with only one state that is not an accept state, it accepts only the empty set.

I get confused when if the DFA of one state is an accept state. Does this mean it accepts everything? Or could you have it only accept "a" and not "b". I guess I don't understand if not having an arrow out implies there is a second "invisible state"

In other words, for a DFA of one state, are there 2 or 4 distinct machines?

Thanks!

# Answer
> 5 votes
First let $\Sigma = \\{a,b\\}$.

Assuming that you're taking a strict approach, there has to be a transition from every state for every symbol in the alphabet, then you have only two possible DFAs (that accept $\emptyset$ and $\Sigma^{\ast}$ respectively).

If you allow a partial transition function, where missing transitions imply rejection (note that this can still be interpreted deterministically), then there are five different languages that can be accepted (strictly there's seven automata): $\emptyset$, $\\{\varepsilon\\}$, $a^{\ast}$, $b^{\ast}$ and $\Sigma^{\ast}$.

With a larger alphabet, in the partial function case, you get more of course. With $|\Sigma| = n$ there are $2^{n} + 1$ possible languages, from $2^{n+1}$ different automata (half produce the same language). You get $2^{n}$ from each possible choice of which symbols will have a transition in the case where the state is accepting, and the $+ 1$ from the case where the state is non-accepting (it doesn't matter what transitions you have then, the languages are all $\emptyset$).

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


title: What is a partially sorted array?

text:
# Question
Title: What is a partially sorted array?
I come across this definition but it's not so clear for me !

> An array is partially sorted if the number of inversions is less or equal a constant times the array length. if array length is N then (number of inversions) \<= c\*N, with c constant.

For me c should be \<= 1 is this what they meant ?

For more context : insertion sort running time is linear for partially sorted arrays.

# Answer
The definition you quote is rather meaningless. More accurately, a *sequence* of arrays, one of each length $n$, is partially sorted if for some constant $c$, the number of inversions of the array of length $n$ is at most $cn$. (More succinctly, a sequence of arrays is partially sorted if the number of inversions is $O(n)$.) The running time of insertion sort on such a sequence of arrays is $O(n)$, that is, linear.

It doesn't make much sense to say that a *single* array is partially sorted, since we can always choose $c$ to make the definition hold. If we want to talk about a single array then we need to fix $c$ in advance. Note that $c$ doesn't have to be at most $1$.
> 8 votes

---
Tags: terminology, algorithm-analysis, sorting, arrays
---


# Question
Title: Problems for which algorithms based on partition refinement run faster than in loglinear time
Partition refinement is a technique in which you start with a finite set of objects and progressively split the set. Some problems, like DFA minimization, can be solved using partition refinement quite efficiently. I don't know of any other problems that are usually solved using partition refinement other than the ones listed on the Wikipedia page. Out of all these problems, the Wikipedia page mentions two for which algorithms based on partition refinement run in linear time. There's the lexicographically ordered topological sort \[1\] and an algorithm for lexicographic breadth-first search \[2\].

> Are there any other examples or references to problems that can be solved using partition refinement very efficiently, meaning something better than loglinear in terms of time?

---

\[1\] Sethi, Ravi, "Scheduling graphs on two processors", SIAM Journal on Computing 5 (1): 73–82, 1976.

\[2\] Rose, D. J., Tarjan, R. E., Lueker, G. S., "Algorithmic aspects of vertex elimination on graphs", SIAM Journal on Computing 5 (2): 266–283, 1976.

# Answer
Some linear time modular decomposition algorithms use (some type of) partition refinement, see e.g. these algorithms for directed and undirected graphs.
> 1 votes

---
Tags: algorithms, reference-request, data-structures, partitions, sets
---


# Question
Title: Why not use large $k$ in a $k$-ary tree?
Obviously binary trees are great because of $O(\log\_2 n)$ search, inserts, and deletes in best case.

To "maximize" occurrence of best case, we can use self-balancing trees like red-black trees, AVLs, splay trees, etc.

If we use a $k$-ary tree, we can get $O(\log\_k n)$ searches, inserts, and deletes in best case. Similarly we can "maximize" the occurrences by using self-balancing trees.

I know these are *asymptotically* of the same order, i.e. $O(\log n)$, but the constant could be huge in practice.

The huge reason I can think of is that by using larger $k$'s, you lose the ability to make a decision based on one comparison.

What are other reasons larger $k$ $k$-ary trees aren't used in practice?

# Answer
BTrees are used in practice - file systems, database with $k$ for example equal 1024 or 4096, so it seems to be bigger than binary.

Probably you have not encountered need yet.
For example ternary tree with comparing \>, =, \< gives theoretical improve $O(log\_3 n)$, but self balancing trees in basic form do not accept duplicates, so there is more overhead and not strictly practical.
But bigger ones, yes, they give boost and you use it right now (on the computer).
> 5 votes

---
Tags: trees, search-trees, balanced-search-trees
---


# Question
Title: Looking for Methods in Computer Vision for Distinguishing Disappearing and Fading Objects
Suppose I have a video in which there are two objects $A$ and $B$. Object $A$ appears suddenly at time $Ta1$, and then disappears suddenly at time $Ta2$. Object $B$ appears suddenly at time $Tb1$, and then starts to fade gradually at time $Tb2$, and at $Tb3$ the object $B$ completely fades away. The background intensity is nearly constant, but is changing at a slope $s$ ($s$ can be a very small positive, zero or very small negative) in the long run. For simplicity, we can assume the objects never move. Also, the time $Ta1$, $Ta2$, $Tb1$, $Tb2$ and $Tb3$ are not known beforehand, they can only be inferred from the data or the graphs.

In the graphs below, (a) shows the intensity of a pixel where object $A$ appears against time, (b) shows the intensity of a pixel where object $B$ appears against time, and (c) shows the intensity of a background pixel against time. The graph on the left hand side is the theoretical plot, while the graph on the right hand side is the actual plot from my data. In all graphs, the slope $s$ is a very small positive number.

I tried to use the Running Gaussian Average with Selective Background Update method. It is quite successful in segmenting the background from the objects $A$ and $B$, except that a slight amount of background may be wrongly regarded as foreground at a late time (when the intensity of the background increases by a certain amount). But leaving this issue aside, I would like to do one step further, that is, to distinguish between objects $A$ and $B$. Surely if $Ta1=Tb1$ and $Ta2=Tb2$, the distinction can only be made after $Tb2$ (or even $Tb3$). But what methods can be applied to perform the distinction?

# Answer
> 2 votes
There are probably many possible approaches, but I'll suggest one candidate step-by-step approach that I think might work well, given the information shown in your question:

## 1. Find the times

As a first step, I suggest that you estimate $Ta1,Ta2,Tb1,Tb2,Tb3$.

The good thing is that $Ta1,Ta2$ will be the same for all pixels of object A, and $Tb1,Tb2,Tb3$ will be the same for all pixels of object B. This means you only need to estimate 5 numbers, and you have an entire video to work with -- so you should have more than enough data to infer these 5 times.

One reasonable way to do this would be to do foreground-background segmentation to identify the foreground pixels, using the Running Gaussian Average with Selective Background Update method you already tried; as you said, this is already fairly accurate. It won't need to be perfect -- just getting it approximately right should be enough for what I'm going to suggest.

When you've done that, pixels inferred to be foreground pixels will be a mixture of object A and object B (plus a little bit of error). Now looking at just the inferred foreground pixels, you should be able to deduce $Ta1$, $Ta2$, $Tb1$, $Tb2$, $Tb3$. For instance, at each time, compute the average pixel intensity over all foreground pixels, and graph this as a function of time. You should find that this time series is roughly constant until $Ta1$, then has a large increase at $Ta1$, another large increase at $Tb1$, a big decrease at $Ta2$, and a smooth decrease from $Tb2$ to $Tb3$. Each of those increases/decreases should be easily detectable in the signal.

For instance, you could take the first derivative of this time series (the average intensity of the foreground pixels) and look at its peaks. You should find large positive peaks at $Ta1$ and $Tb1$ and a large negative peak at $Ta2$. Apart from those three times, the first derivative should be close to zero for all time periods, except that it is a significant negative value from $Tb2$ and $Tb3$. I suspect these two characteristics should be enough to identify $Ta1,Ta2,Tb1,Tb2,Tb3$.

If that's not accurate enough, there are alternative approaches; ask if you need them. But I expect it will be relatively easy to implement this step and find the times $Ta1,Ta2,Tb1,Tb2,Tb3$.

## 2. Build a three-class classifier

Now that you know the times $Ta1,Ta2,Tb1,Tb2,Tb3$, I suggest that as your next step you build a classifier that takes the time series for a particular pixel and classifies it as one of three classes: A (object A), B (object B), or Bg (background).

It will probably suffice to build a simple classifier by hand. My guess is you probably won't need terribly sophisticated methods. I'd suggest you identify a few features, and for each pixel, compute a feature vector (the values of those features, for that particular pixel). There are some natural features you could use, for instance:

* $\text{avg}(\[Ta1+\varepsilon,Ta1+2\varepsilon\])-\text{avg}(\[Ta1-2\varepsilon,Ta1-\varepsilon\])$, where $\text{avg}(\[t\_1,t\_2\])$ is the average intensity of the pixel taken over times in the interval $\[t\_1,t\_2\]$. This basically tells you how large a "jump" in the signal there is, at time $Ta1$; for A you expect it to be large, whereas it should be approximately zero for B and Bg.
* $\text{avg}(\[Ta2+\varepsilon,Ta2+2\varepsilon\])-\text{avg}(\[Ta2-2\varepsilon,Ta2-\varepsilon\])$. For $A$ you expect this to be very negative, whereas it should be approximately zero for B and Bg.
* $\text{avg}(\[Tb1+\varepsilon,Tb1+2\varepsilon\])-\text{avg}(\[Tb1-2\varepsilon,Tb1-\varepsilon\])$. For B you expect it to be large, whereas it should be approximately zero for A and Bg.
* $\text{avg}(\[Tb3+\varepsilon,Tb1+3\varepsilon\])-\text{avg}(\[Tb2-2\varepsilon,Tb2-\varepsilon\])$. For B you expect it to be very negative, whereas it should be approximately zero for A and Bg. (unless $Ta1$ or $Ta2$ falls within the interval $\[Tb2,Tb3\]$, in which case you can also figure out what you expect it to be: very positive for A if $Ta1$ is in the interval but $Ta2$ isn't; very negative if $Ta2$ is in the interval but $Ta1$ isn't; or zero if they're both in the interval)
* The fraction of the time points that your Running Gaussian Average with Selective Background Update method classifies the pixel as background. For A and B we expect it to be small; for Bg we expect it to be large.

You might be able to build a classifier simply by setting thresholds for each of these features and using the result to select which object you have.

If that's not accurate enough, you could imagine training a classifier using some machine learning method (e.g., logistic regression, linear SVM, etc.).

Now apply this classifier to each pixel separately, to classify it as belonging to object A, object B, or the background.

## 3. Optional: Clean up the results

You could optionally clean up the results by using spatial locality: we expect object A to be a connected region in the image, and same for object B. For instance, if a pixel belongs to object A, then that makes it incrementally a bit more likely that the neighboring pixels belong to object A. Or, a more sophisticated version of this is: if two adjacent pixels have approximately the same color, then they're a bit more likely to belong to the same class; if they have very different colors, there are no restrictions (they might belong to the same class, or might belong to a different class; each is equally plausible).

There are methods to take this information into account. For instance, suppose your classifier outputs not just its predicted class, but also a probability for each of the three classes (e.g., 90% chance this particular pixel is object A, 8% chance it is object B, 2% chance it is background). Then you can combine this with a graph cut method to take into account spatial locality, i.e., to find a segmentation that both takes into account your classifier's predictions and also takes into account spatial locality.

This kind of post-processing might further enhance the accuracy of your method, by cleaning up the boundaries of the objects.

---
Tags: image-processing, computer-vision
---


# Question
Title: How to get an O(n) for a search algorithm
Given an two sorted arrays X and Y, both of size n. Determine if there is an element x of X and an element y of Y such that **x = 3y**. The algorithm needs to run in linear time in the worst case. At the moment, the algorithm runs in O(n^2). I am unsure how to leverage the fact that the algorithm is sorted to have a scenario where the worst case would have O(n). I am aware of the fact that a binary search has O(log n).

```
public static void main (String [] args)
{
    int[] listX = {1,2,3,4};
    int[] listY = {1,2,3,8};

    for(int x = 0; x<listX.length; x++)
        for(int y = 0; y<listY.length; y++)
        {
            if(listX[X] == (3*listY[y]))
            {
                System.out.println("TRUE");
                break;
            }

        }
}

```

# Answer
> 3 votes
If we imagine that every element of Y is multiplied by 3 in-place in a first step, the problem then becomes equivalent to finding whether there is a common element in the resulting list and X. The required algorithm is similar to the algorithm for merging two sorted lists into a single sorted list, which has a well-known solution in linear time.

The pseudo-code for the solution of O(n) is:

```
for (x=0, y=0; x < listX.length && y < listY.length; ) {
  if (listX[X] == (3*listY[y])) {
    print TRUE;
    break;
  }
  if (listX[X] < (3*listY[y])) {
    x++
  } else {
    y++
  }
}

```

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


# Question
Title: ZK proof that I possess a ZK proof for membership in $L$?
A zero-knowledge proof system for a language $L$ is an interactive proof system where a prover $P$ (a Turing machine) tries to convince a verifier $V$ (a polynomially bounded Turing machine) in a sequence of message exchanges that $x \in L$ so that $V$ learns nothing from the interaction except whether $x \in L$ or not.

**Question.** Is it known how iterate this, i.e.: how to produce a ZK proof that I possess a ZK proof for membership in $L$?

# Answer
> 3 votes
Yes, it's possible. There is a ZK proof for every language in NP. Roughly speaking, this means that if there's a way for someone to prove it (by giving a polynomial-size witness/proof), there's a way to prove it with a zero knowledge proof.

For instance, if you have a transcript of a ZK interaction, there's a polynomial-time algorithm to verify whether the ZK interaction should be accepted by the verifier, so it's possible to prove in ZK (i.e., it's possible to give a ZK proof) that you know a transcript of a ZK interaction that would be accepted by the verifier. However, this might not be quite what you want, because this doesn't prove that the randomness was chosen randomly by the verifier.

Here's a better instance of what you're looking for. Look up non-interactive zero knowledge proofs. Suppose I know a string $p$ that is a valid non-interactive zero knowledge (NIZK) proof of some statement $s$. Moreover, there is a polynomial-time algorithm that allows verifying whether $p$ is a valid NIZK proof of $s$. Therefore, there's a way I can use a ZK proof to prove to Alice in zero-knowledge that I know a string $p$ that is a valid NIZK proof of $s$, without revealing $p$ to Alice (because this is proving a NP statement).

That said, this probably isn't useful. What would be the point? I don't think this lets Alice conclude anything more than if I just proved in ZK to her that $s$ is true.

---
Tags: complexity-theory, reference-request, complexity-classes
---


# Question
Title: MIN-2-XOR-SAT and MAX-2-XOR-SAT: are they NP-hard?
What is the complexity of $\text{MIN-2-XOR-SAT}$ and $\text{MAX-2-XOR-SAT}$? Are they in P? Are they NP-hard?

To formalize this more precisely, let

$$\Phi\left(\mathbf x\right)={\huge\wedge}\_{i}^{n}C\_i,$$

where $\mathbf{x} = (x\_1,\dots,x\_m)$ and each clause $C\_i$ is of the form $(x\_i \oplus x\_j)$ or $(x\_i \oplus \neg x\_j)$.

The $\text{2-XOR-SAT}$ problem is to find an assignment to $\mathbf{x}$ that satisfies $\Phi$. This problem is in $P$, as it corresponds to a system of linear equations mod $2$.

The $\text{MAX-2-XOR-SAT}$ problem is to find an assignment to $\mathbf{x}$ that maximizes the number of clauses that are satisfied. The $\text{MIN-2-XOR-SAT}$ problem is to find an assignment to $\mathbf{x}$ that minimizes the number of clauses that are satisfied. What are the complexities of these problems?

Inspired by Is MIN or MAX-True-2-XOR-SAT NP-hard?

# Answer
Sorry for answering an old post

The problem of determining if a MONOTONE-2-XOR-SAT (all clauses are of the kind $({x\_i}\oplus x\_j)$) instance is satisfiable can be reduced to the problem of determining if a graph is bipartite, see this.

To do that we create a graph $G$ with a node for each literal of the formula and we connect each literal with another if they are in the same clause (edges are clauses)

For instance:

If we have an unsatisfiable formula that is $({x\_1}\oplus x\_2) \wedge ({x\_1}\oplus x\_3) \wedge({x\_2}\oplus x\_3) \wedge ({x\_1}\oplus x\_4) $

We have a graph like this:

that is not bipartite

There are three clauses that are satisfiable and so we have just to eliminate an edge

Now, we can reduce the problem of determining if we can find a maximum bipartite subgraph with $k$ vertex to the problem of determining if we can satisfy $k$ clauses in a MONOTONE-MAX-2XOR-SAT formula, see this. And the maximum bipartite subgraph problem is equivalent to max cut

To do the reduction we simply create a new literal for each vertex and we create a clause for each edge connecting two literals

For instance:

We have this graph,

We create the follwing formula $({x\_1}\oplus x\_2) \wedge ({x\_1}\oplus x\_4) \wedge({x\_2}\oplus x\_4) \wedge ({x\_2}\oplus x\_3) \wedge ({x\_4}\oplus x\_5) \wedge ({x\_3}\oplus x\_5) $

So, if we can find an assignment that satisfies $k$ clauses that will mean that there is a bipartite subgraph with at least $k$ edges.
> 7 votes

# Answer
Where each clause is **only** given as $(x\_i\oplus x\_j)$, create a vertex for each literal $x\_i$, create an edge between two vertices if there exists an XOR relationship between them. For the statement $x\_i\oplus x\_j$ to be true, it should satisfy $x\_i\neq x\_j$. Now we can adopt the vertex coloring problem (no two vertices connected by an edge are assigned the same color, we have additional constraint of 2 colors only if we want to satisfy the equation). The clause $x\_i\oplus x\_j$ is true iff the corresponding vertices have been assigned different colors in the graph.

If all the vertices of the graph can be colored using 2 colors and none of two vertices with a common edge share are assigned the same color then the equation is satisfiable.

But a graph is 2-colorable iff it is a bipartite graph. And determining whether a graph is bipartite can be done in polynomial time. Therefore the problem is in P, because if we can determine in polynomial time that the graph is bipartite graph then it is solvable, otherwise it is not solvable.
> -1 votes

---
Tags: complexity-theory, optimization, np-hard, satisfiability
---


# Question
Title: Proof that circuit design problem is NP-hard
I have the following problem, and I want to show that it is NP-hard (or NP-complete).

Consider a clause which can have OR and XOR relationship between literals, e.g. $c\_1=y\_1 \lor y\_2 \lor (y\_3\oplus y\_4)$. Will the assignment of literals such that the equation given by the conjunction of such clauses, e.g. $c\_1\wedge c\_2 \wedge c\_3 \ldots$ is satisfiable or not a problem in NPC or P?

I suspect that the CIRCUIT SAT can be reduced to it, but I am unable to reach there.

# Answer
> 0 votes
If all clauses have the form $y\_i \lor y\_j \lor (y\_k \oplus y\_l)$, your problem is in P: simply setting all of the $y\_i$ to 1 will satisfy all of the clauses, always. Therefore, it's unlikely to be NP-complete, and you're unlikely to find a reduction from 3SAT (well, unless P=NP).

But if you additionally allow some clauses to take the form $y\_i \oplus y\_j$, then your problem becomes NP-complete. This follows from Schaefer's dichotomy theorem plus a reduction to double the number of inputs (to enable one to express negated literals); or you can find a direct reduction.

---
Tags: np-complete, reductions, 3-sat
---


# Question
Title: Proving simple bound on coupon collector
I came across this paper which gives bounds on coupon colloector problem. Page 451 contains a table where reference to U1 is given as 'folklore'. I presume this is trivial to follow from the definition but I can't see the logic behind this. Does anyone have hints for me? I tried to get this bound by taking the limit of probability that some coupon is not found after n tries but that needs n to be infinity.

# Answer
> 2 votes
Divide the process into $n$ phases. The $m$th phase ($m=1,\ldots,n$) starts when the $(m-1)$st cell has been occupied, and ends when the $m$th cell has been occupied. The first phase takes time $1$. Suppose that the occupied cell is $i\_1$. The second phase then takes expected time $1/(1-p\_{i\_1})$. Suppose that the occupied cell is $i\_2$. The third phase then takes expected time $1/(1-p\_{i\_1}-p\_{i\_2})$. And so on. Overall, the expected time is $$ 1 + \frac{1}{1-p\_{i\_1}} + \frac{1}{1-p\_{i\_1}-p\_{i\_2}} + \cdots + \frac{1}{1-p\_{i\_1}-\cdots-p\_{i\_{n-1}}} = \\ \frac{1}{p\_{i\_1}+\cdots+p\_{i\_n}} + \frac{1}{p\_{i\_2}+\cdots+p\_{i\_n}} + \cdots + \frac{1}{p\_{i\_n}} \leq = \\ \frac{1}{np\_1} + \frac{1}{(n-1)p\_1} + \cdots + \frac{1}{p\_1} = \\ \frac{H\_n}{p\_1} \leq \frac{\ln n + 1}{p\_1}. $$

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


# Question
Title: Why does a graph traversal algorithm is initialised with visited[s]←true
I just had a course on algorithm, we just started to study graph traversal. the teacher wrote analgorithm but I think there is a mistake: I'm a bit shy so I didn't asked her why so...

```
EXPLORE (s:sommet, D:dictionnary of the following vertexes or ahed of vertexes,
var visited:tab)
var: LIST:list; i,j: vertexes;
visited[s]←_true_;
LIST←{s}
While LISTE ≠ 0
    Select i∈LIST
    if ∃ j ∈ D[i], not visited[j]
    visited[j]←true;
    Else LISTE←LISTE-{i}

```

I'm not sure about this line:

```
visited[s]←_true_;

```

What does that mean? shouldn't it be false? At the begining, we haven't visited any vertexes yet?

# Answer
> 1 votes
Suppose you don't mark the start vertex as visited. As you explore the graph, you might come back to the start and begin to explore from there again. Since the first thing you do is visit the start, it's marked as visited at the start of the algorithm.

However, the given algorithm clearly doesn't perform a graph traversal. It adds the start node to the list, then marks all its neighbours as visited, one at a time, then deletes the start node from the list, then terminates. The line

```
visited[j]←true;

```

should be

```
visited[j]←true; LIST←LIST+{j};

```

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


title: Can starvation occur with interrupts?

text:
# Question
Title: Can starvation occur with interrupts?
The Computer Science text book I own describes how an interrupt is handled in an operating system:

* At some point at the end of an instruction the processor checks if there are any outstanding interrupts
* If there are, the priority of the present task is compared with the highest priority interrupt
* If there is a higher priority interrupt, the current job is suspended
* The contents of the special registers are stored so that the job can be restarted later (aren't general purpose registers preserved as well? or do ISRs do not use these?)
* Interrupts are then serviced until all have been dealt with
* Control is returned to the original job
* If the current task has more priority than the interrupt, it is queued and serviced later

The last point "If the current task has more priority than the interrupt, it is queued and serviced later". Does this mean that if an I/O interrupt is generated but the current tasks are all very high priority, they will not get serviced (ignored)? moreover, how does the computer determine when to service these if the current task is more "important"?

# Answer
> 3 votes
I quite disagree with your textbook.

First, Interrupts can be very different between architectures. Most does not support nesting interrupts, while others allow some forms of it (fast interrupts for time critical operations in embedded...)

One can imagine a CPU having 3 modes :

* User
* Supervisor
* Interrupt

When the interrupt request signal\[s\] is active, the CPU automatically saves a few registers, sets the supervisor flag and branches into the interrupt vector. If several interrupts occurs simultaneously, the highest priority interrupt is taken. If one or several interrupts becomes active while the CPU is already in interrupt processing mode, it will wait until the end of the current interrupt service routine to eventually process the next highest level interrupt. This is similar when interrupts are temporarly masked by the OS when it is updating some structures...

Which registers are saved depends a lot of the type of CPU. The minimum is just being able to resume execution later : PC, flags, one register. You can also have a full set of shadow registers reserved for interrupts and which don't need to be saved.

OS tasks are not interrupts. There is usually a timer that regularly tiggers an interrupt which, in turn, wakes the scheduler for switching tasks. It is also done by I/O related interrupts : A network packet is received, an interrupt is triggered, the Ethernet NIC interrupt routine tells the OS to wake the network daemon...

No task has higher priority than interrupts.

Because while being in "interrupt" mode, the CPU cannot be interrupted and cannot process higher priority stuff, OSes try to spend as little time as possible in that state, they instead schedule tasks to asynchronously process events, for one or several symmetric CPUs.

---
Tags: operating-systems
---


# Question
Title: "Archiving" byte sequence into human-readable set of chars
Ok, lets assume we have sequence of 1000 bytes. So the possible number of value variations is 2^100.

Is there a way to "index" each variation with letters and decimal numbers (A-Z, 0-9), having as shortest length as possible?

So the person can dictate sequence of letters and numbers by phone and it can be recreated into bytes on the other side.

Im really bad at math, and found how to shorten that string up to about 100 symbols. Any way to di it shorter?

# Answer
A common encoding used for such tasks is Base64. It is easy to implement and it has been implemented multiple times in many main-stream languages. However, it is not exactly suited for being read by humans.

The basic underlying idea is that a character of Latin alphabet is encoded in ASCII using 6 bits. The encoding alphabet is completed by few punctuation symbols to make it the exact multiple of 8.

Here is a nice even if somewhat light-hearted proposal http://www.crockford.com/wrmg/base32.html for alternative Base32 encoding (it also tries to prevent occasional appearance of expletives in the produced encoding, at least if it is interpreted as English language).

Unfortunately, you won't be able to make it much shorter using only Latin alphabet, unless you have more information about the nature of the data being encoded. Text compression algorithms would try to discover such information about the text being encoded and use variable length encoding, assigning shorter sequences in the output to the more common sequences in the source text. For a simple example of such encoding you can look into Huffman coding

Another, obvious way to shorten the output length is to use a larger alphabet.
> 2 votes

---
Tags: complexity-theory, combinatorics, combinatory-logic
---


# Question
Title: Finite strings and relationships between words
I have a finite alphabet Σ and Σ\* refers to the set of all finite strings over Σ.

1) Given x, y ∈ Σ\* we say that x is a prefix of y if ∃z ∈ Σ\* y = xz. If x is a prefix of y and y is a prefix of x what is the relationship between x and y?

I'm assuming it is a direct relationship because as x goes up so does y, but I'm not sure if that's correct.

2) For this part we assume that Σ = {a, b}. We write #a(x) for the number of occurrences of the letter a in the word x and similarly for #b. We claim that ∀x ∈ Σ\*, ∃y, z ∈ Σ\* such that x = yz ∧ \[#a(y) = #b(z)\].

Is this true? Prove or disprove.

# Answer
For your first question, if $x$ is a prefix of $y$ then there is a $z$ such that $y=xz$. Similarly, if $y$ is a prefix of $x$ then $x=yw$ for some $w$. Then $$ y=xz=ywz $$ and if we remove the characters in $y$ from both sides sequentially, we conclude that $wx=\epsilon$, the empty string, so $w=x=\epsilon$ and hence $y=x$.
> 1 votes

---
Tags: formal-languages
---


title: Hardcore Bit proof for discrete log

text:
# Question
Title: Hardcore Bit proof for discrete log
I am studying Crypto and am trying to understand why discrete log creates is useful for creating a PRG. More specifically, I want to prove via reduction that $B(x)=(x\<p/2)$ is a hardcore bit for the one-way function $f\_{p,g}(x)=g^x \bmod p$. So far, I have shown that if there is a polynomial-time algorithm $D$ that computes this bit perfectly, then there is another polynomial-time algorithm $I$ that inverts the one-way function perfectly. I want to extend the proof to the case when $D$ is imperfect, but successful with probability $\frac12 +\epsilon$ for some nonnegligible $\epsilon$ (in this case, the probability is taken over a random choice of $x$ between 0 and $p-1$). I want to show that for this case, it is possible to invert $f$ with nonnegligible probability in polynomial time.

Any help is appreciated.

# Answer
The usual approach is to identify a randomized self-reduction. In other words, given a problem instance $x$, you generate a randomized version of $x$, say $x'$, and show how the solution to $x'$ gives you the solution to $x$.

How does this help? Given a problem instance $x$, you can generate many randomized versions, say $x'\_1,x'\_2,\dots,x'\_m$ (each one using independent randomness). Now, try to solve each of the $x'\_1,x'\_2,\dots,x'\_m$. By the conditions of your problem, you know that you'll have a way to solve them, so that a $1/2 + \epsilon$ fraction of the answers are correct: i.e., so that $m/2 + \epsilon m$ of the $m$ answers are correct.

Now, you take it from here. How could you use that to form a reasonable guess at the solution to $x$?
> 3 votes

---
Tags: cryptography, pseudo-random-generators, one-way-functions
---