157 reputation
147
bio website
location Schloss Dagstuhl, Germany
age
visits member for 4 years, 2 months
seen Jan 2 at 13:08

Apr
12
awarded  Famous Question
Feb
19
awarded  Good Question
Feb
1
awarded  Good Answer
Sep
5
awarded  Notable Question
Nov
1
awarded  Popular Question
Jul
23
comment Aren't “oracle machines” unsound concepts?
If I understand correctly, there is no problem with using undecidable languages like the halting problem H as oracles. Using an H oracle introduces a new halting problem, i.e., a halting problem for TMs using an H oracle. This eventually leads to the notion of the arithmetical hierarchy.
Mar
30
awarded  Enthusiast
Mar
19
comment Finding all paths on undirected graph
@rgig: Ok, I see. But wouldn't you then loose the "time linear in the total length of all the output paths" property Suresh aims for? Consider the following counterexample: The graph consists of $n+1$ nodes, more precisely, a $K_n$ containing the start node, and the single target node which is only adjacent to the start node. Then the number (and length) of all output paths is 1, while the backtracking has to search through all the exponentially many paths within the $K_n$.
Mar
19
comment Finding all paths on undirected graph
I agree. Thanks for pointing out the flaw.
Mar
19
comment Finding all paths on undirected graph
@Suresh: Are you sure a DFS will find all paths? Asssume two $K_n$ connected by a single bridge edge, with the source node in one $K_n$ and the target node in the other. DFS will traverse the bride edge exactly once, while there is certainly a much larger number of distinct paths from source to target that are crossing this edge.
Mar
19
answered Finding all paths on undirected graph
Mar
19
awarded  Nice Answer
Mar
18
answered What are the worst notations, in your opinion ?
Mar
18
comment What are the worst notations, in your opinion ?
Please don't confuse the residue-class ring ${\mathbb Z}_q$ (aka ${\mathbb Z}/q{\mathbb Z}$) with a Galois field of $q$ elements, conveniently denoted by ${\mathbb F}_q$ (or $GF(q)$). It is one of the most popular fallacies of our students to assume that both symbols denote the same mathematical object, even if $q$ is not a prime.
Mar
18
awarded  Scholar
Mar
18
accepted Theorem versus Proposition
Mar
17
comment Theorem versus Proposition
In fact, in German I would use "Satz" for a minor theorem and "Theorem" for a major, fundamental theorem. However, I think it will be regarded as hubris to call a theorem of your own a "Theorem".
Mar
17
awarded  Supporter
Mar
16
awarded  Nice Question
Mar
16
awarded  Student