# Question
Title: How does one generate a list of size N of all possibilities using a dictionary of size D?
Say that we have a list of size $N$ to fill with elements of a dictionary of size $D$. So we would have in total $D^N$ elements/possibilities.

It makes sense to me how to write an algorithm for this when the number of possible slots to fill $N$ is fixed. For example if $N = 2$:

```
A %array of size (D x D x D) = D^3
for i1=1:3
    for i2=1:3
        for i3=1:3
            A[i1,i2,i3] = (i1,i2,i3)

```

however, I was having some issue generalize such algorithm because it wasn't clear to me how to extend this chain of for loops for general N. Someone have an idea how to do this?

---

I think the recursive solution is:

```
V %dictionary of size D
N %number of slots
def combos(n)
    if n==1:
        return V
    answers = []
    for combo in combos(n-1):
        for word in V:
                answers.append(combo+word)
    return answers

```

# Answer
There is no need to use recursion. You can use high-school addition instead. Here is pseudocode that generates all answers in lexicographic order.

```
Initialize A[0] = ... = A[n-1] = 0
Repeat
  Output A
  i = n
  Repeat
    i = i - 1
    A[i] = (A[i] + 1) mod D
  Until A[i] ≠ 0 Or i = 0
Until A[i] = 0

```

This algorithm thinks of the contents of `A` as a number in base `D`, which it repeatedly increments. Incrementing `A` proceeds as follows. We first increment the rightmost digit. If it increments to `D`, we change it back to `0`, and then move one digit to the left. We continue this way until some digit increments to a non-zero number, or until we reach the end of the number.
> 2 votes

# Answer
The answer is elementary: recursion!

The underlying observation is that if you can create lists of size $N-1$, you can easily create lists of size $N$ by just appending any one of the $D$ values to every $N-1$ long list.

In pseudo code:

```
def all_possibilities(n, D) {
  if ( n == 0 ) {
    return [[]]
  }
  else {
    smaller = all_possibilities(n-1,D)
    return smaller.map { l =>
        D.map {
          d => l ++ [d]
        }
      }.flatten
  }
}

```

You can prove this correct by induction over $N$.
> 2 votes

---
Tags: algorithms, enumeration
---


# Question
Title: Consequence of $\mathsf{NP\subseteq BPP}$ to $\mathsf{NP\subseteq ZPP}$?
If $\mathsf{NP\subseteq BPP}$, then we know that $\mathsf{NP\subseteq RP}$ (http://www.csie.ntu.edu.tw/~lyuu/complexity/2011/20120103s.pdf). Does $\mathsf{NP\subseteq BPP}$ also imply $\mathsf{NP\subseteq coRP}$ and hence $\mathsf{NP\subseteq BPP}$ also imply $\mathsf{NP\subseteq ZPP}$?

# Answer
If you could prove that implication, then lower bounds such as $NEXP \neq BPP$ would hold unconditionally. (proof: $NEXP = BPP$ implies $NEXP = \Sigma\_2 P$ and $NP \subset BPP$, and if the latter also implies $NP$ is in $coRP$ then UNSAT is in $NP$. So $NEXP = \Sigma\_2 P = NP$ which is false by the nondeterministic time hierarchy). Good luck!
> 5 votes

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


# Question
Title: Term for most degenerate tree with two children on every inner node
I'm looking for the name of a binary tree which is almost degenerate: at least one child of every interior node in the tree is a leaf.

(Image from Penn State course STAT 557, *Data Mining*, lesson 10.)

# Answer
> 3 votes
This *is* a binary tree, when by a binary tree we mean a tree where each vertex has at most 2 children. In other words, you have a tree of maximum degree 3. Also, generally a tree that has a dominating path is a *caterpillar*.

# Answer
> 3 votes
I've seen this type of tree called a *comb*. But this isn't such a widespread term that you can use it without defining it.

Technically, a nested data structure where every node has one child that's a leaf, with the list always on the same side, is a *list*. When the last node has two leaves the one that's not on the usual leaf side is not a special “null” marker, it's an *improper list*. But this terminology works for data structures, it sounds strange when applied to a decision tree.

# Answer
> 0 votes
You mean a rooted tree for which all interior nodes have two children?

These are called *extended* binary trees, and the one you have would be the extended binary tree with maximum height among all such with $n$ nodes.

---
Tags: graphs, terminology, trees
---


# Question
Title: Algortihm for path existence in a N by N board moving with a chess knight
I have a problem which goes like this.

There is an $N$ x $N$ board in which some squares are maked with $x$. The upper left and lower right corner squares are also marked. You have a chess knight with which you want to go from the upper left to the lower right corner, using only marked squares. Find an effective algorithm which determines if such a path exists. The input is a boolean matrix $N$ x $N$, where there is a $1$ if the square is marked.

My first thought is to use recursion to check if such a path exists, but that doesn't sound very effective. Any ideas?

# Answer
> 1 votes
I think that you should run directed floodfill "knight-connected" from both ends using BFS and mark every visited x as 0.

From starting points you check board as knight would move, mark 0 (as it is no longer needed, and if you were there already, there would be shorter path). Add to Queue, and do the same on the other side.

If queue is empty on any side and it has not finished yet it is unreachable.

If array is really boolean, you should check if both queues contain same element, otherwise denote visited elements as 2, and upon reaching such number you have path.

On every move you should increase counter if you need length.

Why directed floodfill? It works similar to this algorithm with different params, and by directed I mean flag where you came from to avoid checking it.

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


# Question
Title: Comparison between IDA* and Recursive best first search
How does IDA\* compare to recursive best first search (RBFS), in terms of (a) the number of nodes expanded, and (b) space complexity?

Both algorithms are intended to be memory-efficient heuristic search algorithms. From my understanding, RBFS just updates the $F(n)$ value for the parent node for which the current execution was stopped in comparison to IDA\*, so it avoids redundant computation to a certain extent, but I'm not sure what exactly this means for the number of nodes expanded or its space complexity.

My main motive of this question was to identify all possible reasons that led to development of RBFS (which can be considered as a successor of IDA\*).

# Answer
> 6 votes
Let me please start by succintly summarizing the behaviour of RBFS. For a thorough explanation of the algorithm refer to the original journal paper: Richard Korf. Linear-space best-first search. Artificial Intelligence, 62 (41--78), 1993. In fact, RBFS is much more than "*just updating the $F(n)$ value for the parent for which the current execution was stopped*". RBFS stores the so-called *stored* $f$-value of each node $n$ as $F(n)$. An invariant of the algorithm is that the stored $f$-value is the minimum *static* $f$-value (ie., the usual $f(n)=g(n)+h(n)$) among all leave nodes generated in a tree rooted at $n$. From here, $F(n)\geq f(n)$ for all nodes $n$ given that costs are monotonic. Initially, when a node is expanded for the first time $F(n)=f(n)$. Later on, when *backtracking* after examining its descendants, its $F$-value (ie., the *stored* $f$-value) is accordingly updated.

So, if nodes beneath node $n$ are examined, up to what point are they developed? Another parameter used in RBFS is an upper bound $B$ which is initially set to $+\infty$. Do not read $B$ as a global upper bound! Indeed, every time a node is selected for expansion, $B$ is updated to the minimum between the current value of $B$ and the second-best $F$-value. So here you are a second invariant of RBFS: every time a node is selected for expansion, it has an $f$-value which is less or equal than the second best $f$-value in the whole search tree. This is true: first, because $B$ is updated using the second-best $F$-value which amounts to compare it with all the descendants of its siblings; second, the other component used is $B$ itself which was, in turn, computed in the same way by its ancestors. Finally, remember that after every expansion, nodes are sorted in increasing order of their $F$-value.

As a result, RBFS expands nodes in the same order of A\*! So far, I do not see it as a successor of IDA\*, but instead, as a new member of the large family of best-first search algorithms. Note that in the preceding statement I solely refer to the new expansions. There will be often in between an arbitrarily large number of re-expansions.

For a more didactical explanation of the algorithm refer to the paper Ariel Felner. The Collapse Macro in Best-First Search Algorithms and and Iterative Variant of RBFS. Symposium on Combinatorial Search (SoCS 2015), 28--34. Israel, 2015. During his dissertation Ariel openly said that this is an algorithm poorly understood in general and there was agreement. Conclusion: read this paper also if you are interested in understanding RBFS (I do sincerely doubt that my review suffices for a good understanding of the algorithm).

Regarding your questions:

1. Note that in the first paragraph I expliclty refered to backtracking ie, RBFS is implemented as a depth-first search algorithm. So far, its memory requirements are $O(bd)$ where $b$ is the branching factor and $d$ is the depth where the solution lies.
2. Assuming that the expansion of every node is the dominant operation and that it takes the same amount of time in spite of the node been expanded, then the number of expansions directly relates to the time complexity. Korf proved that, in the general case, the time complexity is (as one would expect) $O(bˆd)$ where $b$ is the asymptotic branching factor. Also, the best and worst case analysis are analyzed by Korf in the original paper.

As you mentioned the relationship with IDA\* let me also remark that Korf proved that RBFS expands less nodes (in total, considering also re-expansions) than IDA\* in the average-case in case of monotonic costs. If costs do not grow monotonically then these algorithms cannot be compared as they traverse entirely different search trees. Since IDA\* is known to be asymptotically optimal, then RBFS is asymptotically optimal as well.

Hope this helps,

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


# Question
Title: Have block edit distances been computed on large code bases?
There is an enormous mass of source code in this world, and I think it's safe to say that most of this source code was once copied from elsewhere, then modified. There is a decent chance of the (small, incremental) modifications having been made traceable in some kind of version control repository, but the (larger-scale) copying of source code usually isn't traceable in this way.

It would be nice to make it easy to detect it anyway.

As far as I can see, the reason it isn't is ultimately that our paradigm for looking at changes is modelled after `diff`: we compute changes as a collection of per-character insertions and deletions, disregarding the possibility of using block edit operations such as *copy*, *cut*, and *paste*. This doesn't match actual code development practices, in which blockwise copies, cuts and pastes are all too common. Allowing these, we can take two arbitrary code bases and 'reconstruct' an 'ideal' minimal distance between them, measured in terms of change operations that developers are actually likely to use, which includes cut, copy, and paste. This would allow us to reconstruct an 'ideal' change history in code bases in circumstances where the actual change history is missing (e.g. when no version control system has been used, or when code has been copied verbatim from one code base into another).

There seems to be a sound computational reason that this isn't routinely provided already: it seems too expensive. Even with just per-character insertions and deletions, computing the minimal difference between two arbitrary strings already takes quadratic time in the size of the difference found; `diff` doesn't evcen attempt to do this perfectly. If we also allow blockwise copies and/or moves at a constant cost, the problem of determining the minimal edit distance between two arbitrary strings becomes NP-complete. However, it has been argued that realistic constraints can be imposed that make the problem quadratic again. (I am linking to this paper, but I haven't actually read it yet.)

My question to you: have you ever seen an application of block edit distance computations (that is, including substring moves and/or deletions and/or copies) in a piece of software built to compare the similarity of two pieces of software? Does there exist a common, widely available tool that supports this? (A `diff` on steroids.) Or has there been a project to use such a technique to detect copy-and-paste operations within a large base of source code?

(The reason I'm asking is that source code does not at all consist of arbitrary strings. These problems are NP-hard for arbitrary strings, but they may well turn out be in P for source code found in practice.)

# Answer
I do not know about publicly available tools to do it, but I did fair amount of diff related algorithms and one tool to check similarities between codes.

There are some basics to start with:

0) diff operates well on similar changed texts and falls into worst case when they are different.

1) Tools to check similarities on codes that I have seen, used and written were all operating on AST trees, disregarding formatting, variable and function names. Even though when codes exhibited packaging into functions it gave really hard time. So after that technique like SSA and strip code of functions was applied.

2) Languages that allow same thing to be done in several ways are to be treated as same expressions.

