# Question
Title: An Exact Method for Solving Small Instances of XORSAT
I have a couple of small instances for XORSAT for which I am to design and implement an exact method. However, there are a few catches. It is guaranteed that there always exists and answer but I need to find the one solution with the minimal (non-zero) number of TRUE variables.

As I understand, XORSAT can apparently be solved in polynomial time through the Gaussian Elimination method but I simply cannot apply the special conditions of this problem (the minimal number of TRUE variables) and I'm wondering if I could potentially get some help on that.

The instances of XORSAT that I have are not completely random, they all consist of a number of variables that if XOR'd together will always yield FALSE. I.e., all of the clauses are in the form of $x\_1 \oplus x\_2 \oplus ... \oplus x\_i = 0$ which would translate into the equation $x\_1 + x\_2 + ... + x\_i = 0\space(mod 2)$.

At first, I tried to apply a greedy method, taking the two most repeated variables in all of the clauses and forcing the value TRUE on them, then propagating their values through all of the clauses and repeating the same method on the remaining unsatisfied clauses but that was fundamentally flawed.

Any help is tremendously appreciated.

# Answer
> 3 votes
If your formula has $n$ variables, for each value of $k$ from 1 to $n$, add an exactly-$k$ cardinality constraint to your SAT instance and then run a SAT solver on each result. The solver will only emit a solution with exactly $k$ variables set TRUE and will return UNSAT if no such solution is possible. As soon as the solver returns something other than UNSAT for an instance containing an exactly-$k$ constraint you have your answer. At worst you will need $n$ runs of the solver.

If you want to get fancy, you can use binary search to probe the $k$ values until you bracket the minimal one and you'll only need $O(\log n)$ solver runs.

# Answer
> 4 votes
I'll assume all of the equations take the form $x\_i + \cdots + x\_j = 0$ (i.e., always 0 on the right-hand side). Then, your problem is: given a boolean matrix $M$, find a $x$ such that $Mx=0$ (modulo 2) that minimizes the Hamming weight of $x$.

I think this is equivalent to the problem of finding the minimum-weight codeword of a linear code. That problem is NP-hard, and hard to approximate. The equivalence: we think of $M$ as the parity-check matrix of a linear code; then $x$ is a codeword iff $Mx=0$, so your goal is to find a minimum-weight codeword. I encourage you to check my reasoning here.

There is a brute-force algorithm that runs in $O({n \choose w})$ time, where $n$ is the number of boolean variables and $w$ is the weight of the solution. Assume that $w$ is known (in practice we can search over increasing values for $w$, as there aren't too many possibilities for it). Then, you simply enumerate all ways to choose a subset of $w$ of the variables to set to true and check whether any of them work.

I think there is a meet-in-the-middle algorithm that takes exponential time but is faster than enumerating all possibilities. The algorithm takes $O({n/2 \choose w/2} \sqrt{w})$ time and space, which is significantly better than the brute-force algorithm. We'll write $x=u+v$, where $u$ is zero in its right $n/2$ bits and $v$ is zero in its left $n/2$ bits. Then $Mx=0$ is equivalent to $Mu=Mv$. We'll optimistically hope that $u$ has weight $w/2$ and $v$ has weight $w/2$; as I argue later, this happens with good probability. So, we enumerate all ${n/2 \choose w/2}$ values of $u$ and store $Mu$ in a hashtable. Then, for each of the ${n/2 \choose w/2}$ possible values of $v$, we compute $Mv$ and look it up in the hashtable. If we find a match $Mu=Mv$, we've found solution $x=u+v$. What's the success probability of this algorithm? It is ${n/2 \choose w/2}^2 / {n \choose w} \approx \sqrt{2/(\pi w)}$. Thus, if we repeat the algorithm about $\sqrt{\pi w/2} = O(\sqrt{w})$ times, with a different split of the $n$ coordinates into two equal-size subsets, we expect to find one solution. Check my reasoning here -- this is from memory, so I can't vouch for this.

I believe there are algorithms in the literature that improve upon this scheme. See, e.g., A new algorithm for finding minimum-weight words in a linear code: application to McEliece’s cryptosystem and to narrow-sense BCH codes of length 511 by Canteaut and Chabaud. I think there has been more recent work but I'm not up to speed on it.

---
Tags: satisfiability
---


# Question
Title: Are non halting programs not computable?
Are non halting programs not computable? How are these two sets of programs related: is a non halting program just a specific example of a type of program that is not computable or is it technically computable just not in finite time (the computation can be defined it just goes on forever). Im just not sure about the goes on forever part -- does that circle back and make it not computable?

Thanks!

# Answer
> 0 votes
A *language* (set of strings) can be computable or not (also called decidable), which means that given a string $\sigma$ there is a Turing machine (more generally speaking, a program) that is guaranteed to halt in a finite time, telling correctly whether $\sigma$ belongs to the language or not.

You can consider e.g. the language of all valid C programs that eventually halt (don't get into some sort of infinite loop). That language is non-computable (no program can take a program and tell correctly in all cases whether it halts or not). To call a C program "non-computable" makes no sense, it is just an element of the language. For any particular example C program you can perhaps answer the question (given enough ingenuity), the point is that you can't solve it *in general*.

---
Tags: computability, halting-problem
---


# Question
Title: The halting problem of Turing machines in view of enumeration of initial tape configurations
As far as I know, presentations of the (general) halting problem (cmp. Wikipedia) are referring explicitly to an ennumeration of (applicable) programs. For the purpose of my questions let's consider specificly any programs for one-head, two-symbol Turing machines with sufficient memory to store the instructions prescribed by the program and any (internal) state reached in the course of executing the program.

Such an enumeration of applicable programs could be symbolically written as

$$ p : \\{ \mathsf{TM\_{\text{(1 head, 2 symbols)}}} \\} \leftrightarrow \mathbb N.$$

(The mapping is one-to-one since enumeration is supposed to be without gaps, and there are infinitely many Turing machine programs to be enumerated. For definiteness, the set $\mathbb N$ here denotes the whole numbers, including $0$.)

I am interested in the consequences of the input (i.e. specificly the contents of the tape, in reference to the machine head, at the start of program execution) being explicitly encoded through an enumeration as well; symbolically

$$ s : \\{ \text{ starting tape configurations } \\} \leftrightarrow \mathbb N;$$

specificly for instance, for input $\text{ tape contents }$ with non-blank fields on positions $1 \le a \lt b \lt c ... \lt l$ to the left of the Turing machine head and on positions $0 \le z \lt y \lt x ... \lt r$ to the right of the head (and if applicable on position $0$ directly under the head in starting position) then

$$ s\[~\text{tape contents}~\] := (4^a + 4^b + 4^c ... +~4^l)/2 + 4^z + 4^y + 4^x ... +~4^r.$$

(The completely blank tape is accordingly encoded as number $0$.)

**My question:**
Given the above description, can the non-existence of a halting program ("*DoesItHalt?*") be proven regardless of the specific enumeration $p$ of Turing machine programs? And if so, how exactly?

---

As an illustration of possible difficulties in trying to argue that a Turing machine program "*DoesItHalt?*" doesn't exist one might perhaps consider the composition

*BadH* := *EncodeInput* | *DuplicateArgument* | *DoesItHalt?* | *ContrarianActor*

which should have the value $p\[$ *BadH* $\]$ in the enumeration of programs,
running on input "*BadI*" which would be selected exactly such that

$p\[$ *BadH* $\] = s\[$ *BadI* $\]$;

where

* *EncodeInput* is supposed to be a specific program implementing the enumeration $s$,
* *DuplicateArgument* is a simple program to prepare the two arguments required for a (meaningful) subsequent execution of *DoesItHalt?*, and
* *ContrarianActor* is a simple program whose action is just the opposite of the intended meaning of *DoesItHalt?*'s result.

Then it would be premature to conclude a contradiction; that program *DoesItHalt?* didn't function as correct halting program because the program *BadH*, being run on the inital tape configuration *BadI*, is thought to act eventually just contrary to the intended meaning of the presumed result of program *DoesItHalt?* evaluating (running on) the two argument values $p\[$ *BadH* $\]$ and $s\[$ *BadI* $\]$. Because:

Already the (apparently necessary) program part "*EncodeInput*" is questionable: It is supposed to terminate when starting on any initial tape configuration with a finite number of non-blank fields (in order to return its enumeration value). But therefore it also returns the exact same result when starting on any "suitably extended" initial tape configuration with some (still finite) additional non-blank fields "sufficiently further out". The correct enumeration values of any such "suitably extended" initial tape configuration cannot be returned by the specific "*EncodeInput*" program.

Then why not enumerate the specific "*BadH*" program of the example above precisely by such an "inaccessible" value (which obviously is not being calculated by program part *DuplicateArgument* either); thus defeating the attempt of arriving at a contradiction in this specific case. (Obviously, this would have to be accomodated by a suitable enumeration of all programs.)

# Answer
The Halting problem is stated in terms of any admissible numbering. There are effective (i.e. Turing-computable) compilers between all such numberings, so the Halting problems are all the same. That is, in particular not decidable.

There are numberings of all partially-recursive functions for which the Halting problem is decidable -- of course. For instance, give all "yes"-instances even and all "no"-instances odd numbers. Such a numbering would certainly not be admissible; in this case because it would not be partially recursive.

Thus, it comes down for you to show that your numbering is admissible or not. If not, the Halting problem *may* be decidable but the numbering would be ... not very useful.
> 3 votes

# Answer
Whatever your "initial tape configuration" may be, you can translate it into a Turing machine starting with blank tape by prepending enough processing to write your starting tape contents before starting your machine proper.
> 0 votes

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


# Question
Title: Busy-Beaver-like question for WHILE-Programs (Theoretical CS)
So this is exam-task is called "Busy WHILE-Programs"

In our lecture it was proven that WHILE-Programs are turing-complete. In short a WHILE-Program only allows the following:

```
Variables             x1,x2,...  (initially all 0 and can only be positive)
Constants c           0,1,2,3,...
Assignment            xi := c
Addition/Subtraction  xi := xj + c, xi := xj - c
while-loops           while(xi != 0) { ... }

```

In part (a) of the task we should show, that every WHILE-program can be simulated by a WHILE42-program.

A WHILE42-program is a WHILE-program where all constants can only be 42 or lower.

Now the task where I need help (I try to translate from german):

*Let WHILE42(n) be the subset of all WHILE42-programs, with no more than n instructions/commands. The function g(n) returns the biggest value, a terminating program from the WHILE42(n)-subset assigns any of it's variables. Prove or disprove the following statement:*

`The function g(n) is not computable`

I have two routes with the second being probably a valid answer:

**First:** My intuition tells me it is not computable and that I should show (like in the Busy-Beaver-example) that if it would be computable, it would solve the Halting-problem. Which would show, that it can't be computable.

My thought-process so far:

If `g(n)` is computable, I could take any TM `M_1` and transform it in a WHILE42-program `W_1` with `n_1` commands. I could then calculate `g(n_1)`.

Then I need to show that from this value `g(n_1)` I can derive somehow an upper value of how many steps I need to simulate `M_1` to decide if it will terminate or run forever.

But I struggle to determine what this upper value is.

**Second:** Here my intuition tells me, that this is not how it is expected to be solved. So I would prefer a solution to the first one, if there is any

If `g(n)` is computable, there is a TM `M_g` that calculates `g(n)`. `M_g` could be transformed in a WHILE42-program `W_g` with `n_g` commands.

Since `W_g` would for any `n` at some point assign the highest value for this WHILE42(n)-subset, `g(n_g)` can not compute a value. For any value k `g(n_g)` could return, it would be possible to construct a terminating WHILE42-Programm that adds the value `42` k-times to a variable which would grow larger than k.

# Answer
Okay I think I figured it out for the **first** solution.

If I would have `g(n_1)` and this would be the limit of any variable of a WHILE42(n\_1) can possibly be, this would mean that I could calculate every configuartion `W_1` could possibly have. With a configuration being the value of all variables (from `0` to `g(n_1)`) and the state (the operation which is about to be executed).

No WHILE42-program that terminates can ever be in the exact same configuration. So if any WHILE42-program runs more operations than the number of possible configurations I therefore know, it will not terminate. =\> this would solve the halting problem for WHILE42 and therefore also for TMs.

=\> g(n) is not computable
> 0 votes

# Answer
Use the same proof as Radó did in his paper: Assume there is a program $\Sigma$ that computes the value asked for, combine with a program that given $n$ computes $2 n$, and add $1$ to the result. Call the number of lines of the result $N$. Writing a program that computes $N$ should take at most $N$ lines (add $1$ $N$ times). Combine the above, the result is of length $2 N$ and computes a value larger than the largest it is able to compute given it's length. Contradiction, $\Sigma$ can't exist.
> 1 votes

---
Tags: computability, halting-problem, busy-beaver
---


# Question
Title: How specifically do I need to describe (in words) the language of a regular expression?
For the regular expression $(a^\*ba^\*b)^\*a^\*$, I want to learn how to describe it in words. I know there are an even number of $b$s but how much do I need to explain it? Do I need to explain it enough that each possible string can be produced from my explanation?
Another example is $(a^\*\[ba^\*c\])^\*$ where I would describe it as as string over $\\{a,b,c\\}$ where there are the same number of $a$s and $c$s.

# Answer
The first language can be described as the set of words on the alphabet $\\{a,b\\}$ with an even number of $b$'s.

The second one is **not** the language of words on the alphabet $\\{a,b,c\\}$ with an equal number of $b$'s and $c$'s (this condition would define a non-regular language). You could use greybeard's description or say: the language contains the empty word, the last letter of the nonempty words of the language is a $c$ and if you delete the $a$'s, you are in $(bc)^\*$.

It would be safe to provide a formal proof by computing the minimal automaton corresponding to each description.
> 1 votes

---
Tags: automata, finite-automata, regular-expressions
---


# Question
Title: Counting strings with balanced substrings
Consider a *string* of characters $a, b, c$ only. Such a string is called *good* if the *number* of $a$'s + *number* of $b$'s is equal to the *number* of $c$'s.

Given an integer $n$, find the number of *strings* of length $n$ consisting only of characters $ a,b,c$ such that all of its substrings of length $k$ are *good*.

*Example:*

$ n = 3 ,k = 2 $ is $6$,

$ n = 2,k = 1 $ is $0$

I could only solve when there are only two characters but can anyone help me how to solve when there are three characters.

# Answer
> 1 votes
For a good string $s$ of length $k$, let $M(n,s)$ denote the number of strings of length $n$ terminating in $s$ in which every $k$-letter substring is good. The quantity $M(n,s)$ is given by the following recurrence: $$ \begin{align} &M(k,s) = 1 \\ &M(n+1,ta) = M(n+1,tb) = M(n,at) + M(n,bt) \\ &M(n+1,tc) = M(n,ct) \end{align} $$ Here $t$ is a string of length $k-1$. Summing over all good strings $s$, we can solve your problem.

Since $a$ and $b$ are really interchangeable, we can also consider a slightly different recurrence, in which $s$ only consists of $a$'s and $c$'s: $$ \begin{align\*} &M'(k,s) = 2^{\\#\_a(s)} \\ &M'(n+1,ta) = 2M'(n,at) \\ &M'(n+1,tc) = M'(n,ct) \end{align\*} $$ Here the second parameter is a "template" in which $a$ stands for either $a$ or $b$.

Using either recurrence, you can find explicit formulas for any given value of $k$.

---
Tags: algorithms, dynamic-programming, combinatorics
---


# Question
Title: Hardware protection needed for operating system kernel
I have a question related to the hardware protection needed to implement an operating system kernel:

> Identify at least three hardware level mechanisms that are necessary to protect an operating system kernel from malicious or erroneous user programs.

I can't work out what that would be from the Wikipedia article.

# Answer
The answer is actually none. This is not what your teacher expects in this homework assignment, but it's true.

The problem in process isolation is to protect against processes that try to access resources that they should not (resources that are used by other programs or by the operating system itself). Resources include memory and peripheral devices.

You can design an operating system that verifies all programs before running them, and only runs a program if it can prove to its satisfaction that the program will never attempt to access a resource that it is not allowed to access. Such operating systems are not very common, but they exist, for example some smartcards running Java Card work like this: only Java bytecode applications can be installed on the card, and they have to have been checked and passed by a bytecode verifier.

That being said, most operating systems enforce process isolation by leveraging hardware means. The most important part is the memory protection unit: a hardware component that assigns privilege levels to blocks of memory and ensures that only programs with the appropriate privilege level can access each block. Often memory protection is performed by a memory management unit which combines protection with virtual memory management, but the indirection afforded by virtual memory is not necessary for the protection aspect. There are processors with an MPU but no MMU. The uClinux project is an example of operating system which enforces process isolation and runs on processors with only an MPU.

In order to be of any use, the MPU has to be combined with some mechanism that assigns privilege levels to programs. Most CPU types that allow privilege isolation have at least two modes (sometimes more), which I'll call kernel and user, with kernel being the most privileged. At any time, the CPU is in one mode or the other. The CPU boots in kernel mode. Switching into kernel mode from user mode always causes a jump to a fixed address. That way, the initial program that is loaded at boot time remains in control of what can be executed in kernel mode. It is up to that program to set up the MPU/MMU so that other programs cannot overwrite kernel code or access peripherals directly, thus enforcing isolation between kernel code and user code. The kernel is also responsible for changing MPU/MMU settings when switching between programs so that programs can only access their own memory and not other programs'.

That's two mechanism. I don't know what your teacher had in mind for the third one.
> 7 votes

# Answer
Hardware level protections is through following mechanisms in OS: 1) **Dual mode operation:** This is the basis of all the protections. All the process operations are performed through either User mode or Kernel mode. User mode is the one in which execution is done on behalf of a user And Kernel/monitor mode is the one in which execution is done on behalf of operating system. So basically all the privileged operations are performed in Kernel mode. 2) **I/O protection:** All the input/output operations are privileged instructions and hence are done in kernel mode. OS must ensure that application prog which is part of user mode does not get control of computer in Kernel mode. 3) **Memory protection:** User mode should be given access to only those memory locations for which they are allowed. It is achieved by having atleast two registers viz. Base register: It stores the starting physical address of the allowed memory location Limit register: It stores the size of the range. So whenever CPU asks for the memory location access by giving its access, it is checked if it falls between Base address and Base+Limit address. In kernel mode OS has access to all the memory locations including kernel and user memory. Loading of base and limit registers is again a privileged instruction and hence done in Kernel mode. 4) **CPU protection:** It is achieved through a timer which is decremented with every clock tick. When timer reaches 0, interrupt occurs and current process execution is suspended by CPU. It is used to implement time sharing, also used for computing current time. Loading of this timer is privileged instruction and hence done in kernel mode.
> 2 votes

# Answer
Early microcomputer operating systems (up to and including MS-DOS) had *no* protection against malicious user programs. At least the multitasking operating system of the Alpha Micro computer (a Motorola 68000 with Z80s handling terminals, i.e., an example of non-symmetric multiprocessor) did run everything (!) in supervisor mode (no protection at all, even on a rather decent processor). We had one for programming courses at UTFSM, students hacked all sorts of nefarious programs on it...
> 0 votes

---
Tags: operating-systems
---


title: Algorithm for token replacement game

text:
# Question
Title: Algorithm for token replacement game
I'm having problems finding an algorithm to the following problem:

A and B take turns replacing a number $n$ of tokens with either $floor((n+1)/2)$ or $n-1$. The player who makes **one** token remain wins. We want to know, if there is a way for B to win the game no matter the moves of A. A begins the game.

My idea is the following:

Is n = 1 -\> No way for B to win the game

We try all moves of first A then B and check for 1 -\> There is a way for B to win

But this does not incorporate the "no matter the moves of A" criteria.

# Answer
> 2 votes
I'd check what happens for some small(ish) values of initial $n$, working up. If you know who wins if there are at most $n$ on the table, working out what happens with $n + 1$ is easy.

---
Tags: algorithms
---


title: Induction proofs in Big-O notation

text:
# Question
Title: Induction proofs in Big-O notation
I'm not sure how go about this question: Prove the following inequality. For a correct proof, we require a value of the constant $c\>0$ and an $n \in \mathbb N$, such that $\forall n\>N : f(x)\<c\cdot g(n)$.

$\mathcal O(2^n) \< \mathcal O (n!)$.

I'm well aware how to prove $2^n \< n!$ using induction, I just don't understand how one is supposed to find a constant, etc. The only thing that springs to mind here is choosing $N = 4$, since that is when $2^n \< n!$ begins to hold. If someone could clarify how I can apply the definition of Big-O notation to solve this, I would be greatful.

# Answer
We need to inspect the factors after that, since the factors of $n!$ grows linearly while the factors of $2^n$ stays constant. We use the first four factors and the rest of them to formulate the constant factors used for the big-O proof. It is obvious that $2^4 = 16$ while $4! = 24$. However, by observing the factors, we notice $2^n$ has $16$ as a factor and $n!$ has $24$ as a factor for all $n \geq 4$ and we factor out the first four \[the first $N$\] to clearly highlight that the factorial grows faster.

The factors of $\frac{1}{16} 2^n$ factors out the first $2\cdot 2 \cdot 2 \cdot 2$. It is equal to $2\cdot 2\cdot 2\\,\cdot \\, ... \cdot \\, 2$ with $(n-4)$ factors. The factors of $\frac{1}{24}n!$ factors out $1 \cdot 2 \cdot 3 \cdot 4$ and is equal to $5 \cdot 6 \cdot 7\\, \cdot \\,... \cdot \\, n$, again with $(n-4)$ factors. When $n = 4$ then these factored-out functions are equal to unity. In fact:

* $2\cdot 2\cdot 2\\,\cdot \\, ... \cdot \\, 2\cdot 2 = c\_f2^n$ where $c\_f = \frac{1}{16}$ whereas
* $5 \cdot 6 \cdot 7\\, \cdot \\,... \cdot \\, (n-1) \cdot n = c\_gn!$ where $c\_g = \frac{1}{24}$.

