Timeline for Complexity of edge coloring of class 1 graphs
Current License: CC BY-SA 4.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 16, 2020 at 14:26 | comment | added | Ben Barber | How we should treat algorithms which are known to terminate but whose run length exceeds any computable function of the input size is on a level of subtlety on which I am not competent to comment. | |
| Jun 16, 2020 at 14:17 | comment | added | Ben Barber | @GordonRoyle I suppose that this could cause a practical difficulty if you happened not to know the implicit constant, or how large $n$ needed to be for some known constant to be valid. But then running for say $nf(n)$ steps would work eventually; and if only $O(\cdot)$ level information is acceptable to call a decision process efficient, we should extend the same courtesy to the run length of the algorithm for producing witnesses. | |
| Jun 16, 2020 at 13:45 | comment | added | Gordon Royle | @BenBarber But most polynomial-time algorithms only come with an $O(f(n))$ time-bound, not a precise number-of-steps bound. | |
| Jun 16, 2020 at 11:35 | vote | accept | vidyarthi | ||
| Jun 16, 2020 at 11:14 | comment | added | Ben Barber | @vidyarthi, It's not unrelated, but it's not exactly the same question. I'd say it's more to do with the difference between decision problems (which just have yes/no answers) and more complicated types of question which are asking for something close to what we'd usually think of as a "computation". | |
| Jun 16, 2020 at 11:09 | comment | added | Ben Barber | @GordonRoyle, suppose I can find colourings when they exist in time at most $f(n)$. I input the graph I'm wondering about into the algorithm and try to run it for $f(n)$ steps. The possible results are that it finds a colouring, or that it fails to find a colouring, possibly because it encounters a state it doesn't know what to do with (the promise of existence having been broken). Which result I get tells me whether a colouring exists. | |
| Jun 16, 2020 at 10:33 | comment | added | Gordon Royle | It is not completely clear to me how you can use a polynomial time algorithm that finds colourings if they exist to actually determine whether or not they exist. Suppose I give you the algorithm and a graph to be tested... what do you do next? | |
| Jun 16, 2020 at 10:27 | vote | accept | vidyarthi | ||
| Jun 16, 2020 at 10:36 | |||||
| Jun 16, 2020 at 9:52 | comment | added | vidyarthi | so the problem i somewhat a rephrasing of whether $P=NP$, right? | |
| Jun 16, 2020 at 9:31 | history | answered | Ben Barber | CC BY-SA 4.0 |