Talk:IP (complexity)

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Mathematics (Rated Start-class, Low-importance)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
Start Class
Low Importance
 Field: Discrete mathematics
WikiProject Computer science (Rated Start-class, Low-importance)
WikiProject icon This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Start-Class article Start  This article has been rated as Start-Class on the project's quality scale.
 Low  This article has been rated as Low-importance on the project's importance scale.
 

Bad format in new version[edit]

unreadble format in the proof for: \text{IP} \subseteq \text{NSPACE} makes the proof harder to read and\or understand. I was expecting something like:
let \text{w} \in \text{IP} \dots
"Now we can define".... "
rollback? Msshapira (talk) 11:24, 2 January 2011 (UTC)

New proof makes strange assertions[edit]

The statement "#SAT in IP" doesn't even make sense - #SAT isn't even a decision problem. It's complete for #P, but how does this proof imply IP is a subset of PSPACE or vice versa? Can the contributor clear up these assertions? Thanks. Deco 23:22, 15 November 2005 (UTC)

The decision problem for #SAT is: For phi and k, does phi have exactly k satisfiable assignments? And the proof for showing #SAT is in IP doesn't imply PSPACE is a subset of IP, but it introduces the technique that is key to showing PSPACE is a subset of IP. --18.244.7.203 08:45, 24 November 2006 (UTC)
Makes sense. :-) Dcoetzee 23:35, 3 December 2008 (UTC)

Typography[edit]

 wt-avg\,
 \text{wt-avg} \,

Am I right in guessing that the second of the above was what was intended? That's what I changed the first to in my recent edits.

Someone didn't know that

  • "Displayed" TeX should be indented;
  • One should write
 \max A\,
rather than
 max A\,
  • One should write
\text{accepts }w\,
rather than
accepts\ w
  • One should write
 a,\dots,z\,
rather than
 a,...,z\,
  • One should write
(1 − x)
rather than
(1-x)
  • lots of other stuff—see my recent cleanups.

This is all in Wikipedia:Manual of Style (mathematics). Michael Hardy (talk) 00:32, 11 February 2009 (UTC)

Copyvio?[edit]

It looks like the proof here is taken from [1]. Does anyone know if we have permission to use it? If not I'm afraid it'll have to get scrapped. Dcoetzee 09:57, 4 April 2009 (UTC)

Overlap with Interactive proof system[edit]

Currently this article has a lot of overlap with Interactive proof system, especially when discussing variants. I propose that this article be only about IP (and theorems about IP), whereas Interactive proof system can be a summary of all the major interactive proof systems, and describe all the variants, and the various relations between them. --Robin (talk) 14:31, 8 December 2009 (UTC)