3) Sometimes code is translated into another language. So perfectly working transpilers should exist in first place. Every transpiler I have used was not fully functional, maybe I am not aware of new achievements, but as I checked there is no tool "write in any language you want and get source in any other".

4) There are situations like using well known algorithms, or copying from one book. Also there is probability that two codes are the same, or almost the same (same AST, same language), and are not copied.

5) There might be a lot of false positives, and even if we overcome above problems, what would be the outcome of such search?

There is no tool to produce comparable and working solution to JS. And nowadays many projects are getting JS spin off. Also with tools like emscripten (to operate on LLVM code) makes it virtually impossible to keep track of code.

If you take Levenshtein distance as a measure, you should probably consider above points. This seems convincing to me that it is really not sufficient to start tracking such changes in open source code, as there are tons of them.
> 3 votes

---
Tags: reference-request, software-engineering, applied-theory, string-metrics
---


# Question
Title: In fast multiplier circuits, what is the difference between a Counter and a Compressor?
When working on fast parallel multiplier circuit designs, like Wallace tree multipliers or Dada tree multipliers I found many papers and books refer to different components used in the tree to reduce the partial products called things like *(4:2) compressor*, or *(7,3) counter* or *(7:3) compressor*. My question is :

> "What is the difference between a (7:3) compressor and a (7,3) counter?"
>
> What makes us to call it a compressor rather than a counter? is there any rule?

# Answer
> 8 votes
In multiplier design an *(n,k) counter* takes an *n* bit input and produces a *k* bit output which is the binary representation of the number of input bits that are 1s. That is: it *counts* the number of input bits set to 1.

A (3,2) counter is just a full adder.

A (7,3) counter is a circuit with 7 input bits and 3 output bits. The 3 output bits tell you (in binary) how many of the input bits are set to 1.

In an (*n*, *k*) counter it must be the case that $k = \lceil \log\_2 (n+1) \rceil$.

A *(n:k) compressor* is any circuit that takes in *n* equal weight input bits (plus, possibly, some carry in bits) and outputs a *k* bit count, plus some additional carry-out bits. The number of carry-in bits usually equals the number of carry-out bits, but you have to figure out the number by looking at the context. (Hopefully there's a picture or a detailed description in the paper or book you are reading.)

So a (7,3) counter is also a (7:3) compressor. But a (7:3) compressor could also mean something else, like something that takes in 7 input bits, plus a carry-in and outputs 3 output bits, plus a carry-out.

The most commonly used compressor is the (4:2) compressor. This takes in 5 inputs, and output 3 outputs. The reason it is not just a (5,3) counter is because the output is not a binary number in the range $\[0, 5\]$. Rather the output is a 2-bit value in the range $\[0,3\]$ plus an additional carry-out. So there are several ways of representing some of the outputs. For example "2" can be represented as "0+carry-out" or as "2+no-carry-out".

---
Tags: arithmetic, multiplication, digital-circuits
---


title: Sorting an already k-sorted array

text:
# Question
Title: Sorting an already k-sorted array
Can anybody give me some hint on how to do this? I'm not really sure where to start. The problem says:

> We say that an array $A\[1...n\]$ is $k$-sorted if it can be divided into $k$ blocks, each of size $n/k$, such that the elements in each block are larger than the elements in earlier blocks, and smaller than the elements in later blocks. The elements within each block need not to be sorted. For example, the following array is 4-sorted: $$1,2,4,3 | 7, 6, 5 | 10,11, 9, 12 | 15, 13, 16, 14$$
>
> a) Describe an algorithm that $k$-sorts an arbitrary array in time $O(n\log k)$.
>
> b) Prove that any comparison-based $k$-sorting algorithm requires $\Omega(n \log k)$ comparisons in the worst case.
>
> c) Describe an algorithm that completely sorts an already $k$-sorted array in time $O(n \log(n/k))$.

Googling I found this paper with the solution of of a) and b), but I still don't fully understand how to solve this.

For a) my teacher said that we need to find the median and then do something like what quicksort does on finding a good pivot. I was searching over the net and I had the idea to put the $k$ first elements as leafs of a min-heap and then take the min element and with the next element of the array fill each block with $n/k$ elements, but it fails with the input: $8, 7, 6, 5, 4, 3, 2, 1$

Clearly, b) is something like proving that any algorithm based in comparisons takes $O(n\log n)$. Maybe $\log k$ is because we only need to sort each block with $n/k$ elements, that means for each block we need to do $O(n/k \times\log k)$ $k$ times, so we could actually do it in time $O(k\times n/k \times \log k) = O(n\log k)$

For c) I'm not really sure, but I can take all the elements of each block and put them as leafs of a min-heap $-$ which gives $O(\log n/k)$ $-$ and then sort them, which I think would take $O(n \log n/k)$.

Thanks in advance.

# Answer
> 1 votes
You have the right idea but I think you are overthinking it a bit.

For a), your teacher had a good hint. I think there is a simpler solution than the way you are going. As a further hint, notice that if $k=2$, the problem is solved after 1 round of quicksort (with linear median-finding). You have two equal-sized subarrays, where the left is smaller than the right. Can you extend this to $k=4$? Then, can you extend it to arbitary $k$?

b) I think you have the right intuition, but this argument is not formal yet. Recall the original proof of the sorting lower bound, where you argue that you need $n\log n$ comparisons to get $n!$ permutations. Can you extend that to this case? How many permutations are required when we don't need to fully sort?

---
Tags: algorithms, sorting, heaps
---


title: Multi object image segmentation methods

text:
# Question
Title: Multi object image segmentation methods
I want to survey the state-of-the-art in image segmentation. Is there a paper on how to segment multiple objects in an image? The segmentation papers I read, normally identify one of the many objects in the image. This object is typically in the center of the frame, or most-foreground compared to other objects in the image. I'm looking for a way to identify ***all*** different objects in an image simultaneously. Is there any recent work on this?

# Answer
> 3 votes
I think that you are interested in MFC - Multiple Foreground Cosegmentation.
MFC article

Awesome material: Articulated Motion and Deformable Objects : 5th International Conference, AMDO 2008, Port d'Andratx, Mallorca, Spain, July 9-11, 2008, Proceedings

In advance I warn you, these are not all out of the box working solutions, but with small changes all can do segmentation so if first link is what you have expected treat these below as starting point to work your own way.

Every "one object only in the foreground" can start iterative scheme: find first, cut, colour it with backgroundish color (presumably gray darker then mean luminance of the image), cut next.

When some classifiers are used, or patterns are known it is easier, but when background is complex and you want just regions there are oldschool ways: use Otsu, or modified K-Means clustering, try region growing, edge detection, make decision from colour or shadows.
In the end you will find yourself in situation that there are some components, now it is time to decide which is background (darker; connected with all edges of the image; bigger? Every of those could fail).

Image segmentation is based on some kind of connecting self similar regions, cuts them by edges even follows perspective lines if possible.

Foreground - Background separation is the most of the time asuming that foreground is smaller, better exposed. Very rarely there is perspective reconstruction and from one image it is virtually impossible (for street views we can detect lines and follow to horizon, but other types fail).

Below are additional links. If nothing helped write me a comment and describe more details.

Examples are connected in this paper but it works for separate objects: automatic foreground extraction

Foreground prediction

Must read:
Otsu image segmentation
Region-based
Graph based

When you expect some objects: Blobs

Sequence of images:
Kalman filter
Background/Foreground

---
Tags: reference-request, image-processing, computer-vision, pattern-recognition
---


# Question
Title: Are non-trivial sets formed by set operations on NPC sets still in NPC?
I know that from this answer to a question on the class NPC, that NPC is not in general closed under intersection and union. However, the answer used languages which form trivial languages under these set operations and trivial languages are of course not NP-complete. If the intersection or union is non-trivial, does the result still hold? Also, I'm also wondering about the Cartesian product of two NP-complete languages since that is another set operation.

# Answer
> 0 votes
Non-trivial sets formed from the unions and intersections of NP-complete sets are also not necessarily NP-complete (of course this is all under the assumption that P != NP).

Let $L$ be a NP-complete language, $A$ be any set in P, and $B:= {\\{0,1\\}}^\*$. Then the following sets are all NP-complete since they are just the disjoint unions of a sets based on $L$, $A$, and $B$.

$L\_1 := 00L \cup 01A$

$L\_2 := 11L \cup 01A$

$L\_3 := 01L \cup 10B$

$L\_4 := 10L \cup 01B$

Then $L\_1 \cap L\_2 = 01A$ and $L\_3 \cup L\_4 = 01B \cup 10B$ These results are both in P and and non-trivial sets.

On the other hand, as mentioned in a comment above, the Cartesian product of two NP-complete sets is always NP-complete: If $X$ and $Y$ are two NP-complete sets then $X \times Y$ is in NP since a NP-witness for $(x,y) \in X \times Y$ is simply a witness for $x \in X$ along with a witness for $y \in Y$. Furthermore, the map $x \rightarrow (x,y\_0)$ is a polynomial time reduction from $X$ to $X \times Y$ where $y\_0$ is a fixed member of $Y$.

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


title: 2-core 2.6GHz vs 4-core 1.3GHz

text:
# Question
Title: 2-core 2.6GHz vs 4-core 1.3GHz
If a process could run as much cores as available, which CPU is faster, a 2-core 2.6GHz CPU or a 4-core 1.3GHz CPU?

# Answer
> 2 votes
The answer is surprisingly: "it depends".

Taking into account factors below are arguments that it will always win, based on assumption these are perfectly sliced situations (we take processor X, cut it into 2 and the same one into 4 and compare them).

The answer is: 2 core with double speed is \> 4 core.

Otherwise it might be other way due to caches, pipelines, and even ability to utilize core (as system threads are in at least one core). Situation is not symmetric. And algorithmically many tasks cannot be parallelised, so disregarding differences 2 cores are still better (because we will run in serial mode, so faster core is better).

There are several unknowns and we take Amdahl's law into equation: https://en.wikipedia.org/wiki/Amdahl%27s\_law This gives time of parallelization gains / loses.

0) Scheduling operation - how threads are created.

1) What part is really parallel?

2) How much time is being spent on intercommunication?

3) Are computations trivially parallel? If yes, and processors are of same cache and pipeline (proportional per core as in model X), there is difference only between scheduling 2 and 4 threads. So 2 is slightly better than 4. If no, due to communication issue 2 cores runs always faster.

If now processors are different (pipelines, cache and other characteristics) this can be solved only per instance basis taking into account also program to be run.

