Timeline for Complexity classes that are closed under subtraction
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 11, 2013 at 23:54 | vote | accept | Andrea Williams | ||
| Dec 11, 2013 at 23:22 | comment | added | G. Bach | @AndreaWilliams P is, whether NP is depends on whether NP = coNP, I think. | |
| Dec 11, 2013 at 23:21 | answer | added | Karolis Juodelė | timeline score: 1 | |
| Dec 11, 2013 at 23:17 | history | edited | Andrea Williams | CC BY-SA 3.0 |
added 235 characters in body; edited title
|
| Dec 11, 2013 at 22:51 | comment | added | Andrea Williams | @G. Bach thats what i was trying to ask, are NP or P closed under subtraction? I was trying to think of an example and that is why i (mistakenly) refered to A and B. | |
| Dec 11, 2013 at 22:12 | comment | added | G. Bach | Languages isn't what you're actually interested in, you want to know whether a given complexity class is closed under subtraction of languages in that class. | |
| Dec 11, 2013 at 21:28 | comment | added | Gilles 'SO- stop being evil' | Hint: if a language class is closed under subtraction, it contains $A \setminus A$. | |
| Dec 11, 2013 at 21:16 | review | First posts | |||
| Dec 11, 2013 at 23:19 | |||||
| Dec 11, 2013 at 21:05 | comment | added | Karolis Juodelė | Well, how would you decide if a word belongs to A\B? | |
| Dec 11, 2013 at 20:57 | history | asked | Andrea Williams | CC BY-SA 3.0 |