# Question
Title: How do I classify the improvement in performance when Hankel functions are replaced with log functions in MatLab?
I am working on a algorithm for acoustic scattering in two dimensions using MatLab, and one of the advantages of this algorithm is that Hankel functions can be replaced with log functions.

For example consider the following:

1. `value = 0; tic; for t=1:100000, value = value + besselh(1,1,abs(1+1i)); end; toc`
2. `value = 0; tic; for t=1:100000, value = value + log(abs(1+1i)); end; toc`

1) takes about 1.095455 seconds, whereas 2) takes about 0.043890 seconds.

Coming from a mathematics background I'm used to analyzing numerical methods in cases such as determining the order of convergence of an ODE/PDE solver or a numerical integration method, along with judging complexity in a program by counting operations.

However in this case, the number of operations is the same (on the surface anyway). So how can the improvement in efficiency be classified in this case? Are empiric results, such as showing that 2) takes much less time than 1), the best I can do in this situation?

Or is there a more formal/rigorous way to classify the improved efficiency?

# Answer
> 3 votes
Asymptotic analysis usually isn't useful, if you care about constant factors (such as a 20x speedup). Counting operations is useful if you only care about asymptotics and don't care about constant factors, but if different operations take a different amount of time and you care about constant factors, then counting operations may not be useful. Asymptotics are just a tool, but they're not always the right tool for every situation.

So, if you want to optimize at this level, you'll need to use different tools -- e.g., empirical evaluation, benchmarking on useful workloads, performance measurement, more precise models (instead of asymptotics).

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


# Question
Title: How does "Greedy Stays Ahead" Prove an Optimal Greedy Algorithm?
I have found many proofs online about proving that a greedy algorithm is optimal, specifically within the context of the interval scheduling problem.

On the second page of Cornell's Greedy Stays Ahead handout, I don't understand a few things:

1. All of the proofs make the base case seem so trivial (when r=1). I don't understand the context behind the base case - perhaps in more easy to understand terms.
2. Are we essentially proving that the number of maximum activities in A cannot exceed the number of activities in O?

In short, are we saying that if A is not optimal, then there would be at least 1 more activity in the optimal solution, O, which would contradict our assumption that O is optimal and that A is the set of requests made by the greedy algorithm? Because we don't say that A is optimal. But we know that it's the set of requests selected by the greedy algorithm. So, if it doesn't include the same number of requests than O, then we know that it couldn't have been selected by the greedy algorithm?

# Answer
What we are saying is that if A is not optimal, then the number of jobs in A (let it be k) should be less than the number of jobs in O ( let it be m).

That means, there must be (k+1)-th job in O, while the k-th job is the last job in A.

Since (k+1)-th job in O must start after k-th job in O, and we know that any i-th job in A finishes earlier than i-th job in O, that means k-th job in A finishes earler than k-th job in O.

**That means, the (k+1)-th job in O can be added to A, which contradicts that A only has k jobs.** Hence, A must be optimal and it must have m items.
> 3 votes

---
Tags: algorithms, greedy-algorithms
---


# Question
Title: Do modern operating systems use memory control blocks?
I was taught in my operating systems class that sections of memory in the heap are marked as free/occupied through the use of memory control blocks (MCB). The generalized definition of an MCB that was given to us is that they hold two memory addresses (one for the next MCB and one for the previous MCB), the size of the block of memory attached to the MCB, and a flag stating whether that block is occupied or not.

When a chunk of memory is requested, the OS finds an unoccupied MCB, marks it as occupied, and creates a new MCB at the end of the now occupied block.

This seems like a sensible way to do things, and yet I cannot find any mention of the term "memory control block" outside of explanations of how DOS tracks memory allocations, even in the textbook Operating Systems Concepts (Silberschatz et al).

I'm confident that *some* sort of administration is going on, via a simple C++ program that creates several pointers to ints and then prints out the addresses stored by the pointers, which are consistently not consecutive (although I guess this doesn't prove anything for sure).

What's going on behind the scenes? Are MCBs simply called something else nowadays?

# Answer
This is really a question about memory allocators and doesn't have much to do with operating systems. "Memory control block" does seem to be a DOS specific term for a node in a free list. I'm not aware of any broadly used term for those nodes. They are usually just called "free blocks" or "unallocated blocks" or some such.

An operating system kernel usually has memory management concerns of its own. A popular choice for Unix-like systems is slab allocation. In Linux, there's a variation that is possibly the default nowadays called SLUB, and there is another option called SLOB which stands for "simple list of blocks" which does correspond to a free list approach.

At the lowest levels though, most popular, general-purpose CPUs organize allocation of physical memory with a page table. (More accurately, page tables manage the physical to virtual address mapping.) The kernel still must keep track of which pages of physical memory are allocated and to which process, but the page table structure makes this a bit less flexible. The main point being that pages come in fixed sizes which allows memory allocation techniques built on fixed sized blocks. In particular, according to Wikipedia, Linux uses a zoned buddy allocator.

So the overall picture looks like this: at the lowest level you have an allocator to keep track of physical pages of memory; above that you have an arena-like allocator motivated by the fact that you often want to allocate many smaller-than-a-page objects and you obviously don't want to allocate a page to each; above that a programming language runtime may have its own memory allocator that may exploit details of the programming language to perform better; finally, an application may do some memory allocation of its own, often also using arenas but now usually motivated by time-cost issues like the costs of allocating/deallocating and data locality.
> 5 votes

---
Tags: operating-systems, memory-management, memory-allocation
---


# Question
Title: Is clrs really needed to be a computer scientist
I want to dive in alghorithms and data structures and maybe AI this year. When I searched on internet everybody was recommending to read clrs. But I found it very complicated, because of the amount and the level of math in it. Is reading clrs really important to be a true computer scientist. If yes, how it can be easier to accomplish. Note: I started reading Data Structures and Algorithm Analysis in C++, but I'm planning to read other books also.

# Answer
To be a computer scientist you need to be able to reason abstractly. The reasoning expected in CLRS is an example. You can find books with titles such as *Discrete Mathematics* that will help with some of the prerequisite material, and with some of the reasoning strategies.
> 0 votes

---
Tags: algorithms, books
---


# Question
Title: Limited number of calls to a black box for finding longest path in graph given an access to oracle
I'm given a black box that on graph $G = (V,E)$ and integer $0\< K\<|V|$ outputs $1$ iff there is a simple path of length greater than $K$ in $G$. I want to find the actual edges of the longest path in $G$ using as few calls to my black box as possible.

What I've come up with thus far is using the same method as when binary searching, i.e. first calling my black box with $K = |V|/2$ and so forth, but I'm not really sure what to do once I've found the $K\_{max}$.. I'd really want to go in and change the black box to output the actual edges but that's impossible.