For instance, if the problem is embarrassingly parallel and each CPU has the same cache, then the fact that the quad core has twice the total cache might be enough to push it's performance higher, especially if the per CPU working set were able to be contained within that cache on the quad core system, but pushed out to main memory on the dual core CPU.

---
Tags: computer-architecture, threads
---


# Question
Title: Is my theorem about $P \neq NP$ correct?
It is known that there are problems in P that, provably, are not solvable in less than $O(N^k)$, for some $k$. Now consider some infinite set $K \subseteq \mathbb{R}^+\_0$ such as K is unbounded from above (you can think of $K$ as being $\mathbb{N}$, for easy reasoning).

**Theorem:** If there exists at least one problem in P for each $k \in K$ that can't be solved in less than $O(N^k)$ steps, then $P \neq NP$.

**Proof:** Assume that $P = NP$, what implies that there is an algorithm that can solve some NP-complete problem in $O(N^q)$ steps, for some $q$. Since the problem is NP-complete, any NP problem can be reduced to it in $O(N^r)$ steps, for some $r$. Thus, every problem in $NP$ (so, also in $P$) can be solved in $O(N^r + N^q)$ steps. Since $K$ is unbounded from above, there are infinitely many $k \in K$ such as $O(N^k) \> O(N^r + N^q)$, and so, for each of these $k$, there is at least one problem in P that can't be solved in $O(N^r + N^q)$ steps. But, since we assumed $P = NP$, every problem can be solved in $O(N^r + N^q)$. Contradiction!

So, to prove that $P \neq NP$, it suffices to find a class of hard P problems, parameterized by a number $k$ -- lets call each of them HARDP-$k$ -- that for each given $k$, it is proven that the best algorithm that solves HARDP-$k$ has time complexity of $O(N^k)$.

If such a class is too hard to define, other less straight strategies can be taken. For instance, without actually defining HARDP-$k$, it suffices to prove that there exists infinitely many problems in P with ever increasing time complexity for the best possible algorithm that solves it.

So, my questions: 1) Is my theorem correct? 2) Is it already known? 3) Is it of any relevance?

# Answer
> 12 votes
I don't think the theorem is correct. At least, your proof is not correct. The problem is in the second sentences of your proof:

> Since the problem is NP-complete, any NP problem can be reduced to it in $O(N^r)$ steps, for some $r$.

This statement is not correct. There's no guarantee there is a single $r$ that works for every NP problem. You might have a different value of $r$ for each NP problem, with no upper bound on the set of all $r$. (To give a silly example: Maybe for 3SAT $r=3$, for 4SAT $r=4$, for 5SAT $r=5$, and so on. Don't take this example too seriously; it's just to give you the idea.)

# Answer
> 6 votes
The time-hierarchy theorem shows that for each $k$ there are problems solvable in time $O(n^{k+1})$ but not in time $O(n^k)$; this problem is (roughly) the halting problem for Turing machines running in time $O(n^k)$. Hence your theorem is *equivalent* to the conjecture $\mathsf{P} \neq \mathsf{NP}$.

---
Tags: complexity-theory, np-complete, p-vs-np
---


# Question
Title: Finding the size of the smallest subset with GCD = 1
This is a problem from the practice session of the Polish Collegiate Programming Contest 2012. Although I could find the solutions for the main contest, I can't seem to find the solution for this problem anywhere.

The problem is: Given a set of $N$ distinct positive integers not greater than $10^9$, find the size $m$ of the smallest subset that has no common divisor other than 1. $N$ is at most 500, and a solution can be assumed to exist.

I managed to show that $m \le 9$. My reasoning is: Suppose there exists a minimal subset $S$ of size $|S|=10$, with gcd = 1. Then all 9-subsets of $S$ must have gcd \> 1. There are exactly 10 such subsets, and their gcds must be pairwise coprime. Let these gcds be $1 \< g\_1 \< g\_2 \< ... \< g\_{10}$, where $\gcd(g\_i,g\_j)=1$, for $i \neq j$. Then the maximum number in $S$ is $g\_2g\_3...g\_{10}$. But $g\_2g\_3...g\_{10} \ge 3\times5\times7\times11\times...\times29=3234846615 \> 10^9$, a contradiction.

However, even with this, a straightforward brute force is still too slow. Does anyone have any other ideas?

# Answer
This problem is equivalent to the following, and it's trivial to construct reduction both ways.

Given a list of bit vectors, find the minimum number of them such that `and` all of them result the $0$ bit vector. $(\*)$

Then we show set cover reduces to $(\*)$. By set cover, I mean given a list of sets $S\_1,\ldots,S\_k$, find the minimum number of sets that covers their union.

We order the elements in the sets to be $a\_1,\ldots,a\_n$. Let $f(S) = (1-\chi\_{a\_1}(S),\ldots,1-\chi\_{a\_n}(S))$, where $\chi\_x(S) = 1$ if $x\in S$, 0 otherwise. Note this function is a bijection so it has a inverse.

Now, if we solve $(\*)$ on $f(S\_1),\ldots,f(S\_k)$, and the solutions is $\\{ f(S\_{b\_1}),\ldots,f(S\_{b\_m})\\}$, then $\\{ f^{-1}(S\_{b\_1}),\ldots,f^{-1}(S\_{b\_m})\\}$ is the solution to set cover.

Thus I would think this problem is testing one's ability to prune the search space.
> 1 votes

# Answer
It's possible to solve this relatively efficiently by computing all pairwise gcd's, removing duplicates, and then recursing. It's the act of removing duplicates before you recurse that makes it efficient.

I'll explain the algorithm in more detail below, but first, it helps to define a binary operator $\otimes$. If $S,T$ are sets of positive integers, define

$$S \otimes T = \\{\gcd(s,t) : s \in S, t \in T\\}.$$

Note that $|S \otimes T| \le |S| \times |T|$ and $|S \otimes T| \le 10^9$ (in your problem); typically, $S \otimes T$ will be even smaller than either of those bounds suggest, which helps make the algorithm efficient. Also note that we can compute $S \otimes T$ with $|S| \times |T|$ gcd operations by simple enumeration.

With that notation, here is the algorithm. Let $S\_1$ be the input set of numbers. Compute $S\_2 = S\_1 \otimes S\_1$, then $S\_3 = S\_1 \otimes S\_2$, then $S\_4 = S\_1 \otimes S\_3$, and so on. Find the smallest $k$ such that $1 \in S\_k$ but $1 \notin S\_{k-1}$. Then you know that the size of the smallest such subset is $k$. If you also want to output a concrete example of such a subset, by keeping back-pointers you can easily reconstruct such a set.

This will be relatively efficient, as none of the intermediate sets grows in size above $10^9$ (in fact, their size will probably be much smaller than that), and the running time requires about $500 \times (|S\_1| + |S\_2| + \cdots)$ gcd operations.

Here is an optimization that might improve efficiency even further. Basically, you can use iterated doubling to find the smallest $k$ such that $1 \in S\_k$. In particular, for each element $x \in S\_i$, we keep track of the smallest subset of $S\_1$ whose gcd is $x$ and whose size is $\le i$. (When you remove duplicates, you resolve ties in favor of the subset that is smaller.) Now, rather than computing the sequence of nine sets $S\_1,S\_2,S\_3,S\_4,\dots,S\_9$, we instead compute the sequence of five sets $S\_1,S\_2,S\_4,S\_8,S\_9$, by computing $S\_2 = S\_1 \otimes S\_1$, then $S\_4 = S\_2 \otimes S\_2$, then $S\_8 = S\_4 \otimes S\_4$, then $S\_9 = S\_1 \times S\_8$. As you go, find the first $k \in \[1,2,4,8,9\]$ such that $1 \in S\_k$. Once you've found $k$ such that $1 \in S\_k$, you can immediately stop: you can find the smallest subset whose gcd is $1$ by looking at the subset associated with $1$. So, you can stop as soon as you reach a set $S\_k$ such that $1 \in S\_k$, which allows you to stop early if you find a smaller subset.

This should be time-efficient and space-efficient. To save space, for each element $x \in S\_k$, you don't need to store the entire set: it's enough to store two backpointers (so the two elements of $S\_i,S\_j$ that you took the gcd of, to get $x$) and optionally the size of the corresponding subset.

In principle, you can replace the sequence $\[1,2,4,8,9\]$ by any other addition chain. I don't know whether some other addition chain will be any better. The optimal choice might depend upon the distribution of correct answers and the expected sizes of the sets $S\_k$, which is not clear to me, but can probably be derived empirically through experimentation.

Credits: My thanks to KWillets for the idea of storing a subset of numbers along with each element of $S\_i$, which allows stopping early.
> 1 votes

# Answer
Perhaps it is faster looking at this in another way... the largest prime less than $\sqrt{10^9}$ is 31607, for a total count of 3401 primes between 2 and 31607, not a very large number. Write each of the numbers you are given fully factored over the primes up to 31607: $$ a\_i = p\_1^{n\_{i 1}} p\_2^{n\_{i 2}} \ldots P\_i $$ Here $P\_i$ is 1 or a large prime. Then a set of the $a\_i$'s is relatively prime if the corresponding $n\_{i j}$ vectors are linearly independent (and their $P$s are different or both 1), and you are looking for the rank of a matrix.
> 0 votes

# Answer
If you are able to find a subset with gcd(S) = 1, then I can always remove redundant elements from the subset till only 2 elements remain , which have gcd(S) = 1. Therefore, I can claim that either the smallest subset will contain 2 elements or it will not exist.

Now, we use recursion to solve this problem. Let's divide the array of numbers into 2 parts, one with n-1 elements and one with 1 element (last element). Either the 2 numbers will be in the first n-1 elements or one element will be there from 1st part paired with last element. Therefore, we are able to solve this problem in

T(n) = T(n-1) + O(n) time. which means T(n) = O(n^2).
> -1 votes

---
Tags: algorithms, number-theory
---


# Question
Title: Why precondition strengtening is sound in Hoare logic
I have problem with understanding why precondition strengthening is sound rule in Hoare logic. The rule is:

$$ {P \implies Q, \\{Q\\} C \\{X\\} } \over {\\{P\\} C \\{X\\}} $$

I really do not understand why precondition in consequence goes in reverse direction that implication works (modus ponens).

I can understand why post-condition weakening works because it follows modus ponens rule but I am no able to understand precondition strengthening.

# Answer
> 3 votes
The triple $\\{Q\\}C\\{X\\}$ states that if $Q$ holds, then after executing $C$, the condition $X$ holds. Now suppose that $\\{Q\\}C\\{X\\}$ and that $P \Longrightarrow Q$. We will prove that $\\{P\\}C\\{X\\}$. Indeed, suppose that $P$ holds. Since $P \Longrightarrow Q$, also $Q$ holds. Hence if we execute $C$, then $X$ will hold. Altogether, we see that $\\{P\\}C\\{X\\}$ is valid.

An example can also be helpful. If we know that $\\{x=1\\}x\gets x+1\\{x=2\\}$ then we certainly know that $\\{x=y=1\\}x\gets x+1\\{x=2\\}$.

---
Tags: logic, program-correctness, imperative-programming, hoare-logic
---


# Question
Title: Using a counting semaphore as a binary semaphore
Are there any methods, so that I can use a *counting semaphore* as a *binary semaphore*?

