# Question
Title: What was the first Turing-Complete programming language?
What was the first turing-complete language? Know about the first machines and computers, but not the programming language.

# Answer
> 1 votes
Why not read this Wikipedia article.

> The first programming languages designed to communicate instructions to a computer were written in the 1950s. An early high-level programming language to be designed for a computer was Plankalkül, developed by the Germans for Z1 by Konrad Zuse between 1943 and 1945. However, it was not implemented until 1998 and 2000.

Also, I think that it is wrong to consider a programming language as such to be Turing Complete since the concept of Turing completeness applies to a computational model, not to a programming language itself. For example, it is Turing machine, RAM machine, or Post systems that is Turing complete and not a set instructions or programming languages used to program them.

If our real life computers had infinite memory we could consider them a Turing machine equivalent to our abstract model we use in CS and Math, meaning that it is not programming languages or instructions sets used to program CPU that makes real life computers not equivalent to the abstract model.

---
Tags: programming-languages, turing-completeness, history
---


# Question
Title: Lower the frechet distance between two curves
Fréchet distance tells how similar two curves are. Now let's say I have two curves A and B, both represented in several discrete coordinate x, y points. And the fréchet distance between A and B is d. What technique can I employ to find another curve that has d/2 fréchet distance from both curves and has a total euclidean distance which is in the range \[min(|A|, |B|), max(|A|, |B|)\], where |A| is the total euclidean distance of the curve A and |B| is the total euclidean distance of the curve B? I know that there is probably not a single curve, any one curve will be great help for me. Thanks in advance.

# Answer
Raichel and Har-Peled wrote a paper, The Frechet Distance Revisited and Extended, which explains how to compute various curves. This might implicitly give you the answer.
> 1 votes

---
Tags: computational-geometry
---


title: AVL tree partition

text:
# Question
Title: AVL tree partition
The statement sais the following

> Design a function to partition an AVL tree such that, given an AVL tree and a key $x$, it returns two AVL trees, one containing the keys lower or equal than $x$, and the other containing the remaining keys. The complexity must be better than $\mathcal{O}(n)$ (being $n$ the cardinality of the tree).

My attempt is the following recursive algorithm (in pseudo code, so notation abuse is probable).

`split(T x, Node root, Node link, Node lower){
 if(root.key <= x){
 if(lower.isEmpty())
 lower=BinaryTree(root.left,root,null);
 else link.right = BinaryTree(root.left,root,null);
 link = root;
 if (root.key< x)
 split(x,root.right.root,link,lower);
 } else split(x,root.left.root,link,lower);
}`

if I am not mistaken, the algorithm returns a binary search tree (but possibly not balanced) whose keys are the ones in the original tree lower of equal than $x$. An analogous one can be done to build the other tree.

So, the question is how to balance both trees without icreasing the current $\mathcal{O}(\log n)$ complexity.

# Answer
> 1 votes
**Basic Idea:** If the root of the tree is equal to $x$ then we just split the tree into two parts $root.left$ and $root.right$, and add $x$ to the $root.left$. This case is trivial and takes $O(\log{n})$ time.

### Case 1 (trivial, root.data = x)

### Case 2 (root.data \> x)

Initialize $T\_l = T\_\emptyset$ (empty tree). We start from root and move in the leftmost direction down the left subtree until we find an element $y$ less than $x$ (see the figure below). At this point we detach $y$ from $w$ and add $y$ to its left subtree $T\_1$ (its elements are less than $x$), but make $T\_2$ $w$'s left child. Since the initial subtree is AVL there is a chance $|height(T\_2) - height(T\_3)| = 2$ in which case we left-rotate at $w$ to balance the new subtree with root at $w$. This updates the height of the node $w$ and we ascend along the leftmost path up to the root by updating nodes' height and rotating if necessary to balance the subtrees (by single left rotations).
Then we again repeat these steps until we find $x$ (which is handled like in the case 1) or there is no element less than or equal to $x$, and so we stop. At each step we join new $T\_l$ and new subtree whose elements is less than $x$. (Note: computing a length of a node takes $O(\log{n})$ time$).

### Case 3 (root.data \< x)

In this case we should add $root.data$ to $root.left$, join $T\_l$ and $root.left$ ($T\_l = Join(T\_l, root.left)$) and set $root = root.right$. If $root.data$ is still less than $x$ then repeat these steps above again until $root.data \geq x$.

```
  Tl = {}
  Tr = T #original AVL tree

  while (root.data < x) # O(\log{n})
    add root.data to root.left  # O(log(n))
    T_l = Join(Tl, root.left)   # O(log(n))
    root = root.right
  end

  loop
    node = root
    go to left until node.data <= x
    if no node with node.data <= x found
      return Tl, Tr
    else
      T_temp = add node.data to node.left
      node.parent.left = node.right
      compute height(node.right) and height(node.parent.right)
      left-rotate at node.parent if these heights differ by two
      backtrack to the root by updating heights of nodes and left-rotating if necessary
    end

    Tl = Join(Tl, T_temp)
  end

```

**Analysis:** The outer loop runs at most $\log{n}$ times since at each step we the length of the leftmost path decreases by $1$. Computing heights of two nodes is $O(\log{n})$. Joining $T\_l$ and $T\_{temp}$ also $O(\log{n})$. Thus we have $O(\log^2{n})$ running time which is better than $O(n)$.

---
Tags: algorithms, data-structures, search-trees, balanced-search-trees
---


# Question
Title: How shall I resolve a nonlocal name in a language with deep binding?
From Programming Language Pragmatics by Scott,

> **Figure 3.14 Deep binding in Python.** At right is a conceptual view of the run-time stack. Referencing environments captured in closures are shown as dashed boxes and arrows. When B is called via formal parameter P, two instances of I exist. **Because the closure for P was created in the initial invocation of A**, B’s static link (solid arrow) points to the frame of that earlier invocation. B uses that invocation’s instance of I in its print statement, and the output is a 1.
>
> The catch is that a running program may have more than one instance of an object that is declared within a recursive subroutine. A closure in a language with static scoping captures the current instance of every object, at the time the closure is created. **When the closure’s subroutine is called,** it will ﬁnd these captured instances, even if newer instances have subsequently been created by recursive calls.

So basically, the quote tries to explain that the following program (which is the same as the one in the screenshot) prints out `1`:

```
def A(I, P):
    def B():
        print(I)
    # body of A:
    if I > 1:
        P()
    else:
        A(2, B)

def C():
    pass # do nothing

A(1, C) # main program

```

I don't quite understand the reason being "because the closure for P was created in the initial invocation of A, B’s static link (solid arrow) points to the frame of that earlier invocation", and "When the closure’s subroutine is called, it will ﬁnd these captured instances". So I modify the example, and then the new example prints out `2` instead of `1`:

```
def A(I, P):
    def B():
        print(I)
    if I > 2:
        P()
    elif I > 1:
        A(3, B)
    else:
        A(2, B)

def C():
    pass

A(1, C)

```

Another modified example prints `1`:

```
def A(I, P):
    def B():
        print(I)
    if I > 2:
        P()
    elif I > 1:
        A(3, P)
    else:
        A(2, B)

def C():
    pass

A(1, C)

```

So how can I know which closure matters when resolving a nonlocal name in a language with deep binding?

Generally, is a closure created whenever a function is passed as an argument to another function?

Thanks.

# Answer
Roughly put, every time you define a function, as in `def B(): ...` you define B to be a closure. This is a pair contains a representation of the body of the function (possibly compiled to a simpler language), and a reference to the current environment (possibly restricted to what B actually needs). The current environment is the one we are in when we run `def B(): ...`.

In the example you provide, `B` is defined inside `A`, so its associated closure gets a reference the the current call frame of `A`. This is why, if you pass `P=B` in the recursive call, after the call running `P` prints the value of `I` in the *previous* call frame.

Note that, in many languages, closures can be returned, which makes the current call frame to be *not* freed after the return. For example,

```
def A(I):
  def B():
    print(I)
  def C():
    nonlocal I  # Python for "use A's I, don't create a fresh local I"
    I += 1
  return (B,C)

# main
(b,c) = A(10)
b() # 10
c()
b() # 11
c()
b() # 12

```

Above, we can see that, even if `A` returned, its local variable `I` is still live! It can be accessed through the two returned closures, which contain a reference to the `A`'s call frame, even if `A` is now finished.
> 1 votes

---
Tags: programming-languages, variable-binding
---


title: Minimal DFA: Number of states

text:
# Question
Title: Minimal DFA: Number of states
I am trying to solve a problem with regards to a DFA. What is the minimal number of states for the following language:

$$L:=\\{x\in\\{a,b\\}^n\ \ | \ \ |x|\_a=|x|\_b\\}$$

where $|x|\_a$ denotes the amount of $a$'s in the word $x$. I have done some calculations and got $3\cdot2^{(n/2)}-1$. Is this the correct number of states?

Here is the DFA for $n=4$:

# Answer
**Hint**. Your answer is plain wrong. First, it trivially does not work if $n$ is odd. But it is also wrong if $n$ is even (except for $n = 2$). Just compute the minimal automaton of $\\{aabb,abab,abba,baab,baba,bbaa\\}$ to be convinced. Your formula gives $3\cdot 2^2 - 1 = 11$ states but the minimal automaton only has $10$ states.
> 3 votes

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


# Question
Title: How to determine the maximum RAM capacity for an operating system?
I was curious to know what limits the max RAM capacity for an OS while reading about microprocessors being 32-bit and 64-bit. I know that limit for 32-bit OS is 4GB and for 64-bit OS is 16 Exabytes, but my question is how do we get there? I found this calculation:

$\qquad 2^{32} = 4\\,294\\,967\\,296$

and

$\qquad \frac{4\\,294\\,967\\,296}{1024 \cdot 1024}\\,\mathrm{B} = 4\\,096\\, \mathrm{MB} = 4\\, \mathrm{GB}$.

It's different for 64-bit:

$\qquad 2^{64} = 18\\,446\\,744\\,073\\,709\\,551\\,616$

and

$\qquad \frac{18\\,446\\,744\\,073\\,709\\,551\\,616}{1024 \cdot 1024}\mathrm{B} = 16\\,\mathrm{EB}$.

What I don't understand is how the calculation of bits turned into bytes and reached the results 4GB and 16EXB?

# Answer
> 1 votes
1. First of all, in computer architecture, 32-bit/64-bit computing is the use of processors that have datapath widths, integer size, and memory addresses widths of 32/64 bits (four/eight octets). Also, 32-bit/64-bit CPU and ALU architectures are those that are based on registers, address buses, or data buses of that size(due to design decisions that may differ in different CPU/OS).
2. Secondly, there is a confusion that is created when calculating the maximum RAM capacity for 32/64 bit OS/microprocessor. The 32-bit/64-bit address/machine word is usually considered as containing a single **byte word** and not **byte** (*e.g a byte word might be a floating point number of 32/64 bits depending on the architecture & a byte on the other hand is 8 bits*) but since we do all our memory calculations in terms of bytes the result her too is in terms of bytes. Hence, **bytes** is the unit written where

1byte = 1 byteword = 1 address space/machine word

So if we have 4,294,967,296 addresses that means we can address as much byte words and hence the total capacity of RAM in a 32-bit OS is 4GB, similarily for 64-bit OS the calculations are of addresses with one byteword each and later written in terms of bytes.

I hope this should make it pretty clear. Thank you for your inputs and replies.