The $(n-4)$ factors of $c\_f2^n$ is clearly less than the $(n-4)$ factors of $c\_gn!$. We arrive at $c\_f2^n \< c\_gn!$. Move the constant factor on the LHS to obtain $2^n \< \frac{c\_g}{c\_f}n! = \frac{24^{-1}}{16^{-1}}n! = \frac{16}{24}n! = \frac{2}{3}n!$.

By inspecting the factors of $2^n$ and $n!$ after the initial four, and knowing that for all $n \> 4:\\: 2^n \< n!$, we factored out the first four terms of each function and inspected the rest to determine $2^n \leq \frac{2}{3}n!$.

The formal definition of big-O states that:

$$\exists c \> 0\\; \exists N \> 0: \forall n\\; (n\>N) \Longrightarrow f(n) \leq cg(n)$$

In your case, $c = \frac{2}{3} = \frac{16}{24}$ and $N = 4$.
> 2 votes

# Answer
That really makes no sense. Check out e.g. Hildebrand's "Short course on Asymptotics" for details of the meanings and usage of asymptotic notations.

In a nutshell, for typical CS use: $O(f(n))$ is *some* function $g(n)$ that satisfies $g(n) \le c f(n)$ for some (unspecified) positive constant $c$ for all $n \ge n\_0$ for some (again unspecified) constant $n\_0$. The functions $f$ and $g$ are positive in our usage. It is meant to represent some rough upper bound, in the sense that an "equation" like:

$\begin{equation\*} e^{1/n} = 1 + O(1/n) \end{equation\*}$

means that $e^{1/n}$ is $1 + g(n)$ (here, by the series for $e^x$ it is $g(n) = \sum\_{k \ge 1} \frac{1}{k! n^k}$) and $g(n) = O(1/n)$ (the sum of the terms after the first is smaller than a constant times $1/n$, as you can check), and $g(n) = O(1/n)$. The convention is that the right hand side is a rougher expression of the left hand side, "$=$" here is *not* equality. For example, you can check that:

$\begin{align\*} 3 \sqrt{n} &= O(n^3) \\ 17 n^3 &= O(n^3) \end{align\*}$

but that doesn't mean $\sqrt{n} = 17 n^3$. If you use $O(\cdot)$ on the left hand side, make sure the right hand side is rougher. And "$\<$" makes no sense whatsoever, any such inequality is subsumed by the $O(\cdot)$ itself.
> 0 votes

---
Tags: asymptotics, proof-techniques, landau-notation
---


title: Question about system calls

text:
# Question
Title: Question about system calls
I had read about the various functionalities of system calls recently in one of my coursebooks and about how they are used to allocate memory for new processes. The book didn't specify whether it was possible to combine multiple memory allocation requests within a single system call. So I asked one of my teachers and they said that it was indeed possible. I feel that this would probably decrease the system's performance in some way but I cannot seem to give a concrete reason for the same.

Could someone explain why the performance drops in this case?

Thank you for your time.

# Answer
> 1 votes
In a standard operating system like Unix, no. You can't directly make multiple requests. But, you can make one big request for a lot of memory. The system call lets you request a certain amount of memory, and you choose how much to request.

In practice your program doesn't make that system call every time you want to allocate memory. Instead, you have a standard library function, such as `malloc()`, which has a pool of available memory. When you call `malloc()`, it selects a region of available memory and allocates that to the caller, and keeps track that it has been allocated. When the available memory runs out, then it uses a system call to ask the operating system for a bunch more memory. So, it might only need to invoke the system call infrequently, even if you call `malloc()` a lot.

See https://en.wikipedia.org/wiki/Memory\_management#DYNAMIC, https://en.wikipedia.org/wiki/Sbrk, https://en.wikipedia.org/wiki/C\_dynamic\_memory\_allocation, https://en.wikipedia.org/wiki/C\_dynamic\_memory\_allocation.

---
Tags: operating-systems
---


# Question
Title: Compendium of approximation ratios, with narrower scope and more up to date than the NP-compendium?
I usually check the NP-compendium from Pierluigi Crescenzi, and Viggo Kann when I want to know the APX status and approximability results of a problem.

However, I understand that maintaining it is a lot of work, which explains why it is not up to date in some cases. By not up to date, I do not mean non-exhaustive, but that better results on some problems are not included.

Does anyone know an equivalent and more specific website focused only on approximation, which would be more up to date ?

I am not really asking the same question as this one, or this one, but I understand that they may bring the same answer.

Remark: The last example I found was on the Minimum Steiner Tree with distance 1 and 2 on complete graphs, which is said to be approximable in 1.28, but there is a paper from 2009 which provides a 1.25 ratio. It may have been updated.

# Answer
You're expecting too much to expect there to be a single web page that is somehow always updated with the latest in the research literature on the subject.

Let me teach you how to figure out this information for yourself, instead of relying on someone else to have done it for you. The general approach is to find one paper on the approximability of your problem; then use Google Scholar to track down related papers.

How do you find one paper on the problem? Perhaps that web page will show you one, even if it's not the latest on the topic. Perhaps you can search using Google Scholar to find such a paper. Perhaps you'll have to try other methods.

Then, how do you find other papers on the subject, to find what is the latest and greatest state of the art? Read the introduction and related work section of that paper, and it should give you an entryway into previous results. Also, search for that paper on Google Scholar and find what papers cite it; that should give you an entryway into newer results, and you can scan the title and abstracts of those papers to see if they are relevant. Then, proceed recursively from each paper you've determined to be relevant.
> 3 votes

---
Tags: complexity-theory, approximation
---


# Question
Title: Do we know something about this refutation method for SAT?
Let we have a formula $\varphi(x\_1,x\_2...x\_k)$. Now we apply a refutation method: $\varphi(x\_1,x\_2...x\_k)\Leftrightarrow(\varphi(x\_1=1,x\_2...x\_k)\lor\varphi(x\_1=0,x\_2...x\_k))$. Latter formula seems to be longer, but no, good algorithm reduces number of literal occurences. On each step we can modify the formula without changing it's solution space. This gives much more power than resolution has. For example, Tseytin contradiction can be refuted this way in linear time using deterministic algorithm.

But what is the worst case for this algorithm?

Example:

$$\varphi=(x\lor y\lor z)(x\lor\overline y\lor t)(x\lor\overline z\lor\overline v)(\overline x\lor\overline t\lor\overline v)(\overline x\lor\overline z\lor v)(y\lor\overline z\lor v)(\overline y\lor\overline t\lor\overline v)\land(\overline y\lor z\lor t)$$

Step 1. Getting rid of $t$.

Putting $t$. Affected remaining clauses: $(\overline x\lor\overline v)(\overline y\lor\overline v)$. Reducing them: $\overline v\lor \overline x\overline y$.

Putting $\overline t$. Affected remaining clauses: $(x\lor\overline y)(\overline y\lor z)$. Reducing them: $\overline y\lor xz$.

Combining them using OR: $\overline v\lor\overline y\lor xz$.

Step 2. Getting rid of $y$.

Putting $y$. Affected subformula: $\overline v\lor xz$.

Putting $\overline y$. Affected subformula: $(x\lor z)(\overline z\lor v)$.

Combining them: $\overline v\lor xz\lor(x\lor z)(\overline z\lor v)$. Reduction: $x\lor z\lor\overline v$.

Step 3. Getting rid of $x$.

Putting $x$. Affected subformula: $\overline z\lor v$.

Putting $\overline x$. Affected subformula: $(z\lor \overline v)(\overline z\lor\overline v)$. Reduction: $\overline v$.

Combining them: $1$.

All clauses are covered, formula is satisfiable.

But what would be the hardest case for this and is it possible to break exponential bound using this method? Is this method general enough (we can modify formula by any ways until solution space is unchanged and this is checkable in polynomial time) that saying it requires superpolynomial time (for unsatisfiable formula) will imply $\mathsf{NP\ne coNP}$?

Note that for unsatisfiable formula it's possible to non-deterministically ignore some clauses if refutation can be done without their usage.

# Answer
> 3 votes
As far as I can tell the earliest mention of the procedure you outline, later described in the literature as *variable elimination by clause distribution*, was in the paper "ZRes: The old Davis-Putnam procedure meets ZBDD" by Philippe Chatalic and Laurent Simon. The procedure was described again, along with other formula simplification techniques, in "Effective Preprocessing in SAT through Variable and Clause Elimination" by Niklas Eén and Armin Biere.

The procedure was shown to be a workable way to improve SAT solver performance if care is taken to minimize clause growth as the implicants of removed terms are distributed, or to use data structures that efficiently manage large clause sets.

# Answer
> 2 votes
The worst case is exponential. Each time you apply your method to a single variable, you are potentially doubling the size of the formula. You might need to apply this to each of the $k$ variables, so the size of the formula might blow up by a factor of $2^k$. In other words, the running time of this algorithm could potentially be exponential.

What you have described is basically a variation on the DPLL algorithm. The DPLL algorithm picks an variable, say $x\_1$, sets it first to true, simplifies, and tests satisfiability of that; then sets it to false, simplifies, and tests satisfiability of that. That's very similar to what you are doing. An important choice here is exactly what simplification we do; you didn't describe that explicitly, but you can find a description of the specific simplifications that are done in the DPLL algorithm can be found in any good reference on DPLL. DPLL is probably better than your method because it separately simplifies $\phi(0,x\_2,\dots,x\_k)$ and simplifies $\phi(1,x\_2,\dots,x\_k)$, which is potentially easier than simplifying the combined formula $\phi(0,x\_2,\dots,x\_k) \lor \phi(1,x\_2,\dots,x\_k)$ (depending on what simplification rules you use).

---
Tags: np-complete, satisfiability
---


# Question
Title: finding best n players in minimum number of comparisons
I am trying to find out if there is any generic way to find out first to nth best player in a tournament if n is less than the square root of input size i.e. 5 best players in the sample size of 25 players?

I thought of using below approach to find out 2 best players.

So for finding out the 3rd best player we can use the same approach i.e. players lost again best best player + players lost against 2nd best player should be again played against each other to find out the 3rd best player.

Am I right if this would be the minimum number of comparisons to get 3rd best player?

Or should I divide the players in square root of input size and then play in groups as this?

Edit: When two players play better player always wins. You can design your own tournament strategy to figure out the best `n` players.

# Answer
You can't. There isn't enough information in a single elimination tournament to know who the $n$ best players are. All you can infer is who the best player is. You can't even tell who is second best; the second-best player could be any of the people who lost to the best player.

If you're not limited to a single-elimination tournament, I recommend you use a selection algorithm to find the top $n$ players, then use a sorting algorithm to rank-order those $n$ players. Asymptotically, this needs only $O(N + n \log n)$ matches if you start out with $N$ players and want to rank-order the top $n$ of them. If you only want to find the top $n$ players without rank-ordering them, a selection algorithm suffices, and then you'll only need $O(N)$ matches. You can study the literature on selection algorithms and sorting algorithms to figure out how to reduce the constant factor hidden in the big-O notation.

