# Question
Title: difference between "addressable" and "address" in memory?
I'm struggle on this practice question from this site....

> Calculate the number of bits required in the address for memory having size of 16 GB. Assume the memory is 4-byte addressable.

MY QUESTION IS: what is the difference between an "address" and "the memory is 4 byte addressable"?

I understand an address would be its location in memory that is represented by bits, such as 2^n, where n is the number of bits in the address. But I'm confused about addressable in this question and how that's different than address

2^n * 4 bytes = 2^34 The solution is 32 bits

# Answer
*Address* is a label that identifies a memory location. *The memory is $4$ byte addressable* means that you have labels that refer to memory locations of size $4$ bytes. You don't have names for smaller sizes. For example, if we have a memory of $12$ bytes and the memory is $4$ byte addressable, then we can have $3$ blocks of memory to which we can assign an address. Their addresses could be `Memory block 1`, `The glorious block 2` and `Ceres`. Instead of fancy long names what is common is for the addresses to be binary numbers. Since there are $3$ addresses, then we need at least $2$ bits.

In your problem, instead of $12$ bytes, you have $16$ GB ${}=2^{34}$ bytes. The memory is $4$ byte addressable. So, we can have $2^{34}/4=2^{32}$ different addresses. So, we need $32$ bits to encode all addresses.
> 8 votes

---
Tags: memory-management
---


title: Basic Binary search tree query

text:
# Question
Title: Basic Binary search tree query
Inorder traversal of BST is always sorted.But can we say Binary tree is BST if and only if inorder is sorted?I mean if inorder is sorted,can we conclude it is always BST?

# Answer
If the height is $0$ it is true.

Assume that all binary trees for which inorder is sorted and height smaller than $h$ are BST.

Consider a tree with root $x$, height $h$ and its inorder is sorted. In particular its left and right subtrees' inorder are sorted and have height smaller than $h$. Then, by the assumption, they are BST. Now, in the inorder of the given tree, the node $x$ is listed after all nodes of its left subtree. Since its inorder is sorted, then $x$ is not smaller than any node of its left subtree. Likewise, $x$ is not larger than any node of its right subtree. Therefore, the tree is a BST.

Hence, by induction on the height of the binary tree, all binary trees for which inorder is sorted are BST.
> 1 votes

---
Tags: data-structures, trees, binary-trees
---


# Question
Title: How do I do a biased shuffling of a deck of cards?
I currently have a deck of cards (in fact this deck is an array of sorted elements in descending order as indicated by the picture above), that I want to shuffle. However, the caveat is that I want the card near the top of the deck to be shuffled to a new position relatively close to the top, while a card near the bottom to be shuffled anywhere including the middle and bottom, but have a very unlikely chance of ending up near the top of the deck.

Therefore I would break down the problem as following:

A card in the **top 33%** of the deck has about:

* 90% chance of ending up in the top 33%
* 8% chance of ending up in the middle 33%
* 2 % chance of ending up in the bottom 33%

A card in the **middle 33%** of the deck has about:

* 5% chance of ending up in the top 33%
* 90% chance of ending up in the middle 33%
* 5 % chance of ending up in the bottom 33%

A card in the **bottom 33%** of the deck has about:

* 2% chance of ending up in the top 33%
* 8% chance of ending up in the middle 33%
* 90 % chance of ending up in the bottom 33%

The percentages of the shuffle do not need to be constant. I wouldn't mind if they were continuous probabilities across the entire deck. Would this boil down to a randomized selection problem? I have no clue as to how to approach this problem as of now.

# Answer
I needed this same thing, a biased shuffling for local/proximity shuffling, but couldn't find any answers, so this is my attempt to create one.

**Pseudocode:**

```
For X passes through the array from 0 to len(array)-1:
    Roll for a 50% chance to swap index and index+1
    Swap direction of array traversal

```

**Python:**

```
import numpy as np
import matplotlib.pyplot as plt

swap_passes = 50

player_count = 100

positions = {}

player = np.arange(1,player_count+1)
for p in player:
    positions[p] = []

for i in range(10000):
    player = np.arange(1,player_count+1)

    for j in range(swap_passes):
        pre_rand = np.random.randint(0,2,player_count)
        if j%2 == 0:
            for i in range(len(player)-1):
                if pre_rand[i] == 0:
                    player[i], player[i+1] = player[i+1], player[i]
        else:
            for i in range(len(player)-1,0,-1):
                if pre_rand[i] == 0:
                    player[i], player[i-1] = player[i-1], player[i]

    for idx, p in enumerate(player):
        positions[p].append(idx)

fcs = [(1,0,0,0.3),(0,1,0,0.3),(0,0,1,0.3),(0.5,0.5,0,0.3),(0,0.5,0.5,0.3)]
plt.figure()
for idx, i in enumerate([1,30,50,70,100]):
    bins = np.arange(0,player_count+1)
    plt.hist(positions[i], bins=bins, fc=fcs[idx])
plt.title('Histogram of indices: 1, 30, 50, 70, 100. 10000 trials, 50 swap passes.')

```

**Results:**

Looks roughly gaussian. Increasing the number of passes will increase the spread of the distribution.
> 1 votes

---
Tags: probability-theory, randomized-algorithms
---


# Question
Title: Comments on "Which combinatorial problem is similar to this problem?"
Regarding the post Which combinatorial problem is similar to this problem?, it is quite hard to believe that, in the absence of information on the cost function, there is no algorithm better than exhaustive search to tackle this apparently easy-to-understand problem. I surfed the Internet and found something called the Weighted Constraint Satisfaction Problem, and I wonder whether this can be of any use in this case.

Any advise would be much appreciated.

EDIT: The problem I have at hand is a regression problem where each of $p$ inputs, $x\_1, x\_2, x\_3, \cdots, x\_p$, needs to undergo a variable transformation using one of $q$ functions from a set of available functions $F = \\{ f\_1, f\_2, f\_3, \cdots, f\_q \\}$. The cost function is the Mean Square Error (MSE) defined as $MSE = \frac{1}{n} \sum\_{k=1}^n (y\_k - \hat{y}\_k)^2$, where $n$ is the number of samples and for each $k$, $y\_k$ is an experimental value and $\hat{y}\_k$ is the predicted value computed by some method (e.g., as from a Gaussian Process Regression) using the transformations ($f\_j(x\_i)$) as input variables. This method must be also selected from a set $M = \\{ M\_1, M\_2, M\_3, \cdots, M\_m \\}$ of widely different available methods. The objective is to decide which function transforms each one of the $p$ inputs and which method to use such that $MSE$ is minimum. There are no constraints whatsoever. I think in this case there is no structure to take advantage of since the cost function changes form depending on the choice of the method.

# Answer
> 1 votes
You are probably assuming that the cost function is efficiently computable, so that "does there exist a selection of the $n$ options with less than $c$ cost" is an NP decision problem. This assumption is not actually stated in the original question. The question merely states "The cost function can be any function, not necessarily linear."

As D.W.'s answer says, "you will need to know something about the cost function and take advantage of some structure or properties it has." Making the assumption that the cost function can be computed in time polynomial in $n$ gives it a little bit of structure. (Exactly how *much* structure this gives it is the essence of the P vs. NP problem.)

---
Tags: complexity-theory
---


# Question
Title: Which combinatorial problem is similar to this problem?
I have $n$ clients and for each client I have different options to choose from, for example, $C= \\{C\_1,C\_2 \\}$. For each combination of $n$ options, there is a cost. I want to choose the best combination that minimizes the cost without calculating the cost for each option one by one and then choose the best one and I do not have any constraints. Which combinatorial problem is similar to this one?

For example, If I have $n=3$ and $C =\\{1,2\\}$, I have set of triples $(x\_1,x\_2,x\_3)$ as $\mathcal{M}= \\{(1,2,1),(1,2,2),(1,1,1),(1,1,2),(2,1,1),(2,1,2),(2,2,1),(2,2,2)\\}$ and equation $cost=x\_1+x\_2+2x\_3$ I want to find the triple that minimizes the cost without calculating one by one. The cost function can be any function not nessesary linear.

# Answer
If the cost function can be any function, then in general there is no algorithm whose performance is better trying all possibilities (in terms of worst-case performance).

This is indicating to you that if you want to do better, you will need to know something about the cost function and take advantage of some structure or properties it has.
> 2 votes

# Answer
In a very literal sense, D.W.'s answer is correct. In the absence of any information about the cost function, there are no alternatives better than simply trying the cost function at each possible input.

However, in real-world applications, we usually know *something* about the cost function—and as soon as we have a little bit of structure, we can leverage that to create more efficient search strategies.

For example, if the cost function has a relatively simple closed form in terms of the inputs, you may be able to apply an optimizing SMT solver such as the widely-used Z3 from Microsoft Research (interactive tutorial here). These solvers use complex strategies to locate and exploit hidden structure in the input problem and find solutions more efficiently than brute-force search.
> 3 votes

---
Tags: complexity-theory
---


# Question
Title: Computational power of a Turing Machine with infinite states
Consider a turing machine with infinite states. This machine is identical to a regular machine. Only that number of states could be infinite. Does this machine has more computational power than a regular machine ?

If yes - Then show that a machine with infinite states can recognize languages that cannot be recognized with a machine that has a finite number of states... ( and how this doesnt contradict the church turing hypothesis)

If no - show how a machine with a finite number of states could imitate the operation of a machine with an infinite number of states..

The main thing to notice above is that the question is about recognizing a language and not deciding a language.

# Answer
> 2 votes
Any language can be recognized by a Turing machine with an infinite number of states. Let the state graph be an infinite trie; scan over the input from left to right once, and you end up at a unique state for each possible input string.

By contrast, if you are familiar with different cardinalities of infinite set, it is easy to see that there must be some language not accepted by any Turing machine with a finite number of states. There are uncountably many languages and only countably many finite Turing machines. This argument works for *any* method of describing languages using descriptions of finite size: no such method can give a description for every language.

---

The Church-Turing thesis, according to Wikipedia, is the statement that

> a function on the natural numbers can be calculated by an effective method if and only if it is computable by a Turing machine.

This does not contradict that a "Turing machine with infinite states" could recognize any language, because the phrase "Turing machine" in unqualified form always refers to a machine with a finite number of states.

The very fact that extending the Turing machine model to permit an infinite state set would allow it to recognize any language means that such a model is mathematically almost useless. Saying that a language is recognized (in linear time!) by a "Turing machine with infinite states" adds no information, because that is true of every language.

---
Tags: turing-machines, automata, church-turing-thesis
---


# Question
Title: Does the term "continuity" have a different meaning in maths and in CS?
I ask this question because of some statements in the question "What is the 'continuity' as a term in computable analysis?" making me suspicious.

I'm engineer, not computer scientist, so I don't have the Turing machine but logic gates in mind when I'm thinking about algebraic operations performed with devices.

I read the answer to the question "Why are computable functions continuous?" and understood it the following way:

> Because the device's input is of infinite length (a decimal number with an infinite number of digits after the decimal point), the device (e.g. Turing machine or computer) cannot read the entire number before writing the $n$-th digit of output.
>
> Instead, the device can only have read $m(n)$ digits of the input when it writes the $n$-th digit of output.
>
> If the first $n$ digits of the output of some function only depend on the first $m(n)$ digits of the input, the function is continuous.

However, if I understand this argumentation correctly, the word "continuous" in computation theory is not identical to the word "continuous" in mathematics:

