Relativizations of the P =? DNP Question for the BSS Model

Author Christine Gaßner



PDF
Thumbnail PDF

File

OASIcs.CCA.2009.2266.pdf
  • Filesize: 328 kB
  • 8 pages

Document Identifiers

Author Details

Christine Gaßner

Cite AsGet BibTex

Christine Gaßner. Relativizations of the P =? DNP Question for the BSS Model. In 6th International Conference on Computability and Complexity in Analysis (CCA'09). Open Access Series in Informatics (OASIcs), Volume 11, pp. 141-148, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
https://doi.org/10.4230/OASIcs.CCA.2009.2266

Abstract

We consider the uniform BSS model of computation where the machines can perform additions, multiplications, and tests of the form $x\geq 0$. The oracle machines can also check whether a tuple of real numbers belongs to a given oracle set ${\cal O}$ or not. We construct oracles such that the classes P and DNP relative to these oracles are equal or not equal.
Keywords
  • BSS machines
  • oracle machines
  • relativizations
  • P-DNP problem
  • real knapsack problem

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail