 | This article is rated Stub-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | ||||||||||
| |||||||||||
"It has also been shown by L. Berman in 1980 that the problem of verifying/falsifying any first-order statement about real numbers that involves only addition and comparison (but no multiplication) is in EXPSPACE."
I don't understand how this is helpful in the context of completeness. I could list many other problems which I solve in EXSPACE, yet I have no idea whether or not any of these is EXPSPACE-complete. Then again, the paper may well establish a completeness result, but I was not able to check that. If it does, then the statement should be made more accurate, otherwise it should be removed completely from this page.--Baueran (talk) 02:51, 6 March 2009 (UTC)
- I think it's okay - not every EXPSPACE problem we give has to be EXPSPACE-complete, as long as it hasn't been shown to be in some well-known class contained in EXPSPACE. This fact is significant because ability to verify logical statements is one of the fundamental ways that classes are distinguished. But I wouldn't mind much if it were removed either. Dcoetzee 05:45, 6 March 2009 (UTC)
- This is exactly my point, the article merely states that there is an EXPSPACE upper bound on the problem, but it does not say whether or not it is tight, hence, whether or not the problem is also contained in a stricly lower complexity class than EXPSPACE. While my suspicion is, just like yours, that no one has managed to show a tighter upper bound so far, the Wikipedia article currently does not say that. (Also, keep in mind that the reference is rather old, so there may have been progress on the problem.) For these reasons, I would still think it would be less confusing to the reader if this statement was simply removed from the article.--Baueran (talk) 03:14, 7 March 2009 (UTC)
- Okay sure - but I think it would be nice to have a more comprehensive list of problems shown to be in EXPSPACE, and it could maybe go there. Dcoetzee 02:45, 9 March 2009 (UTC)
- This is exactly my point, the article merely states that there is an EXPSPACE upper bound on the problem, but it does not say whether or not it is tight, hence, whether or not the problem is also contained in a stricly lower complexity class than EXPSPACE. While my suspicion is, just like yours, that no one has managed to show a tighter upper bound so far, the Wikipedia article currently does not say that. (Also, keep in mind that the reference is rather old, so there may have been progress on the problem.) For these reasons, I would still think it would be less confusing to the reader if this statement was simply removed from the article.--Baueran (talk) 03:14, 7 March 2009 (UTC)