Boolsk krets - Boolean circuit

Eksempel boolsk krets. De noder er OG-porter , de nodene er OR porter , og nodene er IKKE porter

{\ displaystyle \ wedge}

{\ displaystyle \ vee}

{\ displaystyle \ neg}

I beregningskompleksitetsteori og kretskompleksitet er en boolsk krets en matematisk modell for kombinasjons digitale logikkretser . Et formelt språk kan bestemmes av en familie av boolske kretser, en krets for hver mulig inngangslengde. Boolske kretser brukes også som en formell modell for kombinasjonslogikk i digital elektronikk.

Boolske kretser er definert i form av de logiske portene de inneholder. For eksempel kan en krets inneholde binære AND- og OR -porter og unary NOT -porter, eller være helt beskrevet av binære NAND -porter . Hver gate tilsvarer en eller annen boolsk funksjon som tar et fast antall biter som input og sender ut en enkelt bit.

Boolske kretser gir en modell for mange digitale komponenter som brukes i datateknikk , inkludert multipleksere , addere og aritmetiske logiske enheter , men de utelukker sekvensiell logikk . De er en abstraksjon som utelater mange aspekter som er relevante for å designe virkelige digitale logikkretser, for eksempel metastabilitet , fanout , feil , strømforbruk og forplantningsforsinkelsesvariabilitet .

Formell definisjon

Ved å gi en formell definisjon av boolske kretser, starter Vollmer med å definere et grunnlag som sett B for boolske funksjoner, tilsvarende portene som er tillatt i kretsmodellen. En boolsk krets over en basis B , med n innganger og m utganger, blir deretter definert som en endelig endret asyklisk graf . Hvert toppunkt tilsvarer enten en basisfunksjon eller en av inngangene, og det er et sett med nøyaktig m noder som er merket som utgangene. Kantene må også ha en viss rekkefølge, for å skille mellom forskjellige argumenter for den samme boolske funksjonen.

Som et spesielt tilfelle er en proposisjonsformel eller boolsk uttrykk en boolsk krets med en enkelt utgangsnode der hver annen node har fan-out på 1. Dermed kan en boolsk krets betraktes som en generalisering som tillater delte underformler og flere utganger .

Et vanlig grunnlag for boolske kretser er settet { AND , OR , NOT }, som er funksjonelt komplett , dvs. e. hvorfra alle andre boolske funksjoner kan konstrueres.

Beregningskompleksitet

Bakgrunn

En bestemt krets virker bare på innganger med fast størrelse. Imidlertid inneholder formelle språk (de strengbaserte representasjonene av beslutningsproblemer ) strenger av forskjellige lengder, så språk kan ikke fullstendig fanges opp av en enkelt krets (i motsetning til Turing-maskinmodellen, der et språk er fullt ut beskrevet av en enkelt Turing maskin). Et språk er i stedet representert av en kretsfamilie . En kretsfamilie er en uendelig liste over kretser , som har inndatavariabler. En kretsfamilie sies å bestemme et språk hvis, for hver streng , er på språket hvis og bare hvis , hvor er lengden på . Med andre ord, et språk er settet med strenger som, når det brukes på kretsene som tilsvarer lengden, evaluerer til 1. ${\ displaystyle (C_ {0}, C_ {1}, C_ {2}, ...)}$ ${\ displaystyle C_ {n}}$ ${\ displaystyle n}$ ${\ displaystyle L}$ ${\ displaystyle w}$ ${\ displaystyle w}$ ${\ displaystyle L}$ ${\ displaystyle C_ {n} (w) = 1}$ ${\ displaystyle n}$ ${\ displaystyle w}$

Kompleksitetstiltak

Flere viktige kompleksitetstiltak kan defineres på boolske kretser, inkludert kretsdybde, kretsstørrelse og antall vekslinger mellom AND -porter og OR -porter. For eksempel er størrelsen på kompleksiteten til en boolsk krets antall porter.

Det viser seg at det er en naturlig sammenheng mellom kretsstørrelseskompleksitet og tidskompleksitet . Intuitivt har et språk med liten tidskompleksitet (det vil si at det krever relativt få sekvensielle operasjoner på en Turing -maskin ) også en liten kretskompleksitet (det vil si krever relativt få boolske operasjoner). Formelt kan det vises at hvis et språk er i , hvor er en funksjon , så har det kretskompleksitet . ${\ displaystyle {\ mathsf {TIME}} (t (n))}$ ${\ displaystyle t}$ ${\ displaystyle t: \ mathbb {N} \ to \ mathbb {N}}$ ${\ displaystyle O (t^{2} (n))}$

Kompleksitetsklasser

Flere viktige kompleksitetsklasser er definert når det gjelder boolske kretser. Den mest generelle av disse er P/poly , settet med språk som kan avgjøres av kretsfamilier i polynomstørrelse. Det følger direkte av det faktum at språk i har kretskompleksitet som P P/poly. Med andre ord kan ethvert problem som kan beregnes i polynomtid av en deterministisk Turing-maskin, også beregnes av en kretsfamilie i polynomstørrelse. Det er videre slik at inkluderingen er riktig (dvs. P P/poly) fordi det er ubestemte problemer som er i P/poly. P/poly viser seg å ha en rekke egenskaper som gjør det svært nyttig i studiet av forholdet mellom kompleksitetsklasser. Spesielt er det nyttig å undersøke problemer relatert til P versus NP . For eksempel, hvis det er et språk i NP som ikke er i P/poly, så er P NP. P/poly hjelper også til med å undersøke egenskapene til det polynomiske hierarkiet . For eksempel, hvis NP ⊆ P/poly, så kollapser PH til . En fullstendig beskrivelse av forholdet mellom P/poly og andre kompleksitetsklasser er tilgjengelig på " Viktigheten av P/poly ". P/poly har også den interessante egenskapen at den kan defineres ekvivalent som klassen av språk som er gjenkjent av en polynom-tid Turing-maskin med en polynom-begrenset rådfunksjon . ${\ displaystyle {\ mathsf {TIME}} (t (n))}$ ${\ displaystyle O (t^{2} (n))}$ ${\ displaystyle \ subseteq}$ ${\ displaystyle \ subsetneq}$ ${\ displaystyle \ neq}$ ${\ displaystyle \ Sigma _ {2}^{\ mathsf {P}}}$

To underklasser av P/poly som har interessante egenskaper i seg selv er NC og AC . Disse klassene er definert ikke bare når det gjelder kretsstørrelsen, men også når det gjelder dybden . Dybden på en krets er lengden på den lengste dirigerte banen fra en inngangsnode til utgangsnoden. Klassen NC er settet med språk som kan løses av kretsfamilier som ikke bare er begrenset til å ha polynomstørrelse, men også til å ha polylogaritmisk dybde. Klassen AC er definert på samme måte som NC, men porter har lov til å ha ubegrenset fan-in (det vil si at AND og OR-portene kan brukes på mer enn to bits). NC er en viktig klasse fordi det viser seg at den representerer klassen av språk som har effektive parallelle algoritmer .

Kretsevaluering

Den Circuit verdiproblem - problemet med å beregne utgangssignalet fra en gitt boolsk krets på et gitt inngangs streng - er en P-komplett avgjørelse problem . Derfor anses dette problemet å være "iboende sekvensielt" i den forstand at det sannsynligvis ikke er noen effektiv, svært parallell algoritme som løser problemet.

Languages

In other projects