skip to main content
Lingue:
Cerca la mia strategia di ricerca: Mostra risultati con: Mostra risultati con:

Languages represented by Boolean formulas

Veith, Helmut

Information processing letters, 1997, Vol.63 (5), p.251-256 [Rivista Peer Reviewed]

Fulltext disponibile

Citazioni Citato da
  • Titolo:
    Languages represented by Boolean formulas
  • Autore: Veith, Helmut
  • Editore: Elsevier B.V
  • Diritti: 1997
  • Note di contenuto: A propositional problem is a problem whose instances are defined by Boolean formulas. Using quantifier free logical reductions, we give a sufficient condition under which a large class of propositional problems becomes exponentially harder than their ordinary encodings. This result extends former upgrading results which hold only for representation by Boolean circuits. It follows that all succinct circuit problems proved complete by Papadimitriou (1994) remain complete under representation by Boolean formulas.
  • Fa parte di: Information processing letters, 1997, Vol.63 (5), p.251-256
  • Soggetti: Propositional logic ; Descriptive complexity theory ; Succinct problems ; Computational complexity
  • Lingua: Inglese
  • Tipo: Articolo
  • Identificativo: ISSN: 0020-0190
    EISSN: 1872-6119
    DOI: 10.1016/S0020-0190(97)00134-8

Ricerca in corso nelle risorse remote ...