Rounding towards zero would only require reading the input until the decimal point (so $m(n)=\text{const.}$); however, the mathematical function being calculated is not "continuous" according to the mathematical definition of that term.

We could also perform a digit-wise operation ($m(n)=n$) and exchange certain digits after the decimal point; for example replace all `4`s by `9`s and all `9`s by `4`s. As far as I understand, the function being calculated is not continuous on any interval of $\mathbb{R}$ (however, it would be right-continuous on $\[0,\infty)$ and left-continuous on $(-\infty,0\]$).

And if I didn't make a conceptual mistake and we use a balanced numeral system (like a Russian computer in the 1960s) instead of the decimal system, a similar algorithm (exchanging `0`s and `1`s instead of `4`s and `9`s) would even represent a mathematical function which is *not even directional continuous* on any interval of $\mathbb{R}$.

**Questions:**

Does the computability depend on the numeral system being used (as the example with the balanced numeral system suggests) or is the term "computable" even assuming a certain numeral system being used?

Is the observation correct that the term "continuous" does not have the same meaning in maths and CS?

# Answer
> 5 votes
If we were to use the decimal expansion to represent real numbers, your reasoning would work. But that gives us a very badly behaved notion of computability:

**Proposition**: Multiplication by 3 is not computable relative to the decimal representation.

*Proof*: Assume the input starts 0.3333333... At some point, our computation needs to start outputting something. The best choices are 0. and 1.. In the first case, we have screwed up if our input has a 4 as next digit we hadn't looked at; in the second case a 2 makes us wrong. Thus, we cannot output a guaranteed prefix of the solution.

Using a different base would yield a different notion of computability, but none of them are suitable. Some ways that all yield the same good notion of computability are:

1. Code a real $x$ as a sequence of rationals $(q\_n)\_{n \in \mathbb{N}}$ such that $|x - q\_n| \< 2^{-n}$.
2. Code a real via a signed digit representation, using $\\{-1,0,1\\}$.
3. Code a real $x$ as a sequence of rational intervals $(I\_n)\_{n \in \mathbb{N}}$ with $\bigcap\_{n \in \mathbb{N}} I\_n = \\{x\\}$

When we speak about computability of a function on the reals without specifying what kind of representation we are using, we mean one of these (or another equivalent one). This is just like we don't always point out using the Euclidean topology on the reals if we do, that is just the standard case. We can now state:

**Theorem**: The functions on the reals which are computable (wrt the standard representation) relative to some oracle are exactly the continuous functions (wrt the Euclidean topology).

Coming back to rounding, this shows that perfectly exact rounding cannot work. However, we can circumvene this by not restricting ourselves to functions. For example, the following task is computable:

*Given a real number $x \in \[0,1\]$, output either $0$ or $1$. If $x \< 0.501$, then $0$ is an acceptable solution and if $x \> 0.499$, then $1$ is an acceptable solution.*

If the input to the task above is from $\[0.499,0.501\]$, then the answer we get does not only depend on the real we are looking at, but on the particular code for that real that our algorithm reads. That can make reasoning about algorithms slightly more cumbersome, but we really can't avoid that.

---
Tags: computability, terminology
---


# Question
Title: Definition of NP-hardness for non-decision problems
As I understand, the term "NP-hardness" is applicable when we also talk about optimization or search problems (i.e. return the satisfying assignment for 3-SAT). How do we formally define NP-hardness for such problems? The standard definition:

> The problem is NP-hard when any problem from NP is polynomial-time reducible to this problem

doesn't make much sense, because of how the reduction is defined:

> Language $A$ is polynomial-time reducible to $B$ if there exists a poly-time computable function $f$, such that $x \in A$ iff $f(x) \in B$.

The problem is that $B$ (e.g. our search problem) doesn't define a language (there may be other equivalent definitions, such as $A(x) \in \\{true, false\\}$, but they'll lead to the same problems).

My friend suggested that we can define a second poly-time computable function $g^{-1}$, which converts an "answer" for $B$ to answer for $A$: $x \in A$ iff $g^{-1}(B(f(x)))$ is $true$, where $B(y)$ is any correct answer for $y$. This makes sense, but I've never seen that.

So, what's the standard definition? For an answer, I would also ask for an appropriate citation (not to Wikipedia or random slides).

# Answer
There is a slight abuse of notation going on. We say that a function $f$ is NP-hard if $f\in FP$ implies $P=NP$. For example, if $L$ is NP complete and $M\_L(x,y)$ is a verifier for $L$, then any function $f$ which maps $x$ to some $y$ such that $M\_L(x,y)$ whenever such $y$ exists is of course NP-hard in this sense. We don't usually talk about actual reductions in this context, however the natural way to go about saying $L$ reduces to computing $f$ is to say that there exists a polynomial time oracle machine $M^f$ with access to $f$ that decides $L$.

See also the zoo on the class FNP. The fact that "function NP" problems are defined relative to a specific verifier introduces some difficulty when talking about search to decision reduction.
> 4 votes

# Answer
You will not find a reference for "the standard definition" of NP-hardness. Some authors restrict the notion "NP-hard" to decision problems only, and use the definition of reduction you mention in your question (which is sometimes referred to as a "Karp reduction" or "many-one reduction"). Other authors use the term more loosely, and extend the notion to other types of problem (such as search or optimization problems). You can find a bit of historical background in Donald Knuth's "Postscript about NP-hard problems".

The wikipedia article explicitly discusses this (and gives some references):

> A decision problem H is NP-hard when for every problem L in NP, there is a polynomial-time many-one reduction from L to H. \[...\]
>
> Another definition is to require that there be a polynomial-time reduction from an NP-complete problem G to H. \[...\] Awkwardly, it does not restrict the class NP-hard to decision problems, and it also includes search problems or optimization problems.

The suggestion of your friend has some similarities with Cook reductions, which are sometimes used as the more loose definition of "NP-hardness". The suggestion of your friend captures well what people usually mean when they talk about an optimization problem being NP-hard.
> 1 votes

---
Tags: np-hard, polynomial-time-reductions, definitions
---


# Question
Title: Why do we need a separate notation for П-types?
# Main

I am confused about the motivation behind the need for a separate notation for П-types, that you can find in type systems from λ2 on. The answer usually goes like so - think about how one can represent a signature of identity function - it can be `λa:type.λx:a.x` or `λb:type.λx:b.x`. The subtle part, they say, is that these two signatures not only `not equal`, **they are not alpha-equivalent as type variables `a` and `b` are free variables inside their correspondent abstractions**. So to overcome this pesky syntactic issue, we present П binder that plays nicely with alpha-conversion.

So the question: why is that? Why not just fix the notion of alpha-equivalence?

# UPDATE z:

Oh, silly of me, `λa:type.λx:a.x` and `λb:type.λx:b.x` are alpha equivalent. But why `a:type -> a -> a` and `b:type -> b -> b` arent then.

# UPDATE suc z:

Aha, interesting, I guess this is a perfect example of selective blindness =D

I am reading the book Type Theory and Formal Proof, and in the chapter about lambda2 author motivates the existence of `П` using exactly that kind of argumentation - one cant say that `\t:*.\v:t.v` : `* -> t -> t` because this makes two alpha-equivalent terms`\t:*.\v:t.v` and `\g:*.\v:g.v` have different types, as corresponding types are not alpha-equivalent, where types like `t:* -> t -> t` are in fact alpha-invariant. **Mind the difference between `t:* -> t -> t` and `* -> t -> t`**. But, doesn't it make this argument a bit trivial, and is it even something meaningful to talk about type `a -> b` where `a` and `b` are unbound by any quantifiers variables. `Andrej Bauer` pointed out in the comments that `П` is indeed resembles a lambda abstraction with a few additional bells and whistles.

**All in all, I am done with that one, thank you guys**.

# Answer
I think we just need to get some things straight here:

1. In the expression $\lambda a : \mathsf{type} . \lambda x : a . x$ the variable $a$ **is bound** (by the outer $\lambda$). The expressions $\lambda a : \mathsf{type} . \lambda x : a . x$ and $\lambda b : \mathsf{type} . \lambda x : b . x$ *are* $\alpha$-equal.
2. The expression $\lambda a : \mathsf{type} . \lambda x : a . x$ **is** the identity function, it is *not* the "signature of the identity function".
3. If by "signature of the identity function" you mean to say "the type of the identity function", then it would be something like $\Pi\_{a : \mathsf{type}} . (a \to a)$, or if you want only product types, then it is $\Pi\_{a : \mathsf{type}} \Pi\_{x : a} a$.

Is there still a question?

Maybe this will help:

* the type of the identity function $\lambda x : a . x$ is $a \to a$
* the type of the identity function $\lambda y : b . y$ is $b \to b$
* the functions $\lambda x : a . x$ and $\lambda y : b . y$ are different
* the types $a \to a$ and $b \to b$ are different
* the type of the *polymorphic* identity function $\lambda c : \mathsf{type} . \lambda z : c . z$ is $\Pi\_{c : \mathsf{type}} . c \to c$.
* the functions $\lambda a : \mathsf{type} . \lambda x : a . x$ and $\lambda c : \mathsf{type} . \lambda z : c . z$ are $\alpha$-equal
* the types $\Pi\_{a : \mathsf{type}} . a \to a$ and $\Pi\_{c : \mathsf{type}} . c \to c$ are $\alpha$-equal.

**Supplemental:** After talking to Alex Simpson over a cup of tea, there is one more thing I can say. We don't *need* separate $\lambda$ and $\Pi$ constructors, as they both have precisely the same syntactic shape (take two arguments, bind one variable). In fact, if my memory serves me right, Automath used the same notation for $\lambda$-abstractions and $\Pi$-types. But the point is that we *want* to use two different constructors because they denote *different concepts*.
> 8 votes

---
Tags: type-theory, polymorphisms
---


# Question
Title: prove: max (w(E), w(E)) is a 1/2 approximation to the value OPT
Hey I would like to find a answer for b. for a  look to the picture that is my answer for it. But I dont habe any Idea how i can solve this. Thank you guys. (I had to translate it to english maybe it will be hard to understand it sorry about that).

# Answer
> 0 votes
I don't know the definition of $1/2$-approximation algorithm, but it looks like what you will need to do is the following argument:

For an enumeration $\sigma:V\to\\{1,2,...,n\\}$ of the vertices, let, for each input graph $G=(V,E)$, the output of the algorithm be $A\_\sigma(G)=\max(w(\overrightarrow{E}),w(\overleftarrow{E}))$.

We have that $OPT(G)\leq w(E)$.

On the other hand, $$ \begin{align} A\_\sigma(G)&=\max(w(\overrightarrow{E}),w(\overleftarrow{E}))\\ &\geq\frac{w(\overrightarrow{E})+w(\overleftarrow{E})}{2}\\ &= \frac{w(E)}{2} \end{align}$$ The last equation is because $\overrightarrow{E},\overleftarrow{E}$ is a partition of $E$.

Putting these two inequalities together we get $$OPT(G)\leq w(E)\leq 2A\_\sigma(G)$$

Therefore $$\frac{A\_\sigma(G)}{OPT(G)}\geq \frac{1}{2}$$

---
Tags: approximation
---


# Question
Title: If P=NP, does this imply that all problems are NP-hard?
A problem is said to be NP-hard if every problem in NP is reducible to that problem in polynomial time. Hence, if P=NP, wouldn't that imply that every problem in NP is reducible to every possible problem, in polynomial time? However the diagram above seems to imply that if P=NP, there exist problems outside of NP-hard.

Is there anything I am missing?

