bio | website | gowers.wordpress.com |
---|---|---|
location | ||
age | ||
visits | member for | 5 years, 6 months |
seen | 20 hours ago | |
stats | profile views | 32,054 |
Mathematics professor at Cambridge
Sep 20 |
awarded | Nice Question |
Sep 8 |
revised |
Philosophy behind Mochizuki's work on the ABC conjecture
fixed typo |
Sep 8 |
comment |
Is every distance-regular graph vertex-transitive?
Yes, but the hypercubes are vertex transitive, as are most of the obvious families. |
Sep 7 |
answered | Is every distance-regular graph vertex-transitive? |
Sep 6 |
comment |
A combination of two well-known complexity problems
@joro, what you're asking is in a sense what's in the back of my mind when I asked the original question: hard instances of graph isomorphism are rather delicate, so can they be combined with a condition about containing Hamilton cycles? If they can't, then the answer to my question is that you can indeed distinguish between the two situations. |
Sep 6 |
comment |
A combination of two well-known complexity problems
@Suvrit, if you were to take two typical hard instances for the Hamilton cycle problem, one that contains a Hamilton cycle and one that doesn't, then it is very likely that it will be easy to tell that they are non-isomorphic. (For example, their degree sequences are likely to differ.) In the other direction, if you have two graphs of large minimal degree that are a difficult case for graph isomorphism, they will both contain Hamilton cycles. I'm not sure whether this is answering your question though. |
Sep 6 |
comment |
A combination of two well-known complexity problems
@Gerhard "I'm sure it's the latter" Paseman, it's only half the latter. I know what zero-knowledge proofs are, but don't immediately see how they answer the question. Could you spell it out? |
Sep 6 |
comment |
A combination of two well-known complexity problems
@Richard Stanley -- that's why I insist that they are both hard, though obviously if graph isomorphism is hard then so are NP-complete problems so I could have just said "assuming that graph isomorphism is hard". |
Sep 5 |
comment |
A combination of two well-known complexity problems
A quick remark: one can of course ask the same question for many other NP-complete problems -- I'd be just as interested, for example, in the same question but with "clique of size m" instead of "Hamilton cycle". |
Sep 5 |
asked | A combination of two well-known complexity problems |
Jul 31 |
awarded | Stellar Question |
Jul 24 |
awarded | Popular Question |
Jun 18 |
awarded | Good Question |
Jun 18 |
awarded | Good Question |
Jun 18 |
awarded | Good Question |
Jun 18 |
awarded | Nice Answer |
Jun 18 |
awarded | Nice Answer |
Jun 18 |
awarded | Nice Question |
Jun 18 |
awarded | Nice Answer |
Jun 18 |
awarded | Nice Question |