Catalogo Articoli (Spogli Riviste)

OPAC HELP

Titolo:
Distributionally hard languages
Autore:
Fortnow, L; Pavan, A; Selman, AL;
Indirizzi:
NEC Res Inst, Princeton, NJ 08540 USA NEC Res Inst Princeton NJ USA 08540NEC Res Inst, Princeton, NJ 08540 USA SUNY Buffalo, Dept Comp Sci & Engn, Buffalo, NY 14260 USA SUNY Buffalo Buffalo NY USA 14260 Comp Sci & Engn, Buffalo, NY 14260 USA Univ Chicago, Dept Comp Sci, Chicago, IL 60637 USA Univ Chicago Chicago IL USA 60637 o, Dept Comp Sci, Chicago, IL 60637 USA
Titolo Testata:
THEORY OF COMPUTING SYSTEMS
fascicolo: 3, volume: 34, anno: 2001,
pagine: 245 - 261
SICI:
1432-4350(200105/06)34:3<245:DHL>2.0.ZU;2-1
Fonte:
ISI
Lingua:
ENG
Soggetto:
RESOURCE-BOUNDED MEASURE; COMPLEXITY CLASSES; BI-IMMUNE; SETS; TIME; NP; COMPLETENESS; RANDOMNESS; SEPARATION; HIERARCHY;
Tipo documento:
Article
Natura:
Periodico
Settore Disciplinare:
Engineering, Computing & Technology
Citazioni:
31
Recensione:
Indirizzi per estratti:
Indirizzo: Fortnow, L NEC Res Inst, 4 Independence Way, Princeton, NJ 08540 USA NEC Res Inst 4 Independence Way Princeton NJ USA 08540 8540 USA
Citazione:
L. Fortnow et al., "Distributionally hard languages", THEOR C SYS, 34(3), 2001, pp. 245-261

Abstract

Cai and Selman [CS] defined a modification of Levin's [Le] notion of average polynomial time and proved, for every P-bi-immune language L and every polynomial-time computable distribution mu, with infinite support, that L isnot recognizable in polynomial time on the mu -average. We call such languages distributionally hard. Pavan and Selman [PSI proved that there exist distributionally hard sets that are not P-bi-immune if and only P contains P-printable-immune sets. We extend this characterizion to include assertionsabout several traditional questions about immunity, about finding witnesses for NP-machines, and about existence of one-way functions. Similarly, we address the question of whether NP contains sets that are distributionally hard. Several of our results are implications for which we cannot prove whether or not their converse holds. In nearly all such cases we provide oracles relative to which the converse fails. We use the techniques of Kolmogorov complexity to describe our oracles and to simplify the technical arguments.

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