Talk:IP (complexity)
From Wikipedia, the free encyclopedia
[edit] 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)
