Using depth to capture average-case complexity

• Tipo: Artigo em Revista Científica Internacional
• Data: 2003

Autores

antunes, l (Autor) FCUP; fortnow, l (Autor) Outra; vinodchandran, nv (Autor) Outra

Revista

A Revista está pendente de validação pelos Serviços Administrativos.

Título: INTERACTIVE SYSTEMS: DESIGN, SPECIFICATION, AND VERIFICATION

Vol. 58

Páginas: 303-310

Indexação

ISI Web of Knowledge - 3 Citações

Scopus - 3 Citações

Outras Informações

ID Authenticus: P-000-JQE

DOI: 10.1007/978-3-540-45077-1_28

Abstract (EN): We give the first characterization of Turing machines that run in polynomial-time on average. We show that a Turing machine M runs in average polynomial-time if for all inputs x the Turing machine uses time exponential in the computational depth of x, where the computational depth is a measure of the amount of "useful" information in x.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 8