We prove that the sequential approximation algorithms for the problems MAX SAT and MIN SET COVER proposed in [9] are P-hard with respect to the logarithmic space reducibility. As a corollary, these two algorithms cannot be implemented efficiently in parallel unless P = NC.

MAX SAT AND MIN SET COVER APPROXIMATION ALGORITHMS ARE P-COMPLETE / G. BONGIOVANNI; P. CRESCENZI; S. DE AGOSTINO. - In: PARALLEL PROCESSING LETTERS. - ISSN 0129-6264. - STAMPA. - 5:(1995), pp. 293-298. [10.1142/s0129626495000278]

MAX SAT AND MIN SET COVER APPROXIMATION ALGORITHMS ARE P-COMPLETE

CRESCENZI, PIERLUIGI;
1995

Abstract

We prove that the sequential approximation algorithms for the problems MAX SAT and MIN SET COVER proposed in [9] are P-hard with respect to the logarithmic space reducibility. As a corollary, these two algorithms cannot be implemented efficiently in parallel unless P = NC.
1995
5
293
298
G. BONGIOVANNI; P. CRESCENZI; S. DE AGOSTINO
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificatore per citare o creare un link a questa risorsa: https://hdl.handle.net/2158/206000
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? ND
social impact