StefanH
  • Member for 6 years, 6 months
  • Last seen this week
2 answers
9 votes
220 views
1 bookmarks
In the beginning, computable functions were always total, but when where the partial functions included
2 answers
6 votes
295 views
2 bookmarks
Proof of Space Hierarchy Theorem incompatible with Linear Speed Up Theorem for time
1 answers
5 votes
82 views
1 bookmarks
Is there such a notion as "effectively computable reductions" or would this be not useful
1 answers
5 votes
161 views
The content of an implication from the snm-Theorem
1 answers
4 votes
373 views
Doing matrix multiplication with $\lceil n^3 / \log n \rceil$ processors in $2\log n$ steps by Brent's principle
1 answers
4 votes
126 views
2 bookmarks
The equational theory of regular languages has no finite set of axioms for general alphabets
0 answers
3 votes
88 views
What about problems that are fixed parameter tractable with an algorithm that does not inspect the parameter?
2 answers
3 votes
630 views
Is the set of language decidable by some Turing machine computing in some given computable time bound decidable
1 answers
3 votes
169 views
Why is dominating set in $W[2]$, but independent set in $W[1]$
0 answers
2 votes
55 views
A synctactic property of the complexity class P
2 answers
2 votes
192 views
Looking for an "intuitive" regular expression for $\{ w \in \Sigma^{\ast} \mid 2|w|_1 + |w|_0 \equiv 0 \pmod{3} \}$
1 answers
2 votes
223 views
A new definition of recursively enumerable set?
2 answers
2 votes
329 views
Question on the definition of computable function and non-terminating behaviour
2 answers
1 votes
146 views
The set of valid sentences in FO is not decidable as a consequence of rec. inseparability
1 answers
1 votes
581 views
How the LZ77 compression algorithm handles the case when the entire look-ahead buffer is matched in the search buffer
1 answers
1 votes
38 views
1 bookmarks
For a turing machine which computes $y$ with argument $x$, how much does the descriptional length of a machine producing $y$ without input increases
1 answers
0 votes
251 views
Choosing a shortest representative number from interval in arithmetic coding
1 answers
0 votes
148 views
A minimal automaton for a language quotient $w^{-1}L$ if $L$ is regular