# Answer
> 5 votes
The calculation is in bytes since the memory is addressed in units of bytes. If a machine word is $N$ bits and an addressed is stored in a register whose size is a single machine word, then you can address $2^N$ different locations, each of which is a byte (in principle, that could depend on the CPU, but I'm not aware of any CPU which addresses its memory in larger words). However, more complicated addressing mechanisms can be used to address more memory. For example, pointers could take up more than a machine word, or segments could be applied (as in 80386 and its successors).

# Answer
> 1 votes
The simple answer that 32bits CPUs can address $2^{32}$ bytes and 64bits CPUs can address $2^{64}$ bytes is quite right, but, one can find some exceptions, or refine the explanation.

CPUs with MMUs manage separate virtual and physical address spaces. They can have different sizes. The 32bits or 64bits designation is about the virtual space : Applications have 32bits or 64bits pointers.

The physical address space can be smaller or larger than the virtual address space :

* In some 32bits x86, starting from the PentiumPro, a larger, 36bits physical address space (=64GB) can be available : Several tasks, each occupying up to 4GB can be simultaneously running on the CPU. The OS must manage a global address space larger than the user software space (and OS writers really hate that, because the OS needs to constantly swap mappings for accessing all the memory). 32bits SPARCs had a similar mechanism.
* In current 64bits x86, the quantity of physical memory that can be really managed is smaller, IIRC 48bits, because 16EXB is too large, for now.

# Answer
> 1 votes
### TL;DR

Q: How to determine the maximum RAM capacity for an operating system?

A: Look into the OS documentation (really).

---

### Let’s dissect

* > I know that limit for 32-bit OS is 4 GB and for 64-bit OS is 16 Exabytes, but my question is how do we get there?

Now we are speaking about flat address space (i.e. how many different addresses a program can distinguish). If such a program is using 32 bit (64 bit) pointers, there are 2³² (2⁶⁴) different addresses. Assuming each of these positions can accommodate 1 byte, we have 4 GB (16 EB) of allocable capacity. This also answers the last question:

> What I don't understand is how the calculation of bits turned into bytes and reached the results 4GB and 16EXB?
* OP refers to 32-bit and 64-bit microprocessors in the first sentence. We need to understand that this reference is to the internal architecture. To illustrate how important is to define topic of discussion let’s have a look at Intel 80386SX CPU:

+ Its architecture is 32 bits,
    + data bus width is 16 bits,
    + address bus width is 24 bits.

While this is 32-bit CPU, it can address only 16 MiB of RAM and it needs two CPU cycles to move a word between a register and the RAM (more examples).

So *why the size of address bus does not always match the size of machine word*? Because the CPU needs to address **reasonable** amount of RAM. Having 8 bit wide address bus on 8-bit CPU would allow for only 256 B of memory. OTOH, having 64 bit wide address bus on 64-bit CPU is not feasible because there is no real demand nor HW available for such a setup, yet it would increase complexity of memory subsystem considerably. What *reasonable* is comes from engineering and business decision made at given time.

There’s related discussion at SO.

# Answer
> 1 votes
The first question is: How much RAM can the hardware support? For example, if there are n bits transferred between CPU and RAM on every access, and the CPU has k address lines, then the CPU can access $2^k·n$ bits, or $2^k·n/8$ bytes.

However, the CPU must address things other than RAM, for example video memory, memory-mapped IO, ROM, and so on. So you need to add up these things to get the maximum usable amount of RAM. And it depends on both the CPU and memory hardware how much is actually usable. For example, if the address lines are enough for 64GB, and other hardware requires 2GB addressable space, then depending on the hardware, only 32GB, or 48GB, or 56GB RAM might be usable, but most likely not 62GB.

The next level is how much RAM the firmware of the computer can recognise. The computer doesn't know how much RAM there is when it is turned on, it must recognise that RAM. That's usually done by software firmly built into the computer. And that software might only be able to recognise say 16GB of RAM. (This often happens with old computers, where no memory chips for more than 16GB were available when the computer was sold, and newer, bigger memory chips cannot be recognised).

So that is all *before* the operating system comes into play. Usually the OS doesn't have any limitations itself. Sure, it requires more memory for page tables etc. if there is more RAM, but then it has more RAM available to hold page tables because it has more RAM. There are cases where the maker of the OS has a "home version" and a "professional version" of the OS, and the "home version" of the OS may be artifically restricted.

Or the OS may have decided to use quite arbitrarily only a small number of bits for the index of a RAM page in some data structure, for example. If the OS uses only 24 bits to store the index of a RAM page, and a RAM page is 4KB, then that OS can only handle 64 GB of RAM. Which is quite possible for an OS written twenty years ago, when someone might have thought "nobody will ever have more than 64GB of RAM". (I remember a computer that could hold up to 1.5GB of RAM, and the RAM was four times more expensive than the rest of the computer).

---
Tags: computer-architecture, operating-systems, memory-access
---


# Question
Title: Show that boring boolean circuit belongs to NP-complete class
> We say that a boolean circuit is boring if it returns the same result for $\>\frac34$ possible input, where we have $n$ input gates. Hence, boring circuit returns the same output ($0$ or $1$) for $\>\frac34 2^n$ inputs. Prove that checking if boolean circuit is boring is NP-complete

Can you help me? I have no idea how to start. I tried to reduce $3$-SAT but no result.

# Answer
> 2 votes
Given a Boolean formula $\varphi$, let $x,y$ be two fresh variables, and consider the circuit computing the function $$ x \lor y \lor \varphi. $$ This circuit is boring iff $\varphi$ is satisfiable.

# Answer
> 6 votes
The problem is PP-hard. This means that unless the polynomial hierarchy collapses to NP, then deciding whether a circuit is boring is not in NP (and consequently is not NP-complete). The collapse follows from the fact that PP is closed under complement, so $\mathsf{PP=NP}$ implies $\mathsf{NP=coNP}$. We now show that deciding whether or not a circuit is boring is PP-hard.

Suppose $L\in PP$, then there exists a probabilistic polynomial Turing machine $M$ such that $x\in L \iff \Pr\left\[M(x)=L(x)\right\]\>\frac{2}{3}$. Now consider the machine $M'$ which tosses two coins, if both output "heads" accept, otherwise execute $M$. If $x\in L$ then $M'$ accepts $x$ with probability $\frac{1}{4}+\frac{3}{4}\Pr\left\[M(x)=L(x)\right\]\>\frac{3}{4}$. Now, let $C\_x$ be the corresponding circuit for $M'$ on input $x$ (its inputs are the coins for $M'$), then $x\mapsto C\_x$ is a reduction from $L$ to your problem, since $x\in L\iff C\_x \text{ is boring}$. To see why, note that if $x\in L$ then $C\_x$ accepts more than $\frac{3}{4}$ of the possible inputs, and if $x\notin L$ then $C\_x$ accepts $\frac{1}{4}\le t\le \frac{3}{4}$ of the possible inputs.

In fact, your problem is PP-complete. To see why this language lies in PP, Let $L$ be the language of circuits who accept more than a $\frac{3}{4}$ fraction of their input, and $L'$ be the language of circuits who reject more than a $\frac{3}{4}$ fraction of their inputs. Clearly $L,L'\in PP$, and since PP is closed under union, deciding whether a circuit is boring, i.e is in $L\cup L'$, is in PP. Note that both here and in the above we used the fact that the constant in the definition of PP can be changed to any rational number.

If we want to avoid using closure properties of PP, then an argument along the following lines should work. Consider the machine $M$, which upon given an $n$-input circuit $C$, approximates the acceptance probability of $C$ by evaluating it on different uniformly distributed random length $n$ strings. Let $\hat{p}$ denote our evaluation. If $\hat{p}\ge\frac{1}{2}$, then $M$ evaluates $C$ on a random string and accept iff $C$ accepts, otherwise $M$ accepts iff $C$ rejects. Let $E$ denote the event that $|p-\hat{p}|\le \frac{1}{4}$, where $p$ is the real acceptance probability of $C$. By evaluating $C$ on polynomially many strings, we can make sure that $\Pr\left\[E\right\]\ge 1-\frac{1}{2^{2n}}$. If $C$ is boring, then conditioned on $E$, $M$ obtained the right evaluation of the majority of $C$ and accepts with probability $\>\frac{3}{4}$. Thus, if $C$ is boring $M$ accepts with probability $\>\frac{3}{4}\left(1-\frac{1}{2^{2n}}\right)$. If $C$ isn't boring, then $C$ outputs either $0$ or $1$ with probability of at most $\frac{3}{4}-\frac{1}{2^n}$. Thus, regardless of our evaluation $\hat{p}$, $M$ accepts $C$ with probability of at most $\frac{3}{4}-\frac{1}{2^n}\<\frac{3}{4}\left(1-\frac{1}{2^{2n}}\right)$, which puts our language in PP.

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


title: Proving $P=BPP$ under a assumption

text:
# Question
Title: Proving $P=BPP$ under a assumption
Let suppose that there exists deterministic polynomial algorithm $A$ that approximates the probability that a given boolean circuit $C$ accepts random input with an error at most $\frac{2}{5}$. More precisely, for a boolean circuit $C(x\_1, .., x\_n)$, $A$ computes a number $A(C)$ such that

$$|\Pr\[C(U\_n) = 1\] - A(C) | \le \frac{2}{5}.$$

$U\_n$ is a uniformly distributed random variable with values in $\\{0,1\\}^n$.

I want to prove that under that assumption $P=BPP$. How can I do that?

Obviously, the problem is with $BPP \subseteq P$. I see that I should create a boolean circuit for "coin tosses", but how?

# Answer
$w$ is an input word, $r$ is a random bits used by a machine to make random decisions.

So, it is obvious that $P \subseteq BPP$, so let's try to show that: $BPP \subseteq P$.

---

