bio | website | |
---|---|---|
location | Schloss Dagstuhl, Germany | |
age | ||
visits | member for | 5 years, 4 months |
seen | Jan 20 at 11:06 | |
stats | profile views | 165 |
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 |