Edit: So I can delete any edge $e\_i$ from $G$ and see if my black box still returns 1 (once I've found the maximal length path) - if it still returns 1 i know $e\_i$ isn't part of the longest path, and if it returns 0 I know $e\_i$ is part of the longest path(s) and I append it to my data structure holding the longest path. But what should I do if there are several paths of the maximum length? It feels as if I will return all the edges of all the longest paths and not just one specific.

# Answer
> 1 votes
Since you can find the actual length of the longest path using binary search, in $\log |V|$ steps, I'll assume you have access to an oracle which tells you the length of the longest path. Given a graph $G$ lets denote the length of the longest path in $G$ by $L(G)$.

If you remove an edge after finding out that it does not affect the length of the longest path in $G$, then you avoid the issue of having to commit to some specific longest path. Suppose you keep iterating over the remaining edges, and for each remainning edge $(u,v)$ you check if $L(G)=L\left(G\setminus\left\\{(u,v)\right\\}\right)$. If they are equal, remove $(u,v)$ from $E$ and return to the main loop. When there are no more edges to delete, $E$ consists of a longest path in $G$.

To prove this, let $\mathcal{P}$ be the set of longest paths in $G$. Note that in any iteration $i$ (each iteration consists of removing an edge which does not affect the longest path length), there exists some $P\in\mathcal{P}$ such that $P$ is a path in $G\_i$. Using this observation, you can show that when there are no more edges to delete, your graph is a longest path.

---
Tags: complexity-theory, graphs, graph-traversal
---


# Question
Title: Building a verifier for sentences involving addition over the natural numbers
Consider the model $(\mathbb{N},+)$; that is, the natural numbers equipped with the addition relation, PLUS($x$,$y$,$z$), where PLUS($x$,$y$,$z$) is true iff $x + y = z$. Let Th$(\mathbb{N},+)$ be the theory of this model; that is, the set of true sentences in the language of the model. For example, the sentence $\forall x \exists y \[x + x = y\]$ is a true sentence in this model. Let's assume for simplicity that all of these sentences are in prenex normal form.

I'm interested in coming up with either an (efficient) verifier for Th$(\mathbb{N},+)$ or a nondeterminstic algorithm that decides Th$(\mathbb{N},+)$. In the former case, I'm wondering what a certificate could be. If all of the quantifiers in the input statement are existential, this isn't a problem: a certificate would just be an assignment of all the variables. However, things are made difficult when the input has a universal quantifier, since it isn't obvious how we can check that something holds for all members of an infinite set.

# Answer
> 4 votes
$\left(\mathbb{N},+\right)$ is a model of Presburger arithmetic. Persburger arithmetic is a complete theory (see the answer here), so for any model $\mathcal M$ for Presburger arithmetic (lets denote this theory by $T$) and every first order formula $\varphi$ in the language of $T$ it holds that:

$\mathcal{M}\vDash \varphi \iff T \vdash \varphi$

To see why this follows for completeness, assume $M\vDash \varphi$, then obviously $T\not\vdash \neg\varphi$, thus by completeness $T\vdash\varphi$ (the $\Leftarrow$ implication is trivial).

This shows you why your question reduces to finding a decision procedure for Presburger arithmetic. This has a known double-exponential lower bound, you can find a proof in Rabin and Fischer's paper "Super-Exponential Complexity of Presburger Arithmetic". This bound also holds for nondeterminstic algorithms.

---
Tags: time-complexity, logic
---


# Question
Title: Why floating point representation uses a sign bit instead of 2's complement to indicate negative numbers
Consider a fixed point representation which can be regarded as a degenerate case of a floating number. It is entirely possible to use 2's complement for negative numbers. But why is a sign bit necessary for floating point numbers, shouldn't mantissa bits be using 2's complements?

Also why do the exponent bits use a bias instead of a signed-magnitude representation (similar to the mantissa bits) or 2's complement representation?

Update: Sorry if I didn't make it clear. I was looking for the reason of how floating point representation is shaped. If there is no strong implementation trade-off between the alternatives, then could someone explain the historical aspects of the floating point representation?

# Answer
> 7 votes
Two's complement makes sense when the two entities in question have the same "units" and the same "width". By width I mean that, say, if you're adding an N bit number and an M bit number, where N and M are different, then you better not use two's complement. For floating point numbers, we have the problem of units: if the exponents are different, then we are mentally shifting one of the mantissas, and now we're at the same problem as before (with the width).

As for the exponent bits, by using a bias instead of sign+magnitude we gain one more value (otherwise we'd have +0 and -0). Here two's-complement makes sense when multiplying or dividing numbers (since then we're adding or subtracting the exponents), but not as much sense when adding or subtracting.

Edit: A commenter remarked that you can add two's complement integers of different lengths using sign extension. There is also some problem with detecting overflow, but that's also fixable. In summary, you could probably use two's complement, if you're careful enough. (You also need to handle multiplication and division.)

# Answer
> 5 votes
From Wikipedia:

> The two's-complement system has the advantage that the fundamental arithmetic operations of addition, subtraction, and multiplication are identical to those for unsigned binary numbers...

Two's-complement is a *representation* of negative numbers that just so happens to be very convenient. That's the whole reason to use it at all.

A mantissa-exponent pair is a representation of a floating point number. Most of the time when using floating point numbers, you aren't doing arithmetic solely on the mantissa or solely on the exponent.

# Answer
> 5 votes
> But why is a sign bit necessary for floating point numbers

False assumption. It isn't necessary. I'm pretty sure I've met floating point formats which used 2's complement for the mantissa, but I'd have to dig out for names.

I'm far from being a specialist in numerical analysis, but I get that having signed zero is important for them. It's probably easier to manipulate than ones' complement. That was probably a criteria in the choice for IEEE-754.

> Also why do the exponent bits use a bias instead of a signed-magnitude representation

Again it's something not needed and some have done thing differently.

It's the representation for which it is easier to do an hardware implementation for the set of operations which are done on exponents (and here having a representation for -0 isn't wanted).

One of the consequence of that choice is that you can use signed integer comparison to compare FP number if you don't care about NaN, which was perhaps a criteria for some (the fact than NaN needs special handling make me doubt it wasn't for IEEE-754).

# Answer
> 3 votes
IEEE 754 uses sign/magnitude, not two's complement or one's complement.

Two's complement has the disadvantage that the positive and negative range are not identical. If all bit patterns are valid, then you have numbers x where you can't easily calculate -x. That's bad. The alternative is that there are invalid bit patterns, which is also bad. In IEEE 754 there are no invalid bit patterns for 64 or 32 bit floating point, so you don't need to worry about that.

One's complement would make multiply / divide more complex (with signed magnitude, you just xor the signs and treat the mantissa as an unsigned number). For add and subtract, I really don't want to think about add and subtract in one's complement, it makes my head hurt.

# Answer
> 2 votes
Having signed zeros gives increased expressiveness that may be useful in numerical computations. The wikipedia page ‘Signed zero’ says:

> It is claimed that the inclusion of signed zero in IEEE 754 makes it much easier to achieve numerical accuracy in some critical problems, in particular when computing with complex elementary functions.

One of the main designers of IEEE 754 floating point, W.H. Kahan is a proponent of signed zero for these reasons. His opinion will have likely carried much weight.

# Answer
> 1 votes
I think it is important to understand that floating-point calculations produce *approximate* values, not *exact* values. That is, if a floating-point calculation yields an encoded value X, then this represents a *theoretically ideal value* which is almost certainly NOT X, but is in the range \[X .. X+e) { where 'e' is the 'machine epsilon', i.e there is no floating-point number between X and X+e }. More specifically, a floating-point zero represents an ideal number which is probably not exactly zero, but which is too small to represent with a nonzero floating-point encoded value.

Given that, using sign-and-magnitude representation is a way of allowing the encoding to 'remember' exactly *which side of zero* the ideal value is on, the positive or the negative. This is critical in certain complex (in the 'a + bi' sense) calculations - complex-\>complex functions are often 'multi-valued', so for proper computation it is critical to pay attention to the locations of 'branch cuts'. Signed zeros then in a sense mark the locations of these branch cuts - the calculation done on the positive side will be different from that on the negative side.

# Answer
> 0 votes
Most floating-point formats take advantage of the fact that, in a binary system, any non-zero value with a non-minimum exponent will have a "1" as the most significant bit of the mantissa. Thus, in a system with a 23-bit field for the mantissa, the mantissas of positive numbers don't range from 0 to 8,388,607 but instead from 8,388,608 to 16,777,215. The mantissas of numbers that may or may not be positive range from -16,777,215 to -8,388,608 and from +8,388,608 to +16,777,215. While two's-complement is best numerical format when it is necessary to have calculations "smoothly" cross zero, the discontinuous ranges of mantissa values mean that calculations wouldn't be able to to operate smoothly across zero whether they use two's-complement or something else.

---
Tags: computer-architecture, floating-point, number-formats
---


# Question
Title: In the "tall cache assumption" what does $\Omega$ represent?
Within the field of cache-oblivious algorithms the ideal cache model is used for determining the cache complexity of an algorithm. One of the assumptions of the ideal cache model is that it models a "tall cache". This is given by the statement $Z = \Omega(L^2)$. Where $Z$ is the size of the cache and $L$ is the size of the cache line. What does $\Omega$ represent?

# Answer
It's the lower bound counterpart to O($\cdot$). Z is larger than some constant times $L^2$
> 5 votes

# Answer
It's called "asymptotic lower bound" - https://www.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/big-big-omega-notation
> -1 votes

---
Tags: asymptotics, landau-notation, computation-models, cpu-cache
---


title: Why does radix sort work?

text:
# Question
Title: Why does radix sort work?
I understand how radix sort works and how to implement it, but I don't understand why it works.

Are there any underlying mathematical or logical principles that it relies on?

# Answer
> 5 votes
Radix sort sorts numbers by sorting on the *least significant* digit first. This is somewhat counterintuitive compared to the rather straightforward method by sorting on the *most significant* digit first.

The key point to radix sort is that the digit sorts used in each iteration of radix sort are *stable*: numbers (digit here) with the same value appear in the output array in the same order as they do in the input array. Given this, you can convince yourself of the correctness of radix sort by simply observing how a set of two-digit numbers are sorted. (Actually, we are using mathematical induction on the number of digits. However, a simple example with a set of two-digit numbers suffices here.)

In the first iteration, the numbers are sorted by their least significant digits. Now consider the second iteration which then sorts these numbers by the leftmost digits. Given two number $a = a\_1 a\_0$ and $b = b\_1 b\_0$, if $a\_1 \neq b\_1$, then after the second iteration, they are in the right order. If $a\_1 = b\_1$, then we know that the order between $a$ and $b$ should be consistent with $a\_0$ and $b\_0$. This is the case because the digit sort used by the second iteration is stable.

---
Tags: data-structures, logic, mathematical-programming, radix-sort
---


# Question
Title: Is an NP-hard problem which is in NP is NP-complete?
I'm reading Combinatorial Optimization book by Bernhard Korte and Jens Vygen. There's a part that they said:

> It is an open question whether each $NP$-hard decision problem $A \in NP$ is $NP$-Complete, because of the difference between polynomial reduction and polynomial transformation.

I understand that, but when I read wikipedia article about NP-complete, I see this picture

According to wikipedia, a decision problem is $NP$-complete when it is both in $NP$ and $NP$-hard, which make me confused. Can someone help me understand the difference between the book and wikipedia?

> *Definition 15.15*. Let P1 and P2 = (X, Y) be decision problems. Let f : X → {0, 1} with f (x) = 1 for x ∈ Y and f (x) = 0 for x ∈ X \ Y . We say that P1 polynomially reduces to P2 if there exists a polynomial-time oracle algorithm for P1 using f
>
> *Definition 15.17*. Let P1 = (X1, Y1) and P2 = (X2, Y2) be decision problems. We say that P1 polynomially transforms to P2 if there is a function f : X1 → X2 computable in polynomial time such that f (x1) ∈ Y2 for all x1 ∈ Y1 and f (x1) ∈ X2 \ Y2 for all x1 ∈ X1 \ Y1.

# Answer
> 5 votes
Check the definitions of NP-completeness and NP-hardness. I suspect they use Karp reductions for one and Cook reductions for the other.

Then, the quote makes sense: it is indeed unknown if Cook reductions and Karp reductions are equivalent in this sense. This is related to the question whether co-NP = NP; Cook reductions can not separate the two but Karp reductions might. See here for some details.

However, the authors use different definitions than (most of) the rest of the CS world: the widely accepted standard is to use Karp reductions. I recommend you read our reference question (and get a better book).

---

To be fair, the authors want to talk about *optimization* problems, in which case they need a notion of (NP-)hardness that is not tied to decision problems. Karp reductions won't get them there directly.

They picked a poor way out, arguably, by defining the notions differently from everybody else. There are cleaner (but more involved) ways, defining complexity classes for optimization problems rigorously, providing them with their own types of reduction, and tying them to the classic decision-problem classes using *threshold* languages.

# Answer
> -1 votes
***NP*** is an abbreviation of the term "non-deterministic polynomial". Informally, it means a problem belonging to the class ***NP*** can be 'solved' (formal term is 'decided') by using a non-deterministic Turing machine (TM) in the number of steps which are polynomial in the input size. Input size is usually no. of TM cells used by the input problem encoded in certain format. Intuitively, it is an amount of memory required to write input on TM tape.

You should note that ***NP*** is a complexity class of problems and not the problem instance itself. The complexity class is a set of problems which requires similar amount of resources (time and/or memory space) to solve.

**Meaning of the term 'Hard'**: I think you have misunderstood meaning of the term 'hard'. Hardness is the measure for comparing amount of resources needed to solve problems in various complexity classes. For a problem in ***NP***, time requirement is polynomial in input size. Problems in the class ***NP***-hard need at least polynomial no. of steps, but they may actually need more. Informally speaking, all problems which have **same or more** resource requirement (hence at least that much hard to solve) than problems in ***NP*** are ***NP***-hard.

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


# Question
Title: Showing $1$-reducibility of $\overline{\text{HALT}'}$ to index set
Note: overline denotes complement

I am trying to show that $\overline{\text{HALT}'}\leq\_1 \\{i\colon\Phi\_i=\Phi\_e\\}:= A$ for some fixed $e$ but I am misunderstanding the problem or method and can't figure out where I'm going wrong. I am using the construction of the proof of Rice's theorem to prove this and I thus do the following:

Let $e\_0\colon \Phi\_{e\_0}\uparrow$. We thus have that, as long as $\Phi\_e\downarrow$, $e\_0\in\overline{A}$. Now choose $e\_1\in A$ and define $s$ such that $$ \Phi\_{s(x)}(y) = \begin{cases} \Phi\_{e\_1}(y),& \text{if } x \in \text{HALT},\\ \text{undefined},& \text{if } x\not\in \text{HALT} \end{cases} $$ we thus get that $x\in\text{HALT}\implies s(x)\in A$ while $x\not\in\text{HALT}\implies s(x)\in\overline{A}$ and it follows that $\text{HALT}\leq\_1 A$ and $\overline{\text{HALT}}\leq\_1\overline{A}$.

This is, however, the opposite of what I want but I can't seem to see where I'm going wrong? Any help would be greatly appreciated!

# Answer
Let $e$ be and index for the constant 0 function. Then consider $s$ such that

$$ \varphi\_{s(x)}(y) = \begin{cases} 0 & \mbox{ if }\varphi\_x(x) \mbox{ does not halt within $y$ steps} \\ 1 & \mbox{otherwise} \end{cases} $$

Then $\varphi\_{s(x)} = \varphi\_e$ if and only if $x \not\in HALT$ (assuming HALT was the diagonal halting problem).

The function $s$ can be choosed to be monotonic (use pumping), hence it is one-to-one.
> 2 votes

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


# Question
Title: A < HPL < Complement(A) What can you say about A and Complement(A)?
Suppose we have the language

$ \overline L = \\{x∈\\{0,1\\}\*:x∉L\\}$

And we know that

$A ≤ HPL ≤ \overline A$

where HPL is the Halting problem.

We need to state whether A is finite, countably infinite and whether $A$ and $ \overline A$ is recursive or not or re or not.

We know that A reduces to HPL and HPL is re and therefore **A is re**. Since HPL reduces to $\overline A$ and HPL is not recursive then **$\overline A$ is not recursive**. Furthermore, if we know that a language is not recursive but its complement is re then the language is not re. We know so far that $\overline A$ is not recurisve but $A$ is re then it means that **$\overline A$ is not re**. Furthermore if you know that a language L is not re then *either* $\overline L$ is not re *or* $\overline L$ is re but not recursive. We know that $\overline A$ is not re but A is re and therefore, we can say that **A is not recursive.**

Can anybody tell me if my deduction is any good? Also, how can I know if A is finite/ count infinite? Any tip would be greatly appreciated!

# Answer
Your analysis appears to be correct. But some clarity may help you. Let's analyse each case and check whether it is consistent with given information. As $\text{HPL} \leq \overline{A}$, $\overline{A}$ cannot be finite or recursive.

\begin{array}{|l|l|} \hline \textbf{If A is } & \textbf{Then }\overline{A} \textbf{ is}\\ \hline \mbox{Finite} & \mbox{Contradiction - }\overline{A} \text{ has to be FA; Violates HPL} \leq \overline{A} \\ \hline \mbox{Recursive} & \mbox{Contradiction - }\overline{A} \text{ has to be recursive; Violates HPL} \leq \overline{A}\\ \hline \mbox{Recursively Enumerable} & \text{Non-Recursively Enumerable}\\ \mbox{but not Recursive} & \\ \hline \mbox{Non-Recursively Enumerable} & \mbox{Contradiction - Violates } A \leq \text{HPL}\\ \hline \end{array}

You can now infer countability based on this information.
> 2 votes

---
Tags: turing-machines, undecidability
---


# Question
Title: What advantage does Tangaroa offer over PBFT?
Tangaroa is a relatively new project adding Byzantine fault-tolerance to the Raft consensus protocol using techniques that were already used in the PBFT algorithm. What are the advantages, when should I use Tangaroa and when PBFT?

# Answer
> 1 votes
The notion of perfection in consensus:

Tangaroa is a BFT flavored Raft usually consisting of 3 - 5 systems in a cluster and can tolerate failure of up to 1/2 of the node count with a concept of *"randomization in election of leadership".*

PBFT is the "practical" BFT system designed for more deterministic behavior with a concept of *"eventual leadership"*. However, I came across this research (https://www.zurich.ibm.com/~cca/papers/sieve.pdf) mentioning *"Fault-tolerant execution on multi-core servers poses a new challenge, even for deterministic applications, because thread-level parallelism may introduce unpredictable differences between processes."* in Related Work.

Choosing which one? I'd leave that to you once you'll be able to determine the nature of the state machine you'd like to see operational.

Hope this helps :) Comments and corrections,(if any) are most welcome!

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


# Question
Title: Is this a valid representation of a function in Lambda Calculus?
Let's say I want to define a function:

This function multiplies an input by two, adds one to this integer, then divides it by two in that order.

f represents the multiplication, g represents the addition, and h represents the division.

Could I represent this as `λx.fxgh`, when explicitly defined with parentheses is shown as `λx.(((fx)g)h))`?

I would think that is correct, because you evaluate the innermost function first, then move outwards treating each evaluated function on the inside as input for the next one, no?

# Answer
It's valid (because it respects $\lambda$-calculus syntax) but won't work as you expect. To see that just take your favorite language and try it out:

```
let f = \x -> 2*x
let g = \y -> y+1
let h = \z -> z/2

```

`(\x -> (((fx)g)h))) 1` won't evaluate to $1.5$. Why?

Because $g$ and $h$ are functions and take one argument each, and application happens when there's an abstraction to the left. So if you change the order you will get the expected behavior.

$$ \lambda x. (h (g (f ~ x))) $$

or

$$ \lambda x. ((h \circ g \circ f) ~ x) $$

In Haskell:

```
(\x -> (h . g . f) x)

```

where `.` ($\circ$) is for function composition.

Example:

$$ \big(\lambda x. (h (g (f ~ x)))\big) 1 \rightarrow (h (g (f ~ 1))) \rightarrow (h (g ~ 2)) \rightarrow (h ~ 3) \rightarrow 1.5 $$
> 2 votes

---
Tags: lambda-calculus
---


# Question
Title: Are these examples of unification problems?
I have been studying unification, especially nominal unification (paper) gets my attention. I read the theory and examples. But I am wondering that what kind of problems occur in unifications. For examples, The following examples are from nominal unification paper. (I write distinct bound variables, so easier to see the solutions )

(1) $\lambda a. \lambda b. (X \\, b) = \lambda c. \lambda d. (d \\,X) $

(2) $\lambda a. \lambda b. (X \\, b) = \lambda c. \lambda d. (d \\, Y) $

(3) $\lambda a. \lambda b. (b \\, X) = \lambda c. \lambda d. (d \\, Y) $

I observed that each variable ($X$ or $Y$) occurs only once on one side of equations. Should it be always that way? Can I write the following

(4) $\lambda a. \lambda b. (X \\, X) = \lambda c. \lambda d. (d \\,X) $

(5) $\lambda a. \lambda b. (Y \\, X) = \lambda c. \lambda d. (d \\,X) $

(6) $\lambda a. \lambda b. (X \\, X) = \lambda c. \lambda d. (X \\,X) $

and are these possible unification problems?

I read many sources, but and all presented unification problems with variables only have once occurrences on one side of equations. I tried to find more examples, but could not find anything different.

I know the unification problems arise from logic programming. And so far, I did not see any logic programs which puts $X$ twice in a term.

Anyway, hoping someone to clarify these points.

Thanks in advance!

# Answer
> 3 votes
Yes, the variables can occur more than once in a term. Either way you end up with a system of equations. For plain unification, you can always have the unification variables be distinct and then add equations to unify them separately. That is, you can turn $\mathtt{p}(X,X) = \mathtt{q}(\mathtt{a},\mathtt{b})$ into $\mathtt{p}(X,Y) = \mathtt{q}(\mathtt{a},\mathtt{b})$ and $X = Y$.

Comparing predicates with duplicate variables comes up all the time in Prolog. For example, one of the most iconic Prolog programs is list append, usually written as:

```
append([], Ys, Ys).
append([X|Xs], Ys, [X|Zs]) :- append(Xs, Ys, Zs).

```

If you want to be very pedantic and say these programs don't illustrate *terms* with duplicate variables, then you can consider another iconic Prolog technique: difference lists. The most general difference list representation of a list $\[1,2,3\]$ is $\[1,2,3|X\]\setminus X$.

---
Tags: logic, unification
---


title: Data Structure example

text:
# Question
Title: Data Structure example
Name a data structure that you could use to implement a queue such that all of the standard queue operations are O(1). If you are thinking of a data structure based on Python's built in list, you need to be more specific then just writing "list".

O(1) is constant time and I know that you can use lists to replace using ADTs but what does the question mean by being more specific? Also I thought that lists are O(n), linear time. How would I return something in constant time?

Note: I am a beginner comp sci student who is learning with Python

# Answer
> 1 votes
Have a look at this post here. Data structure with search, insert and delete in amortised time $O(1)$? To summarise, it is not possible to have all operations in constant time. If usage of parallelism is an option for you, have a look at this paper titled "A Parallel Priority Queue with Constant Time Operations", http://dx.doi.org/10.1006/jpdc.1998.1425.

---
Tags: data-structures, queues
---


# Question
Title: Calculate joint entropy of a Hamming Code over a Binary Symmetric Channel?
I have a normal (7,4,3) Hamming Code over GF(2) and a parity check matrix for it (not posted, because I don't think it's involved).

I have a set X of 4 bit source vectors called x. They all have equal probability to be sent. So I would assume p(x) = 1/16. They are sent over a BSC with the bit error probability p=0.15.

Y is the decoded message set. It contains the same elements as X. However it can occur that a message x from X sent and decoded into y from Y would not be x = y (too many errors to correct/detect).

For each pair (x, y) from X x Y (Most likely Cartesian product?) we can derive a probability p(x,y) (the probability that a message x was sent, but received as y).

The task says "it is not hard to see we can calculate p(x,y) if we have the BSC bit error probability."

It is hard to see for me, though. I would have 16 vectors in X and 16 vectors in Y, that would give me a 256 row table. Then for each of that to calculate the probability of 1 scrambled bit, 2 scrambled bits, 3... and so forth?

I can write a program to do it, but this course is meant to be done by hand. Any help appreciated!

# Answer
> 1 votes
You can express $p(x,y)$ as a formula that depends on just the number of bits that differ between $x$ and $y$. Try to see if you can do that. That will provide a nice clean formula that doesn't require examining $16 \times 16$ cases by hand.

---
Tags: probability-theory, information-theory, entropy
---


# Question
Title: Finding a subarray of time series data in which all values are less than X for specified time Y?
The idea is to find an anomalous value (i.e. it's less than *X*) in time series data (sorted by time), and check if this behavior continues during specified time (*Y=2 hours*).

If all values in sub-array (which represents 2 hours period) are  X, the subarray is returned as a result, and we do not continue further.

Else search continues until such sub-array is found or we have no more data.

Is there an algorithm or family of algorithms that are suited for this task?

---

**Example:**

*X = 10*

*Y = 2 hours*

**Data:**

(time=00:00, value=4)

(time=01:00, value=4)

(time=02:00, value=11)

(time=03:00, value=4)

(time=04:00, value=3)

(time=05:00, value=3)

**Result:**

(time=03:00, value=4)

(time=04:00, value=3)

(time=05:00, value=3)

---

...during these 2 hours all values were *consistently  than X=4*.

On the other hand, 00:00 - 02:00 range has X=11 at the end, so it isn't included in result.

---

**Update:**

There are approx. 1440 data points in the array (1 point per minute x 24 hours).

This shouldn't be a streaming algorithm, all needed data points are already available.

Data points are immutable, values (or time) don't change.

It's important that we use as little memory during the search as possible.

Search is run once a day, so the data is different and does not depend on previous searches.

# Answer
You don't need a clever or sophisticated algorithm. It suffices to linearly scan through the time series, in chronological order, and keep track of the length of window of values less than $X$.

At time $t$, remember the length of the longest window ending at time $t$ such that all values in the window are less than $X$. At time $t+1$, when you see the next value, update this length (it either increases by 1, if the new value is less than $X$, or resets to 0, if the new value is at least $X$). Keep track of the longest such window that you saw during the entire scan. If it is longer than $Y$, output it.

This requires very little memory (only an integer to keep track of the length of the window of consecutive values $\< X$, and an integer to keep track of the current position in the array). The algorithm should be extremely fast.
> 1 votes

---
Tags: subsequences, time-series-analysis
---


# Question
Title: Why is an Artificial Neural Network with high accuracy score giving poor results?
I implemented my ANN using SKlearn module's class MLPClassifier. Fitting it on some data and testing it on a very specific subset of said training data, it gives a score of 1.0, but actually using the ANN to **generate outputs for said testing data** almost always gives incorrect output. What could be the possible reasons for this? I am using this ANN as a memory network and there is never a case when input is out of training data.

# Answer
> 3 votes
You're testing your neural net with data from the training set, of course it will get you great results. But you're neural net is now trained for a specific data and is unable to make generalization. This is known as Overfitting.

You should either split your data into test/train or use another technique to estimate your NN performance. A good technique is K-fold Cross validation.

Also check Overfitting wiki page and Cross validation on sklearn if you want more details.

---
Tags: neural-networks
---


# Question
Title: How to make a Post Machine for $a^nb^n$?
I have tried to make a Post machine for that all words of the form $a^nb^n$ by the following steps.

1. add a marker '#'
2. read first 'a'
3. read next 'a's and add them
4. read first 'b'
5. read next 'b's and add them
6. read '#' (that we added in the first step)

repeat steps while input tape is not empty

but this algorithm also accepts words of the form $(ab)^n$ e.g abab, ababab I want to make a Post machine that only accepts words of the form $a^nb^n$ How to do that?

# Answer
> 0 votes
Hint. One possible solution is checking the format of the input in the beginning of the procedure to get sure the user input is in form of $a^nb^n$. If it is in correct format then go to next step otherwise reject. In next step using the instructions that you've written can accept the language. But one thing which is important in post-turing machines is it's model (eg. Davis), which you didn't mention.

# Answer
> 1 votes
This language $a^nb^n$ can be recognized by a one counter automaton, i.e. a pushdown automaton with only one kind of stack symbol (other than the stack bottom).

That can be easily mimicked by a Post machine (with capital P, like Turing), according to the Wikipedia definition.

So first try to design the PDA with a single stack symbol (that is easy), and then translate it to a Post machine.

But I am not sure you are using the same type of Post machine as described in Wikipedia, and you did not describe your model.

# Answer
> 0 votes
Given the description of the steps in your Post machine, and assuming that step 6 connects to step 1, then you have the correct algorithm.

Your machine will accept only the language $a^n b^n$ and it will not accept $abab$ or any other word not of the form $a^n b^n$.

Given the example $abab$, the machine will crash/reject at step 5 after it reads the second $a$ in $abab$.

---
Tags: context-free, automata
---


title: Spacetime Tradeoff

text:
# Question
Title: Spacetime Tradeoff
I understand that many algorithms have space/time tradeoffs-that is, to run faster, you can do things like caching data, which reduces time taken in exchange for space consumed.

Given conservation of energy and spacetime equivalence, is there any relationship between the time saved by using extra space and vice versa? After all, extra running time consumes more energy-is this energy equivalent to the energy taken to store the extra data in any way, or the other way around?

# Answer
> 2 votes
There surely are results about space/time tradeoffs but I'm not familiar with them. I would, though, like to address two significant misconceptions in the question.

First, it's important to note that when computer scientists talk about space and time, we're not referring to physical space or time. We're referring to purely mathematical concepts that are independent of the physical universe. "Time" to a computer scientist is just the number of computation steps that have been executed, and "space" is just the number of items of data that have been stored. We're interested in these quantities because we believe that they are a good model for physical computation, but the quantities themselves are not physical. Turing machines don't have to obey conservation of energy because they're not physical systems: nowhere in the definition of Turing machines do you see any power source. Indeed, I'm not aware of any theoretical work treating energy as a computational resource. Surely, some must exist, but it's not a concept that has made its presence felt in theoretical CS. Note also that number of computation steps on an ordinary Turing machine actually *doesn't* correspond very closely to the time taken by a physical computer.

Second, in physics, there is no such thing as "spacetime equivalence". Spacetime is not simply a convenient four-dimensional notation that lets us write "location $(x,y,z)$ at time $t$" as the four-dimensional co-ordinate $(x,y,z,t)$. The fundamental point is that the metric used to compute "distance" in this four-dimensional space is not the standard Euclidean metric but the Minkowski metric, which treats space and time differently. (See What is spacetime (simple explanation)? on Physics.SE for more on this.)

---
Tags: time-complexity, space-complexity
---


# Question
Title: Which algorithm suits this problem best?
I have an optimization problem and I'm looking to find an algorithm whitch best fits this. The problem is the following:

There are several points of interest (POI), each has a value (for the user), the distance to each other POI is also known. Now I want to generate the best tour (ordered list of POIs) with the most value for the user given a maximum distance he has to travel.

At first I was thinking about the knapsack problem where the distance would be the weight. The problem is, the order of the POIs is important and the weights vary according to the POIs already selected (more specifically, they depend on the last POI selected). Another idea is using TSP, where I first need to somehow select the subset of nodes which should be visited.

Does anyone have an idea, which known problem is similar to the one described and/or if there is an algorithm solving this. I'm not looking for an ideal solution, a good approximization is fine as well. Also perfomance is not an issue (for now).

# Answer
> 1 votes
I thought of a method to state this problem completely in terms of metric vertex weights, which could be considered a (very non-standard) kind of TSP.

In particular, look at the following subproblem:

> Given a graph $G=(V,E)$, with an initial vertex $v\_0\in V$, a distance function $d : E\rightarrow \mathbb{R}^+$ such that the graph is metric, a function $p : V \rightarrow \mathbb{R^+}$ that assigns points to vertices, a maximum distance $D$, a minimum value $P$ and an integer $k$.
> Determine if there exists a (simple) tour on $G$ starting at $v\_0$ of exactly $k$ vertices such that the total distance is less than $D$ and the sum of the points $p(v)$ is at least $P$.

So, we want to find a tour of vertices $v\_1,\ldots,v\_k$ with total distance at most $D$, so $\sum\_{i=1}^{k-1} d(v\_i,v\_{i+1})\leq D$. Additionally, we want to have enough POI points, so $\sum\_{i=1}^{k} p(v\_i)\geq P$. We will rewrite to the second condition to be similar to the first.

We can replace the second condition by $\sum\_{i=1}^{k} -p(v\_i)\leq -P$, but now we have negative weights. Since we have fixed $k$, we can solve this by adding the value $p^\* =\max\_{v\in V}p(v)$ to every individual point: set $p'(v\_i):=p^\*-p(v\_i)$ and $P':=k\cdot p^\* - P$, so we get $\sum\_{i=1}^{k} p'(v\_i)\leq P'$. Now, $p'(v\_i) = p^\*-p(v\_i)$ is non-negative, and we may assume $P'=k\cdot p^\*-P$ non-negative, since we know for sure that we cannot get enough points in any tour of $k$ vertices otherwise.

Now, the difference is that points are assigned to vertices in stead of edges. We solve this by defining $p'(v,w):= \frac{1}{2}(p'(v) + p'(w))$ and now we require $\sum\_{i=1}^{k-1} p'(v\_i,v\_{i+1})\leq P'$. This is still equivalent to the previous condition, as we must leave and enter every vertex on a (simple) tour exactly once. Note that $p'(v,w) \leq p'(v,w)+ p'(u) = \frac{1}{2} (p'(v) + p'(w)) +p'(u) = \frac{1}{2}(p'(v)+p'(u)) + \frac{1}{2}(p'(u) +p'(w)) = p'(v,u) + p'(u,w)$ for any $u,v,w\in V$, since $p'(u)$ is positive. So, the distance $p'$ is metric on $G$, as it satisfies the triangle inequality.

Now, there are no more differences between the pairs $(p',P')$ and $(d,D)$. This means that we can phrase our subproblem as follows: determine if there exists a simple tour of exactly $k$ vertices of length at most $P'$ under metric $p'$ AND of length at most $D$ under metric $d$. I call this the *$k$-vertex simultaneous TSP*.

Note that this problem, if we assume $(p',P')$ arbitrary, could actually be a lot harder than the current problem. $(p',P')$ is extremely 'regular' for a TSP, since the order in which we visit the vertices doesn't matter for this metric. (which should be the case, since it didn't matter in the original formulation either)

---

Initially, I thought this approach would lead to a regular TSP problem, but it seemed more unlikely as I wrote it down. Nevertheless, I think the ideas here can be useful in approaching the problem, at least. I don't see a way to 'combine' the different distances for an exact solution, but it might be possible if we are satisfied with an approximation.

---
Tags: algorithms, optimization, knapsack-problems, traveling-salesman
---


# Question
Title: Finding longest balanced parentheses using $n$ smaller strings
Given $n$ strings consisting only of '$($' and '$)$', how one can compute the length of the longest string that can be built by concatenating a subset of these strings in some order such that the resulting string is a balanced parenthesis?

Example: If we have the strings $\\{"(()",")(",")","(("\\}$, one can build the string $"(())()"$ which has length 6. We cannot construct a longer one from the previous set, thus the answer is 6.

In general, the answer is always even, and always $\geq 0$ because we can always take the empty set.

Problem source: North American Invitational Programming Contest (NAPIC) 2017, Problem A.

# Answer
First, let's remark that the order in which you put the selected strings is not significant as long as it is valid. That means that you can put the strings in a canonical order and you know that the solution is a subsequence of that sequence. The canonical order I suggest is first the strings which increase the number of opened parenthesis (with D.W. triplet notation, the triplets $\langle i,j,\ell \rangle$ for which $j\>i$) tied resolved by increasing $i$, then those which don't change the number of opened parenthesis ($i=j$) then those which decrease the number of opened parenthesis($i\>j$) this time solving the tie by decreasing $i$.

Then you apply the favorite technique of programming contests: dynamic programming. You are filling an array of $n$ columns. An entry $c,r$ of $\ell$ states that with the $c$ first strings in our canonical order, you can have $r$ opened parenthesis pending with a total length of $\ell$. This is filled using the content of the column $c-1$ with the initial column stating that with no strings you have a $0$ opened parenthesis pending and a length of $0$. You have to pay attention to avoid entries which would need to have more opened parenthesis than available, and when an entry is reachable with two lengths to keep the longest one.

You avoid the exponential behavior because you know that the strings have a bounded length of 300 (thus you can't have more than $300\\; c$ opened parenthesis after $c$ columns instead of the $2^c$ entries which would have been possible without that bound) and thus you are sure that after the ninth or so column, you'll have duplicate entries.
> 1 votes

# Answer
I don't know of any algorithm whose worst-case running time is reasonable. I list below an approach that *almost* works, but becomes slow when we add logic to ensure that no string is used more than once. Perhaps you can find a way to improve it.

Treat two strings $x,y$ as equivalent (written $x \sim y$) if you can obtain one from the other by repeatedly removing or inserting $()$. For instance, $()( \sim ( \sim (()$.

Now, every string of parenthesis is either (a) equivalent to $)^i (^j$ for some $i,j \in \mathbb{N}$, or (b) cannot appear as a substring of any string with balanced parentheses. In case (b), there's no way to extend it to a solution to the problem, so such strings can be ignored, and we can focus on case (a).

We'll identify each string of parentheses with the tuple $\langle i,j,\ell \rangle$, where the string is equivalent to $)^i (^j$ and $\ell$ is the length of the string. Build an (implicitly-represented) graph corresponds to all valid sequences. We'll basically do pruned search in this graph.

In particular, we'll imagine a graph with one vertex for each valid sequence, and with the edge $u \to v$ if the sequence $v$ can be obtained from $u$ by appending one of the $n$ strings to $u$. Now, you can search the graph to find all vertices that are reachable from $\epsilon$ (the empty sequence of length 0). We're looking for the longest configuration of the form $\langle 0,0,\ell \rangle$ (i.e., the one where $\ell$ is as large as possible).

You can use any graph reachability algorithm, such as BFS. However as a heuristic I would suggest prioritizing exploration of longer configurations first, e.g., using a priority queue that is keyed on $\ell$. (Equivalently, you can think of this as using Dijkstra's algorithm where the length of each edge is the number of symbols appended -- the amount that it increases the length of the sequence.)

The problem with this approach is that it might end up using some of the $n$ strings more than once. Here is one way to fix that: now a configuration is given by $\langle i,j,\ell,S \rangle$, where $S$ represents the subset of $n$ strings that were used to construct this string. Unfortunately, now there can be exponentially many configurations.

A possible advantage of this approach is that you don't try to explore all orderings: you can prune sequences can't possibly be present in any valid answer, and thus possibly explore fewer than all possible subsets and orders. That said, this could still take exponential time in the worst case, so it might fail to be feasible.

This approach *is* asymptotically slightly better than the brute-force approach of exhaustively trying all possible sequences. The brute-force algorithm takes $O(n!) = O(2^{n \log n + O(n)})$ time. The approach I list here takes $O(n^3 2^n) = O(2^{n + O(\lg n)})$ time, which is better... but still exponential, alas.
> 0 votes

# Answer
Your problem is $\text{NP}$-hard. It is an optimization version of the following decision problem. \begin{array}{|l|} \hline \textbf{Decision problem }\mathcal{P}\textbf{:}\\ \text{Given }n\text{ strings consisting only of \`(' and \`)', does there exist a subset of strings}\\ \text{which when concatenated in some order yield a string with balanced parenthesis?}\\ \hline \end{array}

I will now prove that Problem $\mathcal{P}$ is $\text{NP}$-hard.

---

We reduce subset sum problem which is known to be $\text{NP}$-complete to Problem $\mathcal{P}$.

**Subset Sum Problem \[NP-Complete\]:** Let $S=\\{a\_1, \cdots, a\_k\\}$ be the finite set of (including negative) integers. We need to decide whether there exists a subset $R \subseteq S$ such that sum of elements in $R$ is zero.

**Reduction to Problem $\mathcal{P}$:** We encode all $a\_i \in S$ to strings of parenthesis in the following manner.

* If $a\_i = +m$, then its string encoding is $\text{Encode}(a\_i) = \`\` \underbrace{((\cdots(}\_{m \text{ times}} "$
* If $a\_i = -m$, then its string encoding is $\text{Encode}(a\_i) =\`\` \underbrace{))\cdots)}\_{m \text{ times}} "$

Now we encode sum operation. Let $S' = \\{a\_1, a\_2, \cdots a\_q \\} \subseteq S$ be any non-empty set such that $a\_1 \geq a\_2 \geq \cdots \geq a\_q$. Then sum over $S'$, $\Sigma \ S' = \text{Encode}(a\_1) \circ \text{Encode}(a\_2) \circ \dots \circ \text{Encode}(a\_q)$, where $\circ$ is a string concatenation operation. With this encoding, following invariant property holds: Sum of a value $(i-j)$ is encoded as a string of the form $\`\` (^i \ )^j "$. Thus, the sum is zero iff parenthesis are balanced.

You can convince yourself that this reduction is polynomial one. This proves NP-hardness of your optimization problem. One way you can solve your problem is by encoding it in SAT or Integer Linear Programs. Then you can use state of art solvers like Z3, LP\_SOLVE or GLPK to get a solution.
> -1 votes

---
Tags: algorithms, strings, permutations, algorithm-design
---


title: Is #HORNSAT polynomial?

text:
# Question
Title: Is #HORNSAT polynomial?
A *Horn clause* is a disjunctive clause of literals containing at most one unnegated literal. Examples are $$ \neg p \lor \neg r \lor \neg q,\\ \neg s \lor q,\\ \neg s \lor \neg q\lor r,\\ s,\\ \neg r \lor t,\\ \neg q \lor \neg t\lor p. $$ Determining whether or not a set of Horn clauses is simultaneously satisfiable takes polynomial time: this is the problem known as HORNSAT. The algorithm does the following:

* If there is a clause containing only a single positive literal, set the letter of that literal to true; then remove the negation of that literal from all clauses containing it. Repeat until no such clauses exist.
* Then, if there is an empty clause, the set is **not satisfiable**.
* If there is no empty clause, the set is **satisfiable**, with satisfying assignment given by setting all unset letters to false.

Following the algorithm, you can quickly see that the above set of clauses is not simultaneously satisfiable, since the last five clauses force all used letters to be true, while the first clause asks at least one to be false.

Now, the problem #HORNSAT asks the following: given a set of Horn clauses, *how many* simultaneously satisfying assignments are there? One might expect the problem to be easier than #SAT, since HORNSAT is so much easier than SAT; on the other hand, it "feels" NP-hard.

# Answer
Even if decision is easy, the counting problem #HORNSAT is #P-complete \[1\], the counting analog of NP-completeness problem. Thus it is very unlikely it has a polynomial time algorithm (for example, if $P \neq NP$ then #HORNSAT has no ptime algorithm).

See \[1\] for a dichotomy characterizing the clause restrictions leading to tractable instances of #SAT. More precisely, it is shown that the only restriction of clauses that gives tractable instances for #SAT are the clauses of the form $x\_1 \oplus x\_2 \oplus ...\oplus x\_n = 0$ where $\oplus$ is the sum modulo $2$. The other restrictions (#2-SAT, #HORNSAT, ...) are all #P-complete.

\[1\] Nadia Creignou, Miki Hermann: Complexity of Generalized Satisfiability Counting Problems. Inf. Comput. 125(1): 1-12 (1996), http://www.sciencedirect.com/science/article/pii/S0890540196900164?via%3Dihub
> 7 votes

---
Tags: complexity-theory, satisfiability
---


title: logical to physical addressing

text:
# Question
Title: logical to physical addressing
Consider the page table below (all numbers are in hex) and assume 1 KB page size. Assume 16-bit logical address and 20-bit physical address.

a.What are the page numbers and offsets for the following logical addresses: 1.1CC4 2.3A98 3.43FC 4.600C 5.2BD0 6.0

b.provide the physical address for each part a:

I figured out part a. I'm stuck on part b. Reason being, we're given a table with valid / invalid bit and a frame number. I know normally you would convert the hex value to binary and use the first set of bits to determine the page number which is used as a index to get the frame number. The issue is that information doesn't exist. This is the only info given...

I'm not sure what im doing wrong here. For example, I calculated 1CC4 being 1 using the first 4 bits. Since there's no index and no 1 in the frame number I guessed a page fault. Sadly, that can't be true because the page fault should only occur if the valid bit is set to 0. Any ideas on what i'm doing wrong here?

# Answer
With this kind of question, you always need to make sure first that you know how the logical address will be broken down.

In this case, you have a 16-bit logical address, with pages that are 1KB. 1024 == 2^10. So, you need 10 bits for offset, leaving 6 bits for the page number.

So, 0x1CC4 =\> 0001110011000100 =\> 000111 (page# 7) --- 0011000100 (offset=0xC4)

Entry 7 in your page table is valid and maps to frame 0x22.

Concatenate the frame number and the offset to get the physical address.

00001000100011000100 = 0x88C4
> 0 votes

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


# Question
Title: Maximizing the boolean combination of given real numbers with dependencies
Let $x\_i,x\_{ij}\in\mathbb{R}$ and $b\_i\in\\{0,1\\}$ for all $i,j\in\\{1,2,\ldots,n\\}$ and $j\>i$. I want to know which of all the possible boolean combinations make(s) the following expression maximal: $$\sum\_i b\_ix\_i+\sum\_{j\>i}b\_ib\_jx\_{ij}$$

I can think of greedy heuristics (for example, identify the $x\_{ij}\<0$ and then set either $b\_i$ or $b\_j$ to zero if $x\_i\<0$ or $x\_j\<0$, respectively), but these don't necessarily have always to give the best answer. Is there any optimal algorithm for this or, at least, an approximation one?

# Answer
It is often more natural to consider $b\_i \in \\{\pm 1\\}$ rather than $b\_i \in \\{0,1\\}$, and it is not difficult to convert your formulation to an equivalent one which uses $\pm 1$ variables rather than $0/1$ variables, using essentially the substitution $b'\_i = 2b\_i-1$. It is then possible to eliminate the linear term by adding a new variable $b\_0$ and replacing $x\_i$ with $x\_{0i}$. The new problem can be formulated as:

> Maximize $x' M x$ over $\\{\pm1\\}^n$, where $M$ is a symmetric matrix with zeroes on the diagonal.

(We can assume without loss of generality that $M$ is symmetric and that its diagonal elements are zero, the latter since $(\pm 1)^2 = 1$.)

This problem is known variously as *quadratic programming*, *binary quadratic programming*, *Boolean quadratic programming*, *unconstrained binary quadratic programming*, and so on; only the first term is ambiguous, since it could also refer to the continuous version of the problem.

Binary quadratic programming generalizes MAX-CUT, and so is NP-hard. In general it is (almost) NP-hard to approximate to within any constant factor, see for example On Non-Approximability for Quadratic Programs by Arora et al. For an up-to-date survey taking a more practical perspective, see The Unconstrained Binary Quadratic Programming Problem: A Survey by Kochenberger et al.
> 3 votes

---
Tags: algorithms, optimization, approximation, integer-programming
---


# Question
Title: For every two decidable languages There is a turing machine that decides if they are equal
I was wondering if this is true. I already proved that it is true for regular languages and I assume it is similar in context free languages (correct me if I am wrong), but what about languages in R that are not context-free?

# Answer
> 1 votes
Many problems that are decidable for regular languages become undecidable for context-free languages.

Even the intuitively simple problem $L = \Sigma^\*$ is undecidable for context-free $L$, where $\Sigma$ is the alphabet of the language. That of course means that equality for context-free language $L=K$ is undecidable too.

---
Tags: computability, turing-machines, context-free, undecidability
---


title: Running time of this Program

text:
# Question
Title: Running time of this Program
```
def f(n):
 i = 2
 while i < n:
  print(i)
  i = i * i

```

I evaluated an expression that becomes something like 2^n or 2^2^n and set that equal to when the loop breaks or (2^2^n ) (\>=)n but can't figure out how to get a runtime. Can someone show how to do complete this analysis and get a runtime?

# Answer
In the loop, $i$ is repeatedly squared so it will take the values $$ 2, 2^2=4, 4^2=16, 16^2=258, \dotsc $$ In other words, $i$ will be $$ 2^1, 2^2, 2^4, 2^8, \dots,2^{2^k} $$ so the loop will iterate $k$ times, until $2^{2^k}\ge n$. Taking the log of this inequality twice we'll have $k\ge \log \log n$ for our running time.
> 4 votes

---
Tags: algorithm-analysis
---


# Question
Title: How can we prove that $g = O(f) $ (Big-Oh notation)
# Problem description

I am trying to understand the first example of Big-Oh notation in Computational Complexity:A Modern Approach page 9.

If $f(n) = 100nlogn$ and $g(n) = n^2$ then we have the relations $f = O(g)$, $g = Ω(f)$, $f = o(g)$, $g = ω(f)$.

---

I understood why $f = O(g)$ and $f = o(g)$ . As for the rest I didn't. For instance in order for $g$ to be equal to $Ω(f)$ we must have $g = O(f)$.

---

# Question

How can we prove that $g = O(f)$ and $g=o(f)$?

# Answer
> 1 votes
I think you have the wrong definition for $\Omega$. When we write $g=Ω(f)$, informally this means that $g$ is bounded below by ${\displaystyle f}$ asymptotically. So, it is basically just the reverse way of saying $f=O(g)$, which means that $|f|$ is bounded above by ${\displaystyle g}$ (up to constant factor) asymptotically.

What you are describing is closest to the definition of Big theta $\Theta$.

---
Tags: asymptotics
---


title: Prefix encoding of algebraic data types

text:
# Question
Title: Prefix encoding of algebraic data types
I'm new to coding theory and formal proofs, and am struggling to understand how to construct and reason about prefix-free encoding algorithms on algebraic data types. I hope it's clear if I use notation from haskell below.

I'm tasked with writing a generic prefix encoding algorithm (`encode`) on ADTs, as well as giving guidance to my users in defining their own implementations of `encode` for their own types if they wish (this being a major reason I want to understand things better).

I've been jumping around sections of Berstel and Perrin's *Theory of Codes* which has been very helpful, but it's slow going and my goals are pretty narrow here.

### One implementation

I believe I have one obvious implementation, which works like this:

> *for products*, concatenate the results of applying `encode` to each of the children (arguments to the constructor):

```
data P a b c ... = P a b c ...

encode (P a b c...) = encode a <> encode b <> encode c <> ...

```

> *for coproducts* (or a sum of products), assign to each constructor a distinct number tag (using a prefix encoding, to be pedantic) which will start the code word, then apply the product rule above

```
data XYZ a b c d... = X a b ... | Y c d ... | Z ...

encode (X a b...) = encode 1 <> encode a <> encode b <> ...
encode (Y c d...) = encode 2 <> encode c <> encode d <> ...
encode (Z ...)    = encode 3 <> ...
...

```

The product rule I'm comfortable with: I've proved to myself that the cartesian product of two independent prefix codes is also prefix.

The coproduct rule also seems to be obviously correct if we're thinking in terms of sums-of-products, and if the product rule holds.

Where I'm struggling, I think is in reasoning about recursion, for instance for inductively-defined lists:

```
List a = Cons a (List a) | Empty

```

I believe my algorithm works in the presence of recursion, but how can I go about proving this using induction? I think my trouble is that "prefix" is a property of the (infinite) set of code words, not any one.

## Other possibly-better algorithms

A proof of the algorithm above would be helpful, but my goal is to have an algorithm that tends to generate compact code words (in fact I don't care about decoding at all; only that the range of `encode` be prefix), and so I want to understand this more fully.

For instance there is a better algorithm for `List`. An alternative would be:

```
encode l = encode (length l) <> map encode l

```

It occurred to me that maybe this is just a special case of a run-length encoding of a variation of the algorithm in section 1, where constructor tags are all concatenated *before* the concatenation of encoding the list elements.

But why should it be valid to do that? Can this algorithm for lists be generalized to produce better (more compact) prefix codes for arbitrary ADTs?

# Answer
A code is prefix-free if there does not exist any distinct two values `v`, `w` such that `encode(v)` is a prefix of `encode(w)`. So, to prove that your encoding is prefix-free, you start by considering two arbitrary distinct values `v`, `w` and demonstrate that `encode(v)` is not a prefix of `encode(w)`.

I suggest you use proof by induction on the "size" of the largest value, so you'll consider two arbitrary values `v`, `w` that are both of size at most $n$. In this case, a reasonable choice for the "size" is the number of times the recursion was applied, i.e., the number of cells in the list. Your inductive predicate $P(n)$ states that for every pair of distinct values `v`, `w` both of whose size is at most $n$, `encode(v)` is not a prefix of `encode(w)`. You want to prove $P(n)$ for all $n$. To do that using the principle of induction, you need to prove $P(0)$ and prove $P(n) \implies P(n+1)$. Here $P(0)$ is trivial, so we can focus on the inductive step $P(n) \implies P(n+1)$.

For your example of the list data structure, that shouldn't be too hard. You'll just case-split on the size and structure of `v`, `w`. There are four cases:

* case (a): `v` has size $\le n$, `w` has size $\le n$
* case (b): `v` has size $\le n$, `w` has size $n+1$
* case (c): `v` has size $n+1$, `w` has size $\le n$
* case (d): `v` has size $n+1$, `w` has size $n+1$

Case (a) is already covered by $P(n)$, so you only need to reason about the three other cases. Each one can be handled by using the induction predicate.

I'll describe how to prove case (d). You should be able to see how to handle the other cases similarly. Let `a = hd(v)` and `k = tl(v)`, so that `v == a::k`. Similarly let `b = hd(w)` and `l = tl(w)` so that `w == b::l`. We can see that

```
encode(v) == encode(1) <> encode(a) <> encode(k)
encode(w) == encode(1) <> encode(b) <> encode(l)

```

Now we assumed that `v`, `w` are distinct, i.e., `v != w`. It follows that either `a != b` or `k != l`. If `a != b`, the fact that `encode` is prefix-free on ground terms implies that `encode(a)` is not a prefix of `encode(b)`, which in turn implies that `encode(v)` is not a prefix of `encode(w)`. If `a == b` and `k != l`, the inductive hypothesis $P(n)$ implies that `encode(k)` is not a prefix of `encode(l)` (since both `k` and `l` have size one less than `v`, `w`, i.e., size $n$), which in turn implies that `encode(v)` is not a prefix of `encode(w)`.

Ultimately, once you've handled all four cases, you'll have proven that `encode(v)` is not a prefix of `encode(w)` for an arbitrary pair of distinct values `v`, `w` of size $n+1$, from which $P(n+1)$ follows.

The same techniques can be applied to any algebraic data types that is formed as a recursive combination of products and co-products.
> 4 votes

---
Tags: coding-theory, encoding-scheme, inductive-datatypes
---


# Question
Title: Is the halting problem claim true with the advent of AI
Alan Turing states that, there can't be a program that can decide if a program will ever stop. But with such advances in AI, won't computers will be able to analyze code and decide like humans on whether a program will halt or not.

Am I missing something in his claim?

Or is it too fictitious?

# Answer
> 6 votes
Even if we can design better AI solving problems we did not think possible even 10 years ago, they will always be *computer programs*. And as you said it yourself, "Alan Turing states that, there can't be a program that can decide if a program will ever stop." (he actually *proved* it and not only stated it...). Thus even the best AI you can think of will not be able to decide this problem, this is *uncomputable*.

This is a **theorem**, and unless we find a new device doing computation beyond the power of Turing machine (I am not talking about faster computation, but really a new kind of computing), this will remain impossible. Even if we have whole new kind of computer defining a new concept of computation, let's call them hypercomputers, it is very likely that those hypercomputers will not be able to decide if a hypercomputer ever stops.

However, you are right in the sense that in every day life, many programs are simple enough to be analyzed and proven to terminate. Thus we can still hope to have better algorithm (using for example advances in AI), that can generate proof of terminations for a large class of programs. See for example Microsoft Terminator \[1\] which precisely address this problem in practice.

\[1\] https://en.wikipedia.org/wiki/Microsoft\_Terminator

# Answer
> 4 votes
The proof that the decision problem doesn't have an algorithmic solution does not exempt artificial intelligence techniques, as long as they're are also algorithmic in nature.

To go beyond this boundary is a matter of speculation. Current advances in AI technology, as impressive as they may be, haven't challenged the theoretical framework we currently use.

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


# Question
Title: How to reduce the low-rank matrix completion problem to integer programming?
Consider the low-rank matrix completion problem:

> Given an integer $k$ and a subset of entries of some $n \times n$ matrix, fill in the rest of the entries so that the resulting matrix has rank at most $k$.

This problem is clearly in NP, since the set of additional entries is the required certificate. Therefore, it can be written as an integer program. How can one do this?

I'm having trouble seeing how to get rid of a rank constraint, even at the expense of adding integer constraints.

# Answer
> 4 votes
Simplifying the problem:

> Given
>
> * a positive integer $r$
> * positive integers $m, n \geq 2$
> * a partial binary matrix $\mathrm A \in \\{\*, 0,1\\}^{m \times n}$ (where $\*$ denotes an unknown entry)
>
> determine whether it is possible to complete the given partial matrix $\mathrm A$ with values in $\\{0,1\\}$ such that the resulting completed matrix has rank at most $r$.

Let us consider an example.

---

### Example

Let $r = 2$, $m = n = 3$ and

$$\mathrm A = \begin{bmatrix} 1 & 1 & 1\\ 0 & 1 & 1\\ 0 & 0 & \*\end{bmatrix}$$

Visual inspection of partial matrix $\mathrm A$ tells us that if the unknown $(3,3)$ entry is $0$, then the rank of the completed matrix is $2$. However, it would be nice not to have to rely on visual inspection.

If the rank is at most $2$, then there are matrices $\mathrm U, \mathrm V \in \\{0,1\\}^{3 \times 2}$ such that $\rm A = U V^{\top}$ holds at all known entries of $\rm A$. From the $(1,1)$ entry, we obtain the equation

$$(u\_{11} \cdot v\_{11}) \oplus (u\_{12} \cdot v\_{12}) = 1$$

where addition and multiplication are done over the finite field $\mathbb F\_2$. Translating the equation above to propositional logic, we obtain

$$\Phi\_{11} := \mbox{Xor} \left( u\_{11} \land v\_{11}, u\_{12} \land v\_{12} \right)$$

If $a\_{ij} = 1$, we have $\Phi\_{ij}$. If $a\_{ij} = 0$, we have $\neg \Phi\_{ij}$. Taking the conjunction of the CNFs of $\Phi\_{ij}$ or $\neg \Phi\_{ij}$, we obtain the following formula

$$\Psi := \mbox{CNF} (\Phi\_{11}) \land \mbox{CNF} (\neg \Phi\_{21}) \land \mbox{CNF} (\neg \Phi\_{31}) \land \mbox{CNF} (\Phi\_{12}) \land \mbox{CNF} (\Phi\_{22}) \land \mbox{CNF} (\neg \Phi\_{32}) \land \mbox{CNF} (\Phi\_{13}) \land \mbox{CNF} (\Phi\_{23})$$

which is in CNF by construction. If $\Psi$ is **satisfiable**, then there are matrices $\mathrm U, \mathrm V \in \\{0,1\\}^{3 \times 2}$ such that $\rm A = U V^{\top}$ holds at all known entries of $\rm A$. Using SymPy:

```
from sympy import *

u11, u12, u21, u22, u31, u32 = symbols('u11 u12 u21 u22 u31 u32')
v11, v12, v21, v22, v31, v32 = symbols('v11 v12 v21 v22 v31 v32')

Phi11 = Xor(u11 & v11, u12 & v12)
Phi21 = Xor(u21 & v11, u22 & v12)
Phi31 = Xor(u31 & v11, u32 & v12)

Phi12 = Xor(u11 & v21, u12 & v22)
Phi22 = Xor(u21 & v21, u22 & v22)
Phi32 = Xor(u31 & v21, u32 & v22)

Phi13 = Xor(u11 & v31, u12 & v32)
Phi23 = Xor(u21 & v31, u22 & v32)
Phi33 = Xor(u31 & v31, u32 & v32)

Psi = to_cnf(Phi11) & to_cnf(Not(Phi21)) & to_cnf(Not(Phi31)) & to_cnf(Phi12) & to_cnf(Phi22) & to_cnf(Not(Phi32)) & to_cnf(Phi13) & to_cnf(Phi23)

print "Formula Psi is \n", Psi

# is Psi satisfiable?
print "\nSatisfiable? \n", satisfiable(Psi)

```

produces $\Psi$ (in CNF)

```
And(Or(Not(u11), Not(u12), Not(v11), Not(v12)), Or(Not(u11), Not(u12), Not(v21), Not(v22)), Or(Not(u11), Not(u12), Not(v31), Not(v32)), Or(Not(u21), Not(u22), Not(v21), Not(v22)), Or(Not(u21), Not(u22), Not(v31), Not(v32)), Or(Not(u21), Not(v11), u22), Or(Not(u21), Not(v11), v12), Or(Not(u22), Not(v12), u21), Or(Not(u22), Not(v12), v11), Or(Not(u31), Not(v11), u32), Or(Not(u31), Not(v11), v12), Or(Not(u31), Not(v21), u32), Or(Not(u31), Not(v21), v22), Or(Not(u32), Not(v12), u31), Or(Not(u32), Not(v12), v11), Or(Not(u32), Not(v22), u31), Or(Not(u32), Not(v22), v21), Or(u11, u12), Or(u11, v12), Or(u11, v22), Or(u11, v32), Or(u12, v11), Or(u12, v21), Or(u12, v31), Or(u21, u22), Or(u21, v22), Or(u21, v32), Or(u22, v21), Or(u22, v31), Or(v11, v12), Or(v21, v22), Or(v31, v32))

```

and the satisfying assignment

```
{v31: False, v11: True, v32: True, u31: False, v22: True, u22: True, u11: True, v21: False, u12: True, u21: False, v12: False, u32: False}

```

Hence,

$$\mathrm U = \begin{bmatrix} 1 & 1\\ 0 & 1\\ 0 & 0\end{bmatrix}$$

$$\mathrm V = \begin{bmatrix} 1 & 0\\ 0 & 1\\ 0 & 1\end{bmatrix}$$

and, thus,

$$\mathrm U \mathrm V^{\top} = \begin{bmatrix} 1 & 0 & 0\\ 0 & 0 & 0\\ 0 & 0 & 0\end{bmatrix} + \begin{bmatrix} 0 & 1 & 1\\ 0 & 1 & 1\\ 0 & 0 & 0\end{bmatrix} = \begin{bmatrix} 1 & 1 & 1\\ 0 & 1 & 1\\ 0 & 0 & \color{red}{0}\end{bmatrix}$$

Thus, if the missing entry of $\rm A$ is *zero*, then we obtain a rank-$2$ matrix.

Translating to binary **integer programming**, formula $x\_i \lor x\_j$ becomes the linear inequality $x\_i + x\_j \geq 1$ and $\neg x\_i$ becomes $1-x\_i$. From $\Psi$ (in CNF), we obtain $32$ linear inequalities

$$\begin{array}{rl} - u\_{11} - u\_{12} - v\_{11} - v\_{12} &\geq -3\\ - u\_{11} - u\_{12} - v\_{21} - v\_{22} &\geq -3\\ & \vdots\\ v\_{31} + v\_{32} &\geq 1\end{array}$$

plus the inequality constraints $0 \leq u\_{ij}, v\_{ij} \leq 1$ and the integrality constraints $u\_{ij}, v\_{ij} \in \mathbb Z$.

To summarize, we reduced a simplified version of the original matrix completion problem to SAT and then we reduced SAT to binary integer programming. However, the reduction to SAT requires the computation of the CNF of either $\Phi\_{ij}$ or $\neg \Phi\_{ij}$, which produces a formula whose number of conjuncts may be **non-polynomial** in $r$.

# Answer
> 3 votes
Building on Rodrigo de Azevedo's answer, and assuming that you are dealing with binary matrices with all arithmetic done modulo 2, here is a more direct way to reduce this problem to integer linear programming:

A $n \times n$ matrix $M$ has rank $\le r$ iff there exist $n \times r$ matrices $U,V$ such that $M = UV^\top$. So, we can treat the entries of $U,V$ as unknowns (zero-or-one variables), and express the requirement that $M=UV^\top$ as a bunch of constraints, and see if there is any assignment to the variables that makes $M=UV^\top$ hold (for all of the entries of $M$ that are given).

Each constraint has the form

$$M\_{ij} = \sum\_{k=1}^r U\_{ik} V\_{jk} \pmod 2$$

where the $i,j$ cell of the partial matrix is filled with the value $M\_{ij}$, and all arithmetic is done modulo 2.

Equivalently, this can be expressed as

$$M\_{ij} = \sum\_{k=1}^r U\_{ik} V\_{jk} - 2 S\_{ij}$$

where $S\_{ij}$ is some integer. We'll introduce fresh new temporary variables $T\_{ijk},S\_{ij}$ where $S\_{ij}$ is constrained to be an integer and $T\_{ijk}$ is constrained to be zero or one ($0 \le T\_{ijk} \le 1$). We'll add some linear constraints to force that $T\_{ijk} = U\_{ik} V\_{jk}$. Then we'll be able to write

$$M\_{ij} = \sum\_{k=1}^r T\_{ijk} - 2 S\_{ij}$$

which is a linear inequality.

So, all that remains is to express $T\_{ijk} = U\_{ik} V\_{jk}$ (a nonlinear constraint) using *linear* inequalities. That can be done using the methods in Express boolean logic operations in zero-one integer linear programming (ILP). In particular, we can do that using the inequalities $T\_{ijk} \ge U\_{ik} + V\_{jk} - 1$, $T\_{ijk} \le U\_{ik}$, $T\_{ijk} \le V\_{jk}$.

In this way, we obtain an integer program that uses only linear inequalities to express all of the constraints. It has $O(n^2r)$ variables and $O(n^2r)$ inequalities.

---
Tags: complexity-theory, reductions, decision-problem, matrices, integer-programming
---


# Question
Title: Prove that my NP-complete problem is strong
I have two problems, one of which is solved using dynamic programming. I showed that it is NP-complete (a knapsack variant), therefore having this dynamic programming solution says that this one is weakly NP-complete. Right?

Then, in the second problem I have added a new dimension to the problem which makes is more complicated. It is still NP-complete and I assume that this one is strongly NP-complete.

Is there a way to prove that it is 'strongly' NP-complete?

**Update:**

I can show that the second problem needs to solve $2^n$ instances of the first problem, where $n$ is the size of problem.

# Answer
> 1 votes
You've asked two questions. To answer the first question:

Not quite right. It depends on the running time of your dynamic programming algorithm. To show that the problem is weakly NP-complete, you should show that there is an algorithm whose running time is polynomial if the input is represented in unary. So, you'll first need to prove that your dynamic programming algorithm has that property.

To answer the second question:

If in doubt, go back to the definition. Wikipedia has a page with a definition of strongly NP-complete; it says

> A problem is said to be strongly NP-complete (NP-complete in the strong sense), if it remains so even when all of its numerical parameters are bounded by a polynomial in the length of the input.

So, that's what you need to prove. It's hard to say much more without knowing what the specific problem is.

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


# Question
Title: Simulating Turing Machine with writing only on non-input fields on read-only Turing machine
*Can you show me how to simulate Turing Machine with writing only on non-input fields on read-only Turing machine ?*

I tried to do it be using internal states, but it provides me to infinitely many states, what is not allowed.
Any ideas ?

**Edit**
I consider standard Turing machines - one leftly-infinite tape.
read-only Turing machine is for me Turing machine such that it can't write on tape.
non-input fields - I mean part of tape where input is given. For example,
`abcd#####...`., machine can't overwrite `abcd` but it can overwrite each `#`. However, readonly can only read this tape, so no changes.

**Edit II**
I am searching for solution in which we use functions and Myhill-Nerode theorem. Can anyone provide this kind of solution ?

# Answer
> 1 votes
By Single-tape Turing Machines with write-protected input recognize only Regular Languages, a Turing machine that writes only on non-input fields accepts a regular language.

Any regular language can be accepted by a read-only Turing machine: just form a DFA for the regular language, then use that as the finite-state control of the Turing machine and scan the input from left to right.

Chaining those two facts together gives a full proof of the statement.

---
Tags: complexity-theory, computability, turing-machines
---


title: Maximum flow properties

text:
# Question
Title: Maximum flow properties
I was trying to solve problems in max flow algorithms. And I came across this MIT Lecture Quiz.

http://people.csail.mit.edu/moitra/docs/6854hw4.pdf

solution : http://people.csail.mit.edu/moitra/docs/6854hw4solns.pdf

Questions :

(a) In any maximum flow, and for all vertices v and w, either the amount of flow from v to w (f(v, w)) or the amount of flow from w to v (f(w, v)) is 0.

(b) Consider a directed graph G = (V, E). There always exists a maximum flow of G such that, for all vertices v and w, either the amount flow on vw or the amount of flow on wv is 0.

These two problems look one and the same. And both are based on the trick of 'Flow conservation on any vertex'. The main properties of both problems are the same. except that

first problem ---\> any flow (all flow)

second problem --\> a flow (at least one flow)

So this made the difference

problem 1 -\> False (because any flow on subtraction and add to incoming and out going we can make it non zero. So the statement 'ALL FLOWS' makes this statement false)

problem 2 -\> True (because any flow on subtraction and add to incoming and out going we can make it non zero, so whatever be the flow, we can make manipulations such that one is zero and other is non zero. so there is 'A FLOW' with this property. this 'A FLOW' makes this statement true.

Am I right in my understanding of the key difference in both the questions, thought both look almost the same ?

# Answer
> 2 votes
A helpful way to build intuition: Try working through an example! Can you find an example of a graph and a flow where property (a) is true? Then, ask yourself: is property (b) true in that one? What made the difference?

Spoiler (but it's best to try the above first; it will help you learn more from this exercise):

> The crucial difference is between "for every maximum flow" vs "there exists a maximum flow". That's the difference between $\forall$ vs $\exists$. As you probably know, $\forall x . P(x)$ can be false even if $\exists x . P(x)$ is true.

---
Tags: algorithms, algorithm-analysis, network-flow, ford-fulkerson
---


title: What is the "Chairman Tree"?

text:
# Question
Title: What is the "Chairman Tree"?
My competitive programming coach told me of a balanced binary tree used by a lot of Chinese competitors that has all the functions of any other balanced binary tree **and is fully persistent** and runs queries and updates in ${O(log^2N)}.$ What information is there on this tree, and does it go by a different, more popular name?

To be clear, any data structure that fulfills the above will be considered as a correct answer. The first one will be marked correct. If there is a link, that would be the best.

# Answer
*Chairman Tree* is an alias of the data structure *Functional Segment Tree*. Its construction is fundamentally similar to a segment tree, only that it supports retroactive queries and modifications.

Every retroactive version is created by attaching new child nodes to the old parent node without modifying the original child node. Clearly, as the depth of a *Chairman Tree* should be no larger than $O(\log n)$, newly created nodes should be no more than $O(\log n)$ per operation. Therefore, total time complexity and memory complexity both equals to $O(n \log n)$.

Queries are performed by subtracting two versions and running a binary search, which might increase its time complexity to $O(n \log^2 n)$, should it contain modify operations. Note that modify operations are only available while operations can be performed **offline**.

Here's a paper which might help you understand functional data structures better: Purely Functional Data Structures

---

For the reason why it is called a *Chairman Tree*, let me take some time to explain. This data structure is first *widely* introduced in China by an OI participant **@fotile96**, who had been unable to code a *Partition Tree* which also performs retroactive operations, had to invent another data structure that was called a *Functional Segment Tree*. However, the phonetic letters of **@fotile96** was the same as the former president of People's Republic of China, other participants happened to call him *Chairman*, which induced the name of *Chairman Tree*.

The inventor himself showed reluctance to the name, however.

Here's a link in Chinese which demonstrated the question: https://www.zhihu.com/question/31133885
> 5 votes

# Answer
I've been doing competitive programming for several years at a very high level and haven't ever heard of a *Chairman tree*. Though I still can tell you how to make any data structure persistent. In case of BSTs and segment trees it even doesn't increase the running time (asymptotically, of course; you can notice some slowdown in practice).

First, let's consider a basic segment tree. I'll write C++-ish code because such trees, when made persistent, are most conveniently interpreted with pointers. For sake of simplicity I'll describe a (rather stupid) tree with two simple operations: assign a number to a position $i$ and get a number on a position $i$.

```
struct node {
    int l, r;
    node *L, *R;
    int value;

    void put(int i, int x) {
        if (l == r) value = x;
        else if (i <= L->r) L->put(i, value);
        else R->put(i, value);
    }

    void get(int i) {
        if (l == r) return x;
        else if (i <= L->r) return L->get(i);
        else return R->get(i);
    }
}

```

For those who are not familiar with notation (though it should be clear from the code): a node represents a segment $\[l, r\]$ of an array. When $l = r$ the node is a single element, else it has two children, $L$ and $R$, having ranges, respectively, $\[l, (l+r)/2\]$ and $\[(l+r)/2+1, r\]$.

When you put a value to a tree, you modify it. But we may notice that each modification touches only $O(\log n)$ nodes of a tree, so instead of modifying existing nodes we may copy them and apply updates only to the new vertex.

Here is the outline: whenever the function wants to modify a node, it makes a copy, modifies a copy and returns the copy back to the caller (because the caller wants to update himself too). In this example only `put` must be modified, and here we go:

```
node* put(int i, int x) {
    node *t = this->makeCopy();

    if (l == r) t->value = x;
    else if (i <= L->r) t->L = t->L->put(i, value);
    else t->R = t->R->put(i, value);

    return t;
}

```

Voi-la! Now we have got a fully-functional persistent array which takes $O(\log n)$ time and space per operation. You only have to store pointers to the roots of versions you need, and as long as the pointer is saved, it will stay untouched. Forever.

The very same technique may be applied to any kind of a segment tree, giving no overhead in time (because segment tree queries are already $O(\log n)$. More, you can use this approach with BST's. The most reasonable choice of a structure to make persistent is a Treap, mostly because it does not require storing pointers to parents. It might be hard to understand which values exactly one should clone while splitting and merging, but it is done in several minutes with pencil and paper.

Now a bonus and a tiny warning. First, you can make *any* data structure persistent: just implement it using persistent arrays :) If the structure itself is not tree-ish, this will cost you a logarithmic increase in time, of course. Second, this technique cannot be applied to any DS which running time is amortized, so be careful with persistent splay tree.

Hope this helps, and don't hesitate to ask something in comments!
> 5 votes

---
Tags: data-structures, trees, persistent-data-structure
---


# Question
Title: How to show that cross entropy is minimized?
This Question is taken from the book Neural Networks and DeepLearning by Michael Nielsen

The Question: In a single-neuron ,It is argued that the cross-entropy is small if **σ(z)≈y** for all training inputs. The argument relied on **y** being equal to either **0** or **1**. This is usually true in classification problems, but for other problems (e.g., regression problems) **y can sometimes take values intermediate between 0 and 1**. Show that the cross-entropy is still minimized when σ(z)=y for all training inputs. When this is the case the cross-entropy has the value:

C is the cost function

σ is the sigmoid function

y is the expected output of the network

---

I am not sure if I understand the question correctly.If σ(z)=y wouldn't the partial derivative of C with respect to the weights(or Bias) be equal to zero?This will imply that the weight is already at the correct value and the cost function cannot be reduced any further by changing the weight.

z is the weighted input to the neuron.(z=wx+b)

Where b is the bias and x is the activation of a neuron in the previous layer.(In this case it is the input to the network itself)

w is the weight value

# Answer
You are calculating the so-called binary cross-entropy. Let $f(\cdot)$ be a sigmoid function. The binary cross-entropy between $y$ and $f(t)$ is

$$ F(t,y) = H(y,f(t)) = -y\log f(t) - (1-y)\log(1-f(t)). $$

When you compute the partial derivative of $F(t,y)$ with respect to $t$, you get:

$$ \frac{\partial F(t,y)}{\partial t} = f(t) - y $$

You reach the minimum when $f(t)=y$. In case of multiple variables, let:

$$ F(\vec{t},\vec{y}) = \frac{1}{n}\sum\_{i=1}^n F(t\_i,y\_i) $$

so

$$ \frac{\partial F(\vec{t},\vec{y})}{\partial t\_i} = \frac{f(t\_i) - y\_i}{n} $$

Now, if $t\_i=\sum\_j w\_{ij}x\_j+b\_i$ is the activation, with the chain rule:

$$ \frac{\partial F(\vec{t},\vec{y})}{\partial w\_{ij}}=\sum\_k\frac{\partial F(\vec{t},\vec{y})}{\partial t\_k}\cdot\frac{\partial t\_k}{\partial w\_{ij}}=\frac{1}{n}\cdot x\_j\cdot\[f(t\_i) - y\_i\]$$
> 5 votes

---
Tags: machine-learning, neural-networks, gradient-descent
---


# Question
Title: What does the symbol "::" mean in computer science?
What does the symbol $::$ mean in the following statement?

$\forall{x}\in K :: x \longrightarrow x$

A cycle in a graph is a path that starts and ends on the same node. Clearly, if nodes in K lie on a cycle, then $\forall{x}\in K :: x \longrightarrow x$.

Look at page 56 in the following.

https://books.google.co.in/books?id=nel4vdeLcqkC&pg=PR7&source=gbs\_selected\_pages&cad=2#v=onepage&q&f=false

# Answer
It is a delimiter between to parts of expression. You can think of it as notation for the English phrase 'such that'. Read your formula as $\`\` \forall x\in K \text{ such that } x \longrightarrow x"$.
> -1 votes

---
Tags: sets
---


# Question
Title: Is P the set of all algorithms whose run-time is $O\left( n^{ O \left( 1 \right) }\right)$?
I'm coming to Computer Science from Mathematics and am familiar with the idea of building classes of objects using Propositional Logic. Namely, start with some universe of objects, define some proposition $P \left( x \right)$, and then iterate over the universe of objects, applying $P \left( x \right)$ to each; keep the objects for which $P \left( x \right)$ is true; exclude each object for which $P \left( x \right)$ is false.

So, when we define a class of objects called $\mathbb{P}$ (as in P vs NP), I really need to see a formal definition of the proposition used to build that class--as well as a formal definition of the universe of objects we're starting with.

### Defining the Universe of Discourse, $\mathbb{U}$

My understanding is that, for the question of $\mathbb{P}$ vs $\mathbb{NP}$, our universe of discourse is all decision problems that are satisfiable. Namely, problems that can be implemented in boolean logic, return a boolean result, and that someone somewhere at some point has found a finite sequence of inputs that cause the implementation to return $TRUE$.

In spite of Russell's Paradox, let us define our universe of discourse as the set $\mathbb{U}$.

### Defining $\mathbb{P}$

$\mathbb{P}$ is a subset of $\mathbb{U}$. Namely, it is the set of all objects in $\mathbb{U}$ for which the following proposition returns $TRUE$:

> This object can be written as a decision problem that returns a boolean value--and that decision problem takes at most $O \left( n^{O \left( 1 \right)} \right)$ time.

That is, given some implementation of a decision problem in $\mathbb{U}$, if that implementation takes at most polynomial time, we can include that implementation in $\mathbb{P}$.

### The Point I Need Clarified

Are we really using $O \left( n^{O \left( 1 \right)} \right)$ to define $\mathbb{P}$? Or are we using $\theta \left( n^{O \left( 1 \right)} \right)$? $O \left( n^{O \left( 1 \right)} \right)$ seems right to me, but--so often material I study from doesn't distinguish between Big-O and Big-Theta. So, I need to clarify.

For example, given the following simple, Java-like implementation of an algorithm:

```
function boolean isOne(int input) {
    return input == 1;
}

```

Should I include this algorithm in $\mathbb{P}$? It is clearly faster than polynomial time; it is constant time. So, it is $O \left( n^{O \left( 1 \right)} \right)$ but not $\theta \left( n^{O \left( 1 \right)} \right)$--as long as zero $\not\in O \left( 1 \right)$?

Should I include it in $\mathbb{P}$?

If zero $\in O \left( 1 \right)$, then is a constant time algorithm in $\theta \left( n^{O \left( 1 \right)} \right)$?

# Answer
> 4 votes
> Should I include this algorithm in $\mathbb{P}$?

Yes. Since the algorithm is asymptotically bounded above by $O(n)$ the algorithm is in $\mathbb{P}$.

> If zero $\in O(1)$, . . .

Zero is in $O(1)$.

> . . . so often material I study from doesn't distinguish between Big-O and Big-Theta

big-O pertains to an asymptotic upper bound, where big-Theta pertains to an asymptotic tight bound.

The formal definition: $$f(n) \in O(g(n)) \iff \exists N\_0,c\in\mathbb{R}^+ \text{ such that } n\>N\_0 \implies 0 \leq f(n) \leq cg(n)$$ Also, $$f(n) \in \Theta(g(n)) \iff \exists N\_0, c\_1, c\_2 \in \mathbb{R}^+ \text{ such that } n\>N\_0 \implies c\_1g(n)\leq f(n)\leq c\_2g(n)$$

For example, $f(n) = n^2 + 3n \in O(n^3)$ and $f(n) \in O(n^2)$. But, $f(n) \not\in \Theta(n^3)$, yet $f(n) \in \Theta(n^2)$.

We can't use $\Theta(n^{O(1)})$ to describe $\mathbb{P}$, as $O(lg(n))$ isn't in $\Theta(n^{O(1)})$, but is in $O(n^{O(1)})$ (and is in $\mathbb{P}$).

# Answer
> 0 votes
P is not a set of algorithms, it is a set of *languages*, where a language is a subset of $\\{0, 1\\}^\*$. In your terminology, the universe of discourse is the power set of $\\{0, 1\\}^\*$ (Russell's paradox is not an issue). P contains exactly those languages $L$ for which there exists a Turing machine $M$ with the following properties.

* When given any $x \in \\{0, 1\\}^\*$ as input, $M$ returns *yes* if $x \in L$, otherwise it returns *no*.
* The time complexity function $f\_M(n)$ of $M$ is $O(p(n))$ for some polynomial $p$. The time complexity function $f\_M(n)$ gives the maximum number of steps for $M$ to halt (with answer *yes* or *no*) on any input $x \in \\{0, 1\\}^\*$ such that $n = |x|$.

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


# Question
Title: Find the maximum (longest) delay to last user in a multicast T. NP complete proof
Given a un-directed weighted graph G=(V,E) where V is the set of vertices and E is the set of edges between vertices, and weights are the time delays on each link between two user. The goal is to construct a multicast tree T (that connects source node to a set of nodes say K) such that to minimize the maximum (longest) delay of the last user in the multicast tree T. The maximum (longest) delay of the multicast tree T should be less than or equal to say d. Thus it seems a an NP-Complete problem but I don't know how to prove it or reduce it. I will appreciate your kind feedback. Thank you

# Answer
> 1 votes
Refer to Shorted Path Tree (SPT)- https://en.wikipedia.org/wiki/Shortest-path\_tree It ensures that the delay from source node is always minimum for all the nodes including the maximal ones.

Based on your problem description I think it is SPT. If that's the case, it is not a $\text{NP}$-hard problem.

---
Tags: complexity-theory, algorithm-analysis, np-complete, decision-problem, spanning-trees
---