title: Selecting Columns with Minimum Overlaps

text:
# Question
Title: Selecting Columns with Minimum Overlaps
Given a matrix $A=\[a\_{ij}\]$ of positive number $0\leq a\_{ij}\leq1$ that has $m$ rows and $n$ columns. I would like to select, for each row $i$, a set of columns $S\_i$ such that $$\sum\_{j\in S\_i} a\_{ij}\geq1,$$ and the number of overlaps $\Delta$ is minimum. The number of overlaps $\Delta$ is calculated as follows: $$\Delta=\sum\_{1\leq p\<q\leq m}\Delta(S\_p,S\_q),$$ where, for any pair of columns $(S\_p,S\_q)$, we have $S\_p\cap S\_q\ne\emptyset\iff\Delta(S\_p,S\_q)=1$.

I would like to find an algorithm that minimizes the number of overlaps.

I tried to sort $a\_{ij}$ for each $i$ such that $a\_{i1}\geq a\_{i2}\geq \cdots\geq a\_{in}$, then make $S\_i=\\{1\\}$ and verify the sum to be larger than $1$, if not make $S\_i=\\{1,2\\}$, and so on. But, I found a counter-example for this to be non-optimal.

# Answer
> 1 votes
I don't know if there is a polynomial-time algorithm, but if your matrix is not too large, you could try approaching this with integer linear programming. Define zero-or-one variables $x\_{ij}$, with the intended meaning that $x\_{ij}=1$ means $j \in S\_i$. Then you have the constraints

$$\sum\_{j} a\_{ij} x\_{ij} \ge 1.$$

Also, introduce zero-or-one variables $o\_{pq}$, with the intended meaning that $o\_{pq}=\Delta(S\_p,S\_q)$, and enforce that

$$o\_{pq} = (x\_{p1} \land x\_{q1}) \lor \dots \lor (x\_{pn} \land x\_{qn})$$

using the techniques in Express boolean logic operations in zero-one integer linear programming (ILP). (In other words, you introduce fresh temporary zero-or-one variables $o'\_{pqj}$ and add the constraints $o'\_{pqj} \ge x\_{pj} + x\_{qj}-1$, $o'\_{pqj} \le x\_{pj}$, $o'\_{pqj} \le x\_{qj}$, $o\_{pq} \le o'\_{pq1} + \dots + o'\_{pqn}$, $o\_{pq} \ge o'\_{pqj}$.)

Finally, minimize $\sum\_{p\<q} o\_{pq}$, subject to the constraints above. This is a set of linear inequalities over integer variables, so you can feed it to an off-the-shelf ILP solver and hope it finds you a good solution. This algorithm will have exponential running time in the worst case, but ILP solvers incorporate many heuristics, so if the matrix is not too large, it's possible this might give you good results in a reasonable amount of time.

---
Tags: algorithms
---


# Question
Title: Why did Google not use an NP problem for their quantum supremacy experiment?
Reading discussions of the recent quantum supremacy experiment by Google I noticed that a lot of time and effort (in the experiment itself, but also in the excellent blog posts by Scott Aaronson and others explaining the results) is spent on verifying that the quantum computer did indeed compute the thing we believe it to have computed.

From a naive point of view this is completely understandable: the essence of any quantum supremacy experiment is that you have the quantum computer perform a task that is hard for a classical computer to achieve, so surely it would also be hard for the classical computer to verify that the quantum computer did complete the task we gave it, right?

Well, no. About the first thing you learn when starting to read blogs or talk to people about computational complexity is that, counter-intuitive as it may seem, there exist problems that are hard to solve, but for which it is easy to verify the validity of a given solution: the so called NP problems.

Thus it seems that Google could have saved themselves and others a lot of time by using one of these problems for their quantum supremacy experiment rather than the one they did. So my question is **why didn't they?**

An answer for the special case of the NP problem `factoring` is given in this very nice answer to a different question: https://cs.stackexchange.com/a/116360/26301. Paraphrasing: the regime where the quantum algorithm starts to out perform the best known classical algorithm starts at a point that requires more than the 53 qubits currently available.

So my follow-up question is: does this answer for the special case extend to all NP-problems where quantum speedups are expected or is it specific to factoring? And in the first case: is there a fundamental reason related to the nature of NP that quantum-supremacy 'kicks in later' for NP problems than for sampling problems or is it just that for NP problems better classical algorithms are available due to their being more famous?

# Answer
> there exist problems that are hard to solve, but for which it is easy to verify the validity of a given solution: the so called NP problems.

This statement is wrong. There are many NP problems which are easy to solve. "NP" simply means "easy to verify". It does *not* mean hard to solve.

What you are probably thinking of is NP-complete problems which is a subset of the NP problems for which we have *very, very good* evidence to think they are hard. However, quantum computers are not expected to be able to solve NP-complete problems significantly more "easily" than regular computers.

Factoring is also thought to be hard, but the evidence for this is only "very good" and not "very, very good" (in other words: factoring is likely not NP-complete). Factoring is one of very few natural problems which falls in between not being NP-complete and not being easy.

The list of problems that we know that are easy to verify, easy to solve on a quantum computer but hard classicly, is even shorter. In fact, I do not know of any problem other than factoring (and the very closely related discrete logarithm problem) with this property.

Moreover, any easy to verify problem would likely have the same issue as factoring: $53$ qubits is not that many, and $2^{53}$ is huge, but just within reach of classical computing. $2^{53}$ less than $10^{16}$, and most classical computers can execute on the order of $10^9$ operations per second. We could run through all possibilities in about $1/3$rd of a year on a single classical desktop computer.

Quantum computers have very few applications which they're known to be good at, and are essentially useless for most hard NP problems.
> 74 votes

# Answer
Because then their experiment would have been a complete failure.

As I wrote in an answer on a sister site (which was somewhat poorly received there, but I think your question validates what I was saying about how a general audience interprets it):

> \[the hyping of the result\] plays on a discrepancy between what they mean by quantum supremacy (QS) and what people tend to think QS means.
>
> What I find most people think QS is supposed to mean, and what I assumed it meant until a month or so ago, was that there exists a computable problem (in the CTT sense of computation) and an actual quantum computer, such that, at some scales, the problem is tractable on the quantum computer but intractable on all classical computers.
>
> The problem the Google QC folks have demonstrated is not computation in the CTT sense. It is a physical process of sampling that involves computations as part of the process, and as with any physical process, it can be simulated approximately by computation. They have good reason to believe (proof? I'm not sure but it should reasonably be assumed true by default anyway) that computation to similate the process is going to be intractably slow. This is not surprising at all. It's a fundamental consequence of quantum mechanics that lots of physical processes will have that property.
> 9 votes

# Answer
Quantum computing is not a piece of magic, and there seems to be a widespread misconception about the power of quantum computers. I am by no means an expert in this field, but as far as I know QC is very suitable for computational problems that employ some kind of cyclic structure. This happens to be true for problems like the integer factoring problem and the discrete logarithm problem, thus, if quantum computers become practical, asymmetric ciphers like RSA and any kind of DSA (including ECDSA) will become obsolete. However, it is not known (or widely believed) that QC breaks symmetric ciphers (the key size has to be increased, though) or, more generally, inverts generic one-way functions. QC is also not known to break lattice-based asymmetric crypto, therefore, NTRU, McEliece etc. do apparently survive QC.

Therefore, even if you have a fully functional QC, you cannot arbitrarily pick any computational problem and conjure the solution instantly.
> 7 votes

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


# Question
Title: Find the sum of numbers from an array closest to a number, where repetition of the numbers are allowed
I would like to find the sum of values from a given number array, where the repetition of numbers are allowed, closest to a target but the sum cannot exceed the target. If there are more solution, I'd prefer the one with the minimum element count.

***Examples:***

**1)**

Given values: \[500, 1000, 2000, 5000\]

Target: 7000

Result: \[2000,5000\]

**2)**

Given values: \[500, 1000, 2000, 5000\]

Target: 7990

Result: \[500, 2000, 5000\]

**3)**

Given values: \[222,333\]

Target: 444

Result: \[222,222\]

**4)**

Given values: \[222,333\]

Target: 777

Result: \[222,222,333\]

Later on I would like to implement this algorithm in JavaScript, and make it run in a browser. I have tried:

-Knapsack algorithm

-Generating all combination of the numbers and find one with the minimum difference

but both are very slow when implemented, and used with big numbers.

# Answer
> 3 votes
This problem is NP-hard by a reduction from partition. Let $X = \\{x\_1, \dots, x\_n\\}$, be an instance of partition and let $2M = \sum\_{x \in X} x$ (assume that $M$ is an integer as otherwise the instance is trivial). Assume that each $x\_i$ is positive and let $\ell = \lceil \log 2M \rceil$.

I will now construct some values based on $X$. I will denote a generic value by a tuple $v$ of $n+2$ entries $(v^{\*}, v^{(0)}, v^{(1)}, \dots, v^{(n)})$, where all entries $v^{(i)}$, $i=0,\dots,n$ are between $0$ and $2^\ell - 1$. The tuple $v$ will actually correspond to integer whose binary representation is obtained by encoding $v^{\*}$ in binary (using a variable number of bits), each of $v^{(0)}, \dots, v^{(n)}$ using $\ell$-bits, and finally concatenating the resulting bitstrings, in order. An example of the tuple $v=(5, 2, 7, 9)$ with $\ell = 4$ is as follows: $$ (\underbrace{101}\_{v^\*} \underbrace{0010}\_{v^{(0)}} \underbrace{0111}\_{v^{(1)}} \underbrace{1001}\_{v^{(2)}})\_2 = (21113)\_{10} $$

Notice that the value obtained in this way has an encoding of polynomial length w.r.t. the length of the encoding of the original partition instance, as long as $v^{(\*)}$ is small enough (as will be the case). The sum of two tuples is the tuple whose integer value equals the sum of the integer values of the summands.

Let then $y\_i = (1, x\_i, 0, \dots, 0, 1, 0, \dots, 0)$, where the second entry set to $1$ is $y\_i^{(i)}$. Similarly, let $z\_i = (1, 0, 0, \dots, 0,1,0, \dots, 0)$, where $z\_i^{(i)} = 1$.

The instance of the problem in the question consists of the set of numbers $S = \\{y\_i : x\_i \in X\\} \cup \\{z\_i : x\_i \in X\\}$ and of the target value $T=(n,M,1, \dots, 1)$.

Given a solution $X' \subseteq X$ to the partition problem, it is easy to construct a solution $S' \subseteq S$ for our problem such that $\sum\_{x \in S'} x = T$. Simply select $S' = \\{ y\_i : x\_i \in X'\\} \cup \\{ z\_i : x\_i \in X \setminus X' \\}$ (notice that it suffices for $S'$ to be a set rather than a multi-set).

I will now argue that if a (multi-)set $S' \subseteq S$ such that $\sum\_{x \in S'} x = T$ exists, then the partition instance $X$ has answer "yes". From now on let $S'$ be such a set and notice that, by our choice of $T$, the overall multiplicity of all the elements of $S'$ cannot be larger than $n$ (as otherwise $T^{(\*)}$ would be exceeded).

**Claim:** Let $m(x)$ be multiplicity in $S'$ of $x \in S$. $\forall i=1,\dots,n$ we have $m(y\_i) + m(z\_i) = 1$.

**Proof:** If $m(y\_i) + m(z\_i) = 0$ then, since $T^{(i)}=1$, $S'$ must contain at least $2^\ell \ge 2M \> n$ elements $y\_j$ or $z\_j$ such that $j \> i$, contradicting $\sum\_{x \in S'} m(x) \le n$.

Assume then that $m(y\_i) + m(z\_i) \> 1$, and consider the tuple $h$ corresponding to the sum of exactly 2 copies of $y\_i$ and/or $z\_i$ in $S'$. We have $h^{(i)}=2$ and, since $T^{(i)}=1$, we conclude that there must be at least $2^\ell - 2$ other copies of some $y\_j$ or $z\_j$ for $j \ge i$ in $S'$. The total multiplicity of the elements in $S'$ is therefore at least $2 + 2^\ell - 2 \> n$, a contradiction. $\\;\\; \square$

