Problem med kretsvärde
Kretsvärdesproblemet (eller kretsutvärderingsproblemet) är beräkningsproblemet att beräkna utsignalen från en given boolesk krets på en given ingång .
Problemet är komplett för P under enhetliga AC- 0 reduktioner. Observera att det, när det gäller tidskomplexitet , kan lösas i linjär tid helt enkelt genom en topologisk sortering .
Det booleska formelvärdeproblemet (eller boolesk formelutvärderingsproblem) är det speciella fallet av problemet när kretsen är ett träd. Problemet med boolesk formelvärde är komplett för NC 1 .
Problemet är nära relaterat till Boolean Satisfiability Problem som är komplett för NP och dess komplement, Propositional Tautology Problem , som är komplett för co-NP .
Se även