New answers tagged

3

Following up on the 2012 paper linked above, the work on RRB vectors has since been extended and published in ICFP'15. RRB vector: a practical general purpose immutable sequence http://dl.acm.org/citation.cfm?id=2784739


3

Here is an example of something fairly contrived, but which might be a good starting place for reductions to other problems: Input: a boolean formula $\phi$ and a satisfying assignment $x$. Goal: find a satisfying assignment $y$ to $\phi$ which has as few variables set to true as possible, but at least as many variables set to true as in $x$ ...


1

I was finally able to find a reference (not necessarily the oldest one) for the efficient simulation of Turing machines by means of RAMs without indirect addressing (nor binary shift): Takumi Kasai, Computational complexity of multitape Turing machines and random access machines, Publications of the Research Institute for Mathematical Sciences 13, 469–...


3

The classic reference for these kind of results is the survey by Peter van Emde Boas, "Machine Models and Simulations", the first chapter of Handbook of Theoretical Computer Science, Vol. A. For simulations between RAM and Turing machines see Theorems 2.5 and 2.6, pp. 26--27. It also contains pointers to historic references.


0

When expressed in first order logic, any proof of the pigeonhole principle for fixed n is exponential in length. However, with arithmetic the proof can be expressed much more concisely. The success of SMT solvers has come from backing off from the abstract model of reducing problems to SAT, allowing richer theories to greatly reduce the amount of ...


9

Dorit Dor and Uri Zwick ("Selecting the Median", SODA 1995, pp 28-37) use green factories and analyze their amortized production costs.


0

This paper: Man Lung Yiu, Dimitris Papadias, Nikos Mamoulis, Yufei Tao: Reverse Nearest Neighbors in Large Graphs. IEEE Trans. Knowl. Data Eng. 18(4): 540-553 (2006) calculates the kNN of each vertex belonging to the target set. The proof can be found on Section 4.1 and algorithm All-NN(k).


2

Temporal Planning with concurrent actions is EXPSPACE-complete, as shown in J. Rintanen, “Complexity of Concurrent Temporal Planning,” Proceedings of the 17th International Conference on Automated Planning and Scheduling, pp. 280–287, 2007 The problem is roughly the following (beware in the paper above it is defined in a different but equivalent ...


0

Notation: Let $X = (V,E)$ be graph, $e = (v_1, v_2) $ an edge of $X$. The vertex set $V_k$ be the set of vertices of distance $k$ from $e$, and let $h$ be the height of $X$. According to definition of $V_k$, $V= V_0 \cup V_1 \dots V_h$ and $V_{(h+1)}= \emptyset$. Let, subset $E_k$ of edges of $X(0 \leq k \leq h)$ is defined as- $E_k = \{ (u,w) | u \in ...


3

As you mentioned that "My main goal is to solve different kinds of games on these graphs, but I'm curious about other problems too", you can have a look at the thesis by Morgan Chopin -- "Optimization problems with propagation in graphs: Parameterized complexity and approximation" (https://tel.archives-ouvertes.fr/tel-00933769). Here, author shows some ...



Top 50 recent answers are included