Catalogo Articoli (Spogli Riviste)

OPAC HELP

Titolo:
The satisfiability problem for probabilistic ordered branching programs
Autore:
Agrawal, M; Thierauf, T;
Indirizzi:
Indian Inst Technol, Dept Comp Sci, Kanpur 208016, Uttar Pradesh, India Indian Inst Technol Kanpur Uttar Pradesh India 208016 ttar Pradesh, India Univ Ulm, Abt Theoret Informat, D-89069 Ulm, Germany Univ Ulm Ulm Germany D-89069 Abt Theoret Informat, D-89069 Ulm, Germany
Titolo Testata:
THEORY OF COMPUTING SYSTEMS
fascicolo: 5, volume: 34, anno: 2001,
pagine: 471 - 487
SICI:
1432-4350(200109/10)34:5<471:TSPFPO>2.0.ZU;2-O
Fonte:
ISI
Lingua:
ENG
Soggetto:
BINARY-DECISION DIAGRAMS; BOOLEAN FUNCTIONS; COMPLEXITY; MANIPULATION;
Tipo documento:
Article
Natura:
Periodico
Settore Disciplinare:
Engineering, Computing & Technology
Citazioni:
22
Recensione:
Indirizzi per estratti:
Indirizzo: Agrawal, M Indian Inst Technol, Dept Comp Sci, Kanpur 208016, Uttar Pradesh, India Indian Inst Technol Kanpur Uttar Pradesh India 208016 h, India
Citazione:
M. Agrawal e T. Thierauf, "The satisfiability problem for probabilistic ordered branching programs", THEOR C SYS, 34(5), 2001, pp. 471-487

Abstract

We show that the satisfiability problem for bounded-error probabilistic ordered branching programs is NP-complete. If the error is very small, however (more precisely, if the error is bounded by the reciprocal of the width of the branching program), then we have a polynomial-time algorithm for the satisfiability problem.

ASDD Area Sistemi Dipartimentali e Documentali, Università di Bologna, Catalogo delle riviste ed altri periodici
Documento generato il 26/01/20 alle ore 10:31:52