Name
Abstract | ||
|---|---|---|
Nancy Lynch proved that if a decision problem A is not solvable in polynomial time, then there exists an infinite recursive subset X of its domain on which the decision is almost everywhere complex. In this paper, general theorems of this kind that can be applied to several well-known automata-based complexity classes, including a common class of randomized algorithms, are proved. |
Year | DOI | Venue |
|---|---|---|
1985 | 10.1145/2455.214111 | J. ACM |
Keywords | DocType | Volume |
hard-core theorem,randomized algorithm,common class,decision problem,randomized computation,infinite recursive subset X,general theorem,Nancy Lynch,polynomial time,complexity core,general terms: theory additional key words and phrases: hard-core,well-known automata-based complexity class | Journal | 32 |
Issue | ISSN | Citations |
1 | 0004-5411 | 17 |
PageRank | References | Authors |
4.12 | 9 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| shimon even | 1 | 2873 | 981.78 |
| Alan L. Selmen | 2 | 17 | 4.12 |
| Yacov Yacobi | 3 | 704 | 133.71 |