# Answer
> 1 votes
**TL;DR**: if $\sf P=NP$ then all languages *except $\emptyset$ and $\Sigma^\*$* are $\sf NP$-hard. The diagram is perhaps misleading if you consider that it has the implication that there are infinitely many problems outside the $\sf NP$-hard region (which you reasonably could, but I didn't assume that from it).

---

We assume throughout that $\sf P=NP$.

Recall that "reducible to" means that we need to map a yes-instance to a yes-instance and a no-instance to a no-instance. This rules out $\emptyset$ and $\Sigma^\*$ (the set of all strings), as they lack either a yes- and no-instance.

For all other problems $L$ in $\sf NP$, we can choose a yes-instance $y$ and a no-instance $n$. To reduce $M\in \sf NP$ to $L$, we can just compute in polynomial time whether it is a yes- or no-instance and return $y$ or $n$ accordingly. Thus, the problems in $\sf NP\setminus \\{\emptyset, \Sigma^\*\\}$ are $\sf NP$-hard.

Now let's look at the problems which are not in $\sf NP$ (or, equally, $\sf P$). Consider a $\sf EXP$-complete problem. Such a problem is not in $\sf NP(=P)$ because $\sf P\neq EXP$, so it falls outside the inner circle in the diagram. Additionally, it cannot be $\emptyset$ or $\Sigma^\*$ because both problems are in $\sf P$, so the problem has a yes-instance $y$ and a no-instance $n$ and thus we can do the same algorithm above to reduce any $\sf NP$ problem to it in polynomial time. So it meets the definition of $\sf NP$-hard.

The diagram on the right is correct that ${\sf NP\neq NP} \text{-hard}$, but there is a technicality that ${\sf P=NP}\not\subseteq{\sf NP} \text{-hard}$ because of $\emptyset$ and $\Sigma^\*$. I think the diagram illustrates this by using $\simeq$ rather than $=$ for the text "NP-complete".

I believe your issue was whether it is meant to say that ${\sf NP} \text{-hard} \neq \mathcal P(\Sigma^\*)$, the set of all languages, and indeed that is true but only on a technicality: ${\sf NP} \text{-hard} = \mathcal P(\Sigma^\*)\setminus \\{\emptyset, \Sigma^\*\\}$. As for whether the diagram implies this or not, that's a matter of interpretation.

The left diagram doesn't have this right diagram's problem because if $\sf P\neq NP$ then $\emptyset$ and $\Sigma^\*$ are in $\sf P$, not $\sf NPC$.

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


# Question
Title: Show that the single-tape TMs that can not write on the portion of the tape containing the input string recognize only regular languages
Show that the single-tape TMs that can not write on the portion the portion of the tape containing the input string recognize only regular languages.

The first part of the answer in a book said that:

We give a DFA $A$ that is equivalent to TM $M$. Design $A$ in two stages.

1. We arrange the states and transitions of $A$ to simulate $M$ on the read-only input portion of the tape.
2. We assign the accept states of $A$ to correspond to the action of $M$ on the read/write portion of the tapeto the right of the input.

Given below the whole answer (sorry for using pictures but the answer was so long and I do not understand it and I have not enough time to write it):

But I do not understand many points:

1. Why the domain and the codomain of the defined function takes this form? and why only finitely many such functions exist as stated by the last line in the first paragraph?
2. Why the author wrote $F\_{\epsilon}$ as in the third paragraph? did he used the idea of epsilon transitions?
3. The last paragraph in the solution I did not understand its idea at all?

Could anyone clarify the above questions for me please?

I saw an answer for the question here Single-tape Turing Machines with write-protected input recognize only Regular Languages but I did not understand it at all.

# Answer
The general idea is that the TM has only finite memory while being in the input part of the tape. It can do arbitrary computations in the right part of the tape, but it can only observe a finite memory footprint of the input. It starts in the input part (on the left) and it can reenter the input part (from the right) arbitrarily often. But each time it enters the input part, the only thing that matters is the state it has when entering (or the fact that it starts from the left). And the only outcome of processing the (read-only) input part is the state it has when it exits (or the fact that it does not exit because it has accepted or rejected in the meantime).

1. That is already the reason for the domain and codomain. The domain is everything that matters about entering the input part, the codomain is everything that matters about exiting that part. Hence the function completely describes the behaviour of the TM on the input part. In a sense, the function contains everything the TM will ever find out about the word $s$. Both domain and codomain are finite, hence so is the set of functions. Although the definition is about infinitely many words $s$, there will only be a finite number of *different* functions $F\_s$.
2. $F\_{\varepsilon}$ is not about $\varepsilon$-transitions. And it does not expand the previous definition. It is just the special case $s=\varepsilon$, that is the case of the empty input word. Or rather, the case of the empty prefix. After all, the paragraph where this appears is all about how $F\_s$ can be computed incrementally along with prefixes of $s$.
3. By now we have fully defined the automaton, except for acceptance. And the automaton state fully describes what the TM can do with the word we have read. We have not yet said anything about the part of the TM's computation that happens outside of the input word. The trick is that we do not have to delve into that computation. We just say that the state $F\_s$ is accepting if the word $s$ belongs to the TM's language. The paragraph has an explanation of why that is well-defined.
> 4 votes

# Answer
Actually, you don't need to construct the DFA, you just need to show that it exists using the Myhill Nerode theorem.

Here's how: given a machine $M$ that cannot write on its input, suppose the input has a prefix $s$. We can then ask the following questions:

1. If $M$ is in its start state $q\_0$ and its tape head points to the **first** symbol in $s$, does the tape head ever go past $s$, i.e. to the first slot *after* $s$? If it does, what state will it be in? If it does not (i.e. the head will always stay within $s$) does $M$ eventually accept or not?
2. If $M$ is in some state $q$ and its tape head points to the **last** symbol in $s$, does the tape head ever go past $s$? If it does, what state? If it does not, does $M$ accept?

Let $G(s)$ be the tuple of answers to the above for any string $s$. The answer to 1. is one component of the tuple, and the answers to 2. (one for each $q$) are the other components. We can make two key observations:

I. The number of possible *values* of the tuple is finite. This is because the value of each component is either a state $q^\prime$ or "accept" or "reject". Hence, the possible values is just a simple cartesian product.

II. For any two strings $s$ and $t$, if $G(t) = G(s)$, then for any suffix $z$, either $M$ accepts both $sz$ and $tz$, or $M$ accepts *neither* $sz$ nor $tz$.

Observation II. can intuitively be seen by noticing that for any $s$ and $t$, when the tape is in the portion *after* the $s$ or $t$, we *know* that there will be no differences, as long as the same $z$ is chosen as the suffix for both. Additionally, if $G(s) = G(t)$, then we know that the behavior is also identical *within* the $s$ or $t$, hence it is identical for the two everywhere in the tape.

I. and II. allow us to divide all possible $s$ into a finite number of Myhill-Nerode equivalence classes. Hence, a DFA recognizing the language of $M$ exists.
> 6 votes

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


# Question
Title: What language does this deterministic finite automaton accept?
Been mulling over this one for hours, my initial thought was { w ε {a,b}\* | w is empty, or ends with either ab or ba} but that's clearly wrong as neither aba nor bab are accepted by the automaton. If anyone has any idea what language this automaton accepts it would really put my mind at ease.

# Answer
> 3 votes
$(a^+b \mid b^+a)^\*$. I am not sure there is a "simple" description of your language in plain English, but directly from the regex you get that it is the language that has the empty string and all strings that can be partitioned in such a way that each part is either multiple $a$'s (at least one) followed by one $b$, or vice versa.

In my opinion the regex and the automaton describe the language better than a "natural language description" in this case.

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


# Question
Title: What Happens if I swap the forget gate and update gate in LSTM model?
Consider the following eqautions used in LSTM ( taken from Andrew ng's course on Sequential model)

In an LSTM model, LSTM Cell has three inputs at any time step t

* Input($X\_t , a^{(t-1)}, C^{(t-1)})$,
Here $X\_t$ is the input vector, $a^{(t-1)}$ is the previous hidden state and $ C^{(t-1)}$ is the previous cell state

Now the new cell state $c^t$ is given by the following formula :
$C^t = $ forget\_gate * $C^{(t-1)} + $ update\_gate\* $\overline{C^t}$
**Question**:
If I swap the places of forget\_gate and update\_gate, I still get a valid $C^t$, So why are we multilyting the previous cell state with forget gate only and the current cell state with update gate only, what if Imultiply previous cell state with update gate ?

Edit : After swapping, the formula would look like this,
$C^t = $ update\_gate * $C^{(t-1)} + $ forget\_gate\* $\overline{C^t}$

# Answer
The two formulas are mathematically equivalent; the only change is that you have swapped the names of the variables (changes them to names that are less intuitive, compared to what effect they have), but that doesn't affect the behavior of the system.
> 1 votes

---
Tags: neural-networks, natural-language-processing
---


# Question
Title: CSP heuristics to help avoid redundancy while checking values for constraint inconsistency?
I'm a complete beginner. Please forgive my ignorance.Trying to learn about CSP online, I noticed a lot of the focus on search methods and heuristics which tell you which variable to expand next (e.g. most constrained variable) and those that tell you which value to try first (e.g. least constraining value) but I've yet to see heuristics that relate to constraint checks. Since I'm doing everything by hand, I notice a lot of redundancy when eliminating values from variable domains. How do you go about checking for violated constraints in a way that is efficient? Say constraint A will have me eliminate odd numbers 1 to 1000 and constraint B will have me wipe out everything above 250. Intuitively, it feels like order matters as I would waste my time cherry picking even numbers above 250 to only later find out that anything above 250 was not consistent in the first place. I apologize for lacking the proper terminology, my understanding is mostly intuitive. I hope it makes sense. Thanks in advance! I'm mostly looking to acquire a conceptual understanding of selected topics in computer science so if you have book recommendations or any resource that would be appropriate for me as an interested layman, please don't hesitate!

# Answer
These are known as variable ordering heuristics. One standard one is "fail first". See the "dom" heuristic, i.e., try first the variable with the fewest number of possible values, or "dom+deg", where ties are broken by choosing the variable that participates in the smallest number of constraints. That would handle the case you list as desired.
> 1 votes

---
Tags: constraint-satisfaction
---


title: Hidden Markov Models for Hand Gestures

text:
# Question
Title: Hidden Markov Models for Hand Gestures
I am completing a final year project for hand gesture recognition using Hidden Markov Models

I have a fair understanding of Hidden Markov Models and how they work using simple examples such as the Unfair Casino and some Weather examples.

I am looking to implement multiple Hidden markov models where each model corresponds to a single gesture, similarly to this paper where the observed states are the angles between the coordinates of different points. This would create a sequence of numbers from 0 to 18 as seen in Figure 3 and Figure 4. .

What would the hidden states be in terms of this scenario?

The weather example has the observations 'Walk', 'Shop' and 'Clean' which would be the numbers 0-18 in the hand gesture case, however I do not know what the states 'Rainy' and 'Sunny' would correspond to in the hand gesture scenario.

**Edit:** I am generating a sequence of numbers that will correspond to a certain gesture using the method mentioned above. I will then use that sequence to train a HMM and will then test that HMM using another set of recorded numbers similar to the training set. Here is an example of my scenario:

Recorded data of observed states (theta) during a gesture:

```
observations = [0,1,4,15,4,3,1,0,19,18,17,16,15,15,16,3,1,1,0,18...]

```

Recorded data of test gesture:

```
test = [0,2,4,15,4,2,1,0]

```

My goal is to create a model from the first set of observations (which will be much longer as the gesture will be recorded many times) and determine the likelyhood of the test gesture to be from said model.

Will I need to generate a hidden state to create an accurate model of the gesture or can I just use unsupervised training for a model?

If i do have to use supervised training, should I create the hidden states using quadrants (i.e. 0-90 degrees = quadrant1, 90-180 degrees = quadrant2...)?

# Answer
You say that your goal is to create a model and compute the likelihood of a test sample using that model. For that purposes, you do not need to find a way to interpret the hidden states, and you do not need to engineer the model so the hidden states have a meaning that you can understand. Instead, let the standard Baum-Welch algorithm compute a reasonable model that fits the training data, and don't worry about the meaning of the hidden states.

If you had a physics model where you knew what the hidden states "should" be, based on some domain knowledge (e.g., about the movement patterns of bones and joints), then you could incorporate that into your model in hopes of improving the model... but that's not required. Since you don't seem to start from such a place, there is no need to try to force the hidden states to take on any particular human-understandable meaning.
> 0 votes

---
Tags: algorithms, machine-learning, hidden-markov-models
---


# Question
Title: what would be the time complexity of DBSCAN algorithm?
what would be the time complexity of DBSCAN algorithm if we use it for graph(sparse) clustering $O(n^2)$ or $O(n \log{n})$?

# Answer
As the graph is sparse, if you have a data structure to query in $O(\log{n})$, you can reach to $O(n \log{n})$ for your case. More details in this link:

> DBSCAN visits each point of the database, possibly multiple times (e.g., as candidates to different clusters). For practical considerations, however, the time complexity is mostly governed by the number of regionQuery invocations. DBSCAN executes exactly one such query for each point, and if an indexing structure is used that executes a neighborhood query in $O(\log n)$, an overall average runtime complexity of $O(n \log n)$ is obtained (if parameter $\varepsilon$ is chosen in a meaningful way, i.e. such that on average only $O(\log n)$ points are returned). Without the use of an accelerating index structure, or on degenerated data (e.g. all points within a distance less than $\varepsilon$), the worst case run time complexity remains $O(n^2)$. The distance matrix of size $(n^2-n)/2$ can be materialized to avoid distance recomputations, but this needs $O(n^2)$ memory, whereas a non-matrix based implementation of DBSCAN only needs $O(n)$ memory.
> 2 votes

---
Tags: graphs, time-complexity, algorithm-analysis, clustering
---


# Question
Title: Variation to spanning tree called Group Spanning Tree
Suppose we have a complete graph, with say 100 nodes. We divide the nodes in the graph into groups, for example 10 nodes in each group, identified by color. We want to obtain a minimum spanning tree under the constraint that at least one node will be present from each group ("group spanning tree").

How to write an efficient algorithm for this, making sure it is a tree (no cycles), without iterating over the entire node set, on every pass checking presence of cycles, and also making sure that at least one node from each group is represented?

# Answer
> 2 votes
A spanning tree connects *all* nodes, so in particular it connects nodes of each color.

Are you sure that is the problem you are facing?

# Answer
> 1 votes
It seems to be a group Steiner tree problem. See the answer by @Juno in connecting an unconnected forest of subtrees in a graph?

# Answer
> 0 votes
I say u find the MST for a virtual graph composed of ur groups each as one node. Meaning u omit edges inside the group and treat edges to/from the outside world as connecting to the virtual node.

Think of it as post office that receives all letters coming to/from a certain district then distribute them

---
Tags: spanning-trees
---


# Question
Title: Does a function $f$ exists such that: $f(n-k) \ne \Theta(f(n))$ for some constant $k\geq1$?
I have encountered the following question in my homework assignment in Data Structures course:

"Does a function $f$ exists such that: $f(n-k) \ne \Theta(f(n))$ for some constant $k\geq1$ ?"

I think no such function $f$ exists, but I do not know how to prove it (or give a counter-example if one exists).

# Answer
> 1 votes
An example is $f(n) = 2 ^ {2^n}$. Now, $f(n-1) = 2 ^ {2^{n-1}}$ and we have $\frac{f(n-1)}{f(n)} = \frac{1}{2^{2^n - 2^{n-1}}} = \frac{1}{2^{2^{n-1}}}$. Hence, $f(n-1) \not \in \Theta(f(n))$. In this example, $k = 1$.

# Answer
> 4 votes
Counterexample: $f(n)=n!$ As $f(n)$ is $n$ times bigger than $f(n-1)$, it is clear that $f(n-1) \neq \Theta(f(n))$.

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


# Question
Title: Description logics with decision problems within NP
Is there any description logic where important decision problems (e.g. abox consistency or concept satisfiability) lie within NP with respect to their time complexity?

The well-researched family of $\mathcal{ALC}$-based logics might not work since even for $\mathcal{ALC}$, problems are PSpace-complete. Neither would the $\mathcal{EL}$ family since the problems are at least CoNP.

Some restriction thereof might work, though, although I couldn't find any so far.

# Answer
> 1 votes
Can see here https://www.w3.org/TR/owl2-profiles/#Computational\_Properties for OWL-EL, OWL-QL and OWL-RL

# Answer
> 0 votes
Yes, but the only example I know is subsumption in FL$^-$, which actually is in P. On the other hand, subsumption in full FL is co-NP hard. A standard reference is Levesque and Brachman, *Expressiveness and tractability in knowledge representation and reasoning*. Here you can find more about FL$^-$, while these note are devoted to the computational complexity of satisfiability and subsumption in several description logics.

---
Tags: time-complexity
---


title: Do the newest computers still have ROM?

text:
# Question
Title: Do the newest computers still have ROM?
Now that many computers use UEFI instead of BIOS to boot the computer, and UEFI instructions are usually stored in a hidden hard disk partition, does this mean the newest computers do not need to have ROM, which is used to store BIOS program in the old days? Or, was ROM unnecessary long ago even before UEFI existed, as BIOS program and settings were stored in flash memory (so as to store the changes in settings by user)?

# Answer
Yes, or maybe no, depending on your definitions. Commonly some small 8-pin SPI NOR-Flash ROM is used, for example my slightly older motherboard has a W25Q64FV. This replaces the older non-flash based EEPROM technology since Flash is cheaper, but it fills the same role, and often the flash versions are still called EEPROM. Since it's Flash memory, you could call that "not ROM", if your definition of ROM excludes Flash.

An other problem with relying on a disk is that *a disk cannot come pre-programmed correctly*. It needs to contain code specific for the motherboard, and be pre-loaded with microcode for the various diffent CPU models supported by that motherboard (which is why recently AMD motherboard manufacturers had some trouble). A disk does not know which motherboard it ends up in, so it cannot fill this role.
> 4 votes

# Answer
Reason it out:

a) Disk-access is way too complicated a process to hard-wire into the CPU. Not to mention that disks from different manufacturers will have different procedures for disk-access, so there is no point in hard-wiring it in advance anyway (*what happens to your CPU chip sailes if the disk manufacturer goes out of business?*).

b) Therefore the machine must run a program to access the UEFI instructions, and indeed must run a program to perform any disk-access - including the very first access.