Let $L$ in $BPP$. Then $M(w, r)$ be a machine that decides $L \in BPP$. $M$ is a polynomial probabilistic machine. Let $M'(w, r)$ be an polynomially amplifcated $M$, so: $$w \in L \implies Pr\[M'(w, r) \text{ accepts }w\] \to 1$$ $$w \not \in L \implies Pr\[M'(w, r) \text{ rejects }w\] \to 1$$

Now, we construct machine $M\_p$ that recognizes $L$ and works in polynomial time.

Let $w$ be a given word to decide. $M\_p$ constructs in polynomial time a boolan circuit $C$ equivalent to $M'(w,r)$ where $w$ be hardcoded in that circuit. So, the input word is a random string, $r$.

Note, that our machine $M\_p$ So, for a random input $r$ our machine for word $w \in L$ must accept it if $M'$ accepts it with probability $\approx 1$.

But, we must show that $L \in P$ so we cannot use a random word $r$.

Instead, we would like to ask our algorithm about probability of acceptance a random word: $A(C)$. The returned value must be $\approx 0.6$ because possible error is $0.4$. So, if A(C) is $\ge 0.6$ then $M\_p$ accepts, else rejects.

It works in polynomial and it accepts the same language:

$$w \in L \implies Pr\[M' \text{ accepts w is }\] \approx 1 $$ $$w \not \in L \implies Pr\[M' \text{ rejects w is }\] \approx 1 $$
> 1 votes

---
Tags: complexity-theory, probabilistic-algorithms
---


title: System f-sub, how to do type checking?

text:
# Question
Title: System f-sub, how to do type checking?
I was reading that system f-sub (polymorphic lambda calculus with sub-typing) and I was quite confused with its one checking rule called "T-TAPP".

This rule as following (ctx denotes the typing context)

```
   ctx |- t1 : ∀X<:T11. T12    ,    ctx |- T2<:T11
   -----------------------------------------------
            ctx |- t1 [T2] : [X-->T2]T12

```

I could not understand how '\[x--\>T2\]T12' will be used (I know it is substitution). This rule appears on page 10 in the following source. I am looking for two type checking examples, in which above inference rule will be applied and at least one example is a case of type checking failure.

Could anyone provide me with concrete examples?
Description of system F-sub

# Answer
> 3 votes
I know this is old but the previous answer has a huge misconception.

The following function is in System F.

$f = \lambda X. X \rightarrow X \rightarrow X$

All we know of this function is it selects one of its arguments and can be instantieded with any type; $\ f$ \[**Bool**\] : **Bool** $\rightarrow$ **Bool** $\rightarrow$ **Bool**.

In System $F\_{\<:}$ is possible to have the following function.

$f' = \lambda X\<:$**Number**$.\ X \rightarrow X \rightarrow X$

This function can be the addition, multiplication, division, subtraction, etc, and can be instantiated with subtypes of **Number**.

$f'$ \[**Int**\], $\ f'$ \[**Double**\], $\ f'$ \[**Real**\] are valid instantiations, but $\ f'$ \[**Bool**\] not, because **Bool** is not a subtype of **Nat**.

Dependent types are a different thing. It has nothing to do here and is out of the scope of the question, but it is a very interesting topic. See Lambda Cube

# Answer
> 1 votes
It would've helped if you mentioned what page that rule appears in.

Anyhow, from what I can tell here's an example.

```
⊢ t₁ : ∀ X <: Animal. “X makes noise”            ⊢ Cat <: Animal
------------------------------------------------------------
                     ⊢  t₁ [Cat] : “Cat makes noise”

```

The **idea** seems to be that t₁ is to be treated as a generic function, or a dependently-typed function, in that for each Animal subtype X, in our example, it gives us a proof t₁\[X\] and the rule just formalises this idea.

Hope that helps.

---
Tags: type-theory, type-checking, type-inference
---


# Question
Title: Optimizing electoral votes in a political simulation... 200,000+ possibilities, how to run through them?
So basically, in my government class, we are simulating a presidential election. Our grade comes from the presentation of our candidate, but as an added challenge our teacher has a running count of electoral votes garnered. How it works is like this:

1. there are only 18 states amounting to 286 delegates, so 144 needed to win
2. Candidates get a +1 'influence' in certain states (for example home state or somewhere they're popular) and -1, as do VP candidates.
3. Some states (CA and TX) have a pre-existing leaning of up to 2 'influences'.
4. You need to choose 4 issues you're against and 4 you're for, out of a list of 14. Each state has an issue they're against or for. As expected, being in agreement with a state nets you +1 in that state and disagreement nets you -1.
5. If you have more influence in the state, you win it. If it's tied at 0, then the popular vote (the class) gets to decide)

I'm trying to lock up the nomination without even needing to get the popular votes, and I'm trying to figure out what software I could use to do this. I know excel and python 3 at a basic level, but I'm wondering if there's some other way to do it.

Here is an image of what I'm talking about (as you can see, I'm playing as the republicans here). Also, the for and against positions formulas link to here. Now, if I need to choose 4 issues to be for and against, I think that's 14 choose 4 times 10 choose 4, which gives me 210,210 possible combinations. Is there a way to run through all of these to see which will give me the highest Net Electoral Vote count with the lowest closeness factor? Obviously, I don't know my opponents topics yet, but I'd like to have the largest margin of error possible to prevent them from flipping states.

Thanks for any help. tips, advice or comments!

TL;DR: Political simulation, have to find best possible combination of issues to talk about out of 200,000+ possibilities, how do I run through them?

# Answer
> 4 votes
200000 is not a terribly large number, a brute force solution in Python would probably run in reasonable time. You'd have to implement a function that calculates your influences depending on your answers to the 14 issues and then just check all the possibilities. Python has some nice library functions that can help in the itertools package, but programming questions should better be asked on Stackoverflow.

A solution that is requires more learning to implement would writing down the problem as an Integer Linear Program and feeding it to a solver. That would probably scale much better than a naive brute force solution. It also sounds more sciency. But as I said, your problem instance is reasonably small.

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


# Question
Title: Graphs: Dectect a sink in $\mathcal{O}(V)$
> Given a directed conected graph which representation is its adjacency matrix $A$, design an algorithm to detect a sink in $\mathcal{O}(V)$ time, being $V$ the number of vertices.

As definitions can vary, in this context, a sink is defined as a vertex with $0$ exit degree and $V-1$ enter degree.

Obviously, the problem is reduced to find a $j\in\\{1,\dots,V\\}$ such as $a\_{ji}=0$ for all $i$ and $a\_{ij}=1$ for all $i\not=j$, thats what I tried. However, this solution is in $\mathcal{O}(V^2)$.

Any idea?

# Answer
> 2 votes
**Assumption** :There is at most one row which contains all zero's.

You want to find a row of the adjacency matrix $A$ whose all entries are zero's. Simple observation if say the desired row is $k$th than in the $k$th column of adjacency matrix $A$ will contain all ones except the \[k,k\] index (it is easy to verify ). Let $n$ is the number of rows and columns in the matrix $A$.

> **Algorithm** :
>
> 1. Start from the top right corner of the matrix $A$.
> 2. If $a\_{i,j} = 0$ and $i \neq j$ then it's not your required column, skip this column mean move to $ j-1 $th column (see you have skipped one column in this step, so the number of columns for your search has been reduced).
> 3. if $a\_{i,j} = 1$ and $i \neq j$ then it is your required column, but it is not required row (think why ? ) so change the row move to $ i+1 $th keep the column same.

**Running time. :** In each step you either reducing the number of rows or number of columns, so maximum number of steps is going to be at max $2n$ (number of rows + number of columns ).

# Answer
> 0 votes
I believe this page provides an answer. The following pseudocode is from that page:

```
   def find-possible-sink(vertices):
     if there's only one vertex, return it
     good-vertices := empty-set
     pair vertices into at most n/2 pairs
     add any left-over vertex to good-vertices
     for each pair (v,w):
       if v -> w:
         add w to good-vertices
       else:
         add v to good-vertices
     return find-possible-sink(good-vertices)

   def find-sink(vertices):
     v := find-possible-sink(vertices)
     if v is actually a sink, return it
     return "there is no spoon^H^H^H^Hink"

```

---
Tags: algorithms, graphs, searching
---


title: Finding all additive orders

text:
# Question
Title: Finding all additive orders
Suppose there are $m$ items, and each item has a price. We order the subsets of items according to their price. For example, if the price of $x$ is 1 and the price of $y$ is 2, then the order is:

$$ \emptyset \< x \< y \< xy $$

What is an algorithm for enumerating all orders of subsets that can be generated by such prices? For example, for two items the output should be two orders:

$$ \emptyset \< x \< y \< xy \\ \emptyset \< y \< x \< xy $$

For three items, the output should be 12 orders - 2 orders for each permutation of $x,y,z$. For example, for $x\<y\<z$ the two orders are: $$ \emptyset \< x \< y \< z \< xy \< xz \< yz \< xyz \\ \emptyset \< x \< y \< xy \< z \< xz \< yz \< xyz $$

One solution is to generate all $(2^m)!$ orders and then check, for each order, whether it is compatible with some prices. However, it is not clear how to do this check, and even with a good algorithm for such a check, it will still very wasteful as most orders will be incompatible. For example, for 3 items we will need to check $8!$ orders to return only 12.

Note: I asked a similar question in math.SE, but the answer is apparently incorrect.

# Answer
> 4 votes
One approach is to recursively extend prefixes of the order. At each recursive call, we have a prefix $\phi$ of the order. We go over all remaining subsets, and for each subset $S$, we check whether the order $\phi \< S$ is consistent. For each consistent $S$, we make another recursive call.

How do we check whether $\phi \< S$ is consistent? This is a linear programming problem, whose solution we can speed up by starting the simplex algorithm from the "witness" showing that $\phi$ is feasible. There are two things to notice here: First, presumably you are assuming that all weights are positive. Second, we replace each constraints $A \> B$ by $A \geq B+1$ (since LPs don't have strict constraints).

There are many optimizations which can be done here. For example, $S$ is always inclusion-minimal among the remaining subsets. Another optimization is to assume that the weights are ordered in a specific way (in your example, $x \< y \< z$); if you are really interested in all possible orders, you can always go over all permutations later.

---
Tags: combinatorics
---


# Question
Title: Does there exist a language which is PSPACE-complete and regular?
> Does there exist a language which is PSPACE-complete and regular? (reduction is polynomial with regard to time).

Correct answer here is "unknown". I can't prove it. Can you help me?

# Answer
> 3 votes
There exists a PSPACE-complete regular language if and only if P=PSPACE, which is unknown.

In fact, we can say even more: the language $\\{1\\}$ is PSPACE-complete if and only if P=PSPACE.

---
Tags: complexity-theory
---


title: Is P decidable?

text:
# Question
Title: Is P decidable?
1. It seems correct that any single given algorithm must either have polynomial runtime or not. Is there a specific algorithm that (does or does not actually lie in $P$, but) can neither be proven nor disproven to do so?
2. Is there a decision procedure for "$\in P$"?
3. Do we know $P$ vs. $NP$ to be decidable? Could it be proven undecidable in the way that an algorithm with proven "optimal" (i. e. proven asymptotically fastest) runtime is non-constructively provided, and then one proves that it is undecidable whether the optimal algorithm has polynomial runtime or not?

# Answer
The following problem is undecidable:

> Given an algorithm $A$, decide whether it runs in polynomial time.

Indeed, if you could decide this problem, then you could decide the halting problem, in the following way. Let $M$ be an input to the halting problem (we want to know whether $M$ halts on the empty input). Construct an algorithm $A$ which, on input $n$, runs $M$ for $n$ steps, and if $M$ halts, counts from $1$ to $2^n$. Then $M$ halts iff $A$ doesn't run in polynomial time.

---

You seem to be conflating several different meanings of *decidable*:

1. Decidable by an algorithm.
2. Can be proved or disproved.
3. Is true or false.

It is meaningless to ask whether "P vs. NP" can be decided by an algorithm, since there's no input here. It is meaningful to ask whether "P vs. NP" is determined by the "axioms of mathematics" (say, ZFC) or not; see what Scott Aaronson has to say about it. Finally, in classical logic every statement is either true or false, and in particular either P=NP or P≠NP.
> 6 votes

# Answer
1. **P** is a class of languages, not a class of algorithms. A language (or problem) is in **P** if there is some Turing machine that decides it in a polynomial number of steps. So, for example, determining whether a graph is connected is in **P**, since a TM can determine that efficiently. However, there are arbitrarily inefficient algorithms to determine connectivity: for example, an algorithm could waste time counting to $2^n$ before looking at the graph. If you want to know whether a particular algorithm runs in polynomial time, that is undecidable, as Yuval shows.
2. No, because that isn't even a computational problem. Suppose that you wanted to design a Turing machine that determined if given languages were in **P**. What would the input to your Turing machine be? Remember – it has to be a finite string. Probably the closest you could get is to give a Turing machine as input and ask if the language accepted by that machine is in **P** (i.e., either the given TM decides the language in polynomial time or some other TM does). But that is undecidable for the same reasons as above.
3. No because, again, that isn't a computational problem: it's something that's either true or false. In this case, there's no input at all.
> 2 votes

---
Tags: complexity-theory, computability, undecidability
---


# Question
Title: Why is there no regularity condition in case 1 of the master theorem?
In case 3 of the master theorem, which is applicable when most of the work is being done at the top node (roughly speaking), we also need a regularity condition that the work done at the topmost level is greater than that at the bottom levels, in addition to it being greater than work being done at last level. However, in case 1, which is applicable when most of the work is being done at the last level, we assume that it will be greater than all the previous levels. Why is that? Shouldn't there be a regularity condition for case 1 also?

# Answer
> 1 votes
You are asking why the regularity condition is absent in case 1. What you *should* be asking instead is why the regularity condition is present in case 3. Let's start with the latter question.

Consider the recursion $$ T(n) = T(n/2) + f(n), \text{ where } f(n)=n^{1 + (\log\_2 n \bmod 2)}. $$ For simplicity I define the function $f$ only for powers of 2, and it is given by $f(2^{2k}) = 2^{2k}$, $f(2^{2k+1}) = 2^{4k+2}$. You can check that $T(n) = \Theta(n^2)$, and so it is not the case that $T(n) = \Theta(f(n))$ (since for $n = 2^k$, $f(n) = n$).

This shows that some regularity condition is indeed necessary in case 3. The proof shows that this particular regularity condition suffices for the conclusion $T(n) = \Theta(f(n))$ to hold.

In case 1, in contrast, the proof works for *every* function $f(n)$ satisfying the condition $f(n) = O(n^c)$, where $c$ is strictly smaller than the critical exponent. You can try to concoct an example like the one above, but you will necessary fail, since the master theorem states that the condition $f(n) = O(n^c)$ suffices for the conclusion $T(n) = \Theta(n^{c\_{crit}})$ to hold.

You can still ask whether there is some deeper reason that the regularity condition is needed in case 3 but not in case 1. I think that the example above is very suggestive: the reason is that in case 3 the answer involves $f(n)$, whereas in case 1 it doesn't. Therefore if $f(n)$ is not well-behaved then it could show up in case 3, but is irrelevant for case 1.

---
Tags: asymptotics, recurrence-relation, master-theorem
---


# Question
Title: Thompson's construction, The empty-expression
Why this case exists in Thompson's construction algorithm?

Isn't just a special case of:
where the symbol **a** is replaced by **ϵ**?

# Answer
> 6 votes
It's not a special case since $a$ is a symbol of the alphabet whereas $\epsilon$ is a symbol representing the empty word. However, you could lump the two cases together if you wish.

It all boils down to your recursive definition of regular expression. Most definitions will have three "axioms": $a$ for $a \in \Sigma$, $\epsilon$, and $\emptyset$. This necessitates three different base cases in the construction.

---
Tags: finite-automata, compilers
---


title: Open question regarding the DFS

text:
# Question
Title: Open question regarding the DFS
It is an **open question** that whether $\mathsf{DFS\text{}}$ can be done in $O(m+n)$ time and $O(n)$ bits of space, where $n,m$ represent the number of vertices and edges in a **undirected graph**. see this for DFS

DFS for directed graph is known to be in RNC i.e. randomised NC. $\mathsf{DFS\text{}}$ also known to be $\mathsf{P\text{-}Complete}$ problem.

My question is what would happen if someone shows that $\mathsf{DFS\text{}}$ can be done in $O(n+m)$ time and in $O(n)$ bits of space?Is it likely in that situation for DFS to admit polyloga-rithmically fast, parallel algorithm using only polynomial resources (see this research paper)?

# Answer
> 2 votes
It is conjectured that $\mathsf{P} \neq \mathsf{NC}$, and so no $\mathsf{P}$-complete problem has polylogarithmic parallel algorithms. This in no way contradicts the existence of a linear time and space algorithm for DFS.

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


# Question
Title: How to find minimum number of k-input LUTs needed to express a n variable boolean function?
An k-input LUT (look up table) takes in atmost k-inputs and gives 1 output (which is a function of the k inputs). I need to devise an algorithm to find the minimum number of k-input LUT's required to express a n variable boolean function.

For example : - n=8 and k=4 8 input variables are a0,a1...a7

1) f1(a0,a1,..a7)= a0\*a1 +a3\*a4 + a5\*a7 + a6\*a8 Requires 3 LUTs : LUT1 :a0\*a1 + a3\*a4 =x1 LUT2 :a5\*a7 + a6\*a8 =x2 LUT3 : x1+x2

2) f2(a0,a1,..a7)= a0\*a1 +a3\*a4 + a5\*a7 + a6 Requires 2 LUTs : LUT1: a0\*a1 +a3\*a4 =x1 LUT2: x1+a5\*a7+a6

