Report on Generic Case Complexity

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

This article is a short introduction to generic case complexity, which is a recently developed way of measuring the difficulty of a computational problem while ignoring atypical behavior on a small set of inputs. Generic case complexity applies to both recursively solvable and recursively unsolvable problems.
17 pages

Keywords

Computational Complexity, F.1.3

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/133261

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/0707.1364
 http://arxiv.org/abs/0707.1364

Collections

arXiv