Let $X' = \\{x\_i : y\_i \in S' \\}$ and call $h = \sum\_{x \in S'} x$. Since there can be at most one copy of each $z\_i$ in $S'$ (see the above Claim), the only way to affect $h^{(0)}$ is through the values $y\_i \in S'$. Since there can be at most one copy of each $y\_i$ in $S'$ (see the above Claim), we must have $\sum\_{x\_i \in X'} x\_i = \sum\_{y\_i \in S'} y\_i^{(0)} = h^{(0)} = T^{(0)} = M$.

---
Tags: algorithms, knapsack-problems, integers
---


# Question
Title: If a sparse language is NP complete, then are all languages in NP in P/poly?
If a Sparse Language is NP complete, then are all languages in NP in P/poly? I know that sparse languages are in P/poly, but does a polynomial time reduction give an addition to the circuit that is super polynomial? A sparse language is such that $\forall n \in \mathbb{N}, |L \cap \\{ 0,1 \\} ^{n} | \leq p(n)$ for some polynomial $p(n)$.

# Answer
> 1 votes
Yes, see Mahaney's theorem. It states that if a sparse language is $\mathbf{NP}-$complete, then $\mathbf{P=NP}$, and since $\mathbf{P\subseteq P\_{poly}}$, then $\mathbf{NP\subseteq P\_{poly}}$

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


# Question
Title: Checking if a $k$-subset of a graph is a vertex cover in time $O(kn)$
Given a graph $G=(V,E)$ with $|V|=n,|E|=m$. I am reading a $\textit{brute force}$ solution to determining whether each candidate vertex cover of size $k \leq n$ is a vertex cover. The graph does not have loops.

As per page 2 of the notes here we have:

* 1) $C(n,k) = O(n^k)$ $k$-subsets of $V$
* 2) $O(kn)$ time to check whether a subset is a vertex cover

I am considering 2).

What I would think of would be to take each edge in our graph, for which there is a maximum of ${n \choose 2} = O(n^2)$, and check the candidate subset to see if at least one of the vertices is an endpoint of the edge, which would take $O(kn^2)$ checks.

I am not sure how the author arrived at $O(kn)$ operations, any insights appreciated.

# Answer
The answer depends on the exact computation model and on the representation of the input. But here is one way to check whether a given subset is a vertex cover, assuming the graph is represented using adjacency lists.

Let the purported vertex cover be $S$, of size $k$. Start by counting all edges in $G$, stopping once you reach $kn$. If there are more than $kn$ edges, then $S$ is not a vertex cover, and we can stop. In time $O(|E|) = O(kn)$, you can count (1) $\sum\_{i \in S} \deg(i)$ and (2) the number of edges connecting vertices in $S$. The total number of edges covered by $S$ is the difference between these two numbers, which you can compare to $|E|$.
> 2 votes

---
Tags: graphs, vertex-cover
---


# Question
Title: Is the choice of static and dynamic typing not visible to the programmers of the languages?
From *Design Concepts in Programming Languages* by Turbak

> Although some **dynamically typed languages** have simple type markers (e.g., Perl variable names begin with a character that indicates the type of value: $ for scalar values, @ for array values, and % for hash values (key/value pairs)), dynamically typed languages typically have no explicit type annotations.
>
> The converse is true in **statically typed languages**, where explicit type annotations are the norm. Most languages descended from Algol 68 , such as Ada , C / C++ , Java , and Pascal , require that types be explicitly declared for all variables, all data-structure components, and all function/procedure/method parameters and return values. However, some languages (e.g., ML , Haskell , FX , Miranda ) achieve static typing without explicit type declarations via a technique called type reconstruction or type inference.

**Question 1:** For dynamically typed languages which "have no explicit type annotations", do they need to infer/reconstruct the types/classes, by using some type/class reconstruction or type/class inference techniques, as statically typed languages do?

**Question 2:** The above quote says static or dynamic typing and explicit or no type annotations can mix and match.

* Is the choice between static and dynamic typing only internal to the implementations of programming languages, not visible to the programmers of the languages?
* Do programmers in programming languages only notice whether the languages use explicit type/class annotations or not, not whether the languages use static or dynamic typing? Specifically, do languages with explicit type/class annotations look the same to programmers, regardless of whether they are static or dynamic typing? Do languages without explicit type/class annotations look the same to programmers, regardless of whether they are static or dynamic typing?

