user avatar
user avatar
user avatar
Thomas Klimpel
  • Member for 10 years, 1 month
  • Last seen this week
18 votes
1 answer
393 views

Is there an O(n log n) algorithm for 4D line simplification?

16 votes
1 answer
5k views

Is it decidable whether a pushdown automaton recognizes a given regular language?

13 votes
1 answer
2k views

Is there a data-structure for semilattices similar to a tree data-structure?

11 votes
2 answers
2k views

The equivalence relations cover problem (in graph theory)

9 votes
1 answer
693 views

What are appropriate isomorphisms between formal languages?

8 votes
2 answers
928 views

Is a stack machine with a forward read iterator Turing complete?

7 votes
1 answer
2k views

Is a LBA with stack more powerful than a LBA without?

7 votes
1 answer
523 views

Is the closure of P under e-free homomorphisms equal to NP?

7 votes
3 answers
2k views

How did it happen that Algol 60 was an improvement on its successors?

6 votes
2 answers
1k views

Why is there readonly (const) in C++, but not writeonly (sink)?

5 votes
2 answers
1k views

How to challenge Hutter's algorithm?

5 votes
1 answer
1k views

Relation between space and time complexity for machines with write once read many (WORM) memory

5 votes
2 answers
3k views

How is a hypergraph different from a bipartite graph?

5 votes
1 answer
325 views

Stronger versions of P != NP which better express actual convictions

4 votes
1 answer
625 views

An obvious approach to explaining NP != coNP, how far has it been pushed?

4 votes
0 answers
94 views

Turing reductions by NX ∩ coNX and binary relation problems

4 votes
1 answer
881 views

NL and NP compute different binary relations, so what?

4 votes
1 answer
71 views

Acceptance behavior of L and NL with and without cycling

4 votes
1 answer
296 views

Why are there no complete problems for NP ∩ coNP?

4 votes
0 answers
53 views

Complete problems and relativization barriers for nonuniform complexity classes

4 votes
2 answers
785 views

Is the complexity class NP computably enumerable?

4 votes
0 answers
206 views

Graph canonization is not a decision problem. But what type of problem is it?

4 votes
1 answer
190 views

Birkhoff-von Neumann theorem for bistochastic digraphs

3 votes
2 answers
905 views

What is the definition of a $\Pi_1$-sentence?

3 votes
1 answer
94 views

Is "duplicate" in RPN enough for replacing variable binding in term expressions?

3 votes
1 answer
433 views

What is the relation between arithmetic circuits and straight line programs?

3 votes
1 answer
137 views

Is the time reversal symmetry of non-deterministic computations important?

3 votes
1 answer
120 views

What is the name of the word problem for free groups under straight line program encoding?

3 votes
0 answers
59 views

How to apply insights from the theory of codes to alternating codes?

3 votes
2 answers
234 views

Is the word problem for regular languages in ALogTime?