Complete divisibility problems for slowly utilized oracles (Q1083192)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Complete divisibility problems for slowly utilized oracles |
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Complete divisibility problems for slowly utilized oracles |
scientific article |
Statements
Complete divisibility problems for slowly utilized oracles (English)
0 references
1985
0 references
The concept of NP-completeness relative to a slowly utilized oracle is introduced and shown to be useful for providing evidence of intractability of some problems that are not known to be NP-complete. One such problem is to decide if a sparse polynomial has a root in the integers (mod p) for prime p. Relationships between unrelativized complexity and complexity relative to a slowly utilized oracle are also given.
0 references
polynomial divisibility
0 references
NP-completeness relative to a slowly utilized oracle
0 references
intractability
0 references
sparse polynomial
0 references
root
0 references
unrelativized complexity
0 references
complexity relative to a slowly utilized oracle
0 references
0 references