NOTE: I want to solve this for the particular case of n=8 and k=4. Though, I would like to extend it to other cases like (n,k)= (8,2).

# Answer
> 3 votes
The following decision version of your problem is NP-complete:

> Given a formula $f$, an integer $k$, and an integer $s$ (encoded in unary), determine whether $f$ can be represented using at most $s$ many $k$-input LUT's.

Indeed, you can easily solve SAT by asking whether the instance of SAT can be represented using at most one 0-input LUT. If you disallow $k=0$, you need to work a bit harder: a formula $\phi$ is satisfiable iff $\phi \oplus x$ (where $x$ is a fresh variable) can be represented using at most one 1-input LUT.

---
Tags: algorithms, optimization, boolean-algebra
---


title: Sorting networks hybrid sort

text:
# Question
Title: Sorting networks hybrid sort
I saw an answer about the fastest way to sort an array with 6 elements. Turns out that using a sorting network is the best choice. If sorting networks are the fastest way to sort a small(\< 16 elements) fixed size array, would it make sense to use them in quicksort or mergesort when the recursive call is for an array with less than the given threshold?

# Answer
The article *Applying Sorting Networks to Synthesize Optimized Sorting Libraries* by Codish et al. experiments in this area, trying to take advantage of "instruction level parallelism and non-branching conditional assignment instructions, both of which are common in modern CPU architectures", and create a quicksort implementation that falls back on sorting networks instead of falling back on insertion sort. In their tests, the result was faster than with the insertion sort fallback. That said, the paper only analyses how it performs with `int`, and has a dedicated "copy-and-swap" algorithm for `int` to order two integers without branches.

The hybrid sorting algorithm RADULS2 described in *Even faster sorting of (not only) integers* by Kokot et al. seems to use sorting networks too. The following note is rather interesting:

> Yet it is worth mentioning, that our implementation of sorting network for 16B records uses SSE to allow elements swapping by branchless code. Without such optimization \[sorting networks\] performed much worse as compilers tend to produce the code with branching instructions. The cost of swapping the elements is easy observable in case of 32B records—in such a situation \[enumeration sort\] clearly outperforms \[sorting networks\].

Access Aligned Sort uses bitonic sorting networks to improve a bottom-up mergesort and ends up with an algorithm that is faster that standard implementations of `std::sort` when sorting properly aligned `float` arrays. The algorithm uses \[Boost.SIMD\] to take advantage of SIMD instructions.

Finally, I've also experimented with sorting networks in a library of mine: I managed to obtain sorting algorithms which were faster than the usual insertion sort for small arrays of `int`, but I had to use the "copy-and-swap" trick described in *Applying Sorting Networks to Synthesize Optimized Sorting Libraries* to make them efficient, and I realized that it didn't really improve things for `long` or `long long` integers. The number of comparison tends to make the algorithm too slow compared to a simple insertion sort, which is adaptive. I tried to use them as a fallback algorithm for quicksort instead of insertion sort, but it didn't make an observable difference.

GPU sorting networks and hardware sorting networks would probably outperform most sorting algorithms, but I don't know much about those. Some guy implemented a few sorting networks with CUDA, you might want to take a look.

**Conclusion:** if you only need to sort small arrays, sorting networks are worth it, but they generally require implementers to carefully implement them if they want decent speed, and most of the time, unless you're sorting something else than raw collections of integers or floating point numbers, they aren't faster than usual sorting algorithms. When you use them as a fallback, it doesn't even always make a speed difference, so unless you *really* need that speed, they're not worth the implementation cost.
> 2 votes

# Answer
It certainly makes sense, and indeed, most descriptions of these algorithms mention that for small enough $n$, insertion sort is used since it is faster.

Why not try it out yourself? Program quicksort and mergesort, and experiment with different versions of these algorithms that switch to handcoded sorts at various thresholds.
> 0 votes

---
Tags: algorithms, sorting, performance
---


# Question
Title: RAM can be accessed hundreds of times faster than a hard drive. Explain How?
* I have been reading this for quiet a long time that "RAM can be accessed hundreds of times faster than a hard drive".
* But, no one has been able to explain it properly.
* I searched on Internet and found that "Access time of RAM is faster because they have **less addresses**(~4GB RAM) than Hard Drive(~1TB), and therefore **address-resolution** is faster".

Please guide me on this topic.

# Answer
Wikipedia has great information on this topic, but as a brief, simplified explanation, know that it boils down mainly to the involvement of mechanical moving parts in a traditional Hard Disk Drive (HDD).

The size of the addressing space in itself doesn't affect the access times. Otherwise you could theoretically build a very small hard-disk drive with only 4GB and expect it to run just as fast as your RAM chip. In reality that is not possible.

## Hard Disk Drives

All the data is read and written by the read and write heads, laying on the round disks that physically store all the data. Whenever data in a specific address is specified, the heads must move to the correct track (the time it takes is the Seek Time) and the disk must rotate until the requested sector is under the head (Rotational Latency). The time until both of these tasks are completed is the Access Time, and only then the data transfer can actually start.

A - Track ; C - (Track) Sector

## RAM

In contrast, RAM cards have no such mechanical moving parts and therefore the time constraints are much lower. They are mainly there to allow proper synchronization of the electronic components that comprise the memory card and ensure that it works reliably.

## SSD

You probably also heard of the term Solid State Drive (SSD). Seagate recently manufactured such a drive with 60TB capacity, and its access times are still much shorter than those of hard-disk drives. How? Like RAM chips, they have *no moving parts*.
> 7 votes

# Answer
RAM is a matrix memory, which is made of capacitors. The matrix is an array of transverse lines (rows) and vertical lines (columns). A capacitor can't be charged if its row terminal isn't grounded and its column terminal doesn't have voltage, the voltage can just exist if it can flow from high voltage to ground. So an IC would scan the columns and rows to charge the capacitors, that process can be done very fast without any mechanical movement. In contrast, hard drives use motors to control the reader arm and rotate the disk, so can't be as fast as RAM.
> 1 votes

---
Tags: computer-architecture, memory-access
---


# Question
Title: Reduction PSPACE language to DSPACE(O(1))
We have a language $L \in PSPACE$. Is it possible to reduce it with $f \in LOGSPACE$ to $L'$ and $L' \in DSPACE(O(1))$? Why/why not?

# Answer
The only languages in $PSPACE$ that can be reduced by the above constraint are languages in $LOG-SPACE$.

Assuming it's a Karp reduction:

A language in $DSPACE(O(1))$ is in $DTIME(O(n))$ (the number of configurations is linear). \[Thanks to Yuval's comment\]

Clearly, everything you can solve in $DSPACE(O(1))$ you can solve in $DSPACE(O(logn))$; So, you might as well leave a bit flag indicating whether to accept the string or not when you reduce the language by solving it in the transducer directly.

Thus, the reduction function will decide the language and since you are constrained to $LOGSPACE$ reduction you can decide only languages in $LOGSPACE$.
> 1 votes

---
Tags: complexity-theory
---


# Question
Title: A problem is NP-hard iff its complement is coNP-complete
$A$ is NP-hard iff $\overline{A}$ is $coNP$-hard, where $\overline{A}$ does mean complement of $A$.

I can't figure out why it is true. Let $A\in NP-hard$. I know that each problem in $NP$ is polynomially reducible to $A$. So, let's "negate" $A$, then by definition: $\overline{A}\in coNP$. However, I am not sure why $\overline{A}\in coNP-hard$. Could you explain it me ?

My intution is that $NP$ and $coNP$ contains only decision problems, using this fact we can use machine for $A$ and negate answer.

# Answer
**Definition**: co$NP = \\{A \mid \overline{A} \in NP \\}$
**Claim**: $A$ is $NP$-hard iff $\overline{A}$ is co$NP$-hard.
**Proof**:
Assume $A \text{ is } NP\text{-hard}$ ($\Rightarrow$). Then by definition $$ \forall L \in NP, \ \ x \in L \Longleftrightarrow f(x) \in A \ \ (\text{ polynomial reducible})$$ equivalently $$ \forall L \in NP, \ \ x \notin L \Longleftrightarrow f(x) \notin A \ \ (\text{ polynomial reducible})$$ implies $$ \forall L \in NP, \ \ x \in \overline{L} \Longleftrightarrow f(x) \in \overline{A} \ \ (\text{ polynomial reducible})$$ meaning $\overline{L} \in$ co$NP$ and reducible to $\overline{A}$, and thus $\overline{A} \text{ is co}NP\text{-hard}$.

Assume $\overline{A} \text{ is co}NP\text{-hard}$ ($\Leftarrow$). Then moving in the backward direction as above:

$$ \forall L \in NP, \ \ x \in \overline{L} \Longleftrightarrow f(x) \in \overline{A} \ \ (\text{ polynomial reducible})$$ equivalently $$ \forall L \in NP, \ \ x \notin L \Longleftrightarrow f(x) \notin A \ \ (\text{ polynomial reducible})$$ and so $$ \forall L \in NP, \ \ x \in L \Longleftrightarrow f(x) \in A \ \ (\text{ polynomial reducible})$$ meaning $A$ is $NP$-hard.

---

**Update:**

If $L \in NP$ then there exists a NDTM $M\_1$ running in polynomial time such that:

* if $x\in L$ then $M\_1(x)=\text{"yes"}$ for **some** computation paths of $M$.
* if $x\notin L$ then $M\_1(x)=\text{"no"}$ for **all** computation paths of $M\_1$.

If $L \in coNP$ then there exists a NDTM $M\_2$ running in polynomial time such that:

* if $x\in L$ then $M\_2(x)=\text{"yes"}$ for **all** computation paths of $M\_2$.
* if $x\notin L$ then $M\_2(x)=\text{"no"}$ for **some** computation paths of $M\_2$.
> 1 votes

# Answer
This argument is given for any complexity class.

If $C$ is a complexity class (for your question NP) and $L$ is $C-Hard$ (an 'identical' argument can be for complete languages):

If $A \in coC$ so $\bar A \in C$ so $ \bar A \le L$: ($\phi$ is the Karp-reduction for that matter)

$ \exists \phi.x\in \bar A \iff \phi(x)\in L $

Since it's iff the negation is:

$ \exists \phi.x\notin \bar A \iff \phi(x) \notin L$

Hence, (by definition of complementary)

$ \exists \phi.x\in A \iff \phi(x) \in \bar L$

$A \le \bar L \implies \bar L \in coC-Hard$

Negating the answer of an NP Turing machine won't help you to decide a language in coNP (except for trivial cases like language in P), since by definition an NP Turing machine accepts iff **there exist** an accepting branch in its' computation.

For simplicity, assume your NP Turing machine always has a rejecting branch in every computation (we can assume it for every NP Turing machine, why?), negating the answer will result in the trivial language $\Sigma $\* every-time.
> 1 votes

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


# Question
Title: Show that if $NP\subseteq BPP$ then also $NP=RP$ - considerations about solution
> Show that if $$NP ⊆ BPP$$ then $$NP = RP$$
>
> **Solution:** It is enough to show that if $NP ⊆ BPP$ then $3SAT∈ RP$. Let $A$ be a $BPP$ algorithm for $3SAT$. Given a formula $ϕ$ with n variables, we first run $A$ on $ϕ$. If $A$ rejects, we reject. Otherwise, we try to construct a satisfying assignment for $ϕ$ one variable at a time. That is, we try instantiating $x\_1$ to $0$, and then use $A$ to decide if the resulting formula is satisfiable: if so, then we permanently set $x\_1$ to $0$ and proceed with $x\_2$; otherwise we set $x\_1$ to $1$ and proceed with $x\_2$. If we manage to construct a satisfying assignment we accept, otherwise we reject, and so on. If $ϕ$ is unsatisfiable, then we always reject. If $ϕ$ is satisfiable, then we construct a satisfying assignment and accept provided that the $n + 1$ invocations of $A$ that we make are all correct. We can ensure that this happens with high probability by replacing each invocation of $A$ with $O(\log n)$ independent ones and taking the majority answer

It is fine solution from https://people.eecs.berkeley.edu/~luca/cs278-04/notes/sol.pdf

My only question is: Why $O(\log n)$ ? After all, we can run it polynomially to make error probablity exponetially small.

# Answer
> 5 votes
It's true that we can run $A$ even more times, but $O(\log n)$ times suffices for us to obtain a certainty of $1 - 1/(100n)$ (say) for each $x\_i$. Applying the union bound, we deduce that the algorithm finds a valid truth assignment with probability at least $1 - 1/100$.

If you run $A$ polynomially many times then you get an *exponentially* small error, which is not needed here.

---
Tags: complexity-theory
---


title: Check if $P^{NP} = P^{coNP}$

text:
# Question
Title: Check if $P^{NP} = P^{coNP}$
> Check if $P^{NP} = P^{coNP}$

To my eye answer is "unknown".
I would try to show that it implies that $coNP=NP$, what is unknown fact.

Lets suppose that $P^{NP} = P^{coNP}$. Then we use simply deterministic turing machine $M\in PTIME$ which use oracle. Lets launch both oracles on the same arbitrary instance. It is moment in which I don't know how to continue. Can you help me?, please ?

# Answer
> 0 votes
Classes $\mathsf{P^{NP}}$ and $\mathsf{P^{coNP}}$ are equal.

Maybe it's not good example (because it is functional problem), but let's look at optimization version of TSP.

It asks *what is the length of the shortest cycle that passes through all vertices?* It is $\mathsf{FP^{NP}}$-complete.

To solve it, we'll use decision TSP oracle which answers *is there a cycle that passes through all vertices of length $\leq k$.* It is $\mathsf{NP}$-complete.

Algorithm works as follows:

1. Choose some starting number $p$. We can use greedy solution for this.
2. Ask TSP oracle if there is a cycle of length $p/2$.
    1. If 'no', ask if there exists a cycle of length $3p/4$.
    2. If 'yes', ask if there exists a cycle of length $p/4$.
3. Continue binary searching until length of shortest cycle is found.

Now to show that TSP optimization is also in $\mathsf{P^{coNP}}$, I'll modify algorithm. It will use now coTSP decision oracle which answers *if there is no cycle that passes through all vertices of length $\leq k$*.

Now modification of algorithm:

1. Choose some starting number $p$. We can use greedy solution for this.
2. Ask TSP oracle if there is no cycle of length $p/2$.
    1. If 'yes' (there is no cycle), ask if there exists a cycle of length $3p/4$.
    2. If 'no', ask if there exists a cycle of length $p/4$.
3. Continue binary searching until length of shortest cycle is found.

So, this shows that $\mathsf{P^{NP}=P^{coNP}}$ (because equality between functional classes implies equality between decision classes).

Edit: confused path and cycle.

---
Tags: complexity-theory, oracle-machines
---


# Question
Title: Proof of bucket sort worst case being all elements in one bucket
By bucket sort I mean on dividing numbers between 0 and 1 into $n$ buckets and performing insertion sort on all the buckets.

```
1| n ← length [A]
2| For i = 1 to n do
3|     Insert A[i] into list B[nA[i]]
4| For i = 0 to n-1 do
5|     Sort list B with Insertion sort
6| Concatenate the lists B[0], B[1], . . B[n-1] together in order.

```

The time taking task is lines 4 and 5, which on uniform distribution takes $\Theta(n)$ time. So the worst case, by intuition, I can say is $\Theta(n^2)$ when all the elements fall into one bucket (standard insertion sort on $n$ elements).

But how can I prove that the worst case for this algorithm is when I take all elements in one bucket? Bucket sort worst case stuff I've seen online directly say that the worst case is when we have all elements in that one bucket. But how can I prove this in the first place? Thanks!

# Answer
For an *upper* bound on the worst-case cost, it's sufficient to show that it can't be worse. Assuming that insertion sort takes $\leq cn^2$ steps on $n$ elements, consider the sum

$\qquad\displaystyle \sum\_{i=1}^n c |B\_i|^2$;

it is an upper bound on the cost of sorting all the buckets. For an upper bound on the worst case for bucket sort, maximize this function subject to $\sum |B\_i| = n$ (and add the remaining cost, which is $O(n)$ for all inputs).

For a *lower* bound on the worst-case cost, we have to find an infinite class of actual inputs and show that their cost behaves as claimed. $\[0, \dots, 0\]$ serves to show an $\Omega(n^2)$ lower bound, as you note.
> 1 votes

---
Tags: algorithm-analysis, runtime-analysis, sorting
---


# Question
Title: Given $g(n) = \omega(f(n))$, then $g(n) + f(n) = \Omega(g(n))$?
I have a proof but I don't know if the assumptions I did are correct.

I know that $g(n)$ dominates $f(n)$, since $g(n) = \omega(f(n))$ and I did the assumption that $g(n) + f(n) = g(n)$. So, by reflexivity, $g(n) = \Omega (g(n))$.

Is this correct?

# Answer
There is a simpler proof. Assuming (as is usually the case) that $f$ is non-negative, we get $g(n) + f(n) \geq g(n)$, which implies that $g(n) + f(n) = \Omega(g(n))$. There is no need to assume anything.

If we know that $g(n) = \Omega(f(n))$, we can conclude further than $g(n) + f(n) = \Theta(g(n))$. And if $g(n) = \omega(f(n))$ then $g(n) + f(n) \sim g(n)$.
> 1 votes

---
Tags: asymptotics
---


# Question
Title: What is the tightest asymptotic bound for this recurrence?
$$T(n) = T\left(\frac{n}{2}\right) + T\left(\frac{n}{4}\right) + T\left(\frac{n}{8}\right) + n$$

How do you solve this recurrence?

# Answer
It will be $\Theta(n)$, to save myself from rewriting an entire answer, I will refer you to this question and you can apply the answer to your question.
> 1 votes

# Answer
Because in each recurrence you are cutting $n$ by half you will have at most $log(n)$ calls, if you use memorization, memorization will make your code faster because you will avoid overlapping calls, because $T(n/4) = T(n/2/2)$.

If $n$ is small number and you can use normall array for storing the values the complexity will be $O(\log n)$, but if n is big (up to $10^{18}$) then you can optimaze by using some data structures (map in c++) to make the complexity $O((\log n)^2)$
> 0 votes

---
Tags: time-complexity, recurrence-relation
---


# Question
Title: Linear Temporal Logic with non-Boolean propositions (e.g. Integers)?
LTL works with *Boolean* propositions. People probably studied extensions to non-Boolean propositions... *Do you know a good starting reference?*

(I am aware of STL, but it also seems to talk about clocks, is there a variant without clocks?)

**Update**: the question is not about "true, false, maybe" but rather about LTL where we can refer to integers, for example. Example: one might want to write `G(i+1 == X(i))`, meaning that value `i` should increment.

# Answer
> 0 votes
Here are some references you might find useful.

# Answer
> 5 votes
There has been some relatively recent work on constructive/intuitionistic variants or interpretations of LTL.

Kojima's and Igarashi's Constructive Linear-Time Temporal Logic: Proof Systems and Kripke Semantics is a decent place to start and references a bit of earlier work. In particular, Maier's Intuitionistic LTL and a New Characterization of Safety and Liveness. More recently, there was Jeffrey's LTL types FRP which showed that proofs of (constructive) LTL formulas corresponded to some FRP (Functional Reactive Programming) programs. Logics with tighter connections were formulated in later work, but this prompted some other work. One recent paper working in a linear logic setting shows a Curry-Howard correspondence between a LTL and event-driven programming: Paykin's, Krishnaswami's, and Zdancewic's The Essence of Event-Driven Programming.

At the level of logic, intuitionistic logic corresponds to having a Heyting algebra of truth values as opposed to a Boolean algebra. In a slightly different vein, Robust Linear Temporal Logic by Tabuada and Neider illustrates a many-valued (5-valued particularly) semantics for a LTL. They don't explore a proof theory except demonstrating that their rLTL can be translated to LTL.

While I didn't mention any, there is undoubtedly work in category theory that relates and would provide another perspective and categorical semantics. E.g. and related to the work above Jeltsch's Towards a Common Categorical Semantics for Linear-Time Temporal Logic and Functional Reactive Programming.

# Answer
> 1 votes
You might be interested in three-valued logic. You can find research papers on three-valued semantics for LTL and versions of LTL for three-valued logic.

---
Tags: reference-request, logic, linear-temporal-logic
---


# Question
Title: Generating many graphs satisfying some properties
Suppose I want to generate all graphs satisfying some properties (specifically 2-connected graphs on 30 vertices with degree sequence $(4, 4, 3, 3,3, \dotsc, 3)$). Unfortunately, there are an enormous number of such graphs. Probably the fastest way to find all of them would to use nauty, but it is too slow.

Is there a way to just generate many such graphs (i.e., not needing a complete list)?

There isn't an obvious way to get nauty to output just the first 10 million graphs, for instance. Maybe this isn't even possible, I don't know how nauty works.

# Answer
There are methods for randomly sampling graphs with a given degree sequence. You could try sampling and post-selecting for 2-connectedness, since that test is essentially a DFS. See for example

Efficient and Exact Sampling of Simple Graphs with Given Arbitrary Degree Sequence
> 2 votes

# Answer
Maybe SageMath can help you with this. Not sure how performance will compare to nauty.

For example, to generate 10 biconnected graphs on 8 vertices with degree sequence `[4,4,3,3,3,3,3,3]` you can use

```
sage: deg_seq=[4,4]+[3 for i in range(6)]
sage: graph_gen=graphs(8,degree_sequence=deg_seq)
sage: for i,g in enumerate(graph_gen):
....:     if i==10:
....:         break
....:     if g.is_biconnected():
....:         # do something with g

```

See documentation for details.

Also, SageMath has a nauty interface, maybe you can use it there to generate the graphs. Reading on how to use `geng` can be useful, however not so sure about how to restrict the degree sequence directly. Perhaps you can get help through their mailing list?

---

Update: `property` is ignored when `degree_sequence` is provided to `graphs`.
> 1 votes

---
Tags: graphs
---


# Question
Title: How many bits needed to describe completely random function?
I read this sentence on mit.ocw and don't understand why this completely random function would need $|U|\log n$ bits to be described?

> Unfortunately, if we choose a hash function h that happens to be a completely random function from U to \[n\], we would actually need $|U|\log n$ bits to describe it.

# Answer
> 2 votes
The word random is misplaced here, the question is how many bits are required to describe a function from $U$ to $\\{1,...,n\\}$. The connection to randomness here is simply the fact that you need to deal with an arbitrary function (since you pick one uniformly at random). Thus, you cannot rely on any structure of the function, which could allow a more compact description (e.g. a constant function would require only $\log n$ bits to describe).

One way to look at it, is saying that you need to specify the output for every possible input. Since there are $|U|$ possible inputs, and specifying an element in the range requires $\log n$ bits, this results in a $|U|\log n$ length description. You can also use the fact that there are $n^{|U|}$ different functions from $U$ to $\[n\]$, so you need $\log n^{|U|}=|U|\log n$ bits to index an element in this set.

---
Tags: random-number-generator
---


# Question
Title: How to prove T Z = Z for binary representation of natural numbers in Coq
I have defined an Inductive in Coq for binary representation of natural numbers as follows:

```
Inductive bin : Type :=
  | Z : bin
  | T : bin -> bin
  | M : bin -> bin.

```

and two recursive functions to convert between nat and bin types as:

```
Fixpoint nat_to_bin (n : nat) : bin :=
  match n with
    | O => Z
    | S n' => incr (nat_to_bin n')
  end.

```

and

```
Fixpoint bin_to_nat (b : bin) : nat :=
  match b with
    | Z => O
    | M b' => S (mult 2 (bin_to_nat b'))
    | T b' => mult 2 (bin_to_nat b')
  end.

```

to show that bin\_to\_nat is the inverse of nat\_to\_bin I need to prove that `T Z = Z` by using these tactics that I know: `simpl reflexivity destruct rewrite replace induction` please recommend some clues showing how to do this. Thank you!

**Edit**

The incr implementation is

```
Fixpoint incr (b : bin) : bin :=
  match b with
    | Z => M Z
    | T b' => M b'
    | M b' => T (incr b')
  end.

```

# Answer
> to show that `bin_to_nat` is the inverse of `nat_to_bin` I need to prove that `T Z = Z`

No, you can't prove that `T Z = Z` because it is false:

```
Lemma TZ_neq_Z : T Z <> Z.
Proof.
  discriminate.
Qed.

```

Indeed, distinct constructors of an inductive type always lead to distinct terms.

That doesn't mean you can't prove that `bin_to_nat` is the inverse of `nat_to_bin` though.
> 5 votes

---
Tags: coq
---


# Question
Title: What is the meaning of 'moderately exponential' running time?
I was reading some research paper where for hypergraph of bounded rank $k$ they have given moderately exponential algorithm. The runtime of the algorithm is $e^{ \mathcal {O}(k^2\sqrt n) \cdot poly(n)}$. Here $k$ is the rank of the hypergraph, and $poly(n)$ means polynomial in variable $n$.

> What is the meaning of *moderately exponential* running time ?

I have seen this link, but did not understand much.

# Answer
> 1 votes
*Moderately exponential* is not a widely accepted term in general theoretical computer science, though it might have a widely accepted meaning in the area to which the paper you are citing belongs.

From context, it seems that the meaning here is $\exp O(n^\alpha)$ for $\alpha \< 1$; an exponential running time would be $\exp O(n)$ or worse.

# Answer
> 2 votes
As others have mentioned, there is no precise definition. The term is often used in the field of *exact exponential-time algorithms*. Here, an exponential-time algorithm that is faster than the naive algorithm can be said to be moderately exponential.

For example, the naive exponential-time algorithm for finding a maximum independent set in a graph tries all possibilities and runs in $O^\*(2^n)$ time. Thus, any (exponential-time) algorithm that runs in $O^\*(c^n)$ time for any $c \< 2$ can be said to be moderately exponential.

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


# Question
Title: How does one generate all the terms of a multivariate polynomial algorithmically?
I was interested in writing a program that given the number of variables and the degree of the multivariate polynomial, it was able to output the multivariate polynomial itself or evaluate it at a specific point (in reality I will feed it vectors with a value for each polynomial and I want to evaluate the polynomial). So here is an example input output in pseudocode:

```
f(variables=[x1,x2],Degree=D) = 1+x1+x2+x1x2+x1^2+x2^2

```

when there is a general number of variables and Degree it gets tricky.

I noticed that this problem is equivalent to considering tuples/sequences with that satisfy the following:

$$ S\_D = \\{ (d\_0, ..., d\_N) : \sum^N\_{i=0} d\_i = D \\}$$

then my answer would be the set:

$$ S^{\*}\_D = \cup^D\_{d'=0} S\_{d'} = \\{ (d\_0, ..., d\_N) : \sum^N\_{i=0} d\_i \leq D \\} $$

I started with an example to try to actually compute that set, say degree 3 and 3 variables. I considered N = 3 and got the tuples:

* (3,0,0), (0,3,0), (0,0,3)
* (2,1,0), (2,0,1)
* (0,2,1), (1,2,0)
* (0,1,2), (1,0,2)

I also tried higher numbers but I didn't really see an obvious way to generalize it wrt to N or D. Any hints on how to do it? (Also the full solution is welcome so I can implement it for my real task)

# Answer
You can generate all non-negative integer solutions to $d\_0 + \cdots + d\_N \leq D$ recursively. The recursion is as follows:

1. If $N = 1$, generate $0,1,\ldots,D$.
2. Otherwise, for each $d\_N \in \\{0,1,\ldots,D\\}$, generate all solutions for $N:=N-1$ and $D:=D-d\_N$, and append $d\_N$ to all of them.

If you don't like recursion, you can also implement this iteratively. Start with the zero solution, and repeatedly try to "increment" it. To increment a solution, find the largest $i$ such that $d\_0 + \cdots + d\_i \< D$ (if any; otherwise, you're done), increment $d\_i$, and set $d\_{i+1} = \cdots = d\_N = 0$. This generates all solutions in lexicographic order.