In practice if you want to hold some matches simultaneously, you might want parallelizable selection algorithms and sorting algorithms. Figuring out how to parallelize selection algorithms might be worth a question of its own.
> 2 votes

# Answer
Optimal to find best and second best is to build a binomial tree from the leaves up (i.e., compare disjoint pairs, compare the winners of pairs, and work your way up to the overall winner, always making sure to compare winners of groups of the same size). This ensures the second best is among those who lost to the winner, at most $\lceil \log\_2 n \rceil$ elements. I'd repeat the above among the losers against the winner and second one, and repeat until you have all you want.
> 1 votes

# Answer
One easy way I can think of is

* **Step1** : Sort the players wrt ***No.of matches won***
* **Step2** : Sort the players who have an equal ***No.of matches won*** wrt ***Best opponent faced***

In the case given by you , if you sort wrt to ***"No. of matches won"*** you get a list in the following order

`10,7,[6,9],[5,0,8,1] // After applying Step 1 to the list`

Now you can see that the players in brackets have an equal ***"No. of matches won"***.So you need to sort the lists `[6,9]` and `[5,0,8,1]` wrt to the ***"Best opponent faced"***

Start from the first list that appears from left

`[6,9]` becomes `[9,6]` because

* 9 faced 10 which comes first in the list obtained after **Step 1**.
* And 6 faced 7 which is second in the list obtained after **Step 1**

So

`10,7,[6,9],[5,0,8,1]` becomes

`10,7,9,6,[5,0,8,1] //After applying Step 2 on [6,9]`

Now if we sort `[5,0,8,1]` wrt to the ***"Best opponent faced"*** then we get `[1,0,8,5]` because

* 1 faced 10 which is first in the list
* 0 faced 7 which is second in the list
* 8 faced 9 which is third in the list
* and lastly 5 faced 6 which is fourth in the list

So `10,7,9,6,[5,0,8,1]` becomes

`10,7,9,6,1,0,8,5 //After applying Step 2 on [5,0,8,1]`.

You can repeatedly perform **Step 2** unless you get the desired number of top players.Your top 5 players for the case in order are

`10,7,9,6,1`

Usually another performance criteria(like points scored) for sorting in **Step 2** is available but I think this one suits if you don't have one.
> -1 votes

---
Tags: algorithms, comparison
---


# Question
Title: Does Dekkers solutions to critical section problem ensure progress?
I was reading concurrency control section from Operating Systems book by William Stallings. In this book, he gives three attempts by Dekker to give solution to critical section problem:

**Attempt 1**

```
+------------------------+------------------------+
| //process 0            | //process 1            |
| while (flag[1]);       | while (flag[0]);       |
| flag[0] = true;        | flag[1] = true;        |
| /* critical section*/; | /* critical section*/; |
| flag[0] = false;.      | flag[1] = false;.      |
+------------------------+------------------------+

```

**Attempt 2**

```
+------------------------+------------------------+
| //process 0            | //process 1            |
| flag[0] = true;        | flag[1] = true;        |
| while (flag[1]);       | while (flag[0]);       |
| /* critical section*/; | /* critical section*/; |
| flag[0] = false;       | flag[1] = false;       |
+------------------------+------------------------+

```

**Attempt 3**

```
+-----------------------+-----------------------+
| //process 0           | //process 1           |
| flag[0] = true;       | flag[1] = true;       |
| while (flag[1])       | while (flag[0])       |
| {                     | {                     |
|    flag[0] = false;   |    flag[1] = false;   |
|    /* delay */        |    /* delay */        |
|    flag[0] = true;    |    flag[1] = true;    |
| }                     | }                     |
| /* critical section*/ | /* critical section*/ |
| flag[0] = false;      | flag[1] = false;      |
+-----------------------+-----------------------+

```

Which of the above attempts ensure progress requirement of solution to critical section?

Progress requirement is stated as follows in the book by Galvin et al:

> If no process is executing in its critical section and some processes wish to enter their critical sections, then only those processes that are not executing in their remainder sections can participate in the decision on which will enter its critical section next, and this selection cannot be postponed indefinitely.

This is what I feel:

1. Remainder section is code executing after critical section. In attempt 1, if process 0 is busy waiting in `while()`, then it will be unblocked by process 1 by setting `flag[1]` to `false`, which is in remainder section. So this attempt does not seem to ensure progress.
2. This attempt can cause deadlock. So, it may indefinitely postpone decision to let process enter its critical section. Hence, it does not ensure progress requirement.
3. This attempt can cause livelock. So, like attempt 2, it may indefinitely postpone decision to let process enter its critical section and hence, it does not ensure progress requirement.

Am I correct with these points?

**Edit - Adding some attempts by Dekker given in the book**

Need confirmation for these too. I feel none of them ensure progress as above three attempts.

**Attempt 0**

```
+------------------------+------------------------+
| //process 0            | //process 1            |
| while (turn != 0);     | while (turn != 1);     |
| /* critical section*/; | /* critical section*/; |
| turn = 1;              | turn = 0;              |
+------------------------+------------------------+

```

**Attempt 4 - Final attempt**

```
+--------------------------------+--------------------------------+
| //process 0                    | //process 1                    |
| while (true) {                 | while (true) {                 |
|     flag [0] = true;           |     flag [1] = true;           |
|     while (flag [1]) {         |     while (flag [0]) {         |
|         if (turn == 1) {       |         if (turn == 0) {       |
|             flag [0] = false;  |             flag [1] = false;  |
|             while (turn == 1); |             while (turn == 1); |
|             flag [0] = true;   |             flag [1] = true;   |
|         }                      |         }                      |
|     }                          |     }                          |
|     /* critical section */;    |     /* critical section */;    |
|     turn = 1;                  |     turn = 0;                  |
|     flag [0] = false;          |     flag [1] = false;          |
|     /* remainder */;           |     /* remainder */;           |
| }                              | }                              |
+--------------------------------+--------------------------------+

```

# Answer
> 1 votes
The overall structure of the processes is modelled to be like:

```
while(TRUE) {
   /** get exclusive access */
   /* critical section is here */
   /** release exclusive access */
   /* remainder, i.e., non-critical section */
}

```

You are right, the remainder is outside of the critical section. A real process alternates between critical section/remainder.

None of the alternatives ensures some process will eventually enter the critical section, the other one might loop around and attempt entering again while this one is waiting.

---
Tags: operating-systems, concurrency, synchronization, deadlocks, critical-section
---


# Question
Title: In Big-O notation, what does it mean for T(n) to be upper bounded by something
I do not have much experience in mathematics but I would really like to grasp Big-O notation on its mathematical level. I already read What does the "big O complexity" of a function mean? from references, but I still do not understand (even graphically), what does it mean when we say:

> T(n) = O(f(n)) if and only if there are constants c and g such that: T(n) \<= c\*f(n), where n\>=g

Specifically, we say that `T(n)` is upper bounded by `c*f(n)`. What does that actually mean and why does it matter? Does it have to do with eliminating constant factors and low-ordered terms?

Sorry if question is kind of confusing, and thanks for the help!

# Answer
> 2 votes
Try it like this: "we can pick a constant $C$ such that, for sufficiently large $n$, $T(n)$ will always be less than $Cf(n)$".

Intuitively, this does indeed mean that lower-order terms and constant factors don't matter. Because lower-order terms stop mattering once $x$ gets sufficiently large, and constant factors can be cancelled out by an appropriate choice of $C$. If $T(n) = n^3 + 2019n^2 + 99999n + 10^{10}$, for example, that will still *eventually* be dominated by $Cn^3$, as long as $C \> 1$ and $n$ is large enough—the $n^3$ term in that expression will eventually outweigh everything else. So we say that $T(n) \in O(n^3)$. (Some people use an equals sign instead; the meaning is the same.)

The "sufficiently large $n$", by the way, is why it's called "asymptotic" complexity: we only care about what happens as $n$ goes toward infinity, not what happens for "small" values.

# Answer
> 0 votes
The clearest explanation (with a lot of applications) I've seen is Hildebrand's "A short course in asymptotics". Somewhat heavy going, and more targeted at analysis/number theory than computer science.

The concepts aren't really too hard, but wrapping your mind around them is critical for computer science.

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


# Question
Title: Is this a correct way to thing about asymptotic notations?
I am reading a book on algorithms. It says that $2n^2+3n+1=2n+\Theta(n)$. For a person like me who has studied some set theory but not from axioms, this notation seems a bit insane. I was wondering why are we allowed to compute a sum of a polynomial and a set. Why not just teach that for every $n\in\mathbb N$ there is a $f:\mathbb N\to \mathbb N$ such that $f\in \Theta(n)$ and $2n^2+3n+1=2n+f$? Is this a formally correct way to think $\Theta$ notation? Or should I learn some other book to learn O-notations, like J.D. Murray: Asymptotic analysis? Or do I have some misunderstanding that becomes clear if I first learn some book of axiomatic set theory?

# Answer
> 2 votes
The answers and comments by other users here do a good job of explaining *how* the notation works, so I figure I'll explain *why* the notation is used this way. The reason for the notation is already evident in your question: **writing out the set inclusion explicitly makes it way more verbose.**

When you are learning asymptotic notation for the first time, it is helpful to clearly state that $O$, $\Theta$, etc. are not functions and that "equality" does not behave like equality in statements involving these symbols. But when you are an expert in a field reading a hundred-page paper written by other experts in the same field to communicate with their kin, you really don't want to have to read this kind of boilerplate over and over again if you can avoid it.

The purpose of asymptotic notation is to allow the author to state theorems and intermediate steps in an extremely compact fashion. When you read something like $f(n) = 5n^3 + 3n^2 + o(n^2)$, what you are really reading is, "$f(n)$ is equal to $5n^3 + 3n^2$ plus a bunch of junk that *neither you nor I have time to care about* because it is sufficiently small that its exact value is irrelevant to the correctness of the rest of the argument I am about to present". Writing everything out in terms of statements about sets would obscure the point the author is trying to communicate.

# Answer
> 1 votes
The clearest, most complete, introduction to asymptotics I've yet found is Hildebrand's "Short Course on Asymptotics". Somewhat heavy going, but nailing the concepts down is crucial.

BTW, $2 n^2 + 3 n + 1 = 2 n + \Theta(n)$ is clearly wrong, it presumably was meant to be $2 n^2 + 3 n + 1 = 2 n^2 + \Theta(n)$

---
Tags: landau-notation
---


