# Tag Info

0

Any absorbing node $n$ will have to be either accepting or not (so that either everything or nothing is accepted once $n$ is entered). If the graph has more than two absorbing nodes, then some of them will end up equivalent for any choice of labeling and accepting set. More generally, for any strongly connected graph $H$ there is only a finite number ...

1

Regarding (1), the problem is not strongly NP-hard, c.f. Corollary 1 in here: Papadimitriou, C. H. (1981). On the complexity of integer programming. Journal of the ACM, 28(4), 765-768. Regarding (2), the problem obviously lies in #P if all constants are positive. There is also a #P-complete version of SubsetSum, which almost fits into your problem instance ...

0

For what it's worth, it turns out that this is how quantum computing works. When it does it's computations, it does so on cubits which can be 1, 0, or a superposition of 1 and 0. If you use superpositional bits, it means that it does the computations on all possible bit value permutations. It's only when the result is "observed" that it collapses into an ...

7

If you do not allow subtraction, then you are in the semi-group/monotone setting and there are tight lower bounds known for many natural matrices $M$ that come from computational geometry. (The interest in computational geometry is that range counting can be encoded as matrix-vector multiplication.) For example, the following lower bounds on the size of ...

9

This is essentially the problem that motivated Valiant to introduce matrix rigidity into complexity (as far as I understand the history). A linear circuit is an algebraic circuit whose only gates are two-input linear combination gates. Every linear transformation (matrix) can be computed by a linear circuit of quadratic size, and the question is when can ...

6

A natural $\text{NEXP}^{\text{NP}}$-complete problem is deciding a sentence of Presburger arithmetic with an $\exists^*\forall^*\exists^*$-quantifier prefix (as shown here). Further complete problems related to database theory have been studied here.

2

If you allow randomization, the CountMin (CM) sketch can be used with weights without modification, and can also handle negative weights. When all weights are positive, the standard analysis of CM shows that with a sketch of size $O(\varepsilon^{-1}\log 1/\delta)$ you can compute a $\tilde{w}_i$ so that $\tilde{w_i} \geq w_i$ always, and $\tilde{w}_i \leq ... 2 Here's a generic randomized solution. (Do we even have deterministic solutions in the unweighted case? Don't Space Saving and Batch Decrement both need hash maps?) This is probably not the ideal solution, but it's a start. Weighted Heavy Hitters Algorithm. Input:$S=\{(\text{id}_i,\text{weight}_i)\}_{i=1}^N$a weighted stream. 1. Create an unweighted ... 2 As J.-E. Pin pointed out my question deals with insertion. I have found another source which I will post here for anyone interested. L.Kari. On Insertion and Deletion in Formal Languages. Ph.D. Thesis, University of Turku, 1991. Here is Part I and Part II of the thesis. From what I can tell this is the original source for the study of insertion. 18 According to the introduction of [1], The complexity of determining if a single polyomino tiles the plane remains open [2,3], and There is an undecidability proof for sets of 5 polyominoes [4]. [1] Stefan Langerman, Andrew Winslow. A Quasilinear-Time Algorithm for Tiling the Plane Isohedrally with a Polyomino. ArXiv e-prints, 2015. arXiv:1507.02762 ... 13 An extended comment: a recent paper by Demaine & al. proves that one tile is enough to simulate an arbitrary computation: Erik D. Demaine, Martin L. Demaine, Sándor P. Fekete, Matthew J. Patitz, Robert T. Schweller, Andrew Winslow, Damien Woods; One Tile to Rule Them All: Simulating Any Turing Machine, Tile Assembly System, or Tiling System with a ... 1 I was able to find an application of combinatorial game theory in cryptography. See the link here 10 The number field sieve has never been analyzed rigorously. The complexity that you quote is merely heuristic. The only subexponential algorithm which has been analyzed rigorously is Dixon's factorization algorithm, which is very similar to the quadratic sieve. According to Wikipedia, Dixon's algorithm runs in time$e^{O(2\sqrt{2}\sqrt{\log n\log\log n})}$. ... 10 As far as I know the NP-completeness of computing the treewidth of a planar graph is still open. The most recent reference I know is a survey by Bodlaender from 2012 called `Fixed-Parameter Tractability of Treewidth and Pathwidth' that appeared in the festschrift for Mike Fellows' 65th birthday. The problem is listed in the conclusion of the survey. 1 the question is challenging in its broadness & disclaimer of vagueness however some areas of research can be cited that impinge on it. roughly the 1st half of the question is about unreliable models of computation and the 2nd half is asking about a "hierarchy" built out of such unreliable systems. a general trend in CS and computer engineering is that ... 3 Rabie introduced the model of "Rusted Turing Machines" in his thesis: The Power of Weaknesses:What can be computed with Populations, Protocols and Machines (Chapter 7). The idea is that there is a restriction on the number of time the TM can change its internal state because of decay. Rabie introduced the class$Piv(f(n))$, the class of Turing Machines that ... 5 It's difficult to know what you mean because you're staying at a level that's so high that there's nothing interesting. Specific cases could be very interesting, but the basic idea that having computed a function for one input can make it easier to compute it for other inputs is too general. It may be that you have a function$f$such that having computed ... 3 This is basically what dynamic data structures and streaming algorithms are about. A few links, off the top of my Google: High performance data structure for streaming graphs Mihai Patrascu's thesis Dynamic Integer Sets with Optimal Rank, Select, and Predecessor Search Dynamic shortest paths and transitive closures For example, a dynamic data structure ... 3 Many times, we can use Linearization of a function to approximate values near a point to reasonable accuracy. A single answer is generated with expensive algorithms (e.g.,$\sqrt{2}\approx1.41421...$) then nearby answers are generated from that answer with a simple algorithm (e.g.,$\sqrt{x}\approx0.35355x+0.70711, x\approx2$. Using expensive algorithms, ... 1 This paper describes a new form of incremental computation: taking derivatives on data-type-valued functions (e.g. List-valued functions). http://www.informatik.uni-marburg.de/~pgiarrusso/papers/pldi14-ilc-author-final.pdf 16 I'm not sure, but you might be talking about what has been termed incremental computation. The key idea behind incremental computation is to program in a way such that the program responds to input changes by updating its output while only re-evaluating those portions of the program affected by the change. Incremental computing is feasible in situations ... 4 You seem to be asking about incremental computation. In general, it takes the following form: we have a function$f$, which is expensive to compute. We have computed$f(x)$for a single input$x$. Now we want to compute$f(x')$, for a second input$x'$where$x'$is somehow "similar" to$x\$. It'd be nice if we could take advantage of the fact that we ...

Top 50 recent answers are included