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