# Question
Title: Why assume Turing machine can compute arbitrary results in Kraft-Chaitin theorem?
The Kraft-Chaitin theorem (aka KC theorem in Downey & Hirschfeldt, Machine Existence Theorem in Nies, or I2 in Chaitin's 1987 book) says, in part, that given a possibly infinite list of strings $s\_i$, each paired with a desired program length $n\_i$, there is a prefix-free Turing machine s.t. there is a program $p\_i$ of length $n\_i$ for producing each $s\_i$, as long as $\sum\_i 2^{-n\_i} \leq 1$. The list of $\langle s\_i, n\_i \rangle$ pairs is required to be computable (D&H, Chaitin) or computably enumerable (Nies).

The proofs in the above textbooks work, it seems, by showing how to choose program strings of the desired lengths while preserving prefix-free-dom. The details differ, but that construction is the main part of the proof in each case. The proofs don't try to explain how to write a machine that can compute $s\_i$ from $p\_i$ (of course).

What I'm puzzled about is why we can assume that an infinite list of results can be computed from an infinite list of *arbitrarily* chosen program strings using a Turing machine that by definition has a finite number of internal states. Of course many infinite sequences of results require only finite internal states; consider a machine that simply adds 1 to any input. But in this case we're given a countably infinite list of *arbitrary* results and we match them to *arbitrary* (except for length and not sharing prefixes) inputs, and it's assumed that there's no need to argue that a Turing machine can always be constructed to perform each of those calculations.

(My guess is that the fact that the list of pairs is computable or c.e. has something to do with this, but I am not seeing how that implies an answer to my question.)

# Answer
Let's take the example in which $n\_i = i + 1$. In this case, we can choose the $i$'th program to be $0^i1$. Here is how the prefix-free Turing machine works. It reads the input, and determines $i$. Now it runs a Turing machine which enumerates the list $\langle s\_j,n\_j \rangle$ until it reaches $\langle s\_i, n\_i \rangle$, at which point it outputs $s\_i$.

More generally, we choose the programs (i.e., the potential inputs to the prefix-free Turing machine) in such a way that we can effectively convert a program $p\_i$ to an index $i$. In other words, contrary to what you write, the programs are *not* arbitrary, only their lengths are. In general the conversion from program to index might require partial knowledge of the sequence $n\_i$.

The actual programs can be constructed greedily. See for example lecture notes of Satyadev Nandakumar, proof of Theorem 3.3.5.
> 4 votes

# Answer
Here's a way to construct a machine that computes $s\_i$ from an input $p\_i$ that has length $n\_i$. It's based on @YuvalFilmus's very helpful answer and the proof of a related theorem by Satyadev Nandakumar, to which Yuval linked. I thought it might be useful to spell out the steps a bit further for anyone else interested in this question--at least, anyone whose insight is impoverished like mine . :-)

As stated in the question, Nies' (*Computability and Randomness*, theorem 2.2.17, pp. 88f) Machine Existence (Kraft-Chaitin) Theorem assumes that we're given a c.e. set of pairs $\langle s\_i, n\_i \rangle$, where $s\_i$ is to be a result of a computation, and $n\_i$ is the length of the input program string that will cause $s\_i$ to be computed. (There is an additional important requirement on the $n\_i$ that's not relevant to my question.) As I noted in the question, most of Nies' proof consists of showing how a set of input strings $p\_i$ can be effectively chosen so that they are prefix-free, but he doesn't spell out explicitly how to use this fact to generate the machine that the theorem claims exists.

> When an input $p$ to the machine is received, store it on a tape. Then begin enumerating the pairs $\langle s\_i, n\_i \rangle$.
>
> As each pair is generated, use the newly generated $n\_i$ to generate the next prefix-free input string $p\_i$ of that length. (Nies' algorithm generates each prefix-free input string directly from a newly given length $n\_i$ along with a set of book-keeping strings generated during the construction of previous strings. There's no reason this procedure can't be interwoven with the generation of the pairs.) Then check whether the original input string $p$ is equal to this newly-generated string $p\_i$. If so, output $s\_i$ and halt. If not, keep looking: go back to the beginning of this paragraph.

(If the set of pairs $\langle s\_i, n\_i \rangle$ is infinite, it may be that $p$ is never found among the $p\_i$'s, and the process will therefore run forever, in which case the machine only computes a partially computable function.)

In answer to my original question, the above procedure shows that given the assumption that the set of "request" pairs is c.e., a normal finite-state Turing machine is all that's needed. Most of the heavy lifting of constructing the outputs $p\_i$ is already present in the original computable enumeration of pairs method, which is available by assumption.

(I suspect that the same construction will work with the prefix-free-string-generation algorithms in other proofs of the Kraft-Chaitin theorem, but I have not checked carefully.)
> 0 votes

---
Tags: turing-machines
---


# Question
Title: Can we find a Turing machine such that there is no Turing machine to decide whether it halts on $\epsilon$?
The halting problem states that there is no Turing machine that can determine whether an arbitrary Turing machine halts on $\epsilon$. But I try to ask something different, can we find a specific Turing machine $M$ such that $L\_M=\\{ 0^n : M$ halts on $\epsilon \\}$ is undecidable? Or at least can we prove there exists such $M$?

The language itself isn't the issue, it is either $L=\\{0^n : n \in \mathbb{N} \\}$ or $L=\phi$ and the way to distinguish the cases is only by the right side of the definition of $L$.

In other words, can we define a Turing machine such that we (or a Turing machine) can't determine whether it halts or not on $\epsilon$?

# Answer
> 4 votes
Suppose you had such a TM, namely a machine $M$ for which the problem was "Does $M$ halt on empty input?" Certainly that problem would be decidable: one of two algorithms must be correct, (1) Answer "yes" or (2) Answer "no". The fact that we might not know which one is the correct algorithm is immaterial here; the only thing that matters is that we're sure *one* of the algorithms is the right one, so we know the problem is decidable. In more general terms, *any decision problem with a finite number of instances is decidable.*

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


# Question
Title: How Intersection of Regular Language and a CFL is a CFL?
CFL is not closed under intersection. That means, if we have L1,L2 of CFL then

```
L1 intersection L2 is not a CFL

```

And we know, all Regular languages are CFL. Then how it is true that intersection of Regular language (R1) (which is again a CFL) and a CFL(CL1) is a CFL?

```
R1 intersection CL1 should not be CFL right? becase R1 is again a CFL.

```

# Answer
> 3 votes
Every CFL language can be describes as a PDA. Every regular language can be described as a DFA.

The orthogonal product of a DFA and PDA can be defined as follows:

The new states of the automaton are all $(q\_{PDA}, q\_{DFA})$. That start state is $(s\_{PDA}, s\_{DFA})$ and the final states are all $(f\_{PDA}, f\_{DFA})$ where $f\_{PDA}\in F\_{PDA}$ and $f\_{DFA} \in F\_{DFA}$.

Given the transition of the PDA defined as $\delta\_{PDA}(q\_{PDA}, stack\_{PDA}, a) = (q'\_{PDA}, stack'\_{PDA})$ and transition function of the DFA $\delta\_{DFA}(q\_{DFA})$

The transition function $\delta(q, a)$ for the new Automaton is where the transition function of the PDA is defined defined as $\delta((q\_{PDA}, q\_{DFA}), stack\_{PDA}, a) = ((q'\_{PDA}, \delta\_{DFA}(q\_{DFA})), stack'\_{PDA})$

(in laymans terms, split out the states simulate the DFA and PDA independently and only accept the language when both are in a final state)

There is only 1 stack in this automaton. Thus it is a valid PDA. Therefor the language described by the intersection of a CFL and a regular language is a CFL.

The reason this does not hold for the intersection of 2 CFLs is because you need a second stack for second PDA.

# Answer
> 0 votes
The sticking point is in the first statement:

> CFL is not closed under intersection. That means, if we have L1,L2 of CFL then
>
> > L1 intersection L2 is not a CFL

This is not what non-closure means. What it actually means is that the intersection of two languages from a given set *may* not be in the given set, so in this case "CFL is not closed under intersection" means that given two context free languages, their intersection might not be a context free language.

For many context free languages however,their intersection is context free.

As you note, and as Ratchet Freak proves, the intersection of a context free language and regular language is context free.

We can make more complicated examples though:

Let $L\_{1} = \\{0^{n}1^{n}\\#0^{m}1^{k} \mid n,m,k \in \mathbb{N}\\}$ and $L\_{2} = \\{0^{n}1^{m}\\#0^{k}1^{k} \mid n,m,k \in \mathbb{N}\\}$, then $L\_{1} \cap L\_{2} = \\{0^{n}1^{n}\\#0^{m}1^{m}\\}$, which is still context free, and both $L\_{1}$ and $L\_{2}$ are non-regular, so there's no extra restriction leading to the intersection being context free.

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


# Question
Title: NP-Complete reductionTrue/False question explanation
Why is the above statement true? my understanding is:

(1)3SAT reduces to X implies X is NP-complete or harder.

(2)Set Cover reduces to X implies X is neither NP-Complete nor harder.

This contradiction gets me a bit lost as to why the conjunction of 1 and 2 implies that X exists in P. I'm hoping someone can explain this to me. Note: both 3SAT and Set Cover are NP-Complete.

# Answer
Your understanding is correct, but the takeaway here is that assuming the contradictions implies that anything can be true. Perhaps reading up on some logic rules might help, the important rule here is that $\bot$ (false) implies everything. Here is a little proof of the problem just for fun:

We know that both **3-SAT** and **Set Cover** are NP-Complete problems. Now, assume that **3-SAT** $\leq^{m}\_P$ **X** and that **Set Cover** $\nleq^{m}\_P$ **X**. We want to show that **X** $\in$ **P**.

Since both **3-SAT** and **Set Cover** are NP-Complete problems, we know that **Set Cover** $\leq^{m}\_P$ **3-SAT**. We also know that **3-SAT** $\leq^{m}\_P$ **X**. By the transitive property of reductions, we know that **Set Cover** $\leq^{m}\_P$ **X**. Now we know that **Set Cover** $\leq^{m}\_P$ **X** and **Set Cover** $\nleq^{m}\_P$ **X**, which is a contradiction. Since false implies everything, we can say that **X** $\in$ **P**. (In fact we can also say that pigs can fly faster than superman can)

Q.E.D.
> 1 votes

---
Tags: np-complete, np-hard, np
---


# Question
Title: Showing that the number of primitive-recursion programs for each function is countably-infinite
## Problem Statement

> Prove that if a function $f$ is primitive recursive, then there are *countably* infinite number of primitive recursive definitions of $f$

Yes, this is a homework question.

## My Work

I proved that there are infinite number of definitions using the following construction

$$g\_k(n) = \underbrace{P\_{1}^1(P\_{1}^1( \dots( P\_{1}^1}\_{k \text{ times}}(f(n))\dots), \ \forall \ k \in \mathbb{N}$$

Here $P\_1^1$ is the projection basis function which picks the $1^{\text{st}}$ element from a vector of size $1$

Now $k$ is unbounded and we will get an equivalent definition for $f$ for each $k$

Now the issue is that this is not the only way to construct an infinite number of equivalent definitions i.e. I could have also use the multiplication operator and multiplied the output of $f$ by 1 as many times as I liked.

How can I show that there is a $1-1$ correspondence of the set of all primitive recursive definitions with the set of naturals numbers? Unlike bit strings, I am unable to comprehend in what way I should assign some number to each function. In fact I don't even know in how many ways can I create equivalent definitions, so how can I even start to enumerate these functions?

Any hints?

# Answer
> I proved that there are infinite number of definitions using the following construction

That works in principle, but be careful about what $f$ is in that term, *formally*.

> Now the issue is that this is not the only way to construct an infinite number of equivalent definitions

Right you are!

> How can I show that there is a 1−1 correspondence of the set of all primitive recursive definitions with the set of naturals numbers?

You don't have to do this explicitly. Use that the class of countable sets is closed against taking subsets.
> 1 votes

# Answer
Suppose we are given a primitive recursive function $f$. Let us define the following sets: \begin{align\*} A &= \text{"the set of all finite strings of symbols"} \\ B &= \text{"the set of all finite strings of symbols that define a primitive recursive function"} \\ C &= \text{"the set of all finite strings of symbols that define $f$"} \end{align\*} Obviously we have $$C \subseteq B \subseteq A$$ You already know that $A$ is countably infinite. In your solution you constructed a countably infinite subset of $C$. Therefore, all three sets $A$, $B$ and $C$ are countably infinite. This is so because:

> **Theorem:** If $X \subseteq A \subseteq Y$ and both $X$ and $Y$ have the same cardinality then $A$ has that cardinality as well.
> 1 votes

# Answer
For any set of functions $X$, let $f(X)$ be the set of functions including

1. all the initial functions
2. the (generalized) composition of any functions in $X$
3. the functions obtained from any $f,g \in X$ by applying the primitive recursion scheme on $f,g$.

If we consider $$ \emptyset \cup f(\emptyset) \cup f(f(\emptyset)) \cup ... = \bigcup\_{n \in \mathbb N} f^n(\emptyset) $$ we build the exactly the set of primitive recursion functions. This is easy to check (and is also an immediate application of Kleene's fixed point theorem in domain theory).

Now, every set $f^n(\emptyset)$ is countable, and a countable union of countable set is also countable.

Note that this argument is applicable not only to the definition of the PR functions set, but to many inductive definitions as well. Indeed, we only need that $f(X)$ is countable when $X$ is such. In computer science, this happens very frequently.
> 0 votes

# Answer
Just define a function $a(n)$ that adds 1 to non-zero (i.e., $a(n) = \operatorname{if} n = 0 \operatorname{then} 0 \operatorname{else} n + 1$) and another one $s(n) = \operatorname{if} n = 0 \operatorname{then} 0 \operatorname{else} n - 1$. For any given function $f(n)$, there are an infinite collection of functions computing the same result, like $s(a(f(\ldots))$, where the $s(a(\ldots))$ game can be repeated as often as you like.
> 0 votes

---
Tags: computability, combinatorics, primitive-recursion, uncountability
---


# Question
Title: is the problem of parallelising any program, NP-complete?
Consider a program written in a common language such as C. Assume that it does not have any explicit parallel constructs. Then, once it is compiled to an executable program, it will be run serially, even if the machine has multiple processors.

Now, suppose we wanted theoretically to write a "parallel compiler", which would analyze such a program and figure out what operations are safe to execute concurrently, and output an executable which would run in parallel on multiple processors, so that, no matter the timing between these threads, the program in the end will come up with the same results as with "serial compiler".

I am guessing that such a compiler, if possible, would need a very long time to calculate - I am guessing that the problem "parallelize an arbitrary program" must be at least NP-complete (possibly exp). Is that known, and if so, is that true, and if so, can you point me to a published argument?

---

Let me try and formalize the problem better. Assuming each instruction emitted by the compiler executes in unit time, then for a given number of processors, and assuming the processors communicate and access memory instantly, given that some instructions will depend on others, there is theoretically the shortest possible time to complete the program.

Let's say we want our compiler, maybe not reach this theoretical limit, but come up with instructions that will take up to 2x the theoretical limit.

# Answer
> 5 votes
It is not clear what exactly you want of that compiler, so let me explore several possibilities.

### Optimize the parallelism

This is impossible. Optimizing even sequential runtime is not computable, and a similar proof shows the same for parallel runtime. The proof also extends to any notion of "almost optimal" like within a constant factor or something similar.

Thus, any notion of parallelization in this direction is not even in NP, and it's not even close.

### Get *some* parallelism

Without defining exactly what "some" means we can not classify the problem in terms of complexity. There are certainly things that modern compilers can do, for instance vectorize suitable `for`-loops -- but all of these are certainly not NP-hard to detect (or they wouldn't do them).

I'm certain that you can carefully define some parallelization feature that is NP-complete to detect. I'd especially look towards coarse-grained parallelism, though exploiting that requires serious rewrites of code.

### Do anything

That's trivial and hence boring. For instance, standard data-flow analyses will identify (sub)sequences of statements that are independent and can thus be reordered or, in principle, be executed in parallel. This will get you some very fine-grained parallelism that may not even gain you a speed-up, and will certainly not scale to many processors, but well.

Some language have features to tell the compiler that two things are independent, e.g. method calls, and that way lies potential gain. Then it's easy for the compiler again, though.

# Answer
> 2 votes
You'd need to define exactly what you mean by "parallelize". Besides, finding a parallelization (what a compiler is presumably asked to do) is a search problem, while NP is a set of decision problems. Search problems can't be "NP complete", they are a different kettle of fish. Sure, problems in NP often have corresponding search problems (see for example Bellare's "Decision vs search"), and if one is hard the other is too. Let's be loose with language and talk about "NP hard search problems" if the corresponding decision problem is NP hard.

Compilers "solve" NP hard search problems as a matter of course all over the place. But they usually only consider a subset of the full problem (lower-hanging fruit, if you will), use approximate solutions, or outright heuristics that "usually work in the programs seen in practice". A fascinating glimpse at the problems tackled and how they are addressed is given by one of LLVMs researchers, John Regher in his blog.

---
Tags: complexity-theory, compilers, parallel-computing, program-optimization
---


# Question
Title: Can algorithm discovery be brute forced?
Ultimately, when you compile them to machine code, algorithms are just 1's and 0's. So then - could you brute force the genesis, and thus the discovery of new, useful algorithms? Say, in pursuit of polynomial time algorithms for NP-complete problems.

Of course, rather than pure brute force, perhaps some intelligent force could be applied as a refinement.

---

My back-of-the-napkin-ish attempt to answer the question. Just an exercise; I don't really trust it.

1. In theory, yes - absolutely. The question is whether, in practice, it could be done in a reasonable amount of time in a cost-effective manner.
2. The amount of possible permutations of 1's and 0's is $2^n$ where n = the number of bits in your code.
3. Roughly how many bits does it take to write algorithms? To answer this question, I googled for a quick sort implementation in c, and compiled it to machine code. The result was about 10,000 bytes. So 80,000 bits. Let's say 100,000 bits for a round number.
4. There are $2^{100,000} = 10^{30,103}$ permutations of 1's and 0's.
5. You'd have to test each of these permutations. Let's say it takes 1 minute to test a permutation of 1's and 0's. Then that'd take $10^{30,097}$ *years* to finish testing. No good.
6. Perhaps the parameters could be tweaked. Let's try just 1,000 bits and 1 second to test each permutation. $2^{1000} = 10^{301}$ permutations. That'd take $10^{295}$ years.
7. Even if we used a lot of computing power, that'd still only cut the exponent down by 5 or 10, maybe. So ultimately, it seems impractical to actually brute force. The question then becomes whether we can combine intelligent force with brute force in algorithm generation.
8. Even though brute force seems impractical, I wonder if future generations will have insane computational power that we would never dream of. If so, brute forcing algorithm generation may be possible. Of course, they may have figured out all the algorithms by then.

# Answer
> 4 votes
You are correct in saying that algorithms are no more than a sequence of strings. However, you should make the distinction between syntactic and semantic properties of the algorithm. Syntactic properties are those relating to the actual code, e.g. what is the length of the program? how many "while" loops does it contain? Semantic properties are related to what the program actually does, e.g. is there some input that would cause this program to go into an infinite loop?

The problem you encounter in your suggestion is that almost every interesting semantic property is undecidable, meaning that even with unlimited resources (time/memory) you cannot algorithmically reason about this property just by looking at the source code. So in fact, the situation is worse than what you think. Even the craziest hardware won't help us, since such tasks are impossible for a computer.

As a side note, suppose your situation was better, and you try to cope with some decidable problem which has an exponential lower bound (i.e. all algorithms for this problem would require exponential time, not just brute force search, even the "smart" ones). Again, better hardware won't help you. For some intuition regarding your parameters, you have $\approx 10^{80}$ atoms in the universe, so performing this amount of operations is hopeless. What you need is a smarter algorithm, but we started with a problem that unfortunately has an exponential lower bound.

# Answer
> 1 votes
Work in somewhat that direction is superoptimization, take a short stretch of machine instructions and search for a shorter/faster one doing the same. The hard part is to check that they really have the same effect. It is a very expensive process, even for it's extremely narrow objective.

# Answer
> 0 votes
It seems that you answered your question. As you stated in 2 your search space has the size of $2^n$, which obviously leads you towards a non polynomial time. Even if you will use some kind of a smart search on this problem that, for example, reduces the search space by the factor of 100 you will still end with a non polynomial size of the search space.

Unless P=NP, you have an algorithm that reduces the search space exponentially or some kind of hardware that works in a totally different way (for example a quantum computer. I don't know if it can help solve this particular problem but there are other problems that have similar complexity that it will solve in reasonable time) you won't be able to solve this problem in a reasonable time.

---
Tags: algorithms, correctness-proof
---


# Question
Title: Probability of terminating in a state in a probabilistic algorithm
Suppose i have a circular array of $n$ elements. At time $t=0$ i am in position 0 of the array. The algorithm moves left or right with probability $p=1/2$ (since the array is circular when it moves left from 0 it goes to position $n$). When i visited all the positions at least once the algorithm returns the position it terminated into.
Launching the algorithms many times shows that it stops with the same probability in any of the n positions (except for zero obviously). **How do i demonstrate that the probability of ending up in each state is uniform?**
My understanding is that this process is explained by a doubly stochastic Markov chain, but is there a theorem i can quote about this specific case?

# Answer
We can imagine simulating the random walk on an infinite line, keeping track of the "extension", which is the distance between the rightmost point visited and the leftmost point visited. Let $\ell(a,b)$ denote the probability that the extension became $b-a$ due to a move to $a$, and let $r(a,b)$ denote the probability that the extension became $b-a$ due to a move to $b$. When $a=b=0$, we arbitrarily define $\ell(0,0) = 1$ and $r(0,0) = 0$.

If we are at the situation counted by $\ell(a,b)$, then known formulas show that we move to the situation counted by $\ell(a-1,b)$ with probability $1-1/(b-a+2)$, and to the situation counted by $r(a,b+1)$ with probability $1/(b-a+2)$. Together with an analogous argument for $r(a,b)$, this gives the recurrences $$ \ell(a,b) = \left(1 - \frac{1}{b-a+1}\right) \ell(a+1,b) + \frac{1}{b-a+1} r(a+1,b), \\ r(a,b) = \frac{1}{b-a+1} \ell(a,b-1) + \left(1 - \frac{1}{b-a+1}\right) r(a,b-1). $$ We want to show that for $i=1,\ldots,n-1$, $$ r(i-n+1,i) + \ell(i-n,i-1) = \frac{1}{n-1}. $$ We will prove the stronger result $$ r(i-n+1,i) = \frac{i}{n(n-1)}, \\ \ell(i-n,i-1) = \frac{n-i}{n(n-1)}. $$ When $n=2$, we need to show $$ r(0,1) = \ell(-1,0) = \frac{1}{2}, $$ which can be checked directly. For $n \> 2$, we have $$ r(i-n+1,i) = \frac{1}{n} \ell(i-n+1,i-1) + \frac{n-1}{n} r(i-n+1,i-1) = \\ \frac{1}{n} \frac{n-i-1}{(n-1)(n-2)} + \frac{n-1}{n} \frac{i-1}{(n-1)(n-2)} = \frac{i}{n(n-1)}, $$ and similarly $$ \ell(i-n,i-1) = \frac{n-1}{n} \ell(i-n+1,i-1) + \frac{1}{n} r(i-n+1,i-1) = \\ \frac{n-1}{n} \frac{n-i-1}{(n-1)(n-2)} + \frac{1}{n} \frac{i-1}{(n-1)(n-2)} = \frac{n-i}{n(n-1)}. $$ (We don't really need to calculate the two cases separately, since symmetry arguments show that $r(i-n+1,i) = \ell(-i,n-i-1)$.)
> 3 votes

---
Tags: algorithms, probability-theory, matrices, probabilistic-algorithms, markov-chains
---


# Question
Title: Why is $O(|V| + |E|)$ the bound on DFS and BFS instead of just $O(|E|)$?
In one sense I understand why the bound on BFS and DFS is $O(|V| + |E|)$. Every vertex gets considered, hence the $O(|V|)$, and over the course of considering all adjacent vertices, we end up considering $2|E| = O(|E|)$ vertices total because $\sum\_{v \in V} d\_v = 2|E|$. What I don't understand is why we even bother specifying $O(|V| + |E|)$ in the first place because it seems to me that the tightest bound you can really have in any situation is $O(|E|)$. I.e., it seems to me that the $O(|V|)$ doesn't help you at all. To see why, consider two cases:

* The graph is connected. Then of course $|E| \ge |V - 1|$.
* The graph isn't connected. Then you are "stuck" in the connected component you start in. Once again, inside the connected component $A$ you start in you have $|E\_A| \ge |V\_A - 1|$. Maybe there are more edges and vertices elsewhere. But once again the $O(|V|)$ seems redundant.

Another way I think about it: Adding a vertex alone doesn't create any more work since the vertex will just be floating in space. Adding edges can create extra work.

So why/when is the $O(|V|)$ useful?

# Answer
You have missed an important element of graph search: the outer loop.

Here is typical pseudocode for a graph search algorithm:

```
S <- new empty set
T <- new empty set
for each vertex u in V:
    add u to T
    while T is not empty:
        v <- remove some element from T
        add v to S
        do something with v
        for each vertex w that is adjacent to v:
            if w is not in S and not in T:
                add w to T

```

Notice the outer loop on the variable `u`. This loop is present in some descriptions of DFS/BFS/etc. and absent in others. Why is this? The answer is that graph searches are used for different purposes. Sometimes, you have a particular start vertex `u` and you just want to search for everything that is reachable from `u`. However, other times you are using the graph search to *find* the connected components of the graph, or as part of an algorithm for computing some other property of the entire graph such as biconnected components. In these cases, the outer loop is necessary.

The crucial special property of graph search is that, even with the outer loop, *the runtime is still bounded by* $O(|V| + |E|)$, and not just by $O(|V| \cdot |E|)$. This property is what makes efficient algorithms possible for computing connected components, etc.

---

It's also worth noting that the $O(|V| + |E|)$ bound assumes that the white/gray/black status of a vertex (i.e. which set it is in) can be checked and modified in $O(1)$ time. This can be achieved by creating an array of size $V$, or by attaching a flag to each vertex; either way, it takes $O(V)$ time to initialize all the vertices into the white set at the start of the algorithm. If you don't use one of these methods, you probably have to add a logarithmic overhead for tracking the vertices in set data structures. This is true even in cases where you don't need the outer loop.
> 3 votes

# Answer
I think you have answered your own question to some extent. Let $G$ be a graph with $V$ is the vertex set and $E$ is the edge set. Let $G$ is not connected, $|E| = \mathcal{O}(\log |V|)$. In this case runtime of BFS/DFS will be $\mathcal{O}(|V| + \log |V|)$ not $\mathcal{O}(\log |V|)$. If $|E| = \mathcal{O}(V)$ then there is no difference between $\mathcal{O}(|V|+ |E|)$ and $\mathcal{O}(|E|)$.

Here is case where writing $\mathcal{O}(|V|)$ is considered as a good than measuring complexity in terms of $\mathcal{O}(|V| + |E|)$. Let $G$ be a undirected graph and we want to find whether $G$ have a cycle or not. The complexity of this problem is $\mathcal{O}(|V|)$. This question can be found in the exercise section of Graph Search Algorithms of book Introduction to Algorithms by Coreman et.al.

**Note:** Adding a vertex cost you if you add vertices in large numbers. Let us consider the case where $|V| = |E|$ and you keep adding the veritces without adding edges such that new graph(with $V'$ vertex set and $E'$ edge set) have $|V'| = |E|^2$. Although you have not added any single edge still runtime increases by a large factor.
> 1 votes

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


# Question
Title: Calculating match % and ranking according to that
I'm creating a website like where users will answer some yes/no questions set by me, up to them how many of those questions they want to answer. After a user submits his answer(s), he will be shown top 5 matches along with their match percentages. If two users have 10 common questions and their answers match for 8 of those questions then their match % will be 80%.

I can make this but my concern is about efficiency. A way of making this: If a user wants to see his top matches then match % (or match ratio) will be calculated for him vs every other user in the system. This will be stored in a temporary array. Array is sorted. Top 5 matches from the array are displayed.

Any less resource intensive way to calculate and show top matches?

Edit: If the top matches can be calculated without first calculating match percentages then i'm open to that.

# Answer
There is probably no algorithm that is significantly better than doing a pairwise comparison between all pairs of users.

You can, as you say, memoize (remember) the top-5 match for each user, so that you never have to recompute the top-5 for that user again in the future, but you'll still need to compare that user to each other user at least once. Basically, each time a new user appears, you compare them to all other users, to compute their top-5 matches (and update the top-5 matches of other users by adding this user to the top-5 lists of other users where appropriate).

That's basically the brute-force algorithm. I don't expect there to be an alternative that is better in practice.

---

In principle, there are a variety of methods. One method is to use a locality-sensitive hash. The simplest form of LSH is to choose a random subset of questions, then for each user extract their answers to those questions, hash that, and store the user in a bucket associated with the user's hash value. Then two users who are very similar have a decent chance of ending up in the same bucket. If you construct 100 such data structures, each with a different subset of questions, and if you choose the parameters right, you might have a decent chance of finding all of the top-5 matches in this way (along with some other extraneous matches, but those can be filtered out by doing a full comparison for each potential match). However, this is pretty fiddly with respect to parameters, and if people tend to answer only some of the questions, I suspect it won't perform that well in practice.
> 1 votes

# Answer
Regarding my "A way of making this",
Instead of array, building min heap of max 5 elements for top 5 matches is a better way. This heap will be populated when match %s are being calculated.
> 0 votes

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


# Question
Title: Graph problem known to be $NP$-complete only under Cook reduction
The theory of NP-completeness was initially built on Cook (polynomial-time Turing) reductions. Later, Karp introduced polynomial-time many-to-one reductions. A Cook reduction is more powerful than a Karp reduction since there is no restriction on the number of calls to the oracle. So, I am interested in NP-complete graph problem that does not have a known Karp reduction from a NP-complete problem.

> Is there a natural graph problem known to be $NP$-complete only under Cook reduction, but not known to be NP-complete under Karp reductions?

Naturalness should disallow specific features of feasible solutions, for otherwise it is quite easy to start from well-known problem and make it a little easier by allowing specific features.

# Answer
I know an example of a problem that is missing two of the four features you ask for - it is not NP-complete, and it is not a problem on graphs.

Buchfuhrer and Umans (2011) show that the minimum equivalent expression problem in Boolean logic is complete for $\Sigma^P\_2$ under polynomial-time Turing reductions.

Given a Boolean $(\wedge;\vee;\neg)$-formula $F$ and an integer $k$, is there an equivalent $(\wedge;\vee;\neg)$-formula of size at most $k$?

On p. 143, the authors state:

> This provides a somewhat rare example of a natural problem for which a Turing reduction seems crucial (in the sense that we do not know of any simple modification or alternative methods that would give a many-one reduction).

They do not cite any other such examples from the literature. I suspect that "somewhat rare" is possibly an understatement.

**References**

David Buchfuhrer and Christopher Umans: "The complexity of Boolean formula minimization" Journal of Computer and System Sciences, Volume 77, Issue 1, January 2011, Pages 142-153
> 4 votes

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


# Question
Title: Finding minimal strongly connected graph
I have this question: Given a strongly connected and directed graph $G = (V,E)$ with positive weights define $E(t)$ to be the group of edges whose weight is at most $t$. Find an algorithm that calculates the minimal $t$ such that $G(t) = (V,E(t))$ is strongly connected.

I thought about running Dijkstra $v$ times from every vertex and then all of the edges will be the minimal $t$ but I am not sure the time complexity is the best. Is there a better solution for this problem?

# Answer
> 1 votes
We can solve the problem in $\mathcal{O}(E \log V)$ by binary search.

We can identify the strongly connected components in a graph in linear ($\mathcal{O}(V + E)$) time. Thus we can check if the graph is strongly connected in linear time.

If $G(t\_{0}) = (V, E(t\_{0}))$ is strongly connected, so is $G(t) = (V, E(t))$ for $t \geq t\_{0}$. Further, if $G(t\_{0})$ is strongly connected, so is $G(t)$ where $t$ is the maximum edge weight that is at most $t\_{0}$. Thus we can binary search for $t$ over all edge weights.

The algorithm is:

1. Sort edges by weight. Let $w\_{i}$ be the $i$th smallest edge weight (1-indexed). Set $w\_{0} = -1$.
2. Initialise binary search: set $l = 1$ and $h = |E| + 1$
3. While $l \neq h$:
    * set $m = \lfloor\frac{l + h}{2}\rfloor$. Then, If $G(w\_{m})$ is connected, set $h = m$. Otherwise set $l = m + 1$.
4. If $l = |E| + 1$, no $t$ works. Otherwise, answer $t = w\_{l}$

In the binary search, we maintain the invariant that $G(w\_{h})$ is strongly connected (or $h = |E| + 1$), while $G(w\_{l - 1})$ is not (assuming $|V| \geq 2$). We exit the loop when $l = h$, thus either $l = |E| + 1$ and the graph is not strongly connected for any $t$, or $G(w\_{l})$ is strongly connected, but $G(w\_{l-1})$ is not, thus $G(t)$ is not strongly connected for $t \< w\_{l}$. Thus the algorithm is correct.

The first step takes $\mathcal{O}(E \log E)$ time. The third step takes linear time and is executed at most $\log E$ times. Thus, the complexity is $\mathcal{O}((V + E) \log E) = \mathcal{O}(E \log V)$.

---
Tags: algorithms, graphs, weighted-graphs
---


# Question
Title: Measures of performance in machine learning
I'm new to machine learning and struggle to interpret the results I get from different measures of performance. If for several prediction models I have e.g. accuracy, precision, recall, F1, FPR, and MCC and want to find out which model performs best, what do I look for? I would assume accuracy is most important?

Also, what influence does the error have on the interpretation? E.g. method 1 has an accuracy of 87 +- 5% and method 2 has 84 +- 5% I would assume method 1 to be better. Is that correct?

# Answer
Precision and recall are the two basic measures and most of the other measures can be written in terms of them. If a model has both better precision and better recall, then it can be seen as strictly better than another model. If two models are incomparable in the sense that another has better precision and another has better recall, then it depends on the application which one is better. For some applications it is essential to avoid false positives, and for some applications it is essential to avoid false negatives.
> 4 votes

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


# Question
Title: Breadth First Search Path Finding - Store Paths in Queue or Track Predecessors?
In studying various solutions for finding a path in a 2d maze using BFS, I've come across two different approaches. One is to store the whole path to a given position in the search queue. The other is to keep track of predecessors and build the path at the end by back-tracking.

I'm curious to hear which of these approaches is considered better in which situations. It looks to me like the time and memory requirements for the "store the path in the queue" method would grow much faster than the "predecessors" approach as the maze grows in size. Is that correct?

Below are two implementations in Python showing the different approaches.

```
"""
BFS maze solver.
The queue contains paths.
"""

import collections

offsets = {
    "R": (0, 1),
    "L": (0, -1),
    "U": (-1, 0),
    "D": (1, 0)
}

def bfs(grid, start):
    queue = collections.deque([[start]])
    seen = set([start])
    while queue:
        print("queue:", queue)
        path = queue.popleft()
        print("path", path)
        i, j = path[-1]
        if grid[i][j] == goal:
            return path
        for direction in ["U", "D", "R", "L"]:
            row_offset, col_offset = offsets[direction]
            i2, j2 = i + row_offset, j + col_offset
            if 0 <= i2 < num_rows and 0 <= j2 < num_cols and grid[i2][j2] != wall and (i2, j2) not in seen:
                queue.append(path + [(i2, j2)])
                seen.add((i2, j2))

wall, clear, goal = "#", ".", "*"
num_rows, num_cols = 2, 4
grid = ["S...",
        "#..*"]
path = bfs(grid, (0, 0))

```

"""
BFS maze solver.
The queue contains only positions. Predecessors are kept in dictionary.
"""

import collections

offsets = {
    "R": (0, 1),
    "L": (0, -1),
    "U": (-1, 0),
    "D": (1, 0)
}

def bfs(grid, start):
    queue = collections.deque([start]) #!!
    seen = set([start])
    while queue:
        print("queue:", queue)
        i, j = queue.popleft()
        print("i, j:", i, j)
        if grid[i][j] == goal:
            return (i, j)
        for direction in ["U", "D", "R", "L"]:
            row_offset, col_offset = offsets[direction]
            i2, j2 = i + row_offset, j + col_offset
            if 0 <= i2 < num_rows and 0 <= j2 < num_cols and grid[i2][j2] != wall and (i2, j2) not in seen:
                queue.append((i2, j2))
                seen.add((i2, j2))
                previous[(i2, j2)] = (i, j)

wall, clear, goal = "#", ".", "*"
num_rows, num_cols = 2, 4
grid = ["S...",
        "#..*"]
start_pos = (0, 0)
previous = {}
previous[start_pos] = (-1, -1)
goal = bfs(grid, start_pos)

if goal:
    path = []
    i, j = goal
    while i != -1:
        path.append((i, j))
        i, j = previous[(i, j)]
    path.reverse()
    print("----Node history---")
    for item in previous.items():
        print(item)
    print("----Path----")
    print(path)
```

# Answer
> 1 votes
There's no set answer, as it depends on the number of nodes in the graph, the average number of nodes in the queue at any point in time, and the average length of paths.

"Considered better" is a matter of opinion, and on this site, we focus on technical questions rather than opinion.

If it were me, I would use predecessor pointers as my default, unless I had careful measurements showing that on my workload the other was better.

---
Tags: search-algorithms
---


# Question
Title: Algorithm for determining whether 2 entities of some feature are the same?
I'm trying to think of a way to do approximate joins between 2 rows in a data table. Like for example lets say I have a row where the person name is "John Doe" but then another data table uses a different person format like "Doe, John." Now suppose I can put them both to a standard format say "John Doe." Sweet so I have a way to reference them and let's say there's other data correlated with "John Doe" is there any algorithms out there to infer whether these 2 John Does are the same given the other data columns? You can see the other data columns as features as well, because I know FB has an algorithm to stop duplicates for the same person and StackOverflow will merge accounts if it thinks they're being used by the same person. Any suggestions?

# Answer
I am not able to clearly understand your use case, but from what I infer I believe if you are trying to de-dupe data on other features, the approach would be to use LSH(Locality Sensitive Hashing) you can see the following links to get an overview. hope this helps.

https://stackoverflow.com/questions/12952729/how-to-understand-locality-sensitive-hashing

https://www.cs.utah.edu/~jeffp/teaching/cs5955/L6-LSH.pdf

https://en.wikipedia.org/wiki/Locality-sensitive\_hashing
> 1 votes

---
Tags: search-algorithms, database-theory
---


# Question
Title: What is the lower bound for the following equation
f(n) = 32n^2 + 17n + 1.

The lecture slide says that lower bound can be Omega(n^2) or Omega(n).

Some body please guide me why the lower bound can be Omega (n). i know the upper bound which is O(n^2).

Zulfi.

# Answer
> 1 votes
This is a quadratic function; therefore $f$ is big-Theta of $n^2$. Therefore, it is both Big-O and Big-Omega of $n^2$.

However, when a function $f$ is big-Omega of another function $g$, then $f$'s growth is of greater or equal order than $g$. However, since a quadratic grows strictly faster than a linear in the long run, $n^2$ is big-Omega of $n$. Think of as if big-Omega means "greater or equal than".

Also note when $f$ is big-Omega of $g$, then $g$ is big-O of $f$. Obviously, $n$ is big-O of both $n$ and $n^2$.

---
Tags: asymptotics
---


title: Is the following fuction computable?

text:
# Question
Title: Is the following fuction computable?
I'm trying to show that $K\_1 \le\_1 K$ where $K$ is the diagonal halting set $\\{x : \varphi\_x(x) \downarrow\\}$ and $K\_1=\\{x: \exists y \\,\\, \varphi\_x(y) \downarrow\\}$, then I defined the function $$\psi(x, y)= \begin{cases} 0 \\, \\, if \\, \\, x \in K\_1 \\ \uparrow \\, if \\, x \notin K\_1\end{cases}$$ By the Parameter Theorem there is a one to one computable function $f$ such that $\varphi\_{f(x)}(y) = \psi(x, y)$ and it's easy to show that $x \in K\_1 \leftrightarrow f(x) \in K$. All above works if and only if $\psi$ is partial computable, I think that function is partial computable because $K\_1$ is r.e. Is this true? I mean, Can I always define a function computable by $$\psi\_A(x, y)= \begin{cases} 0 \\, \\, if \\, \\, x \in A \\ \uparrow \\, if \\, x \notin A\end{cases}$$ for each r.e. set $A$?

# Answer
You're using the terminology of recursion theory. Let me rephrase the argument in terms of computer programs.

* $K$ is the set of all programs $x$ which halt when run on $x$ as input.
* $K\_1$ is the set of all programs $x$ which halt on *some* input.

Given a program $x$, consider the following program $f(x)$:

* For $n=1,2,3,\ldots$: run program $x$ on inputs $1,\ldots,n$ for $n$ steps, and halt if $x$ halts of any of them halt.

The program $f(x)$ halts iff $x \in K\_1$. In particular, $x \in K\_1$ iff $f(x) \in K$. Since $f$ is computable, this gives a reduction from $K\_1$ to $K$.
> 2 votes

---
Tags: computability, reductions
---


# Question
Title: Capacity of a discrete memoryless channel
For an integer $I$, the input-output relationship of a discrete memoryless channel is given by:

$Y = X + Z$ (mod $I$, i.e. sum indicates a modular addition)

where $I ≥ 2$, and

$X$ is an integer chosen from the alphabet $A\_x = \\{1,\dots,2I\\}$,

$Z$ is noise which is a uniform Bernoulli random variable. This means that $A\_z = \\{0,1\\}$, and

$$\Pr\\{Z = 0\\} = \Pr\\{Z = 1\\} = 0.5.$$

How can we calculate the capacity of this channel?

# Answer
This answer assumes that $Y = X + Z \bmod 2I$, which seems more reasonable than the current $Y = X + Z \bmod I$, which would mean that $X$ is effectively chosen from an alphabet of size $I$ rather than $2I$.

The capacity is $\log I$.

For the upper bound, $$ I(X;Y) = H(Y) - H(Y|X) = H(Y) - H(Z) = H(Y) - 1 \leq \log(2I) - 1 = \log I. $$

For the lower bound, if $X$ is chosen uniformly among the $I$ values $1,3,\ldots,2I-1$ then you can recover $X$ from $Y$ (without any error!), and so $I(X;Y) = H(X) = \log I$.
> 2 votes

---
Tags: information-theory
---


# Question
Title: Can quantum computers really compute a vast number of possible solutions simultaneously?
This link says

> They are not constrained to stepwise calculations but, rather, can compute a vast number of possible solutions simultaneously—and at a speed that is far beyond anything we can imagine.

Is this really true? AFAIU quantum computers **cannot** compute a vast number of possible solutions simultaneously. **A quantum computer is not a parallel computer**. It is true that the wave function will exist in a superposition of states before measurement, but when we make a measurement it will collapse to a definite state. And measurements is all we can do.

From scott aaronson’s blog (https://www.scottaaronson.com/blog/)

> If you take just one piece of information from this blog: Quantum computers would not solve hard search problems instantaneously by simply trying all the possible solutions at once.

curious to know what experts think

# Answer
> 2 votes
> They are not constrained to stepwise calculations

As far as I know, all QC models are stepwise.

> Under the laws of nature, the ball spins either to the right or to the left, but never in both directions at the same time. The world of quantum computing is different: Here, the ball can revolve in both directions simultaneously

I think this is the source from which comes all this “QC is a massive parallel computation”.

It is not exactly wrong to think of superposition $\frac{|0\rangle + |1\rangle}{\sqrt{2}}$ as “both $|0\rangle$ and $|1\rangle$ at the same time”, but it’s confusing. It might make you think that both things are simultaneously available for arbitrary processing, which you can fully control. As if preparing a superposition is something like creating clones.

A more precise way to think about superposition is interpreting it as uncertainty. So, less confusing statement would be “neither $|0\rangle$ nor $|1\rangle$, until the setup forces it to be definite”.

---
Tags: quantum-computing
---