FIRST P-cOMPLETE AND NP-COMPLETE PROBLEMS 3.34 Show that the language MONOTONE CIRCUIT VALUE defined below is P-complete. MONOTONE CIRCUIT VALUE Instance: A description for a monotone circuit with fixed values for its input variables and a designated output gate. Answer: "Yes" if the output of the circuit has value 1 Hint: Using dual-rail logic, find a way to translate (reduce) a string in the language CIRCUIT VALUE to a string in MONOTONE CIRCUIT VALUE by converting in loga- rithmic space (in the length of the string) a circuit over the standard basis to a circuit over the monotone basis. Note that, as stated in the text, the composition of two ce reduction. To simplify the con- version from non-monotone circuits to monotone circuits, use even integers to index vertices in the non-monotone circuits so that both even and odd integers can be used in the monotone case. FIRST P-cOMPLETE AND NP-COMPLETE PROBLEMS 3.34 Show that the language MONOTONE CIRCUIT VALUE defined below is P-complete. MONOTONE CIRCUIT VALUE Instance: A description for a monotone circuit with fixed values for its input variables and a designated output gate. Answer: "Yes" if the output of the circuit has value 1 Hint: Using dual-rail logic, find a way to translate (reduce) a string in the language CIRCUIT VALUE to a string in MONOTONE CIRCUIT VALUE by converting in loga- rithmic space (in the length of the string) a circuit over the standard basis to a circuit over the monotone basis. Note that, as stated in the text, the composition of two ce reduction. To simplify the con- version from non-monotone circuits to monotone circuits, use even integers to index vertices in the non-monotone circuits so that both even and odd integers can be used in the monotone case