**Question 3:** If you can understand the following quote from *Practical Foundation of Programming Languages* by Harper (a preview version is https://www.cs.cmu.edu/~rwh/pfpl/2nded.pdf),

* Do the syntax for numeral (abstract syntax num\[n\] or concrete syntax overline{n}) and abstraction (abstract syntax fun(x.d) or concrete syntax λ(x)d ) use explicit types/classes with dynamic typing?
* If yes, is the purpose of using explicit types/classes to avoid type inference/reconstruction?

> **Section 22.1 Dynamically Typed PCF**
>
> To illustrate dynamic typing, we formulate a dynamically typed version of PCF, called DPCF. The abstract syntax of DPCF is given by the following grammar:
>
> ```
> Exp d :: = x x variable
>            num[n] overline{n}      numeral
>            zero zero      zero
>            succ(d) succ(d)      successor
>            ifz {d0; x.d1} (d) ifz d {zero → d0 | succ(x) → d1}      zero test
>            fun(x.d) λ(x)d      abstraction
>            ap(d1; d2) d1 (d2)      application
>            fix(x.d) fix x is d      recursion
>
> ```
>
> **There are two classes of values in DPCF**, the numbers, which have the form num\[n\], and the functions, which have the form fun(x.d). The expressions zero and succ(d) are not themselves values, but rather are constructors that evaluate to values. General recursion is deﬁnable using a ﬁxed point combinator but is taken as primitive here to simplify the analysis of the dynamics in Section 22.3.
>
> As usual, the abstract syntax of DPCF is what matters, but we use the concrete syntax to improve readability. However, notational conveniences can obscure important details, such as the tagging of values with their class and the checking of these tags at run-time. For example, the concrete syntax for a number, overline{n}, suggests a “bare” representation, the abstract syntax reveals that the number is labeled with the class num to distinguish it from a function. Correspondingly, the concrete syntax for a function is λ (x) d, but its abstract syntax, fun(x.d), shows that it also sports a class label. The class labels are required to ensure safety by run-time checking, and must not be overlooked when comparing static with dynamic languages.

Thanks.

# Answer
> 3 votes
> Question 1

No, dynamically-typed programming languages usually do not perform any kind of type inference. The common approach is to check types at runtime, and cause a runtime error or exception in case a type mismatch is found.

> Question 2

Having static or dynamic type checking is a choice which is visible to programmers. A program like

```
print "hello"
print (3 / "a string?")

```

in a statically-typed language will cause a compile-time type error (hence before it prints anything), while in a dynamic language the program will start, print `hello`, and then error out.

Also a program like

```
if 0==1:
    print (3 / "a string?")

```

will run perfectly fine in a dynamically-typed language, but won't compile if using static type checking.

> Question 3

There is no type inference, or type reconstruction being performed there. Types are not made explicit in the program. The runtime system can simply store a tag near values to remember their type (`number` or `function`), so that runtime type checking can be performed.

---
Tags: programming-languages, type-theory
---


title: Algorithm to find best solution

text:
# Question
Title: Algorithm to find best solution
I am writing a software as small project in TypeScript/JavaScript and got to a problem i cant solve: A Company makes a new contract with a customer and wants to order materials. There are serval suppliers with fix delivery costs. Each supplier can offer some of the materials with different pack sizes and prices. What is the best approach to get the materials for the lowest price? I wanted my App to automatically suggest the best order.

*** You can order at multiple suppliers; You can order more materials than needed ***

Further explanation: I know what materials needed for the contract, for Example (Input):

750 of Material 1 250 of Material 2 500 of Material 4 50 of Material 5

I know the delivery Costs and material costs of each supplier. Delivery costs are only paid once for each supplier. I want to get the best solution to order the materials (cheapest).

Output should be a list like: Ammount - Product of supplier - Supplier

Example:

Material 1

1 x 500Q,P40 from Supplier 1 2 x 125Q,P12 from Supplier 3

Material 2

1 x 250Q,P60 from Supplier 3

....

# Answer
> 1 votes
Your problem is hard, but not too hard.

Start with a subproblem: For one material, you have various package sizes with different cost. You also require a certain amount of material. Find the cheapest way to buy your material.

To do that, use dynamic programming: Let's say you need 5000 units. Find in turn the cheapest way to buy at least 1, 2, 3, ..., 5000 units. The cheapest way for 0 units is buying nothing. To buy at least K units, you either buy one package with size \>= K, or you buy one package with size k \< K, then buy packages with total size at least K - k at the lowest possible price. Of the choices you have, you use the cheapest one.

Second subproblem: Find all sets of possible suppliers. Just try all possible subsets - for n suppliers there are $2^n$ possible subsets of suppliers, and reject all subsets that don't contain any supplier for a material that is required.

Then for each possibe subset of suppliers, find the cheapest way to buy each material. Add up the cost for the materials, plus the delivery cost. And then take the subset of suppliers that was cheapest.

For small problem sizes, this shouldn't take too long. Of course the problem looks NP-complete if you turn it into a decision problem, so your execution time will grow exponentially with the problem size.

Finding the cheapest way to buy each material seems to be the most time critical. Think how you can optimise it by finding packages you should never buy (if you have a pack of 25 costing 12, and a pack of 24 costing 13, you would never buy the 24), and amounts you don't care about (in your example with pack sizes 100, 200 and 500, your total is always a multiple of 100).

# Answer
> 0 votes
Your problem is NP-hard. Note that I'm slightly changing definitions here, since the original problem is an optimization problem and not a decision problem. More specifically, I will assume your problem is a decision problem where we want to decide if you can make an order that is below a cost $C$. I will now assume that there is a hypothetical subroutine Order-Cost that runs in polynomial time that solves this.

We can reduce Set Cover to your problem fairly easily. Let $U$ be the universe of elements, let $\mathcal{X}$ be the set of subsets of $U$. We are also given an integer $k$. We now want to decide whether there exist (at most) $k$ sets in $\mathcal{X}$ with their union being equal to $U$.

For each $X \in \mathcal{X}$, we create a supplier with a delivery cost of 1. For each $x \in X$ we make a material with only one quantity and price, where the quantity is equal to 1 and its price to 0. Furthermore, we set $C = k$. For our order we want to have at least all elements of $U$.

Note that this reduction runs in polynomial time as we go over each set of $\mathcal{X}$ and element of $U$ once. We return whatever Order-Cost returns.

Proof of correctness: Suppose a Set Cover instance is a yes instance, then let $S$ be the set of sets that unify to $U$. Note that $|S| \leq k$. Since the constructed suppliers directly correspond to the sets in $\mathcal{X}$, we can buy all items from our order $U$ with cost at most $k$. Hence, Order-Cost also outputs yes.

The other direction is extremely similar. If we can find at most $k$ suppliers, that is we pay at most $k$, to complete our order, then there exist $k$ sets such that their union is $U$.

Since your problem is NP-hard, finding an efficient algorithm will be hard. You can attempt a backtrack algorithm, where you go over each material and vendor. Although since there is a touch of subset sum involved, even that will become rather complicated.

---
Tags: algorithms, mathematical-analysis
---


# Question
Title: What is the language feature which allows a variable to be associated with values of different types?
In Python, I can change the types of values associated with a variable:

```
>>> x=1
>>> x="abc"

```

In C, I can't do the same.

What is the name of the feature that allows Python to behave so, while not C?

I was wondering if the following language features have to do with the observation in Python:

* no explicit type annotations,instead of explicit type annotations
* dynamic typing, instead of static typing
* or reference model of variable, instead of value model of variables?

Thanks.

# Answer
> 4 votes
Allow me to address the misconceptions in your question one by one.

> In Python, I can change the types of values associated with a variable:
>
> ```
> >>> x=1
> >>> x="abc"
>
> ```

In type theory, types classify *expressions*, i.e., *syntactic* objects, i.e., *program* fragments. From this point of view, Python has exactly one type. Confusingly, what Python calls “types” are what type theory calls *classes* of a single type.

> I was wondering if the following language features have to do with the observation in Python:
>
> * no explicit type annotations,instead of explicit type annotations

Annotations have nothing to do with this. There exist languages, such as ML and Haskell, that allow the programmer to omit most type annotations, yet the type of a variable binding is never allowed to change throughout its scope.

This is not to say that it is impossible to design a programming language in which the type of a variable could change within its scope, but Python is by no means such a language.

> * dynamic typing, instead of static typing

What I said above about the meaning of “type” in type theory.

> * or reference model of variable, instead of value model of variables?

There is no such thing as “reference model of variable”. A variable always stands for a value. It just so happens that Python has no values other than object references. For example, the Python expression `2 << 1000` does not evaluate to the number $2^{1000}$. It evaluates to an *object* that represents the number $2^{1000}$. There can be two different objects that represent the same number, as this snippet illustrates:

```
>>> x = 2 << 1000
>>> y = 2 << 1000
>>> x is y
False

```

Of course, in mathematics, it makes no sense whatsoever to distinguish between “this $2^{1000}$” and “that $2^{1000}$”. Since Python's `int`s do not behave like mathematical integers, Python simply does not have integer values.

Confusingly enough, against established tradition, Python's equality testing operator is called `is` rather than `==`.

---
Tags: programming-languages, type-theory
---


# Question
Title: Stable matching problem is greedy or Dynamic?
Is the stable matching problem greedy or Dynamic ? Please anyone can give a strong explanation as i tried to find it on the net but it isn't available.

# Answer
If you consider the Gale–Shapley algorithm, it takes a greedy approach.

By the definition of Wikipedia:

> A greedy algorithm is an algorithmic paradigm that follows the problem solving heuristic of making the **locally optimal choice at each stage** with the hope of finding a global optimum.

The Gale-Shapley Algorithm does exactly that. **At each step**, the 'proposers' take a greedy decision of selecting the best partner (**locally optimal choice**) that was not yet proposed.
> 1 votes

# Answer
Problems are not greedy or dynamic. Algorithms might use a greedy heuristic or the dynamic programming paradigm.

The usual algorithm for solving the stable matching problem is iterative, and so fits to neither the greedy paradigm nor the dynamic programming paradigm. You might as well have asked whether quicksort were greedy or dynamic programming.
> 2 votes

# Answer
If you are asking about the Gale-Shapley algorithm, GS algorithm is not greedy.

A greedy algorithm is one that does not change its decision once made.
> 1 votes

---
Tags: dynamic-programming, greedy-algorithms, matching
---


# Question
Title: If a sparse language is NP-complete then are all NP languages sparse?
If a Sparse Language is NP-complete then are all NP languages sparse? We say a language is sparse if $\forall n \in \mathbb{N}, |L \cap \\{ 0,1 \\} ^{n}| \leq p(n)$, for some polynomial $p(n)$?

# Answer
> 1 votes
If we only consider the latter half of the question: "are all NP languages sparse", the answer is no. A counterexample is $\\{0,1\\}^\*$. It belongs to NP but is not sparse.

However, you added a precondition: "a sparse language is NP-complete", and $A\rightarrow B$ is true if $A$ is false, so the answer depends on whether there exists a NP-complete sparse language. Since it remains open whether there exists a NP-complete sparse language, your question also remains open.

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


# Question
Title: How does image reconstruction take place in neural network?
I am reading through and thinking about how neural network works and have been reading about convolutional neural networks (CNN). I am particularly interested in image filtering (or enhancing) using CNN. The thing that confuses me is, how exactly does CNN produce the output, filtered/enhanced image? From what I understand each layer convolves the previous input into more distinctive features, so aren't we essentially losing details? How would the network then know that, for example, this noisy image A, should be cleaned up here and there as such trained to produce a clean image B?

# Answer
A plain CNN normally isn't used to produce an image as output; but if you combine it with deconvolution layers, then you can produce an image as output.
> 1 votes

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


# Question
Title: Given a DCEL, how do you identify the unbounded face
I have constructed a DCEL using the procedure described in How do I construct a doubly connected edge list given a set of line segments?.

This correctly identifies all faces, however I'm struggling to come up with a way to identify the unbounded face surrounding my graph.

So far my only idea is that by building a polygonal representation of every face, I could find the face polygon which 'contains' all the others, but this seems kind of messy.

# Answer
Take any extreme vertex (say among the vertices having the minimum x-coordinate, the one that minimizes y). This vertex is incident to two edges touching the outer face. Namely the first and the last half-edges leaving this vertex. The first one has the outer face on its right and the last one on its left.
> 3 votes

---
Tags: data-structures, computational-geometry, doubly-connected-edge-list
---


# Question
Title: Is there any scenario whereby randomly shufflying a sequence improves it's compressibility?
I'm performing some correlation assessment à la NIST Recommendation for the Entropy Sources Used for Random Bit Generation, § 5.1.

You take a test sequence and compress it with a standard compression algorithm. You then shuffle that sequence randomly using a PRNG, and re-compress. We expect that the randomly shuffled sequence to be harder to compress as any and all redundancy and correlations will have been destroyed. It's entropy will have increased.

So if there is any auto correlation, $ \frac{\text{size compressed shuffled}} {\text{size compressed original}} \> 1$ .

This works using NIST's recommended bz2 algorithm, and on my data samples, the ratio is ~1.03. This indicates a slight correlation within the data. When I switch to LZMA, the ratio is ~0.99 which is \< 1. And this holds over hundreds of runs so it's not just a stochastic fluke.

What would cause the LZMA algorithm to repetitively compress a randomly shuffled sequence (slightly) better than a non shuffled one?

# Answer
> 1 votes
I now think that it's because of this:-

> ZPAQ has 5 compression levels from fast to best. At all but the best level, it uses the statistics of the order-1 prediction table used for deduplication to test whether the input appears random. If so, it is stored **without compression** as a speed optimization.

... from https://en.wikipedia.org/wiki/ZPAQ#Compression

I'm referring to LZMA in my question, but I'm not familiar with how it's implemented in code. If it followed the same speed optimisation strategy as ZPAQ, the hypothesis would be consistent with my observations. You can imagine in edge cases where $ \frac{\text{size compressed shuffled}} {\text{size compressed original}} = 1 - \epsilon $, that an $n$ order predictor decides that there is insufficient advantage to be had due to the necessary compression encoding overhead. My $\alpha \approx 0.01$, but recently I've seen it as high as 0.04.

---
Tags: algorithm-analysis, entropy
---


title: Minimum descending stacks

text:
# Question
Title: Minimum descending stacks
Assume a randomly ruffled pack of n cards with numbers from 1 to n. Each time we pick the top card from the pack (while there are still cards) and we put them according to the following rules:

The first card goes to the top of a stack

For every new card k,or

(i) the k is put on the top of an already existed stack, if the value of the top card of a existed stack is bigger than the value of the card k or

(ii) we create a new stack righter than the other stacks and with the card k.

The game is completed after n rounds when there are no more cards on the first pack of cards.

The problem asks to find the optimal algorithm for minimum stacks and prove that this one is the optimal. Thanks in advance.

# Answer
Use the following strategy $S$: Put each card $c$ on the stack with the smallest top card $c'$ such that $c' \> c$.

Consider a generic strategy $T$, and iteratively simulate $S$ and $T$. Let $s\_i = (s^i\_1, s^i\_2, \dots, s^i\_{h\_i})$ be the values on the top of the stacks after placing the $i$-th card $c\_i$ according to strategy $S$, in increasing order. Define $t\_i = (t^i\_1, t^i,\_2, \dots, t^i\_{k\_i})$ similarly for strategy $T$.

Claim: $\forall i=1,\dots,n$, we have: i) $h\_i \le k\_i$ and ii) $s^i\_j \ge t^i\_j$ for all $j = 1, \dots, h\_i$.

The proof is by induction on $i$. For $i=1$ we have $h\_1=k\_1=1$ and $s^1\_1 = t^1\_1 = c\_1$. For $i\>1$ we have two cases.

Case 1) $S$ places $c\_i$ in a new stack. Then, by hypothesis we must have $c\_i \> s^{i-1}\_j \ge t^{i-1}\_j$ for every $j = 1, \dots, h\_{i-1} $. It follows that $k\_i \ge h\_{i-1} + 1 = h\_i$, proving i). Notice that ii) is also verified since, for $j=1,\dots, h\_{i-1}$, we have $c\_i \> s^i\_j = s^{i-1}\_j \ge t^{i-1}\_j = t^i\_j$ by induction hypothesis, and $t^i\_{h\_i} \le c\_i = s^i\_{h\_i}$.

Case 2) $S$ places $c\_i$ in an existing stack. Let $\ell$ be the index such that $s^{i}\_\ell = c\_i$. We clearly have $k\_i \ge k\_{i-1} \ge h\_{i-1} = h\_i$, proving i). As far as ii) is concerned, for every $j = 1, \dots, \ell-1$ we have $c\_i \> s^{i-1}\_j \ge t^{i-1}\_j$, and hence $s^i\_j \ge t^i\_j$. Also, $s^i\_\ell = c\_i = \min\\{s^{i-1}\_\ell, c\_j\\} \ge \min\\{t^{i-1}\_\ell, c\_j\\} = t^i\_\ell$. Finally, for $j=\ell +1, \dots, h\_i$, we have: $s^i\_j = s^{i-1}\_j \ge \max\\{c\_i, s^{i-1}\_j\\} \ge \max\\{c\_i, t^{i-1}\_j\\} \ge t^i\_j$.

Instantiating the claim with $i=n$ yields $h\_n \le k\_n$, showing that $S$ is minimizing the number of stacks.
> 1 votes

---
Tags: algorithms, time-complexity, stacks
---


# Question
Title: Distinction between paging and segmentation?
In my operating systems textbook, there is a paragraph which states:

---

As for the contents of each PTE, we have a number of different bits in there worth understanding at some level. A valid bit is common to indicate whether the particular translation is valid; for example, **when a program starts running, it will have code and heap at one end of its address space, and the stack at the other. All the unused space in-between will be marked invalid, and if the process tries to access such memory, it will generate a trap to the OS which will likely terminate the process.** Thus, the valid bit is crucial for supporting a sparse address space; by simply marking all the unused pages in the address space invalid, we remove the need to allocate physical frames for those pages and thus save a great deal of memory.

---

However, the bold sentences confuse me. I thought the whole point of paging was that you do away with the contiguous regions of logical code segments like stacks and heaps? With paging, couldn't the stack and heap be anywhere and non-contiguous? What guarantee do you have that the code, heap and stack will be separated to the top and bottom of the address space,as they say?

# Answer
There are two different address spaces, let's call them *logical* and *physical*. The addresses a programmer thinks about are the logical addresses, the page table translates logical addresses to physical addresses.

As you point out, *paging* allows you to sparsely map the logical address space to the physical address space.

But the bold sentences in your quote are talking about the sparsity of the *logical* address space. The quote is arguing that the valid bit is necessary for the sparsity of the logical address space.
> 2 votes

---
Tags: memory-management, memory-hardware, virtual-memory, memory-access, memory-allocation
---


# Question
Title: Schedule each entree so that all entrees are completed in the shortest amount of time
Lets say we have plenty people to dress up entrees, but only one chef to cook them. Each entree $E\_i$, takes $c\_i$ time to cook and $d\_i$ time to "dress up". The dressing up of entrees can occur while other entrees are being cooked and dressed up, but we can only cook one entree at a time. How would you go about creating an algorithm to schedule each entree $E\_i$ in a manner that they all get finished in the shortest amount of time?

# Answer
> 3 votes
The link suggested by @D.W. above put into words exactly what I was looking for, an "exchange lemma" that proves the optimality of the greedy strategy. Here it is:

