User talk:RobinK

DSPACE, etc.

Thanks for several corrections and a {{dn}} fix. I don't know why I didn't see Alternation (complexity)...

CRGreathouse (t | c) 05:56, 5 March 2010 (UTC)

No problem. You didn't see it because I fixed the disambiguation page for Alternation to list Alternation (complexity) instead of (algorithms), and created a redirect from (complexity) -> Alternating TM, after you were done disambiguating. --Robin (talk) 13:54, 5 March 2010 (UTC)

AM,MA

Hi Robin, thanks for the fix in Arthur–Merlin_protocol. I saw that the current condition for AM reads as follows (and is correct)

• if x is not in L, then $\Pr \nolimits _{y\in \{0,1\}^{p(n)}}(\forall z\in \{0,1\}^{q(n)}\,M(x,y,z)=0)\geq 2/3.$

I wanted to note that it can be equally written as

• if x is not in L, then $\Pr \nolimits _{y\in \{0,1\}^{p(n)}}(\exists z\in \{0,1\}^{q(n)}\,M(x,y,z)=1)\leq 1/3.$

However, the second condition seems to go well together with the x is in L condition, as 2/3 and 1/3 add up to 1. —Preceding unsigned comment added by Sg313d (talk • contribs) 07:37, 2 June 2010 (UTC)

I felt the first one contrasts better with the condition for x in L, since for x in L, the condition says that "there exists" something, I felt the condition for x not in L would look better if it said something like "for all". Both are correct though, and I wouldn't mind changing to the other definition if that seems clearer. Also, this way it looks similar to the definition of MA. --Robin (talk) 13:17, 2 June 2010 (UTC)