Talk:Low (complexity)

Untitled

This article doesn't clearly explain lowness to self. As it now reads, I'm inclined to ask "shouldn't an attachment to your computer which is as powerful as your computer, but instantaneous make your computer faster?" I understand that faster isn't necessarily more powerful, but there's a clarity problem, I think. Booklegger (talk) 00:55, 4 June 2008 (UTC)

Actually, some classes are not low for themselves, for precisely the reason that you describe. For example, NP is not low for NP. The important thing is that the time bound remains within the definition of the class. I'm not sure how best to explain this in the article. Dcoetzee 07:22, 4 June 2008 (UTC)

---

$(NP=coNP)\implies (P=NP)$  ?!?

(10/18/09) ^^ I don't think this is true either. If it is, it is a very recent result. The page on co-NP doesn't mention this either. I'm going to remove it. Feel free to add it back if I am incorrect. —Preceding unsigned comment added by 216.40.158.249 (talk) 07:02, 18 October 2009 (UTC)

Yes, you're right. That implication isn't known. --Robin (talk) 16:05, 18 October 2009 (UTC)

Low and high hierarchy

Is this the same concept as Low and high hierarchies? That page sounds like it was written with no awareness of this page, so maybe it should be revised (or even deleted). (I don't know anything about the subject, so I'm afraid to do it myself.) -- Walt Pohl (talk) 14:45, 27 September 2010 (UTC)

No, these concepts are unrelated. Dcoetzee 08:05, 20 February 2012 (UTC)

Expansion to include the computability theory notion?

Computability theory has a similar concept. Examples include Low (computability) (low for $\Delta _{2}^{0}$) and low for randomness. Should that be included here? It would require some reworking, since the concept can be a little more general. For instance, the article claims that "if B is low for A then B is contained in A", but this isn't true in computability theory---the reals which are low for randomness are very much not random.--130.195.2.100 (talk) 23:30, 19 February 2012 (UTC)

Just from reading the definitions, I don't see any relationship between these two concepts at all. They might have some deeper connection, or it might be coincidental terminology. The word "low" is already used for several things, even in complexity theory. Dcoetzee 08:08, 20 February 2012 (UTC)

In computability theory, a real A is said to be "low for X" (where X is some relativizable notion) if X^A = X. That's pretty much exactly analogous to the complexity theory concept, except X doesn't have to be a complexity class. Low (computability) doesn't look like this in the way it's usually defined, but it's equivalent to "low for $\Delta _{2}^{0}$" (see Arithmetical hierarchy). Low for randomness is random^X = random (this is actually many notions, depending on which randomness notion you use).--130.195.2.100 (talk) 00:08, 21 February 2012 (UTC)

If that's the case then a merge certainly seems called for. However I wouldn't feel confident doing it myself without access to some good resources on the concept in computability. Could you make some recommendations, or if you like expand the article yourself? Thanks! Dcoetzee 09:13, 21 February 2012 (UTC)

(This is 130) There's a section on it in the book Algorithmic Randomness and Complexity, by Downey & Hirschfeldt. Also one in Computability and Randomness by Nies. Most of the good references are going to be texts on randomness, since computability theorists didn't get interested in the notion until Low for Martin-Lof randomness turned out to be such a robust class (I'm surprised we don't already have a page on that one). I could take a shot at expanding the article, but not for a couple of weeks, I'm afraid.--121.74.109.179 (talk) 10:00, 21 February 2012 (UTC)

Regarding lowness and complements

The article states "Every class which is low for itself is closed under complement. ". This isn't necessarily true if the class can't invert the result, as might be the case for classes of monotone circuits. Can someone think of a more accurate phrasing of this sentence that doesn't become needlessly convoluted? // Yonatan (talk) 14:20, 3 October 2013 (UTC)

Wow, I wrote this and I hadn't even considered such classes that low in power. I think it'll suffice to tack on "provided it is powerful enough to negate the boolean result", which I've done. Dcoetzee 20:00, 3 October 2013 (UTC)