Suppose we cook in the order $1,2,\ldots, n$. Let $i \in \\{1,2,\ldots,n-1\\}$ be the smallest integer such that $d\_i\<d\_{i+1}$. We claim that altering the order of the cooking of dishes $i$ and $i+1$, and changing nothing else, results in an equally good or better finishing time. Let us denote $ft(k)$ as the time when dish $k$ is finished under the original ordering (and all dishes are finished at time $\max\limits\_{1\leq k\leq n} ft(k)$). We also denote by $ft'(k)$ the time when dish $k$ is finished under the altered ordering.

In general, we have $$ ft(k) = \sum\limits\_{j=1}^k c\_j + d\_k $$ since we need to finish cooking dish $k$, which happens after $1,2,\ldots, k-1$, and then finally we dress it.

For the altered ordering we have \begin{align\*} ft'(i+1) &= \sum\limits\_{j=1}^{i-1} c\_j + c\_{i+1} + d\_{i+1}\\ ft'(i) &= \sum\limits\_{j=1}^{i-1} c\_j + c\_{i+1} +c\_i + d\_{i} \end{align\*} (the funny ordering is just to emphasize the order in which the dishes are cooked).

The following three facts are easy to prove:

1. $ft(k)=ft'(k)$ for all $k \neq i, i+1$
2. $ft'(i)\leq ft(i+1)$
3. $ft'(i+1)\leq ft(i+1)$

These three together imply that $\max\\{ft'(i),ft'(i+1) \\} \leq \max\\{ ft(i),ft(i+1)\\}$ and hence $\max ft'(k) \leq \max ft(k)$ which proves the greedy strategy.

---
Tags: greedy-algorithms
---


# Question
Title: Defining $a^n b^{n^2}$ with one existential SO binary relation
> Is it possible to define the language:

$$L = \\{ a^n \\; b^{n^2} \\}$$

> using an existential second order sentence over strings (ordered structures with unary predicates $U\_a(x), U\_b(x)$) using only one binary relation?

The sentence should have this form: $\exists M ( \exists B\_1,...,B\_n ( \varphi ))$ where:

* $M$ is a binary relation
* $B\_i$ are monadic
* $\varphi$ is first order with signature (available relations) $\sigma = \langle \<, U\_a, U\_b \rangle$

If not, how to prove it? (or cite a textbook in which I can find similar exercises)

# Answer
First off, I assume you also want to have a binary relation on the domain, acting as a linear order: \<. Furthermore, I assume you want to deal with existential second-order logic, which in general allows more than one existential quantifiert.

Then, you can employ Fagin's theorem: wikipedia And what remains to show is that you can recognize the language $a^{n}b^{n^{2}}$ in polynomial time. Can you do that?

**Edit:** Now, since it is clarified that you indeed want to just have an existential binary relation, consider the following:

* Büchi-Elgot-Trakthenbrot tells us that regular languages (which yours is not, but that needs a prove) are exactly those that can be described by MSO. The prove gives already big insights in how many different variables you need.
* Those languages definable in MSO are exactly those that are definable in existential MSO (see for this *Finite Model Theory* by Ebbinghaus and Flum, thm 6.2.3)
* Those languages definable in existential SO are those recognizable in NP, that's Fagin's theorem.

So you have that e-MSO matchs the regular languages. If you can prove that the different existential quantifiers in BET are necessary for recognizing a language and a binary relationvariable cannot encode the unaries, you are done.

A different approach (possibly more fruitful) is to argue the following way: The constraint $a^2 = b$ is a meta constraint. You have to emulate this inside your language to get it in the object-world. Now im general SO over the empty signature is strong enough for such, but this is a different exercise. So you have to show two things: Is your framework strong enough to emulate $x \mapsto x^2$ relative to the discrete order? Pay attention, Beth's Definability Theorem does fail in general in the finite, as does Craig's Interpolant Theorem (both for FO). This is also in above's book, 3.5.1. If you succeed in doing so, you still have to following problem: You need to get the "meta-size" of $U\_a$ and $U\_b$ into the object language. This is possible if you allow existential quantifiers of the form "exists exactly n many x:", which is possible in FO. However, you can only do this for a fixed number, additionally, you cannot get the "object-size" into the meta language. You could employ counting to test for sizes. In the MSO setting, they are of the form "$C\_n(X)$ which is satisfied iff $ X mod n = 0$. These are not possible to emulate with just a binary relationvariable and FO. Can you show that even using those, you cannot get enough?

**Another edit**: Lets consider the solution with two binary relations, $R$ and $S$. I'll furthermore use $\bot$ as the smallest element of the order, $\top$ as the largest.

* $\forall x, y: (x,y) \in R \implies U\_a(x) \wedge U\_b(y)$
* $\forall x: ((x,\top) \in R \iff x = \bot) \wedge ((\bot,x) \in R \iff x = \top)$
* $\forall x: \exists y: (x,y) \in R$
* $\forall y: \exists! x: (x,y) \in R$
* $\forall x\_1, x\_2, y\_1, y\_2: x\_1 \< x\_2 \wedge U\_a(x\_1) \wedge U\_a(x\_2) \wedge (x\_1, y\_1) \in R \wedge (x\_2, y\_2) \in R \implies y\_2 \< y\_1$

Well, $R$ does split $U\_b$ into $|U\_a|$ many equivalence classes, each of which is not empty and the smaller the values in $U\_a$, the large the corresponding values in the factorized $U\_b$. A model of this sentence can look like this (numbers being the elements in $U\_a$ and letters being the elements in $U\_b$ factorized by the equivalence relation induced by $R$.

> w = 1-2-3-cc-bbbbbbb-a

What is left now is to make sure that the equivalence classes have the appropriate size. For this, note that we can indeed encode $x \mapsto x^2$ inside a binary relation (somewhat). See here that if $n = 1$, we have to append 1 element to the end and if $n = m + 1$, then for this one element more in $U\_a$, we have to add as many elements to $U\_b$ as we did for m, and two additional ones ($(n+1)^2 - n^2 - (n^2 - (n-1)^2) = 2$, aka when considering adding +1 repeatedly to $n$, one has to add 1, 3, 5, ... to $n^2$).

So, let's encode this behaviour with $S$:

* $\forall y\_1, y\_2: (y\_1, y\_2) \in S \implies U\_b(y\_1) \wedge U\_b(y\_2)$
* $\forall y: \neg (y, \top) \in S$ (probably redundant)
* $\forall y\_1: (\exists y\_2: (y\_1, y\_2) \in S) \implies (\exists! y\_2: (y\_1, y\_2) \in S)$
* $\forall y\_1: (\exists y\_2: (y\_2, y\_1) \in S) \implies (\exists! y\_2: (y\_2, y\_1) \in S)$
* $\forall y\_1, y\_2: (y\_1, y\_2) \in S \implies (\exists x\_1, x\_2: (x\_1, y\_1) \in R \wedge (x\_2, y\_2) \in R \wedge \neg \exists x\_3: (x\_1 \< x\_3 \wedge x\_3 \< x\_2) \wedge x\_1 \< x\_2)$
* $\forall y\_1: (\exists x\_1, x\_2: x\_1 \< x\_2 \wedge (x\_1, y\_1) \in R) \implies \exists y\_2: (y\_1, y\_2) \in S$

This asserts that $S$ acts only on $U\_b$, that if it is defined, it'll be uniquely defined (an injective partial function so to say, I'll use it from now on as a function), nothing is mapped to the largest element and whenever "$y\_2 = S(y\_1)$", than $y\_2$ is in the equivalence class induced by the direct successor of the inducer of the equivalence class of $y\_1$. Furthermore, $S$ is defined for each element that is not member of the "least" equivalence class.

With the help of this auxiliary function, we can control the size of the equivalence classes produced by $R$:

* $\forall x: \bot \< x \wedge U\_a(x) \implies (\exists x': x' \< x \wedge (\neg \exists x'': x' \< x'' \wedge x'' \< x') \wedge (\forall y: (x', y) \in R \implies (x, S(y)) \in R \wedge \exists^2 z: U\_b(z) \wedge (x, z) \in R \wedge \neg \exists q: S(q) = z \wedge \forall w: (x, w) \in R \implies (w = z \vee \exists y: (x', y) \in R \wedge w = S(y)))$

This formula expresses that for each element in $x \in U\_a$, which is not the smallest one, there is a next smaller one $x'$. The elements which are paired with $x'$ in $R$ translated with $S$ are paired with $x$ in R, there are two additional elements which are not the image of any of those. Lastly, there are no elements paired with $x$) besides these two additionals and those that came from $x'$.

The following is now up to you:

1. Prove that all models of this sentence are words of the form $a^nb^{n^2}$
2. Prove that every word of the form $a^nb^{n^2}$ does satisfy this sentence
3. Show that you can indeed encode the two relations into one
> 3 votes

# Answer
After a little bit of struggling I found an easy answer by myself:

We can "define" a ternary relation:

$T(x,y,z) \equiv M(x,y) \land M(y,z) \land M(z,x)$

Then we can define $L$ in this way:

