Skip to main content
Computer Science

Return to Question

added 1 character in body
Source Link
Dennis
Dennis
  • 165
  • 7

Define the following languages:

$$ \text{SUCC-CVAL}=\{(S,x,i) : \substack{S \text{ is a succint representation for circuit } C \\ \text{ and } C_i(x)=1 \text{ where } C_i \text{ is the i'th gate in } C(x) } \} $$ $$ \text{CorrectSuccintSolver} = \{C \, | \, \forall S,x,i\,C(S,x,i)=1\Leftrightarrow (S,x,i)\in \text{SUCC-CVAL} \} $$

I need to prove that $\text{CorrectSuccintSolver} \in \mathbf{coNP}$.

I have tried to far constructing a $\forall$ sentence with a polynomial-time TM $M$ that validates the correctness of the given input circuit $C$, such that $C\in\text{CorrectSuccintSolver} \textbf{ iff } \, \forall S,x,i\ M(C,S,x,i)$.

We need to check if the circuit $C$ is correct. The machine $M$ uses the given input circuit $C$ to check whether $C$'s output on gate $i$ is consistent with $C$'s outputs for gates $j,k$ that are connected to gate $i$ (w.l.o.g., $i = j \text{ op } k$ where $\text{op}\in{\{\wedge,\vee,\neg}\}$).

I think that there is a problem in my solution (something is missing). In addition, I have few missing details. For example, how to find gates $i,j,k$ only from succint representation?

Please advise. Thank you.

Define the following languages:

$$ \text{SUCC-CVAL}=\{(S,x,i) : \substack{S \text{ is a succint representation for circuit } C \\ \text{ and } C_i(x)=1 \text{ where } C_i \text{ is the i'th gate in } C(x) } \} $$ $$ \text{CorrectSuccintSolver} = \{C \, | \, \forall S,x,i\,C(S,x,i)=1\Leftrightarrow (S,x,i)\in \text{SUCC-CVAL} \} $$

I need to prove that $\text{CorrectSuccintSolver} \in \mathbf{coNP}$.

I have tried to far constructing a $\forall$ sentence with a polynomial-time TM $M$ that validates the correctness of the given input circuit $C$, such that $C\in\text{CorrectSuccintSolver} \textbf{ iff } \, \forall S,x,i\ M(C,S,x,i)$.

We need to check if the circuit $C$ is correct. The machine $M$ uses the given input circuit $C$ to check whether $C$'s output on gate $i$ is consistent with $C$'s outputs for gates $j,k$ that are connected to gate $i$ (w.l.o.g., $i = j \text{ op } k$ where $\text{op}\in{\{\wedge,\vee,\neg}\}$.

I think that there is a problem in my solution (something is missing). In addition, I have few missing details. For example, how to find gates $i,j,k$ only from succint representation?

Please advise. Thank you.

Define the following languages:

$$ \text{SUCC-CVAL}=\{(S,x,i) : \substack{S \text{ is a succint representation for circuit } C \\ \text{ and } C_i(x)=1 \text{ where } C_i \text{ is the i'th gate in } C(x) } \} $$ $$ \text{CorrectSuccintSolver} = \{C \, | \, \forall S,x,i\,C(S,x,i)=1\Leftrightarrow (S,x,i)\in \text{SUCC-CVAL} \} $$

I need to prove that $\text{CorrectSuccintSolver} \in \mathbf{coNP}$.

I have tried to far constructing a $\forall$ sentence with a polynomial-time TM $M$ that validates the correctness of the given input circuit $C$, such that $C\in\text{CorrectSuccintSolver} \textbf{ iff } \, \forall S,x,i\ M(C,S,x,i)$.

We need to check if the circuit $C$ is correct. The machine $M$ uses the given input circuit $C$ to check whether $C$'s output on gate $i$ is consistent with $C$'s outputs for gates $j,k$ that are connected to gate $i$ (w.l.o.g., $i = j \text{ op } k$ where $\text{op}\in{\{\wedge,\vee,\neg}\}$).

I think that there is a problem in my solution (something is missing). In addition, I have few missing details. For example, how to find gates $i,j,k$ only from succint representation?

Please advise. Thank you.

Source Link
Dennis
Dennis
  • 165
  • 7

Prove $\text{CorrectSuccintSolver} \in \mathbf{coNP}$

Define the following languages:

$$ \text{SUCC-CVAL}=\{(S,x,i) : \substack{S \text{ is a succint representation for circuit } C \\ \text{ and } C_i(x)=1 \text{ where } C_i \text{ is the i'th gate in } C(x) } \} $$ $$ \text{CorrectSuccintSolver} = \{C \, | \, \forall S,x,i\,C(S,x,i)=1\Leftrightarrow (S,x,i)\in \text{SUCC-CVAL} \} $$

I need to prove that $\text{CorrectSuccintSolver} \in \mathbf{coNP}$.

I have tried to far constructing a $\forall$ sentence with a polynomial-time TM $M$ that validates the correctness of the given input circuit $C$, such that $C\in\text{CorrectSuccintSolver} \textbf{ iff } \, \forall S,x,i\ M(C,S,x,i)$.

We need to check if the circuit $C$ is correct. The machine $M$ uses the given input circuit $C$ to check whether $C$'s output on gate $i$ is consistent with $C$'s outputs for gates $j,k$ that are connected to gate $i$ (w.l.o.g., $i = j \text{ op } k$ where $\text{op}\in{\{\wedge,\vee,\neg}\}$.

I think that there is a problem in my solution (something is missing). In addition, I have few missing details. For example, how to find gates $i,j,k$ only from succint representation?

Please advise. Thank you.