Complete divisibility problems for slowly utilized oracles
DOI10.1016/0304-3975(85)90017-9zbMATH Open0604.68044OpenAlexW1973529901MaRDI QIDQ1083192FDOQ1083192
Authors: David A. Plaisted Edit this on Wikidata
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
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
intractabilitysparse polynomialrootcomplexity relative to a slowly utilized oracleNP-completeness relative to a slowly utilized oraclepolynomial divisibilityunrelativized complexity
Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Polynomials over finite fields (11T06)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Probabilistic Algorithms in Finite Fields
- New NP-hard and NP-complete polynomial and integer divisibility problems
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- The network complexity and the Turing machine complexity of finite functions
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
- Sparse complex polynomials and polynomial reducibility
- Some Polynomial and Integer Divisibility Problems are $NP$-Hard
- Fast verification, testing, and generation of large primes
- Title not available (Why is that?)
Cited In (2)
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)