A binary semaphore should have two possible states: `0` and `1`. The operation `wait()` should atomically look at the state, if the state is \> `0`, the state should be decremented and the process should continue. If the state is `0`, the process should be atomically placed on a queue of waiters and the process should block. The operation `signal()` should atomically look at the state, if the state is `0`, and there are processes blocked, exactly one of them should be woken. If there are no blocked processes the value of the semaphore should be set to `1`.

I specifically need a binary semaphore, not a *mutex*. A mutex assumes *ownership*: that a processes will first lock and then after a resource is used, the process will unlock the mutex. But in my case there are some processes that will only do semaphore `signal()` operation, without ever performing a `wait()` operation.

How can I make sure that the value of the counting semaphore never goes above `1`?

I asked a similar question, on Stack Overflow, specifically about solving this problem with the POSIX synchronization APIs, but the suggestion I got there was to use file locking, which is much slower than semaphores, and also seems to have the mutex semantics I can't use.

# Answer
> 4 votes
A binary semaphore is just a semaphore whose values are limited to 0 and 1 (locked and unlocked; when locked there can be an unlimited queue of tasks waiting). When using such a semaphore you have to be careful never to increment it past 1. The point is that if the values are thus limited, some tricks are possible that speed up the implementation quite a bit, and this is also the most common use (think using the semaphore as a mutex). There is no real conceptual difference involved.

If you want a detailed discussion of the use of semaphores and other synchronization primitives (with some implementation discussion) see Downey's "Little Book of Semaphores". The Linux kernel used to have highly optimized semaphore implementations for contemplation, but they were removed a while back.

---
Tags: operating-systems, concurrency, synchronization
---


# Question
Title: Tools for practicing problem solving and expression of algorithms
I'm involved in a university course which is a crash course in the basics of problem solving and common concepts in computer science. The course contains a number of practical assignments and ends with a group project (~30 hours) in which at least two students solve a problem given to them. Lately we have focused on assigning problems to be solved by use of some computer program and/or device. Examples include visualizing algorithms in a virtual world by use of Alice and Scratch, as well as programming pre constructed Lego Mindstorms robots to perform specific tasks. We think those kinds of environments are suitable because of the low pre-requisites needed and because of the quick feedback that the students are given. As a bonus, the presentations tend to not be boring.

We are currently searching for additional tools to use in the course, which is why I ask you users of Stack Exchange Computer Science this:

What kinds of tools have you come across that could be used to practice problem solving and expression of algorithms? Feedback does not have to be visual -- we are investigating sound/song generation as a possible assignment. What is important is that basically any pair of students should be able to solve our assignments (with guidance if needed) in ~30 hours. That is, the students should not need any pre existing knowledge other than possibly basic mathematics. Whatever tool is required must be available for free.

# Answer
> 0 votes
Problem solving is best done (in my opinion) on pencil and paper. However, some other useful tools for helping solving problems is Wolfram|Alpha. If you need to, Python is a fairly good scripting language for solving problems. Of course, this all depends on what kind of problem you are working on (for example, a geometry problem would be very difficult to solve using Python).

---
Tags: algorithms, education
---


# Question
Title: O(n) time algorithm for maximum earnings
There are $n$ plates $p\_1$ to $p\_n$ each filled with money of value $a\_1$ to $a\_n$. You can take the money from one or more plates if the sum of the money in them is divisible by three. I need a $\mathcal{O} (n)$ asymptotic time logarithm for finding the maximum earnings that can be achieved. I have no idea for such a fast algorithm, so any help is welcomed.

# Answer
You can use DP for solving this problem.

Let's iterate $i$ from $1$ to $n$ and calculate next values for each $i$:

1. $m\_{i,0}$ - biggest sum of money from plates $j \le i$ which is divisible by 3
2. $m\_{i,1}$ - biggest sum of money from plates $j \le i$ which have reminder 1 after division by 3
3. $m\_{i,2}$ - biggest sum of money from plates $j \le i$ which have reminder 2 after division by 3

Base case: $m\_{0,0} = 0, m\_{0,1} = -\infty, m\_{0,2} = -\infty$

Iteration:

1. $k \in \[0, 1, 2\]: m\_{i, k} = m\_{i-1, k}$
2. $k \in \[0, 1, 2\], m\_{i-1,k} \ne -\infty: m\_{i, (m\_{i-1,k} + a\_i)\\%3} = max(m\_{i, (m\_{i-1,k} + a\_i)\\%3}, m\_{i-1,k} + a\_i)$

And result will be $m\_{n,0}$.
> 1 votes

---
Tags: algorithms, optimization
---


# Question
Title: Starvation Condition in CPU/Process Scheduling?
Let's say OS is using preemptive CPU scheduling. A process P1 gets a chance to run for some time and then next higher priority process comes and preempts P1. After that higher priority processes are coming regularly and P1 never gets chance. Is this condition called starvation or not?

# Answer
The first line in the wikipedia states "In computer science, starvation is a problem encountered in concurrent computing where a process is perpetually denied necessary resources to proceeds its work."

https://en.wikipedia.org/wiki/Starvation\_%28computer\_science%29

so the condition you stated is starvation because P1 is perpetually denied necessary resources to proceeds its work.
> 1 votes

---
Tags: operating-systems, process-scheduling
---


# Question
Title: Can only information(data) be stored in ram?
Basic question, but is only information/ data stored in ram? Are computer files such as a word file considered information/ data? This is one of the questions in a summer assignment for ap computer science.

# Answer
RAM is just a really fast hard disk (except the contents are usually lost if powered down). It can store anything you could store on a hard disk (programs, documents, pictures, temporary data,...).
> 2 votes

# Answer
Data and information $-$ as storable entities, not as sequences of events $-$ are related concepts, but the difference between them is clear enough. To make it short, data can be defined as the representation of information, usually stored in somewhat large scale, not yet given a specific purpose or particular interpretation, and encoded in a such a way as to be decodable, and eventually operable.

That said, computer memory (of any kind) will not necessarily contain data (or information). A set of bits is not data if we don't have access to the patterns used to encode information on it. Conversely, computers are not the only kind of information/data processing machine that exists.

Even though you can say that a Microsoft Word file stored on a hard disk is information, it will have to be loaded on RAM before it can be operated with, so you can say (if you want to be extremely acurate) that everything that has been stored outside of main memory is only *potentially* information.
> 2 votes

# Answer
RAM (short for Random Access Memory) is computer memory that can be accessed randomly; i.e. any byte can be accessed without using the previous byte(s). So the answer to your. So yes, only information/data can be stored using RAM.
> -1 votes

# Answer
As mentioned by Tom van der Zanden, RAM is in fact a storage medium much like a typical Hard Drive. Today you have what is called a Solid State drive which is essentially a lot of RAM. RAM as mentioned by AMACB is an Acronym for Random Access Memory. Essentially the information that you are currently accessing is transferred from the Hard Drive onto the RAM chips installed on the motherboard, which is then buffered for usage by the CPU. Computer programs, word documents, etc are in fact Data stored on a computer. There is no way for a user to store content on a RAM Chip like you do on a hard drive (Dragging information off the hard drive onto the RAM Chip is not possible). However when creating a program you can use a command such as MALLOC, (Memory Allocation) to create a predetermined portion of RAM to be reserved specifically for a particular operation. The context of the question in this case is essentially more complicated than a yes or no. "Storing" a typical file directly onto the RAM is possible assuming the system never loses power. RAM is a "Volatile" storage medium, meaning that you lose the contents when the system loses power. Which is why you can edit a word document and lose power without saving that document and when you power the system back on you have lost all changes. The data is stored temporarily on the RAM until the user opts to Save his/her work through the Save As or Save option.

TLDR: Yes, but it wouldn't be wise.
> -1 votes

---
Tags: terminology, computer-architecture, memory-management
---


# Question
Title: Sort deck of cards with least no of moves
We have n cards with each card numbered from 1 to n.

All cards are randomly shuffled but all cards are visible

We are allowed only operation MoveCard(n) which moves the card with value n to the top of the pile.

We need to sort the pile of cards with minimum number of MoveCard operations.

The brute force approach which i can think of is start with MoveCard(n), MoveCard(n-1), MoveCard(n-2).... MoveCard(1).

This approach will solve the problem in n MoveCard operations.

But can we optimize it.

For instance, If the input is like: 3 1 4 2

As per my approach:

```
4 3 1 2
3 4 1 2
2 3 4 1
1 2 3 4

```

MoveCard operations is 4.

But we can solve this problem with minimum number of moves:

Optimized solution is:

```
2 3 1 4
1 2 3 4

```

MoveCard operations is 2.

The aim is to find the first card which has to be moved. In this case its 2

# Answer
> 3 votes
Given a permutation $\pi:\[n\]\to\[n\]$ of cards from $1$ to $n$ you can find the first card to move to the front the following way:

1. $c \leftarrow n$
2. for each $k$ from $n$ down to $1$ do
3. $\space\space\space$ if $c = \pi(k)$ then
4. $\space\space\space\space\space\space$ $c \leftarrow c - 1$
5. $\space\space\space$ end if
6. end for
7. return $c$

In other words, choose the highest card, for which there is another card of higher value in front of it. More formally, choose a maximum $c\in\[n\]$ such that there exists a $c' \> c$ with $\pi(k') = c'$, $\pi(k) = c$ and $k' \< k$. Clearly, this card is not in order yet and since it is the one with the highest value it must be moved first if we want to keep the number of moves minimal. For the permutation $3,1,4,2$ this card is clearly card number $2$.

# Answer
> -2 votes
use Count sort

```
for x in input:
    count[key(x)] += 1

# calculate the starting index for each key:
total = 0
for i in range(k):   # i = 0, 1, ... k-1
    oldCount = count[i]
    count[i] = total
    total += oldCount

# copy to output array, preserving order of inputs with equal keys:
for x in input:
    output[count[key(x)]] = x
    count[key(x)] += 1

return output

```

sorry about that. in that case you can pick the first greatest card which is smaller than the top card and move it to top. with this the above example i.e. 4 3 1 2 can be done in three steps and this one 2 3 1 4 in ONE step..

---
Tags: algorithms, sorting
---


# Question
Title: Improve minimum spanning tree with new edge, with better running time than O(|V|)?
The problem gives a MST $T$ and a series of $Q$ queries, each one with a new edge $e = \\{u,v\\}$ such that no edge between $u$ and $v$ exists in $T$. For every query, we have to improve $T$ with $e$ and print the new weight of $T$.

The best I can do is run a DFS ($O(|V|)$) to find the current path $P$ between $u$ and $v$, and find the heaviest edge $e\_\text{max}$ in $P$. If $w(e) \> w(e\_\text{max})$, we improve $T$ removing $e\_\text{max}$ and inserting $e$. The overall running time for a test case is $O(Q|V|)$.

Does anybody know an asymptotically faster algorithm for this problem?

# Answer
Using **Heavy path decomposition**.

The key idea is to partition all edges into heavy edges and light edges. Consider tree edge from parent node X to child node Y:

* **heavy edge**: size of sub tree Y is at least half of the size of sub tree X;
* **light edge**: size of sub tree Y is smaller than half of the size of sub tree X;