As an optimization, you can store and update the running sums $s\_i = d\_0 + \cdots + d\_i$ to speed up the procedure. This optimization should make the increment routine run in amortized $O(1)$ time.
> 1 votes

---
Tags: algorithms, combinatorics, polynomials
---


title: Quantum Computing Superposition

text:
# Question
Title: Quantum Computing Superposition
**Disclaimer:**
By asking this question i'm assuming that "memory" on a quantum computer works similarly compared to a regular computer in the sense that you can store information deterministically and when needed, retrieve it in the same way.
I'm also assuming that *n* qubit has 2^*n* "states" that can be set/read independently/concurrently

---

**Question:**

Let's suppose that in a 3 qubits quantum machine, at a certain point in time, after a bunch of other operations, I have set my 3 qBit to "111". In another words, those 3 qubits have a state that says "111" and other 7 states of irrelevant information.
At a later moment, given the superposition effect, how does one guarantee that reading those 3 men addrs will yield me my "111"s? In another words, how can I be sure that I'm reading the state that i set previously?

# Answer
> 1 votes
Your assumptions are wrong, and I suggest picking up a textbook on quantum computing.

The state of $n$ qubits can be described by $2^n$ complex numbers $\varphi\_x$ whose squared magnitudes sum to 1. You can think of these $2^n$ complex numbers as indexed by $\\{0,1\\}^n$. When you "read" the $i$th qubit (the technical term is "measure"), what happens is that with probability $p\_b := \sum\_{x\colon x\_i=b} |\varphi\_x|^2$ you see the value $b$. Moreover, from now on the value of this qubit will *always* be $b$ (unless you apply quantum operations to it). The rest of the state is updated accordingly: $\varphi\_x := 0$ if $x\_i \neq b$ and $\varphi\_x := \varphi\_x/\sqrt{p\_b}$ if $x\_i = b$.

