Timeline for Proof for P-complete is not closed under intersection
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 29, 2012 at 20:54 | history | edited | Gilles 'SO- stop being evil' | CC BY-SA 3.0 |
added definitions from comments
|
| Nov 29, 2012 at 17:22 | comment | added | Uriel | @A.Schulz: These lecture notes are a bit unstructured, but I think the definition above refers to the definition of the $\text{LOGSPACE}$-reduction: Let $A,B \subset \Sigma^{*}. A \le_{L} B: \Leftrightarrow \exists f \in \text{FLOGSPACE}$ with $(x \in A \Leftrightarrow f(x) \in B).$ | |
| Nov 29, 2012 at 17:07 | comment | added | A.Schulz | It all depends on the definition of $\le_L$. How is the reduction defined? | |
| Nov 29, 2012 at 15:06 | answer | added | Yuval Filmus | timeline score: 10 | |
| Nov 29, 2012 at 14:14 | comment | added | Uriel | Please accept my apologies for not providing the definition. I thought the definition is uniform. Here it is: $A \subset \Sigma^{*}$ is complete for $\text{P}$ if 1. $A \in \text{P}$ 2. $B \le_L A$ for all $B \in \text{P}$ | |
| Nov 29, 2012 at 13:53 | comment | added | Niel de Beaudrap | What reductions are you using? Might they be log-space many-to-one reductions (the reduction model favoured e.g. in Papadimitriou's text)? | |
| Nov 29, 2012 at 13:49 | history | tweeted | twitter.com/#!/StackCompSci/status/274148051269058560 | ||
| Nov 29, 2012 at 13:15 | history | edited | A.Schulz | CC BY-SA 3.0 |
deleted 1 characters in body; edited tags
|
| Nov 29, 2012 at 13:12 | answer | added | A.Schulz | timeline score: 5 | |
| Nov 29, 2012 at 12:56 | comment | added | Uriel | This is the reason for quotation. I've searched in the literature (Papadimitriou, Bovet Crescenzi) and also on the internet, but I didn't find something useful. That's why I'm asking for help. | |
| Nov 29, 2012 at 12:48 | history | asked | Uriel | CC BY-SA 3.0 |