There are at most $O(\log |V|)$ heavy paths (path with only heavy edges) from any leaf to root. Maintaining each heavy path using segment tree or balanced BST, and converting MST into tree of heavy paths, one can query the heaviest edge $e\_{max}$ between any two vertices $u$,$v$ in $O(\log |V|)$.

Another method is using **Link cut tree** which handles each query in $O(\log |V|)$ amortized time complexity. This can also handle the case that each query is applied to the result of previous implement.
> 2 votes

---
Tags: algorithms, graphs, weighted-graphs, minimum-spanning-tree
---


title: Understanding Log(n) Loop Invariant

text:
# Question
Title: Understanding Log(n) Loop Invariant
When attempting to find the following loop invariant for:

```
int log(int x)
{
  int i = 0;
  int j = x;
  while (j > 1) {
    j = j / 2;
    i = i + 1;
  }
  return i;
}

```

I come up with the following loop invariant:

j \>= 0 and i \>= 0 must be true before, during and after each iteration.

For case where x \>= 0, upon checking the condition the first time, the loop invariant holds true.

For case where any input x \>= 0, the invariant loop also holds true.
However, going through some of the other loop invariant reads found here on stackexchange, I am convinced that this is not the loop invariant for this particular algorithm as it does not solve the problem we are trying to accomplish. More specifically, this loop invariant holds true, but without pointing out explicitly that this is a logarithm calculator, the loop invariant is invalid.

I am unsure of the loop invariant I provided as I don't even think it is sufficient for proving out the correctness of the algorithm. How would I create an effective loop invariant that will satisfy the simple algorithm above?

# Answer
> 3 votes
Your understanding is mostly correct. That *is* a valid loop invariant. It's just a relatively weak one. It is common to find a situation like this, where there are multiple possible loop invariants, some more useful than others. You've found a relatively weak (less useful, less informative) loop invariant.

Your real question is: how do I find a loop invariant that is strong enough to let you prove your code is correct? The answer to *that* is that you need to start by *specifying* what it means for your code to be correct. You need to start by writing a specification for your code, that outlines what it means for it to correctly compute the log function.

The specification will typically take the form of a precondition and a postcondition on the function itself. The loop invariant is only a tool to help you prove that the code of `log` meets the specification for `log`.

I can't tell you what the right specification is, as you haven't told us what you want `log` to do. But here is one example specification:

* Precondition: $x=2^k$ for some $k \in \mathbb{N}$
* Postcondition: if $x=2^k$, then the return value of `log` is equal to $k$

When you try to crank through a Hoare-style proof that `log` meets this specification, you'll find that you need a loop invariant. The following loop invariant will be sufficient:

$$i \ge 0 \land j \ge 1 \land j = x \cdot 2^i.$$

I don't expect it to necessarily be obvious that this is a valid loop invariant, nor that this is sufficient to prove the code above meets the spec I gave. Fortunately, there is a systematic step-by-step way to verify that: you use Hoare logic. To learn about this, I recommend that your next step be to spend some quality time with a textbook that explains preconditions, postconditions, loop invariants, and Hoarse logic.

Of course, that's not necessarily the only specification you might have in mind. Another possible specification would be

* Precondition: $x \ge 1$
* Postcondition: if $2^k \le x \< 2^{k+1}$, then the return value of `log` is equal to $k$

or even:

* Precondition: $x \ge 1$
* Postcondition: the return value of `log` is equal to $\lfloor \lg x \rfloor$

Those might require different, more elaborate loop invariants. The point is: whether a loop invariant is strong enough depends upon what you're trying to prove, and in particular, what spec you're trying to prove the code meets.

---

A small correction: When you write

> "without pointing out explicitly that this is a logarithm calculator, the loop invariant is invalid",

that's not quite right: the loop invariant you gave *is* a valid loop invariant. It's just a relatively weak one.

Also, when you write "satisfy the simple algorithm above", that's probably not the right way to put things. I've never heard the word "satisfy" used in this way before. Instead, the right question to ask is: how do I prove that this code meets a particular specification? To ask that, you first need to know what the specification that you're trying to meet is.

# Answer
> 0 votes
Assume input $x \ge 1$, and $x$ is an integer.

**Loop invariant**: $j\*2^i \le x \< (j+1)\*2^i$, or $\[x/2^i\]=j$

**Proof**:

* Initial: $i=0, j=x, x=j\*2^i$
* Inducing: Suppose after $k\_{th}$ loop, we have $j\*2^i \le x \< (j+1)\*2^i$. After the next loop, $j\_1=\[j/2\]$, $i\_1=i+1$, then $j\_1\*2^{i\_1} = \[j/2\]\*2^{i+1} = 2\*\[j/2\]\*2^i$, and $(j\_1+1)\*2^{i\_1} = (\[j/2\]+1)\*2^{i+1} = (2\*\[j/2\]+2)\*2^i$. Applying $0 \le j-2\*\[j/2\] \le 1$, we have $j\_1\*2^{i\_1} \le j\*2^i \le x$ and $(j\_1+1)\*2^{i\_1} \ge (j+1)\*2^i \gt x$
* Final: $j=1$, thus $2^i \le x \< 2^{i+1}$, ie. $\[\log\_2x\]=i$

**Conclusion**:log(x) computes the base 2 logarithm of x, rounding down to integer.

---
Tags: correctness-proof, loop-invariants
---


# Question
Title: Implications of $NP = \Sigma_2 P$ for PH collapse
A simple fact is that $P = NP \to P = coNP$, which follows from the observation that $P$ is closed under complement.

I am having trouble seeing that an analogous statement is true at higher levels of $PH$. For example, is it known that $NP = \Sigma\_2 P$ implies $NP = \Pi\_2 P$? If so, is there an easy proof? Would such a statement have any other interesting implications (For example $NP = coNP$)?

It seems somewhat likely to me that this is true, based on the observation that $NP = \Sigma\_2 P$ means that $\exists \forall$ quantifier patterns can be replaced with $\exists$ quantifier patterns, and so all higher levels of $PH$ would *at least* collapse to $\Pi\_2 P$.

# Answer
> 4 votes
The answer is yes. notice that $NP=\Sigma\_1$ and for all $i$ you have $\Sigma\_i=\Sigma\_{i+1} \Rightarrow \Sigma\_i=\Pi\_i$. This is true since $\Pi\_i\subseteq \Sigma\_{i+1}=\Sigma\_i$. The inclusion holds since if $\bar{L}\in\Sigma\_i$ then you have $x\notin L \iff \exists v\_1\in \left\\{0,1\right\\}^{p(|v\_1|)}...Q\_iv\_i\in\left\\{0,1\right\\}^{p(|v\_i|)}M(x,v\_1,...,v\_i)=1 $ or equivalently $x\in L \iff \forall v\_1\in \left\\{0,1\right\\}^{p(|v\_1|)}...\bar{Q\_i}v\_i\in\left\\{0,1\right\\}^{p(|v\_i|)}M(x,v\_1,...,v\_i)=0$. So now your $\Sigma\_{i+1}$ verifier for $L$ will ignore $v\_1$, run $M(v\_2,...,v\_{i+1})$ and flip the answer. It remains to show $\Sigma\_i\subseteq\Pi\_i$. Let $L\in\Sigma\_i, \bar{L}\in \Sigma\_{i+1}$ and since $\Sigma\_i=\Sigma\_{i+1}$ you get $\bar{L}\in\Sigma\_i$.

Back to your question. If $NP=\Sigma\_2$ (or $\Sigma\_1=\Sigma\_2)$ then $\Sigma\_1=\Pi\_1$. Let $L\in\Pi\_2$ then $\bar{L}\in\Sigma\_2\Rightarrow \bar{L}\in\Sigma\_1\Rightarrow \bar{L}\in\Pi\_1\Rightarrow L\in\Sigma\_1$, So $L\in NP$ as required. The opposite direction is clear(for all $i$ $\Sigma\_i\subseteq\Pi\_{i+1}$).

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


# Question
Title: While using K-means, how do I represent IP addresses and languages on the coordinate axis?
I'm using K-means for unsupervised learning, using data vectors with an IP address and a language. I need to represent them in an abstract way, so that I can use this algorithm.

# Answer
If your data doesn't map in an obvious way onto vectors of continuous real numbers, don't use K-means.

To use K-means clustering you need to have a well defined *distance* between any two points in the space. To do that you need to have a notion of distance for each axis.

Typically discrete classifications like "language" don't have any natural mapping onto real numbers.
> 1 votes

---
Tags: machine-learning
---


# Question
Title: Pumping lemma regular language can't be pumped
Suppose we have a regular language that describes every string with the exact length of 3.That is obviously a regular language and it still can't be pumped because there is no cyclic behavior in that string/ the corresponding dfa

Can you please help me figure out my mistake?

# Answer
Have a look at the exact wording of the pumping lemma: It has a precondition that only words exceeding a certain size need to be pumpable. This is exactly so that *only* words with repetitions have to be pumpable.

For your language (and every other finite one) you can simply set that size beyond the maximum word size (e.g. at 4). No words are longer than that, and all of them can be pumped.
> 5 votes

---
Tags: regular-expressions, pumping-lemma
---


# Question
Title: Selective Background Updating in Running Gaussian Average Method for Background Subtraction
I am studying the Running Gaussian Average Method for background subtraction. One alternative, as described in Wikipedia, also known as Selective Background Updating, is to only update the distribution of background pixels.

I have two questions on this topic:

(1) To determine whether a pixel is foreground or background, we need to calculate ${\mu}\_t$ as follows: $${\mu}\_t = M{\mu}\_{t-1} + (1-M)(I\_t{\rho}+(1-{\rho}){\mu}\_{t-1})$$

But the $M$ in this formula depends on whether the pixel is foreground (in this case, $M=1$) or background (in this case, $M=0$). So it becomes a circular dependence. Currently I tried to solve this by calculating: $$(I\_t{\rho}+(1-{\rho}){\mu}\_{t-1})$$

Then after deciding the pixel is foreground or background, I determine $M$ and use the first formula to update the value of ${\mu}\_t$. Is this correct?

(2) The Wikipedia page only suggests to update the mean of each background pixel using the first formula above. Shall we update the variance as well, like as follows? $${\sigma\_t}^2 = M{\sigma^2\_{t-1}} + (1-M)(d^2{\rho}+(1-{\rho}){\sigma^2\_{t-1}})$$

# Answer
> 1 votes
1) You start with first frame of video. Gather several frames to calculate accumulators, denote everything like background - at first frame you do not know which is which. Yes, recalculate.

2) Yes we shall update variance.

Never used unmodifief version: remember to use illumination infependent color space. Think about taking running variance on your own.

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


title: Executing an NFA

text:
# Question
Title: Executing an NFA
I am trying to verify that the NFA below does not accept `babba`. However, when I tried to do it by hand I must have made a mistake: $$\\{q\_1\\}, \\{q\_2,q\_3\\}, \\{q\_1, q\_2, q\_3\\}, \\{q\_2, q\_3\\}, \\{q\_3\\}, \\{q\_1\\} \rightarrow \text{Accept}$$ Where is my error?