---
Tags: quantum-computing
---


# Question
Title: Show that problem of Shortest-Path in digraph is in NL
Look at solution to exercise 2, please.
Exercise and solution is derieved from: https://people.eecs.berkeley.edu/~luca/cs172-07/solutions/sol8.pdf

> $$ShortestPath = \\{(G, k, s, t)| \text{the shortest path from $s$ to \> $t$ in $G$ has length $k$}\\}$$ (a) Prove that $ShortestPath$ is in $NL$.
>
> (a) Solution: We construct a $NL$-machine for ShortestPath as follows: on input $\langle G, k, s, t\rangle$, first compute $r\_{k−1}$ (the number of vertices reachable from $s$ in at most $k − 1$ steps). Then, on input $\langle G = (V, E), k, s, t\rangle$ and $r\_{k−1}$ on the work tape,
>
> ```
> d ← 0
> flag ← FALSE
> for all w ∈ V do
> p ← s
> for i ← 1 to k − 1 do
> non-deterministically pick a neighbor q of p
> if p = w then
> d ← d + 1
> if w = t reject
> if w is a neighbor of t then
> flag ← TRUE
> if d < r_{k−1} reject
> if flag then accept else reject
>
> ```

I don't know why it is so complex.
Tell me please, why direct and simple algorithm is not ok:
Check if there exists path from $s$ to $t$ of length $1$
Check if there exists path from $s$ to $t$ of length $2$
...
Check if there exists path from $s$ to $t$ of length $k-1$
If there exists path of length $\le k -1 $ then reject. Else check if exists length of $k$ and accept if exists.

In other words we check one be one each length. We can check existence of path thanks to non-determinism. We launch number of visited nodes and check if we end up in $t$

# Answer
The difficulty here is how to check using non-deterministic logarithmic space that there is no path from $s$ to $t$ of some length $\ell$. We cannot just go over all possible paths of length $\ell$ since in order to do this we will need to "remember" $\ell$ vertices, whereas we are only allowed to remember $O(1)$ vertices (since each vertex takes up $\Theta(\log n)$ space).

