Timeline for Benefits for syntactic and semantic classes
Current License: CC BY-SA 2.5
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 12, 2018 at 18:17 | answer | added | Lance Fortnow | timeline score: 5 | |
| Mar 10, 2018 at 16:43 | answer | added | Joshua Grochow | timeline score: 4 | |
| Mar 10, 2018 at 7:31 | history | tweeted | twitter.com/StackCSTheory/status/972374275935166464 | ||
| Mar 10, 2018 at 2:57 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Apr 13, 2017 at 12:32 | history | edited | CommunityBot |
replaced http://cstheory.stackexchange.com/ with https://cstheory.stackexchange.com/
|
|
| Aug 4, 2011 at 1:23 | answer | added | Tayfun Pay | timeline score: 1 | |
| Feb 9, 2011 at 14:11 | comment | added | Hsien-Chih Chang 張顯之 | @Artem: I guess the class $\mathsf{NP}$ counts? A nice syntactic class it is, but no known semantic characterization exists. (Unlike the plausible conjecture $\mathsf{NL} = \mathsf{UL}$, which reduces the syntactic class $\mathsf{NL}$ into something only accepts or rejects with specific patterns; here accepts only if there is a unique accepting computation path and rejects if there is none.) | |
| Feb 8, 2011 at 22:00 | comment | added | Artem Kaznatcheev♦ | on the "or vice versa": what would a semantic characterization of a syntactic class be? Is there examples of a semantic class without such a semantic characterization? | |
| Feb 8, 2011 at 18:05 | comment | added | Hsien-Chih Chang 張顯之 | @Robin: Thanks for the comment. So we should consider a semantic class which is not believed to have a syntactic characterization, say the unambiguous poly-time $\mathsf{UP}$. But it doesn't have too much "nice properties" though. Any other examples? | |
| Feb 8, 2011 at 17:55 | comment | added | Robin Kothari | It can never hurt to have a syntactic characterization of a semantic class. I don't see how one can compare the benefits of having a syntactic or semantic characterization of a class. BPP is not known to have a syntactic characterization, but it is widely believed to have one (if P = BPP), so the fact that BPP has "nice properties" doesn't seem to have anything to do with it being a semantic class. | |
| Feb 8, 2011 at 6:45 | history | asked | Hsien-Chih Chang 張顯之 | CC BY-SA 2.5 |