Timeline for Complexity of advice language?
Current License: CC BY-SA 2.5
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 27, 2010 at 16:00 | history | edited | András Salamon | CC BY-SA 2.5 |
added 603 characters in body
|
| Sep 27, 2010 at 15:31 | vote | accept | András Salamon | ||
| Sep 27, 2010 at 15:13 | comment | added | András Salamon | @Tsuyoshi: In this question I was envisaging the advice language of advice strings, forgetting which input length each string is associated with. The advice function $\{(i,A(M)(i)) \mid i \in \mathbb{N}\}$ that you suggest, mapping each input length $i$ to the string for the inputs of that length, would probably be an interesting object itself. However, the advice function wasn't what I had in mind here. | |
| Sep 27, 2010 at 14:39 | comment | added | Tsuyoshi Ito | I read revision 4, and would like to point out that an advice is a sequence of strings y_0, y_1, …, not a language. The set {y_0, y_1, …} of advice strings has little to do with the nature of the advice, because this set “forgets” which i’s each string y_i came from. The following question occurred to me just now: Is your question really about advice language, or is it about the function $1^i \mapsto y_i$ (which might be called advice function)? | |
| Sep 27, 2010 at 14:17 | history | edited | András Salamon | CC BY-SA 2.5 |
clarify in light of further comments
|
| Sep 26, 2010 at 12:18 | comment | added | Tsuyoshi Ito | The definition of A(M) is still unclear to me, and the previous comment still applies. Note that usually the sequence y_0, y_1, … of advice strings is not considered as part of the Turing machine. | |
| Sep 25, 2010 at 21:52 | history | edited | András Salamon | CC BY-SA 2.5 |
address comments
|
| Sep 25, 2010 at 17:55 | comment | added | Tsuyoshi Ito | The definition of A(L,M) is unclear to me. Are you viewing a (possibly uncomputable) sequence y_0, y_1, … of advice strings as part of the machine M and defining A(L,M) as the set {y_0, y_1, …} (forgetting which input length they correspond to)? In that case, I do not expect that there is any relation between L and A(L,M). | |
| Sep 25, 2010 at 17:49 | history | edited | András Salamon |
edited tags
|
|
| Sep 25, 2010 at 17:43 | comment | added | Robin Kothari | It isn't clear to me that A(L,M) is uniquely specified by L and M. Could you explain that a bit more? (Unrelated: I'd recommend adding the tag advice, and removing ppoly. ppoly looks bad, and is probably too specific to be a tag.) | |
| Sep 25, 2010 at 17:24 | answer | added | Hrushikesh | timeline score: 5 | |
| Sep 25, 2010 at 17:06 | history | asked | András Salamon | CC BY-SA 2.5 |