# Question
Title: Is this an example of a natural, strictly NP-intermediate language (assuming EXP ≠ NEXP)?
In the wikipedia page for the NP-intermediate complexity class, the following observation is made:

> Under the assumption that P ≠ NP, Ladner explicitly constructs a problem in NPI, although this problem is artificial and otherwise uninteresting. It is an open question whether any "natural" problem has the same property \[...\]

In the '80s, a work by Galperin and Widgerson was dedicated to problems on graphs with succinct circuit representations. Intuitively, a graph has a succint circuit representation if there is a polylogarithmically sized boolean circuit which takes two (padded) integers representing node numbers as input, and outputs 1 if there is an edge between those two nodes and 0 otherwise. Many NP-complete predicates of graphs were shown to be NEXP-complete when the graph is provided in its succinct form.

Now consider any particular NP-complete problem among these. The above fact can be because, aside from the input having become exponentially smaller, the following informal statement must be true:

> Call $\sigma$ the subset of instances of the original NP-complete problem that are representable by a succinct circuit. $\sigma$ turns out to not be dramatically easier to decide than its parent set; that is, $\sigma$ is not susceptible to some specialized, polynomial method leveraging some particular structural peculiarity common to all its members.

In fact, if there was a polynomial time algorithm *A* that, when applied to members of $\sigma$ (it doesn't even matter what *A* does with the other instances!), would correctly decide them, you could simply "decompress" the graph and then use *A* to decide the instance. Both of these steps take deterministic time exponential in the succinct input length. But the succinct problem is NEXP complete, so this could happen only if EXP=NEXP. This provides evidence that $\sigma$ itself is not in P unless EXP=NEXP. To decide $\sigma$, you would need to establish that the instance has a small circuit, then solve it. The first part is the MCSP problem, which for all we know could be in P. But the second part would require *A*, that as mentioned exists only if EXP=NEXP.

I wish to observe that $\sigma$ is *sparse*, by the simple fact that, asymptotically, as graph size increases linearly only logarithmically many small circuits can be proposed, and therefore only logarithmically many instances selected.

In Papadimitriou and Yannakakis this topic is tackled. They observe:

> \[...\] Also, our result can be interpreted as an elaboration on the work of Hartmanis, Sewelson, and Immerman (1983). They showed that there exist sparse sets in NP-P iff NEXP ≠ EXP. We have exhibited, essentially for any known NP-complete set, a sparse subset that is the most likely to be in NP - P exactly if NEXP ≠ EXP (namely, the members of the language that are succinctly representable by the scheme suggested in the proof).

NP-P includes both NP-complete and NP-intermediate. But, assuming P ≠ NP, $\sigma$ cannot be NP-complete by virtue of Mahaney's theorem, and therefore it must be NP-intermediate. Thus, $\sigma$ is an arguably "natural" example of a problem strictly in NPI (provided naturally that EXP≠NEXP), in contrast with the wikipedia article.

Did I make some mistake in my reasoning? Why do Papadimitriou and Yannakakis use NP-P, and why do they say that if EXP≠NEXP $\sigma$ is only "most likely" to be in NP-P, and not certainly in NP-P?

If $\sigma$ is, in fact, in NPI if NEXP ≠ EXP, why isn't this mentioned in NP-intermediate discussions? Could this really just have been overlooked?

# Answer
> 3 votes
Great observation and question! There is no contradiction, but you have to get into the details. I'll explain why below. Also, as it happens, something very similar to your example has been noted before.

# Details

I interpret Wikipedia as saying: it is an open question whether there is any natural problem $L$ with the property that, if $P \ne NP$, we can prove that $L$ is NP-intermediate.

You have shown a natural problem $\sigma$ with the property that, if $P \ne NP$ and $EXP \ne NEXP$, we can prove that $L$ is NP-intermediate.

These two statements are consistent with each other and can both be true. I don't see any contradiction between the two. As far as I am aware, we don't know of any proof that $EXP \ne NEXP$, or any proof that $P \ne NP$ implies $EXP \ne NEXP$.

# Noted before

Check out the last paragraph of Joshua Grochow's answer here. That is a very similar construction.

# On Wikipedia

As a reminder, Wikipedia is not a primary source. You shouldn't necessarily trust technical claims made on Wikipedia to be correct, unless you can verify them yourself or Wikipedia cites a primary source and you consult the primary source. My experience is that Wikipedia is generally quite reliable for statements about computer science, but is not perfect, and the statements are sometimes stated in a somewhat imprecise manner. In this case, the precise details of the statement matter. In those cases it is often worth finding a better source that gives a more precise treatment of exactly what is being claimed.

Unfortunately, the Wikipedia article doesn't give any citation for the claim it makes. However, I can offer a better source for that statement:

> "We do not know of a natural decision problem that, assuming $NP \ne P$, is proven to be in $NP \setminus P$ but not $NP$-complete, and there are remarkably few candidates for such languages."
>
> Sanjeev Arora and Boaz Barak, *Computational Complexity: A Modern Approach*, Princeton University, 2007.

I think this supports my interpretation above.

# On natural problems

One trickiness is that what counts as "natural" is inherently subjective. So, another way to understand these claims is as an empirical observation that it's rare to run across problems in everyday life that are NP-intermediate: most problems that we run across in everyday life that are in NP are either in P or are NP-complete. It is a bit of a mystery why this happens, but you can find some discussion on this point at https://cstheory.stackexchange.com/q/20930/5038.

---
Tags: graphs, np-complete, succinct-data-structures, np-intermediate
---


# Question
Title: Mathematical operation for removing duplicate rows in a matrix
I am using the GraphBLAS C API (https://graphblas.org/) which provides an interface for performing mathematical operations on sparse matrices. Given an adjacency matrix $\mathbf{A}: \mathbb{R}^{n \times n}$, I would like to remove duplicate rows from the matrix. Instead of implementing this in the standard $\mathcal{O}(n^3)$ way where each row must be checked against every subsequent row, I would like to try and take advantage of built-in mathematical operations from the API.

For instance in the matrix

$$ \begin{bmatrix} 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \end{bmatrix} $$ either the first or third row should be deleted (which one matters not).

Does anyone know of such a mathematical operation that can take $\mathbf{A}$ and multiply/divide/\<operate\> with either itself or another $n \times n$ matrix (or vector) such that duplicate rows are deleted (but one of the duplicates is kept)?

If this is off-topic, let me know and I can move over to Math SE (although they will probably tell me to bug off :)

# Answer
A more efficient approach is to hash each row, insert them into a hash table, and find duplicates in that way. The running time will be $O(n^2)$.

You can implement something like this using only linear algebra operations. In particular, pick a random column vector $v$. Multiply using your BLAS API to obtain the product $w=Av$. Now if $A\_i=A\_j$ (i.e., if the $i$th and $j$th rows of $A$ are duplicates), then you will have $w\_i=w\_j$. So, it suffices to sort the entries of $w$ (which brings all duplicates next to each other), find all duplicates, and check whether the corresponding rows of $A$ are duplicates. This basically uses a linear function as the hash function, so that you can hash all the rows efficiently using your BLAS API.

I suggest that one reasonable way to instantiate this scheme is to pick $k \ge 2\lg n$, choose $v$ so that each entry of $v$ is chosen uniformly at random from $0,1,2,\dots,2^k-1$, and perform all arithmetic modulo $2^k$. With this instantiation, you can expect very few "false alarms" (i.e., very few cases where $w\_i=w\_j$ but $A\_i\ne A\_j$). Or, you can pick $k$ in a way that is convenient, and deal with the false alarms. Or, you can replace $v$ with a $n \times 2$ or $n \times 3$ matrix, compute a matrix product, and look for duplicate rows in the resulting $n\times 2$ or $n \times 3$ matrix. There are many possibilities which you can experiment with, depending on the typical size of $n$ and the performance characteristics of your BLAS.
> 1 votes

---
Tags: graphs, matrices, linear-algebra, sparse-matrices
---


title: Time complexity of Jacobi symbol

text:
# Question
Title: Time complexity of Jacobi symbol
Here is my algorithm with inputs $a$, which is an integer and $n$, which is an odd natural. Is $\mathcal{O}(n)$ the time complexity of this algorithm?

My thoughts:

The if-cases in the lines $1$ up to $20$ and $32$ up to $37$ are checked in $\mathcal{O}(1)$.

In lines $21$ and $22$, the symbol is reduced. My guess it that this can happen at most $n$ times, so this would be $\mathcal{O}(n)$.

The remaining if-case in line $24$ divided the number $a$ by $2$ as often as possible. This is done in $\mathcal{O}(\log\_2(n))$ times.

So since $\mathcal{O}(n)$ is the dominating term here, I suppose that this is the time complexity of this algorithm.

# Answer
> 2 votes
I haven't checked carefully, but the running time is most likely $\mathcal{O}(\log \max(a,n))$ iterations, or $\mathcal{O}((\log \max(a,n)) \cdot (\log n)^2)$ bit-operations. In the special case where $a \le n$, we can describe this as $\mathcal{O}(\log n)$ iterations or $\mathcal{O}((\log n)^3)$ bit-operations. Good algorithms for evaluating the Jacobi symbol have that running time. As a quick glance at your pseudocode, it looks like the algorithm you present has that running time too.

For lines 21-22, at a first glance, it looks like those might get executed up to $n$ times, but a more careful analysis shows that this is overly pessimistic.

Suppose that the running time when $a \le n$ is $\mathcal{O}((\log n)^3)$ bit-operations. Then if you invoke it with $a \> n$, it will take $\mathcal{O}((\log a)(\log n)^2)$ time to compute $a \bmod n$, and then $\mathcal{O}((\log n)^3)$ time to compute the recursive call. The former dominates, so the total running time in this case is $\mathcal{O}((\log a)(\log n)^2)$, as claimed.

You might be concerned about how lines 21-22 and line 37 interact. However, after every 5(?) invocations, the value of $n$ is reduced by at least factor of $4/3$. $(a,n)$ becomes $(n,a)$, which becomes $(b,a)=(n \bmod a, a)$, which becomes $(a,b)$, which becomes $(c,b)=(a \bmod b, b)$, which becomes $(b,c)$, and $c \le 4n/3$. A similar thing happens with the Euclidean algorithm for computing the gcd; see standard analyses of it for more details, e.g., https://stackoverflow.com/q/3980416/781723.

I might be getting a few details wrong, so please check my reasoning carefully yourself, but I think the general gist here is probably correct.

Of course, $\mathcal{O}((\log n)^3)$ is smaller than $\mathcal{O}(n)$. So yes, you could say that the running time is $\mathcal{O}(n)$, but that would be an extremely loose and misleading upper bound on the running time.

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


# Question
Title: NP-hardness of a variation of the bin packing problem
I was wondering if a variation of the bin packing problem where the 'size' of a bin is calculated as the product of item sizes in a bin instead of their sum is NP-hard. It seems like it must be, but I don't know how to prove it.

More formally, the problem is as follows:

Given a list of positive integer item sizes $a\_1, a\_2, ..., a\_n$ and a positive integer $x$, find the smallest positive integer $k$ such that it is possible to partition the items into $k$ disjoint sets $S\_1, S\_2, ..., S\_k$ such that the product of sizes in each $S\_i$ is $\leq x$.

# Answer
> 3 votes
The bin packing problem is strongly NP-hard. That means that even if the sizes are given in unary, the problem is still NP-hard.

In your case, your product-bin packing is equivalent to sum-bin packing, using $\log a\_i$ and $\log x$ as sizes, and it is still NP-hard.

---
Tags: algorithms, reductions, np-hard
---


# Question
Title: Prove that if $L \subseteq b^*$ isn't regular then $M = a^+L \cup b^*$ isn't regular
There is an exercise in a book about finite automata that I couldn't solve:

Prove that if $L \subseteq b^\*$ isn't regular then $M = a^+L \cup b^\*$ isn't regular either, using the fact that REG is closed under inverse morphism (paraphrase).

I think one obvious approach would be to find a Language $L'$ and morhpism $\varphi$, s.t. $L' = \varphi^{-1}(M)$ and $L'$ can be transformed into $L$ using regular operations. Does someone have a hint on how to solve this exercise?

Cheers and thanks in advance

Edit: Typeset the wrong formula

# Answer
> 1 votes
Assume towards a contradiction that $M = a^+ L \cup b^\*$ is regular. Then $M' = M \cap a^\*b^\* = a^+ L$ is also regular (since it is the intersection of regular languages), and so is $a^\* \setminus M' = L$, which contradicts the fact that $L$ is not regular.

---
Tags: formal-languages, regular-languages, theory
---


# Question
Title: What is the "big theta" order of the solution of T_n = T_(n/2) + log n, n > 0?
What method(s) could be used to solve this? I am still new to this stuff and would appreciate detailed justification for every step as well as some intuition and the examination of all possible viable methods to go about this, not just one. Thanks.

# Answer
Assume for simplicity that $n$ is a power of $2$.

By unrolling $T(n) = T(n/2) + \log n$ you get: $$ \begin{align\*} \log n + \log \frac{n}{2} + \log \frac{n}{4} + \log \frac{n}{8} + \dots &= \log n + ( \log n - 1 ) + (\log n - 2) + (\log n - 2) + \dots \\ & = \sum\_{i=0}^{\log n} (\log n - i) = \sum\_{i=0}^{\log n} i=\frac{(\log n)(\log n + 1)}{2}\\ & = \Theta(\log^2 N). \end{align\*} $$

---

This even easier to see if you substitute $n = 2^k$ and define $S(k) = T(2^k)$: $$ S(k) =T(2^k) = T(2^k-1) + \log 2^k = S(k-1) +k. $$ Unrolling shows that $S(k) = \sum\_{i=1}^k i = \frac{k(k+1)}{2} = \Theta(k^2) = \Theta(\log^2 n)$.

---

Otherwise you could use the master theorem. For $a=1$, $b=2$, $k=1$, and $f(n) = \log n$ you have: $$ T(n) = a T(n/b) + f(n) $$ and $n^{\log\_a b} \cdot \log^k n = \Theta(f(n))$. Then $T(n) = n^{\log\_a b} \cdot \log^{k+1} n = 1 \cdot \log^2 n = \Theta(\log^2 n)$.
> 0 votes

---
Tags: time-complexity, asymptotics, recursion, master-theorem
---


# Question
Title: How do you compute and compare the delays between a (4:2) compressor and (3,2) counter carry save tree?
My question: How is Table 6.8 shown below computed for different operands? For example, for 3 operands how did they compute:

Number of levels using (3,2) = 1

Number of levels using (4;2) = 1

Equivalent delay: 1.5

Or how about for 9 operands how did they compute:

Number of levels using (3,2) = 4

Number of levels using (4;2) = 3

Equivalent Delay: 4.5

**The textbook also points out that the equivalent delay of a (4;2) compressor carry save tree with 9 operands (4.5) is bigger than that of a carry save tree using (3,2) counters. Why is that?**

What are the general conditions when one is bigger than the other?

The following is an image of a (4:2) compressor taken from this book.

The truth table provided for this compressor is:

where $a=b=c=1$ and $d=e=f=0$. I think these constants are used to generalize the circuit.

> An adder tree that uses (4;2) compressors will have a more regular struc-ture and may have a lower delay than an ordinary CSA tree made of (3,2) counters. Table 6.8 compares the delays of carry-save trees using either (3,2) counters or (4;2) compressors. Since the delay of a (4;2) compressor is 1.5 times that of a (3,2) counter, the number of levels of (4;2) compressors in column 3 is multiplied by 1.5 to yield the equivalent delay in column 4. **Note that the equivalent delay of a carry save tree using (4;2) compressors (column 4) is not always smaller than that of a carry save tree using (3,2) counters (column 2). For example, for nine partial products, (3,2) counters will yield a carry save tree with an overall lower delay.** Various other counters and compressors can be employed in the implementation of the addition tree for the partial product accumulation; for example, (7,3) counters

Please look at the bold face sentence above:

# Answer
* The first column list all ranges with uniform number of levels for both approaches, up to 42.
One way is to start with one level, and compute how many inputs a circuit with that many outputs accommodates - twice as many with (4;2) compressors, three halves, truncated, with (3,2) counters.
* With a simple timing model (each XOR contributes .5), this means uniform delay, too:
The number of levels with equals the unit delays for (3,2) counters, multiply with 1.5 for (4;2) compressors.

The condition for the (4;2) compressor delay to be bigger than the (3,2) counter one is:
Number of operands is 3 or 9.
It will be smaller above 19 (as well as for 4, 7, 8 and 10-16).
> 1 votes

# Answer
It took me a while to figure out what this circuit does: It takes 5 inputs and produces 3 outputs. (So why is it called a 4-2 compressor and not a 5-3 compressor?) One output is the sum with a value of 1, and two carry bits with a value of 2. If the sum of the inputs is 2 or 3, one of the two carries must be set, and one cleared; it doesn’t matter which one; this gives you the values a, b, c, d, e and f, with arbitrary values.

The number of levels for a given number of inputs is not a continuous function but has jumps, and they are in different places for both methods. So from eight to nine inputs, (4,2) needs an extra level where (3,2) doesn’t yet, and that’s why for this one point (3,2) has less delay.

I’d try to find the best implementation with NAND gates. Then it may be that some outputs are produced faster than others, and some inputs delay the total result while others don’t. Also consider that a circuit may output a negated output quicker, and another circuit might be faster if given a negated input.
> 1 votes

---
Tags: arithmetic, digital-circuits
---


# Question
Title: How many operands does the NOP instruction have?
At first I thought it is obvious, since the `NOP` instruction does not have any operand, we say it is zero-operand instruction. But then looking on the zero-operand instruction,

But looking after the definition I am confused to classify the instruction into $n$-operand category, where $n \in \\{0, 1, 2, 3\\}$ ref

> These instructions do not specify any operands or addresses. Instead, they operate on data stored in registers or memory locations implicitly defined by the instruction.

What I know so far: Based on the number of operands in the instructions (including literals) we classify the $n$-operand class.

*Update 0x00:*
Is the NOP instruction zero-operand? If **no then why** (it is not using any operand), if **yes, then why** (it is not using any data stored in stack / register memory location). I am stuck in this dilemma. If the bracket part doesn't make sense to you, you may choose to ignore it

# Answer
A 0-operand instruction is simply an instruction that takes no operand. As a result, if such an instruction changes some data either in memory or in some register, the corresponding address or register name is implicitly determined by the instruction itself at time of execution (e.g., the affected memory location might depend on the contents of some register).

I think that your confusion stems from the fact that the "definition" for 0-operand instruction is sloppily written.

A 0-operand instruction is **not required** to operate on any data nor register. What the definition is trying to say is that **if** such an instruction operates on data/registers **then** the address of the data/the involved register must be implicitly determined (duh).

`NOP` is a $0$-operand instruction as it does not take any operand.
> 2 votes

# Answer
To name one example, one of the NOPs in x86 (there's a bunch!) is encoded as `90`. It's a special case of the family of instructions encoded as `90+rd` meaning that it encodes *one* operand in the 3 bottom bits of the opcode, in `90` those three bits are obviously zero, which encodes `eax`. The `90+rd` family encodes `xchg eax, r` so `90` encodes `xchg eax, eax`, swapping a register with itself. So it doesn't do anything, but how many operands is that? At the assembly level, 2 if you write `xchg eax, eax` and 0 if you write `nop`. At the machine code level, 1. 0 operands if you consider how many operands are "logically" used.

To name a couple of other examples, the "normal" NOP in MIPS can also be decoded as `sll $r0, $r0, 0`, RISC-V appoints `addi x0, x0, 0` for that role, and x86 has a "long NOP" `0F 1F /0` where `/0` indicates that a ModRM byte follows and its `r` field has to be set to zero as part of the opcode. This NOP can encode a memory operand, so `nop dword ptr es:[eax + 2 * edx + 4]` is a valid instruction that can be encoded as `26 0f 1f 44 50 04`. How many operands does it have? Maybe 1 since it has only the one memory operand? Maybe 4, counting the segment override and the 3 "parts" of the address separately? Maybe 3, not counting the segment override (are overrides operands? maybe not) but still counting the others? Maybe 0 because none of those things are actually used in the execution of the instruction? I wouldn't want to give any definitive answer, even if I did it would just be my opinion.
> 1 votes

# Answer
A NOP instruction is used to fill program space while having no side effect. This is done for example to make a loop start at the beginning of a cache line to run faster. The AMD processor manuals describe 1 byte to 9 byte NOP instruction. None is officially called NOP.

For example “add constant 0 to register x” would be a NOP instruction. It also has a constant input, a register input, and a register output. Or “set register x to the OR of register x with the contents of register x”, this time two inputs.
> 0 votes

---
Tags: computer-architecture, instruction-set
---


# Question
Title: Loop Bounds vs. Iteration Domain in Polyhedral optimization
**Context:**

I was reading a tutorial on polyhedral optimization. But got confused **while trying to translate the iteration domain (i.e. loop bound) to set builder notation.**

**Problem Description:**

*A code snippet from the article*;

```
for (int i = 0; i <= 2*N; ++i)
    S: Z[i] = 0.;

```

The iteration domain for the statement 'S' is described with the set-builder notation as

`{S[i] : 0 ≤ i ≤ N}`. But the code says that i should go up to or equal to `2*N`.

**Example Case:**

Let’s consider the code given above. And also assume N = 5

Then this loop will iterate from `i = 0 to 10 (where, 2xN = 2x5 = 10)`.

But from the set builder notation, we can see that the iteration domain should be in the range of

`0 <= i <= N, i.e, 0 <= i <= 5`.

But considering the real code snippet,

```
for (int i = 0; i <= 2*N; ++i)
    S: Z[i] = 0;

```

`i` go up to 10.

**So my doubts are…**

1. Then should I write the set builder as `{S[i] : 0 ≤ i ≤ 2N}` or `{S[i] : 0 ≤ i ≤ N}`?
2. For now, even if both of them are correct; later are there any implications/issues that would arise? That I should be concerned on now? I am asking, because I have seen, that those notations are heavily used in forming systems of equations (To solve what, I don’t know yet )

Screenshots are attached from the tutorial for quick review. Thank you.

# Answer
> 1 votes
The article is correct about $T$ but not $S$ since ${S\[i\] : 0 ≤ i ≤ 2N}$ and $T\[i,j\] : 0 ≤ i, j ≤ N$.

I believe a TL;DR of the question is in order, therefore:

1. What is the iteration domain of this loop?

```
for (int i = 0; i <= 2*N; ++i)

```

The answer is ${S\[i\] : 0 ≤ i ≤ 2N}$, and the article incorrectly says ${S\[i\] : 0 ≤ i ≤ N}$.

2. What is the iteration domain of this loop?

```
for (int i = 0; i <= N; ++i)
    for (int j = 0; j <= N; ++j)

```

The answer is $T\[i,j\] : 0 ≤ i, j ≤ N$, and the article correctly says $T\[i,j\] : 0 ≤ i, j ≤ N$.

---
Tags: optimization, arrays, loops, upper-bound, iteration
---


# Question
Title: Problem with cache and memory from university class
In my university class, I received this homework assignment on computer architecture, but I don't know how to solve it. I already know that the correct answer is 0, but I don't understand why. Could someone help me?

Problem: The byte-addressable memory has a 16-bit address. The directly addressed cache has 7-bit tags and 8-byte rows. You need to provide the cache row address if the memory address is #8614. The result should be given in hexadecimal, omitting the # sign.

# Answer
> 2 votes
If I understand correctly, your directly-mapped cache has 128 cache lines of 8 bytes. So, in a memory address, the 3 least significant bits (bits `[0:3]`) are used to compute the location *inside the cache line* while the rest of the bits are used to target a specific cache line inside the cache. I can only *assume* that the 7 next bits (bits `[3:10]`) are used for this purpose. Therefore, memory address `#8614` corresponds to byte 4 in cache line `#42`, because `#8614 % 8 = 4` and `(#8614 // 8) % 128 = #42`.

---
Tags: computer-architecture, memory-management, memory-allocation, cache
---


# Question
Title: Can PTAS be used to optimally solve Knapsack?
Suppose you have a Knapsack (optimisation) problem with integer values and weights, and you know the optimal value $OPT$. Can you compute an optimal solution in polynomial time by using a PTAS or FPTAS and setting $\epsilon \< 1/OPT$, since this would mean it computes a solution in polynomial time which is of value $\geq (1-\epsilon) OPT \> OPT - 1$ which due to values being integers, means it must be an optimal solution?

Also, does this idea generalise by setting $\epsilon$ to something so that $\epsilon OPT$ is smaller than the smallest difference in value between items? This can even be done without knowledge of $OPT$ by searching for the smallest difference $d$ in time $O(n^2)$ for $n$ items and then setting $\epsilon \< d / V$ with $V$ being the sum of all item values.

Is there perhaps a catch about Knapsack being a weakly NP-hard problem, meaning $OPT$ isn't a value bounded polynomially by the input size (even if $OPT$ is given, since it's given in binary) and thus the runtime of the PTAS or FPTAS isn't polynomial...?

# Answer
> 1 votes
The runtime of a FPTAS is polynomial in the input size and in $1/\epsilon$. However, if $\epsilon$ depends on parameters which may **not** be polynomial in the input size, such as in this case $OPT$ or $V$, then the algorithm is not a polynomial time algorithm.

It is however a pseudo-polynomial time algorithm, since the running time is polynomial in the **value** of the input, if not in the size of the input. But at this point, it is a better idea to directly use the pseudo-polynomial time dynamic algorithm for Knapsack (since this is the underlying mechanism for the FPTAS anyway).

---
Tags: optimization, approximation, knapsack-problems
---


title: Is 2-coloring in NL or L?

text:
# Question
Title: Is 2-coloring in NL or L?
The 2-coloring problem is in P. How can I prove that it is in NL or L? I see that I should create a deterministic/nondeterministic algorithm with logarithmic space, but I have no idea how to store the coloring in logarithmic space.

# Answer
The 2-coloring problem is $\mathsf{SL}$-complete. That means that there is a logspace reduction from 2-coloring to undirected accessibility (and conversely). See this paper for some references.

It was showed in 2004 that $\mathsf{L} = \mathsf{SL}$.
> 5 votes

# Answer
Note that a graph $G$ is 2-colorable iff $G$ is bipartite iff $G$ has no odd cycle. All these equivalences are well-known and can be easily looked up. Using that, it is easy to show that the language is in $NL$, and one can even show that it is in $L$, as already answered here.
> 3 votes

---
Tags: complexity-theory, graphs, complexity-classes, colorings
---


# Question
Title: Kd-trees excluding some splitting dimensions
I have a 12-dimensional state-space and would like to use a kd-tree to partition my data, so that nearest neighbour operations can be performed quickly. Unfortunately I have the issue that three of the states are angular values which wrap-around (360 degrees and 0 degrees are the same), which will mislead the nearest neighbour search on this dimension as two values which fall on different sides of a partition could in reality be close. Is it valid, when constructing the tree and performing the nearest neighbour searches, just to 'switch/split on' the nine dimensions which don't wrap around, and rely on the fact that the nearest neighbour considering all twelve of the states will be found when the metric comparisons and branch exploration operations are performed on the way back up the tree?

In my mind this seems okay, but I just wanted to sanity check as it's very possible that I'm missing something... Alternatively, if there are any data structures that you think would be better suited to this problem, please let me know! Thank you for any help.

# Answer
> 0 votes
I suggest that you tweak the distance metric slightly, and then tweak the split function in your k-d tree to match it. You can define any distance metric that you want, to capture/measure similarity between two points. And you can modify a standard k-d tree so it works well with the revised distance function.

When computing the distance between two angles $r,s$, a helpful definition is

$$d(r,s) = \min(|r-s|,|r+360-s|,|r-360-s|),$$

or concisely, $d(r,s) = |r-s| \pmod{360}$. Here I am assuming $r,s$ are measured in degrees; if they are measured in radians, replace $360$ by $2\pi$.

The total distance can be obtained by computing the the distance for each coordinate/dimension, squaring all those distances, summing up all of those squares, and taking the square root of that sum. In other words,

$$D(x,y) = \bigg( \sum\_i d\_i(x\_i,y\_i)^2 \bigg)^{1/2},$$

where $d\_i(\cdot,\cdot)$ is a distance metric that is appropriate for the $i$th dimension: $d\_i(x\_i,y\_i) = |x\_i-y\_i|$ if the $i$th dimension contains ordinary data, or the angular distance metric listed above if the $i$th dimension contains angular data.

Then, I suggest you define the "nearest neighbor" using this distance measure $D(\cdot,\cdot)$.

Next, you need to adapt the k-d tree so it will be useful for finding the nearest neighbor.

My thought would be to build a k-d tree on all 12 dimensions, but change how the "split" works for the 3 angular dimensions, to accommodate the wrap-around semantics.

Normally, we split based on a threshold $\tau$. All data points $x$ with $x\_i \le \tau$ go to one group, and all data points with $x\_i \> \tau$ go to the other group. This splits the range $(-\infty,+\infty)$ of all possible values into two subranges: $(-\infty,\tau\]$ and $(\tau,+\infty)$.

With angular data, one plausible approach would be to split based on a threshold $\tau$, but adapting the comparison to take into account wraparound. Specifically, all data points $x$ with $\tau-180 \< x\_i \le \tau$ or $x\_i \> \tau+180$ go to one group, and all data points with $\tau \< x\_i \le \tau+180$ or $x\_i \< \tau-180$ go to the other group. (Here I assume $x\_i$ is an angle measured in degrees. If it is measured in radians, replace $180$ with $\pi$.) In other words, the threshold $\tau$ basically splits the range $\[0,360)$ of all possible angles into two subranges: $(\tau-180 \bmod 360, \tau\]$ and $(\tau, \tau+180 \bmod 360\]$, with all values taken modulo 360 to take into account wraparound.

Then, for each dimension, the k-d tree would use either a normal split or a wraparound split, according to whether that dimension refers to normal data or angular data.

Finally, you can adapt standard algorithms for building a k-d tree to work with this modification, and you can adapt standard algorithms for finding the nearest neighbor by traversing the k-d tree to work with this modified distance metric and modified data structure.

---

A minor side note: If you are finding nearest neighbors for nearest-neighbor classification or a similar purpose, it is often helpful to standardize all of the coordinates (subtract off the mean for that coordinate, divide by the standard deviation), before computing the distance. If you do that, you'll need to divide $360$ by the standard deviation in the above distance metric for angles.

---
Tags: data-structures, nearest-neighbour, kd-tree
---


# Question
Title: Check-digit algorithm that includes characters?
I have a data set that uses a very simple modulo 10 checksum algorithm which ignores alphabetic characters entirely. Which wasn't a big deal, as the few alphabetic characters present weren't critical.

Changes to the data format are upcoming, including characters which will now be critical to the interpretation of the data. So I'd like to propose a new checksum algorithm that can detect errors in those characters. And something more powerful then modulo 10 wouldn't hurt either.

I've been looking at the Luhn, Verhoeff and Damm and a few other check digit algorithms, but they all only handle digits, not characters. Is there anything out there that does both digits and characters \[A-Z.+-\] ? I'd rather implement something existing and proven rather then roll my own. I think the check 'digit' could reasonable be any character from the alphabet in use \[A-B.+-\], not just \[0-9\]

Thanks!

# Answer
## Check *digit*

If the check digit needs to be a *digit* (0-9), here is one solution:

You could take the SHA256 hash of the character string, modulo 10, and use that as your check digit. The advantage is that this has good properties on average, and takes into account all characters.

Arguably, a possible disadvantage is that it is not guaranteed to detect all single-digit errors and all transpositions; those are only detected with probability 9/10. (Some other checksum algorithms for *digits* achieve the latter guarantee, but they don't work with alphabet characters. Moreover, there is no hope or possibility of achieving both of those guarantees when you have to deal with alphabetic characters: it's not possible to guarantee detection of either kind of error when you have alphabetic characters and a check digit that is restricted to 0-9.) Therefore, I'm not sure it is possible to do much better than this.

## Check character

If the check digit can be anything from the character set, here is an alternative solution:

Suppose there are $n$ characters, so each character can be thought of as a number in the range $0,1,2,\dots,n-1$. Let the characters in the string be $x\_1,x\_2,\dots,x\_k$. Then you can use the following as the check sum:

$$x\_1 + 2x\_2 + 3x\_3 + \dots + kx\_k \bmod n.$$

If $n$ is prime, this has the following nice guarantee: any one-character error will be detected (e.g., `cooking` -\> `cooling`), and any transposition of two characters will be detected (e.g., `weird` -\> `wierd`) (unless the transposed characters are a multiple of $n$ positions apart).

If $n$ is not prime, you get weaker properties, but it's still a reasonable checksum.

Alternatively, you can use the SHA256 hash of the character string, modulo $n$, as the check sum. That has no guarantees but is good on average.
> 1 votes

# Answer
Ok, in reading my the links I posted above more carefully, I found one answer: Luhn mod N algorithm Similar to the suggestion Yuval gave above I guess. Suggestions still welcome, but this is a good starting point I think.
> 1 votes

# Answer
I realize that this is a very old question, but I just came across it as part of my own research into the topic. Hopefully, this will be useful to somebody else who finds it.

There has been a newer proposal by Chen et al. ("A general check digit system based on finite groups", there's an author's copy here) for a system that can also be instantiated for base 36 (see Section 5.3 of that paper) and in that case will not only catch all single errors and transpositions (like the Verhoeff and Damm algorithms), but also all instances of errors such as jump transpositions.

It also seems like this system is being used in some real-world applications.

The Damm algorithm can also be extended to arbitrary bases (as per Damm's PhD thesis \- generated operation tables are also given here for a number of orders including 36). It's easier to implement than the aforementioned one, but as I currently understand it, gives only the guarantee of detecting all single errors and adjacent transpositions by construction (though some of the many possible groups for a given order might provide stronger detection capabilities, see for example the table on page 107 of the thesis).

Note that all these systems are optimized for the kinds of errors that happen during transcription by humans. From your question, it's not quite clear if that is what you're going for. If not, a traditional checksum might be more appropriate.
> 1 votes

---
Tags: hash
---


title: Converting Regex to DFA

text:
# Question
Title: Converting Regex to DFA
People I know said that converting a Regex to DFA is just a "matter of judgement" (I do not believe them, there has to be a more systematic approach).

Is there a simple/intuitive, yet concise way to convert a Regex like this

a\*b+a(b+a|aa+b)\*ab(a?|bb?a)+

into a DFA?

# Answer
> 7 votes
You can convert the regular expression into an automaton using the Glushkov's construction.

The resulting automaton is non-deterministic, but you can find a deterministic automaton using the powerset construction.

However, the resulting automaton could have a size exponential in the size of the regular expression. There is no construction that always gives an automaton with polynomial size. For example, the minimal deterministic automaton that recognizes $(a\mid b)^\*a\underbrace{(a\mid b)…(a\mid b)}\_{n-1\text{ times}}$ has $2^n$ states.

# Answer
> 1 votes
You can convert a regexp to a DFA with Thompson's algorithm. It is covered in many resources, including standard textbooks on automata theory.

Alternatively, you could consider Glushkov's algorithm. See also what is glushkov NFA. What is the difference between Glushkov NFA and Thompson NFA?.

These convert a regexp to NFA. Then you can use the subset construction to convert the NFA to a DFA.

There are others as well. See, e.g., Bruce W. Watson, A taxonomy of finite automata construction algorithms; Russ Cox's tutorial; and a good textbook on automata theory.

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


# Question
Title: The Hamiltonian cycle problem is P-hard?
I know what P-hard means. Let's denote the P-hard problem as H. For any problem A in P, there exists a polynomial-time reduction from A to H. I think the answer is yes (I suppose that every "easy" problem can be reduced to a "harder" problem (in this case problems in P to an NP-complete problem), but I am not sure.

# Answer
> 4 votes
The Hamiltonian cycle problem is $\mathsf{NP}$-Hard (w.r.t. poly-time reductions), that means that there is a Karp reduction from any problem in $\mathsf{NP}$ to Hamiltonian cycle.

Since $\mathsf{P} \subseteq \mathsf{NP}$ the same holds true for any problem in $\mathsf{P}$. Therefore Hamiltonian cycle is $\mathsf{P}$-Hard (w.r.t. poly-time reductions).

Note however, that stronger notions of reductions are often used when talking about $\mathsf{P}$-completeness / $\mathsf{P}$-hardness. Using poly-time reduction yields some "rough" results like: All non-trivial problems in $\mathsf{P}$ are $\mathsf{P}$-Hard.

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


# Question
Title: How to get the TSP using DP algorithm can use 40 vertices?
I\`m currently doing my homework that solving TSP using DP algorithm or branch and bound algorithm or backtracking algorithm only to solve up to 40 vertices and I can solve up to 30 vertices when I try 35, it get bad\_alloc at memory location 0x00000059F29EEB30. I try to figure out the algorithm but it doesn't get any better. Any solution to this ? Thanks so much. Here is the code:

```
#include <fstream>
#include <vector>
#include <algorithm>
#include <limits>

using namespace std;

const int INF = numeric_limits<int>::max();

int tsp(int n, vector<vector<int>>& graph, vector<int>& dp, unsigned long long mask, int pos) {
    if (mask == (1ULL << n) - 1) {
        // All cities have been visited, return to the starting city
        return graph[pos][0];
    }

    if (dp[mask] != -1) {
        // The subproblem has already been solved
        return dp[mask];
    }

    int minCost = INF;

    // Try to visit every unvisited city
    for (int nextCity = 0; nextCity < n; ++nextCity) {
        if ((mask & (1ULL << nextCity)) == 0) {
            unsigned long long newMask = mask | (1ULL << nextCity);
            int cost = graph[pos][nextCity] + tsp(n, graph, dp, newMask, nextCity);
            minCost = min(minCost, cost);
        }
    }

    // Memoize the result
    dp[mask] = minCost;

    return minCost;
}

int main() {
    ifstream inputFile("input.txt");

    if (!inputFile.is_open()) {
        cerr << "Error opening input file." << endl;
        return 1;
    }

    int n;
    inputFile >> n;

    // Initialize the graph with distances between cities
    vector<vector<int>> graph(n, vector<int>(n));
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            inputFile >> graph[i][j];

    // Close the input file
    inputFile.close();

    // Initialize the memoization table using a column array
    vector<int> dp(1ULL << n, -1);

    // Start from city 0
    unsigned long long mask = 1ULL;
    int pos = 0;

    // Solve the TSP
    int minCost = tsp(n, graph, dp, mask, pos);

    // Write the result to the output file
    cout << "Minimum cost of the TSP: " << minCost << endl;

    return 0;
}

```

and can use any type of code language like Java or Python or C++

# Answer
The code provided uses dynamic programming on travelling salesman problem, which has a time complexity of $O(2^n n^2)$, better than $O(n!)$ for brute force but very slow for $n = 40$. Worse is that it has a space complexity of $O(2^n n)$ for memoization, which would require RAM in the terabytes. It is not known whether there is a classical algorithm faster than $O(2^n)$, or a quantum algorithm faster than $O(\sqrt{3}^n)$.

However there are other approaches that are often faster in practice such as branch and bound which can handle $n$ in the thousands or incorporating plane-cutting into branch and cut which solved $n = 85900$ points in 2006. If the solution need not be exact, only $2-3\\%$ from being optimal, then heuristics approaches such as Lin-Kernighan can handle $n$ in the millions. Read travelling salesman problem wikipedia page.
> 0 votes

---
Tags: dynamic-programming, traveling-salesman, search-problem
---


# Question
Title: Do I need a multilevel page table in the following design?
I am practicing paging in virtual memory and came across a question with the following details

* 44-bit address space
* 16KB page size
* 16 Bytes Page table entry (PTE)

If I understand paging correctly then there would be 2^30 pages, and the page table size if 2^44 bytes

My questions is, do I use a single-level page table or do I have to go with multi-level and why?

# Answer
> -1 votes
Yeah, you probably do. The total size of the page table is $2^{30}\cdot2^4=2^{34} = 16GB$. Clearly prohibitively large. A better arrangement would be a three-level page table, where each level maps ten bits of the virtual address. Since each entry is 16 bytes, the size of a page table for one level is $2^4\cdot2^{10} = 16KB$ which neatly fits into one 16KB page.

---
Tags: virtual-memory, paging
---


# Question
Title: Easy proof of IP ⊆ PSPACE for private coins
There is an extremely standard proof that IP⊆PSPACE, used for instance here, here, or here, by the argument that the full protocol is max-avg game tree that can be evaluated in polynomial space. It's really clean and, dare I say, obvious as a first example of a simulation argument. Great! But that works as long as all coins are public. This one makes this explicit at least, defining IP in terms of message histories.

But this isn't how people talk about IP in practice! The classic graph non-isomorphism protocol, as it's presented to students, in private-coin; the same goes for the standard PSPACE⊆IP proof. In fact, IP\[k\] is often explicitly used to mean private coins, while AM\[k\] is used to mean public coins. I'm aware that private-coin and public-coin are equivalent, this was the substance of Goldwasser+Sipser "Private Coins vs. Public Coins in Interactive Proof Systems", but it is nontrivial. My question is if there's a simple explanation that IP⊆PSPACE that doesn't require going through this.

If you take the 'standard' proof that IP⊆PSPACE and try to apply it with private coins, it doesn't work; now the prover's response needs to depend only on the message and not the coins, so it no longer forms a tree.

If I was teaching this, I would prefer not to define IP one way, then give a proof for a materially different definition. Is there a good way to see that IP⊆PSPACE even with private coins?

# Answer
Following the comments, below is a sketch of the proof that shows explicitly that there is no need for the coins to be public, as we can iterate over all random choices in polynomial space.

Sketch of the proof that $\text{IP} \subseteq \text{PSAPCE}$: consider a language $L \in \text{IP}$, and let $(P, V)$ be an interaction protocol for $L$. It is sufficient, for all $x\in L$, to compute the quantity $cp\_x = \max\limits\_{\widetilde{P}} \Pr\limits\_{r} \ \[\langle \widetilde{P}, V(x, r) \rangle\]$ in polynomial space (intuitively, $cp\_x$ is the maximal convincing probability for $V$ on input $x$). Indeed, if $x\in L$, then $cp\_x \geq \frac{2}{3}$ as for example this quantity is obtained when we consider completeness w.r.t the prover $P$, and if $x\notin L$, then by soundness $cp\_x$ is at most $\frac{1}{3}$. Hence, a PSPACE algorithm first computes $cp\_x$, on input $x$, and accepts only when $cp\_x \geq \frac{2}{3}$.

Note that it is okay to write "max" although there are infinitely many potential provers. The point is that we need not iterate over all provers, but rather over all transcripts of at most polynomial size and there are finitely many. Having this intuition in mind, we can compute the best prover strategy, denoted $P\_b$, a one that maximizes the convincing probability $cp\_x$. Once we have $P\_b$, we can obtain $cp\_x$, to be detailed below.

We can treat $P\_b$ as a function from partial transcripts, describing $i$ rounds of interaction so far, to the next message $a\_{i+1}$ to be sent by the prover, such that $a\_{i+1}$ maximizes the convincing probability conditioned on the past partial transcript that we had so far. Thus, $P\_b(x, a\_1, b\_1, a\_2, b\_2, \ldots, a\_i, b\_i) = a\_{i+1}$, where $a\_k$ and $b\_k$ are the $k$'th messages of the prover and the verifier, respectively.

It is not hard to see that, for input $x$, computing the best prover strategy $P\_b$ in polynomial space is sufficient. Indeed, if we have $P\_b$, then $cp\_x$ is simply obtained by $$ cp\_x = \frac{\sum\limits\_{r\in R} 1\_{\[\langle P\_b, V(x, r) \rangle = 1\]}} {|R|}$$

where $R = \\{ 0, 1\\}^{p(|x|)}$ describes the randomness of the verifier $V$ on input $x$, and $p$ is a polynomial bounding the runtime of $V$. Indeed, for every random string $r \in R$, it is easy to simulate in polynomial space the interaction between $P\_b$ and $V$ on input $x$. Hence, if $P\_b$ can be computed in polynomial space, then so is $cp\_x$.

So to conclude the proof it suffices to compute $P\_{b}$ in polynomial space, for every input $x$. We can compute $P\_{b}$ by induction on the total number of rounds $t$ (note that $t$ is also bounded by a polynomial in $|x|$).

* The base case is the case where we have survived $i = t-1$ rounds of the interaction. Let $(a\_1, b\_1, a\_2, b\_2, \ldots, a\_i, b\_i)$ denote the history of the interaction so far. Then, $$ P\_b(x, a\_1, b\_1, a\_2, b\_2, \ldots, a\_i, b\_i) = \arg\max\limits\_{a\_t} \mathop{\mathbb{E}}\_{r \in R\[x, i\]} \[V(x, r, a\_1, a\_2, \ldots, a\_{t-1}, a\_t)\]$$ where $R\[x, i\]$ is the set of random strings that are consistent with $x$ and the partial transcript $(a\_1, b\_1, a\_2, b\_2, \ldots, a\_i, b\_i)$. Note that it is easy to iterate over all random strings $r$ and check which ones are in $R\[x, i\]$ in polynomial space. All you need to do to simulate the interaction with the current random string $r$ and input $x$, and check if the answers induced by it are consistent with the partial transcript. So the outer loop remembers the best $a\_t$, and the inner loop iterates over all consistent randomness $r$ (even if it is private, we can do that as we can afford it in polynomial space). Both loops can be computed in polynomial space each -- recall the the length of the message $a\_t$ is at most polynomial, so we can iterate over all potential $a\_t$'s in polynomial space.
* The induction step is the case where we have survived $i \< t-1$ rounds of the interaction. Let $(a\_1, b\_1, a\_2, b\_2, \ldots, a\_i, b\_i)$ denote the history of the interaction so far. Then, $$ P\_b(x, a\_1, b\_1, a\_2, b\_2, \ldots, a\_i, b\_i) = \arg\max\limits\_{a\_{i+1}} \mathop{\mathbb{E}}\_{r \in R\[x, i\]} \[V(x, r, a\_1, a\_2, \ldots, a\_{i}, a\_{i+1}, a^\*\_{i+2}, \ldots, a^\*\_t)\]$$

where $a^\*\_j$ is the best prover message obtained by simulating an interaction that is consistent with $x, r, a\_{i+1}$ and $(a\_1, b\_1, \ldots, a\_i, b\_i)$. So once $a\_{i+1}$ and $r$ are fixed and we are in the inner loop, we can compute $b\_{i+1} = V(x, r, a\_1, a\_2, \ldots, a\_{i+1})$, $a^\*\_{i+2} = P\_b(x, r, a\_1, b\_1, \ldots,a\_{i+1}, b\_{i+1} )$ and proceed similarly to compute $b\_{i+2}$ and $a^\*\_{i+3}$, etc. The point is that inside the inner loop, we can compute $a^\*\_j$ in polynomial space as we are applying the induction hypothesis and computing $P\_b$ on transcripts with $ \> i$ rounds. So we kinda open an inner third loop to do that, but it takes at most polynomial space in total as the induction assumption takes care of that.

**Note:** We're actually traversing a tree that has polynomial depth, and exponential fan-out. The base case corresponds to the leaves of the tree. So we have the max-nodes and average-nodes, and to compute the root's value, we kinda apply a standard tree traversal algorithm, which takes at most polynomial space.

**Credit to:** I recall the idea from a lecture of Alessandro Chiesa that I saw online two years ago, but unfortunately I do not recall where or whether it is still up there.
> 2 votes

---
Tags: complexity-theory, education, interactive-proof-systems
---


# Question
Title: Time complexity to remove an item from the heap
Given an array of size $n$ that has the item of the heap. To remove an arbitrary element from the heap we would need $O(n)$ to find the element and then $O(logn)$ to reheapify if I am commrect, which means total time complexity is $O(n + logn)=O(n)$. In study notes, I saw it's written $O(nlogn)$, which does not make sense to me as both finding and reheapify are separate.

# Answer
Yes, that is correct. O(n) to find an arbitrary item, O(log n) to remove it, total O(n).

If you often remove arbitrary items, say you insert n items, then remove the largest or a random item each n/2 times, then the total will be quite large. In this case you could consider a different approach: Mark items as “removed” that you want to remove, then you remove those marked items whenever you encounter them while adding an item or removing the largest item.
> 1 votes

---
Tags: data-structures, heaps, heap-sort
---


# Question
Title: Is there a decidable problem that we know for sure cannot be solved in polynomial time?
If yes, could you say an example? P=NP would result in NP problems being solvable in polynomial time, but there would still be problems in the EXPTIME class.

# Answer
It is known that P $\ne$ EXPTIME. Therefore, any EXPTIME-complete problem suffices. For instance: given a deterministic Turing machine $M$, an input $x$, and a positive integer $k$ (represented in binary), determine whether $M$ halts on input $x$ within at most $k$ steps.

Related: How do we know for sure that EXPTIME ≠ P?, Halting problem in EXP-complete.
> 5 votes

# Answer
Given an integer n \> 0, let x = A(n) be the value of the big Ackerman function. Is the sum of decimal digits of x greater then $4.5 \cdot \log\_{10}(x)$?
> 0 votes

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


# Question
Title: Find a pair $a,b$ with a range condition in Hash table
Given an array with the size of $n$ of integer numbers. Our goal will be to analyze the expected running time of an algorithm that uses a hash table to find (if exists) a pair $(a,b)$ subject to $2\<|a-b|\<5$.

The answer is $O(n)$ but I have no idea to convince myself. Some thoughts that come to my mind are as follows: consider $a$ to find a $b$ in the hash table maybe I have a cost $1+2+\dots+n$ so for each $a$ the average cost will be $O(n^2)$. But the answer is $O(n)$. Anyone can correct my mistake?

# Answer
> 3 votes
If all items in the hash table are integers, then the difference between a and b is 3 or 4. You need an iterator that iterates through all elements of the hash table in O(n) to find all possible values of b in random order; most hash table implementations will provide this. Then for each b you check whether b-3 or b-4 is in the hash table. That's O(n)

If the items in the hash table are real numbers, then the only way is to extract all values, sort them and iterate through the sorted array to find all pairs. Note that the number of pairs (a, b) can be O(n^2), for example if all values are between 1 and 2. The time is O (n log n + m), where m is the number of pairs (a, b). n log n is for sorting the values.

---
Tags: algorithms, hash
---


# Question
Title: Time complexity for logarithmic algorithm
I am trying to find complexity for following algorithm. It is from "The Algorithm Design Manual" book.

```
for k = 1 to n:
   x = k
   while (x < n):
      print ’*’
      x = 2x

```

I simulated algorithm for some values. Each time inner loop operates on `n-k` value.

```
k=1
   x=1
   x=2
   x=4
   x=8
   ...
k=2
   x=2
   x=4
   x=8
   x=16
k=3
   x=3
   x=6
   x=12

```

And I do think that it has complexity of

$\sum\limits\_{k=1}^{n}k\*\lg(n-k)$

What do you think?

**Edit 1**

After some time, I think it should be $\sum\limits\_{k=1}^{n}\lg(n-k)$

# Answer
> 2 votes
$\sum\limits\_{k=1}^{n}\log \frac{n}{k} = \sum\limits\_{k=1}^{n}\log n-\sum\limits\_{k=1}^{n}\log k = \log n^n - \log n! = n \log n - (n \log n - n + O(\log n)) = n - O(\log n) = O(n)$

# Answer
> 1 votes
You need to add log (n / k), not log (n - k).

To examine this closer: For values n/2 \<= k \<= n you have only one iteration of the inner loop. For values n/4 \<= k \< n/2 you have two iterations. For values n/8 \<= k \< n/4 you have three iterations of the inner loop.

So the total number of iterations of the inner loop is 1 * n/2 + 2 * n/4 + 3 * n/8 + 4 * n/16 ... which is n + n/2 + n/4 + n/8 ... which is 2n. So you have about 2n iterations in total of the inner loop, and the total time is O(n).

---
Tags: time-complexity
---


# Question
Title: pick K random integers without repetition
Suppose we've to pick $K (\le N)$ random integers in the range $\[0, N - 1\]$ for very large $N$ such that there is no repetition, while also deterministically minimizing the number of calls made to the $rand()$ function. How would we do it?

Assume $rand(X)$ produces a random integer in the range $\[0,X - 1\]$; calling it with any argument counts as one call.

Picking at random till we get a unique value may not be efficient for smaller N, and $O(N)$ algorithms, i.e. ones which require looping through the entire range of integers is also not feasible, as $N$ could be up to $10^{18}$.

Is there any way to accomplish this?

# Answer
Ṃųỻịgǻňạcểơửṩ mentioned that this is the reservoir problem. The reservoir sampling problem, though, is explicitly a very strict requirement for a streaming algorithm, i.e. it works in just one pass over a stream of values whose eventual size we don't know.

In this case, we want to do it in one pass, but we do know both N and K, so the problem is a little different and it permits a simpler solution.

Floyd's algorithm is designed for this task. It has some resemblance to both the Fisher-Yates shuffle and to reservoir sampling.

A couple of minor differences from the framing in your question:

* K \< N
* we use randint(i, j) which produces a random integer between i and j inclusive
* the samples will be generated in the range 1 to N inclusive (but of course it is easy to adjust this at the end)

Here's the Python code:

```
import random

n = 200
k = 5
s = set()

for j in range(n-k+1, n+1):
    t = random.randint(1, j)
    if t not in s:
        s.add(t)
    else:
        s.add(j)

print(s)

```

A good source for the origin of and mathematical justification for Floyd's algorithm is this article by Jon Bentley from 1987. It's worth noting that the algorithm only calls randint() K times.

A very brief description of how it works is that, on iteration t, it draws a number randomly from \[1..n-k+t\]. If the number has not been drawn before, it is added to the sample. Otherwise, it adds the number n-k+t to the sample. This works to give the proper probabilities of inclusion in the final set.

In Bentley's article there is a description of the recursive formulation of the algorithm:

> We can appreciate the correctness of Floyd’s algorithm anecdotally. When M = 5 and N = 10, the algorithm first recursively computes in S a 4-element random sample from 1..9. Next it assigns to T a random integer in the range 1..10. Of the 10 values that T can assume, exactly 5 result in inserting 10 into S: the four values already in S, and the value 10 itself. Thus element 10 is inserted into the set with the correct probability of 5/10.

I can't do better than that explanation, right now!

The algorithm has been mentioned on StackOverflow and proofs are here on Math SE.
> 16 votes

# Answer
What quality of randomness do you need? You can construct a Linear Congruential Generator as a PRNG with period of `N` (or the next prime above `N`) and discard out-of-range samples.

Use `rand()` only to seed your LCG PRNG.

Of course you get the same sequence every time, just from different start points, unless you also try to randomize your LCG's multiplier and adder parameters. Or as John Bollinger puts it, *for any given K it can produce only about N distinct K-element samples*.

Re-randomizing the multiplier (`a`) and adder (`c`) constants while still satisfying the conditions for period `m` (the modulus) can make multiples sets of sequences possible. And/or raise `m` so there are more numbers between N and `m` you'd have to discard if generated. But there's limited freedom so this only goes so far. (And depending on LCG parameters there can be significant correlation between numbers.)

This requires O(1) storage and negligible time per result, just a 64-bit multiply, add, and modulo.
If you need bigints for this, I guess O(log2(N)) storage and time per query with a small constant factor. But 10^18 \< 2^64. Initial setup time requires finding a prime above N.

---

**Quality of randomness is low**: even the best LCGs are not great pseudo-random generators by modern standards, although some of their downsides come from choices like a power-of-2 `m`odulus which makes the low-order bits highly correlated. (Other downsides include a short period, which we're taking advantage of here.) But automated selection of LCG parameters to fit a given period can result in generators much worse than a "good" LCG. For some small N, pairs of consecutive numbers are common in the output sequence. Maybe different LCG parameters with the same or similar period could avoid that.

I used this in practice for a partly-finished subtree-pruning-regrafting library that I never did much with, GPLed code on Github with comments explaining the algorithm, citing Knuth TAOCP for the conditions that produce period `m`, and Numerical Recipes for some PRNG quality folklore and best practices. The LCG-selection part does work correctly, but basically gives up and makes the multiplier 1 and adder 0 in some corner cases. Also for tiny `maxval = N`, 6 or less, since for this library's purposes, 6 was few enough to just brute-force try all possibilities and see which tree gave the maximum likelihood.

```
struct lcg {
    unsigned int state;
    unsigned int a, c, m;
    unsigned int startstate;
};

/******************** Linear Congruential Generator setup ************/
/* to generate all possible SPRs in a pseudo-random order, we generate
 * all the numbers between 0 and the number of possible SPRs once each
 * without repetition using an LCG of the form: x_n+1 = x_n*a + c mod m.
 */
/*
 * Knuth: TAOCP 3.2.1: ex 2: if a and m are relatively prime,
 * the number X_0 will always appear in the period.  (will return to start?)
 *
 *  3.2.1.2: Theorem A: An LCG will have period m iff:
 *   -  c is relatively prime to m
 *   -  b = a-1 is a multiple of p, for every prime p dividing m
 *   -  b is a multiple of 4, if m is a multiple of 4
 *
 *  3.2.1.3: ex 4:  m = 2**e >= 8  ->  maximum potency when a mod 8 = 5.
 *   small multipliers are to be avoided.
 *
 * Numerical recipies suggests c = a prime close to (1/2 - sqrt(3)/6)*m
 */

/* make up some parameters for an LCG that will have the maximum period
 * equal to the range, so every value is generated once.
 * When maxval doesn't have any repeated prime factors, a = m+1,
 * which is the same as a=1.  It's not exactly random, but it does still
 * mix up which SPRs are done.
 *
 * TODO: take advantage of the fact that maxval = floor(sqrt(maxval))*ceil(sqrt(maxval))
 *  could do that, but then the code would be less general-purpose
 * successfully brute-force tested for maxval=1..1000.
 */
void findlcg(struct lcg *lcg_params, int maxval)
{
    unsigned int a, b, c, m = maxval;
    int i;

    primesetup (maxval+maxval/2);

    if (m<=6){ // will be either 6 or 2.  Just loop in order
        b=0;
        c=1;
    }else{
        int divlimit = m;
        b=1; // b must be a multiple of all of m's prime factors
        if (!(m%2)){
            b=2;
            while (divlimit%2 == 0) divlimit /= 2;
        }
        for (i=3 ; i <= divlimit ; i+=2){
            if (is_prime(i) && m%i == 0){
                b *= i;
                while (divlimit%i == 0) divlimit /= i;
            }
        }

        if (!(m%4)){    // if m is a mult of 4, b must be.
            while (b%4) b *= 2;
        }

        /* make sure a isn't too small */
        while (b<sqrtf(m)) b*=7;

        if (b == m) b=0;  // just give up and avoid overflow

// Numerical Recipies says there is "lore" behind this... :)
// TAOCP says it's useless unless the multiplier sucks (section 3.3.3, eq. 40)
// That would be us.
        c = next_prime(max(5, (0.5 - sqrtf(3)/6.0)*m - 2));
        while (m%c == 0) c = next_prime(c+1);
        // Luckily we don't have to test for c>m, because it doesn't
        // happen with any m<100, and there are enough primes later...
/* I've observed that when a == m, (e.g. a=13, c=13, m=72) you often get
 * two consecutive numbers...  Do something to avoid that if it's a problem */
    }

    a = b+1;

    unsigned long long l = (unsigned long long)a * m;
    if (l > ULONG_MAX){
        fprintf(stderr, "spr: chosen Linear Congruential Generator is bogus\n"
        "   x_n+1 = x_n*%u+%u mod %u\n"
        "   a*m > ULONG_MAX, so it would overflow :(\n", a, c, m);
    }

    lcg_params->a = a;
    lcg_params->c = c;
    lcg_params->m = m;
    lcg_params->startstate = UINT_MAX;
    lcg_params->state = rand() % m;
}

```

My use-case was smallish trees so for prime finding I just used a straightforward Sieve to find true primes, not just relatively-prime which would be sufficient. Quality of pseudo-randomness was not a priority at the time, before moving on to other work. There might be room to spend more time choosing LCG parameters better than the algorithm shown here.
> 6 votes

# Answer
If you care only about having uniform probability for each of the $N$ elements to be included in the $K$-element sample, then @PeterCordes's suggestion to use just one call to $rand()$ to seed a suitably tuned LCG is very attractive.

If it is additionally important to have equal probability of each of the $\tbinom{N}{K}$ distinct possible $K$-element samples, without regard to order, then Floyd's algorithm for sampling without replacement, as suggested by @TheoH, is hard to beat.

But if the order of the selections is important, such that for every draw, each as-yet unselected element should have an equal probability of being selected, then you need something more. A partial Fischer-Yates shuffle could do this job in $K$ calls to $rand()$, but that requires an impractical amount of storage for large $N$. Or does it?

You can perform a Fischer-Yates-like selection of $K$ elements with $K$ calls to $rand()$ and with only $O(K)$ overhead by maintaining a map from previously selected values to replacement values. Such a map can be constructed with $O(K)$ memory for which storage and retrieval operations each have $O(1)$ amortized asymptotic complexity, so this does not asymptotically increase either computational complexity or the storage required ($O(K)$ storage already being required for the result). Having first initialized an empty map, $M$, one proceeds as follows on the $i$th draw ($i$ starting from 0):

* compute $x = \mathrm{rand}(N - i)$
* compute the selected element $y$ as $y = \begin{cases} M\[x\] & \text{if it exists} \\ x & \text{otherwise} \end{cases}$
* set $M\[x\] = \begin{cases} M\[N - i - 1\] & \text{if it exists} \\ N - i - 1 & \text{otherwise} \end{cases}$
> 5 votes

# Answer
You can do it in **one** call to the *rand()* function, with a perfect uniform distribution, if you're willing to use large integers.

Here's the basic idea:

1. List out all of the possible ways to choose K distinct integers from the range \[0, N-1\].
2. Throw a dart at the list, choosing one of those ways

Once you've done this, you'll realize that you don't actually *need* that list of possibilities: You can use a mathematical formula to compute the selection choice directly from the id, in O(1) time, without the list.

For example, if you're trying to select k = 2 distinct items from n = 3 options, then you could use the list:

```
L(3, 2) = ["011", "101", "110"]

```

...where "110" means that you would select the first two items, and ignore the third. So, if *rand*() generates "id = 2", then you'd look up the binary sequence at position 2 ("110"), and select those first two items.

In general, there are M = (N K) = N!/(K!(N-K)!) possible ways to select K distinct integers from the set \[0, N-1\]. So a single call to the random number generator, *rand*(M), will randomly choose one of those possibilities.

All you need to get started is a canonical list of the possibilities--that is, a canonical *ordering* of the list.

Really, *any* ordering will work. But here's one that has a nice recursive formula:

```
L(n, 0) = ["0...0"] (where "0...0" has length n), and
L(n, n) = ["1...1"] (where "1...1" has length n), and
L(n, k) = [], for n < k, and
L(n, k) = ["0" + L(n-1, k), "1" + L(n-1, k-1)]
...where "1" + "001" = "1001" is string concatenation.

```

This lets you build up a canonical list of any size.

For example, if you'd like to generate the list from earlier, L(n, k) where n = 3 and k = 2, then you could do it like this:

```
L(1, 1) = ["1"]
L(2, 2) = ["11"]
L(1, 0) = ["0"]
L(2, 0) = ["00"]
L(3, 0) = ["000"]

L(2, 1)
 = ["0" + L(1, 1), "1" + L(1, 0)]
 = ["0" + ["1"], "1" + ["0"]]
 = ["01", "10"]

L(3, 1)
= ["0" + L(2, 1), "1" + L(2, 0)]
= ["0" + ["01", "10"], "1" + ["00"]]
= ["001", "010", "100"]

L(3, 2)
= ["0" + L(2,2), "1" + L(2,1)]
= ["0" + ["11"], "1" + ["01", "10"]]
= ["011", "101", "110"]

```

This allows you to compute the canonical list for any problem size. This already enough to get a solution using dynamic programming.

But you can do better. The recursive formula also yields a closed-form solution, and its inverse, g(id), directly computes the binary sequence.

This is a high-effort approach, but it does yield a *fantastic* O(1) solution that involves only one call to the random number generator.
> 4 votes

# Answer
Theo H's suggestion of using Floyd's algorithm is a good one, but requires knowing the number of elements we wish to sample in advance. However, there's a fairly similar algorithm that allows the sampled elements to be generated one at a time "on demand".

The basic idea is to run a partial Fisher–Yates-Durstenfeld–Knuth shuffle on a sparse array, storing only the elements that have changed from their initial values.

To understand this algorithm, it may be useful to start with a quick recap of the basic FYDK shuffle (zero-based ascending-index version with initially sorted array):

> * Let *a* be an *n* element array initialized with *a*\[*k*\] := *k* for all 0 ≤ *k* \< *n*.
> * For each *i* from 0 to *n*-1:
>     + Let *j* be a uniformly chosen random integer with *i**j* \< *n*.
>     + If *i**j*, swap *a*\[*i*\] and *a*\[*j*\].
> * Now *a* is a random permutation of the integers from 0 to *n*-1.

Looking at the FYDK shuffle algorithm above, we can see a few notable features and invariants:

* In each loop iteration, the new value of *a*\[*i*\] is chosen uniformly at random from among the values not yet assigned to any *a*\[*k*\] for some *k* \< *i*.
* The value assigned to *a*\[*i*\] in each loop iteration is never overwritten by later iterations.
* By induction on the above, at the end of each loop iteration, *a*\[0\] … *a*\[*i*\] is a uniformly chosen (and uniformly shuffled) random sample of *i*+1 distinct integers from the range \[0, *n*).

In particular, this leads to the following observations:

* If we stop the FYDK shuffle (as given above) after *k**n* iterations, the first *k* elements of the array *a* form a uniformly chosen (and uniformly shuffled) random sample of *k* distinct integers from the range \[0, *n*).
* During the first *k* iterations, only at most 2*k* elements of *a* are changed from their initial values. Thus, if *k* is much smaller than *n*, we can save time and storage space by using a sparse map to only store the changed elements of the array *a*.

Also, since the first *k*-th elements of *a* are never changed after the first *k* iterations of the FYDK shuffle loop, we can easily transform the algorithm into a coroutine that yields the *k*-th element to the caller immediately after the *k*-th iteration:

> * Let *a* be a sparse map with default values *a*\[*k*\] = *k* for all 0 ≤ *k* \< *n*.
> * For each *i* from 0 to *n*-1 (or until caller stops iteration):
>     + Let *j* be a uniformly chosen random integer with *i**j* \< *n*.
>     + Yield *a*\[*j*\].
>     + Let *a*\[*j*\] := *a*\[*i*\].
>     + Unset *a*\[*i*\].

…or, equivalently (using a map without implicit default values):

> * Let *a* be a sparse map.
> * For each *i* from 0 to *n*-1 (or until caller stops iteration):
>     + Let *j* be a uniformly chosen random integer with *i**j* \< *n*.
>     + If *j* is a key in *a*, yield *a*\[*j*\], else yield *j*.
>     + If *i* is a key in *a*, let *a*\[*j*\] := *a*\[*i*\], else let *a*\[*j*\] := *i*.
>     + Unset *a*\[*i*\].

(The "unset *a*\[*i*\]" step at the end of the loop is not strictly necessary for correctness, but since no later iteration will access *a*\[*i*\], there is no point in storing it any longer.)

Anyway, here's an example implementation in Python:

```
import random

def sample_range(start, stop=None, step=1):
    """
    Yields a stream of random unique integers from range(start, stop[, step]) using only
    O(k) storage for k outputs. This is done using the Fisher-Yates-Durstenfeld-Knuth
    shuffle on a sparse array (implemented using a dict) that only stores elements that
    have been changed and not yet yielded to the caller. The first k outputs form a
    uniformly chosen (and shuffled) random sample of k distinct elements from the range.
    """
    if stop is None:
        # Python convention: range(n) == range(0, n)
        start, stop = 0, start

    # Conceptually this dictionary is initialized so that a[k] = k for all k in the range,
    # but we only explicitly store values for entries that are changed from this default.
    a = dict()

    for i in range(start, stop, step):
        j = random.randrange(i, stop, step)
        # Conceptually we swap a[i] and a[j] and then yield a[i] to the caller. However,
        # as a[i] will never again be accessed after this, we can save some time and
        # storage space by leaving it unset.
        yield a.get(j, j)   # a.get(key, default) returns a[key] if set, else default
        a[j] = a.pop(i, i)  # a.pop(key, default) does the same, but also unsets a[key]

```

(And here's an online demo with a basic test of correctness and uniformity.)

FWIW, I do not know if this particular algorithm / coroutine has a name. I've used and written about it before, but for all I know I could be the first person to invent it. Given its simplicity, however, I very much doubt that.

In particular, I rather suspect that, had someone described this algorithm to Knuth 50 years ago, he would've considered it a natural and obvious extension of the FYDK shuffle. Which of course doesn't mean that it's necessarily quite as obvious to us lesser mortals.

(Edit: In fact, except for trivial indexing differences, I believe this is essentially the same algorithm as the one sketched out in John Bollinger's answer.)
> 2 votes

---
Tags: randomness
---


# Question
Title: Generate sets of size N+1 from sets of size N
Given a set $S$ of N-element sets, I want to generate all (N+1)-element sets (call this set $T$) such that for each element of $T$ each N-element subset is in $S$.

My current naive algorithm performs quite badly. Set $S$ ~ 100-10000 elements and $N$ ~ 5 or so.

More concretely (although perhaps more confusingly).

Let $N\in\mathbb N$ and $X$ be a set.

Let $S$ be such that for each $s\in S$ we have that $s\subseteq X$ and $|s| = N$.

Design an algorithm such that produces $$T = \\{t\subseteq X:|t|=N+1 \land s\in S \\,\forall\\, (s\subseteq t \land |s| = N )\\}$$

For Example:

Given a set $S = \\{(1, 2), (1, 3), (2, 3), (2, 4)\\}$ then the resulting set $T$ is $\\{(1, 2, 3)\\}$. as $(1, 2, 3)$ is the only 3 element set such that all 2-element subsets are in $S$.

For $N=2$ this is equivalent to finding all triangles in a graph.

# Answer
> 1 votes
I will suggest one possible approach::

* Build a hashtable that for each set $r$ of size $N-1$, maps to a list of elements $x$ such that $r \cup \\{x\\} \in S$.
* Now, for each $s \in S$, and each $r \subset s$ such that $|r|=N-1$, look $r$ up in the hashtable, find the corresponding list, and for each $x$ in the corresponding list, check whether $s \cup \\{x\\}$ satisfies the requirements -- specifically, whether every subset of size $N$ of $s \cup \\{x\\}$ is in $S$.

The running time will depend on the structure of sets in $S$. I can give a heuristic analysis. I suspect that often, each set $r$ will map to only a few elements $x$. In such cases, the running time of this algorithm is something like $O(|S| \cdot N^2)$. That ought to be fast enough for the parameters you list in the question.

---
Tags: graphs
---


# Question
Title: Big O, Understanding when the increment is doubling
I am trying to find the Big O notation of this code below, really its the big theta, but whatever I believe its the same in this case.

```
for (i=2; i < n^2; i++){
   for (j=3; j < 4i^3; j = 2*j){
      x = i+n
   }
}

```

One, I believe that the constant in 4i^3 can be dropped. And so, the inner loop is maybe, O(i^3) =\> (2^k)^3 for some summation of k = 0 to k = log (i^3). I am not really sure what to do from there. And, I'm not really sure if I understand that portion correctly.

# Answer
The inner loop: After k iterations we have $j = 3 \cdot 2^k$. We exit the loop if $3 \cdot 2^k \ge 4 \cdot i^3$ or $2^k \ge (4/3) \cdot i^3$ or $k \ge \log (4/3) + 3 \cdot \log i$.

So we add $\log (4/3) +3 \cdot \log i$ for $ 2 \le i \lt n^2$. An immediate upper bound is $n^2 \cdot (\log (4/3) + 6 \log n)$. The actual number of iterations is not much smaller because for most values i, $\log i \approx \log n^2$. So we have roughly $6 \cdot n^2 \cdot \log n$ iterations of the inner loop.
> 3 votes

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


# Question
Title: SAT formulation of the condition that an even number of a given set of variables must be set to true
Lets say I have a SAT problem with variables $x\_1,...,x\_n$. For a given subset of the variables I want to create a clause which forces an even number of the variables in $S$ to be true. Of course there is the brute force solution, but I would like a more efficient solution with as few clauses/variables as possible.

# Answer
Let $\oplus$ be XOR, then your question is asking for $\bigoplus\_{k=1}^n x\_k = 0$. We can encode this efficiently without an exponential explosion in clauses by introducing new variables.

The basic premise is the following:

$$a = b \oplus c \quad\iff\quad a \oplus b \oplus c = 0$$

Assuming $a$ is the new variable this is equivalent to adding the following CNF clauses:

$$(\neg a \vee \neg b \vee \neg c) \\,\wedge\\, (\neg a \vee b \vee c) \\,\wedge\\, (a \vee \neg b \vee c) \\,\wedge\\, (a \vee b \vee \neg c)$$

Using the above construction we add the following clauses:

$$y\_1 = x\_1$$ $$y\_2 = y\_1 \oplus x\_2$$ $$y\_3 = y\_2 \oplus x\_3$$ $$\cdots$$

Finally we add the clause $\neg y\_n$.

Total cost is $n$ additional variables and $4n + 1$ ternary CNF clauses. You can shave off a couple variables / clauses with a better base case for the recursion - I could not be bothered.
> 6 votes

---
Tags: logic, satisfiability
---


# Question
Title: Is there an NP-hard problem that is polynomially reducible to its complement, and whose complement is polynomially reducible to the problem?
I suppose that this statement is true if NP equals with coNP, otherwise not, but I don't know how can I prove that.

# Answer
> 2 votes
Take any NP-hard problem $A \subseteq \\{0,1\\}^\*$. Now let $\langle A, \overline{A}\rangle := \\{0w \mid w \in A\\} \cup \\{1w \mid w \notin A\\}$. Clearly, $A$ is polytime reducible to $\langle A, \overline{A}\rangle$ via $w \mapsto 0w$, thus $\langle A, \overline{A}\rangle$ inherits being NP-hard from $A$. Also, $\langle A, \overline{A}\rangle$ is polytime equivalent to its own complement, namely by the map that just flips the first bit.

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


title: Calculate the CPI of a program

text:
# Question
Title: Calculate the CPI of a program
```
foo:
addi $t0,$zero,1
addi $v0,$zero,0
outer:
beq $t0,$zero,exitout
sll $t0,$t0,0
addi $t1,$zero,0
add $t2,$zero,$a0
addi $t0,$zero,0
inner: addi $t8,$a1,-1
slt $t9,$t1,$t8
beq $t9,$zero,outer
sll $t0,$t0,0
addi $v0,$v0,1
lw $t8,0($t2)
lw $t9,4($t2)
slt $t7,$t9,$t8
beq $t7,$zero,skip
sll $t0,$t0,0
lw $t8,0($t2)
lw $t9,4($t2)
sw $t9,0($t2)
sw $t8,4($t2)
addi $t0,$zero,1
skip: addi $t2,$t2,4
j inner
addi $t1,$t1,1
exitout:
jr $ra
sll $t0,$t0,0

```

**Question** What is the clock cycles per instruction (CPI) when executing foo with the following C code call: foo(lst,1) (that is the second argument is 1 instead of 3)? Do not include the time it takes to call the function, but you must include the clock cycles for returning. That is, count the clock cycles up until just before the next instruction is fetched after returning from foo. Include the branch delay slot in the instruction count.The first instruction is located at address 0x40003300.

```
int lst[] ={100,23,8};
int r = foo(lst,3);

```

**Here is what I don't understand** Don't we only execute 11 instructions from 1st to 10th then 4th agan? Or do we include the branch penality instructions also in which case we will have 15? Also how can 4 misses give 40 cycles? Also we never get far enough to execute 3 branches. Can someone just help me?

**Answers**

> By following the program, we can see that there will be no memory accesses. Hence, we do not have any data cache misses. Only 4 instruction cache blocks will be touched. Hence, we have 4 instruction cache misses, which imply a cost of 40 clock cycles. If we count the number of executed instructions, we get 12 instructions without penalties for hazards. We do not have any stalls due to data hazards, but we have 3 branch instructions that give a penalty of 3 + 3 + 1 = 7 clock cycles. Hence, we have in total 40 + 12 + 7 = 59 clock cycles. If we count, we get 15 instructions, including the delay slot instructions. Hence, the CPI is 59/15.

# Answer
> 1 votes
Begin by drawing a table of the instructions executed:

| # | INSN | OP1 | OP2 | OP3 | COMMENT |
| --- | --- | --- | --- | --- | --- |
| 1 | addi | t0 | zero | 1 | t0 = 1 |
| 2 | addi | v0 | zero | 0 | v0 = 0 |
| 3 | beq | t0 | zero | exitout | t0 != 0 (hit) |
| 4 | sll | t0 | t0 | 0 | (bds) |
| 5 | addi | t1 | zero | 0 | t1 = 0 |
| 6 | add | t2 | zero | a0 | t2 = 0x40003300 |
| 7 | addi | t0 | zero | 0 | t0 = 0 |
| 8 | addi | t8 | a1 | -1 | t8 = a1 - 1 = 1 - 1 = 0 |
| 9 | slt | t9 | t1 | t8 | t9 = 0 |
| 10 | beq | t9 | zero | outer | t9 == 0 (miss) |
| 11 | sll | t0 | t0 | 0 | (bds) |
| 12 | beq | t0 | zero | exitout | t0 == 0 (miss) |
| 13 | sll | t0 | t0 | 0 | (bds) |
| 14 | jr | ra |  |  |  |
| 15 | sll | t0 | t0 | 0 | (bds) |

I've marked the instructions in the branch delay slots with (bds).

Your question doesn't describe the microarchitecture so we assume it is the five-stage MIPS pipeline commonly used in education. It has five stages; instruction fetch (F), decode (D), execute (X), memory (M), and writeback (W). We assume bypasses from execute to decode for arithmetic instructions and from decode to fetch for branches (so that branches never stall). I have indicated stalls with "!":

| # | INSN | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| 1 | `addi t0, zero, 1` | F | D | X | M | W |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
| 2 | `addi v0, zero, 0` |  | F | D | X | M | W |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
| 3 | `beq t0, zero, exitout` |  |  | F | D | X | M | W |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
| 4 | `sll t0, t0, 0` |  |  |  | F | D | X | M | W |  |  |  |  |  |  |  |  |  |  |  |  |  |
| 5 | `addi t1, zero, 0` |  |  |  |  | F | D | X | M | W |  |  |  |  |  |  |  |  |  |  |  |  |
| 6 | `add t2, zero, a0` |  |  |  |  |  | F | D | X | M | W |  |  |  |  |  |  |  |  |  |  |  |
| 7 | `addi t0, zero, 0` |  |  |  |  |  |  | F | D | X | M | W |  |  |  |  |  |  |  |  |  |  |
| 8 | `addi t8, a1, -1` |  |  |  |  |  |  |  | F | D | X | M | W |  |  |  |  |  |  |  |  |  |
| 9 | `slt t9, t1, t8` |  |  |  |  |  |  |  |  | F | ! | D | X | M | W |  |  |  |  |  |  |  |
| 10 | `beq t9, zero, outer` |  |  |  |  |  |  |  |  |  |  | F | ! | D | X | M | W |  |  |  |  |  |
| 11 | `sll t0, t0, 0` |  |  |  |  |  |  |  |  |  |  |  |  | F | D | X | M | W |  |  |  |  |
| 12 | `beq t0, zero, exitout` |  |  |  |  |  |  |  |  |  |  |  |  |  | F | D | X | M | W |  |  |  |
| 13 | `sll t0, t0, 0` |  |  |  |  |  |  |  |  |  |  |  |  |  |  | F | D | X | M | W |  |  |
| 14 | `jr ra` |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | F | D | X | M | W |  |
| 15 | `sll t0, t0, 0` |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | F | D | X | M | W |

The answer claims that there are no stalls due to data hazards. That's, afaict, incorrect; both instruction 9 and 10 need to stall due to RAW hazards. We can compute the total number of cycles with $n + (p - 1) + s$, where $n$ is the number of instructions, $p$ the number of pipeline stages, and $s$, the number of stall cycles, so $15 + (5 - 1) + 2 = 21$. I'm not sure why there are four instruction cache misses or why the instruction cache miss penalty is 10 cycles, but if we account for that we get $(40 + 21) / 15 \approx 4.06$ CPI.

---
Tags: computer-architecture, cpu-pipelines, c, assembly, mips
---


title: Min sum vertex cover complexity proof

text:
# Question
Title: Min sum vertex cover complexity proof
One version of the minimum sum vertex cover \[1\] is the following problem:

We are given an undirected graph $G(V, E)$, and let $n = |V|$. The task is to find a bijective function $\psi: V \rightarrow \lbrace{1, 2, \dotsc, n \rbrace}$ such that the following objective is minimized: $\sum\_{(u, v) \in E} \min(\psi(u), \psi(v))$.

\[1\] & \[2\] implicitly claim that the problem is NP-Complete to solve optimally, however they do not point to any references that prove the claim. I could not find a source myself after searching a lot on the internet. Can someone point me to the proof of the problem or provide hints if you happen to know.

References

\[1\] Gera, R., Horton, S., Rasmussen, C. and Stanica, P., 2006. Results on the min-sum vertex cover problem. Congressus Numerantium, 178, pp.161-172.

\[2\] Feige, U., Lovász, L. and Tetali, P., 2004. Approximating min sum set cover. Algorithmica, 40, pp.219-234.

# Answer
> 1 votes
As mentioned in the comments  proves this in Theorem 14 with the slightly stronger claim: "For some $\epsilon'\>0$, it is NP-hard to approximate min sum vertex cover within ratios better than $1+\epsilon'$."

---
Tags: complexity-theory, vertex-cover, vertex-labeling
---


# Question
Title: Main subjects to learn Artificial Intelligence in CS
In my PhD, I will work with ML models. However, I will only use ready-made models as a tool, but I want to delve deeper into Artificial Intelligence not just to use ready-made models, but to understand how it works and create my own AI.

I noticed that most of the content I found talked more about how to use ready-made tools. I am interested in, over time, being the person who 'makes the medicine' and not just the one who 'takes it'.

I was considering doing another degree in Computer Science, but I was hesitant. Doing another degree to learn about AI at the same time as my PhD, I was thinking about using this time I will have during my postgraduate studies to study independently.

I found this free degree in CS, I took a look at the schedule and I don't know if everything is necessary to have this level of knowledge in AI.

Because, at least in Chemistry, many subjects are unnecessary to learn some topics.

Could you help me with what subjects I should take?

# Answer
A course in multivariable calculus is useful for understanding back-propagation.

Some familiarity with a programming language like Python would helpful to understanding how it all works, and for actually running some common libraries.

A course in statistics would be useful as well!
> 0 votes

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


# Question
Title: A Turing machine for which it is impossible to predict whether it halts or not on a fixed input
The halting problem is undecidable, i.e. $\not \exists$ $M$ Turing machine s.t. for every $(M\_0,w\_0)$ input where $M$ is the description of a Turing machine and $w\_0$ is an input word, the output of $M$ is "$1$" if $M\_0$ will halt on $w\_0$ and "$0$" if it will not.

From this statement only, it does not follow that there must be an ($M\_0,w\_0$) pair for which it is impossible to predict if $M\_0(w\_0)$ halts or not. It only means there is no general way to decide this question for all ($M\_0,w\_0$) pairs.

So my question is the following: Does there exist a ($M\_0,w\_0$) pair for which it is known that it is impossible to predict whether $M\_0(w\_0$) halts or not? If yes, is there a known example or construction for an ($M\_0,w\_0$) pair such that?

# Answer
For any specific machine $M\_0$ and input $w\_0$, there is a machine that decides whether $M\_0$ halts on $w\_0$. Indeed, one of the following machines works:

* The machine that outputs "Yes".
* The machine that outputs "No".

However, there is no program $P$ that given *arbitrary* $M$ and $w$ produces a machine $T\_{M,w}$ that correctly decides whether $M$ halts on $w$, since such a program can be used to solve the halting problem. Indeed, given $M$ and $w$, run $P$ on the input $\langle M,w \rangle$, and then run the machine $T\_{M,w}$ that $P$ outputs.

---

We can go further, and for every reasonable proof system $\Pi$ (one for which Gödel's incompleteness theorems apply) which is sound and consistent, we can construct a machine $M\_\Pi$, accepting no input, such that $\Pi$ cannot "decide" whether $M\_\Pi$ halts, in the sense that there is neither proof that $M\_\Pi$ halts nor a proof that it doesn't halt. The machine $M\_\Pi$ simply enumerates all proofs in $\Pi$, halting if there is a $\Pi$-proof of contradiction. Since $\Pi$ is consistent, $M\_\Pi$ doesn't halt, and so, since $\Pi$ is sound, it cannot prove that $M\_\Pi$ halts. On the other hand, $\Pi$ cannot prove that $M\_\Pi$ doesn't halt, since this contradicts Gödel's second incompleteness theorem.

(I hope that I got this proof right — mathematical logic is often quite confusing.)
> 3 votes

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


# Question
Title: We know that there is an algorithm for a problem that decides it in $\Omega(2^n)$ time. We know that it is not in P class, or we cannot decide?
I know that exists problems that surely cannot be decided in polynomial time because P class doesn't equal with EXPTIME (for example Go, generalized chess etc.). But I assume that there may be problems for which we currently only have an algorithm with exponential time complexity and yet can be solved in polynomial time.

# Answer
Well, there is a sorting algorithm that takes $\Omega(n!)$ steps on average: Create a random permutation of your data, check whether the resulting array is sorted, and repeat until it is sorted. But obviously the problem can be solved in $O(n^2)$ and practically in $O(n \log n)$.
> 1 votes

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


# Question
Title: Language of Turing Machines that only accept their own encodings
Is the language $L = \\{\langle M\rangle|L(M)=\\{\langle M\rangle\\}\\}$ recursive?

I've been trying for hours to find a way to prove or disprove that it is.

My first attempt was to show it wasn't recursive using Rice's theorem but I'm not sure if one can create a Turing machine that only accepts it's own encoding? How would it figure out it's own encoding at run time?

# Answer
You can reduce K to L:

Let

K = {e | e's Turing machine halts on e}

Let f(x,y) be

f(x,y) = Code of the following machine:

For any input w:

Run y's Turing machine on y.

If w = x, accept. Otherwise reject.

Here by Recursion theorem, We know there is some computable function s which:

f(s(y),y) = s(y)

Also by proof of Recursion theorem, we know that s(y) can be computably constructed from f((which is computable)) and y. So we can compute s(y) from y.

Here by definition of f, we know that if M is the Turing machine encoded by s(y) Then:

L(M) = {s(y)} if and only if y belongs to K.

So we reduced K to L. Since K is not recursive, L is not recursive either.

For your second question about how to construct a Turing machine which only accepts its own code. I refer you to Recursion theorem and the following question:

Understanding Whether a Set is an Index Set

I hope this can help you.
> 1 votes

---
Tags: turing-machines, computability, proof-techniques
---


# Question
Title: Finding all stable matchings in stable marriage problem
I need to find an algorithm for a modified version of the stable marriage problem. In particular, I need to find all possible stable matchings and not only one (unlike what the Gale-Shapley algorithm does). The only solution I have is to recursively enumerate all the possible matchings, discarding the recursive branches which do not satisfy the conditions. This algorithm has a complexity of **O(n!)**, with n being the number of items in each set.

I found this similar question that shows that the upper bound to the number of solutions is exponential. Is there any better algorithm than the one I have so far?

In the context of similar questions, this paper by Gusfield comes up. However, it solves a different problem.

# Answer
> 1 votes
I worked with OP on this problem. This is what we found.

The problem solved by Gusfield in the paper "Three Fast Algorithms for Four Problems in Stable Marriage" does indeed include a solution to this problem. It should be noted, however, that the algorithm for building the graph of rotations contains an error (also, the paper in general is very hard to parse). We corrected that error.

The algorithm proposed there requires linear time for each stable matching. C. Palmer and D. Pálvölgyi find in "At most 3.55n stable matchings" that the number of stable matchings is O(3.55^n). Putting these two things together, we find that Gusfield's algorithm takes **O(n * 3.55^n)**.

---
Tags: algorithms, complexity-theory, np-hard, combinatorics, matching
---


# Question
Title: Proof or disproove $L_1 , L_2 \in RE \setminus R $ such that $ L_1 \cup L_2 \in R $ and $ L_1 \cap L_2 \in R $
> Proove or Disproove $ \exists L\_1 , L\_2 \in RE \setminus R $ such that $ L\_1 \cup L\_2 \in R $ and $ L\_1 \cap L\_2 \in R $

I tried to use the languages

the union is $ \sigma^\* $ and the intersection is empty language but I am really not sure if that really answer the question

# Answer
Let us assume that $L\_1$ and $L\_2$ are both computably enumerable, and that $L\_1 \cap L\_2$ and $L\_1 \cup L\_2$ are decidable. I claim that $L\_1$ is decidable, too.

Given some $w \in \Sigma^\*$, I want to determine whether $w \in L\_1?$. I proceed as follows:

1. First, I test whether $w \in L\_1 \cup L\_2$. If not, I can stop and answer **no**.
2. Second, I test whether $w \in L\_1 \cap L\_2$. If yes, I can stop and answer **yes**.
3. Otherwise, I know that $w$ belongs to exactly one of $L\_1$ and $L\_2$. I run the semi-decision procedures I have for these in parallel, until one of them stops (which has to happen). If I learn that $w \in L\_1$, I answer **yes**. If I learn that $w \in L\_2$, I answer **no**.
> 2 votes

---
Tags: formal-languages, turing-machines
---


title: How complement of ETM is semidecidable

text:
# Question
Title: How complement of ETM is semidecidable
If ETM = {＜M＞ ∣ M is a Turing Machine and L(M) = ∅}, how can I prove that the complement of ETM is semi-decidable?

# Answer
First, you have to find a way to enumerate the elements of $\overline{ETM}$. One way is to create a procedure which, in stage $n$, tests the first $n$ Turing machines for the first $n$ inputs for $n$ steps, outputing the code of a machine if it finds an input it accepts. If $M\in\overline{ETM}$, then, eventually, your procedure will find $M$, the input it accepts, and be in a stage where it simulates $M$ for enough steps.

Now, to see that it is semi-decidable and not decidable, you can, for example, find a reduction from the Halting problem to ETM. One possible way is to, given a machine $M$, construct a machine $M'$, which accepts an input $x$ whenever $M$ accepts $0$. Then, $L(M')$ is either $\mathbb{N}$ or $\emptyset$ and $M\in HALT$ if and only if $M'\in\overline{ETM}$.

Are you familiar with these constructions?
> 1 votes

# Answer
Consider an alphabet $\Sigma$, and let $w\_1, w\_2, w\_3, \ldots$ denote all words in $\Sigma^\*$ in *minlex* order, that is, for all $i \< j$, one of the following holds: (1) either $|w\_i| \< |w\_j|$, or (2) both $w\_i$ and $w\_j$ are of the same length, yet $w\_i$ comes before $w\_j$ in the lexicographic order. For example, $b \<\_{minlex} aa \<\_{minlex} ab$.

Now to show that $\overline{E\_{TM}} \in \text{RE}$, we define a TM $T$ that, on input $\langle M\rangle$, simulates the run of $T$ on all words in $\Sigma^\*$ in parallel, and checks if $M$ accepts at least one word, where $\Sigma$ is the input-alphabet of $M$. Formally, $T$ works in iterations $i = 1, 2, \ldots$, where in iteration $i$, $T$ simulates the run of $M$ on the words $w\_1, w\_2, \ldots, w\_i$, for $i$ steps each. If $M$ accepts one of the words $w\_1, w\_2, \ldots, w\_i$ within $i$ steps, then $T$ halts and accepts, otherwise, $T$ proceeds to the next iteration. So in the $i$'th iteration, we simulate the run of $M$ on the first $i$ words in minlex order.

Regarding correctness, if $T$ accepts in some iteration $i$, the clearly, one of the words $w\_1, w\_2, \ldots, w\_i$ is accepted by $M$ and thus $L(M)\neq \emptyset$. Conversely, if $L(M)\neq \emptyset$, then there is $j\geq 1$ such that $w\_j\in L(M)$. Let $t$ denote the number of steps that takes the machine $M$ to accept $w\_j$, and consider $i = \max(t, j)$. Clearly, $w\_j$ is one of the first $i$ words in minlex order. If $T$ survived all iterations and reached iteration number $i$ and got to the point where it simulates the run of $M$ on $w\_j$ for $i \geq t$ steps, then it halts an accepts as $M$ accepts $w\_j$ within $t$ steps, in particular, within $i$ steps.

**Notes:**

1- The fact that we traverse all words in $\Sigma^\*$ in minlex order is crucial. For example, if $\Sigma = \\{ a, b\\}$, and we traverse all words following a lexicographic order, then if $M$ accepts only the input $b$, we will never find that out, as there are infinitely many words that start with $a$.

2- Note that $T$ need not halt, when $L(M)$ is empty, but this is okay as we're showing that $\overline{E\_{TM}} \in \text{RE}$. In fact, we cannot do better as the language is not decidable.
> 0 votes

---
Tags: turing-machines, reductions, semi-decidability
---


# Question
Title: proof or disproof if $ L_1 \subseteq L_2 $ then $ L_1 \leq L_2 $
proof or disproof

if $ L\_1 \subseteq L\_2 $ then $ L\_1 \leq L\_2 $

I tried to think with HP and the empty language because HP is in RE and the empty language is in R but how do I prove this does not always happen? I don't understand whats the formal way to write it down

# Answer
> 2 votes
The claim essentially says that if $L\_1$ is included in $L\_2$, then $L\_2$ is harder than $L\_1$, which clearly cannot be correct as the biggest language w.r.t containment is very simple. So you can take $L\_1$ to be the halting-problem, and $L\_2$ to be $\Sigma^\*$. Proceed from there.

---
Tags: formal-languages, turing-machines
---