Complete divisibility problems for slowly utilized oracles

DOI10.1016/0304-3975(85)90017-9zbMath0604.68044OpenAlexW1973529901MaRDI QIDQ1083192

David Alan 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

intractabilityrootsparse polynomialcomplexity relative to a slowly utilized oracleNP-completeness relative to a slowly utilized oraclepolynomial divisibilityunrelativized complexity

Mathematics Subject Classification ID

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

Cites Work

• New NP-hard and NP-complete polynomial and integer divisibility problems
• Fast verification, testing, and generation of large primes
• The network complexity and the Turing machine complexity of finite functions
• Sparse complex polynomials and polynomial reducibility
• Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
• Probabilistic Algorithms in Finite Fields
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• Some Polynomial and Integer Divisibility Problems are $NP$-Hard
• Unnamed Item
• Unnamed Item
• Unnamed Item

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