c) The program run which performs the very first disk-access obviously cannot itself have been read from the disk.

Conclusion: Yes, machines still need ROM.
> 2 votes

# Answer
Consider a very common modern computer, an iPhone. The ROM needs to be capable of downloading at least the first parts of the operating system and perform cryptographical checks that the downloaded code is genuine and not forged, and then write it to permanent memory in encrypted form. That thakes quite a bit of code.
> 0 votes

---
Tags: computer-architecture
---


# Question
Title: Why is NFA minimization a hard problem when DFA minimization is not?
I know that we can minimize DFAs by finding and merging equivalent states, but why can't we do the same with NFAs? I'm not looking for a proof or anything like that--unless a proof is simpler to understand. I just want to understand intuitively why NFA minimization is so hard when DFA minimization is not.

# Answer
For DFA there is a nice algebraic structure that determines which states can be equivalent, the Myhill-Nerode equivalence on strings is related to minimization of DFA.

For NFA the situation is complicated as there is no *unique* minimal NFA in general.

Here is an example for the finite language $\\{ ab, ac, bc, ba, ca, cb\\}$. The two automata are both state-minimal. The example is from the paper *A note about minimal non-deterministic automata* by Arnold, Dicky and Nivat.

This answer tries to express the fact that the two problems are "technically" different. See the answer by vzn for details how the problems differ in computational complexity.
> 11 votes

# Answer
You asked about an intuitive take.

In a DFA, any given input prefix can only reach at most one state. One can then merge together pairs of states that are indistinguishable for any suffix. States that can be distinguished by some suffix cannot be merged. This leads to a minimal automaton that is isomorphic to all other minimal automata.

In contrast, if the automaton is nondeterministic then merging suffix-indistinguishable single states is not good enough. For a given input, not all sequences of transitions in an NFA have to result in an accepting state: if just one such sequence exists, that is enough for the NFA to accept. To correctly decide if two states can be merged, one may need to keep track of more information than for a DFA. For instance, suppose there is a word $pq$ in the language, with prefix $p$ that results in some state $P$, yet so that from $P$ there is no accepting state for the suffix $q$. It is possible that there is another state $Q$ that is indistinguishable from $P$ by any suffix other than $q$. In this case one would want to merge $P$ and $Q$. So one needs to extend the notion of when states are indistinguishable, to take into account such "phantom" differences. This essentially requires keeping track of all possible *subsets of states*.

Going from tracking $n$ states to $2^n$ subsets of states makes dealing with NFA minimization harder in the worst case.
> 7 votes

# Answer
the question does not define "hard" whereas there is a technical sense of the word in TCS. in one sense neither is "hard" (either minimizing DFAs or NFAs) because many algorithms exist for both. however, another angle on this. DFA minimization has runtime $O(ns \log n)$ where s is the number of states ie PTime. NFA minimization has been proven PSpace complete. NFA minimization is not in PTime unless P = PSpace which is widely believed not to be true.

see also this TCS.se question computing the minimal NFA for a DFA
> 2 votes

# Answer
This paper claims to provide minimized NFA in linear time: https://www.tandfonline.com/doi/abs/10.1080/03057920412331272153
> -2 votes

---
Tags: complexity-theory, finite-automata, nondeterminism
---


# Question
Title: Could someone break down this grouping problem for me?
I am trying to work through this programming problem but I can't progress because I genuinely don't understand what it is that its asking me.

