MRA
Reputation
Next privilege 200 Rep.
 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