Timeline for Does two languages being in P imply reduction to each other?
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 3, 2014 at 14:05 | comment | added | Raphael | See here. Also, brushing up on fundamentals might help. | |
| Jan 3, 2014 at 14:04 | history | edited | Raphael |
edited tags
|
|
| Jan 3, 2014 at 13:03 | history | edited | Juho | CC BY-SA 3.0 |
added 260 characters in body
|
| Jan 1, 2014 at 13:54 | history | edited | David Richerby |
edited tags
|
|
| Dec 31, 2013 at 22:54 | vote | accept | Yechiel Labunskiy | ||
| Dec 31, 2013 at 22:49 | answer | added | ymbirtt | timeline score: 11 | |
| Dec 31, 2013 at 22:44 | review | Close votes | |||
| Jan 3, 2014 at 14:28 | |||||
| Dec 31, 2013 at 22:40 | comment | added | Yechiel Labunskiy | L1 <= L2 if there exists a reduction function f such that for all input X, X is part of L1 IFF f(X) is part of L2. | |
| Dec 31, 2013 at 22:37 | comment | added | ymbirtt | That's actually an interesting edge case that I hadn't spotted, but usually for these sorts of problems we ignore these edge cases $\emptyset$ and $\Sigma^*$. Can you recall the definition of a reduction? | |
| Dec 31, 2013 at 22:24 | review | First posts | |||
| Jan 1, 2014 at 13:54 | |||||
| Dec 31, 2013 at 22:04 | history | asked | Yechiel Labunskiy | CC BY-SA 3.0 |