# Answer
> 4 votes
The error is that you don't distinguish when you read a letter from the input and when not. For instance, the first (closure of) state(s) is not $\\{q\_1\\}$ but rather $\\{q\_1,q\_3\\}$ due to the epsilon move. Then, the first letter is $b$, thus $$\\{q\_1,q\_3\\} \to^{b} \\{q\_2\\}$$ continue like this and you'll get the correct answer.

---
Tags: automata, finite-automata, nondeterminism
---


# Question
Title: How to "properly" handle incorrect values in a random walk?
I'm performing a simple one dimensional walk to create sample interest rates. Whilst I know there are lots of options for encouraging values to oscillate around a mean etc. I'm yet to find a simple "proper" way to handle truly random processes going out of bounds. Whilst you could simply turn it in the other direction, is there some sort of commonly accepted way of making asymptotically less and less likely to get closer to the boundary the closer you get to it?

# Answer
> 1 votes
A random walk $(X\_i)$ can't become negative if there are no positive-probability transitions to negative values. One condition that causes it to stay finite with probability $1$ is that, for all large enough $n$, $\mathbb{E}(X\_{i+1}|X\_i=n)\<n$.

---
Tags: algorithms, randomized-algorithms
---


title: Minimum edge deletion partitioning

text:
# Question
Title: Minimum edge deletion partitioning
I'm interested in the time complexity of the following problem:

Given an undirected graph $G=(V,E)$ and a weight function $w: E \rightarrow \mathbb{Z}$ (so weights can be negative, too), color the vertices in such a way that the sum of the weights of the monochromatic edges (i.e. those between same color vertices) is minimized.

