Timeline for Why can't we say that NP is closed under complement given that we can say it is closed under intersection

7 events

when toggle format	what		by	license	comment
Jun 16, 2020 at 10:30	history	edited	CommunityBot		Commonmark migration
Jan 6, 2018 at 14:02	comment	added	Yuval Filmus		When defining NL using this model, you'll have to restrict access to the guess tape – say the head only moves to the right. But this subtlety doesn't arise when defining NP.
Jan 6, 2018 at 14:01	comment	added	Albert Hendriks		It's an interesting model. Notice that in this model NL=NP, which is generally considered false in most models.
Jan 6, 2018 at 5:56	history	edited	Yuval Filmus	CC BY-SA 3.0	deleted 1 character in body
Jan 6, 2018 at 5:55	comment	added	Yuval Filmus		Yes, $M'$ passes its witness to $M$. Of course, this doesn't compute the complement language, which is precisely the point.
Jan 6, 2018 at 5:48	comment	added	Albert Hendriks		(assuming $M'=M^c$) "The machine $M′$ accepts an input $x$ if there exist a string $y$ such that when running $M$ on $x$ with $y$ on the guess tape, it rejects." -> I find this very hard to understand. I'd think: The machine $M′$ accepts an input $x$ if for all strings $y$ such that when running $M$ on $x$ with $y$ on the guess tape, it rejects. Or does $M'$ pass $y$ to $M$? That would be new for me.
Jan 5, 2018 at 12:11	history	answered	Yuval Filmus	CC BY-SA 3.0