If we want to check that there *exists* a path of length $\ell$, we can simply guess the path vertex-by-vertex and check that it leads from $s$ to $t$; this only requires counting up to $\ell$, which takes logarithmic space (since we're only interested in $\ell \< n$). But it's not so clear how to check that there *doesn't* exist a path of length $\ell$ – what would be a witness for that?

The solution is to use the technique of *inductive counting*, invented for the proof of the Immerman–Szelepcsényi theorem, which states that NL=coNL. This is what the solution uses.
> 1 votes

---
Tags: complexity-theory
---


# Question
Title: Probability of k-connectedness for a random graph with given degree sequence
For a degree sequence $(d\_1,\ldots, d\_n)$ with $\min d\_i \geq k$ pick a graph with that degree sequence uniformly at random. What's the probability that the graph is k-connected?

I know that for Erdos-Renyi graphs the k-connectivity threshold coincides with with the appearance of degree k vertices, but that doesn't say much about the probability when we only know that the minimum degree is $k$.

This question is related to this question. I'd like to estimate how many graphs you need to sample before picking a biconnected graph.

# Answer
The answer probably mildly depends on how wild the $d\_i$ are. A random $k$-regular graph is $k$-connected whp for $3 \leq k \leq n-4$ according to slides by Wormald (page 12), so I would expect that if, say, $k \leq d\_i \leq \ell$ for constants $k,\ell$ (or even $\ell$ growing mildly with $n$) then the graph is still $k$-connected whp. The proof shouldn't be difficult (for constant $\ell$) using the configuration model.

A 1-regular graph is never connected (for $n \> 2$), and a random 2-regular graph is, if I remember correctly, disconnected whp. If you only have a few degree 2 vertices then perhaps the graph is 2-connected whp – that would be my guess.
> 2 votes

---
Tags: graphs, probability-theory
---


title: Composing $L$ and $NL$

text:
# Question
Title: Composing $L$ and $NL$
Let $A$ be a problem. I would like to solve $A$ in $NL$. So, I am trying to construct Turing machine working in $NL$:

Let $w$ be a input of length $n$. Firstly, we run machine $M\_1$ that working in $LOGSPACE$. It produces a output $o$ of length $P(n)$ where $P$ is a polynomial. Secondly, a machine $M\_2$ working in $NL$ reads the output $o$ written by $M\_1$.

Does t work in $NL$? Why?

P.S. If machine $M\_2$ worked in $L$ it would be obvious that problem is solvable in $L$. But, I am not sure if that algorithm solves $A$ in $NL$.

# Answer
> 2 votes
$M\_2$, while running on $w$, calls $M\_1(w)$ as a subroutine. So if $M\_1(w)$'s output is stored on $M\_2$'s working tape then it requires polynomial space, not logarithmic space. So, $M\_2$ does not work in logarithmic space no matter it is deterministic or nondeterministic.

Of course you could design your machine $M\_2$ so that $M\_1(w,i)$ would return $i$th bit on demand (on each call). In this case it would work in logarithmic space. But it depends on the problem you solve.

---
Tags: complexity-theory
---


# Question
Title: Efficient way to choose set from including conditions on sets
Let $m, n \in \mathbb{N}$ and $n \le m$. Given $k$ subsets $X\_1, X\_2, \dots, X\_k$ of $\\{ 1, 2, \dots, m \\}$ and $k$ nonnegative integers $a\_1, a\_2, \dots, a\_k$, find all subsets $Y$ of $\\{ 1, 2, \dots, m \\}$ satisfying the following conditions:

* The set $Y$ contains exactly $n$ elements: $|Y| = n$
* The set $X\_i$ has exactly $a\_i$ elements with $Y$ in common: $\forall 1 \le i \le k: |X\_i \cap Y| = a\_i$

**EXAMPLE.** Let $m = 5$, $n = 2$. We are given the following conditions. Set $Y$ contains...

* 1 element out of $\\{ 2, 3, 4, 5 \\}$, $\quad$ ($a\_1 = 1$)
* 2 elements out of $\\{ 1, 2, 3, 4 \\}$, $\quad$ ($a\_2 = 2$)
* 1 element out of $\\{ 1, 3, 4, 5 \\}$. $\quad$ ($a\_3 = 1$)

$Y = \\{ 1, 2 \\}$ is a unique solution. It is necessary to have $1 \in Y$, else we must select two elements of $\\{ 2, 3, 4 \\}$ (2nd set without $1$), which is a subset of the 1st set. Now consider the 3rd set. If we select $3, 4$ or $5$ instead of $2$, $Y$ would contain two elements from 3rd set.

Of course, there may be many solutions, up to $\binom{m}{n}$ to be specific.

**QUESTIONS.** I have the following two questions:

* Are there any algorithms better than trivial brute-force to find all solutions to an instance of this problem? Do these algorithms fulfill known lower bounds?
* Given that there exists a unique solution, can we use this extra knowledge to do better than in the general case in terms of time complexity?

**MY APPROACHES.** Obviously, it is possible to enumerate all $\binom{m}{n}$ subsets and check the conditions. At least for the last step (I know, the first step causes the lack of efficiency) I can think of some improvements. First, we may represent the sets as boolean arrays of size $m$. When iterating over the possible solutions, we may compute $X\_i \cap Y$ in time $\mathcal{O}(m)$ resulting in an $\mathcal{O}\left(m\binom{m}{n}\right)$ solution. Additionally, if there is a set $X\_i$ with $|X\_i| = a\_i$ we are lucky. In this case, we know $X\_i \subseteq Y$ and may erase all elements of $X\_i$ in the other subsets $X\_j$ replacing $a\_j$ by $a\_j - |X\_i \cap X\_j|$. But in general, this special case does not occur with certainty.

I would appreciate any kind of help and material.

# Answer
> 1 votes
I think it should be straightforward to reduce One-in-3SAT to this problem: For example, you can create a size-2 set $X\_i$ for each variable $x\_i$ from the One-in-3SAT instance, and set $a\_i=1$ to force that either the variable or its negation is chosen. $n$ will be the number of variables, and you will need additional sets $X\_j$ for each clause, with $a\_j=1$ (reflecting the constraint that exactly 1 literal in each clause be positive).

Showing this reduction would show that the problem is NP-hard, indicating that a polynomial-time solution is very unlikely.

---
Tags: algorithms, algorithm-analysis, sets
---


# Question
Title: Polynomially many times launch $NL$ machine - is it in $NL$? On example of ACYCLIC
Lets consider $$ACYCLIC = \\{\langle G \rangle | G \text{ is acyclic}\\}$$
We are going to prove that $ACYCLIC\in NL$. I know that the easiest approach for this task is to use the fact that $coNL=NL$. However, I wonder if correct answer is following approach:

The idea is to check each existence of each length of cycle. Let $n$ will be number of cycles.

```
    for l = 1..n
       is_cycle = non-deterministally check if there exists cycle of length l
       if (is_cycle == "yes")
          then return "no"
    return "yes"// graph is acyclic because there is no cycle of length 1..n

```

Is it correct approach in $NL$?

# Answer
You cannot implement this part in NL:

> nondeterministically check something
>
> if yes, return no

Consider the following analogy: the language $K$ of all Turing machines that halt is recursively enumerable but its negation isn't. That is, $K$ is accepted by some nondeterministic Turing machine, but its negation cannot be accepted by any nondeterministic Turing machine. This means that you *provably* cannot implement the following using nondeterminism:

> nondeterministically check if the given Turing machine halts
>
> if yes, return no

Your idea suffers from the same problem.

---

Here is a different angle. The following algorithm checks nondeterministically that $s$ and $t$ are connected:

> guess a path $w$ from $s$ to $t$
>
> verify that $w$ is a path; if so, output yes, otherwise, output no

The semantics of this algorithm are as follows:

1. If there is some witness that causes the algorithm to output yes, then the input is a yes input.
2. If all witnesses cause the algorithm to output no, then the input is a no input.

What you are trying to do is as follows:

> guess a path $w$ from $s$ to $t$
>
> verify that $w$ is a path; if so, output no, otherwise, output yes

All inputs are yes instances in this case, since there is always some witness $w$ that *isn't* a path from $s$ to $t$.

In order to check that there is no path, you would have to do the following:

> go over all possible paths $w$ from $s$ to $t$
>
> if none of them works, output yes, otherwise, output no

Unfortunately, this doesn't describe a nondeterministic Turing machine.
> 1 votes

---
Tags: complexity-theory, space-complexity
---


# Question
Title: Complexity of the algorithm to find occurences of a given number in a given array
I have an algorithm that I think its complexity is O(n^2). However, our teacher insists that the algorithm takes O(n) time. How can it be? Here is the pseudo-code of the algorithm:

```
// A is the input array.
// |A| is the size of the input array.
i = 1
j = 1
m = 0
c = 0
while i < |A| {
    if A[i] == A[j]
        c = c + 1
    j = j + 1

    if j > |A|
        if c > m
            m = c
        c = 0
        i = i + 1
        j = i
}
return m

```

# Answer
> 1 votes
If we retain only the references to `i` and `j`, the code reduces to

```
i = 1
j = 1
while i < |A|
    j = j + 1
    if j > |A|
        i = i + 1
        j = i

```

This is equivalent to

```
for i in [1 |A|]
    for j in [i |A|]

```

... which is gone through about ${|A|^2 \over 2}$ times. So it is $\Theta(n^2)$: both $O(n^2)$ and $\Omega(n^2)$.

The algorithm appears to be looking for the maximum number of replicates in the array. There are faster ways to do so. A good hash map has (average) constant time access/update. So you can count how many of each thing are in the array in $\Theta(n)$ time. You can then find the maximum in $\Theta(n)$ time too.

So the problem admits a $\Theta(n)$ solution, but what you have been offered isn't it.

# Answer
> 0 votes
Here's the heading of your question :

> Complexity of the algorithm to find occurences of **a given number** in a given array

Your algorithm finds multiple occurrences of ***all elements*** of the given array within itself which takes $O(n^2)$ time because $n$ elements are to be compared and each element needs $n-1$ comparisons.

But finding the multiple occurrences of **a** **given** **number** in an array will take only $O(n)$ time as we will have to compare only $1$ given number with $n$ elements of the given array i.e. $n$ times.

I guess you are talking about the complexity of **your algorithm**(which does more work than needed) but the teacher is telling you about the complexity of going through the array and **comparing each number in the array** with **the given number**.

---
Tags: algorithm-analysis, runtime-analysis, loops
---


title: Monte Carlo algorithm: Element in array

text:
# Question
Title: Monte Carlo algorithm: Element in array
> Design a Monte Carlo algorithm that checks in constant time if a given element $x$ is in a $n$-dimensional vector $V$. Calculate the probability for a correct answer. Then suppose $n=10$, how many times the algorithm must be executed so the probability for a correct answer is greater than $0.9$?

Thats what I tried. Lets pick an arbitrary index $i$ which make sense in $V$, then check if $x=V\[i\]$ and return true or false as the equality holds or not.

My doubt comes at the time of calculating the probability of a correct answer as the statement gives no more details. Is it even numerically doable without additional asumptions?

I guess the probability of $x\in V$ once $x\not=V\[i\]$ is $$p=p\_1+p\_2+\dots+p\_{n-1}$$ (following law of total probability) being $p\_j$ the probability of $V$ having $j$ times the element $x$. But this probabilities are unknown. Or $$p=1-p'$$ being $p'$ the probability of $V$ not having $x$ as an element (also unknown).

Am I forced to suppose $V$ is a vector of elements of a certain finite set $X$ of $m$ elements or something similar?

# Answer
It doesn't matter what other elements are. We can assume that $k$ elements in $V$ are equal to $x$. Then the probability for a correct answer would be $k/n$ and $1-k/n$ for an incorrect answer. Then after $m$ tries, the probability of failure would be $(1-\frac{k}{n})^m$. And the probability of success in $m$ tries is the probability of not to be failed in every try, which is $1-(1-\frac{k}{n})^m$.
> 2 votes

# Answer
Your vector has n entries. If x is in the vector, then finding it when you pick a random index has probability at least 1/n (higher if there are multiple copies of x).
> 1 votes

---
Tags: monte-carlo
---


# Question
Title: Does the existence of the universe mean Chaitin's number is more than half?
This may be too philosophical for this stackexchange.

Chaitin's constant $\Omega$ is the probability that a bitstring will halt when run on a universal Turing machine. It is uncomputable due to the halting problem.

My thought is that if $\Omega\<\frac{1}{2}$ then most likely nothing would exist. So, since something does exist, it is most likely that $\Omega \geq \frac{1}{2}$.

Is this reasoning valid?

# Answer
No, your reasoning is invalid. Chaitin's constant depends on the choice of a universal Turing machine, and by appropriately choosing the universal Turing machine, we can fix the first $n$ bits of Chaitin's constant to be whatever we want, for any fixed $n$.

---

One reason to suspect your reasoning is that the actual argument is missing. Your argument can be paraphrased as follows:

1. $\Omega$ is the probability of something.
2. If $\Omega \< 1/2$ then something counterfactual.
3. Hence I suspect that $\Omega \geq 1/2$.

The problematic step here is Step 2. What does $\Omega$ have to do with existence?
> 7 votes

---
Tags: halting-problem
---


# Question
Title: Probabilistic analysis of finding 2nd largest value in vector
Given the following algorithm for finding the second largest element in a vector:

`2ndMAX(v):
 n = length of v
 largest = 0
 second_largest = 0
 for i in 1 to n:
 if v[i] > largest:
 second_largest = largest
 largest = v[i]:
 else if v[i] > second_largest:
 second_largest = v[i]
 return second_largest`

How many assignments is the algorithm expected to make to `second_largest`?

I can see the asymptotic lower and upper bounds on the problem, but how can I approach this probabilistically and give the expected number of assignments?

For the maximum I suppose it is N/2 assignments; but for the 2nd largest I am getting confused. I am trying to divide the cases in: largest comes before second largest, so there are no more assignments past the second largest, but there may be before the largest and between the largest and second largest. But it gets complicated really quickly. I also tried some inductive analysis but couldn't get too far.

# Answer
Let's assume for simplicity that $v$ is a random permutation of the numbers $1,\ldots,n$. In step $i$, `largest` is assigned to if $v\_i$ is the maximal element among $v\_1,\ldots,v\_i$ (a "record"), and `second_largest` is assigned to if $v\_i$ is the second maximal element among $v\_1,\ldots,v\_i$. The probability of each of these events is $1/i$ (the second, assuming that $i \geq 2$), since $v\_1,\ldots,v\_i$ is a random permutation of $\\{1,\ldots,i\\}$.

Linearity of expectation shows that the expected number of times that `largest` is assigned to is $$ \sum\_{i=1}^n \frac{1}{i} = H\_n = \log n + \gamma + O\left(\frac{1}{n}\right). $$ Similarly, the expected number of times that `second_largest` is assigned to is $$ \sum\_{i=2}^n \frac{1}{i} = H\_n - 1 = \log n + \gamma - 1 + O\left(\frac{1}{n}\right). $$ In both formulas, $H\_n$ is the $n$th harmonic number, $\log$ is the natural logarithm, and $\gamma$ is Euler's constant.
> 3 votes

---
Tags: algorithm-analysis, probability-theory
---


# Question
Title: Can the formalisms of category theory replace those of type theory?
The subtleties of the correspondence between type theory and category theory are outside my ken. However, by my naive understanding of the relationship between the two historically convergent disciplines, the latter entirely subsumes the former. If this is so, can the language and formal/graphical descriptions used by category theorists replace those of type theorists? And should they (e.g., in pedagogy and academic publishing)?

Different formalisms can inspire novel perspectives and lay bare conceptual connections that might otherwise be obscure. However, a multiplicity of dialects probably also limits the size of a receptive audience, and, should a polyglot approach be taken, the length and complexity of exposition is compounded.

If category theory does subsume type theory, should the dialectical differences of the two disciplines be retained, and if so, why? For the sake of historical or cultural value? To retain different but salient differences of instructional or theoretical emphasis? What might these be?

# Answer
Since you say that "the subtleties of the correspondence between type theory and category theory are outside your ken", perhaps the best way to understand the correspondence is to read non-technical expositions on the topic. I can recommend two:

1. Steve Awodey, From Sets to Types, to Categories, to Sets, In: Sommaruga G. (eds) Foundational Theories of Classical and Constructive Mathematics. The Western Ontario Series in Philosophy of Science, vol 76. Springer, Dordrecht (free preprint here)
2. Robert Harper's blog post The Holy Trinity, and also see these slides.

I suppose, the lesson to take away is that each approach has something to offer and that they work best together, and not so much if you try to replace or subsume one with the other.
> 9 votes

# Answer
My view is more or less similar to chi's. I see category theory as (roughly) being to type theory what model theory is to logic. Some of the consequences of that are, first, each can exist autonomously. Indeed, type theory predates category theory, and the creation of category theory was not motivated by these concerns. Second, many of the distinctions category theory/model theory are purposely trying to blur are of primary interest in type theory/logic.

As a very basic example, all presentations of the axioms of a group give rise to the same class of models (namely groups). From the perspective of universal algebra, a variety (in the universal algebra sense, or a finitary algebraic category from a CT perspective) forgets its presentation. Meanwhile, from the perspective of equational logic, presentation is all there is. A primary computational topic here is E-unification which operates entirely at the level of equational logic, i.e. presentation.

This is typical. We say the simply typed lambda calculus (with products) (STLC) is the internal language of Cartesian closed categories, but it is really just one presentation of the internal language and not even the most "direct" one. The Categorical Abstract Machine (CAM) is arguably a more "direct" representation. Even with the STLC, the arrows of corresponding syntactic category are $\beta\eta$-equivalence classes of lambda terms! (But see this.) So either we somehow directly describe the syntactic category as a mathematical structure whose hom-sets just happen to coincide with $\beta\eta$-equivalance classes of STLC terms and have *no computational content*, or we need to already understand the STLC external to category theory, or we need to talk instead of *presentations* of Cartesian closed categories which, taking a fairly natural approach, will lead to something CAM-like. In the last case, equality of arrows becomes something like an E-unification problem. Understanding and simplifying this process as well as placing the more ergonomic facade of the STLC in front of it, requires techniques that are the bread and butter of logic and type theory but are not particularly natural within category theory.

A massively over-simplified picture that may nevertheless give a better idea of how category theory and type theory interrelate is the following. You can imagine them as two dimensions. The tools, techniques, and notations of type theory are geared toward moving vertically between different presentations of the same object, meanwhile the tools, techniques, and notations of category theory and geared toward moving horizontally between different mathematical objects. You might even say that a category is a whole vertical line and that category theory talks about moving one vertical line to another but not how the points of the two lines correspond. In this picture, category theory is not even *capable* of talking about the distinctions type theory is making, but this is intentional because it means that the arbitrarily complicated mapping of points on one vertical line to points on another is just irrelevant to what category theory cares about and can be ignored.

In my blog post, Category Theory, Syntactically, I describe an approach that makes category theory look more like type theory (rather than the other way around). Unsurprisingly, what I'm really discussing there are presentations of categories. Further, you can see aspects of normalization enter the picture, e.g. in my discussion of "product theories", even though this is not a focus at all of that particular post.
> 9 votes

---
Tags: type-theory, category-theory
---


# Question
Title: Theory of Turing machine which outputs Turing machine?
I understand the notion of the universal Turing machine ($U$), which receives a pair of Turing machine ($M$) and an input to $M$ ($x$). If $M$, which obtains $x$, outputs $y$, $U$, which obtains $(M, x)$, outputs $y$ as follows:

$M: x \mapsto y \\ U: (M, x) \mapsto y$

My question is whether there is a theory of another type of Turing machine where the output (not input) of Turing machine is another Turing machine like:

$U': x' \mapsto M$

I guess a program which generates another program can be regarded as this kind of Turing machine $U'$. If so, automatic code generator and machine learning algorithm might be regarded as this type of Turing machine.

(Maybe, brains of human programmers can be modeled using a theory of such Turing machines because a source code seems a form of Turing machine.)

# Answer
It depends on what your are referring as "theory" (which basically means everything or anything).

Something which is closely related to what you are referring can be the field of **Program transformations**, which tries to study systematically programs that modifies other programs. The original interest of this field is the transformers that are semantically invariants (with a bit of hand waving: you want to study transformers $T$ such that for any program (or a TM) $p$, $T(p)$ *does the same thing* as $p$). Derives from these original considerations the subfield of **program synthesis** (here, given some input datas, you want to automatically generate a program that satisfies some conditions encoded by you input).

A good introduction can be the thesis of M. Ward *"Proving Program Refinements and Transformations"* with an emphasis on the proof of program side.
> 2 votes

---
Tags: turing-machines, computation-models
---