Talk:PSPACE
Talk:PSPACE
| WikiProject Mathematics | (Rated Start-class, Mid-priority) | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| |||||||||||||
₢What do you mean by PSPACE-complete <= PSPACE?
- It's rather obvious, that PSPACE-complete <= PSPACE, actually it's part of the definition. This is a bit puzzling. Someone should change this.
In the introductory paragraph, the sentence "It is also widely suspected that the symbol on the last line should be a ." references a symbol that is not present in the last line. Either one of the symbols is incorrect (wrt this sentence), or someone removed the line ;-)
- The addition here had the original claim that PSPACE-complete ≤ PSPACE, and the comment referred to the conjecture that this containment was strict, i.e. that not all PSPACE problems were complete for the class. The last line was later removed, so the claim didn't make sense.
Someone had modified it further, but I removed it entirely from the text as it didn't make any sense anymore, and I don't think the PSPACE-complete < PSPACE idea is really that important to mention. --Saforrest 05:53, 15 November 2005 (UTC)
Problems with the main page -- stale content[edit]
The main page states that PH PSPACE and that P relationship to PSPACE is unknown (open problem). I think these claims are stale because in 2018 Tal and Raz proved that BQP PH, as BQP PSPACE and P BQP not all of these results can be valid at the same time. — Preceding unsigned comment added by 2A00:23C4:8585:7D01:244F:974F:E271:6C71 (talk) 12:32, 11 October 2021 (UTC)
Subset symbols[edit]
There are four subset symbols on the first line, the text should be updated accordingly. — Preceding unsigned comment added by 128.208.47.181 (talk) 20:56, 4 June 2007 (UTC)
- Done. Next time, feel free to do it yourself. Phaunt 10:45, 27 June 2007 (UTC)
P < EXPTIME[edit]
May be, relation P < EXPTIME should be added?
- No. That's true, and those classes are mentioned in the discussion, but this article isn't a complete hierarchy of classes, and the relationship of P and EXPTIME isn't relevant to PSPACE. Dcoetzee 00:15, 16 May 2008 (UTC)
- This text from the article did seem to be a bit misleading:
- The following relationships are known between the classes NL, P, NP, PSPACE, EXPTIME and EXPSPACE:
- True, it did't explicitly say that these are all known relations, but it did suggest so. I've decided to be bold and reworded it a bit. Oliphaunt (talk) 00:48, 16 May 2008 (UTC)
- This text from the article did seem to be a bit misleading:
Infobox[edit]
The new infobox says "DTIME: , ". Exactly what is this supposed to mean? Infobox documentation says "Functions f such that the class is in DTIME[f(n)], if applicable." So is it trying to claim that PSPACE is both in DTIME[] and in DTIME[]? — Miym (talk) 10:26, 18 October 2009 (UTC)
- I think I understand what the author is trying to say, but it's going to be extremely confusing. I'm taking it out for now. --Robin (talk) 16:09, 18 October 2009 (UTC)
Why is PSPACE-complete defined by poly-time reduction, but not poly-space reduction?[edit]
Thanks. —Preceding unsigned comment added by Tmbu (talk • contribs) 08:46, 1 July 2010 (UTC)
COSPACE[edit]
Why isn't COPSPACE (or CO-PSPACE, should you prefer) mentioned? 212.68.15.66 (talk) 11:24, 14 February 2011 (UTC)
- I know (I remembered it quite shortly after posting here) but shouldn't that be mentioned? 212.68.15.66 (talk) 06:01, 15 February 2011 (UTC)
Definition is confusing[edit]
In the intro paragraph it says that "PSPACE is the set of all decision problems which can be solved by a Turing machine using a polynomial amount of space." Does it mean space as in physical volume or hard drive space or spaces on the Turing machine tape? If the later, wouldn't it make more sense to add "on the Turing machine tape" to the end of the definition? 70.44.138.215 (talk) 02:00, 21 August 2011 (UTC)
#PSpace = #P[edit]
The idea of counting all valid quantifications of a boolean formula defines a canonical #PSpace problem. It turns out that the number of valid quantifications of a formula is equal to the number of satisfying assignments of the formula, so calculating solutions to #PSpace problems is only as hard as #P, which is thought to be EXP, so the equivalence may be rather moot.24.33.70.144 (talk) 21:35, 1 March 2014 (UTC)Daniel Pehoushek
Why there is no LOGSPACE in the containments?[edit]
Is there anay reason why
doesn't start with logspace instead of NL? — Preceding unsigned comment added by 2.97.117.210 (talk) 20:51, 27 August 2014 (UTC)
If adding a truthful k-clause during sat solving is equivalent to deciding an (n-k) variable QBF, then is NP=PSpace?[edit]
I have never seen this kind of statement in theory. I have encountered the truth of it in practical sat solvers.Daniel pehoushek (talk) 22:42, 9 February 2017 (UTC)
Comments
Post a Comment