# Question
Title: Algorithm for efficiently identifying ambiguities in a set of HTTP routes with wildcards/Unix Globs?
So I have a bunch of strings that represent routes in a HTTP web framework. Each string has a leading `/`, some `/`-separated path segments which can either be a string, a single-segment wildcard `?`, or a trailing multi-segment wildcard `*`. (For this problem, we can assume that `*` can only be in a trailing position, but there may be more than one `?`s)

e.g.

```
/foo
/bar
/qux/?
/?/baz/thingy
/xyz/*
/xyz/abc

```

I am trying to analyze this list of strings to figure out if any of the routes are potentially ambiguous. For example, in the above set,

1. `/?/baz/thingy` and `/xyz/*` are ambiguous, because a path `/xyz/baz/thingy` would satisfy both routes
2. `/xyz/*` and `/xyz/abc` are similarly ambiguous because a path `/xyz/abc` would satisfy both routes

Is there any standard/well-known/commonly-used algorithm for taking the list of inputs and identifying ambiguous subsets of them?

I think this problem can be converted without loss of generality to the problem of finding ambiguities among a set of UNIX-style globs, as below. But I also don't know what algorithm I could use to find ambiguities among a set of unix globs

```
a
b
c?
?dg
e*
ef

```

What exactly the algorithm should return is also a bit unknown to me. e.g. ambiguity between routes is not transitive, so

1. `/?/baz/thingy` is ambiguous with `/xyz/*`,
2. `/xyz/*` is ambiguous with `/xyz/abc`
3. But `/?/baz/thingy` is not ambiguous with `/xyz/abc`

For my purposes I don't really care about the shape of the return value, as long as I can return something human-readable so the user of the framework can see the ambiguities and resolve them. I need it to list all the inputs which are ambiguous, and at least one other input with which it is ambiguous with, but I don't need to list out all the pairwise ambiguities.

EDIT: in fact, for my purposes, finding a single pairwise ambiguity if one exists, or reporting that no pairwise ambiguity exists, is sufficient

I know how to do this pair-wise, e.g. given two routes, it's easy to walk them both in lockstep and see if they are ambiguous or not in one pass. This can give an `O(num_routes^2 * length_of_routes)` algorithm for finding all routes which are ambiguous. Can we do better, especially if we just need to list all the ambiguous routes and not all the pairwise ambiguities? Or is quadeatic complexity the best we can get?

# Answer
> 1 votes
Here is one approach. Suppose $n$ is the max length of any route, in segments. Build $2n$ indices, of the following form:

* An index of all routes, where we include all segments (exact match).
* An index of all routes, where we ignore the $i$th segment, for $i=1,\dots,n$ (match on all but the $i$th segment).
* An index of of all routes, where we only pay attention to segments $1..i$ (i.e., we truncate each route after the $i$th route, so we match on only the first $i$ segments).

Each index can be built as a hashtable or a dict, so that given a route, you can look it up to see if there is any match in the set of all routes.

Of course, what constitutes a match depends on the index. For example, for the index where we ignore the 2nd segment, `/a/b/c/d` is considered to match `/a/x/c/d` and `/a/?/c/d`. This can be implemented by deleting the 2nd segment before inserting or looking up a route in the index; or by building a custom hash function that ignores the 2nd segment.

Insert all routes into these indices.

Now given a route with no wildcards (no `?`, no `*`), you can test whether it matches any other route by looking it up in the first index (exact match on all segments).

Given a route with a trailing `*`, count how many segments precede the `*`, call it $i$, and look up in the index where you match on segments $1..i$ (i.e., on the prefix of length $i$).

Given a route with a single `?`, let $i$ denote the index of the segment where the `?` appears, and look up in the index where you match on all but the $i$th segment.

Given a route with multiple `?`s, fall back to your approach, where you compare this route to all others, one at a time, using your pairwise algorithm. As an optimization, letting $i$ denote the index of the first `?`, you can look up in the index that matches on segments $1..i-1$, enumerate all matches, and use pairwise testing on only those matches. This doesn't help for something like `/?/a/b/?/c`, but it helps a lot for `/a/b/?/d/?/e`.

If you have a lot of routes with multiple `?`s, see String matching.

Related: Efficiently enumerating all "good" strings given the ability to say whether a partial specification can be good, String matching for wildcard-based records, Given a set of string patterns, find which ones match a particular string, https://cstheory.stackexchange.com/q/36913/5038.

---
Tags: algorithms
---


title: Logical address vs physical address

text:
# Question
Title: Logical address vs physical address
I have been trying to understand the logical and physical address of some data/instruction the logical address is a address generated by the CPU during a execution cycle.So if I write this code

```
int a = 0;
printf("%d",&a);

```

what will be printed is the logical address right?So everything from the OS which is running in the computer to a simple program know only the logical address.

# Answer
The OS has to "know" the correspondence between physical and logical addresses, because it's responsible for configuring the Memory Management Unit to map between them, and some part of the OS kernel has to start up in a memory region where logical and physical addresses are identical in order to be able to do that mapping.

Other than that, you're correct, user programs and most of the OS exclusively use logical addresses, and unless you're a low-level kernel developer, you don't need to consider physical addresses at all.
> 2 votes

# Answer
Every time your computer executes an instruction, the address of that instruction is a logical address. Every time a computer instruction access data, the address of the data is a logical address.

There will be some table that describe at which physical address the data belonging to some logical address is stored. Or it isn't stored at any physical address at all, but somewhere on the hard disk, so when you try to execute an instruction or read data, your program gets interrupted, the operating system finds a bit of unused physical memory, reads the data from the hard drive, puts it into that unused memory, then updates the table to reflect where the data is know, and continues your program. OR the table contains information telling your program that it isn't allowed to access data at this logical address, and your program crashes.

Well, there isn't one table, but every process has its own table. So when you switch from process A to process B, A might have data for logical address 12345678 stored at the physical address X, while process B will have completely different data at logical address 12345678 stored at a totally different physical address Y.

The tricky thing is to get the whole thing started. When your computer is turned on, some things happen through the processor's hardware, and then the computer will start executing code at some address X. At this point there is likely no translation between logical and physical addresses turned on yet (because that's too complicated to do using hardware only), so things will be set up so that at this point physical and logical addresses are still the same, and the very first code that the processor executes will likely try to find out which memory chips you have installed in your computer, then it will set up the very first translation table which it can do because it knows what physical memory is available, and then translation gets turned on.
> 2 votes

# Answer
Physical address is the precise location of data in computer memory and logical address is a virtual address that a computer program uses to access memory. While newer processors seamlessly handle both physical and logical addresses, older ones like the Intel 8080/8085 directly generates physical addresses. It doesn't have a separate Memory Management Unit (MMU) or support virtual memory.
> 0 votes

---
Tags: computer-architecture, cpu
---


# Question
Title: Show that NP is closed under concatenation
> Show that NP is closed under concatenation.

This is a homework problem and I would appreciate some guidance. I began by saying the following:

Let $A$ and $B$ exist in NP. Let $V\_1$ and $V\_2$ be verifiers for $A$ and $B$, respectively.

Is it as simple as saying build two NTMs $M\_1$ and $M\_2$ that decide $A$ and $B$ and then concatenate them and build a new machine to decide?

# Answer
No, it's not that simple. You need to explain what you mean by *concatenate $M\_1$ and $M\_2$*. The machines $M\_1,M\_2$ don't output strings that can be concatenated.

You need to describe what the concatenated machine $M$ does. On input $x$, how does it use the machines $M\_1,M\_2$? If you run $M\_1,M\_2$ on the entire input $x$ it won't help you to decide the concatenated language, so you'll have to be more industrious.
> 2 votes

# Answer
The easiest way to prove that *NP is closed under concatenation* is the following:

Assume that $L\_1 , L\_2 \in NP$. Thus, there are two nondeterministic deciders $M\_1$ and $M\_2$ such that $M\_1$ decides $L\_1$ in nondeterministic time $O(n^l)$ and $M\_2$ decides $L\_2$ in nondeterministic time $O(n^k)$.
Let $M$ a TM s.t.

> $M$ on input $w$:
>
> 1. Split $w$ into $w\_1 \in L\_1$ and $w\_2 \in L\_2$ s.t. $w = w\_1 w\_2$;
> 2. Run $M\_1$ on $w\_1$. If $M\_1$ rejects then reject;
> 3. Else run $M\_2$ on $w\_2$, if $M\_2$ rejects then reject;
> 4. Else accept.

This will use $O(n^{\max{l,k}})$ steps. So $M$ is a polytime nondeterministic decider for $L\_1L\_2$.
> 2 votes

# Answer
Proof: If L1,L2∈NP then there exist a deterministic polynomial verifier for L1 and a deterministic polynomial verifier for L2. A polynomial verifier for L1⋅L2 will receive a split “index” (a natural number) of the input w to w1 and w2. The verifier for L1⋅L2 runs L1 verifier on w1 and L2 verifier on w2. Since the verifiers are deterministic and run in polynomial time, we can run them in series and check their answer. If they both accept, the verifier for L1⋅L2 accepts. Otherwise, it rejects.
> 0 votes

---
Tags: complexity-theory, closure-properties, np
---


# Question
Title: Is the "intersection" of the special Halting Problem with a language always undecidable?
I'm exploring the decidability characteristics of a particular language formed by the intersection of two languages, specifically in the context of the Halting Problem. The languages are defined as follows:

