Tag Info

Hot answers tagged

2

All NP-Complete problems are already solvable, they're just intractable. That said, if one NP-Complete problem is proven to be on P, then all of them are on P and thus, tractable. This happens because all NP problems can be reduced one into another (they are essentially the same).


2

The notation $f_x$ denotes a separate function specified at each node $x$. For each $x$, the transfer function $f_x$ of node $x$ must be monotone. On this, see e.g. Wikipedia. The condition for monotonicity is $x\le y\implies f(x)\le f(y)$. If you think of lattices as algebraic structures rather than partial orders, see, again, Wikipedia for the connection. ...


2

Maybe this curiosity qualifies? ... The following three functions (which map naturals to naturals) form a "complete basis" for universal computation: $$\begin{align} f_0(n) & = n + [n>0][n\ \text{even}]\ 2^{|n|_2} \\ f_1(n) & = n + [n>0][n\ \text{even}]\ 2^{|n|_2 + 1}\\ f_2(n) & = [n>0] \left\lfloor\frac{n-1}{2}\right\rfloor ...


1

It is not unique, even up to permutation of the numbers. Note the sum of the squares of the positions just gives a constant depending on the length of the string. We know $\sum_{i=1}^ni^2=\frac 16n(n+1)(2n-1)$, so in your case it is $45$. The simplest example that fails is $(0,0,0,2)$ and $(1,1,1,1)$. Another is $(3,4)$ and $(0,5)$ To get a provably ...


1

Let Vertex-Cover = $\{ <G, k> : G$ has a vertex cover of size k$\}$ Given an instance $<G(V, E), k>$ of Vertex-Cover construct an instance $<G'(V', E'), k+2>$ of $K_4$-Cover: 1) Set $V' = V \cup \{x, y\}$. 2) Set $E' = E$ 3) Add the edge (x, y) to E' 4) For each edge $(u, v)$ in E', add the edges $(x, u), (x, v), (y, u), (y, v)$ ...


1

On your first question: That sentence is false; the text itself goes on to state in the very next paragraph under which circumstances the method can be used for singular potentials. The case in which it can't be used is with targets and sources spatially intermingled and a singular potential, because in this case there's no single expansion that will work ...


1

It depends on what kind of mixing you denote with "$+$". If you overlay layers then it is not even a commutative operation (e.g., if both are opaque, the top layer always wins). To really "mix" we should consider what we expect to happen with a coloured background behind the single and the mixed layer. I assume that $(r,g,b,a)$ covering $(r',b',g')$ results ...



Only top voted, non community-wiki answers of a minimum length are eligible