Instance complexity
Open Access
- 2 January 1994
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 41 (1) , 96-121
- https://doi.org/10.1145/174644.174648
Abstract
We introduce a measure for the computational complexity of individual instances of a decision problem and study some of its properties. The instance complexity of a string x with respect to a set A and time bound t, ic t (x : A), is defined as the size of the smallest special-case program for A that runs in time t, decides x correctly, and makes no mistakes on other strings ("don't know" answers are permitted). We prove that a set A is in P if and only if there exist a polynomial t and a...Keywords
This publication has 13 references indexed in Scilit:
- A classification of complexity core latticesTheoretical Computer Science, 1986
- The density and complexity of polynomial cores for intractable setsInformation and Control, 1986
- Nonlevelable sets and immune sets in the accepting density hierarchy inNPTheory of Computing Systems, 1985
- Bi-immune sets for complexity classesTheory of Computing Systems, 1985
- Hard-core theorems for complexity classesJournal of the ACM, 1985
- On sparse sets in NP–PInformation Processing Letters, 1983
- The intrinsically exponential complexity of the circularity problem for attribute grammarsCommunications of the ACM, 1975
- On Reducibility to Complex or Sparse SetsJournal of the ACM, 1975
- A variant of the Kolmogorov concept of complexityInformation and Control, 1969
- On the Simplicity and Speed of Programs for Computing Infinite Sets of Natural NumbersJournal of the ACM, 1969