* $\exists M$ such that
* $\forall x,y \\;.\\; U\_a(x) \land U\_b(y) \to x \< y$ ($a$s before $b$s)
* $\forall z \\;.\\; U\_b(z) \to \exists x, y \\;.\\; U\_a(x) \land U\_a(y) \land T(x,y,z)$ (for all $b$s there is a pair of $a$s and ...)
* $\forall x, y, z\_1, z\_2 \\;.\\; U\_a(x)\land U\_a(y) \land U\_b(z\_1) \land U\_b(z\_2) \\;.\\; T(x,y,z\_1) \land T(x,y,z\_2) \to z\_1 = z\_2$ (... there is a disticnt pair of $a$s associated with each $b$)
* $\forall x,y \\;.\\; U\_a(x) \land (U\_a(y) \to \exists z \\;.\\; U\_b(z) \land T(x,y,z)$ (... and there is no "unmapped" $a$)

the number of distinct $a$s pairs is exactly $n^2$
> 1 votes

---
Tags: reference-request, finite-model-theory
---


# Question
Title: Are SAT problems with at most two false clauses NP-complete?
Is the problem of deciding whether a SAT instance, where at most two clauses are false (that is, any given variable assignment will either lead to all clauses being true, all but one, or all but two), is satisfiable solvable in polynomial time?

This is a follow-up from my previous question. The problem presented in that question (at most one false clause) was solvable in polynomial time, because we could take advantage of the fact that the set of truth assignments that make a clause false is disjoint to that of any other clause. With two or more clauses, the sets that make a clause false can overlap with each other. Does this mean that problems with at most two (or more) false clauses (when I say "or more," I do not mean that the number can change with the problem size. A problem with five clauses where at most five are false is a trivial version of regular SAT, but what about a problem of a few million clauses where are most five can be false?) are NP-complete, or are all versions of SAT where you limit the number of false clauses solvable in polynomial time?

# Answer
Yes. You can solve this in polynomial time. The same strategy as in Are SAT problems with at most one false clause NP-complete? works.

Let $\varphi$ denote the CNF formula you care about, and $n$ the number of variables in $\varphi$. Let $A\_{i,j}$ denote the number of truth assignments that do not satisfy clauses $i$ or $j$ of $\varphi$, let $A\_i$ denote the number of truth assignments that do not satisfy clause $i$ but do satisfy all other clauses of $\varphi$, and let $A$ denote the number of truth assignments that satisfy all clauses of $\varphi$.

These three cases are mutually exclusive. Therefore,

$$\sum\_{i,j} A\_{i,j} + \sum\_i A\_i + A = 2^n,$$

where $n$ counts the number of variables in the formula. In other words,

$$A = 2^n - \sum\_{i,j} A\_{i,j} - \sum\_i A\_i.$$

You can compute $A\_i$. Let $S\_i$ denote the set of variables mentioned in clause $i$. There is only one assignment to the variables in $S\_i$ that will make clause $i$ false, so substitute in those values for the variables in $S\_i$ and simplify the formula; the result is a CNF formula $\varphi'$ where we are guaranteed that every assignment to the remaining $n-|S\_i|$ variables satisfies at most one clause, so https://cs.stackexchange.com/a/115849/755 tells us how to count the number of satisfying assignments to $\varphi'$, say $n\_i$. Then $A\_i = n\_i$.

You can compute $A\_{i,j}$. It is either $2^{n-|S\_i \cup S\_j|}$ or $0$, depending on whether there is any variable $x\_k$ such that both $x\_k$ and $\neg x\_k$ appear in those clauses $i$ and $j$ of $\varphi$.

Therefore, you can compute $A$, the number of assignments that satisfy the formula. Now, if $A \ne 0$, then you know that the formula is satisfiable; if $A=0$, the formula is not satisfiable.
> 4 votes

# Answer
It depends on the availability of data...

If you store the relaitonships between the data rather than trying to compute at runtime then it is an o1 operation with massive storage requirements...

Otherwise arbitrarily hard..
> -2 votes

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


# Question
Title: On satisfiability for 2-variable FOL being NEXPTIME-complete
Let $\mathbf{FO^2}$ be the fragment of first-order logic consisting of sentences with at most two variables and no function symbols. It is well known that satisfiability for $\mathbf{FO}^2$ is decidable (see \[\], for instance). Furthermore, in that same paper, it is argued that $\mathbf{FO^2}$ satisfiability is $\mathbf{NEXPTIME}$-complete, and that this result follows from these two lemmas:

1. Satisfiability for $\mathbf{FO^2}$ is in $\mathbf{NTIME}(2^{O(n)})$.
2. Satisfiability for $\mathbf{FO^2}$ has a lower complexity bound of the form $\mathbf{NTIME}(2^{cn/\log{n}})$ for some positive constant $c$.

I don't have a lot of background in complexity theory, so this has left me with two questions:

1. Is it easy to see that these two lemmas imply $\mathbf{NEXPTIME}$-completeness?
2. Is this result not contradictory? By definition, $\mathbf{NEXPTIME} = \bigcup\_{k \in \mathbb{N}}\mathbf{NTIME}(2^{n^k})$, and by the non-deterministic time hierarchy theorem we have for any $i, j \in \mathbb{N}$ that $\mathbf{NTIME}(2^{n^i}) \subsetneq \mathbf{NTIME}(2^{n^j})$ if $i \< j$. So I'm wondering how a problem complete for the class can lie at the "lowest rung" of the ladder - is this because Karp-reductions can blow-up the size of an input polynomially?

---

*REFERENCES*

\[\] On the Decision Problem for Two-Variable First-Order Logic - Grädel, Kolaitis and Vardi

# Answer
> 1 votes
Regarding your first question: I haven't read the paper, but I guess that the proof of the second lemma is by a polynomial time reduction from a generic $\mathbf{NEXPTIME}$-hard problem. This establishes $\mathbf{NEXPTIME}$-hardness. Membership in $\mathbf{NEXPTIME}$ is by the first lemma. Regarding the second question, your guess is correct.

---
Tags: complexity-theory, first-order-logic
---


title: Scheduling task optimization

text:
# Question
Title: Scheduling task optimization
I have the acyclic directed graph of tasks I want to perform. Each edge of the graph is a dependency, e.g. task 4 could be performed only after 1 and 2 completed.

```
0
`----> 1 ------------> 4 ---> 7
`                      ^      ^
`---> 3                |      |
`     `------> 2 -----/       |
`     `------> 5 ----------- /
`     `------> 6 ---------- /
`
`--> 8
     `------> 9
     `------> 10
     `------> 11

```

I need to perform all tasks consequently but with optimizations like running tasks in parallel where it is possible.

Topological sorting allows me to build just a sequence of tasks execution:

```
0, 1, 3, 8, 2, 5, 6, 9, 10, 11, 4, 7

```

But I need something like:

```
0, [1, 3, 8], [2, 5, 6, 9, 10, 11], 4, 7

// [...] - means parallel processing

```

Could you recommend any algorithm to achieve this?

# Answer
> 4 votes
When you compute the topological ordering, you usually select one node with no predecessor and remove it from the graph. Instead you can scan the whole list of vertices and select *all* source vertices and remove them at once, only then you update the degree of the remaining vertices. The groups of vertices you remove together represent tasks that can be executed in parallel.

Note: As it stands now, all your tasks take the same amount of time. In reality however tasks started at the same time aren't finished at the same time. You maybe want to have a look into the Program evaluation and review technique

---
Tags: algorithms, graphs, scheduling
---


# Question
Title: What kind of language does the following DFA accept?
can anyone please describe the language this FA accepts? thank you

# Answer
> 0 votes
It accept all the words containing $i$ "a"s and $j$ "b"s for which $i \equiv j \pmod{4}$.

---
Tags: formal-languages, automata, finite-automata
---


# Question
Title: How to mathematically prove that a relation T(n)=T($\sqrt{n}$)+c is O(log(log(n))?
following question, I understood the intuition behind how cutting down the size of input by square root on each iteration leads to O(log(log(n))) complexity.

I tried to derive it on paper.

Let T(n) = T($\sqrt{n}$) + c
$\implies$ T($n^{1/2}$)+2c
$\implies$ T($n^{1/4}$)+3c
$\implies$ T($n^{1/8}$)+4c
$\implies$ T($n^{1/16}$)+5c
.....upto n \> 1

I noticed that the power of n becomes 1/2 times the last value.

How should I proceed from here on? I need to derive that T(n) is O(log(log(n))).

# Answer
> 1 votes
As you mention, you can show inductively that $T(n) = T(n^{1/2^k}) + kc$, with base case $T(n) = O(1)$ for $n \leq 2$ (say). It follows that $T(n) = \Theta(\ell)$, where $\ell$ is the minimal number such that $n^{1/2^\ell} \leq 2$. Taking a log, we get $\frac{\log n}{2^\ell} \leq 1$, or $\log n \leq 2^\ell$. Taking another log, we get $\log \log n \leq \ell$. Hence $\ell = \lceil \log\log n \rceil$, and it follows that $T(n) = \Theta(\log\log n)$.

# Answer
> 2 votes
Let $x = \log n$ and $Q(x) = T(2^x)$. You can rewrite your recurrence as follows: $$ Q(x) = T(2^x) = T(n) = T(n^\frac{1}{2}) + c = T(2^{x/2}) + c = Q(x/2) + c. $$

Which is easily solved using, e.g., the Master Theorem to obtain $Q(x) = \Theta(\log x)$. Substituting back: $$ T(n) = Q(x) = \Theta(\log x) = \Theta(\log \log n). $$

# Answer
> 1 votes
Define S(k) = $T(2^{2^k})$.

Then S(k) = $T(2^{2^k})$ = $T(2^{2^{k-1}}) + c$ = $T(2^{2^{k-2}}) + 2c$ = ... = $T(2^{2^{k-k}}) + k\cdot c$ = $T(2) + k\cdot c$.

---
Tags: algorithm-analysis, time-complexity, asymptotics, runtime-analysis
---


title: Queries on knapsack

text:
# Question
Title: Queries on knapsack
Given items with weights $w\_{1}, w\_{2}, \dots, w\_{n}$ and queries of form $(l, r, w)$ asking for possibility to find a subset of items $w\_{l}, w\_{l + 1}, \dots, w\_{r}$ with total weight $w$, how to answer these queries with $O(1)$ time by having done precalculation of some table in $O(nW)$ time, where W is strict upper bound for $w\_{i}$.

The time for precalculation looks similar to the straight 0-1 knapsack, but here I can't see what we really should put in the table.

# Answer
I'm assuming that $W$ is an integer upper bound to $\sum\_i w\_i$, as asked by xskxzr, that all $w\_i$ are positive integers, and that the values $w$ in the queries are also integers upper bounded by $W$.

For $i \ge 1$, let $S\[i,w\]$ be the largest index $j \in \\{1, \dots, i\\}$ such that it is possible to select a subset of $\\{w\_k : j \le k \le i \\}$ of weight $w\>0$. If no such index $j$ exists, or if $w \le 0$, let $S\[i,w\] = -\infty$.

According to the above definition:

* For $w \neq w\_1$, $S\[1,w\] = - \infty$.
* For $i \ge 1$, $S\[i,w\_i\] = i$.
* For $i\>1$, and $w \neq w\_i$, $S\[i,w\] = \max \begin{cases} S\[i-1,w\] & \\ S\[i-1,w-w\_i\] & \end{cases} $

There are only $O(n W$) "interesting" values of $S\[i,w\]$ to compute (namely those with $i=1,\dots,n$ and $w=1,\dots,W$), each of which can be found in constant time.

To answer a query $(l,r,w)$ proceed as follows (pick the first condition that applies):

* If $w = 0$, return true (the subset you're looking for is the empty set);
* If $w \< 0$, return false;
* If $r \< 1$, return false (since, at this point, $w \neq 0$).
* return true if and only if $S\[\min\\{r,n\\},w\] \ge l$.
> 1 votes

---
Tags: dynamic-programming, matrices, intervals
---


# Question
Title: Guaranteed existence of a blocking set in the accept definition of Stellar
In the SCP, condition 2 of the accept definition allows a node to vote for one statement and later accept a contradictory one. Condition 2 assumes the existence of a v-blocking set which has not only voted for a but also accepted it. What is the argument to show that this is the case?

# Answer
> 1 votes
What is guaranteed is that if a quorum of an intact nodes accepts a statement s, then eventually every intact node v will find itself v-blocked by a set of nodes that has accepted s, i.e. "accept s" cascades throughout all intact nodes until all have accepted and then confirmed s. This is called the cascade theorem in the paper "Fast and secure global payments with Stellar". You can find a brief justification of this theorem at the end of section 3.1.2. There is also a formal proof in Isabelle/HOL here: https://github.com/stellar/scp-proofs. Finally it is also guaranteed that if an intact node is v-blocked by "accept s", then at least one intact node saw a quorum voting for s.

---
Tags: distributed-systems, communication-protocols, consensus, blockchain
---


title: Prove its not a regular language

text:
# Question
Title: Prove its not a regular language
I have a question. Assume $L = \\{ a^m b^m \mid m ≥ 1 \\}$ is not a regular language. Prove that $I = \\{ a^{5n} b^{3m} c^n d^m \mid m,n ≥ 0 \\}$ is not a regular language.

I can prove it with pumping lemma but the question is to solve it by using the assumption.

Thanks.

# Answer
Here's a hint: we know that $L = \\{x^m y^m \mid m ≥ 1 \\}$ is a non-regular language.

Is there some part of $I = \\{ a^{5n} b^{3m} c^n d^m \mid m,n ≥ 0\\}$ which looks similar to $x^m y^m$?

Could you somehow extract that part?

If you could, could you use the fact that $L$ is not regular to conclude that the extracted part is not regular?

Given this, can you then conclude that $I$ is not regular?
> 1 votes

---
Tags: regular-languages
---


title: Can a dfa return only the final state?

text:
# Question
Title: Can a dfa return only the final state?
I am given an assignment to design a tiny arithmetic unit (from 0 to 15 inclusive) start with 0 and using a DFA. The operations are as follow:

* increment x+1 and if x+1 is larger than 15 then x+1 goes to 0
* decrement x-1 and if x-1 is less than 0 then x-1 goes to 15
* multiplication: 2\*x and if 2\*x is larger than 15 then we take 2\*x - 16
* division: we simply take the floor of (x/2)

My initial though of the solution was as follow:

1) number the states as follow q0,q1,q2,...,q15 where q0 is the initial state. So the state represent the result of the arithmetic operations

2) the transitions between the states represent the arithmetic operations.

However, soon after I remembered my teacher saying that the DFA return a string of transitions.

My question is can we make the DFA return the final state only (so in my case if it returns qN then the result is N) ? if not how should I solve this problem?

# Answer
I think there's a misconception. DFA by themselves don't return anything. A DFA is a mathematical model. You can interpret the current state of the DFA when it hits an accept state as containing a result, but that's an interpretation you are making that's not part of the mathematical notion of a DFA. Alternatively, you can consider a Moore machine or Mealy machine, which are mathematical models that do produce output; you can think of them as like a DFA but with an extension to allow them to produce output.
> 2 votes

---
Tags: regular-languages, finite-automata, logic
---


# Question
Title: Recover permutation from prefix sums, using segment trees?
I encountered the following problem on Codeforces.

> An array of integers $p\_1,p\_2,…,p\_n$ is called a permutation if it contains each number from 1 to n exactly once. For example, the following arrays are permutations: $\[3,1,2\],\[1\],\[1,2,3,4,5\]$ and $\[4,3,1,2\]$. The following arrays are not permutations: $\[2\],\[1,1\],\[2,3,4\]$.
>
> There is a hidden permutation of length $n$.
>
> For each index $i$, you are given $s\_i$, which equals to the sum of all $p\_j$ such that $j\<i$ and $p\_j\<p\_i$. In other words, $s\_i$ is the sum of elements before the $i$-th element that are smaller than the $i$-th element.
>
> Your task is to restore the permutation.

How can I solve this problem using segment trees in $O(n\log n)$ time?

I tried to understand the solution on Codeforces but I could not understand it. Their solution:

> Let us fill the array with numbers from 1 to $N$ in increasing order.
>
> 1 will lie at the last index $i$ such that $s\_i=0$. Find and remove this index $i$ from the array and for all indices greater than $i$, reduce their $s\_i$ values by $1$. Repeat this process for numbers $2,3,\ldots,N$. In the $i$th turn, reduce the elements by $i$.
>
> To find the last index with value zero, we can use segment tree to get range minimum query with lazy propagation.

I do not understand what is stored in segment tree (like least number in the given range) and how the update is done in $O(\log n)$ time in this case. Can you show me an example input and show me what happens in each iteration?

My attempt: I tried to solve this problem by making a segment tree where each node will contain the smallest number in the range corresponding to that node. But I was not able to solve the problem.

For example: Suppose I have sample input:

```
5
0 1 1 1 10

```

My segment tree will look like:

```
                           [1-5](0)
                          /        \
                      [1-2](0)      [3-5](1)
                    /      \         /      \
                [1-1](1) [2-2](1)   [3-4](1) [5-5](10)
                                   /       \
                              [3-3](1)      [4-4](1)

```

Value adjacent to each range is minimum value in its sub tree. I failed to solve using this approach since update will take $O(n)$ time.

# Answer
> -1 votes
The segment tree is useful in this problem because you need to maintain an array of values where the supported operations are: 1) decrementing all elements in a range by the same amount and 2) querying a range for its (rightmost) minimum-value location.

