Yes, there are even algorithms which are able to satisfy additional constraints. It can occur as a subtask during mesh generation. The vanilla algorithm is the Delaunay triangulation, which is closely ...

Yes, there is such a theorem, more or less. It basically states that the k-dimensional Weisfeiler-Lehman procedure subsumes (i.e. dominates) all known combinatorial approaches to graph isomorphism ...

Even without P=NP, today's computers are unbelievable powerful. 12873891274647018937561708356916501047777612653914909670721635802187 can be factored by a single computer in less than a second. For ...

The notion of a PDA can be generalized to an $S(n)$ auxiliary pushdown automaton ($S(n)$-AuxPDA). It consists of a read-only input tape, surrounded by endmarkers, a finite state control, a read-write ...

Also wanted to know that from which reference book or papers are the concepts in the udacity course on Parallel Computing taught...? The History of Parallel Computing goes back far in the past, where ...

The research language Clean has a better type system than Haskell, because it has uniqueness types. The ideas behind uniqueness types are closely related to linear logic, which is closer to the ...

This blogpost on lattice theory has a useful reference section, which contains among others "Lattice Theory with Applications" by Vijay K. Garg. Chapter 2 "Representing Posets" describes some data ...

The state of the art for solving parity games is now quasipolynomial time. Here are references: Deciding Parity Games in Quasipolynomial Time (PDF), by Cristian S. Calude, Sanjay Jain, Bakhadyr ...

Theorem The following are equivalent. $L$ is accepted by a deterministic LBA with stack $L$ is accepted by a nondeterministic LBA with stack $L$ is in $\operatorname{DTIME}(c^n)$ for some constant $c$...

References are highly appreciated. An author is expected to address the question of the context and relevance of his results at the begin of his publication. I just skimmed over the introduction of "...

The "what is" part of the question was succinctly answered by D.W.: An AC0 many-one reduction is a many-one reduction that can be implemented by an AC0 circuit. It's just like a polynomial-time ...

Learning category theory is a huge time investment, and the question whether it is worth it is very valid. I still struggle with this too, and I already know why I should learn it. I wrote: I liked ...

My question in short: If I believe that P=NP, you would say "then show your algorithm that solves an NP problem in polynomial time!". Don't forget that you still have to prove that your algorithm ...

Has my problem already been solved, so that I just need to read the right references? The theory of abstract family of languages is relevant. For example, the morphisms defined by finite state ...

As long as you execute the same machine code on the different machines and as long as the settings for the floating point unit are identical, you will get identical results. However, you cannot ...

One theoretical weakness of a Turing machine is its predictability. An all powerful and omniscient opponent could exploit this weakness when playing some game against the Turing machine. So if a ...

In my opinion, a formal system should have A well defined set of symbols. A well defined grammar, which tells how well-formed formulas are constructed out of the symbols. One or more well defined ...

If the lowest common ancestor of two types always exists and is unique, then your structure is a join-semilattice. Computing the lowest common ancestor is possible, but the worst case runtime ...

Khachiyan's ellipsoid method (1979) for linear programming famously proved the polynomial-time solvability of linear programs, even so the older simplex algorithm is much faster than the ellipsoid ...

suppose we've resolved C1 and C2 to C5, can we resolve C1 with C5 or C2? No, not really. If C1 and C2 can be resolved in more than one way, then all those resolvents are tautologies. And if C1 can be ...

The decision version of the clique problem asks whether a given graph $G$ contains a complete graph with $k$ vertices as subgraph. The wikipedia article just explains why the decision version of the ...

Is there a direct relationship between the complexity of an algorithm (such as best / worst case of quick sort), and class of automata that can implement the algorithm. The question which class of ...

The Kalman Filter only estimates the current state variables of the system, but doesn't (try to) influence the future state of the system. So a Kalman filter alone is just adaptive observation. I'm ...

We have the following MSO characterization of regular nested word languages: Regular languages over nested words are exactly the set of languages described by Monadic second-order logic with two ...

Your definition of non-erasing Turing machine is "not the common one". Turlough Neary nicely summarizes early definitions and results for non-erasing Turing machines: Non-erasing Turing machines ...

One could replace the exact function $f(x,p)$ by the noisy function $f(x+\Delta x, p + \Delta p)$, where $p$ is an artificial parameter used to describe the noise dependency such that $\Delta x$ and $\... View answer 4 votes To prove that$\mathsf{NP}^A=\mathsf{coNP}^A$for a "sufficiently natural"$\mathsf{PSPACE}$oracle$A$implies$\mathsf{NP}^A=\mathsf{PSPACE}$should be much easier than to prove$\mathsf{P}\neq\...

No, there cannot be such a generic method to produce algorithms $A_{in}, A_{out}, A_{1},\dots, A_k$ with the requested properties. The basic problem is that the requested parallel algorithm only uses ...