English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
  The circuit subfunction relations are $sum^P_2$-complete

Borchert, B., & Ranjan, D.(1993). The circuit subfunction relations are $sum^P_2$-complete (MPI-I-93-121). Saarbrücken: Max-Planck-Institut für Informatik.

Item is

Files

show Files
hide Files
:
MPI-I-93-121.pdf (Any fulltext), 9MB
Name:
MPI-I-93-121.pdf
Description:
-
OA-Status:
Visibility:
Public
MIME-Type / Checksum:
application/pdf / [MD5]
Technical Metadata:
Copyright Date:
-
Copyright Info:
-
License:
-

Locators

show

Creators

show
hide
 Creators:
Borchert, Bernd1, Author
Ranjan, Desh1, Author           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 Abstract: 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$?

Details

show
hide
Language(s): eng - English
 Dates: 1993
 Publication Status: Issued
 Pages: 14 p.
 Publishing info: Saarbrücken : Max-Planck-Institut für Informatik
 Table of Contents: -
 Rev. Type: -
 Identifiers: URI: http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/93-121
Report Nr.: MPI-I-93-121
 Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

show
hide
Title: Research Report / Max-Planck-Institut für Informatik
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: - Identifier: -