In this problem, the values maintained in the array are the *sums* $s\_i$, that have to be adjusted as described by the solution.

In your example, the subsequent contents of the array will be as follows:

```
0 1 1 1 10 # we query range (1, 5) and obtain position 1 (rightmost minimum)
∞ 1 1 1 10 # we remove the value at position 1, by setting it to INFINITY
∞ 0 0 0 9  # we subtract 1 from all values to its right (range (2, 5))
∞ 0 0 0 9  # we query range (1, 5) and obtain position 4 (rightmost minimum)
∞ 0 0 ∞ 9  # we remove the value at position 4
∞ 0 0 ∞ 7  # we subtract 2 from all values to its right (range (5, 5))
∞ 0 0 ∞ 7  # we query range (1, 5) and obtain position 3 (rightmost minimum)
∞ 0 ∞ ∞ 7  # we remove the value at position 3
∞ 0 ∞ ∞ 4  # we subtract 3 from all values to its right
∞ 0 ∞ ∞ 4  # we query range (1, 5) and obtain position 2 (rightmost minimum)
∞ ∞ ∞ ∞ 4  # we remove the value at position 2
∞ ∞ ∞ ∞ 0  # we subtract 4 from all values to its right
∞ ∞ ∞ ∞ 0  # we query range (1, 5) and obtain position 5 (rightmost minimum)
∞ ∞ ∞ ∞ ∞  # we remove the value at position 5 and stop.

```

