Storleken på Ordered Binary Decision Diagram (OBDD) bestäms av den valda variabeln order. Ett dåligt val kan få en OBDD att vara för stor för att passa in i det tillgängliga minnet. Beslutsvarianten av variabelt beställningsproblem är känd för att vara NP-fullständig. Vi stärker detta resultat genom att visa att för varje konstant c > 1 det inte finns någon polynom tid approximation algoritm med prestandaförhållandet c för variabel beställning problem om inte P = NP. Detta resultat rättfärdigar, även ur teoretisk synvinkel, att använda heuristik för variabla beställningsproblem. Exempel: En OBDD H för vissa funktioner f. Problem: Beräkna en variabel som beställer minimering av OBDD-storleken för f och. Vi noterar att från H och varje variabel som beställer en OBDD för f med variabel beställning kan beräknas i polynom tid (Savický och Wegener (1997), Meinel och Slobodová (1994) ). Därför räcker det att definiera MinOBDD som ett problem för att beräkna en optimal variabel beställning istället för en minsta storlek OBDD. MinOBDD är det problem som uppstår vid tillämpning av dynamiska variabla beställningstekniker som införts av Rudell (1993): Vid beräkning av OBDD, t.ex. Beräkning av en OBDD för en funktion som representeras av en krets, den uppsättning funktioner som representeras av förändringar under denna beräkning. Därför kan också de variabla beställningar som medger små OBDD för de representerade funktionerna ändras. Därför är det rimligt att ändra den variabla beställningen under beräkningen. Bryant (1995) rapporterar att denna omordning bromsar beräkningen, men att det ibland är den enda möjligheten att slutföra beräkningar utan att överskrida det tillgängliga minnet. Argumentet för hårdheten hos den första versionen av variabel beställningsproblem gäller inte för MinOBDD eftersom funktionen f redan anges som en OBDD, för vilken tillfredsställande testet kan göras i polynom tid. Det första steget för att bevisa hårdheten i MinOBDD gjordes av Tani, Hamaguchi och Yajima (1993). De visade att beslutsvarianten av problemet MinSBDD är NP-fullständig. SBDDs (delade binära beslut diagram) är generaliseringen av OBDDs för representation av mer än en funktion och MinSBDD är problemet att beräkna en optimal variabel beställning för en uppsättning funktioner som ges av en SBDD. bevisade att även beslutsvarianten av MinOBDD är NP-fullständig. Algoritmer för att lösa problemet MinOBDD exakt presenteras i tidningarna Ishiura, Sawada och Yajima (1991) och Jeong, Kim och Somenzi (1993). Som förväntat av NP-fullständighet resultat dessa algoritmer har en exponentiellt värsta fall körtid. Båda algoritmerna är förbättringar av algoritmen Friedman och Supowit (1990) för beräkning av minsta storlek OBDD. Denna algoritm har uppenbarligen exponentiell körtid eftersom den fungerar på sanningstabeller. NP-fullständighetsresultaten motiverar, även ur teoretisk synvinkel, att tillämpa algoritmer som inte nödvändigtvis beräknar optimala lösningar. De kända heuristikerna för MinOBDD är baserade på lokal sökning och simulerade glödgningsmetoder (se t.ex. Icke desto mindre utesluter NP-fullständighet inte förekomsten av goda approximationsalgoritmer som polynomiska tid approximeringssystem för variabel beställningsproblem (även om P 6 = NP). NP-fullständigheten resultat för MinOBDD och MinSBDD bevisas genom minskningar från problemet Optimal Linear Arrangemang. Minskningarna verkar inte vara ungefärliga och vi känner inte till något icke-tillnärmelsebart resultat för Optimal Linear Arrangemang. Den enda indikationen på att bra approximation algoritmer för variabel beställning problem inte finns är den misslyckade sökandet efter sådana algoritmer. De kända heuristikerna ger ingen garanti för kvaliteten på sina resultat. Vanligtvis testas heuristikerna endast på någon uppsättning av referenskretsar. I detta dokument karakteriserar vi komplexiteten i problemet med variabel beställning mer exakt genom att bevisa följande teorem. Teorem 1 Om det finns någon polynom tid approximation algoritm för MinOBDD med prestandaförhållandet c, där c är några konstant, sedan P = NP. 2. Utgångspunkten är följande:
Dessutom är approximationsproblemet också svårt, eftersom det för varje konstant c > 1 är NPhard att beräkna en variabel beställning som resulterar i en OBDD med en storlek som är som mest c gånger större än optimal REF ].
The Nonapproximability of OBDD Minimization
{'venue': 'Information and Computation', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}