# All Questions

29,681 questions
465 views

### Why can L3 caches hold only shared blocks?

In a recent CACM article [1], the authors present a way to improve scalability of shared and coherent caches. The core ingredient is assuming the caches are inclusive, that is higher-level caches (e....
144 views

### Problem with the definition of P

In "Introduction to Algorithms: 3rd Edition" there is Theorem 34.2, which states $P = \{ L \mid L \text{ is accepted by a polynomial-time algorithm} \}$ "Accepted in polynomial-time" is defined by:...
8k views

### Time complexity formula of nested loops

I've just begun this stage 2 Compsci paper on algorithms, and stuff like this is not my strong point. I've come across this in my lecture slides. ...
278 views

711 views

### Micro-optimisation for edit distance computation: is it valid?

On Wikipedia, an implementation for the bottom-up dynamic programming scheme for the edit distance is given. It does not follow the definition completely; inner cells are computed thus: ...
2k views

### Optimization problem vs decision problem - reduction

Assume we have an optimization problem with function $f$ to maximize. Then, the corresponding decision problem 'Does there exist a solution with $f\ge k$ for a given $k$?' can easily be reduced to ...
2k views

### Examples of undecidable problems whose intersection is decidable

I know that given two problems are undecidable it does not follow that their intersection must be undecidable. For example, take a property of languages $P$ such that it is undecidable whether the ...
575 views

### Showing that the set of TMs which visit the starting state twice on the empty input is undecidable

I'm trying to prove that $L_1=\{\langle M\rangle \mid M \text{ is a Turing machine and visits } q_0 \text{ at least twice on } \varepsilon\} \notin R$. I'm not sure whether to reduce the halting ...
346 views

### How to implement simulation on two LTSs?

Does any one know how to implement the simulation relation on two labelled transition systems (LTS)? I know how to do it for branching bi-simulation. The signature refinement theorem is used for ...
12k views

### Generalised 3SUM (k-SUM) problem?

The 3SUM problem tries to identify 3 integers $a,b,c$ from a set $S$ of size $n$ such that $a + b + c = 0$. It is conjectured that there is not better solution than quadratic, i.e. $\mathcal{o}(n^2)$....
841 views

206 views

428 views

### Are regular languages closed under sort (Parikh image)?

Assume $L$ is a regular language over an ordered alphabet. Is the language built by taking every word in $L$ and sorting it always a regular language?
595 views

### Can top SAT-solvers factor easy numbers?

Modern SAT-solvers are very good at solving many real-world examples of SAT instances. However, we know how to generate hard ones: for instance use a reduction from factoring to SAT and give the RSA ...
332 views

### Choosing an element from a set satisfying a predicate uniformly at random in $O(1)$ space

We are given a set of objects, say integers, $S$. In addition, we are given a predicate $P$, for example $P(i): \Leftrightarrow i \geq 0$. We don't know in advance how many elements of $S$ satisfy the ...