Timeline for Does two languages being in P imply reduction to each other?
Current License: CC BY-SA 4.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S May 20, 2021 at 4:04 | history | edited | John L. | CC BY-SA 4.0 |
More detailed explanation when L2 is the "full" language
|
| S May 20, 2021 at 4:04 | history | suggested | IniasP | CC BY-SA 4.0 |
Explanation on the argument for when L2 is the "full" language
|
| May 19, 2021 at 15:30 | review | Suggested edits | |||
| S May 20, 2021 at 4:04 | |||||
| Jun 16, 2020 at 10:30 | history | edited | CommunityBot |
Commonmark migration
|
|
| Feb 21, 2017 at 9:17 | comment | added | David Richerby | "No in general" is a rather misleading way of saying "Yes, except in two special cases." | |
| Feb 21, 2017 at 8:39 | history | edited | ymbirtt | CC BY-SA 3.0 |
Tighten up argument to account for empty and full languages
|
| Feb 21, 2017 at 8:27 | comment | added | ymbirtt | @Auberon, yep, you're right! Damn, I was sloppy 3 years ago, wasn't I? I'll throw an updated version together momentarily. | |
| Feb 20, 2017 at 15:48 | comment | added | Auberon | $\Sigma^*$ and $\emptyset$ are valid languages in $P$. They are not trivial cases. So the answer is actually NO. This answer needs to be edited to be more complete. | |
| Dec 31, 2013 at 23:01 | comment | added | Yechiel Labunskiy | I think ymbritt did just that in our exchange above. | |
| Dec 31, 2013 at 22:59 | comment | added | D.W.♦ | ymbirtt, Normally we try not to just dump the complete answer to a question that looks like a homework exercise, especially when the question shows no evidence of effort. (It might be what the original author is hoping for, but I don't think it's doing them a service, and I don't think it's good for our community in the long run -- it just encourages more such bad questions.) I tend to think it is better to provide hints, or better still, wait for the original author to make a serious effort on their own and come back to show us what they've tried. | |
| Dec 31, 2013 at 22:55 | comment | added | Yechiel Labunskiy | Thanks for your help, a bit fudgy in my mind, but starting to sink in. | |
| Dec 31, 2013 at 22:54 | vote | accept | Yechiel Labunskiy | ||
| Dec 31, 2013 at 22:49 | history | answered | ymbirtt | CC BY-SA 3.0 |