> New Students are arriving at college. Initially the students don't know each other, and each has a circle of friends limited to themselves. As the semester progresses, groups of friends form.
>
> As they arrive, each students gets an ID number, 1 to n. You will be given three arrays, each aligned by index. The first array will contain a `queryType` which will be either `Friend` or `Total`. The next two arrays, `students1` and `students2`, will each contain a Student ID.
>
> If the query type is `Friends` the two students become friends. If the query type is `Total`, you must report the sum of the sizes of the groups of friends for the two students. For example, if you have `n=4`students numbered 1-4 and you receive the following queries:
>
> ```
> Friend 1 2   Friend 2 3   Total  1 4
>
> ```
>
> Students will start as discrete group {1}, {2}, {3} and {4}. Students 1 and 2 become friends as do 2 and 3. The new groups are {1,2}, {2,3} and {4} which simplifies to {1,2,3} and {4}. We then total the number of friends for student 1 = 3 and student 4 = 1 for a total =4. Notice that student 3 is part of student1's circle of friends indirectly through student 2.
>
> Functional Description Complete the function `getTheGroups` in the editor below. The function must return an array of integers where the value at each index $j$ denotes the answer for the $j$th query of type Total. `getTheGroups` has the following parameter(s):
>
> ```
> n: the number of students, integer
> queryType [queryType[1],...queryTpe[q]]: an array of query type strings
> student1 [student1[1],...student1[q]]: an array of student integer ID's
> student2 [student2[1],...student2[q]]: an array of student integer ID's
>
> ```
>
> Constraints
>
> ```
> 1 <= n <= 10 pow 5
> 1 <= q <= 10 pow 5
> 1 <= students1[i] <= n
> 1 <= students2[i] <= n
> queryType[i] is a member of {Friend, Total}
>
> ```
>
> Input Format. Input from stdin will be processed as follows and passed to the function.
>
> ```
> The first line contains an integer n, the number of students.
> The next line contains an integer q, the number of queries.
> Each of the next q lines contains a string queryType[i] where 1 <= i <= q.
> The next line contains an integer q, the number of students.
> Each of the next q lines contains a string students1[i] where 1 <= i <= q.
> The next line contains an integer q, the number of students.
> Each of the next q lines contains a string students2[i] where 1 <= i <= q.
>
> ```
>
> Sample Input
>
> ```
>   3            - the number of students
>   2            - the number of queries
>   Friend       - queryType[1]
>   Total        - queryType[2]
>   2            - the number of queries
>   1            - student1[1]
>   2            - student1[2]
>   2            - then number of queries
>   2            - student2[1]
>   3            - student2[2]
>
> ```
>
> Sample Output
>
> ```
>  3
>
> ```

What I got from the problem was to take the sum of the size of all groups of friends? So if student1, student2 are friends and student2, student3 are friends, then the sum would be 4?
I apologize for the rookie question. I genuinely couldn't make sense of the description.

# Answer
> 0 votes
Read this sentence from the description carefully:

> If the query type is Friends the two students become friends. If the query type is Total, you must report the sum of the sizes of the groups of friends for the two students.

So your program must maintain a state between queries. The queries are read off sequentially by taking all of the first indices of the 3 arrays for the first query, then all the second indices of the 3 arrays for the second query, etc. The Friends query modifies the state, while the Total query accesses the state and returns "size of group containing student 1 + size of group containing student 2".

---
Tags: algorithms, group-theory
---


# Question
Title: Solving unusual recurrence with two variables
I have the following recurrence relation:

$$T(n,k) = T(n-1,k)+T(n-1,k+1)$$

With the following base cases (for some given constant $C$):

For all $x \leq C$ and for any $k$: $T(x,k)=1$

For all $y \geq C$ and for any $n$: $T(n,y)=1$

I want to get a formula for $T(n,0)$. I think that it can be seen that after $i$ iterations we get the following relation:

$T(n,0) = \sum\_{j=0}^i {n\choose{j}}\cdot T(n-i,j)$

But I don't know if it helps and can't proceed much further than that.

My question is $-$ what are the right techniques for dealing with recurrence with 2 variables, and in particular with this recurrence (where the second variable is increasing)?

# Answer
> 2 votes
In the cases $C\leq0$ and $C\geq n$ you have $T(n,0)=1$.

Assume that $0\<C\<n$. Show that $$T(n,0)=\sum\_{i=0}^{\color{red}{k}}\binom{\color{red}{k}}{i}T(n-\color{red}{k},i)$$ for $0\leq k\leq n-C$ and $n\leq 2C$. It looks like this is the formula that you mentioned in the question, except that the binomial coefficient should have the same amount that is being subtracted from the first entry of $T$.

Apply it for $k=n-C$.

We get $$T(n,0)=\sum\_{i=0}^{n-C}\binom{n-C}{i}T(C,i)=\sum\_{i=0}^{n-C}\binom{n-C}{i}=2^{n-C}$$

If $n\>2C$ the formula that we get is

$$T(n,0)=\sum\_{i=0}^{\color{red}{C}}\binom{\color{red}{k}}{i}T(n-\color{red}{k},i)$$

Putting $k=n-C$ we get

$$T(n,0)=\sum\_{i=0}^{C}\binom{n-C}{i}T(C,i)=\sum\_{i=0}^{C}\binom{n-C}{i}\in O(n^C)$$

since it is a polynomial of degree $C$.

---

We didn't need it this time, but a technique that could be useful to work with recurrences is generating functions.

# Answer
> 0 votes
You know T(n, C) for all n. I’d try to determine T(n, C-1) for all n, then T(n, C-2) and so on.

---
Tags: asymptotics, recurrence-relation, big-o-notation
---


# Question
Title: Bubble Sort: Runtime complexity analysis line by line
I'm trying to analyze Bubble Sort runtime in a method similar to how to it's done in "Introduction to Algorithms 3rd Ed" (Cormen, Leiserson, Rivest, Stein) for Insertion Sort (shown below). I haven't found a line by line analysis like the Intro to Algorithms line by line analysis of this algorithm online, but only multiplied summations of the outer and inner loops.

For each line of bubblesort(A), I have created the following times run. Appreciate any guidance if this analysis is correct or incorrect. If incorrect, how it should be analyzed. Also, I do not see the best case where $T(n) = n$ as it appears the inner loop always runs completely. Maybe this is for "optimized bubble" sort, which is not shown here?

Times for each line with constant run time $c\_n$, where $n$ is the line number:

Line 1: $c\_1 n$

Line 2: $c\_2 \sum\_{j=2}^n j $

Line 3: $c\_3 \sum\_{j=2}^n j - 1$

Line 4: $c\_4 \sum\_{j=2}^n j - 1$ Worst Case

$T(n) = c\_1 n + c\_2 (n(n+1)/2 - 1) + c\_3 (n(n-1)/2) + c\_4 (n(n-1)/2)$

$T(n) = c\_1 n + c\_2 (n^2/2) + c\_2 (n/2) - c2 + c\_3 (n^2/2) - c\_3 (n/2) + c\_4 (n^2/2) - c\_4 (n/2)$

$T(n) = (c\_2/2+c\_3/2+c\_4/2) n^2 + (c\_1 + c\_2/2+c\_3/2+c\_4/2) n - c\_2 $

$T(n) = an^2 + bn - c$

# Answer
The runtime in the original post is correct. The O(n) runtime is for a different algorithm, called optimized bubble sort.
> 0 votes

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


# Question
Title: What is the difference between Big O, Omega, and Theta?
I know that this question is asked a lot of time but I don't understand or I think, I got lost when I was reading Introduction to algorithms

They said, "It is not contradictory, however, to say that the worst-case running time of insertion sort is Omega(n^2), since there exists an input that causes the algorithm to take Omega(n^2) time.".

I read many articles that Omega is the best-case. As I understand correct me if I'm wrong, that the best-case is Omega notation and why they said, "since there exists an input that causes the algorithm to take Omega(n^2) time.", I don't understand why they called it worst-case and why I can call it Omega(n^2), isn't Big O for worst-case.

Also I don't understand they said, "Theta is notation is a stronger notion than Big O". Why is that? and When should I call an algorithm that it's Big O of whatever, Theta or Omega?

Because I'm confused and I don't know which one is for or how to use them.

# Answer
Check the definitions, e.g. in Hildebrand's Introduction to asymptotics. In a nutshell, for the usual computer science use for running times (all relevant functions positive), it is said that:

* $f(n) = O(g(n))$ if there are $n\_0$ and $c \> 0$ so that for all $n \ge n\_0$ it is $f(n) \le c g(n)$
* $f(n) = \Omega(g(n))$ if there are $n\_0$ and $c \> 0$ so that for all $n \ge n\_0$ it is $f(n) \ge c g(n)$
* $f(n) = \Theta(g(n))$ if both $f(n) = O(g(n))$ and $f(n) = \Theta(g(n))$.

Note that the last implies two possibly different $n\_0$ values, and different values for $c$ (one each for $O$ and $\Omega$).

Informally, $O(\cdot)$ gives an upper bound, $\Omega(\cdot)$ gives a lower bound, while $\Theta(\cdot)$ gives a sharp bound.

Some examples:

$\begin{align\*} n &= O(2^n) \\ (3/2)^n &= \Omega(n^3) \\ n^2 (\sin n + \cos n) &= \Theta(n^2) \end{align\*}$}

There are functions that don't have a simple expression, like:

$\begin{align\*} f(n) &= \begin{cases} n^2 & n \text{ odd} \\ n^5 & n \text{ even} \end{cases} \end{align\*}$

Here clearly $f(n) = \Omega(n^2)$ and $f(n) = O(n^5)$, both best possible among functions $n^\alpha$; there is no simple $g$ so that $f(n) = \Theta(g(n))$.

Lower and upper bounds don't need to be "best possible" in any sense. Often people take great care to get best bounds, but they aren't implied in the notation at all.

To use $\Omega$ to mean best case and $O$ for worst case is misleading at best. For example, the best case for bubblesort on an array of $n$ elements is $\Theta(n)$ (bounded below and above by a linear function in the number of elements; when sorting an already sorted array it does one pass over the data), it's worst case is $\Theta(n^2)$ (if the data are in reverse order). We could say it is $\Omega(n^{1/2})$ and $O(n^3)$ as well, both valid for best *and* worst cases.
> 2 votes

---
Tags: complexity-theory, algorithm-analysis
---


title: What is the complexity of $i^i$?

text:
# Question
Title: What is the complexity of $i^i$?
What is the complexity of the following algorithm in Big O:

```
for(int i = 2; i < n; i = i^i)
{
    ...do somthing
}

```

I'm not sure if there is a valid operator to this type of complexity. My initial thought was as follows:

After $k$ iterations we want: (using tetration?)

${^{k}i} = n \implies k=\log\log\log...\_k\log{n}\implies\mathcal{O(\log\log\log...\_k\log{n})}$ (where we have k times the log function) but i'm not sure if this is evan a valid way of writing this. Anyway, we have a complexity that that includes $k$, which does not seems right to me.

# Answer
> 2 votes
This sequence is OEIS A173566. To understand how large it grows:

$a\_n = 2^{2^{b\_{n-1}}}$

where:

$b\_0 = 0$

$b\_n = b\_{n-1} + 2^{b\_{n-1}}$

The sequence $b\_i$ grows faster than $2^{\cdotp^{\cdotp^{2^0}}}$, where there are $i$ 2's in the tower.

EXPTIME is $O(2^n)$, 2-EXPTIME is $O(2^{2^n})$, and in general, you can define n-EXPTIME . The sequence $b\_i$ is not in n-EXPTIME for any natural n. So it, and therefore $a\_i$, is not in the complexity class ELEMENTARY.

The definition above shows that $a\_i$ is primitive recursive, which is interesting, because that means it doesn't grow as fast as the Ackermann function.