1. $\text{Special Halting Problem Language} K: K := \\{ w \in \\{0, 1\\}^\* \mid w\\#w \in H \\}$, where $H$ is the Halting Problem language defined as: $H := \\{ w\\#x \mid w, x \in \\{0, 1\\}^\* \text{ and } M\_w \text{ halts for the input } x \\}$
2. Arbitrary Language $B$: A language that is not further defined for this question.

The language in question, $A$, is the intersection of these two: $A := K \cap B$

My query pertains to the decidability status of $A$. I understand that if $B$ is undecidable, it doesn't necessarily imply that $A$ will also be undecidable, since the intersection of two undecidable languages can have different decidability properties.

Given this context, is the language $A$ decidable, semi-decidable, or undecidable? I'm looking for insights or theorems that could be applied to determine the decidability of $A$, considering the nature of $K$ and the potential characteristics of $B$.

# Answer
> 1 votes
There is no general answer.

$B$ could be decidable or undecidable, and $A$ could too, independently of $B$. This table contains different values of $B$ for all cases.

|  | $B$ decidable | $B$ undecidable |
| --- | --- | --- |
| $A$ **decidable** ($A = \emptyset$) | $B = \emptyset$ | $B = H$ |
| $A$ **undecidable** ($A = K$) | $B = \\{0, 1, \\#\\}^\*$ | $B = K$ |

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


# Question
Title: Proving that $(A \cup B)^* = A^*(BA^*)^*$
I would like to prove that $(A \cup B)^\* = A^\*(BA^\*)^\*$, where * means the Kleene star.

I would like to use induction to prove this equality but I do not how to proceed and how is the best way to set the induction hypothesis.

Could someone please help? Thanks !

# Answer
> 2 votes
As already stated in the comments, it is easy to see that $A^\*(BA^\*)^\* \subseteq (A\cup B)^\*$ as every word $x$ in $ A^\*(BA^\*)^\*$ can be written as a concatenation of words that are either in $A$ or in $B$.

We show that the other containment holds. Consider a word $x \in(A\cup B)^\*$. Then $x$ can be written as $w\_1\cdot w\_2 \cdots w\_k$, where $k\geq 0$ and for all $i\in \[k\]$, it holds that $w\_i\in A$ or $w\_i \in B$ -- note that $x = \epsilon$ can be obtained as a concatenation of length $k=0$. If $x = \epsilon$, or for all $i\in \[k\]$, $w\_i\in A$, then clearly $x$ is in $A^\*(BA^\*)^\*$. Otherwise, let $1\leq i\_1 \< i\_2 \< \cdots \<i\_n \leq k$ be the maximal sequence of indices (maximal w.r.t the number of induces) such that for all $t\in \[n\]$, we have that $w\_{i\_t}\in B\setminus A$. Thus, for all $i\notin \\{i\_t\\}\_{t\in \[n\]}$, we have that $w\_i\in A$. We can now write $x$ as $$x = w\_1\cdot w\_2 \cdots w\_{i\_1} \cdot w\_{i\_1 + 1} \cdots w\_{i\_2} \cdot w\_{i\_2+1} \cdots w\_{i\_n} \cdot w\_{i\_n+1} \cdots w\_k$$

Now it is not hard to see that $x \in A^\*(BA^\*)^\*$. Indeed, the prefix $w\_1 \cdot w\_2\cdots w\_{i\_1 - 1}$ of $x$ is in $A^\*$, and the suffix $w\_{i\_1} \cdot w\_{i\_1 + 1} \cdots w\_{i\_2} \cdot w\_{i\_2+1} \cdots w\_{i\_n} \cdot w\_{i\_n+1} \cdots w\_k$ of $x$ is in $(BA^\*)^\*$: every $w\_{i\_t}$ is in $B$, and every $w\_{i}$, for $i\notin \\{i\_t\\}\_{t\in\[n\]}$, is in $A$. Hence, $w\_{i\_t} \cdot w\_{i\_t+1} \cdots w\_{i\_{t + 1} - 1} \in BA^{i\_{t+1}-i\_{t} - 1}$ (for $t = n$, we let $i\_{n+1}$ refer to $k+1$).

---
Tags: formal-languages, automata, induction
---


# Question
Title: How to unscramble an RGB image 1024x1024
I have a colored image 1024x1024 whose rows and columns were randomly shifted, how would I unscramble it without having any information about the original image?

# Answer
> 0 votes
Adding some type of edge detection would likely help as well, otherwise all the edges would glom together as a mass. How you'd do that I do not know as pixels don't retain edge characteristics.

# Answer
> 1 votes
You can't. Information has been lost.

There might be heuristics to make a best-effort recovery effort, based on the observation that typically adjacent pixels tend to have similar values (the difference in pixel intensities between neighboring pixels tends to be small). So, you could try to solve an optimization problem to find the rearrangement that minimizes the sum of pixel intensity differences between all pairs of adjacent pixels. That might be a non-trivial optimization problem, I don't know.

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


title: Amortised cost - transferring tokens

text:
# Question
Title: Amortised cost - transferring tokens
I'm trying to solve a problem from one of the older exams.

Question:

> There's an infinite, one-dimensional board, with fields numbered consecutively $\ldots, -2, -1, 0, 1, 2, \ldots$ A move in the game consists of selecting a field and placing a token on it. If after placing the token it turns out that on two adjacent fields there are an equal number of tokens (at least one each), then we move all tokens from one of these fields to the other, clearing the first field and doubling the number of tokens on the second field. If there's a choice between two adjacent fields, we make that choice arbitrarily. Then we continue the described process of clearing the field and doubling the number of tokens on the adjacent field until there's not an equal number of tokens on two adjacent fields.

Example:

> Suppose that on fields numbered $1, 2, 3, 4, 5$ there are $0, 1, 2, 4, 6$ tokens respectively. After adding one token to the field numbered $1$, we get the following arrangement of tokens on the board: $0, 0, 0, 8, 6$. A basic move in the game involves placing or removing a token. Therefore, moving $k$ tokens from one field to another requires performing $k$ removal operations and $k$ placement operations on the board. Analyze the amortized cost of a single move in the game measured by the number of basic moves.

I think first part of the solution goes like this: Suppose there are $n$ tokens on the board. No token could be moved more than $\log n$ times because with each move, it would be on a stack twice as large, and the height of that stack would be greater than the total number of tokens. For example, if there are $8$ tokens on the board, then no token could be moved 4 times because it would be on a stack of height $16$. Hence, each token could be moved at most $\log n = \log 8 = 3$ times. Therefore, the cost is at most $\log n$.

What is the method to establish a lower bound?

# Answer
> 1 votes
To prove a lower bound simply take a worst case example. We will prove the following:

**Induction Hypothesis:** There exists a sequence of moves that results in $n$ tokens at position $\log n$ that requires at least $n \log n$ *place* and *remove* operations. For simplicity, assume that $n$ is some power of $2$, and $\log$ with base $2$.

**Base Case**: Let $n = 2$. Then, place a token at position $1$ and $2$, each. Total place and remove operations are $4 \> n \log n = 2$. Thus, the base case holds correctly.

**Induction Case**: Suppose there exits a sequence of moves that results in $n/2$ tokens at position $\log(n/2)$, which requires at least $(n/2) \log (n/2)$ operations.

Similarly, $n/2$ tokens can be obtained at position $\log(n/2)-1$ if the placement of tokens starts from index $0$. It also requires at least $(n/2) \log (n/2)$ operations.

Since the two sets are adjacent to each other, we move the tokens from position $\log n -1$ to position $\log n$. It requires $n$ remove and place operations.

Total operations are thus $\geq (n/2) \log (n/2) + (n/2) \log (n/2) + n = n \log n$. Hence, the induction hypothesis is holds.

---
Tags: algorithm-analysis, proof-techniques, amortized-analysis
---


title: NP-hardness of partitioning into k sets

text:
# Question
Title: NP-hardness of partitioning into k sets
Given a multiset $S$ of positive integers and a fixed positive integer $k$, can $S$ be partitioned into $k$ parts with equal sum?

For $k = 2$, this is the well-known Partition problem. For general $k$, this is described on Wikipedia as the "multiway number partitioning" problem, and it's claimed there that this problem is NP-hard for every fixed $k$. However, the reference provided there is not satisfactory because it is about a different problem. I also cannot find this problem in Garey and Johnson's "Computers and Intractability: A Guide to the Theory of NP-Completeness".

Is there a good reference for the NP-hardness of this problem?

# Answer
The reduction is simple, so you might not require a reference.

Given an instance for $k = 2$, simply add $p$ integers each of value $SUM/2$, where $SUM$ is the sum of all the elements in multiset $S$. The new instance has $k := p + 2$.

For $k = 2$, the $\mathsf{NP}$-hardness proof is already given on wiki.
> 1 votes

---
Tags: reference-request, partitions
---


# Question
Title: Is there a challenge with which one could reasonably show to have found a feasible polynomial algorithm for an NP problem?
Say there is someone claiming to have solved P vs NP, by finding a (computationally feasible, i.e. no huge constants) polynomial solution to a problem in NP:

Apart from a formal proof, is there any kind of challenge comparable to the RSA Numbers, which could be used to "prove" (or at least give strong evidence) that you have indeed found a polynomial solution to a NP problem?

\[For comparison: If I claim to have found a solution to FACTORING and present factors for RSA-2048, that might not actually prove my approach, but would make my attempt a lot more credible\]

# Answer
> 2 votes
You might consider the following instance of an NP-hard problem: Eternity II. This particular instance has been unsolved for more than 15 years, despite dozens of papers about it. Solving this problem would get significant attention, and if it comes with a claim of having a polynomial time algorithm for it, people would definitely be compelled to check it.

Beating the benchmarks in any NP-hard problem, say, on datasets for TSP, or Set Cover, would also be significant enough to draw attention to the new algorithm.

# Answer
> 1 votes
https://cgi.luddy.indiana.edu/~sabry/cnf.html

if you have a computationally-feasible program to solve SAT problems (NP-complete), but you don't know how to encode other problems into SAT, this website will encode factoring for you

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


title: Reduce CNF-SAT to decision problem

text:
# Question
Title: Reduce CNF-SAT to decision problem
Given CNF-SAT reduce it to the following decision problem:

Given `n` items, `m` groups (and for each group a set of items) and a parameter `k`. The problem outputs yes/no if there exists `k` or less groups such that every item is at least in one of the selected groups.

How can I reduce the CNF-SAT to this problem?

I get stuck when it comes to negative literals in the CNF-SAT. Because otherwise I could reduce it in the following way:

Each clause is a group and literals in the group are the items. parameter `k` is the number of clauses. If we find `k` or less groups that contain all literals, then they must be also contained in other clauses so we successfully reduced the CNF-SAT.

How can I incorporate negative literals in the reduction?

# Answer
It is not clear in your solution why treating clauses as groups helps. Note that a satisfying assignment should induce a set of groups and vice versa.

**Hint: a non direct reduction (but you can start from there):** Think about it as a covering problem. For example, it smells like the vertex-cover problem: each vertex $v$ defines a group of edges that touch $v$, and items can be the set of all edges.
> 2 votes

---
Tags: complexity-theory, reductions, satisfiability, decision-problem
---


title: Check if n-bit number is divisible by 7

text:
# Question
Title: Check if n-bit number is divisible by 7
Show how to check if n-bit number is divisible by 7 in logarithmic circuit depth.

How can I construct the circuit to be able to check the divisibility?

# Answer
$8^k \cdot x \mod 7 = x \mod 7$, therefore we can split the number into groups of three bits and add these groups.

Now you use a 3-2 adder: A 3-2 adder takes three n-bit inputs and creates one n-bit output and one n-bit shifted output with the same sum: This is just done by connecting all triples of three bits with a one-bit full adder.

Now if you add three 3-bit values with bit values 421, 421 and 421, and get two sums 421 and 842, then 8 mod 7 = 1, so you move the bit at index 3 to index 0, and you turned three 3-bit numbers into two 3-bit numbers with the same value modulo 7.

Say you have a 128 bit number. Split into 43 3 bit numbers. Add 3 numbers, 14 times in parallel, and you have 28+1 = 29 numbers. Then add 9 times 3 numbers, and get 20 numbers. Add 6 times 3 numbers, getting 14 numbers, then from 14 to 10, from 10 to 7, from 7 to 5, from 5 to 4, from 4 to 3, and finally from 3 to two 3-bit numbers.

That sum x+y is divisible by 7 if x xor y is all bits zero or all bits 1.
> 0 votes

---
Tags: circuits, arithmetic, binary
---


# Question
Title: Few lines of code to test whether a student will understand computer science
A couple of years ago, I read a story about a professor of computer science, who showed his first semester students a few lines of code with a simple questions. I think it was something along the lines of this:

```
a = 5
b = a
a = b + 5
c = a + b

What is c?

```

And this professor argued, that this simple test is in some sense surprisingly reliable to check, whether a first semester student will be good at computer science or not. Sadly I cannot find any reference to this story anymore online.

Does anybody know about this story? Is it true? What was the exact code?

I am really sorry, if this is the wrong site for this kind of questions. I looked at different StackExchange websites and this seemed to be the best fit for my question.

# Answer
You might be thinking of this paper:

Testing Programming Aptitude. Saeed Dehnadi. PPIG, 2006.

They used a quiz that contained questions like:

> Read the following statements and tick the box next to the correct answer in the next column.
>
> ```
> int a = 10;
> int b = 20;
> a = b;
> b = a;
>
> ```
>
> The new values of a and b are: \[...\]

Dehnadi reported very high success at predicting which students would be successful in an introductory CS course.

Others attempted to reproduce these results in other years and found less impressive results:

Mental models and programming aptitude. Michael E Caspersen, Jens Bennedsen, and Kasper Dalgaard Larsen. SIGCSE 2007.

Mental models, consistency and programming aptitude. Richard Bornat, Saeed Dehnadi, Simon. Australasian Computing Education, 2008.

For instance, Caspersen et al. found no correlation between quiz results and student success, and Bournat et al. reported that the approach "has failed to live up to that early promise". I am not an expert on this topic, but my impression is that the early reports have not panned out and do not appear to be correct.

There has been lots of other research on predicting student success in introductory CS courses, with mixed success.
> 4 votes

# Answer
This test shows that you have at some point in time programmed a computer in a procedural language or at least seen someone doing it. A mathematician from the 1920s might very well fail this test. That doesn’t mean they would have any problem learning either computer science or software development.
> 1 votes

---
Tags: algorithms
---


# Question
Title: What would be the consequences of TQBF having polynomial length winning instructions?
By the winning instruction I mean a string that a deterministic polynomial time Turing machine can use in order to win the opponent in a competitive game. The difference from a certificate is that the winning instruction does not have to prove its own correctness, you just trust it.

A naive winning instruction for TQBF would look like:

> If the opponent has assigned $y\_i=0$ then go to the line $a$, otherwise go to the line $b$.

The naive instruction would not be reusing the lines. I.e., say, it would say to go to line 2 if the opponent has assigned $y\_1=1$ and to line 3 otherwise. Then the line 2 would tell to go to line 4 if the opponent has assigned $y\_2=1$ and line 5 otherwise. Meanwhile, the line 3 would tell to go to lines 6 and 7 respectively. For $y\_3$ you'd need lines 8 to 15. So, the amount of lines doubles with each variable which means such an instruction would have an exponential size.

A simple complexity class that has polynomial size winning instructions is $\Sigma\_2^{\mathsf{FP}}$. Suppose a quantified boolean formula $\exists X\forall Y:\varphi(X,Y)$ is true. Then a partial assignment $p(X)$ that turns the formula into a tautology would be the winning instruction.

On the other hand, it seems that $\Pi\_2^{\mathsf{FP}}$ has no such winning instruction: there are exponentially many different formulas that could be produced by the opponent.

Now, suppose a formula $\exists X\ \text{Maj}(Y):\varphi(X,Y)$. Assuming it is true, the winning instruction would be a partial assignment $p(X)$ that produces a formula $\text{Maj}(Y):\varphi'(Y)=1$. This means that $\mathsf{FNP^{PP}}$ also has polynomial sized winning instructions.

However, there does not seem to be a similar construction for TQBF. It's clear that the existence of polynomial sized winning instructions is necessary for $\mathsf{PSPACE\subset NP}/poly$, however it seems far from sufficient.

So, there would be two questions here:

1. Is it an open problem whether TQBF has polynomial sized winning instructions?
2. If yes, then what would be the consequences of that?

# Answer
Most likely TQBF, and even 2QBF, has no winning instruction.

Let $f:\\{0,1\\}^\* \to \\{0,1\\}^\*$ be a one-way permutation (OWP). Though we have no proof, it is believed/conjectured that OWPs exist. In particular, under reasonable cryptographic assumptions, one can construct a OWP.

Now consider a formula of the form

$$\forall X \exists Y . f(Y)=X,$$

where $X,Y$ are boolean vectors of length $n$. This formula is true, since $f$ is a permutation on $\\{0,1\\}^n$; but there is no polynomial-length winning instruction (any such winning instruction would provide a polynomial-time algorithm to invert $f$, contradicting the assumption that $f$ is one-way).

This is not yet an instance of TQBF, because there is no guarantee that there is a concise boolean expression for $f$. But you can build a boolean circuit for $f$, and then use the Tseitin transform to construct a 3CNF formula $\varphi$ such that $f(Y)=X$ iff $\exists Z . \varphi(X,Y,Z)$.

Therefore, the formula

$$\forall X \exists Y \exists Z . \varphi(X,Y,Z)$$

has no winning instructions (under the assumption that $f$ is a OWP). This formula is in TQBF. In fact, since you can absorb $Y,Z$ into a single boolean vector $Y'=(Y,Z)$, it is in 2QBF, since it has the form $\forall X \exists Y' . \varphi(X,Y')$.

---

Or, another way to put it is that if TQBF has winning instructions, then one-way permutation do not exist.
> 1 votes

---
Tags: complexity-theory
---


# Question
Title: Could a compiler/static analysis infer the best abstract data type?
I initially brought this up on the Swift Forums, and it was suggested that this might be a thing better suited for CS SE. So here goes:

I had this thought that the compiler already has enough information to be able to infer an appropriate data structure to use given the rest of the usage patterns that follow. This sounds too hard and abstract when I put it into words (and I'm sure this is intractable in its full generality), but what I have in mind is more simple rules of thumb based substitutions. Like if I'm using a special "List" type that the compiler knows about, and the compiler sees that the bulk of what I'm doing are checking for element memberships, then it puts in a Set in the code it emits. Or if it sees that I'm doing a lot of prependings, then it uses a dequeue. And if it doesn't see me doing anything special (or if it can't infer what I'm doing), it falls back to using a regular array.

This sounds doable in my head using the similar sort of static analysis that compilers already do for other forms of program optimization. But based on the responses I got in the Swift forum, it seems I have vastly underestimating the difficulty of doing even a toy version of this with the sort of techniques compilers use today.

So my question here is twofold - Can compilers (theoretically) infer the best (from an available set) of concrete data types for use in a given program? This is not for picking from all possible data structures, it is a more narrow question of picking from say 3 or 4 alternative implementations, when the programmer specifies he's using a "generic linear sequence" (let's call it a List) type.

And is this prior art or research around this? I looked, but I'm not able to hit on the correct search term.

Thank you!

# Answer
If I understand your question correctly, you are asking whether the compiler can choose the implementation of a generic data structure, exactly how a programmer would define some variable to be a template in C++, and then specify how memory access and presence testing are carried out choosing the concrete implementation.

I think there are a few problems with the algorithm responsible for deciding which data structure to use:

1. correctness,
2. precision,
3. actual costs.

Concerning correctness, in the most general case, the problem could even be undecidable because the compiler would be forced to decide whether some branches can be reached. Consider the following (contrived, artificial) excerpt:

```
std::set<C> S;
unsigned long int r = ...;// A huge random natural number.
if (collatz(r)==1) {
  /* A huge number of insertions of sorted elements on S. */
} else {
  /* A huge number of removal of scattered elements on S. */
}

int collatz(unsinged long int r) {
  while (r!=1){
        if (r%2==1)
            ans=(3*r)+1;
        else
            r /= 2;
  }
  return 1;
}

```

Here I take advantage of Collatz's function, which is nowadays not known to always terminate for all inputs. In this situation, the compiler would be forced to determine which data structure to use depending on the content of the two branches. Here I am abstractly hinting that in the first branch, a list would suffice, in the second case a hashtable would be preferable. Since nobody has ever proved that `collatz` terminates for all naturals, this task will certainly be out of reach for the compiler.

Concerning precision, in my opinion, this shows that the compiler must make a guess and approximate. This could generate some software that behaves properly under some loads and improperly under others.

On the other hand, let's say we are happy with such an approximation and the compiler makes correct choices on practical input programs. In that case, I would ask why we should add this check in the compiler itself. It sounds to me like it should be a task more suited for a lint'er or a performance evaluation suite. This last observation helps me to cover the last point; the compiler must produce the output in finite time, and doing so while producing high-quality output is time-consuming. Here there a two cases: either the compiler has only one candidate or it has more; the only way to choose the best is to generate each solution and run it. Postponing the whole pipeline because the compiler must benchmark the source code for making the most efficient decision sounds strange to me, however, it is a possible strategy.

Last, but not least, it comes the problem of declaring new data structures the compiler could choose from. Let's say I devised a new data structure perfect for querying spatial data in some program of mine, how should I inform the compiler of its existence? How could the compiler state that a set is not efficient while my new structure would be preferable?

Concluding, I think there exists a strategy that achieves what you are asking, but I don't expect amusing results, especially in non-trivial programs/environments.
> 1 votes

# Answer
The problem is too ill-defined to admit a definite answer.

Can you construct some heuristics for a compiler to choose a data structure that might be suitable, with no guarantees? Sure, of course.

Can a compiler guarantee to select the data structure that will provide optimal performance? No, that is undecidable. For instance, consider code of the following rough form:

```
l = new List()
if (hard_to_predict()) {
    while (True) { ... operations on l that are best for a singly linked list ... }
} else {
    while (True) { ... operations on l that are best for an array ... }
}

```

Here `hard_to_predict()` might be anything -- it might even be as hard as the halting problem to predict at compile time whether it will return true or false.

I'm guessing that in practice we probably care about something in between those two extremes. For instance, maybe we want to know whether a compiler can perform reasonably well at this problem on common workloads, under some metric. Those kinds of engineering questions can probably only be answered experimentally, by trying to build such a scheme, and measuring how well it performs on a particular dataset of programs. They can't be answered based on theoretical considerations.

Will the benefits be worth the costs (implementation complexity of the compiler, unpredictability to the developer, the risks that the compiler makes a bad choice)? Unclear, and probably a matter of opinion.
> 0 votes

---
Tags: data-structures, compilers
---


# Question
Title: Number of n-variable symmetric boolean functions that are linear
How many symmetric boolean functions exist that are linear?
Let $f$ be a $n$-variable boolean function. $f$ is said to be symmetric if it is unchanged by any permutation of its variables, i.e. for 2-variable boolean functions $f$ is symmetric if $f(a,b) = f(b,a)$. In addition $f$ is called a linear function if it does not include second- or higher degree product terms in the ring sum normal form (RSNF). For example, a 2-variable function $g(x\_1, x\_2)$ is linear if the RSNF is of the form $$f(x\_1, x\_2) = c\_0 \oplus c\_1 x\_1 \oplus c\_2 x\_2$$
I found the number of symmetric functions as $2^{n+1}$ and the number of linear functions as $2^n$ but I'm not sure if the number of linear functions is correct.
How do I get the number of symmetric functions that are also linear?

# Answer
There are only 4 symmetric linear functions. You can easily show that you must have $c\_1=c\_2$ (otherwise $f(1,0,0,\dots,0)$ will be different from $f(0,1,0,\dots,0)$), and similarly, you must have $c\_1=c\_2=\cdots=c\_n$. $c\_0$ can be anything. Therefore, once you choose $c\_0$ and $c\_1$, the function is wholly determined.

You have some errors in your question. The number of linear functions is $2^{n+1}$. The number of symmetric functions is far higher than $2^{n+1}$.
> 1 votes

---
Tags: combinatorics, boolean-algebra
---


title: Concurrency in Operating System

text:
# Question
Title: Concurrency in Operating System
I had the following question in an exam:

Which of the following best describes the concept of concurrency in an operating system?

Options:

1. The ability to execute multiple programs simultaneously.
2. The ability to perform multiple I/O operations concurrently.
3. The ability to execute multiple threads simultaneously
4. The ability to allocate memory efficiently

The answer is given as **3**(which is correct) but could option **1** be an answer as well?

# Answer
Strictly speaking, no. You could have an OS that can run one application at a time only. It would be much less useful, but possible.
> 1 votes

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


# Question
Title: Is there a way to automate solving for coefficients in multivariable systems of equations?
I am trying to find a way to automate solving for **all** possible numerical values in a large multivariable system of equations. By this I mean equations such as

> k(90)\*g(-3)=434

and

> k(47)\*g(-5)=237

Essentially I want to solve for variables such as g and k in the context of one another and all the equations (the equations are much more complex - I am simplifying for clarity).

Is this a feasible approach and if so how would I go about achieving this? In addition, is this doable if I want the product value to be within a set number range? For example,

> k(47)\*g(-5)= a number from 217-257

If this is also doable, I am eager to hear it.

Apologies if I sound incoherent-- if any clarification is needed feel free to ask. Many thanks in advance.

Edited to add: These equations will all be either linear or quadratic in nature. I am looking for integer solutions preferably, but finding real number solutions would also work.

# Answer
> 1 votes
If we take the equalities from your example:

$$\begin{eqnarray\*} 90k - 3g & = & 434 \\ 47k - 5g & = & 237 \end{eqnarray\*}$$

Well, that's just a linear system, and can be solved by Gaussian elimination or other similar technique.

If we look at the inequalities:

$$\begin{eqnarray\*} 47k - 5g & \le & 257 \\ -47k + 5g & \le & 217 \\ \end{eqnarray\*}$$

That's a linear program. If you want integer solutions, then this is exactly the integer linear program feasibility problem, which is known to be NP-hard. For rational solutions, this is solvable in polynomial time, but in practice, the simplex method works extremely well.

If you have quadratic equality constraints, then Quadratic programming isn't quite what you want, because most of the algorithms for that only talk about quadratic objective functions, not equality constraints. Someone else might know better than I do on this point, but you may want to look into something like cylindrical algebraic decomposition, which in theory should work with any polynomials.

# Answer
> 0 votes
The problem is NP-hard, when you have quadratic constraints.

Solving over the reals: then your problem is an instance of quadratically constrained quadratic programming (QCQP), and you can find a single solution with a QCQP solver. Finding all solutions is challenging. One standard approach is to find one solution, then add a "blocking constraint" to rule out that one solution and solve again. For instance, if you have the single solution $x=13$, $y=15$, it might work to add the blocking constraint $(x-13)^2+(y-15)^2 \> 0$ to the system of equations, and solve it again. (This requires the solver to allow "$\>$" inequalities. If it only accepts "$\ge$" inequalities, one possibility is to try picking some small $\epsilon$, and require $\ge \epsilon$ instead of $\>0$, but this is a heuristic that is not guaranteed to work.) There might be better ways.

You could also try Groebner bases.

Solving over the integers: It appears it is undecidable whether there exists any solution over the integers. See https://math.stackexchange.com/a/616704/14578. I am not an expert in this area, so I can't independently confirm or refute that statement.

Standard warning: there might be exponentially many solutions, so if you really want to enumerate all solutions, then enumerating all of them can take exponential time in the worst case.

Related: Does Quadratically-Constrainted Quadratic Programming get easier if all constraints are equalities?, https://en.wikipedia.org/wiki/System\_of\_polynomial\_equations, Is deciding solvability of systems of quadratic equations with integer coefficients over the reals in NP?, https://math.stackexchange.com/q/2084636/14578, https://math.stackexchange.com/q/1366528/14578.

---
Tags: algorithms
---


# Question
Title: Find maximum length subarray whose bitwise AND is at least $k$ in $o(n^2)$
Given an array $A$ of unsigned integers, a subarray is a contiguous interval $A\[\ell\],\ldots,A\[r\]$. The *bitwise AND* of the subarray is just the bitwise AND of $A\[\ell\],\ldots,A\[r\]$ (what is denoted by `A[l] & ... & A[r]` in C).

I am faced with the following task:

> Given an array and an integer $k$, find the maximum length of a subarray whose bitwise AND is at least $k$.

The intended running time is $o(n^2)$, but I can only think of $O(n^2)$ solutions. How do I get below quadratic running time?

# Answer
Suppose that $A$ has length $n$, and let $m$ be the midpoint. Partition your array into two parts: $A\_1 = A\[1\],\ldots,A\[m\]$ and $A\_2 = A\[m+1\],\ldots,A\[n\]$. Any solution must either lie entirely in $A\_1$, entirely in $A\_2$, or must consist of a suffix of $A\_1$ and a prefix of $A\_2$. This suggests a recursive algorithm which recurses on $A\_1$ and on $A\_2$, and then needs to find the maximum length of a subarray AND'ing to at least $k$ which consists of a suffix of $A\_1$ and a prefix of $A\_2$.

For the latter task, we first compute the ANDs $$ A\[m\], A\[m-1\] \\& A\[m\], \ldots, A\[1\] \\& \cdots \\& A\[m\], $$ storing them aside. Now we find the first $i$ (if any) such that $A\[i\] \\& \cdots \\& A\[m\] \geq k$. We find the maximum $j \geq m$ such that $A\[i\] \\& \cdots \\& A\[j\] \geq k$. This gives us a candidate subarray. Now we increment $i$, and advance $j$ to the maximum position satisfying $A\[i\] \\& \cdots \\& A\[j\] \geq k$, giving us another candidate; here we are crucially using the property $x \\& y \leq x$, which guarantees that the maximal $j$ is a monotone function of $i$. We continue incrementing $i$ in this way until we have processed $i = m$. At this point, we have checked all maximum length subarrays straddling the midpoint $m$.

This divide-and-conquer algorithm runs in $O(n\log n)$.
> 1 votes

# Answer
Keep track of the and of a0 to a3, a4 to a7, a8 to a11 etc, a0 to a7, a8 to a15 etc, a0 to a15, a16 to a31 etc. This lets you calculate the and of any subarray in O(log n).

Find the first a(I) \>= k. Find the largest j such that the and of a(I) to a(j) is \>= k. This may be optimal. If a(j) \< k then look for the next a(I) \> k and try again.

If a(j) \>= k then use your tables to find the smallest a(I) making the and \>= k. This takes O(log (j-i)) time only. As an optimisation you can skip this step if a(j) and a(j+1) \< k because you can’t get a subranges longer than the previous longest one.
> 0 votes

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


# Question
Title: Help understanding the proof that $L = \{ \langle M \rangle \mid M \text{ is a TM that accepts the input string } 101\}$ is undecidable
I understand of the existence of Rice's Theorem, however, I want to understand better how this reduction is formed. My professor gives the answer as follows:

"By contradiction, assume that $L$ is decidable and let $D$ be a decider for $L$. Then construct the TM $S$ such that $S$ decides the Halting Problem as follows:

(I gave a picture instead of typing since he uses a special $\LaTeX$ environment, if I need to change this please let me know.)

**My questions/concerns**:

1. How *exactly* does the construction of $S$ relate to the original language $L$? I am having a hard time seeing how we are actually deciding the Halting Problem...
2. The construction of $M\_x$ says "If $M$ halts, then $M\_x$ accepts $x$." This seems like circular reasoning or a contradiction in and of itself. How can we say "If $M$ halts..." when the question of a TM halting is undecidable?
3. The "on input $x$" seems arbitrary to me; it feels like we are just waving our hands.

# Answer
As you know, a Turing reduction from $L\_1$ to $L\_2$ (i.e. $L\_1 \leq\_T L\_2$) means that if we can decide $L\_2$, then we can also decide $L\_1$. In general to show $L\_1 \leq\_T L\_2$, we construct a machine $T$ such that $T$ decides $L\_1$ and $T$ is permitted to query $L\_2$. Being permitted to query $L\_2$ means that $\forall w \in \Sigma^\*$, $T$ can determine if $w \in L\_2$ or $w \notin L\_2$ (while $T$ is running) by asking an "oracle" whether or not $w$ is in $L\_2$. Understanding how querying a language is accomplished on the tape is not necessary for understanding the reduction at a high level, but I would encourage you to look into it.

In your case, we're showing that $HALT\_{TM} \leq\_T L$ by constructing the machine $S$ such that $S$ decides $HALT\_{TM}$ and $S$ is permitted to query $L$. This is how $S$ relates to $L$: $S$ queries $L$ (i.e. $S$ asks whether or not a string is in $L$, specifically in step $2$ of the provided pseudocode). An oracle is not a Turing machine, but a decider can be used to simulate an oracle because all questions about whether or not a string $w$ is in a given language can be answered by simply running the decider for that language on $w$. So in $S$, the decider, $D$, for $L$ is playing the role of the oracle (more specifically, $D$ is how $S$ queries $L$).

Now we just need to show that $S$ decides $HALT\_{TM}$. $S$ takes in input $\langle M, w \rangle \in \Sigma^\*$, which we understand to be the code of the machine $M$ and a string $w$. Recall that $S$ must determine whether or not $M$ halts on $w$.

$S$ starts by constructing a machine $M\_x$. You stated that "on input $x$" in the definition of $M\_x$ seems arbitrary and that's because it is. We're defining the behavior of $M\_x$ when taking in any input $x \in \Sigma^\*$. What's probably a little confusing is that $x$ is being used to denote the variable input string and in the name of the machine ($M\_x$) but these have no relation. To address your second question regarding the condition "if $M$ halts on $w$", I will note that we are not deciding if $M$ halts on $w$ or not. $M\_x$ is running/simulating $M$ on $w$, and if $M$ happens to halt on $w$ while $M\_x$ is running $M$ on $w$, then $M\_x$ behaves accordingly as described in the pseudocode. This seems reasonable as $HALT\_{TM}$ is recognizable. If $M$ does not halt on $w$, then $M\_x$ will not halt either because it will run $M$ on $w$ and wait for $M$ to halt on $w$ forever. It's important to note that $M\_x$ is not determining that $M$ does not halt on $w$ and not halting in response to this but rather $M\_x$ is not halting because it is running $M$ on $w$ until $M$ halts on $w$, however, $M$ never halts on $w$. We will now briefly prove the following lemma:

**Lemma:** If $\langle M, w \rangle \in HALT\_{TM}$, then $M\_x$ accepts all input strings (including $101$), and if $\langle M, w \rangle \notin HALT\_{TM}$, then $M\_x$ does not halt on any input strings and therefore does not accept any input strings (including $101$).

Consider $x \in \Sigma^\*$. First suppose $\langle M, w \rangle \in HALT\_{TM}$. Since $M$ halts on $w$, $M\_x$ accepts $x$ by the definition of $M\_x$. Moreover, because $M\_x$ does the same thing, regardless of its input, we know that $M\_x$ accepts all inputs. Now suppose $\langle M, w \rangle \notin HALT\_{TM}$. Since $M\_x$ runs $M$ on $w$ until $M$ halts on $w$ and we've assumed $M$ never halts on $w$, $M\_x$ runs forever/does not halt and therefore does not accept $x$. Once again, since $M\_x$ always runs $M$ on $w$, regardless of its input, we know that $M\_x$ does not halt on all inputs and therefore does not accept any inputs.

With this in mind, we can now show that $S$ decides $HALT\_{TM}$. Consider the following two cases:

1. $\langle M, w \rangle \in HALT\_{TM}$. By our lemma, $M\_x$ accepts all input strings (including $101$), which means $\langle M\_x \rangle \in L$. Since $D$ decides $L$, $D$ accepts $\langle M\_x \rangle$, so by step $2$ of the pseudocode, $S$ accepts $\langle M, w \rangle$.
2. $\langle M, w \rangle \notin HALT\_{TM}$. By our lemma, $M\_x$ does not halt on any input strings and does not accept any input strings (including $101$), which means $\langle M\_x \rangle \notin L$. Since $D$ decides $L$, $D$ rejects $\langle M\_x \rangle$, so by step $2$ of the pseudocode, $S$ rejects $\langle M, w \rangle$.

Thus, if $\langle M, w \rangle \in HALT\_{TM}$ then $S$ accepts $\langle M, w \rangle$, and if $\langle M, w \rangle \notin HALT\_{TM}$, then $S$ rejects $\langle M, w \rangle$. Putting these together, we have that $S$ decides $HALT\_{TM}$ and $HALT\_{TM} \leq\_T L$. Thus, if $L$ is decidable, then $HALT\_{TM}$ would be decidable.
> 1 votes

# Answer
1. Fix $\langle M, w\rangle$, and consider the constructed machine $M\_x$. It is not hard to see by the construction of $M\_x$ that either $M\_x$ accepts all its inputs (and that happens when $M$ halts on $w$), or $M\_x$ does not halt on all its inputs (and that happens when $M$ does not halt on $w$). So $M\_x$ behaves on all its inputs the same way, depending on what happens in the run of $M$ on $w$. Hence, to understand how $M\_x$ behaves, it is sufficient to consider its behaviour on the input $101$, but we can do that through the decider machine $D$. Thats why we have the check in item 2, and the magic here is that $D$ halts on $\langle M\_x \rangle$ as it is a decider TM, and therefore, $S$ is also a decider. So in total we get that, $D$ accepts $\langle M\_x \rangle$ iff $M\_x$ accepts the input $ 101$ iff $M\_x$ accepts all its input (as $M\_x$ behaves the same on all inputs) iff $M$ halts on $w$ (by the construction of $M\_x$). So we got in total that $S$ decides the halting problem.

**Note:** The machine $S$ never simulates the run of $M$ on $w$, it produces a description of a machine $M\_x$ that does that, and then simulates the run of $D$ on $\langle M\_x\rangle$ and halts.

2. Note that if $M$ does not halt on $w$, then $M\_x$ does not halt as well. So $M\_x$ is not deciding the halting problem, it just simulates the run of $M$ on $w$ and waits for $M$ to accept $w$, and in fact it can wait forever and not halt at all. So its not a contradiction as we are here kinda semi-deciding the halting problem and not deciding it.
3. Its not arbitrary, its how $M\_x$ works. It does the same thing regardless of the input $x$, and so we can write "on input $x$, do blah blah blah" -- meaning on any input $x$, we behave the same way.
> 1 votes

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


# Question
Title: Free variable in the programming language
From the wikipedia of Free variables and bound variables

> In computer programming, the term free variable refers to variables used in a function that are neither local variables nor parameters of that function. The term non-local variable is often a synonym in this context.

Since local variables and parameters are **bound** to *particular invocation* of the function. Can we say only global variables are the free variables?

# Answer
> Can we say only global variables are the free variables?

No.

Counterexample in ECMAScript:

```
function outerFn() {
  const outerVar = "Outer";

  function innerFn() {
    return outerVar;
  }

  // Could also be written:
  const innerFn2 = () => outerVar;

  return innerFn();
}

console.log(outerFn());

```

Counterexample in Python:

```
def outer_fn():
    outer_var = "Outer"

    def inner_fn():
        return outer_var

    return inner_fn()

print(outer_fn())

```

Counterexample in Ruby:

```
def outer_method
  outer_var = "Outer"

  inner_lambda = -> () { outer_var }

  inner_lambda.()
end

puts outer_method

```

Counterexample in Scala:

```
def outerMethod =
  val outerVar = "Outer"

  def innerFn = outerVar

  innerFn

println(outerMethod)

```

Counterexample in Java:

```
public class FreeVariablesInJava {
    static String outerMethod() {
      var outerVar = "Outer";

      java.util.function.Supplier<String> innerFn = () -> outerVar;

     return innerFn.get();
    }

    public static void main(String args[]) {
      System.out.println(outerMethod());
    }
}

```
> 2 votes

---
Tags: functional-programming, variable-binding
---


# Question
Title: Find max of all trees resulting from single edge removal in generic tree in linear time
Given a generic tree with $n$ weighted nodes, there are $n-1$ edges. Removing any of the edges will partition the tree into two distinct trees, hence we can construct $2(n-1)$ possible trees in this way. Is there a way to find the node with the maximum value in each of these resulting trees, that is all the $2(n-1)$ values in $O(n$) time?

# Answer
Let's assume that nodes have a field maxvalue that gives the value of the largest node of the subtree in which it is the root. Now we can define a function as follows:

```
foo(tree t):
    //Lets assume t has fields t.maxvalue and t.secondmaxvalue
    t.maxvalue=valueof(t)
    for all children tchild of t do:
        temp=foo(tchild)
        if(temp>t.maxvalue):
            t.maxvalue=temp
        else if(temp>t.secondmaxvalue):
            t.secondmaxvalue=temp
        //the idea is that t.maxvalue will contain the value of the largest child of t and t.secondmaxvalue will contain the value of the second largest child of t.
    return t.maxvalue

```

We define other function as follows (assume `root` is the root of the entire tree):

```
foo2(tree t):
    for all children tchild of t do:
        if(t.maxvalue==root.maxvalue):
            print("if we disconnect the tree at (t,tchild) then we will get two trees with max node values as root.maxvalue and root.secondmaxvalue")
        else:
            print("if we disconnect the tree at (t,tchild) then we will get two trees with max nodes values as t.maxvalue and root.maxvalue")

```

Now we first call `foo(root)` and then `foo2(root)`. Both the two functions traverse each node exactly once and hence have linear time.
> 0 votes

# Answer
Yes.

Fix an arbitrary `root` of your tree. Then perform a DFS where you compute for each node, what is the maximum value on its subtree (including itself):

```
function max_value_on_subtree(node, parent = NIL):
    node.max_value = node.value

    for neighbor in node.neighbors:
        if neighbor == parent:
            continue

        subtree_max_value = max_value_on_subtree(neighbor, node)
        node.max_value = max(node.max_value, subtree_max_value)

# Call the function from the `root` (an arbitrary node) to populate the tree.
max_value_on_subtree(root)

```

In the next step, we want to compute the max value on the trees on both sides of the edge for every edge. We will do this in a separate DFS, where we maintain what is the maximum value among all nodes outside of the subtree we are currently looking in the DFS step. Before traversing an edge, we should compute the maximum value outside of the new subtree, which is the current maximum value, or the maximum on the subtrees from the current node we are inspecting other than the subtree we are stepping into. We build a prefix and sufix table with the max values, to make this computation in $O(1)$

```
function iter_max_values(node, parent = NIL, max_complement = -inf):
    """
    node: Is the current node on the DFS
    parent: The previous node. We keep it to avoid traversing from node to parent
    max_complement: The maximum value on the complement of the subtree with root at `node`
    """

    # Store a list with all the children. The parent is a
    # neighbor of the current node, but it is not a child.
    children = []
    for neighbor in node.neighbors:
        if neighbor != parent:
            children.push(neighbor)

    # Compute the maximum value for every prefix and suffix
    num_children = len(children)
    prefix = list(len = num_children)
    suffix = list(len = num_children)

    # For the sake of brevity, assume indexing out index return `-inf`
    for i in [0, num_children - 1]:
        child_max_value = children[i].max_value
        prefix[i] = max(child_max_value, prefix[i - 1])

    # Loop backward.
    for i in [num_children - 1, 0]:
        child_max_value = children[i].max_value
        suffix[i] = max(child_max_value, suffix[i + 1])

    # Iterate through every child, and before traversing the edge
    # toward the children compute the new max_complement
    for i in [0, num_children - 1]:

        # Again, for brevity, assume indexing outside of index returns -inf.
        new_max_complement = max(max_complement,
                                 node.max_value,
                                 prefix[i - 1],
                                 suffix[i + 1])

        # Before traversing the edge, we have the new max values
        # on both subtrees to the side of this edge.
        # A = new_max_complement
        # B = children[i].max_value
        # In this step, you can operate on them.

        iter_max_values(children[i], node, new_max_complement)

iter_max_values(root)

```

Notice each step of the DFS take $O(|children|)$ time (including computing prefix / suffix / new\_max\_complement) so overall it takes $O(N)$
> 0 votes

---
Tags: algorithms, graphs
---


# Question
Title: Big number of false positives in binary classification
I am fine-tuning the inception-v3 network(pretrained on ILSVRC) of tensorflow in a binary classification problem. I want to recognize if an image contains food or not. My dataset is imbalanced, the non-food class contains 5 times more images than the food class. I read that in an imbalanced dataset, I should train the network with balanced batches to get right results. So I split the dominant class in 5 splits and when I have to train the network for 50000 iterations I am changing the split every 10000 iterations, so that the batches that are passed to the training are balanced with food and non-food. I am testing the network in a balanced test-set. From the first 5000 iterations I am getting high accuracy in the food images, but the non-food class gives me imbalanced accuracy. I can receive high accuracy in the beginning and then it will be low. By accuracy I mean (number of rightly predicted food) / (number of food) for the food class and respectively for the non-food. Generally the network learns the food characteristics because the softmax can output non-food for a food image, but the localization of food would be right using the weights of food (I made test). To sum up, the network is probably overfitted but I don't know yet. Any ideas of what might be happening?

# Answer
It's hard to know, from just the information you've given us. It could be any number of things: overfitting, insufficient training data, class imbalance, or something else. The first step is probably to figure out the source of the problem, then you can explore the solutions.

There are standard diagnostics to check for overfitting (cross-validation, comparing accuracy on the validation set to accuracy on the training set, etc.). I'd suggest you use them to diagnose whether the network seems to be overfitting. There are many ways to combat overfitting: regularization, early-stop training, dropout, etc.

There are also ways to check if the problem is that you just don't have enough training data. For instance, you can take different-size subsets of your training set (10K, 20K, 30K, 40K, 50K) and plot how accuracy depends on the size of the training set. If accuracy seems to be gradually improving as training set size increases and doesn't appear to have reached a plateau yet, that's a suggestion that obtaining more training data might be useful.

Finally, class imbalance might be a factor. When you have 5 times as many non-food instances as food instances, that's call class imbalance. There's lots written on that subject and many techniques (undersampling the minority class, oversampling the majority class, using class weights, adjusting the threshold for classification, and more). I suggest you do some reading about that topic. It's not necessarily true that you need to train on a training set with balanced classes; that's one strategy, but it's not the only one, and it may not be optimal.

Hopefully this will help you narrow down what might be going on and then ask a more focused question.
> 1 votes

# Answer
The neural network you're building in Tensorflow does not predict categories. The neural network gives predictions on a continuum. It is then up to you to decide what you want to do with those predictions. Often, the predictions are in the range $\[0,1\]$ and can be interpreted as probabilities of membership in one of the classes, typically the minority category (but it depends on the exact way you have coded the problem). A common decision rule for those predictions on $\[0,1\]$ is to predict one category if the prediction is below $0.5$ and the other category otherwise. However, you do not have to use this decision rule. Indeed, receiver-operator characteristic and precision-recall curves exist by varying that threshold and not just using the software default of $0.5$.

There are reasons to evaluate the raw outputs of the model \[1, 2\], but if you don't want to use the arguably hard-to-interpret measures of performance like log loss and Brier score that are discussed in the links, favoring easy-to-interpret measures like accuracy, you're at least allowed to vary the decision rule and see if your two-stage pipeline of model predictions followed by a classification based on those model predictions yields better classifications than the software-default decision rule. You can even do this without having to worry about the class imbalance giving all majority-class classifications, since you vary the threshold and can have a very low threshold that gives many (even all) minority-class classifications.

You might, for instance, write a loop over all values $\left\\{0, 0.001, 0.002,\dots, 0.998, 0.999, 1\right\\}$ and plot various classification metrics at the various thresholds in that set of thresholds. My suspicion is that you have gotten poor classification results due to using a software-default threshold of $0.5$ and that you will get better performance with a lower threshold.
> 1 votes

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


# Question
Title: Impact of label flipping on ROC-AUC score
I was exploring a problem of label flipping in the target column:

**Problem:** I have a data frame with just two columns: *Predicted probability* | *Target*. *Target* column is binary (contains only 0 and 1) --- the actual target values. *Predicted probability* column contains outputs from my model. I calculate the ROC-AUC metric based on these two columns and, let's say, I have ROC-AUC = $a\_1$.

Next, I flip some zeros in the *Target* column to ones, and I measure the ROC-AUC again, and I get value $a\_2$ now. And $a\_2 \< a\_1$.

---

**Question**: What should be the distribution of positions of flipped labels, with which the second ROC-AUC (after flipping 0 to 1) is lower than the initial ROC-AUC?

I know that it is just a particular case, but in my problem, it would be sufficient to understand only the case when the ROC curve after flips lies completely under the ROC curve before flips. So, make assumptions, under which the ROC curve after flipping lies below the initial ROC curve.

For example, I am looking for something like (dummy statement):

* *For each threshold (which corresponds to a point on the ROC curve) I want to have the number of flips to the right (*here and further I assume that data frame is sorted by predicted probabilities and leftmost is the lowest one*) of this threshold to be greater than the number of initial ones to the right of the threshold*

---

Now, what I tried to do is:

1. Let's say I have a point on the initial curve $(p\_0, p\_1) = (\frac{x}{X}, \frac{y}{Y})$. This point corresponds to the threshold $t$ and $x$ is the number of zeros to the right of $t$, $X$ -- the total number of zeros in *Target* before flipping ($y, Y$ are the same but for ones). Then after all the flips this point, obviously, changes its coordinates. New coordinates will be $(\frac{x-c^r}{X - C}, \frac{y+c^r}{Y+c^r+c^l})$, where $C$ -- is the total number of flips, $c^r$ -- number of flips to the right of threshold $t$, $c^l$ -- to the left.
2. I want this new point to be under the initial ROC curve. So for the new first coordinate, second coordinate should be less than coordinate of the point on a blue curve. Namely, $\frac{y+c^r}{Y+c^r+c^l} \< \frac{?}{Y}$. Where $\frac{?}{Y}$ is the point on a blue curve with first coordinate equal to $\frac{x-c^r}{X - C}$.
3. I have no idea how to find $?$ in the numerator.

Any help will be really appreciated.

# Answer
> 0 votes
I don't think this should be a surprise.

You fit your model on the original labels, and while you (probably) did not optimize the ROCAUC in the model training, many measures of model performance are at least roughly associated with ROCAUC.

This is to say that the predictions are as good as the model can get for the true labels.

Then you go and change the rules by switching some of the categories. "Well if I knew that was a $1$ then I would have made a different regression equation with different predictions," the model must be thinking. When you change the rules, I find it predictable that the model does not do as well.

---
Tags: machine-learning, statistics, performance
---


# Question
Title: What do we know about the asymptotic proportion of "easy" instances of NP-complete problems
In practice, it seems that many NP-hard problems "usually" lead to easy instances, in the sense that a commercial solver can handle them reasonably. A few past questions on this topic (see here and here) have been answered by saying they are not well-posed

Here's a shot at a asking a question which might have a non-trivial answer:

> Suppose $P \neq NP$ (or assume something stronger like ETH). For each $n$, let $S\_n$ be a set of 3SAT instances of size $n$. Additionally, suppose the the number of positive instances and negative instances in $S\_n$ is equal. What is the maximum growth rate $|S\_n|$ can have while the language $\bigcup\_n S\_n$ is still polynomial time decidable.

Is this version of the question also trivial? If not, what work has been done on it?

Another question: What other ways of formalizing easy/hard instances are available, and what progress has been made on analyzing them?

# Answer
Unfortunately, I don't think this way of formalizing the problem is going to lead to much insight.

The practical experience you are referring to has to be a consequence of something about the distribution of instances seen in practice: that "not-too-hard" instances are common in practice, in the settings where commercial solvers often work. I don't know how to formalize that, as it seems dependent in non-trivial ways on those particular application settings.

For your specific problem, under reasonable assumptions, the maximum growth rate is basically polynomial. If $|S\_n|$ grows polynomially quickly, then the promise problem can be solved in polynomial time, in non-uniform models of complexity (e.g., P/poly).

Conversely, we can generate sets $|S\_n|$ that grow a bit faster than polynomial, and where heuristically we do not expect any way to solve it in polynomial time. Consider the problem of breaking cryptography, and specifically, recovering the key to a block cipher given a few random known-plaintext pairs. Concretely, each positive instance is obtained by randomly picking a key $k$ and random values $x\_1,\dots,x\_m$, letting $y\_i=E\_k(x\_i)$, and then creating a 3SAT formula $\varphi(t)$ that evaluates to true if $E\_t(x\_i)=y\_i$ for all $i$, i.e., if $t$ is a key that encrypts each $x\_i$ to $y\_i$. (This can be done by applying the Tseitin transform to the boolean circuit that tests if $t$ is the desired key.) Each negative instance is obtained by picking random values $x\_1,\dots,x\_m,y\_1,\dots,y\_m$, and creating a 3SAT formula $\varphi(t)$ that evaluates to true if $E\_t(x\_i)=y\_i$ for all $i$. We know that all the positive instances are satisfiable. Heuristically, the negative instances are all unsatisfiable. Moreover, under standard cryptographic assumptions (that the block cipher $E$ is secure), no polynomial-time algorithm can distinguish between positive vs negative instances with non-negligible advantage. (Roughly speaking, no polynomial-time algorithm can do better than random guessing.) Therefore, if you define $S\_n$ by sampling some super-polynomial number of positive instances and some super-polynomial number of negative instances, no polynomial-time algorithm will decide this promise problem with good probability (any such algorithm could be turned into an attack on the block cipher that is faster than exhaustive keysearch).

In other words, $|S\_n|$ only needs to grow slightly faster than polynomial, and the problem can already be hard.

This argument relies on the assumption that we have blockciphers where there is no attack faster than exhaustive keysearch. That is not proven; it is a conjecture. But based on our experience with cryptography so far, it seems like a pretty plausible guess. In any case, it means that for a solver to do well on all problem subclasses where $|S\_n|$ grows even slightly faster than superpolynomial, would represent a major advance in attacking block ciphers. So we shouldn't reasonably expect existing solvers to achieve such a level of performance.
> 3 votes

---
Tags: np-complete
---


# Question
Title: Resources for studying the mathematical foundations of machine learning, for someone from a math/physics background
I am a soon-to-be physics graduate student with a background in theoretical and experimental cosmology. In my work, I've often found myself applying machine learning models and techniques for the purposes of performing data analysis tasks. I, as many do, find the field to be fascinating, but have little more than a superficial, very applied understanding. I know how to throw a simple neural network together with TensorFlow & Keras (and understand the mechanics of how the actual computations are performed), but have little understanding of *why* a neural network is able to achieve what it does, *why* deep neural networks perform better than their shallow counterparts, *why* Google tells me that certain convolutional kernel sizes are more likely to perform well, etc. in the way that I am used to in mathematics and physical science. In these fields (and this is, of course, a gross generalization) there is an expectation of proof and some more intuitive level of understanding.

I've tried studying from various online courses and textbooks, and all take a very applied, engineering-y approach that really bothers me. I'm aware that machine learning is, in fact, largely an engineering field, and that there is a lot we simply don't understand yet. I would assume, however, that there must be at least some very, more math-y elementary understanding of the field.

It was previously suggested to me that I should look into the field of "Statistical Learning". I purchased Hastie and Tibshirani's text, and have nearly completed the companion online course. I found it to be more satisfactory in that they provide a statistician's mathematical perspective, and oftentimes I could search around about the topics discussed to learn a bit more about why they work in the way that they do, and sometimes even find proofs for certain claims.

I'm looking for additional resources that attempt to explain the why and how behind machine learning, that might be more appealing to someone from a math and physics background. I am specifically interested in neural networks and their training. I know that this is a bit vague and, due perhaps in large part to my limited understanding of the field, I don't know what precisely I'm really looking for. There is a plethora of textbooks and online learning content available for those interested in machine learning, but seemingly few that discuss it at a depth I would find satisfactory. What textbooks/online courses/etc. might I use to move on from here?

# Answer
> 10 votes
Your assumptions may be a little bit off. Deep learning is largely an engineering field, and it is a young and rapidly moving one. Most "why" questions don't have very good answers. To the extent that there are partial answers to the "why" questions, mostly they are found in research papers, and I'm not sure whether they've made it into any textbooks yet. There are a lot of papers on the theory of deep learning, but (in my personal opinion) they mostly haven't been very successful on shedding light on the practical engineering practice of deep learning used in the field. If you come from a mathematics background, you might find it unsatisfying.

Generally, those who come from the field of statistics tend to have more of an emphasis on "why?" and principled foundations and mathematics and provable guarantees, which you might find more satisfying. Those who come from the field of machine learning often tend to have more of an emphasis on engineering and whatever works. See, e.g., Statistical Modeling: The Two Cultures (by Leo Breiman) and https://stats.stackexchange.com/q/6/2921. So I agree that you might find it helpful to study statistics. For instance, you might enjoy learning about logistic regression, which has solid theory underpinning it.

But if you want to study neural networks, be prepared that neural networks came from the ML culture, not the statistics culture, so you might not find what you are wishing for.

I would still suggest that you read standard textbooks and resources on deep learning. Start with the fundamental concepts and ideas everyone else is learning. Then you can search for theoretical explanations where they exist. For instance, I've heard a lot of good feedback on Deep Learning by Goodfellow, Bengio, and Courville, and that has some mathematical and theoretical background.

# Answer
> 3 votes
I was in an ML talk recently, where the speaker talked about how theory of ML has completely failed to explain much of anything that we do in practice.

Take, as one simple example, stochastic gradient descent. Would sampling with or without replacement converge faster? Empirically, the community has known that without replacement sampling outperforms with replacement sampling for many years. Yet this hunch (with standard assumptions) was only proved in 2019. This should serve as an example to demonstrate that theory lags behind engineering.

With that said, if you're interested in theory of machine learning, I recommend the book Understanding Machine Learning as it has a focus on mathematical rigor, and is a good resource for PAC learning.

# Answer
> 0 votes
The resource that helped me the most in understanding the math behind deep learning is the excellent book "Neural networks and deep learning" by Michael Nielsen, which is available online for free (legally).

---
Tags: machine-learning, neural-networks, mathematical-foundations, books
---


# Question
Title: Is this correct Context free grammar(CFG) for these two languages?
Question 1: L = { 0^n 1^n | n \> 0 } My answer = S -\> 0 S 1 | 10

Question 2: L = { 101^n0^2n | n \> 0 } My answer = S -\> 101 S 00 | 100

Can anyone correct this if there is any issue with this CFG?

# Answer
> 0 votes
First one seems correct. Second one is wrong because n \> 0 so there must be at least two 1s in the string. The string 100 can't be derived from S. You need to add another non-terminal, say T such that T derives 1T00 or the empty string and S derives 101T00.

---
Tags: automata, finite-automata, context-free, pushdown-automata
---


# Question
Title: Using time hierarchy theorem to show $Time(n^7)$ strictly contained in P
I'm relatively new to computational complexity and am trying to use the time hierarchy theorem to show that $Time(n^7)$ is strictly contained in P. I understand that the time hierarchy theorem says that if the limit as n tends to infinity of $\frac{T\_1(n)}{T\_2(n)}=0$ then $Time(T\_1(n))$ is strictly contained in $Time(T\_2(n))^2$. It seems obvious to me that this implies the desired result because for any number $x$ greater than 7, $Time(n^7)$ will be strictly contained in $Time(n^{2x})$ and then P is the union over all such time complexity classes. Could anyone help with how I might write this more formally? Is it necessary to assume the existence of some language in $Time(n^{16})$ for example? I feel like I might be missing something because it just seems clear to me, any help is much appreciated.

# Answer
By the time hierarchy theorem, if $f$ and $g$ are time-constructible functions and $f(n) \log f(n) = o(g(n))$ then $\mathsf{DTIME}( f(n) ) \subsetneq \mathsf{DTIME}(g(n))$.

From your question you seem to be using the following weaker for of the theorem: if $f$ and $h$ are time-constructible and $f(n) = o(h(n))$ then $\mathsf{DTIME}( f(n) ) \subsetneq \mathsf{DTIME}( h(n)^2 )$. This follows from the previous statement by choosing $g(n)=h(n)^2$ and noticing that $f(n) \log f(n) = O(f(n)^2) = o(h(n)^2)$. I will therefore use this latter version.

Choosing $f(n) = n^7$ and $h(n) = n^8$: $$ \mathsf{DTIME}( n^7 ) \subsetneq \mathsf{DTIME}( n^{16} ) \subseteq \bigcup\_{k \in \mathbb{N}} \mathsf{DTIME}(n^k)=\mathsf{P}. $$
> 1 votes

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


# Question
Title: PAC-learning framework: Why the sample size must also be polynomial if the full sample is received by the algorithm
On page 11 in the book *Foundation of Machine Learning*, 2nd edition MIT press, the authors wrote:

> Definition 2.3 (PAC-learning) A concept class $C$ is said to be PAC-learnable if there exists an algorithm $A$ and a polynomial function $poly(·,·,·,·)$ such that for any $ε \> 0$ and $δ \> 0$, for all distributions $D$ on $X$ and for any target concept $c ∈ C$, the following holds for any sample size m ≥ poly(1/ε, 1/δ, n, size(c)): $P\[R(h\_{S}) \le \epsilon\] \ge 1−\delta$, $S\sim D\_{m}$. (2.4)

The authors further explained:

> If A further runs in $poly(1/ε, 1/δ, n, size(c))$, then C is said to be efficiently PAC- learnable. When such an algorithm A exists, it is called a PAC-learning algorithm for C.
>
> A concept class *C* is thus PAC-learnable if the hypothesis returned by the algorithm after observing a number of points polynomial in $1/ε$ and $1/δ$ is approximately correct (error at most ε) with high probability (at least 1 − δ), which justifies the PAC terminology. The parameter δ \> 0 is used to define the confidence 1 − δ and ε \> 0 the accuracy 1 − ε.

Which I can understand. However, I couldn't understand when they wrote:

> Note that if the running time of the algorithm is polynomial in 1/ε and 1/δ, then the sample size m must also be polynomial if the full sample is received by the algorithm.

Could anyone help to explain why the sample size m must also be polynomial if the full sample is received by the algorithm if the running time is polynomial in 1/ε and 1/δ?

# Answer
> 1 votes
The assumption is that the algorithm must read in data (given that the full sample is received) thus it is $\Omega(m)$. So, if $m$ is not polynomial, there is no way for the algorithm to be polytime as well.

---
Tags: machine-learning
---


# Question
Title: Question about the proof for the sample complexity of axis-aligned rectangles
The classical proof for the sample complexity of the hypothesis class of axis-aligned rectangles usually begins by stating that our $A(S) \subset R^\*$, where $R^\*$ is the target function. My only question is regarding the inclusion, surely if we have no positive samples, then there is no (obvious at least) reason to believe that statement to be true? I'm just confused about why do we not separately treat the case in which we have no positive samples in $S$, because then the area in which we could do mistakes is an arbitrary rectangle we choose with $A(S)$.

# Answer
> 1 votes
I agree with D.W.'s comment; please include more information! I believe the algorithm you're referring to outputs $A(S)$ as a membership indicator of the smallest rectangle containing all positive samples. This would not be an arbitrary rectangle in the case of only negative rectangles, rather $\emptyset$. So, it would always output 0 as $A(S)(x) = 1 (x \in \emptyset) = 0$ where $\emptyset \subset R$. So it wouldn't merit a special case.

---
Tags: machine-learning, learning-theory
---


title: Double Dominating Set NP-Complete

text:
# Question
Title: Double Dominating Set NP-Complete
How do i show that Double Dominanting Set is NP-Complete by reducing Dominating Set to it i have thought by adding a edge but my solution is not correct

Input is an undirected graph and a target. The question is whether it is possible to find a subset with a maximum vertices that doubly dominate all vertices in the graph. This means that each vertex is either in the subset or has two neighbors that are in the subset. Show that this decision problem is NP-complete by partly showing that it lies in NP and partly by designing a polynomial Karp reduction between the NP-complete problem Dominant Set

# Answer
> 1 votes
The problem is clearly in $\mathsf{NP}$ (you can use the double dominating set as a yes certificate), and the following reduction shows that it is also $\mathsf{NP}$-Hard.

Given a graph $G = (V,E)$ with $V = \\{v\_1, \dots, v\_n\\}$, define $G' = (V', E')$ as the graph obtained by adding $n$ new vertices $v'\_1, \dots, v'\_n$ along with all edges $(v\_i, v'\_i)$ for $i=1,\dots,n$.

**$G$ has a dominating set of size at most $k$ if and only if $G'$ has a double dominating set of size $k+n$.**

Proof: If $S$ is a double dominating set of $G$ of size at most $k$ then $S' = S \cup \\{v'\_1, \dots,v'\_n\\}$ has size at most $n+k$ and is a double dominating set of $G'$. Indeed, each vertex $v\_i \in V' \setminus S' = V \setminus S$ is dominated by $v'\_i$ and by at least one neighbor in $S$.

Conversely, if $S'$ is a dominating set of $G'$ of size at most $n+k$ then $S'$ contains all vertices in $\\{v'\_1, \dots, v'\_n\\}$ since each of these vertices only has a single incident edge. Then $S = S' \setminus \\{v\_1, \dots, v\_n\\}$ has size at most $k$ and is a dominating set of $G$. Indeed, each $v\_i \in V \setminus S$ is dominated by at least two vertices in $S'$ (in the graph $G'$) and, since at most one of these vertices is in $\\{v'\_1, \dots, v'\_n\\}$, the others (i.e., at least one) must be in $S$.$\square$

---
Tags: np-complete
---


# Question
Title: Cache memory temporal locality and spatial locality principles
How does cache memory take advantage of both temporal locality and spatial locality principles?

# Answer
> 1 votes
It loads data in "blocks". Hence, data close together will be loaded together - space locality

It gets rid only of the most unused data - temporal locality

# Answer
> 0 votes
Consider block size as 20B and integer array of 5Elements each of 4B, we know array is stored in contiguous memory locations, consider the base address of Array as 0x0000, the moment you access the very first element it will be miss, because the block you are referring haven't refered before, so for the first element it will be miss, when you the second element it will be hit, because the moment the you access the first element the whole brought into Cache memory like this it will be hit for 3,4,5the elements also (Spatial locality) , you keep accessing the same variable for ex:- sum += 1, here you are accessing variable sum again and again so when you access it first it will be miss, after that it will be unless the block contains the variable has been replaced.

This how cache memory takes advantage of spatial and temporal locality.

---
Tags: cpu-cache
---


# Question
Title: How to Remove Left Recursion from this Grammar?
How to remove left recursion in the following Grammar:

```
S→Bb/a
B→Bc/Sd/e

```

Im new to this, below is the way I'm doing it:

```
S-> Sd/a
B-> Bc/Bb/e

```

I replaced the values of S and B with Bb and Sd to make the grammar easier to deal with. Then:

```
S-> aS'
S'-> dS' / ε

```

Is this the correct approach to do this ?

# Answer
> 0 votes
```
S->Bb|a
B->SdB'|eB'
B'->cB'|ε

```

---
Tags: context-free, formal-grammars, compilers, recursion
---


# Question
Title: Can a MMU be emulated entirely in software?
I'm curious about the viability of creating memory isolated processes on a processor without an MMU.

While it would be inefficient I'm wondering if it's possible to basically create a virtual machine with an MMU and process each instruction on the emulator. In essence the VM would keep track of the current processes memory offset, pre compute memory access to verify the instructions stay in bounds, etc.

Are there alternative approaches? I understand Microsoft did something involving compile timer verification but I couldn't find much about it.

# Answer
> 1 votes
I have seen research papers studying approaches to this, for use on low-end embedded microprocessors. One approach I have seen is to use SFI (Software Fault Isolation) (or other techniques, like dynamic instrumentation) to provide memory isolation and also patch the code so that, on each backward branch, you check whether the process has run long enough that you should do a context switch.

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


# Question
Title: Accuracy of Digit Recognition with Template Matching
I have designed a C++ program to recognize the digits on an ID card based on OpenCV. First I preprocess the ID card image and then segment it based on contours. The segmentation results are as expected. Then I use the matchTemplate function with templates stored in the template path. However the recognition is inaccurate, for example $0$ may be recognized as $8$. Here is my template matching algorithm, matching the digit image with template images $j = 0$ to $j = 9$:

```
for (int j = 0; j < 10; j++) {
    string templatePath = "C:\\Users\\86188\\Desktop\\numbers\\" + to_string(j) + ".png";
    Mat templateImg = imread(templatePath, IMREAD_GRAYSCALE);
    resize(templateImg, templateImg, Size(digitWidth, height));
    Mat result;
    matchTemplate(digitImg, templateImg, result, TM_CCORR_NORMED);
    double matchVal;
    minMaxLoc(result, nullptr, &matchVal, nullptr, nullptr);
    if (matchVal > maxMatchVal) {
        maxMatchVal = matchVal;
        maxMatchNum = to_string(j);
    }
}
matchedNumbers.push_back(maxMatchNum);

```

Why is it inaccurate? Is there an accurate algorithm for digit recognition? According to OpenCV:

> Template Matching is a method for searching and finding the location of a template image in a larger image. OpenCV comes with a function cv.matchTemplate() for this purpose. It simply slides the template image over the input image (as in 2D convolution) and compares the template and patch of input image under the template image. Several comparison methods are implemented in OpenCV. (You can check docs for more details). It returns a grayscale image, where each pixel denotes how much does the neighbourhood of that pixel match with template.
>
> If input image is of size (WxH) and template image is of size (wxh), output image will have a size of (W-w+1, H-h+1). Once you got the result, you can use cv.minMaxLoc() function to find where is the maximum/minimum value. Take it as the top-left corner of rectangle and take (w,h) as width and height of the rectangle. That rectangle is your region of template.

# Answer
> 0 votes
Don't use template matching; use a classifier to classify each digit.

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


# Question
Title: Languages having only one Myhill–Nerode equivalence class
Consider the alphabet $\Sigma = \\{a,b\\}$. For which languages does the Myhill–Nerode equivalence relation have exactly one class?

From what I understand about equivalence classes, each state is considered a class. So would $\\{ a^n : n\>0\\}$ be the one class?

# Answer
Assuming that you mean the Myhill-Nerode relation, the Myhill-Nerode theorem states that the number of equivalence classes exactly equals the number of states in the minimal DFA accepting the language (if it's regular; otherwise there are infinitely many equivalence classes). So we have reduced the question to the following one:

> Which regular languages can be accepted using a DFA having only one state?

I'm sure you can answer this one yourself.
> 6 votes

# Answer
Let $L \subseteq \\{ a, b\\}^\*$ be a language with one Myhill-Nerode equivalence class. You can show that $L$ must be trivial, that is $L\in \\{\emptyset, \\{a, b\\}^\*\\}$, either by using the Myhill-Nerode theorem as Yuval did, or by showing that directly. Indeed, as for $L$ to have a single Myhill-Nerode equivalence class, it means that for all three words $x,y$ and $z$ over $\\{ a, b\\}$, it holds that $$x\cdot z \in L \Longleftrightarrow y\cdot z \in L$$

In words, we cannot separate any two words $x$ and $y$, by any word $z$. Hence, $L$ must be trivial, because otherwise there are two words $x\in L$, and $y\notin L$, and for $z = \epsilon$, we get that $x \cdot z = x \in L$, but $y\cdot z = y \notin L$, and we have reached a contradiction.
> 2 votes

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


# Question
Title: Use of Myhill-Nerode Theorem to prove minimal number of states
I'm confused about how we can use the Myhill-Nerode Theorem to solve this problem, some pointers would be very helpful

Let $Σ = {\\{a, b}\\}$ and $C\_k=Σ^\*aΣ^{k-1}$

Prove that for each k, no DFA can recognize $C\_k$ with fewer than $2^k$ states.

# Answer
You need to find $2^k$ words which belong to different equivalence classes of the Myhill–Nerode relation. Put differently, you need to find a collection of $2^k$ words such that for any two of them $x \neq y$ there is a word $z$ such that $xz \in L$ and $yz \notin L$ or vice versa.
> 2 votes

# Answer
(I know, ancient question)

Consider the $2^k$ different strings in $\Sigma^\*$ of length $k$, and consider which of those strings are equivalent to which other of those strings under the equivalence relation used in the Myhill-Nerode theorem.

Obviously, strings that end in `a` aren't equivalent to strings which end in `b` because if you attach a suffix of length $k-1$, the strings that end in `a` are in $C\_k$ but the strings that end in `b` aren't.

Similarly, strings with the second-to-last letter of `a` aren't equivalent to strings with the second-to-last letter `b` because of what happens with a suffix of length $k-2$, and so on.

Therefore none of these strings are equivalent to each other, and we're done.
> 2 votes

# Answer
Consider the language ${C\_k}$, and let $\sim\_{C\_k}\subseteq \Sigma\times \Sigma$ denote the Myhill-Nerode equivalence relation w.r.t to $C\_k$. As the number of Myhill-Nerode equivalence classes bounds from below the size of the minimal DFA that recognizes $C\_k$, it is sufficient to bound the number of Myhill-Nerode equivalnce classes from below. Specifically, we show that the relation $\sim\_{C\_k}$ has at least $2^k$ equivalence classes. Consider all words $w\_1, w\_2, \ldots, w\_{2^k} \in \Sigma^k$, thus, every word $w\_i$ is of length $k$ and consists only of letters from $ \Sigma = \\{ a, b\\}$. We claim that for all $1 \leq i \< j \leq 2^k$, it holds that $\[w\_i\]\_{\sim\_{C\_k}} \neq \[w\_j\]\_{\sim\_{C\_k}}$ ($w\_i$ and $w\_j$ are not in the same equivalence class) , and hence there are at least $2^k$ equivalence classes:

As the words $w\_i$ and $w\_j$ are of length $k$, we can write them as $w\_i = c\_1\cdot c\_2 \cdots c\_{k}, w\_j = d\_1\cdot d\_2 \cdots d\_{k}$, where $c\_l, d\_l \in \Sigma$ for all $l\in \[k\]$. Recall that the words $w\_i$ and $w\_j$ are distinct, and let $l \leq k$ be the maximal index such that $c\_l\neq d\_l$. Assume w.l.o.g that $c\_l = a$ and $d\_l = b$. Then, any word $z$ of length $l-1$ is such that $w\_i \cdot z = c\_1\cdot c\_2 \cdots c\_l \cdot c\_{l+1} \cdots c\_{k} \cdot z$ has $c\_l =a$ as its $k$'th letter from the end, and $w\_j \cdot z = d\_1\cdot d\_2 \cdots d\_l \cdot d\_{l+1} \cdots d\_{k} \cdot z$ has $d\_l = b$ as its $k$'th letter from the end. Hence, every word $z$ of length $l-1$ is such that $w\_i \cdot z \in C\_k$, but $w\_j\cdot z \notin C\_k$, and thus $\[w\_i\]\_{\sim\_{C\_k}} \neq \[w\_j\]\_{\sim\_{C\_k}}$.
> 1 votes

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


# Question
Title: Finding Specific Order Statistics with O(n log(n/k)) Complexity
I'm working on a problem where I need to find specific order statistics in a set of numbers. Given `n` numbers, I want to determine the `k-th` smallest, the `2k-th` smallest, and so on, up to the `⌊n/k⌋-th` smallest element. I'm looking for a method to accomplish this with a time complexity of `O(n log(n/k))`.

**My Attempt:**

So far, I've considered using modified sorting algorithms and heap structures, but I'm not sure if these approaches can achieve the desired time complexity. I suspect there might be a more efficient way to find these specific elements without fully sorting the entire array.

**Question:**

Can anyone suggest an algorithm or method to find these elements with the required time complexity?

# Answer
Find `n/2k-th` in $O(n)$ time. There are standard algorithms for finding any `p-th` smallest element in array in $O(n)$ time.

Partition the array in almost equal halves about this `n/2k-th` smallest element. Run the algorithm recursively on the two halves. Once the algorithm finds all the required $n/k$ elements; return.

Note that the height of the recurrence tree is $O(\log(n/k))$. and in each level the algorithm is doing $O(n)$ comparison operations.

Thus, the overall running time is $O(n \log (n/k))$.
> 2 votes

---
Tags: algorithms, sorting
---


# Question
Title: Distinction between square roots in cyclic fields
* Let $\mathbb{F}=\mathbb{Z}/p\mathbb{Z}$ a cyclic field. Where $p$ is fixed
* Let $(H)\_{n\in\mathbb{N}} \in \mathbb{Z}\[x\_1,\dots\]^{\mathbb{N}}$ a family of polynomials with $H\_n\in \mathbb{Z}\[x\_1,\dots,x\_n\]$
* Let $\varphi : \mathbb{Z}\rightarrow \mathbb{F}$ the ring isomorphism defined by $\varphi(x)=x\bmod p$
* Let $f$ a positive increasing function of the size of polynomial.
* Let $u\_1,\dots,u\_n \in\mathbb{F}$

With that, I was thinking about the following problem: Suppose that $\varphi(H\_n^2)(u\_1,\dots,u\_n)$ can be calculated in $\mathcal{O}(f)$ time. Can we calculate $\varphi(H\_n)(u\_1,\dots,u\_n)$ in $\mathcal{O}(f)$ times?

---

To illustrate an example, I will refer to the Vandermonde polynomials: $$ V\_n(x\_1,\dots,x\_n)=\prod\_{i\<j}x\_j-x\_i $$ I was able to calculate $V\_n^2(u\_1,\dots,u\_n)$ in $\mathcal{O}(M(n) \log n)$ as follow:

* Build $P(x)=\prod\_{i=1}^{m}x-u\_i$
* Calculate $P'(u\_1),\dots,P'(u\_n)$ using fast multi-point evaluation
* The result is the product $\prod\_{i=1}^{n} P'(u\_i)$

Now, with $V^2\_n(u\_1,\dots,u\_n)$ calculated. There are (usually) two candidates for $V\_n(u\_1,\dots,u\_n)$ that can be calculated in $\mathcal{O}(1)$ (The cyclic field is fixed). I was not able to arrive to any method that can extracts the correct square root from both candidates.

That is it appears to me that both square roots are indistuinguishable in $\mathbb{F}.$ But they are in fact distinguishable in $\mathbb{Z}$ as we can infer the sign from the sign $\delta(\Pi)$ of the permutation $\Pi$ that sorts $(u\_1,\dots,u\_m)$ in their increasing order.

In the other hand I was able to have a $\mathcal{O}(M(n) (\log n)^2)$ algorithm as described here.

So to conclude, is calculating $V\_n^2$ and $V\_n$ in the same computational class?

# Answer
I don't believe you can compute $\varphi(H\_n)(u\_1,\dots,u\_n)$ from $\varphi(H\_n^2)(u\_1,\dots,u\_n)$ in a black-box manner, because there are two possibilities for the square root, exactly as you wrote.

Whether you can compute $\varphi(H\_n)(u\_1,\dots,u\_n)$ efficiently depends on $H\_n$.

I don't know whether you can compute $V\_n(u\_1,\dots,u\_n)$ in $O(M(n) \log n)$ time.

I realize this is probably not helpful. I'm trying to answer exactly the question you asked.
> 0 votes

---
Tags: complexity-theory, polynomials
---