Complete divisibility problems for slowly utilized oracles (Q1083192)
From MaRDI portal
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