Talk:IP (complexity)

Bad format in new version

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

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

$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

$maxA\,$

• 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?

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

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)

This is especially irritating as "IP" seems to stand for Interactive Proof https://complexityzoo.net/Complexity_Zoo:I#ip and not Interactive Polynomial --2A01:C23:7C3C:BB00:E1EA:B3C9:F3FA:C1AB (talk) 15:42, 25 December 2020 (UTC)

Not clear definition

It's not clear at the definition section what's $Q$ stands for. Also, although it was mentioned in the introduction, I think it should be stated more formally what are $P$ and $V$ (probabilistic TM's, their computational power, etc.). — Preceding unsigned comment added by 93.173.63.178 (talk) 14:12, 10 April 2016 (UTC)

a polynomial number, p(n), of messages

The phrase "a polynomial number, p(n), of messages" doesn't compute for me. n is a string. Does this mean polynomial in the length of the string? If so, is it wrong as written? If so, does one normally write p(len(n)) or some such? Or is this the convention, and is there a common way to explain that on wikipedia? ★NealMcB★ (talk) 17:16, 26 September 2016 (UTC)

Relation to Arthur-Merlin protocols

"The Arthur–Merlin protocol, introduced by László Babai, is similar in nature, except that the number of rounds of interaction is bounded by a constant rather than a polynomial."

This doesn't seem right at all to me. From what I understand the difference is that the messages from the verifier in Arthur-Merlin protocols are restricted to the coin tosses. AM is public coin and IP is private coin. See [2] — Preceding unsigned comment added by Smyds (talk • contribs) 13:29, 23 May 2018 (UTC)

You're right, but it turns out that AM (which is defined with public coins) with any constant number of rounds is the same as IP (defined with private coins) with any constant number of rounds. So one could say AM is just IP with constant number of rounds. But this doesn't follow from its traditional definition, which is a 2-round protocol with public coins, and has to be proved. --Robin (talk) 23:17, 24 May 2018 (UTC)