MPI-INF/SWS Research Reports 1991-2021

# MPI-I-93-121

## The circuit subfunction relations are \$sum^P_2\$-complete

### Borchert, Bernd and Ranjan, Desh

#### May 1993, 14 pages.

.
##### Status: available - back from printing

We show that given two Boolean circuits \$f\$ and \$g\$ the following three problems are \$\Sigma^p_2\$-complete: (1) Is \$f\$ a c-subfunction of \$g\$, i.e.\ can one set some of the variables of \$g\$ to 0 or 1 so that the remaining circuit computes the same function as \$f\$? (2) Is \$f\$ a v-subfunction of \$g\$, i.e. can one change the names of the variables of \$g\$ so that the resulting circuit computes the same function as \$f\$? (3) Is \$f\$ a cv-subfunction of \$g\$, i.e.\ can one set some variables of \$g\$ to 0 or 1 and simultanously change some names of the other variables of \$g\$ so that the new circuit computes the same function as \$f\$? Additionally we give some bounds for the complexity of the following problem: Is \$f\$ isomorphic to \$g\$, i.e. can one change the names of the variables bijectively so that the circuit resulting from \$g\$ computes the same function as \$f\$?

URL to this document: https://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1993-121

BibTeX
@TECHREPORT{BorchertRanjan93,
AUTHOR = {Borchert, Bernd and Ranjan, Desh},
TITLE = {The circuit subfunction relations are \$sum^P_2\$-complete},
TYPE = {Research Report},
INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},