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

    Identifiers