Complete divisibility problems for slowly utilized oracles

DOI10.1016/0304-3975(85)90017-9MaRDI QIDQ1083192zbMATH OpenOpenAlexFDO

Authors David A. Plaisted

Publication date 1985

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(85)90017-9

zbMATH Keywords

complexity relative to a slowly utilized oracleintractabilityNP-completeness relative to a slowly utilized oraclepolynomial divisibilityrootsparse polynomialunrelativized complexity

Mathematics Subject Classification ID

Polynomials over finite fields (11T06) Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30)

Review text

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.

Recommendations

• On the oracle complexity of factoring integers
• On the complexity of linear arithmetic with divisibility
• Deterministic factoring with oracles
• On a certain nontraditional version of computations with oracles
• Generalized computations with binary oracles
• Deterministic integer factorization with oracles for Euler's totient function
• On oracle factoring of integers
• Polynomial-time random oracles and separating complexity classes
• Generalized computations with oracles
• scientific article; zbMATH DE number 4079399

Cites work

• Fast verification, testing, and generation of large primes
• scientific article; zbMATH DE number 3642710 (Why is no real title available?)
• scientific article; zbMATH DE number 3566230 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• New NP-hard and NP-complete polynomial and integer divisibility problems
• Probabilistic Algorithms in Finite Fields
• Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• Some Polynomial and Integer Divisibility Problems are NP-Hard
• Sparse complex polynomials and polynomial reducibility
• The network complexity and the Turing machine complexity of finite functions

Cited in

(2)

• New NP-hard and NP-complete polynomial and integer divisibility problems
• NP-complete problems for systems of linear polynomial's values divisibilities

This page was built for publication: Complete divisibility problems for slowly utilized oracles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1083192)