IP = PSPACE - Revision history

Srikar at 12:33, 3 May 2021

2021-05-03T12:33:30Z

Srikar at 12:33, 3 May 2021

2021-05-03T12:33:16Z

PratyushRTiwari at 22:35, 2 May 2021

2021-05-02T22:35:18Z

Srikar: Blanked the page

2020-10-18T06:24:07Z

Blanked the page

Srikar: Created page with " $\lim_{z\rightarrow z_0} f(z)=f(z_0)$ "

2020-10-18T06:23:47Z

Created page with "<math>\lim_{z\rightarrow z_0} f(z)=f(z_0)</math>"

New page

<math>\lim_{z\rightarrow z_0} f(z)=f(z_0)</math>

@@ Line 1: / Line 1: @@
 General proof sketch:
-. We consider the language <math>#SAT_D<\math> which is the decision variant of <math>\#SAT</math>, the language of CNF formulae and their satisfying assignment.
+. We consider the language <math>\#SAT_D<\math> which is the decision variant of <math>\#SAT</math>, the language of CNF formulae and their satisfying assignment.
      <math> \#SAT_D = \{\langle \phi, K\rangle: \text{ K is the number of satisfying assignments of }\phi\} </math>

@@ Line 1: / Line 1: @@
 General proof sketch:
-. We consider the language <math>\#SAT_D<\math> which is the decision variant of <math>\#SAT</math>, the language of CNF formulae and their satisfying assignment.
+. We consider the language <math>#SAT_D<\math> which is the decision variant of <math>\#SAT</math>, the language of CNF formulae and their satisfying assignment.
      <math> \#SAT_D = \{\langle \phi, K\rangle: \text{ K is the number of satisfying assignments of }\phi\} </math>

← Older revision	Revision as of 22:35, 2 May 2021
Line 1:	Line 1:
	+	General proof sketch:

	+	1. We consider the language <math>\#SAT_D<\math> which is the decision variant of <math>\#SAT</math>, the language of CNF formulae and their satisfying assignment.
	+
	+	<math> \#SAT_D = \{\langle \phi, K\rangle: \text{ K is the number of satisfying assignments of }\phi\} </math>
	+
	+	where <math>\phi</math> is a 3CNF formula. Prove that <math>\#SAT_D \in \mathsf{IP}</math> via arithmetization and the sumcheck protocol.
	+
	+	2. Arithmetization is the idea of converting boolean formulae to an algebraic form. So, <math>x\land y</math> can be represented by <math>x\cdot y</math> and <math>\neg x</math> can be represented by <math>1-x</math> and <math>x\lor y</math> can be represented by <math>1 - (1- x)(1-y)</math>.
	+
	+	3. Sumcheck protocol: add general description of the sumcheck protocol
	+
	+	4. Using a very similar idea we then prove that <math>\mathsf{TQBF} \in \mathsf{IP}</math> and since <math>\mathsf{TQBF}</math> is <math>\mathsf{PSPACE}</math>-complete, we have that <math>\mathsf{PSPACE} \in \mathsf{IP}</math>.
	+
	+	5. And we know that <math>\mathsf{IP} \in \mathsf{PSPACE}</math> by the following argument. We know that the prover can use an arbitrary function, it can in principle use unbounded computational power. Therefore, given any verifier, the optimum prover strategy can be computed using <math>poly(\|x\|)</math> and <math>2^{poly(\abs{x})}</math> time. This is by brute forcing through the possible space of prover verifier communication, optimizing for the probability of acceptance by the verifier. This takes polynomial space, hence <math>\mathsf{IP} \in \mathsf{PSPACE}</math>.

← Older revision		Revision as of 06:24, 18 October 2020
Line 1:		Line 1:
−	~~<math>\lim_{z\rightarrow z_0} f(z)=f(z_0)</math>~~	+

IP = PSPACE - Revision history

Srikar at 12:33, 3 May 2021

Srikar at 12:33, 3 May 2021

PratyushRTiwari at 22:35, 2 May 2021

Srikar: Blanked the page

Srikar: Created page with "\lim_{z\rightarrow z_0} f(z)=f(z_0)"

Srikar: Created page with " $\lim_{z\rightarrow z_0} f(z)=f(z_0)$ "