StefanH
  • Member for 6 years, 6 months
  • Last seen this week
0 answers
2 votes
54 views
A synctactic property of the complexity class P
0 answers
3 votes
87 views
What about problems that are fixed parameter tractable with an algorithm that does not inspect the parameter?
1 answers
5 votes
81 views
1 bookmarks
Is there such a notion as "effectively computable reductions" or would this be not useful
1 answers
4 votes
372 views
Doing matrix multiplication with $\lceil n^3 / \log n \rceil$ processors in $2\log n$ steps by Brent's principle
2 answers
6 votes
294 views
2 bookmarks
Proof of Space Hierarchy Theorem incompatible with Linear Speed Up Theorem for time
2 answers
3 votes
628 views
Is the set of language decidable by some Turing machine computing in some given computable time bound decidable
1 answers
3 votes
166 views
Why is dominating set in $W[2]$, but independent set in $W[1]$
1 answers
4 votes
125 views
2 bookmarks
The equational theory of regular languages has no finite set of axioms for general alphabets
2 answers
1 votes
145 views
The set of valid sentences in FO is not decidable as a consequence of rec. inseparability
2 answers
9 votes
219 views
1 bookmarks
In the beginning, computable functions were always total, but when where the partial functions included
1 answers
0 votes
249 views
Choosing a shortest representative number from interval in arithmetic coding
1 answers
1 votes
579 views
How the LZ77 compression algorithm handles the case when the entire look-ahead buffer is matched in the search buffer
2 answers
2 votes
191 views
Looking for an "intuitive" regular expression for $\{ w \in \Sigma^{\ast} \mid 2|w|_1 + |w|_0 \equiv 0 \pmod{3} \}$
1 answers
1 votes
37 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
5 votes
160 views
The content of an implication from the snm-Theorem
1 answers
2 votes
222 views
A new definition of recursively enumerable set?
2 answers
2 votes
327 views
Question on the definition of computable function and non-terminating behaviour
1 answers
0 votes
147 views
A minimal automaton for a language quotient $w^{-1}L$ if $L$ is regular