Using depth to capture average-case complexity

• Type: Article in International Scientific Journal
• Date: 2003

Authors

antunes, l (Author) FCUP; fortnow, l (Author) Other; vinodchandran, nv (Author) Other

Journal

The Journal is awaiting validation by the Administrative Services.

Title: INTERACTIVE SYSTEMS: DESIGN, SPECIFICATION, AND VERIFICATION

Vol. 58

Pages: 303-310

Indexing

ISI Web of Knowledge - 3 Citations

Scopus - 3 Citations

Other information

Authenticus ID: 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.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 8