Since the sequence of minimum positions was P = \[1, 4, 3, 2, 5\], it means that in the hidden permutation number 1 is at position 1, number 2 is at position 4, and so on. Hence the hidden permutation is \[1, 4, 3, 2, 5\], the *inverse* of P (although in this case it's the same).

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


title: Spanning tree with chosen leaves

text:
# Question
Title: Spanning tree with chosen leaves
I'm working on the following problem:

> Suppose that we're given a connected, undirected graph $G = (V, E)$ with edge weights $w\_e$ and a subset of vertices $U \subset V$. We want to find the lightest spanning tree in which the nodes of $U$ are leaves (there may be other leaves as well). We want to do so in $O(|E|\log(|V|))$ time.

Here's my thinking: since every node $v \in U$ must be a leaf, there must exist a vertex $u \in V \setminus U$ that is the source (i.e. each leaf in $U$ is connected to $u$). However, I'm having trouble find a way to do this that doesn't involve running a polynomial time algorithm. Can anyone help?

# Answer
> 4 votes
Hint for idea: Consider the subgraph $G'$ induced by the vertices in $V \setminus U$. Compute its MST $T'$. Then how should you attach the vertices in $U$ to $T'$?

Hint for implementation: To achieve $O(|E| \log |V|)$, you still run ordinary MST on the original graph $G$, but pay special attention to the vertices in $U$.

# Answer
> 3 votes
The solution can be found here which is similar to that suggested by @hengxin

Minimum spanning tree with chosen leaves

Outline of the algorithm

1. Generate an induced graph `G'` containing the vertices `V'=V-U` and the edges `E'` not involving the vertices in `U`
2. Apply Kruskal's algorithm to get `T'= MST(G')`
3. If `T'` does not exist then the solution does not exist
4. Construct an edge set `E" = (u, v)` where `u` belongs to `U` and `v` does not belong to `U`
5. Apply Kruskal's algorithm on `E"` by adding edges to `T'`
6. Return `T'`

# Answer
> 0 votes
I guess a few modification to the graph may close to the answer. The set $U$ must be chosen and they must form the leaves, right? suppose $u \in U$, For every $v$ adjacent to the $u$ find the minimum edge $\\{u,v\\}$, assign weight $0$ to it and then remove every other edge connected to the $u$. In the result graph every vertex $u \in U$ necessarily form the leaves.

But you must be careful that every two vertices belong to $U$ must be either disconnected or be on at least one cycle in order to form leaves.

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


# Question
Title: Is my formal definition of programming language correct?
I found this formal definition of a programming language in the 1973 paper Formal definition of programming languages by Terrence Pratt.

> PL is a formal language endowed with two structures: a translator and an abstract machine.
>
> Translator defines a mapping from program strings, as defined by BNF grammar, into a representation of programs as hierarchies of directed graphs.
>
> Abstract machine is a mathematical model of computation.

Is it an appropriate and full definition? Do you have another?

# Answer
> 1 votes
It is certainly not a full definition; one might reasonably expect a "real" programming language to have not merely an abstract mathematical model defining the language's semantics, but also a concrete implementation of a compiler or an interpreter which runs on an actual computer. Then again, one might reasonably not expect this. Is lambda calculus, for example, a programming language? Wikipedia doesn't define it as one, but if somebody else does then I can't say they are wrong.

There are many aspects of what makes a language a "programming language"; reasonable people might disagree on whether a certain aspect (say, Turing completeness) is strictly necessary for something to count as a true programming language. It is unlikely that any list of such aspects would ever be agreed by all computer scientists, or even just the academic computer science community, to be both correct and complete.

The concept of a "programming language" is not in the same category as mathematical concepts such as "group". It is possible for a formal definition of a group to be correct or incorrect, but a formal definition of a programming language can merely be useful or not useful (or, more useful or less useful) relative to the use at hand. Presumably, the definition you quoted was useful for the author of the paper you found it in.

---
Tags: formal-languages, computability
---


# Question
Title: Assigning Balls to Bins with Constraints on Which Ball to Go to Which Bin?
Let us say we have $m$ bins and $n$ balls. Every bin $i$ has capacity $c\_i$ which is the number of balls that can be put into bin $i$. We have $c\_i\geq1$ for all $i$. For each bin $i$, there is a collection of sets $S\_i=\\{X\_1,X\_2,\ldots,X\_{k\_i}\\}$ for given $k\_i$. Each $X\_j\in S\_i$ is the set of balls that can be put into bin $i$. We have $|X\_j|\leq c\_i$ and $\emptyset\in S\_i$ for all $i$.

For example, for $m=2$ and $n=3$, with $c\_1=1$ and $c\_2=2$, say we have $k\_1=4$ and $k\_2=5$. Say we have $S\_1=\\{\emptyset,\\{1\\},\\{2\\},\\{3\\}\\}$. $S\_2=\\{\emptyset,\\{1\\},\\{2\\},\\{3\\},\\{2,3\\}\\}$. This means that ball $1$, $2$ or $3$ can be each assigned to bin $1$. Also, each ball can be assigned to bin $2$. Further, balls $2$ and $3$ can be together assigned to bin $2$. We might have an instance with $k\_2=6$ and $S\_2=\\{\emptyset,\\{1\\},\\{2\\},\\{3\\},\\{2,3\\},\\{1,2\\}\\}$ for example.

We want to assign the maximum number of balls into the bins. Is this easy or hard?

# Answer
You can reduce the Exact Cover problem to your problem. The elements in the Exact Cover problem corresponds to the balls in your problem. For each subset $T$ in the Exact Cover problem, we construct a bin $i$ with $S\_i=\\{\emptyset, T\\}$. Then there exists an exact cover if and only if all balls can be put into the bins. Hence, your problem is NP-hard.
> 2 votes

---
Tags: algorithms, np-hard
---


# Question
Title: Worst Case running time of the Minimum Vertex Cover Approximation algorithm
Considering this factor $2$ minimum vertex cover approximation algorithm :

> Repeat while there is an edge:
>
> Arbitrarily pick an uncovered edge $e=(u,v)$ and add $u$ and $v$ to the solution. Delete $u$ and $v$ from the graph. Finally output the candidate cover.

I want to find the worst case running time of this algorithm. Since in a fully connected graph we have $O(n^2)$ edges, then the loop will run at most $O(n^2)$ times.

Here I am not sure what the maximal number of delete operations could be or perhaps for less than $O(n^2)$ edges being processed in the loop there would be some scenario with a large number of delete operations would contribute to the overall complexity.

I want to say naively that in the worst case you simply multiply the max number of edges possible with the max number of delete operations possible (both $O(n^2))$ giving $O(n^4)$, but this seems wrong.

Any insights appreciated.

# Answer
> 1 votes
It depends on which data structure you use to store the graph.

For example, suppose the nodes are represented as $0,\ldots,n-1$, and the edges are stored as a list of pairs of nodes. We can build an boolean array $\mathrm{arr}$ of length $n$ initialized with all $\texttt{true}$s, and when a node $i$ is deleted, we simply mark $\mathrm{arr}\[i\]$ as $\texttt{false}$. Each time we deal with an edge, we first check if any of its endpoints is deleted to see if the edge has already been covered. With such data structures, your algorithm runs in $O(n^2)$.

---
Tags: algorithms, algorithm-analysis, time-complexity, vertex-cover
---


# Question
Title: Does DFS in an unweighted DAG find the shortest path for each vertex from a source?
I have many questions which related to this topic. I saw somewhere that a topological sorting can be used to find shortest path, and in DAG it can even find shortest weighted paths of all vertex by asking about each vertex whether it's weighted higher than edge plus previous vertex. The point is, I don't understand since we are in DAG why isn't DFS alone enough to find shortest paths. Both weighted and unweighted. I also don't understand why we need a stack in topological sort. If you were to perform a DFS on some DAG. It will automatically produce a topological sort, if you do a pre-order DFS traverse.

# Answer
The only question is in the tile so I'm going to answer that.

A DFS visit from a source $s$ of a unweighted DAG $G$ does not find the shortest paths of $G$ from $s$. As a counter example look at the following graph:

If vertex $a$ is visited before vertex $b$ you will not necessarily discover the shortest path from $s$ to $b$.

Also, the same example shows that the order in which vertices are considered by a preorder DFS traversal is not necessarily a topological sort. Indeed, if $b$ is visited before $a$ the order would be: $s, b, a$ but there is an edge from $a$ to $b$.
> 1 votes

# Answer
> 1. Why don't we just use DFS to find shortest path in DAG?

For this try to find shortest path from source vertex $0$ to all vertex in following graph.

In particular if DFS visits $1$ first from $0$ then it will assign shortest path distance $10$ to $4$ which is wrong.
> 1 votes

---
Tags: algorithms, algorithm-analysis, topology
---


title: Time Complexity of the below code?

text:
# Question
Title: Time Complexity of the below code?
here is a nested loop where all the variable are integers.This is another question to the thread. I understood the solution part , but stuck in the time-complexity part.

**What is the time complexity of the below code and how**?

```
def divide(dividend, divisor):
    """
    :type dividend: int
    :type divisor: int
    :rtype: int
    """
    #Time-complexity ??
    while dividend>=divisor:
        t=0;k=divisor

        while dividend>=k:
            dividend-=k
            k<<=1
            q+=1<<t
            t+=1

    return q

```

# Answer
It is $O(\log^2 \frac{\text{dividend}}{\text{divisor}})$.

The inner loop clearly takes at most $O(\log \frac{\text{dividend}}{\text{divisor}})$ time since initially $k= \text{divisor}$ and it is doubled at every iteration.

The outer loop requires at most $O(\log \frac{\text{dividend}}{\text{divisor}})$ iterations since the inner loop subtracts from $\text{dividend}$ the highest multiple $x = k \cdot \text{divisor}$ such that $k=2^i - 1$ for some integer $i$ and $x \le \text{dividend}$. This is true because initially $k \le \log ( 1+ \frac{\text{dividend}}{\text{divisor}})$ and the same value of $i$ cannot be selected more than two times in a row since $3 \cdot (2^i - 1) = 3 \cdot 2^i - 3 = 2^{i+1} + (2^i-3) \ge 2^{i+1} - 1$.

---

This analysis is tight in the following sense: let $\text{divisor}=1$ and $S\_j = \sum\_{i=0}^j (2^i - 1)$. Let $\text{dividend}= S\_\ell$ for some $\ell \ge 2$ of choice.

Clearly $S\_j \> 2^j - 1$. Moreover, we can show by induction on $j$ that $S\_j \< 2^{j+1}-1$.

The base case $j=0$ is trivial: $S\_0 = 0 \< 2^1 - 1 = 1$. Suppose now that the claim is true for $j-1$: We have $S\_j = S\_{j-1} + (2^j - 1) \< 2^j - 1 + (2^j - 1) = 2^{j+1} - 2$.

This means that when divisor is $S\_j$, the inner loop will subtract $2^{k}-1$ where $k=j$ (in $k-1$ iterations), and the divisor will become $S\_{j-1}$. It follows that $\ell$ iterations of the outer loop are needed to reach $S\_0 = 0$.

The **overall** number of iterations of the inner loop is then: $$ \sum\_{i=1}^\ell (i-1) = \sum\_{i=0}^{\ell-1} i = \frac{\ell (\ell-1)}{2} = \Theta(\ell^2). $$

But $\ell \ge \log S\_\ell$, since $S\_\ell$ has at least $\ell$ binary digits and hence the above quantity is $\Omega(\log^2 S\_\ell) = \Omega(\log^2 \text{dividend}) = \Omega(\log^2 \frac{\text{dividend}}{\text{divisor}})$.
> 2 votes

---
Tags: algorithms, algorithm-analysis, time-complexity, runtime-analysis, loops
---


# Question
Title: Algorithm for mapping objects of list without mapping to itself?
I want to map objects of a list, to objects of that same list, randomly, without ever mapping any given object to itself.

So given a list of objects \[a, b, c\] valid maps would be, for example:

```
   a -> b,
   b -> c,
   c -> a

```

or

```
   a -> c,
   b -> a,
   c -> b

```

an invalid mapping would be:

```
   a -> a,
   b -> c,
   c -> b

```

I just cannot figure out how to implement such an algorithm.

(This is for a small Secret Santa app that I am building where each person will be assigned to buy gift to one of the other participants.)

# Answer
> 2 votes
If you want a cyclic permutation with no trivial cycles (i.e., the only cycle involves all elements) see Sattolo's algorithm.

If you only want to avoid trivial cycles (but you are fine with cycles of length at least $2$), the mathematical object is called a derangement.

See: https://math.stackexchange.com/questions/302057/generating-a-random-derangement

Since the probability $p\_n$ that a random permutation on $n$ elements is a derangement approaches $\frac{1}{e}$ as $n \to \infty$, you can easily get a randomized algorithm by simply generating a random permutations (e.g., using Fisher-Yates shuffle) until you find a derangement.

The above bound is asymptotic but this works even for small values of $n$. This is because the number of derangements on $n \ge 2$ elements is $!n = \left\lfloor \frac{n!}{e} + \frac{1}{2} \right\rfloor$ (see,e.g., here). Since $p\_n = \frac{!n}{n!}$, we can explicitly compute $p\_2 = \frac{1}{2}$, $p\_3 = \frac{2}{6} = \frac{1}{3}$, and for $n \ge 4$ we have:

$$ p\_n = \frac{!n}{n!} = \frac{\left\lfloor \frac{n!}{e} + \frac{1}{2} \right\rfloor}{n!} \> \frac{\frac{n!}{e} - \frac{1}{2}}{n!} = \frac{1}{e} -\frac{1}{2 \cdot n!} \ge \frac{1}{e} -\frac{1}{2 \cdot 24} \> \frac{1}{3}. $$

This shows that, on average, you will not reject more than $2$ permutations. In general, the probability that you will look at more than $2t$ permutations will always be at most $(2/3)^{2t} \le 2^{-t}$.

---
Tags: algorithms
---


# Question
Title: When are log complexities considered equivalent?
Would we consider $O(\log\_2(n))$ to be the same complexity as $O(\log\_2(n-1))$?

Why or why not? I'm specifically wondering about how the number we take the log of affects the time complexity.

# Answer
> 3 votes
$O(\log(n))$ and $O(\log(n-1))$ contain the same set of functions.

The inclusion $O(\log(n-1)) \subseteq O(\log(n))$ is trivial. As for $O(\log(n-1)) \supseteq O(\log(n))$, let $f(n) \in O(\log(n))$ and let $c \ge 1$ and $n\_0 \ge 3$ be such that: $$ f(n) \le c \log(n) \quad \forall n \ge n\_0. $$

We have: $$ f(n) \le c \log(n) = c + c \log(n/2) \le c + c \log(n-1) \le 2c \log(n-1). $$

Showing that $f(n) \in O(\log(n-1))$.

---
Tags: asymptotics, landau-notation
---


# Question
Title: Decoding problem and conditional probabilities
I'm reading the book by MacKay "Information theory, inference and learning algorithms" and I'm confused by how he introduces the decoding problem for LDPC codes (page 557).

> given a channel output $\mathbf{r}$, we wish to find the codeword $\mathbf{t}$ that whose likelihood $P(\mathbf{r}|\mathbf{t})$ is biggest.

I can get on board with that, even if it seems a bit backwards since $\mathbf{r}$ is the *evidence* we have, so I would be more comfortable if we were trying to find $\mathbf{t}$ that maximizes $P(\mathbf{t}|\mathbf{r})$, and as a matter of fact, he goes on to say

> there are two approaches to the decoding problem both of which lead to the generic problem 'find $\mathbf{x}$ that maximizes $$ P^\*(\mathbf{x})=P(\mathbf{x})\mathbb{1}\[\mathbf{Hx}=\mathbf{z}\]$$

he exposes the two points of view in the following page, the first one especially confuses me

> *the codeword decoding point of view*
>
> First, we note the prior distribution over codewords $$ P(\mathbf{t})=\mathbb{1}\[\mathbf{Ht}=\mathbf{0}\]$$\[...\]. The posterior distribution over codewords is given by multiplying the prior by the likelihood \[...\] $$P(\mathbf{t}|\mathbf{r})\propto P(\mathbf{t})P(\mathbf{r}|\mathbf{t}) $$

from the generic decoding problem he gave, it looks like we're actually trying to maximize $P(\mathbf{x})=P(\mathbf{t}|\mathbf{r})$, instead of $P(\mathbf{r}|\mathbf{t})$.

Is it obvious that the two maxima are the same and with the same maximizer? It is not obvious to me since the maximizer $\mathbf{t\_0}$ that maximizes $P(\mathbf{r}|\mathbf{t})$ might actually minimize $P(\mathbf{t})$, so the maximizer of $P(\mathbf{t})P(\mathbf{r}|\mathbf{t})$ might be different! I understand that in this case $P(\mathbf{t})$ is uniform, so this shouldn't be a problem, but it seems weird to me that this is simply not stated and I feel like I'm missing something.

Why should we start with the problem of maximizing $P(\mathbf{r}|\mathbf{t})$ and not $P(\mathbf{t}|\mathbf{r})$? Why does he seem to switch after a few sentences? Am I correct in thinking the algorithm presented actually maximizes $P(\mathbf{t}|\mathbf{r})$?

Thank you

# Answer
> 2 votes
Maximizing $P(r|t)$ is known as the Maximum Likelihood (ML) principle, while maximizing $P(t|r)$ is known as the Maximum A Posteriori probability (MAP) principle.

Here are some facts that answer your question:

* Optimal decoding (minimizing the probability of error) is achieved by the MAP principle. See p. 152 of the book.
* However, using MAP would require a different decoding algorithm for every distribution on $t$. I.e. you would have to adapt decoding to the statistical properties of the source. To avoid this, it is typical to assume a uniform distribution on $t$. In this case, MAP and ML are equivalent because $P(t|r)$ becomes proportional to $P(r|t)$ (see p. 152 again).
* I agree with you he should have started with the MAP problem of maximizing $P(t|r)$, since that's the correct goal anyway. But I presume that he is assuming a uniform distribution on $t$, in which case the difference doesn't matter anyway.

---
Tags: coding-theory, error-correcting-codes
---


# Question
Title: Are these special (one production) Context-Free Grammars always unambiguous?
Consider the following (Context-Free) Grammars with only one production rule (not including the epsilon production):

* $S \rightarrow aSb\\;|\\;\epsilon$
* $S \rightarrow aSbS\\;|\\;\epsilon$
* $S \rightarrow aSaSb\\;|\\;\epsilon$
* $S \rightarrow aaSaaSbb\\;|\\;\epsilon$
* $S \rightarrow aSbScSdSeSf\\;|\\;\epsilon$
* etc...

Grammars like these uphold 4 basic rules:

1. **The non-terminal symbol $S$ can never appear next to itself.**
    * e.g. $\[\\;S \rightarrow aSSb\\;|\\;\epsilon\\;\]$ would **not** be allowed.
2. **The non-terminal symbol $S$ can appear at the beginning or end of a production but not on both sides at the same time.**
    * e.g. $\[\\;S \rightarrow SabaS\\;|\\;\epsilon\\;\]$ would **not** be allowed.
    * e.g. $\[\\;S \rightarrow Saba\\;|\\;\epsilon\\;\]$ or $\[\\;S \rightarrow abaS\\;|\\;\epsilon\\;\]$ *would* be allowed.
3. ~~**The sequence of terminal symbols that exist between each non-terminal $S$ cannot *all* match.**~~ (EDIT: This rule is redundant, Rule 4 already ensures that at least two sequences of terminals are non-matching)
    * ~~e.g. $\[\\;S \rightarrow aSaSa\\;|\\;\epsilon\\;\]$, $\[\\;S \rightarrow abSabSab\\;|\\;\epsilon\\;\]$, etc. would **not** be allowed.~~
    * ~~e.g. $\[\\;S \rightarrow aSaSb\\;|\\;\epsilon\\;\]$, $\[\\;S \rightarrow abSabSaf\\;|\\;\epsilon\\;\]$, etc. *would* be allowed.~~
4. **The sequence of terminal symbols at the beginning and end cannot match.**
(i.e. $\[\\;S \rightarrow ☐\_1SaS☐\_2\\;|\\;\epsilon\\;\]$ s.t. $☐\_1 \neq ☐\_2$ where $☐\_1$ and $☐\_2$ are a sequence of terminal symbols)
    * e.g. $\[\\;S \rightarrow aSbSa\\;|\\;\epsilon\\;\]$, $\[\\;S \rightarrow aaSbSaaS\\;|\\;\epsilon\\;\]$, etc. would **not** be allowed.
    * e.g. $\[\\;S \rightarrow aSbSb\\;|\\;\epsilon\\;\]$, $\[\\;S \rightarrow aaSbSaxS\\;|\\;\epsilon\\;\]$, etc. *would* be allowed.

> 5. **The grammar cannot be made to break any of the above rules via a $S \rightarrow \epsilon$ production. (Vimal Patel)**
>     * e.g. $\[\\;S \rightarrow aSbSaSbS\\;|\\;\epsilon\\;\]$ could become $\[\\;S \rightarrow abSabS\\;|\\;\epsilon\\;\]$ if the first and third $S \rightarrow \epsilon$, thus violating Rule 4.

Are (Context-Free) Grammars, that follow these 4 rules, always unambiguous? It would seem so. I really don't see any conceivable way that such Grammars could be ambiguous.

(Note: To show why Rule 4 is necessary consider the grammar $S \rightarrow aSbSa\\;|\\;\epsilon$ with the string $aababaababaa$. A visual derivation can be found here.)

I've spent a lot of time thinking about this question and have had a hard time finding any way of either proving or disproving it. I've tried showing that Grammars like these are $LL(1)$. However, it seems only Grammars of the form $S \rightarrow aSb\\;|\\;\epsilon$ are $LL(1)$. Grammars like $S \rightarrow aSaSb\\;|\\;\epsilon$ are *not* $LL(1)$. Maybe I need to use a higher $k$ for $LL(k)$?

(This question is a follow-up/reformulation of a previous question.)

I would *really* appreciate any help I could get here.

# Answer
Here is a simple counter example: $S \rightarrow aSbSaSbS \space |\space \epsilon$

and string $w: abababab.$ In one case we use last $S$ and in other case we use second $S$. All other $S$ goes to $\epsilon$.

---

Why I was able to get this grammar?

Let's rewrite above grammar with numbers assigned to each $S$'s.

$S \rightarrow aS\_1bS\_2aS\_3bS\_4 | \epsilon$

Now We can virtually eliminate $S\_1$ and $S\_3$. (For this whenever we have to derive something from $S\_1$ or $S\_3$ we will only derive $\epsilon$ from both of this type of $S$'s.)

So we get $S \rightarrow abS\_2abS\_4|\epsilon$. (At this time we already have got rid of rule 3.)

Which we were looking for.
> 9 votes

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


# Question
Title: Is there a O(log n)-time algorithm to find the maximum element of a circular shift of a sorted array?
Consider this problem: You are given an array $A$ (of distinct integers) of one out of the following four types:

* Ascending (e.g., 1,2,4,6);
* Descending (e.g., 6,4,2,1);
* Ascending rotated (a non-trivial circular shift of an ascending array, e.g., 4,6,1,2);
* Descending rotated (a non-trivial circular shift of an descending array, e.g., 4,2,1,6).

The task is to determine the type and the maximum element of $A$.

Since $A$ is "sorted", is there a $O(\log n)$-time approach or is the best possible time complexity $O(n)$, as suggested in the link?

# Answer
Let $A = \langle a\_1, \dots, a\_n \rangle$ be the input array. I will only consider the case $n \ge 3$, otherwise the problem is trivial.

The key property is that the order relation between all but one pair of consecutive elements modulo $n$ in $A$ will be "greater than" if $A$ is some circular shift of an increasing array (possibly the trivial shift by $0$), and "less than" if $A$ is some circular shift of a decreasing array. Examining the first and last elements suffices to determine if the shift is trivial or not.

In practice you can determine the type of $A$ in constant time, as follows:

* Look the majority value $x$ among $\textrm{sign}(a\_1-a\_n)$, $\textrm{sign}(a\_2-a\_1)$, and $\textrm{sign}(a\_3-a\_2)$.
* If $x = +1$ then $A$ is some circular shift of an increasing array. If $\textrm{sign}(a\_1-a\_n)=-1$, $A$ is of type "ascending", otherwise it is of type "ascending rotated".
* If $x = -1$ then $A$ is some circular shift of a decreasing array. If $\textrm{sign}(a\_1-a\_n)=1$, $A$ is of type "descending", otherwise it is of type "descending rotated".

As for returning the maximum, I will only discuss the case in which $A$ is a circular shift of an increasing array (the complementary case is handled similarly). Notice that, if the maximum element is in some position $a\_j$, then all $a\_1, \dots, a\_j$ are larger than or equal to $a\_1$, while all ements $a\_{j+1}, \dots, a\_n$ are smaller than $a\_1$. This allows you to binary search for the last element that is larger than or equal to $a\_1$, i.e., $a\_j$.
> 4 votes

# Answer
if we are given with first two cases i.e Ascending sorted array and descending sorted arrays we can simply find the difference b/w last element of array and first element of array i.e (last element of array - first element of arrays)if difference is positive then it is ascending order and maximum element is the element at last index of array (in ascending sorted arrays ) and vice versa. it takes just 0(1) in that case.
> 0 votes

---
Tags: binary-search
---


# Question
Title: Is there any importance in problems whose witness for membership in a set, cannot be bounded by a polynomial?
The class NP can be defined as a polynomially bounded relation $R$. Where $x \in R$ if there exists some $y$ that has length bounded by $p(|x|)$, where $p$ is some polynomial.

* Why do we not study the case where $y$ is not bounded by a polynomial?
* Is there any significance in problems of this nature; in-efficient proof systems?

# Answer
If we remove the condition on the size of the witness, then a problem is in the resulting class NANY iff it is recursively enumerable.

Indeed, if $L$ is in NANY, then given $x$, we can go over all possible $y$, and for each of them run the machine that decides whether $y$ is a witness for $x \in L$.

In the other direction, suppose that the Turing machine $M$ halts on $x$ iff $x \in L$. We can use the transcript of a halting computation as a witness that $x \in L$.
> 1 votes

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


# Question
Title: If $Q$ reduces to $L$ then $\overline{Q}$ reduces to $\overline{L}$
The following exercise is taken from Chapter 17 of *Languages and Machines* by Thomas Sudkamp:

> Let $Q$ be a language reducible to a language $L$ in polynomial time. Prove that $\overline{Q}$ is reducible to $\overline{L}$ in polynomial time.

I am not sure if my solution idea is correct. Anyone knows the correct solution of this exercise?

My idea is: I use the definition of NP-complete. Q is in NP class and L is NP-complete. The function f to reducible in polynomial time Q to L, is also the function f to reducible in polynomial time notQ to notL

# Answer
By hypothesis $Q \le\_p L$, i.e., there exists a poly-time computable function $f(x)$ such that $x \in L \iff f(x) \in Q$. Then: $$ x \in \overline{L} \iff x \not\in L \iff f(x) \not\in Q \iff f(x) \in \overline{Q}. $$

Therefore $\overline{L} \le\_p \overline{Q}$.
> 2 votes

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


title: Stepwise regression

text:
# Question
Title: Stepwise regression
I think that both forward selection and backward selection should give the same results if the evaluation model is deterministic and using the same variables gives the same results. Is this true? If so, what are the reasons for chosing one method over the other?

# Answer
No, it's not true. There is no guarantee that they will give the same results. They are a heuristic. Neither one is guaranteed to find the optimal subset of features, and they might produce two different subsets.

For instance, the effectiveness of a set of features might depend in some nonlinear and complicated way on the particular set you choose. So, in general, the problem is just the general optimization problem of finding a set $S \subseteq \\{1,2,\dots,n\\}$ that maximizes $f(S)$, where $f$ is some function (here, the accuracy of the model on a cross-validation set). Since $f$ can be arbitrary, forward selection and backward selection can give different results, and neither is guaranteed to yield the optimal set of features.
> 0 votes

---
Tags: machine-learning
---


# Question
Title: Matrix element value counting in O(1) space
The question arise from my customer's real-time system (RAM model, off-course), which has very limited resources.

Given an NxM matrix of integer values, we need to verify that the number of non-zero elements in **every row** and **every column** is maximum 2. The matrix cannot be stored! It comes as a stream (M and N are known in advance but are not constants), row after row, and each element is accessed only once. The space requirement is O(1), i.e. no additional array of size N or M can be used, only a constant number of variables.

Can this be done? If not, can it be proved? Can this be done in O(log(N) + Log(M)) space?

We were taught in undergrad school that if you are unable to provide an adequate solution, prove that no one else can... So I tried to prove to my customer that this can't be done in o(M) space, but was unable to.

Thanks allot

# Answer
Checking whether the number of nonzero elements on each row is at most $2$ can be done in $O(1)$ space on a row-by-row basis by simply counting those elements.

Therefore the only interesting part is checking the condition over the columns. This can be done in $O(M)$ space by keeping a counter for each column. In details, the counter $c\_i \in \\{0,1,2\\}$ associated with the $i$-th column will be the number of rows seen so far that contain a nonzero element in column $i$. As soon as a row with a nonzero element in column $i$ is seen and $c\_i$ was already $2$, you can immediately return "false". If the whole matrix is processed without this happening you can return "true".

Unfortunately, your problem cannot be solved using $x= o(M)$ bits. Suppose this were the case and consider some matrices with $M$ of columns and $N=2M+1$ rows, of the form described in the following.

The $i$-th of the first $M$ rows will have zeros in all columns $j \neq i$, while $i$-th column will either contain a $0$ or a $1$.

The number of distinct choices for the first $M$ rows is $2^M$, yet there are at most $2^x \< 2^M$ (for sufficiently large $M$) different possible states of the $x$ bits of memory. This means that there are (at least) two distinct choices $R$ and $R'$ of the first $M$ rows that leave the algorithm in the same internal state.

In other words, for any choice of the $(M+1)$-th to $(2M+1)$-th rows, the algorithm must behave in the same way, regardless of whether the set of the first $M$ rows was $R$ or $R'$.

Since $R$ and $R'$ are distinct, there must be (at least) one index $i$ such that the element $r\_i$ in the $i$-th column of the $i$-th row of $R$ is different from the element $r'\_i$ in the $i$-th column of the $i$-th row of $R'$. Without loss of generality assume that $r\_i = 0$ and $r'\_i=1$.

For $i=1,\dots,M$, let the $(M+i)$-th row be the row containing a single $1$ in the $i$-th column. Finally, choose the $(2M+1)$-th row to have exactly one $1$ in the $i$-th column.

This leads to a contradiction: On one hand, if the set of the first $M$ rows is $R$, the algorithm must return "true" since there is at most one nonzero element per row and at most two nonzero elements per column; on the other hand, if the set of the first $M$ rows is $R'$, the algorithm must return "false" since column $i$ has $3$ nonzero elements (in the $i$-th, $(M+i)$-th, and $(2M+1)$-th rows).
> 3 votes

---
Tags: algorithms, decision-problem, online-algorithms, streaming-algorithm
---


# Question
Title: On the computable function of a problem that halts
Let's say program $P$ with given input $i$ is found to halt (or doesn’t halt) by a Turing machine. Is it true that the same program $P$ with input $F(i)$ also halts (or not, respectively), where $F$ is a computable function?

In general, is it true that the behavior of program $G(P)$ with the input $F(i)$ identical to the behavior of P with input i? (Both $G$ and $F$ are computable.)

# Answer
> 2 votes
No, it is not.

In general, to help you think about this kind of problem, I recommend you work through some examples. Keep them as simple as possible.

Here is an example that illustrates why the answer is no. Suppose $P$ is the following program: "if the input is 1, then halt immediately; otherwise enter an infinite loop". Suppose $F(1)=2$. Then $P$ halts on the input $i=1$, but it does not halt on the input $F(i)=F(1)=2$. So, the behavior of the program $P$ on one input tells you nothing about its behavior on a different input.

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