Thomas Klimpel
  • Member for 9 years, 8 months
  • Last seen this week
Is there a computationally reasonable algorithm for generating a set of polygons from a set of 2d points?
13 votes

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 ...

View answer
Literature about a naive approach to graph isomorphism by inspecting polynomials of adjacency matrices
Accepted answer
12 votes

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 ...

View answer
What would be the real-world implications of a constructive $P=NP$ proof?
10 votes

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

View answer
Smallest class of automata model whose corresponding language class contains CFL and is closed against (dis)allowing nondeterminism in the model
Accepted answer
10 votes

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 ...

View answer
Reference book for Parallel Computing and Parallel algorithms.
9 votes

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 ...

View answer
Which research languages have a stronger typesystem than Haskell and why?
9 votes

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 ...

View answer
Is there a data-structure for semilattices similar to a tree data-structure?
Accepted answer
9 votes

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 ...

View answer
Solve parity game in polynomial time?
8 votes

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 ...

View answer
Is a LBA with stack more powerful than a LBA without?
Accepted answer
8 votes

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$...

View answer
What was going on before PAC learning
Accepted answer
8 votes

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 "...

View answer
What does "AC0 many-one reduction" mean?
6 votes

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 ...

View answer
Reference request: Category theory as it applies to type systems
6 votes

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 ...

View answer
How to prove P$\neq$NP?
6 votes

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 ...

View answer
What are appropriate isomorphisms between formal languages?
Accepted answer
6 votes

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 ...

View answer
Will floating point code return the same arithmetical results on two different computers?
Accepted answer
6 votes

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 ...

View answer
Theoretical machines which are more powerful than Turing machines
5 votes

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 ...

View answer
Relationship between formal system and formal languages
Accepted answer
5 votes

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 ...

View answer
Lowest common ancestor similar algorithm for a graph
5 votes

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 ...

View answer
What are the examples of problems which first had large polynomial time complexity algorithms but later the complexity was reduced significantly?
4 votes

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 ...

View answer
in refutation (resolution) can we use a clause that have been resolved
Accepted answer
4 votes

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 ...

View answer
Subgraph isomorphism reduction from the Clique problem
4 votes

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 ...

View answer
Relationship of algorithm complexity and automata class
4 votes

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 ...

View answer
What's the difference between Adaptive Control and a Kalman Filter?
Accepted answer
4 votes

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 ...

View answer
Have non-regular language classes of infinite words been studied?
Accepted answer
4 votes

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 ...

View answer
Non-erasing Turing machines and loss of generality
4 votes

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 ...

View answer
Mathematical optimization on a noisy function
4 votes

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
Has there been any more progress on P vs. PSPACE compared to P vs. NP?
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\...

View answer
Is there a generic way to parallelize algorithms?
Accepted answer
3 votes

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 ...

View answer
NP with a parallelism model?
Accepted answer
3 votes

Your description of NP is still missing the accept criterion. For example you might decide to accept the input exactly in case all computation paths accept. This would give you the class coNP instead ...

View answer
Is every undecidable language reducible to any other undecidable language?
3 votes

You are probably thinking about undecidable languages which are computably enumerable. Otherwise, the diagonalization technique described in answers to similar questions would have provided simple ...

View answer