The closest NP-hard problem I could find is the "minimum edge deletion k-partition" (https://www.nada.kth.se/~viggo/wwwcompendium/node43.html), however, in that problem $k$ is known and fixed beforehand, whereas in my problem, the optimal $k$ (i.e. the number of different colors) is not known.

Any hints, pointers, comments are welcome.

# Answer
I believe this problem is NP-hard and it can be shown by a reduction from the vertex coloring problem with $k$ colors.

Assume we are given a graph $G' = (E',V')$ and we want to decide whether there exists a coloring of the vertices in $V'$ using only $k$ colors. To do so, we construct a new graph $G$ that consists of $G'$ as well as the complete graph $K\_k$. Furthermore, we add edges of weight $-1$ from every vertex in $G'$ to every vertex in $K\_k$. The edges inside of $G'$ as well as $K\_k$ on the other hand have a very large weight.

Now, I claim that $G'$ admits a $k$-coloring, if and only if we can color $G$ and achieve a profit of $|V'|$. To see this, we first observe, that due to the large weight on the edges inside of $G'$ and $K\_k$, both sub-components must be colored in such a way that no adjacent vertices inside of them share the same color. For $K\_k$, this trivially implies a $k$-coloring. Next, note that all vertices with matching colors between $G'$ and $K\_k$ add a profit of one to the total profit. However, there can be at most one such edge between $G'$ and $K\_k$ for every vertex in $G'$. This is exactly the case if $G'$ has a $k$-coloring (using the same colors that were used in $K\_k$). Thus $G'$ admits a $k$-coloring if and only if we can find a coloring of $G$ with a profit of $|V'|$. This in turn implies NP-hardness of your problem.
> 4 votes

# Answer
Interesting problem. Here are some results for some special cases.

If all weights are negative then colour every vertex in the same colour. This will be optimal.

if G is planar and all weights are positive then you can colour its vertices with 4 colours such that no two connected vertices are the same colour (no monochromatic edges). This is due to the 4-color theorem. With no monochromatic edges you will get a sum of 0 and this will be optimal. If G is non-planar and all weights are positive then the chromatic number of G gives you the minimum number of colours needed to obtain zero monochromatic edges:

http://mathworld.wolfram.com/VertexColoring.html

http://mathworld.wolfram.com/ChromaticNumber.html

For the general problem I can't find any quick solution. The closest is what you have mentioned already: minimum edge deletion k-partition = minimum k-partition. Suppose you had a solution to this problem for a given k, call it f(k). Find f(1), then f(2), then f(3) and so on, each time recording the best result. You can terminate as soon as you have found a k such that f(k)=f(k-1).
> 1 votes

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


# Question
Title: Global Optimization of a well-defined function with gradient information
I try to minimize the function $$ f(x\_1, …x\_n)=\sum\limits\_{i}^n-a\_i\cos(4(x\_i-b\_i)) +\sum\limits\_{ij}^\text{edge}- \cos(4(x\_i-x\_j)), \quad x\_i,b\_i\in (-\pi, \pi)$$ where $\sum\limits\_{ij}^{edge}$ only sums over predefined edges (the edges are sparse, typical there are 4 edges for each $i$). The variables $a\_i, b\_i$ are constants, $ a\_i \in (0,1)$; many $a\_i$s are 0. The gradient at each iteration can be directly computed. I observe that Gradient Descent converges very fast, but produces very bad results (very easily falls into local optimal). I have no idea whether Conjugate Gradient Algorithm or BFGS algorithm will make a significant difference.$$$$ While general optimization such as simulated annealing and GA do not use the gradient information (they seem powerful but blind to local derivative), thus I am looking for techniques making good use of gradient information.

# Answer
> 1 votes
One alternative is to use Newton's method. Newton's method uses information from the first and second derivative (i.e., the Hessian matrix), so it can converge in fewer steps than gradient descent (which uses only information from the first derivative) -- but the cost is that each single step is slower, because it requires more complex computations.

If Newton's method is too slow, there are faster variants, such as BFGS and other quasi-Newton methods or the conjugate gradient method.

Another approach is to continue using gradient descent, but make some adjustments. One simple thing you can try is to apply it many times, each time with a different random starting point. Also there are various tuning knobs you can tweak, such as adjusting the step size or using momentum. A third possibility could be to try to make a "smarter" choice of starting point for gradient descent: you can approximate each cosine by a quadratic function (using the Taylor series expansion at a particular point), obtain a function $f^\*$ that is a quadratic approximation to $f$, and then find the exact minimum for $f^\*$ using least-squares method. This basically amounts to applying one step of Newton's method and then continuing with gradient descent from there.

Trying several different methods shouldn't be too hard if you use the right software, as there are many software packages that let you specify the function and then make it easy to try multiple different optimization methods.

# Answer
> 0 votes
Thank D.W! I would like to try various Newton methods in near future. But I found my function here has a special structure that can be formulated as a quadric form. Today I tried quadratic programming with Java and it works! First, the energy function is defined as (a little bit from the original one): $$ f(x\_1, …x\_n)=\sum\limits\_{i}^n(x\_i-m\_i)^2 +\sum\limits\_{ij}^{edge}(x\_i-y\_i)^2$$ Let $x=\\{ x\_1, …x\_n \\}$ we get a quadratic form: $$ f(x\_1, …x\_n)= \frac{1}{2}x^TAx-b^Tx $$ Which can be solved by Ax=b, by one shot instead of iterative process! I programmed it in Java and it gives the results in the following image(the red points are $m\_i$). Here $n=2156$, so matrix $A$ is $2156\times2156$. It takes several seconds to compute its inverse to solve the system.

while, the 'sharp' peak at each $m\_i$ is not desirable, I guess modifying the energy function would change the curvature at the peaks.

---
Tags: optimization
---


# Question
Title: Dual-pivot Quicksort reference implementation?
Has some sort of canonical - or reference - implementation of Dual-pivot Quicksort been posted anywhere?

I would like to include that algorithm in a comparison among sorting algorithms for a specialized need that I have, but the Java versions I've seen appear to have various kinds of tweaks applied to them, like using Insertion Sort for small (sub-) arrays, which makes it harder to compare the fundamentals.

# Answer
I tried to do exactly such a comparison in my master thesis, which thus naturally includes pseudo-code of “basic” versions of several dual-pivot Quicksorts (there is a list of them on page 9).

Here is my basic implementation of Yaroslavskiy's algorithm (the dual-pivot scheme that is used in Java 7):

```
void sort(int[] A, int left, int right) {
    if (right > left) {
        // Choose outermost elements as pivots
        if (A[left] > A[right]) swap(A, left, right);
        int p = A[left], q = A[right];

        // Partition A according to invariant below
        int l = left + 1, g = right - 1, k = l;
        while (k <= g) {
            if (A[k] < p) {
                swap(A, k, l);
                ++l;
            } else if (A[k] >= q) {
                while (A[g] > q && k < g) --g;
                swap(A, k, g);
                --g;
                if (A[k] < p) {
                    swap(A, k, l);
                    ++l;
                }
            }
            ++k;
        }
        --l; ++g;

        // Swap pivots to final place
        swap(A, left, l); swap(A, right, g);

        // Recursively sort partitions
        sort(A, left, l - 1);
        sort(A, l + 1, g - 1);
        sort(A, g + 1, right);
    }
}

void swap(int[] A, int i, int j) {
    final int tmp = A[i]; A[i] = A[j]; A[j] = tmp;
}

```

The partitioning loop maintains the following invariant: (Initially, the “?”-area is the whole array, at the end it is gone; the indices are moved in the direction indicated by the arrays, so $\ell$ and $k$ start at the left, $g$ at the right end of $A$.)

I did a mathematical average case analysis for these algorithms to determine the expected number of key comparisons, element swaps and also instruction counts for some specific low-level implementations (in Java Bytecode and MMIX, an RISC assembly language).

The main result is that Yaroslavskiy's algorithm uses $1.9n \ln n + O(n)$ comparison, which is 5% less than the $2n \ln n + O(n)$ comparisons of classic single-pivot Quicksort (both average case on random permutations). However, it needs $0.6 n\ln n + O(n)$ swaps for that, where classic Quicksort only needs $\frac13 n \ln n + O(n)$ swaps; similarly, my instruction counts also indicate that classic Quicksort is more efficient. What exactly makes Java 7's dual-pivot algorithm faster remains an open question. (In case you are interested in more details on that, I could elaborate further.)

Tweaks of the algorithm like switching to Insertionsort for subproblems smaller than some (constant) threshold or optimizing code outside the partitioning loop (`while(k <= g) { ... }`) will only change the numbers hidden by $O(n)$. This means that for large lists, they are not important. For practical input sizes, they still help a lot, so having them in library code is a must.
> 11 votes

# Answer
Check out the implementation by Joshua Bloch which is part of the jdk. It has very good documentation as well with some diagrams. If you don't want the optimization for short arrays just skip past it.

http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/tip/src/share/classes/java/util/DualPivotQuicksort.java
> 2 votes

---
Tags: algorithms, reference-request, sorting, quicksort
---


# Question
Title: Understanding the fundamentals of building an in-Memory Distributed Graph
I am working on a project where I have to build an in-memory distributed graph capturing the relation between similar files(based on some similarity metric) stored in shared file system over multiple nodes in a network.

I know basic graph data structure. I googled to know about distributed graph, but what I found mostly is just an info about existing distributed graph databases like titan, FlockDB etc. But I really couldn't find any fundamental guide to building a distributed graph or in general explaining a basic algorithm of building a distributed graph.

Can you please suggest few references where I can get such material explaining the fundamentals.

# Answer
You should look at the *Cloud Computing* area - there is a lot of research about graphs representation and processing there.

For example, this paper.
> 1 votes

---
Tags: graphs, data-structures, reference-request, distributed-systems
---


# Question
Title: Isn't Domain of a variable nothing but a constraint?
In Constraint programming we have Variables and their Domains and then all the constraints, but if you at the concept of a domain of a variable it is nothing but another type of constraint, you are saying that this variable can take all these values. Is there any particular reason why domain is defined as a different concept than constraints?

# Answer
As you observe, restricting the domain of a variable has exactly the same effect as applying a unary constraint to it.

One situation where you might prefer to use unary constraints rather than restricted domains is when you want to control very tightly the relations that are allowed to be used in constraints. For example, if you want to investigate the computational complexity of CSP with a particular class of constraint languages. On the other hand, such investigations often assume that all unary relations are included in the constraint language, which is equivalent to fixing a global domain but allowing the domain of any variable to be any subset of that. (This is known as the "conservative" case because of certain algebraic properties of the constraint langauges.)
> 2 votes

# Answer
Even though a domain may be considered just another type of constraint, there do exist good reasons to keep them separated, and it may be easier to think of them from a pure mathematical standpoint. Domains should in a sense be seen as the definition of the variable in terms of Type - e.g. Integer or Real etcetera. The domains can also be seen as the Master bounds. Defining the domain type (Integer / Real) is also important to help the constraint solver determine what solving method to use for each specific constraint.

I would like to illustrate it with the following example;

Consider the following constraint problem for Pythagoras theorem.

Variables: a b c

Domains: a \[1..10\] Integer b \[1..10\] Integer c \[1..10\] Integer

Constraint: a x a + b x b = c x c

We actually have three unknowns but the finite sets of the domains will allow the constraint solver to find the following solutions for a,b,c;

a = 3,4,6,8 b = 3,4,6,8 c = 5,10

Now let us change the domains from Integer to Real, to the following;

a \[1..10\] Real b \[1..10\] Real c \[1..10\] Real

Simply by changing the domains, it will no longer be possible to find all solutions as there do exist an infinite number of solutions.

Therefore, the domains should in general be seen as the main definition of the total search space (in terms of type and bounds) while the constraints should be seen as the definition of the problem.
> 1 votes

# Answer
I suppose what is called domain for constraint programming corresponds to what would be called type in most contexts, and particularly in most programming languages.

The issue of types is an old one, and I am unfortunately not knowledgeable enough to give you a precise account. But this may hopefully serve as an introduction.

The idea of theorizing types is attributed to Bertrand Russell, to serve as an alternative to set theory and do away with some paradoxes of naive set theory.

What it says, intuitively, is that terms are always supposed to be typed and that operators or predicate make sense only when applied to the proper types. The idea is quite close to static type checking in programming languages. But I suggest you read at least the beginning of the wilipedia page on Type Theory, which seems rather clear.

Thus, as a first approximation, it seems quite possible to do as suggested in the question: consider the domains as simple constraints, on a universal sets of values. That is just returning to naive set theory and its paradoxes, which was however sufficient to do a lot of good mathematics for some time.

But it seems that a cleaner way to do things is to separate values into domains were operations and predicates have meaning. Otherwise, is the value *true* odd or even, and what is its square root? This is the way to ensure that the language you use (whether constraints or other) will have properly defined semantics, relying hopefully on a consistent logic.

But can we have both consistency and domains as constraints, and is there a cost?

The benefits of typing may come at the cost of Turing Completeness. For example, while (untyped) $\lambda$-calculus is Turing complete, simply typed $\lambda$-calculus is more restricted. Whether typing can be consistent with Turing Completeness is an issue I would not address at my competence level.

An important point of all this however is that typing systems have been shown to be isomorphic to logical predicates, through what is known as the Curry-Howard isomorphism. So this would vindicate from a theoretical perspective the view that domains can be seen as a constraint expressed by some predicate to be satisfied. From this point of view, there is no difference between a formula (to be satisfied) and a type, given appropriate formalization apparatus with a consistent logic.

However, it may be (I do not know) that distinguishing domains from other predicates may be a way of enforcing consistency of the underlying logical system (to be checked).

Now, if you wish for more details, it would be best to asked a full-fledged type theorist, as I am getting onto grounds for which I have no chart.

From a more mundane point of view, you may consider that expressing constraints makes sense only with respect to some domain, and there is in practice a hierarchical structures that enforces the existence of some sense (semantics) to what can be written, and also allows for more efficient implementations. That is pretty much, I believe, why static types were introduced in programming languages, as they had to refer to the encoding techniques used for the corresponding values (though I would not underestimate the influence of logicians on early programming language design, especially Lisp and Algol, that were both extremely influencial).

Of course, if the kind of domains you are willing to consider in your constraint programming language is very restricted, you are probably safe from paradoxes, and could, if you wish, freely see domains as unary constraints as already suggested by David Richerby's answer.
> 0 votes

---
Tags: type-theory, typing, constraint-programming, curry-howard, constraint-satisfaction
---


# Question
Title: Complexity of "given a graph $G$ with vertex $v$, is there a maximum clique containing $v$"?
The usual way of translating the maximum clique problem into a decision problem is to ask "does there exist a clique of size $\ge k$ in $G$?" Clearly this problem is in NP (and is NP-hard).

Another possible way of making it into a decision problem would be:

**Instance**: Graph $G=(V,E)$ and vertex $v\in V$.
**Question**: Does there exist a clique $C\subseteq V$ in $G$ that contains $v$ and is of maximum cardinality among cliques?

If P = NP, this problem is polynomial-time solvable. The problem is also contained in $\Sigma\_2^p$ (does there *exist* a clique such that *all* other cliques are not bigger?). Has its precise complexity been studied?

(Very similar questions can of course also be asked about vertex cover, dominating set, independent set and the like).

# Answer
> 5 votes
I do not recall having seen this precise problem before, but it does have a Cook reduction (polynomial-time Turing reduction) to $k$-Clique:

> Let $Y$ be an oracle for $k$-Clique. On input $(G,v)$:
>
> 1. Determine the maximum clique size $\omega(G)$ via at most $log\_{2}(n)$ calls to $Y$ using binary search.
> 2. Create $G'$ by removing all vertices $u \neq v$ where $uv \notin E(G)$ (i.e. $V(G') = N\[v\]$).
> 3. Determine $\omega(G')$ using $Y$ and binary search.
> 4. If $\omega(G') = \omega(G)$ answer YES, otherwise answer NO.

This puts it in $\Delta\_{2}^{P} = P^{NP} = P^{SAT}$, a refinement of your observation.

As there are $O(\log{}n)$ calls to the oracle, we can squash containment a little further; the problem is in $\Delta\_{2}^{P}\[O(\log{}n)\] = P^{NP}\[O(\log{}n)\] = P^{SAT}\[O(\log{}n)\]$.

**\[Thanks here to Ricky Demer\]** If $P=NP$, then $P^{NP} = P^{P} = P$, so you are correct about the polynomial time solvability in this case (contrary to my original, now edited, musings).

So perhaps the problem is $P^{NP}\[O(\log{}n)\]$-complete, it shouldn't be (as Dominik observed in his answer) $P^{NP}$-complete. I have tried to use the results of Theorem 3.5 from Krentel's paper to construct a reduction, but unless $P^{NP}$ is low for itself (which I don't think it is, but don't know), this has been without luck. (If it is low for itself, then I have a marvellous proof, sadly there are no margins here to put it in.)

# Answer
> 4 votes
For what it's worth, here is a reduction showing NP-hardness. As regards $\Delta\_2^p$-completeness, I'm not too optimistic, since one complete problem for this class is "given a formula, does its lexicographically maximal satisfying assignment set the last variable to true?" which seems harder than this problem.

We reduce from 3SAT. Let a formula $\phi'$ with $m-1$ clauses be given; add a fresh variable $x$ and add the one-literal clause $x$; this forces $x$ to be true. Thus we obtain a formula $\phi$ with $m$ clauses which is satisfiable if and only if $\phi'$ is.

Next we construct the graph $G$, which up to an extra component is identical to the graph used in Karp's original reduction showing that CLIQUE is NP-hard. Take a vertex $\ell$ for each literal occurrence in $\phi$. Include an edge between literal occurrences $\ell\_1$ and $\ell\_2$ if and only if (a) the occurrences are in different clauses, and (b) $\ell\_1$ and $\ell\_2$ are not contradictory (i.e. are negations of each other). Further, add a disjoint copy of the complete graph $K\_m$ of $m$ vertices. This completes the description of $G$. As special vertex $v$ use the single literal occurrence of $x$.

Suppose the formula is satisfiable. Note first that there cannot be a clique among the literals of size larger than $m$ since every clique can contain at most 1 vertex per clause. Of course, among $K\_m$, there is also no clique larger than $m$. Now take a satisfying assignment of $\phi$, and pick one true literal per clause. Since these literals cannot be contradictory, this forms a clique of size $m$, and includes the vertex $v$; it is of maximum cardinality $m$.

Suppose there is a maximum-cardinality clique in $G$ containing $v$. Then from the presence of $K\_m$ in $G$, this clique must have size at least $m$. From what we said before, it can't have size larger than $m$, so it is of size exactly $m$. The clique thus chooses one literal per clause, and we can set them all true in a contradiction-free assignment. Hence $\phi$ is satisfiable.

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


# Question
Title: Is it allowed to do a binary search with an oracle when proving NP-completeness?
In https://cs.stackexchange.com/a/45524/28999, they do a binary search using an oracle for an NP-Complete problem. They show that the original problem can be reduced to that NP-Complete problem, implying that the original problem is in NP.

Why is that allowed? Why are you allowed to continue after the oracle returns false? Doesn't this defeat the whole idea of NPC versus co-NPC? You could then simply use an oracle for a NP-complete problem to show that NPC = co-NPC?

I would think that the whole reduction is wrong and that the original problem is probably not in NP. Or aren't they implying that?

# Answer
The answer in its current form shows only that it belongs to $\Delta\_2^P$, or $P^{NP}$. This is a (not necessarily strict) subset of $\Sigma\_2^P$, or $NP^{NP}$, which is what the asker had mentioned.

The answerer said that they don't know whether it's $\Delta\_2$-complete, but doubt it; and it similarly seems unlikely that this in $NP$. (The next answer shows that it is $NP$-hard, so that if it is in $NP$, it is certainly $NP$-complete.)

You are correct that, if one wanted to show a problem to be in $NP$, one must not use multiple queries to an $NP$ oracle. As an example of how this might look, I could ask the problem: "Given these two instances of 3SAT, $(Problem\_1,Problem\_2)$, is exactly one satisfiable?" This is not going to be easily shown to be in $NP$, but it's easily shown in $P^{NP}$: I query the first problem, and then the second, and then I xor their answers together. This could be written as the problem existing in $DTIME(1)^{NP}$.

The exponent notation refers to oracles that they can query in constant time, only.
> 5 votes

# Answer
Well, nowhere does the answer claim the reduction "implies that the original problem is in NP". So, that explains your confusion. You read something into the answer that isn't actually there.

Also, the answer says "Cook reduction". This was a heads-up about the fact that it's not the Karp-style reduction you might be used to. You might like to learn about the difference between a Cook reduction vs a Karp reduction. Read https://en.wikipedia.org/wiki/Turing\_reduction. As you suspected, a Karp reduction is part of what is used in the definition of NP-completeness, but this answer isn't trying to prove NP-completeness, so the Cook reduction is "allowed".
> 5 votes

---
Tags: np-complete, reductions, oracle-machines
---


title: Prove that $coRP \subseteq RP^{RP}$

text:
# Question
Title: Prove that $coRP \subseteq RP^{RP}$
I've read in an article that $coRP = RP$ is an open question, but that it is obvious that $coRP \subseteq RP^{RP}$.

If $L \in coRP$, I don't understand how access to the oracle helps to build a probabilistic machine that proves $L \in RP^{RP}$.

Any explanation would be appreciated.

# Answer
Suppose $L \in \mathsf{coRP}$, so that $\overline{L} \in \mathsf{RP}$. Using an oracle to $\mathsf{RP}$ we can determine whether a given string $x$ is in $\overline{L}$, and so whether $x \in L$. This gives a $\mathsf{P}^{\mathsf{RP}}$ algorithm for $L$.
> 1 votes

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


# Question
Title: Why are inversions useful in computer science?
In the second chapter of Cormen's textbook on *Algorithms*, he lists a discrete mathematics exercise on so-called "**inversions**", defined as follows:

> Let $A\[1 \ldots n\]$ be an array of $n$ distinct numbers. If $i \< j$ and $A\[i\] \> A\[j\]$, then the pair $(i, j)$ is called an **inversion** of $A$.

**Question:** Is this a mathematical concept that is used frequently in computer science? Are there some widely known applications of inversions that other people here know of? (I checked the wikipedia page for the concept, but it didn't list any).

# Answer
> 4 votes
To analyse many algorithms, in particular for the all-important sorting problem, the characteristics of permutations are important measures. For instance, the number of inversions determines the number of data movements when running insertion sort.

---
Tags: discrete-mathematics
---


title: What is the size of an algorithm?

text:
# Question
Title: What is the size of an algorithm?
**Question:** Does the "size" of an algorithm typically refer to the number of its inputs, or its running time?

This seems an ambiguous term to me that I keep seeing in textbooks.

# Answer
In complexity theory, "size" refers to the length of (some string representing) the input to the algorithm. One is then interested in some cost measure of the work done (most commonly some upper bound) when processing input of a given size as a function of said size.
> 1 votes

---
Tags: algorithm-analysis
---


title: What is the use of Horner's Method?

text:
# Question
Title: What is the use of Horner's Method?
Here is Wikipedia's explanation of Horner's Method:

> Given the polynomial
>
> $$ p(x) = \sum\_{i=0}^n a\_i x^i = a\_0 + a\_1 x + a\_2 x^2 + a\_3 x^3 + \cdots + a\_n x^n, $$
>
> where $a\_0, \ldots, a\_n$ are real numbers, we wish to evaluate the polynomial at a specific value of $x$, say $x\_0$.
>
> To accomplish this, we define a new sequence of constants as follows:
>
> $$ \begin{align} b\_n & := a\_n \\ b\_{n-1} & := a\_{n-1} + b\_n x\_0 \\ & {}\ \ \vdots \\ b\_0 & := a\_0 + b\_1 x\_0. \end{align} $$
>
> Then $b\_0$ is the value of $p(x\_0)$.
>
> To see why this works, note that the polynomial can be written in the form
>
> $$ p(x) = a\_0 + x(a\_1 + x(a\_2 + \cdots + x(a\_{n-1} + a\_n x)\cdots)). $$
>
> Thus, by iteratively substituting the b\_i into the expression,
>
> $$ \begin{align} p(x\_0) & = a\_0 + x\_0(a\_1 + x\_0(a\_2 + \cdots + x\_0(a\_{n-1} + b\_n x\_0)\cdots)) \\ & = a\_0 + x\_0(a\_1 + x\_0(a\_2 + \cdots + x\_0(b\_{n-1})\cdots)) \\ & {} \ \ \vdots \\ & = a\_0 + x\_0(b\_1) \\ & = b\_0. \end{align} $$

**Question:**

Is the point of this algorithm that we can now evaluate $p(x\_0)$ without having to ever evaluate any of the values $x\_0^2, \ldots, x\_0^n$, and instead, we are able to just just iteratively compute $b\_n$ through $b\_0$, where by the time we eventually get to $b\_0$ we are finally able to evaluate $p(x\_0)$?

If this is the case, why is this useful? Why not just compute $p(x\_0)$ the normal way?

---

**EDIT:** Is it true that using Horner's rule to compute a polynomial of degree $n$ takes running time from $\Theta(n^2)$ down to $\Theta(n)$?

# Answer
> 5 votes
Yes, exactly as you said. This is used to decrease the number of multiplications, so it is more efficient than computing it the normal way.

Example:

> You have the polynomial $ax^3 + bx^2 + cx + d$. Computing directly you have six multiplications: (a * x * x * x, b * x * x, c * x). With Horner $((ax + b)x + c)x + d$ you have three multiplications: (a * x, first parenthesis * x, second parenthesis * x)

It is important to remember that in floating point calculations results from these two methods (direct and Horner) will differ.

---
Tags: polynomials
---


title: Half-SAT intractability proof

text:
# Question
Title: Half-SAT intractability proof
I've been struggling lately with a problem that was in my last complex algorithms exam, and I can't find a solution. The problem is as follows:

> Half-SAT is a problem where C is a CNF boolean formula with n variables and m clauses, where m is even. We have to determine if there exists an interpretation that satisfies exactly half of the clauses. Prove Half-SAT intractability with a reduction from SAT.
>
> Clues: A formula can have duplicated clauses It's possible to write clauses that are always true.

I'd be very grateful if you could give me any clue on how to approach this problem.

# Answer
> 4 votes
The clue that you got is a bit strange, since true clauses are not enough. Here is one possible solution. Given a CNF formula with $m$ clauses, let $a$ be a new variable, add the clause $a \lor \lnot a$, and add $m+1$ copies of the clause $a$. I claim that if this formula is half-satisfiable then the original formula is satisfiable.

An assignment in which $a$ is true satisfies at least $m+2$ out of the $2m+2$ clauses, which is more than half the clauses. Therefore any assignment half-satisfying the new formula must assign false to $a$, leading to the conclusion that the $m$ original clauses must all be satisfied.

---
Tags: reductions, satisfiability, np
---


# Question
Title: Example of reduction in communication complexity
Let us assume the standard situation in communication complexity with two players $P\_1,P\_2.$

We have a function $f:\[n\] \times \[n\] \mapsto \\{0,1\\}$ that both players known in advance. They wish to compute $f(x,y)$ given that the first player only knows $y$ and the second player only knows $x.$ The communication complexity of $f$ is the smallest number $k$ such that $P\_1,P\_2$ can always compute $f(x,y)$ communicating at most $k$ bits of information to each other.

If $f$ is the equality function (that is $f(x,y) = 1$ if and only if $x = y$) then I know that $P\_1,P\_2$ need to exchange at least $\log\_2{n}$ bits in order to be able to always compute $f.$

Consider now the function $h\_n:\[n\]\times\[n\] \mapsto \\{0,1\\}$ such that $h\_n(x,y) = 1$ if and only if $x+y = n.$ I would like to show that $P\_1,P\_2$ cannot compute $h$ using fewer than $\Omega(\log{n})$ bits and the idea is to use the fact about the communication complexity of computing $f.$

Hence I am wondering how to make a reduction in this case?

Suppose we can compute $h\_n(x,y)$ with fewer than $\Omega( \log{n})$ bits. Can we somehow simulate such a protocol in order to be able compute $f$ using less than $\Omega(\log{n})$ communication bits?

Player $P\_1$ receives the string $y$ and $P\_2$ the string $x.$ Now $x = y$ if and only if $x+y = 2x = 2y.$ Hence they could simulate the algorithm for computing $h\_{2x}(x,y).$ The problem that I see here is that in this reduction $h\_n$ is not fixed in advance and may not even define the same function for $P\_1,P\_2$ (if $x,y$ actually differ).

Hence I am wondering

> How can one show that $h\_n(x,y)$ cannot be computed communicating fewer than $\log\_2{n}$ bits ?

# Answer
Assume that each player gets a number in $\[n\]$, and they can compute $h\_n(x,y)$. Each player knows $n$, so if $h\_n$ is computable with less than $log(n)$ communication, they can compute $h\_n(n-x,y)$ in under $log(n)$ bits of communication. Since you have $h\_n(n-x,y)=1 \iff x=y$ then you managed to compute $\delta\_{x,y}$ in sub logarithmic communication, contradiction.
> 3 votes

---
Tags: complexity-theory, communication-protocols, communication-complexity
---


# Question
Title: Classification problem where one attribute is a vector
Hello I am a layman trying to analyze game data from League of Legends, specifically looking at predicting the win rate for a given champion given an item build.

### Outline

A player can own up to 6 items at the end of a game. They could have purchased these items in different orders or adjusted their inventory position during the course of the game.

In this fashion the dataset may contain the following rows with:

```
   champion id   |                 items ids               | win(1)/loss(0)
----------------------------------------------------------------------------
       45        |   [3089, 3135, 3151, 3157, 3165, 3285]  |       1
       45        |   [3151, 3285, 3135, 3089, 3157, 3165]  |       1
       45        |   [3165, 3285, 3089, 3135, 3157, 3151]  |       0

```

While the items are in a different order the build is the same, my initial thought would be to simply multiply the item ids as this would give me an integer value representing that combination of 6 items.

While there are hundreds of items, in reality a champion draws off a small subset (~20) of those to form the core (3 items) of their build. A game may also finish before players have had time to purchase 6 items:

```
                items ids
------------------------------------------
   [3089, XXXX, 3151, 3285, 3165, 0000]
   [XXXX, 3285, XXXX, 3165, 3151, 0000]
   [3165, 3285, 3089, XXXX, 0000, 0000]

XXXX item from outside core subset
0000 empty inventory slot

```

As item 3089 compliments champion 45 core builds that have item 3089 have a higher win rate than core builds which are missing item 3089.

The size of the data set available for each champion varies between 10000 and 100000. The mean is probably around 35000.

### Questions

1. Is this a suitable problem for supervised classification?
2. How should I approach finding groups of core items and their win rates?

# Answer
Yes. If you have a non-trivial data set of this form, this would be a reasonable fit for statistical analysis.

For independent variables, you have one binary feature for each core item (indicating whether that item was purchased or not); the outcome is a binary variable (win or loss). Accordingly, one reasonable approach would be to try logistic regression. You'll have one independent variable $X\_i$ for each item; $X\_i=1$ means that item $i$ is one of the 6 items that the champion purchased in this game, $X\_i=0$ means item $i$ was not purchased. You'll have a dependent variable $Y$; $Y=1$ means that the champion won this game, $Y=0$ means the champion lost. Then logistic regression will tell you which items tend to be associated with winning games.

There are other methods you could try as well: pretty much any method for supervised classification that works well with binary/categorical variables.

The one thing I *don't* recommend you do is multiply the item codes. That's not going to help. Instead, just have 20 features, where each feature indicates whether a particular item was purchased or wasn't.
> 1 votes

---
Tags: machine-learning, classification
---