I think (but don't really have the time to formally prove or disprove right now) that means it's $\mathcal{E}^4$ in the Grzegorczyk hierarchy. Left as an exercise.

# Answer
> 0 votes
There is no closed form. The number of loop iterations is 0 if n \<= 2, 1 if n \<= 4, 2 if n \<= 256, 3 if n \<= $2^{264}$, 4 if n is less than some number with more than $2^{264}$ digits, so the universe isn’t large enough to write that number down.

The real problem is not the number of iterations, but how long it takes to calculate the last i, which is obviously larger than $n^n$.

# Answer
> 0 votes
You can compute the number of rounds by a recursive formula. Find an $i$ such that $i^i = n$. But we know that $i = 2^k$. Hence, we should find a $k$ such that $n =(2^k)^{2^k}$. Hence, $\log{n} = 2^k \log{2^k} = k \times 2^k$. Now, if we suppose $n = 2^m$, $m = k\times 2^k = i \log{i}$ and $n = 2^{i \log{i}}$. Hence, if we suppose $T(n)$ is the complexity of the method, $T(n) \leq T(\log(n)) + 1$, as $\log(n) = i \log{i}$ and it means $i \leq \log{n}$. On the other hand, we know that $\log^\*(n) = \log^\*(\log n) + 1$. Therefore, we can conclude that $T(n) = O(\log^\*n)$.

---
Tags: time-complexity, big-o-notation
---


# Question
Title: How can I mathematically show the largest possible value of a 64-bit double?
I'm a physics student wondering how I can mathematically show the largest possible value of a 64-bit double. I don't want to know just the answer, since that is freely available. The equation I was shown by a professor says a machine number is represented as $s\times m \times 2^{E-e}$ with $m$ the mantissa and $e$ the bias of the exponent, but I'm not sure how to use this to show the largest possible 64-bit double. The mantissa is 52 bits long and the largest exponent is 2047. The bias is 1023. The largest exponent is reserved for infinity. The leading 1 is not stored.

# Answer
> 1 votes
Assuming IEEE754 64 bit format:

You have an 11 bit exponent field, a 1 bit sign field, and a 52 bit mantissa field.

The exponent field can have values from 0 to 2047. An exponent field of 0 is reserved for denormalized numbers, and an exponent field of 2047 is reserved for infinity and Not-a-number. You could say that +Infinity is the largest value, but I assume you are looking for the largest finite value. The largest exponent field for a finite value is 2046.

This format has an "exponent bias" of 1023, that is the numbers 1.0 ≤ x \< 2.0 have an exponent field of 1023. So the largest value has an unbiased exponent of 2046 - 1023 = 1023, and numbers with an exponent field of 2046 are in the range $2^{1023} ≤ x \< 2 \cdot 2^{1023}$.

The mantissa field is 52 bit, with an implicit leading 1 bit. So a mantissa field with a value m, 0 ≤ m ≤ $2^{52}$, means the actual mantissa is 1 + $m \cdot 2^{-52}$. The largest possible mantissa field is all bits 1 or $2^{52}-1$, this makes the largest possible mantissa $2-2^{-52}$.

Multiply with the exponent, and the largest possible number is $2^{1023} \cdot (2-2^{-52})$ or $2^{1024} \cdot (1-2^{-53})$ or $2^{1024} - 2^{971}$

---
Tags: computer-architecture
---


# Question
Title: Proof that L^2 is regular => L is regular
I'm trying to show $L^2 \in \mathsf{REG} \implies L \in \mathsf{REG}$ with $L^2 = \\{w = w\_1w\_2 \mid w\_1, w\_2 \in L\\}$ but I cant seem to find a proof that feels right.

I first tryed to show $L \in \mathsf{REG} \implies L^2 \in \mathsf{REG}$, by constructing an machine $M$ that consists of two machines $A=A'$ with $A$ recognizing $L$. $M$ has the same start states as $A$ but the final states of $A$ are put together with the starting states of $A'$. Further $M$ uses the same accepting states as $A'$. Hope that makes sens so far :D

Now to show $L^2 \in \mathsf{REG} \implies L \in \mathsf{REG}$ I'd argue the same way, but:

The machine $M'$ that accepts $L^2$ has to recognize $w\_i \in L$ in some way, and because $L^2$ is regular, $M'$ has to be a NFA/DFA. So the machine has to check if $w\_i \in L$ and this cant be done by using something else than a NFA/DFA.

This feels wrong and not very mathematical, so maybe somebody knows how to do this?

# Answer
Your claim is false. Indeed, it is equivalent to prove that if a language $L$ is not regular, then also $L^2$ is not regular, but this is not true. Here Yuval Filmus gives (possibly) two examples of a non regular language whose "square" is regular, namely $L = \\{ 1^p \mid p \text{ is an odd prime}\\}$, under the Goldbach conjecture, and $L' = \\{ 1^{a^2} \mid a \geq 0 \\}^2=\\{1^n \mid n \text{ is the sum of two squares}\\}$.

---

For a simpler example, consider the set

$$\text{NP}=\\{1^n\mid n \text{ is not prime}\\}$$

Clearly NP is not regular (otherwise also its complementary would be regular), but NP$^2$ is regular, as its complementary is finite. Indeed, if $n$ is even and greater than or equal to 8, then $n=4+(n-4)$ and $4$ and $n-4$ are not prime and so $1^n\in \text{NP}^2$. Instead, if $n$ is odd and greater than or equal to 13, then $n=9+(n-9)$ and $9$ and $n-9$ are not prime, as $n-9$ is even and greater than 2, and again $1^n\in \text{NP}^2$ (actually, NP$^2=\\{1^n\mid n\neq 3\\}$, here I don't consider 1 as a prime number).

---

In general, if $L$ is a non regular language sufficiently "sparse", then there is a good chance that $(L^C)(L^C)$ is cofinite, and then regular. For example, again on a unary alphabet, one can consider the non regular language

$$\text{L}=\\{1^n\mid n \text{ is not a power of }2\\},$$

then it is easy to see that $L^2=\\{1^n\mid n\not\in\\{1,2 \\}\\}$, which is regular.

On a two letter alphabet one can consider the example below of Bernardo Subercaseaux (I think there's a little misunderstanding in his comment, as here we are considering the concatenation of a non regular language with itself), namely the language $L$ that is the complement of the language of well parenthesized strings on the alphabet $\\{(,)\\}$: in this case $L^2=\\{(,)\\}^\*\setminus\\{\varepsilon,(,)\\}$, again regular.

Another simple example is given by the non regular language

$$\text{L}=\\{w\in\\{a,b\\}^\*\mid w \text{ is not of the form }a^nb^n\text{ with }n\>0\\},$$

then it is easy to see that $L^2=\\{a,b\\}^\*$: indeed if $w\in L$, then $w=w\varepsilon\in L^2$, else if $w=a^nb^n$ then $w=a\cdot a^{n-1}b^n\in L^2$.
> 5 votes

# Answer
Here is a simple example. Take any non-regular language $N$ contained in $(aa)^+$ and consider the language $L = 1 + a(aa)^\* + N$. Then $L$ is not regular since $L \cap (aa)^+ = N$ is not regular. On the other hand, $L^2 = a^\*$ is regular.
> 4 votes

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


# Question
Title: How to prove $\{a^nb^na^n \mid n\geq1\}$ is not regular using pumping Lemma
Here the problem is that I’m confused how to take the pumping value $p$ is it arbitrary any value?

Also I don’t know if I should prove all $3$ conditions of the pumping lemma is false or if any one should be proved as false by considering the given language as regular by proof by contradiction.

# Answer
> 0 votes
Let's recall the Pumping Lemma statement:

> *For all regular language $ L $, exists a positive constant called $ p $ (i.e. $ p \geq 1 $) such that every string $ w $ in $ L $ with length $ |w| \geq p $ exist strings $ x, y, z $ such that $ w = xyz $ and that statisfying the following conditions:*
>
> * $ |y| \geq 1 $
> * $ |xy| \leq p $
> * $ xy^iz \in L, \\: \forall i \geq 0 $

So yes, $ p $ is an arbitrary value and a fixed costant, called "pumping length". The proof for your language may be the following:

Let's assume that $ L $ is a regular language, so for all strings $ w \in L $ it must satisfy conditions of PL. Now choose a string $ w $ that is in $ L $, let choose $ w = a^pb^pa^p $ and we can split $ w $ in $ xyz $, so let's say that:

* $ x = a^k $
* $ y = a^h $
* $ z = a^{p-h-k}b^pa^p $

with $ h \geq 1 $ and $ h + k \leq p $.

Now note that the first two conditions of the PL are satisfied, but for the third, if we take $ i = 0 $ then $ w = xy^0z = a^ka^{p-h-k}b^pa^p = a^{p-h}b^pa^p $ and this string clearly doesn't belongs to $ L $ and this contraddict the initial assumption of $ L $ regular, so this meanings that $ L $ isn't a regular language because it doesn't satisfy the PL.

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


# Question
Title: Computer Security versions of the Halting Problem
I'm plenty familiar with the Halting Problem for Turing Machines. It occurred to me after reading several posts on this site that it would be interesting, educational and useful to start a list of equivalents to the Halting Problem in terms of Computer Security. I think this might help students of computer science and allied areas come to appreciate the true depth and application of the Halting Problem in whatever their application area.

So, I ask that the proposed (or actual) equivalent problem be:

(1) One that makes sense in the domain of computer security. This can be from information management, Cryptography, hacking, or programming (ideally with a security bent, since there are plenty of Halting equivalent problems already well known in the world of programming languages and compilers).

(2) One stated with a reference to literature on that subject if possible, and maybe even (although I wouldn't require it) a proof if you know of an elegant one.

Example: I have an antivirus software on my machine, and I want to know whether it will ever execute malicious code. As far as I can tell, this is the Halting problem in disguise.

# Answer
What you're looking for is Rice's Theorem, which is a generalized version of Halting Undecidability.

It basically says that any property of a Turing Machine (i.e. any computer program) is undecidable, if it's a property of the *behavior* of the program (i.e. a property of the language it accepts/produces), as opposed to a particular syntactic feature of the implementation. This holds unless it's a trivial property (always true or always false).

For example, deciding "Does instruction X ever get executed" or "Is a high security value stored in low security memory" are all questions about program behavior.

But things like "does this program contain a for-loop" or "is this program type-correct" aren't behaviors, because there might be equivalent programs which don't have the same values for those properties. You can phrase a program with a for-loop as using while-loops without changing the behaviour, or you can make a version of a program which behaves correctly but doesn't check under your typing discipline. So these aren't properties of the behavior, they're properties of the particular implementation.
> 5 votes

# Answer
Specifically related to **security**, we can cite the problem when system administrators assess the impact of an access control policy on his system's security. In the paper "*Protection in operating systems*" Harrison, Ruzzo, and Ullman \[1\] presented a formal model of "access control". A state in this system is denoted by a set of objects, some of which are subjects, and a protection matrix giving the current access rights between pairs of subjects and objects. The safety problem defined was: "Given a set of policy rules, a generic access right X and an initial matrix, is it possible to reach a state in which X is granted to any subject". This problem is undecidable, the safety problem **is reducible to the halting problem** for Turing machines.

\[1\] *Harrison, M., W. Ruzzo and J. Ullman, Protection in operating systems, Communications of the ACM(1976).*
> 2 votes

---
Tags: computability, reference-request, halting-problem, security
---


title: Peterson's vs. Bakery Algorithm

text:
# Question
Title: Peterson's vs. Bakery Algorithm
From my CS course, the Peterson's Algorithm and the Bakery Algorithm both are solutions which satisfy the 3 requirements of any solution to the critical section problem. a) What are their adv/disadv over each other , and b) if they already solve the critical section problem, why do we need semaphores?

# Answer
> 2 votes
> a) what are the advantages/disadvantages over each other?

According to the lecture note: Sections 17.4.1 and 17.4.3, we can summarize as follows:

1. The *original* Peterson’s Algorithm works with only 2 processes.
2. The Peterson's algorithm requires multi-writer registers while the Bakery algorithm uses only single-writer registers.
3. Both algorithms are starvation-free. Furthermore, the Bakery algorithm offers a strong near-FIFO guarantee.
4. Both algorithms work with atomic registers. However, the Bakery algorithm works with even weaker registers (*safe* registers actually, see here).
5. The Bakery algorithm uses unbounded registers. Nevertheless, this problem can be fixed.

> b) If they already solve the critical section problem, why do we need semaphores?

A Semaphore is a generalization of mutual exclusion locks. Each Semaphore has a capacity, denoted by $c$ for brevity. Instead of allowing only one thread at a time into the critical section, a Semaphore allows at most $c$ threads, where the capacity $c$ is determined when the semaphore is initialized. (See the book "The Art of Multiprocessor Programming" by Maurice Herlihy and Nir Shavit; Section 8.5).

# Answer
> 0 votes
They don't work for multiprocessors and modifying them to solve them is a hassle.

Whereas semaphores are simply mathematical methods to create process precedence graphs for concurrent execution.

Just an integer variable, that's it.

---
Tags: process-scheduling, synchronization
---


# Question
Title: Stratification of Bisimilarity : $\sim$ does not coincide with $\sim_\omega$
I am reading Sangiorgi's paper *On the origins of bisimulation an coinduction*.

Definition 2.5, on page 5, defines *Stratification of Bisimilarity*:

> Let $W$ be the states of an LTS. We set:
>
> * $\sim\_0 \overset{\text{def}}{=} W\times W$
> * $s\sim\_{n+1} t$, for $n\geq 0$, if:
>
> (1) for all $s^\prime$ with $s \overset{\mu}{\rightarrow} s^\prime$, there is $t^\prime$ such that $t \overset{\mu}{\rightarrow} t^\prime$ and $s^\prime\sim\_n t^\prime$;
>
> (2) the converse, that is, whenever for all $t^\prime$ with $t \overset{\mu}{\rightarrow} t^\prime$, there is $s^\prime$ such that $s\overset{\mu}{\rightarrow}s^\prime$ and $s^\prime\sim\_n t^\prime$.
> * $\sim\_\omega \overset{\text{def}}{=} \bigcap\_{n\geq 0}\sim\_n$

The paper follows with the remark that, in general, $\sim\_\omega$ does not coincide with $\sim$ (the usual bisimilarity), and provides the following example (Example 2.6 in the paper) to highlight that:

We take the LTS with $\\{a\\}$ as the set of (arrow) labels, and the set of states is $\\{a^0, a^1, \dots, a^\omega, s, t\\}$, and the transition function $\overset{a}{\rightarrow}$ is the least function such that:

* $a^\omega\overset{a}{\rightarrow}a^\omega$
* $\forall n\geq 1, a^n\overset{a}{\rightarrow} a^{n-1}$
* $\forall n\in\mathbb{N}, s\overset{a}{\rightarrow} a^{n}$
* $\forall n\in\mathbb{N}, t\overset{a}{\rightarrow} a^{n}$
* $t\overset{a}{\rightarrow} a^{\omega}$

which is represented in this picture:

The example then states:

> It is easy to prove, by induction on $n$, that, for all $n$, $s\sim\_n t$, hence also $s\sim\_\omega t$.

However, I do not understand how that holds, even for $\sim\_1$: $s\sim\_1 t$ if (from item (2)): whenever for all $t^\prime$ with $t \overset{\mu}{\rightarrow} t^\prime$, there is $s^\prime$ such that $s\overset{\mu}{\rightarrow}s^\prime$ and $s^\prime\sim\_0 t^\prime$. Let's take $a^\omega$ as $t^\prime$, we indeed have $t\overset{a}{\rightarrow} a^\omega$. So, we have to find $s^\prime$ such that $s\overset{a}{\rightarrow} s^\prime$ and $s^\prime \sim\_0 a^\omega$.

Hence my question : which state is suitable for such $s^\prime$, since $s\not\overset{a}{\rightarrow} a^\omega$ ?

# Answer
> 0 votes
I found the answer of my question when writting it, which once again prove the effectiveness of writting down properly the question we have.

---

To show that $s \sim\_1 t$, to map $a^\omega$, one can take any $a^i$ we want (e.g. $a^0$): by definition, $\sim\_0 \overset{\text{def}}{=} W\times W$, and therefore we indeed have that $s\overset{a}{\rightarrow} a^0$ and $a^0\sim\_0 a^\omega$.

Something to notice is that, for each $n$, we have $a^\omega \sim\_n a^m$ for $m\geq n$. Therefore, to show that $s\sim\_{n+1} t$, to show item (2), one can simply take $a^n$ as $s^\prime$ when we take $a^\omega$ as $t^\prime$. The rest of the proof is trivial.

---
Tags: process-algebras, transition-systems
---


# Question
Title: What is the difference between a simulator, emulator, and cross compiler?
As far as I understand, cross compilers, emulators, and simulators are all ways that one computer system to be able to behave like or run another computer system.

What is the difference between these concepts? Are some of them equivalent?

# Answer
Cross-development environment involve

* a *host* computer (such as a PC) that runs the development tools,
* a *target* computer (such as an embedded processor) that is where the code will eventually run.

A cross-compiler\* generates the code that the target can understand, though compilation takes place on the host. The compiled code is sent to the target for execution.

An emulator is an ad-hoc piece of hardware that is able to mimic the behavior of the target, but is better suited for evaluation and testing.

A simulator is a software running on the host and able to mimic the behavior of the target without a physical target being present. Even though it runs on the host, it is able to execute the cross-compiled code.

A typical development scheme goes as follows:

* cross-compile and debug with a simulator to obtain the correct functional behavior,
* then cross-compile and debug with an emulator to check real-time performance and possibly interaction with real peripherals,
* finalize the product on the real target.

---

\*A compiler that compiles for the platform it runs on is called *native*.
> 2 votes

---
Tags: compilers, simulation
---


# Question
Title: How to prove that there is no better algorithm
```
Input: Set of machines M, Each machine has an availability array D_m[t],
set of activities A, for each activity j its starting time s_j,
its duration p_j and its consumption in D during processing.

Output: True or False if the usage for  each machine at each instant is less than the availability

for each machine m in M

  usage := array[0..L] of zeros

  for each activity j in A
    usage[s_j] += c_{j,k}
    usage[s_j + p_j] -= c_{j,k}

  for each time t in [1, L]
    if usage == 0
       usage[t] += usage[t-1]

  for each time t in [0, L-1]
    if usage[t] > D_m[t]
      return false

return true

```

The complexity is $O(|M| * (L + |A|))$. But $L$ is not an input length, it's a numerical value. I guess it's pseudo-polynnomial (Am I right ?)

How to prove that there is no better alternative, In other words that its also $\Omega(|M| * (L + |A|))$

# Answer
> 1 votes
I presume that $L$ is the length of $D\_m$ for all machines. Hence your input is of size $O(|M|\cdot (L+|A|))$ because it contains $|A|$ activities for all machines and the $D\_m$ array of length $L$ for all machines. Your runtime is $O(|M|\cdot (L+|A|))$. Thus your algorithm runs in linear time with respect to your input (meaning your algo is not pseudo-polynomial it is in fact polynonmial and even linear).

If a value in $D\_m$ could be below $0$ we would have to check every value in $D\_m$ for every machine at least once and for every activity that $D\_m$ is large enough making the minimum runtime $\Omega (|M|L + |M||A|) = \Omega (|M|(L+|A|))$ and thus your algo optimal.

---
Tags: complexity-theory
---


title: Automated reasoning with real numbers

text:
# Question
Title: Automated reasoning with real numbers
I have a large number of equivalences which look like:

$(a \leq 0.54 \wedge b \geq 0.12) \vee (c \gt 0.98)$ $\Leftrightarrow$ $(x \leq 0.25) \vee (x \gt 0.91 \wedge y \geq 0.01)$

This is just an example. In general, formulae on either left or right side of the equivalence could be anything that takes the form of a disjunctive normal form (DNF) clause, the numbers could be any real numbers with a fixed precision, and the inequality signs could be $\leq$, $\lt$, $\geq$, or $\gt$.

What is important is that the possible variables on the left side of all the formulae (here $\\{a, b, c\\}$) form a set that is distinct from the possible variables on the right side of all the formulae (here $\\{x, y, z\\}$). There could be any fixed number of variables on either side: doesn't need to be 3 variables, and doesn't need to be an equal number on either side.

I also have some implications of the form:

$(a \leq 0.32 \wedge b \geq 0.62)$ $\Rightarrow$ $(c \gt 0.00)$

Here both left and right sides are just conjunctions of inequalities, but what is important is that the set of variables on *both* left and right sides, i.e. $\\{a, b, c\\}$ here, is the same as the set of variables on *only* the left side of the previous kind of the formula (i.e. the equivalences).

My question is: what kind of automated reasoner would I need to find the logical consequences of a set of such formulae? I am just looking for a concrete identification of the general class of problems this belongs to, and any out-of-the-box reasoners which may be available. Perhaps this is an SMT problem?

# Answer
Yes, you could solve this with a SMT solver that supports linear real arithmetic. However SMT supports more general inequalities where you can have linear sums of variables (e.g., $2a+3x \le 5.7$) instead of simple comparisons between a single variable and a constant (e.g., $a \le 1.6$), so it might be more powerful than you need, so if you don't have any linear inequalities involving sums, then I agree with Pseudonym that the best approach may be to use a SAT solver.

I would suggest a slightly different encoding to SAT. Instead of a one-hot encoding, where $x\_i$ means that $c\_{i-1} \le x \le c\_i$, I would suggest a slightly different encoding: $x\_i$ means $x \le c\_i$. Thus instead of encoding to a $(x\_1,\dots,x\_n)$ vector like $(0,0,0,1,0)$ you would encode to $(1,1,1,1,0)$. You add constraints that $x\_i \implies x\_{i-1}$, and then each inequality $x \le c\_i$ corresponds to a boolean variable $x\_i$.
> 2 votes

# Answer
In your case, the simplest solution may be to use SAT.

Your first clause includes $x \le 0.25$ and $x \> 0.91$. This means that there are five regions of interest for the variable $x$, which we identify with boolean variables: $X\_1 \equiv x \in(-\infty, 0.25)$, $X\_2 \equiv x = 0.25$, $X\_3 \equiv x \in (0.25, 0.91)$, $X\_4 \equiv x = 0.91$, $X\_5 \equiv x \in (0.91,\infty)$.

Create a boolean variable for each of these ranges, and convert the clause to use them. So, for example, $x \le 0.25$ would convert to $X\_1 \vee X\_2$, and $x \< 0.91$ would convert to $X\_1 \vee X\_2 \vee X\_3$.

More clauses would mean more constants, and hence more ranges of interest for a primitive variable.
> 3 votes

---
Tags: constraint-satisfaction, automated-theorem-proving, smt-solvers
---


# Question
Title: efficient algorithm for min cut with specified number of vertices
Consider a graph with vertices $V$ and edges $E$. The standard version of the min cut problem is to find the partition of $V$ into a (non-empty) subset $C$ and its complement $\bar{C}$ so as to minimize the number of edges going between $C$ and $\bar{C}$. Algorithms are known for this problem which solve it in polynomial time. My question is, what if one additionally specifies the constraint that $|C| = n$ for some $n \< |V|$? That is, we wish to find the set of $n$ vertices with the minimal number of edges connecting it to the rest of the vertices. Are there also efficient algorithms for this case? I am interested both in the question of whether this problem is formally solvable in polynomial time (which I would guess that it is) and also in what algorithms are best in practice.

# Answer
For $n= \frac {|V|} 2$, it's called Minimum Bisection, and it's NP-hard. There exists an $O(\log^{3/2} n)$-approximation: "A polylogarithmic approximation of the minimum bisection".

If you are interested, the more general problem is splitting into multiple components of the same size, and it is called Balanced Graph Partitioning. For more than 2 parts no finite approximation exists unless P=NP: "Balanced Graph Partitioning" (Andreev, Rakke), since you can't efficiently check if the answer is 0.

If the parts are not necessarily exactly balanced (a small imbalance is allowed), an $O(\log n)$-approximation algorithm exists: "Balanced Partitions of Trees and Applications".

---

Some algorithms (also check https://en.wikipedia.org/wiki/Graph\_partition and "references" sections of the following papers):

* Local search with various flavors: we start with some partitioning and then try to swap vertices between parts to minimize the cut. E.g. we compute "gain" for each vertex (improvement if we move it to another part), and swap vertices with the maximum gain. Its advantage is that you can apply it after any other algorithm.
* Spectral partitioning (see e.g. Spectral Graph Theory and Graph Partitioning): uses the second eigenvector of a Laplacian matrix to approximate the partitioning (e.g. by moving the smallest $|V|/2$ coordinates to the first part). Works surprisingly well. However, I'm not sure it can be adapted to the case when you want an unbalanced bisection (e.g. $1:2$ instead of $1:1$).
* Linear embedding: "Distributed Balanced Partitioning via Linear Embedding". We embed vertices into a one-dimensional array while minimizing sum over all pairs of vertices: the distance between them multiplied by the weight of their edge. Then we just split this array into consecutive chunks of required sizes. Didn't work that well in my experience.
* (Ads) Our paper: "Multi-Dimensional Balanced Graph Partitioning via Projected Gradient Descent", where we used gradient descent to find minimum bisection: for each vertex we introduce a variable which roughly represents a probability that the vertex belongs to the first part, and minimizing the cut reduces to constrained optimization of a quadratic function. It's a bit outperformed in practice by a fine-tuned local search, but it works really well when you have multiple balance constraints.

Aside from the spectral method, all of them can be trivially adapted to partitioning the graph in arbitrary proportions.

There are also standard solvers: KaHIP, METIS. In my experience, KaHIP was pretty good. I'm not sure they support splitting into parts of arbitrary sizes though.
> 6 votes

---
Tags: algorithms, graphs, time-complexity, optimization
---


# Question
Title: Church–Turing thesis and infinite Turing machines
What exactly is the definition of church turing thesis? It's really confusing.

I want to prove the following statement:

> A Turing machine with infinitely many states is more powerful than a regular Turing machine, as it can accept all languages.

How does this statement not contradict the Church–Turing thesis?

I don't exactly understand the definition of the Church–Turing thesis, and how it applies in this context.

# Answer
The Church–Turing thesis is the following philosophical claim:

> Our intuitive notion of computability coincides with the mathematical notion of computability.

Here the mathematical notion of computability states that a language is computable if some Turing machine computes it, and the intuitive notion of computability is necessarily vague.

Turing machines with infinitely many states can compute any language (exercise), and so are more powerful than the usual Turing machines, which can only compute computable languages. We know that not all languages are computable. Indeed, almost all languages are uncomputable, since there are only countably many computable languages, but uncountably many languages. Also, certain concrete languages such as the Halting Problem are known to be uncomputable.
> 2 votes

---
Tags: turing-machines, computability
---


# Question
Title: Paging only for user code. What about kernel code?
Why is paging done only for user code (user space)? I know that the basic intuition behind paging is for managing larger logical address space in smaller physical main memory space. Won't the kernel size also be large? If the kernel code is large enough and the RAM size is small, then how is it managed? Please clarify.

# Answer
Other than the fact that kernels tend to be small, as Yuval points out, you should also consider that they are often not relocatable code (in fact, address binding for kernels is done at compile-time) and so the memory they are allocated could not be moved or swapped-out in any case, not only for paging. Obviously there are also performance-related concerns, and one should consider handling exceptional cases too, like the code responsible for paging being swapped out.

Usually, memory limitations in operating systems are handled in different ways other than paging. For monolithic kernels, this means offering a loadable module system, while for microkernels the problem might not even apply, since their footprint on main memory is usually much lower than monolithic kernels (system services in microkernels are implemented as user-level processes).

---

Last but not least, enabling paging on kernel memory would defy one of its main definitions, being *"\[that\] part of the operating system that is always resident in memory"* ;-).
> 3 votes

---
Tags: operating-systems, paging, os-kernel, kernel-functions
---


# Question
Title: Why is $((aa)^*bb(aa)^*bb(aa)^*)^*$ of star-height 1
A generalized regular expression is like a regular expression but with one more operation allowed: complementation. The (generalized) *star-height* of a generalized regular expression is the maximal number of nested Kleene stars. The star-height of a language is the minimal star-height of a regular expression describing it. It is not known if there is even a language of star-height 2.

So I imagine the langage $((aa)^\*bb(aa)^\*bb(aa)^\*)^\*(aa)^\*$ of words consisting of concatenations of $aa$ and $bb$, with an even number of $bb$, is of generalized star-height $1$. But I couldn't prove it. In the paper *Some results on the generalized star-height problem* (Pin, Straubing, Thérien), lemma 6.1 (the transfer lemma) cannot be applied because both $(bb)^\*$ and $(aa)^\*$ are of star-height 1.

I saw elsewhere some languages which were conjectured to be of star-height 2 and they were more complex than the one I give, so it is very probably of star-height 1. Is it the case?

# Answer
(This is an attempt to an answer, I hope the details are right.)

Your language consists of all strings in $(aa+bb)^\*$ with an even number of $bb$.

We are allowed to use complementation, so we start by looking at the complement of the language. I think we can split the complement into two (overlapping) parts

* strings not of the form $(aa+bb)^\*$, that language has starheight one.
* strings of the form $w\_0\cdot bb\cdot w\_1\cdot bb\cdot w\_2 \dots bb\cdot w\_n$, where (1) the number of $bb$ is odd, and (2) the $w\_i$ do not contain any $bb$ (but I will have to be more precise on that)

Now we will try to find an expression for the language $W$ of the $w\_i$ without using star. That means we can use the star to count the odd number of $bb$, as in $(W\cdot bb\cdot W\cdot bb)^\*\cdot W\cdot bb\cdot W$.

This is the tricky part. Strings from $W$ are either

* the empty string $\varepsilon$
* just one single $a$
* of the form $axa$, where $a$ does not contain $bb$. Not "containing $bb$" is the complement of $(a+b)^\*bb(a+b)^\*$, and as you know $(a+b)^\*$ is again star-free.

The strings we now have specified can have longer stretches of $b$'s, but whenever that happens the $b$'s come in pairs.
> 1 votes

---
Tags: regular-languages
---


title: algorithm for checking satisfiability

text:
# Question
Title: algorithm for checking satisfiability
In order to prove that SAT is in NP, I need to come up with a polynomial time verfier (an algorithm). The Cooks Levin Theorem uses a non-deterministic Turing machine but that's not what I am looking for.

The idea of the algorithm could be that we put in the values and calculate the answer. Then, we check whether the answer is 1 or not. However, I am unable to understand how I could write a psuedocode for the 'putting in values' part and then show that it's polynomial for sure.

```
if x = 1:
 accept
else:
 reject

```

This could be in O(1). But what about the remaining part?

# Answer
> 1 votes
Here is how I would do it:

**Algo:** Verifier for DNF-SAT problem given as array of closures and a possible mapping of literals to booleans
**Input:**
Array of closures: \[$C\_1$,$C\_2$,...,$C\_m$\]
where $C\_j \subseteq \\{x\_1,...,x\_n,\neg x\_1, ... \neg x\_n\\}$
(Certificate) Array $M$ where $M\_i$ is the boolean value of literal $x\_i$
**Output:** true or false

```
for $i = 1$ to $m$:
  value = true
  for literal in $C_i$:
    if literal == $x_i$:
      value = value or $M[i]$:
    else if literal == $\neg x_i$:
      value = value or (not $M[i]$)
  if not value:
    return false
return true

```

Note: the math notation is indented and commonly used in pseudocode sadly cs stackexchange doesn't support it

---
Tags: complexity-theory, computability, np, satisfiability, 3-sat
---


# Question
Title: Decidable non-context-sensitive languages
It is arguable that most languages created to describe everyday problems are context-sensitives. In the other hand, it is possible and not hard to find some languages that are not recursive or even not recursively-enumerable.

Between these two types are the recursive non-context-sensitive languages. Wikipedia gives one example here:

> An example of recursive language that is not context-sensitive is any recursive language whose decision is an EXPSPACE-hard problem, say, the set of pairs of equivalent regular expressions with exponentiation.

So the question: What others problems exists that are decidable but yet non-context-sensitive? Is this class of problems the same as decidable EXPSPACE-hard?

# Answer
CSL is the same as $\mathsf{NSpace}(n)$ (non-deterministic linear space). Any language which is outside $\mathsf{NSpace}(n)$ is not CSL.

To get a feeling of the situation, remember that $SAT \in \mathsf{NSpace}(n)$ and even TQBF.

> What others problems exists that are decidable but yet non-context-sensitive?

The are many problems. Any problem that is complete for a complexity class larger than $\mathsf{PSpace}$ will do (we need $\mathsf{PSpace}$ because problems like TQBF in $\mathsf{NSpace}(n)$ that are complete for $\mathsf{PSpace}$ because a (polynomial time) reduction can blow up the size of an input by a polynomial). Giving an example will mean proving a lowerbound for the complexity class containing the problem and that is very very difficult task. The only major way we know so far to do this is diagonalization which intuitively means that the larger class should be able to simulate the smaller class.

So $\mathsf{ExpSpace\text{-}hard}$ seems a natural place to start to look for natural examples of language which are not CSL.

> Is this class of problems the same as decidable EXPSPACE-hard?

No. By the space hierarchy theorem, there are languages which are in $\mathsf{NSpace}(n^2)$ which are not in $\mathsf{NSpace}(n)$. If you are asking for nice examples, that is going to be difficult because the theorem works using diagonalization and therefore the language it proves to satisfy these conditions is very artificial.

I suggest that you ask a separate question for a natural problem that separates $\mathsf{NSpace}(n^2)$ from $\mathsf{NSpace}(n)$.
> 11 votes

# Answer
Just like $\\{a^nb^n:n\geq 0\\}$ is context-free but not regular, the language $L=\\{a^nb^nc^n:n\geq 0\\}$ is decidable but not context-free. However, $L$ can be solved using logarithmic space (you just need a counter for each of the symbols $a$, $b$ and $c$), so it is not EXSPACE-hard.

Also, the language $\\{(r\_1,r\_2):L(r\_1)=L(r\_2)\\}$, where $r\_1$ and $r\_2$ are regular expressions, is PSPACE-complete. I'm almost sure it's not context-sensitive, but I don't remember a proof and I'm writing from my phone, so it's not easy to go looking for references.
> 3 votes

# Answer
intersection operator\to the syntax of regular expressions, deciding whethertwo such expressions describe the same language is EXPSPACE-hardcheck here hence this language is not context sensitive but recursive https://jeffe.cs.illinois.edu/teaching/algorithms/book/12-nphard.pdf
> 0 votes

---
Tags: formal-languages, complexity-theory, formal-grammars
---