Skip to main content
MathOverflow

Return to Answer

nicer language and formatting
Source Link
user44143
user44143

Can't add a comment at the moment so has to use another answerHere is more about the result of M.Dekhtiar Dekhtiar. There are several (and only several) mentions that he has provedreferences to him proving the existence of an oracle $A$ thatwith $P^{A} \ne NP^{A}$. E (e.g. mentionedthe Trakhtenbrot notes mentioned in another answer and L. Stockmeyer). TheHis result of of M.Dekhtiar is stated in of M.Dekhtiar 'On the impossibility of eliminating complete enumeration in computing a function relative to its graph' (in, which is in Russian, justand states theorems without proofs and, sometimes mastermentioning a master’s thesis is mentioned which possibly containsmay contain all the proofs). If I didn't miss somethingthis is the only source, then I can't agree that suchan oracle with $P^{A} \ne NP^{A}$ was found or that the work could be compared tois comparable to somethose parts of 'BakerBaker-Gill-Solovay theorem'. In a few words Mtheorem.Dekhtiar

Briefly, Dekhtiar considered the problem of an oracle machine which has an access to an unknown oracle from some set $U_{O}$ but, where we know that the oracle calculatecalculates some partial recursive function $f \colon \mathbb{N} \to \mathbb{N}$ (canwhich can be considered as ain the language of function graphgraphs as $(x, f(x))$, iff $f(x)$ is defined). Without knowledge of that oracle, we should construct the oracle Turing machine to calculate the value $f(y)$ for some input word $y$, if it is defined. The main result of M.DekhtiarDekhtiar is to prove withproving by diagonalization method over all partial recursive functions that 'the best way' is to make sequential queries to the oracle $(y, 0)$, $(y, 1)$, $(y, 2)$ ... until we either get the value of the function or we will loop if it is undefined. AndHere 'the best' means inwith the number offewest queries to the oracle and 'the best' accordingly to, by comparison with the whole set of possible oracles (graphs of all partial recursive functions). So,

  • polynomial bounds were not considered;
  • nondeterministic Turing machines were not considered;
  • the only used resource isbound considered was the number of queries to the oracle;
  • diagonalization over all partial recursive functions was used;
  • the main idea was not in oracle separation but a class of oracles was used to show that for each 'better machine'‘better machine’ we can find some oracle where it's not true (not that it will make a mistake but will use more queries).

Yes, sometimesSometimes it is said that that this work can be considered foras solving $P^{A} \ne NP^{A}$ problem implicitly. SoFor that, we would need to add polynomial bounded functions, and nondeterministic machines, it's towhich are not so hard. The proof explicitly uses estimation of the 'best machine' over all partial recursive functions (and, and this could be fixed with diagonalization over bounded functions). However, we can't change the formulation of the problem from M.Dekhtiar and it differs from the $P^{A} \ne NP^{A}$ problem. There is no trying to construct oneone oracle to makefor oracle separation but only choosing for each machine we can choose ananother oracle to show that it's better (in some way and only for this oracle with that machine) to use exhaustive search with sequential queries.

So phraseit sounds better to say: 'In 1969, M.Dekhtyar’ showed that nondeterminism can be more powerful than determinism if access to an oracle is allowed.' allowed’, which is from J.Buss Buss, Relativized Alternation and Space —- Bounded Computation (especially, and sounds even better if we will add implicitly) sounds better“implicitly”. Also from As J. BussBuss - 'Independentlyalso said: “Independently in 1975, Baker,Gill Gill, and Solovay exhibited oracles A, B, C, and D such that $P^{A} \ne NP^{A}$, $P^{B} = NP^{B}$, $P^{C} = NP^{C} \cap coNP^{C} \ne NP^{C}$ and $P^{D} \ne NP^{D} = coNP^{D}$. \begin{align} & P^{A} \ne NP^{A}\\ & P^{B} = NP^{B}\\ & P^{C} = NP^{C} \cap coNP^{C} \ne NP^{C}\\ & P^{D} \ne NP^{D} = coNP^{D} \end{align} They suggested that their results give evidence of the difficulty of the unrelativized $P =? NP$ problem.”

Can't add a comment at the moment so has to use another answer about the result of M.Dekhtiar. There are several (and only several) mentions that he has proved the existence of oracle $A$ that $P^{A} \ne NP^{A}$. E.g. mentioned Trakhtenbrot notes and L. Stockmeyer. The result of of M.Dekhtiar is stated in of M.Dekhtiar 'On the impossibility of eliminating complete enumeration in computing a function relative to its graph' (in Russian, just theorems without proofs and sometimes master thesis is mentioned which possibly contains all proofs). If I didn't miss something then I can't agree that such oracle was found or that work could be compared to to some parts of 'Baker-Gill-Solovay theorem'. In a few words M.Dekhtiar considered the problem of oracle machine which has an access to unknown oracle from some set $U_{O}$ but we know that oracle calculate some partial recursive function $f \colon \mathbb{N} \to \mathbb{N}$ (can be considered as a language of function graph $(x, f(x))$, iff $f(x)$ is defined). Without knowledge of that oracle we should construct the oracle Turing machine to calculate the value $f(y)$ for some input word $y$, if it is defined. The main result of M.Dekhtiar is to prove with diagonalization method over all partial recursive functions that 'the best way' is to make sequential queries to the oracle $(y, 0)$, $(y, 1)$, $(y, 2)$ ... until we get the value of the function or we will loop if it is undefined. And 'the best' means in the number of queries to the oracle and 'the best' accordingly to the whole set of possible oracles (graphs of all partial recursive functions). So,

  • polynomial bounds were not considered;
  • nondeterministic Turing machines were not considered;
  • the only used resource is the number of queries to the oracle;
  • diagonalization over all partial recursive functions was used;
  • the main idea was not in oracle separation but a class of oracles was used to show that for each 'better machine' we can find some oracle where it's not true (not that it will make a mistake but will use more queries).

Yes, sometimes it is said that that work can be considered for $P^{A} \ne NP^{A}$ problem implicitly. So we need to add polynomial bounded functions, nondeterministic machines, it's to so hard. The proof explicitly uses estimation of the 'best machine' over all partial recursive functions (and this could be fixed with diagonalization over bounded functions). However we can't change the formulation of the problem from M.Dekhtiar and it differs from the $P^{A} \ne NP^{A}$ problem. There is no trying to construct one oracle to make oracle separation but for each machine we can choose an oracle to show that it's better (in some way and only for this oracle with that machine) to use exhaustive search with sequential queries.

So phrase 'In 1969, M.Dekhtyar’ showed that nondeterminism can be more powerful than determinism if access to an oracle is allowed.' J.Buss Relativized Alternation and Space- Bounded Computation (especially if we will add implicitly) sounds better. Also from J. Buss - 'Independently in 1975, Baker,Gill, and Solovay exhibited oracles A, B, C, and D such that $P^{A} \ne NP^{A}$, $P^{B} = NP^{B}$, $P^{C} = NP^{C} \cap coNP^{C} \ne NP^{C}$ and $P^{D} \ne NP^{D} = coNP^{D}$. They suggested that their results give evidence of the difficulty of the unrelativized $P =? NP$ problem.

Here is more about the result of M. Dekhtiar. There are several references to him proving the existence of an oracle $A$ with $P^{A} \ne NP^{A}$ (e.g. the Trakhtenbrot notes mentioned in another answer and L. Stockmeyer). His result is stated in 'On the impossibility of eliminating complete enumeration in computing a function relative to its graph', which is in Russian, and states theorems without proofs, sometimes mentioning a master’s thesis which may contain all the proofs. If this is the only source, then I can't agree that an oracle with $P^{A} \ne NP^{A}$ was found or that the work is comparable to those parts of Baker-Gill-Solovay theorem.

Briefly, Dekhtiar considered the problem of an oracle machine which has access to an unknown oracle, where we know that the oracle calculates some partial recursive function $f \colon \mathbb{N} \to \mathbb{N}$ (which can be considered in the language of function graphs as $(x, f(x))$ iff $f(x)$ is defined). Without knowledge of that oracle, we should construct the oracle Turing machine to calculate the value $f(y)$ for some input word $y$, if it is defined. The main result of Dekhtiar is proving by diagonalization over all partial recursive functions that 'the best way' is to make sequential queries to the oracle $(y, 0)$, $(y, 1)$, $(y, 2)$ ... until we either get the value of the function or loop if it is undefined. Here 'the best' means with the fewest queries to the oracle, by comparison with the whole set of possible oracles (graphs of all partial recursive functions). So,

  • polynomial bounds were not considered;
  • nondeterministic Turing machines were not considered;
  • the only resource bound considered was the number of queries to the oracle;
  • diagonalization over all partial recursive functions was used;
  • the main idea was not oracle separation but a class of oracles used to show that for each ‘better machine’ we can find some oracle where it's not true (not that it will make a mistake but will use more queries).

Sometimes it is said that this work can be considered as solving $P^{A} \ne NP^{A}$ problem implicitly. For that, we would need to add polynomial bounded functions, and nondeterministic machines, which are not so hard. The proof explicitly uses estimation of the 'best machine' over all partial recursive functions, and this could be fixed with diagonalization over bounded functions. However, we can't change the formulation of the problem from Dekhtiar and it differs from the $P^{A} \ne NP^{A}$ problem. There is no trying to construct one oracle for oracle separation but only choosing for each machine another oracle to show that it's better (in some way and only for this oracle with that machine) to use exhaustive search with sequential queries.

So it sounds better to say: 'In 1969, M.Dekhtyar’ showed that nondeterminism can be more powerful than determinism if access to an oracle is allowed’, which is from J. Buss, Relativized Alternation and Space —- Bounded Computation, and sounds even better if we add “implicitly”. As Buss also said: “Independently in 1975, Baker, Gill, and Solovay exhibited oracles A, B, C, and D such that \begin{align} & P^{A} \ne NP^{A}\\ & P^{B} = NP^{B}\\ & P^{C} = NP^{C} \cap coNP^{C} \ne NP^{C}\\ & P^{D} \ne NP^{D} = coNP^{D} \end{align} They suggested that their results give evidence of the difficulty of the unrelativized $P =? NP$ problem.”

Source Link
Andrii
Andrii
  • 41
  • 1

Can't add a comment at the moment so has to use another answer about the result of M.Dekhtiar. There are several (and only several) mentions that he has proved the existence of oracle $A$ that $P^{A} \ne NP^{A}$. E.g. mentioned Trakhtenbrot notes and L. Stockmeyer. The result of of M.Dekhtiar is stated in of M.Dekhtiar 'On the impossibility of eliminating complete enumeration in computing a function relative to its graph' (in Russian, just theorems without proofs and sometimes master thesis is mentioned which possibly contains all proofs). If I didn't miss something then I can't agree that such oracle was found or that work could be compared to to some parts of 'Baker-Gill-Solovay theorem'. In a few words M.Dekhtiar considered the problem of oracle machine which has an access to unknown oracle from some set $U_{O}$ but we know that oracle calculate some partial recursive function $f \colon \mathbb{N} \to \mathbb{N}$ (can be considered as a language of function graph $(x, f(x))$, iff $f(x)$ is defined). Without knowledge of that oracle we should construct the oracle Turing machine to calculate the value $f(y)$ for some input word $y$, if it is defined. The main result of M.Dekhtiar is to prove with diagonalization method over all partial recursive functions that 'the best way' is to make sequential queries to the oracle $(y, 0)$, $(y, 1)$, $(y, 2)$ ... until we get the value of the function or we will loop if it is undefined. And 'the best' means in the number of queries to the oracle and 'the best' accordingly to the whole set of possible oracles (graphs of all partial recursive functions). So,

  • polynomial bounds were not considered;
  • nondeterministic Turing machines were not considered;
  • the only used resource is the number of queries to the oracle;
  • diagonalization over all partial recursive functions was used;
  • the main idea was not in oracle separation but a class of oracles was used to show that for each 'better machine' we can find some oracle where it's not true (not that it will make a mistake but will use more queries).

Yes, sometimes it is said that that work can be considered for $P^{A} \ne NP^{A}$ problem implicitly. So we need to add polynomial bounded functions, nondeterministic machines, it's to so hard. The proof explicitly uses estimation of the 'best machine' over all partial recursive functions (and this could be fixed with diagonalization over bounded functions). However we can't change the formulation of the problem from M.Dekhtiar and it differs from the $P^{A} \ne NP^{A}$ problem. There is no trying to construct one oracle to make oracle separation but for each machine we can choose an oracle to show that it's better (in some way and only for this oracle with that machine) to use exhaustive search with sequential queries.

So phrase 'In 1969, M.Dekhtyar’ showed that nondeterminism can be more powerful than determinism if access to an oracle is allowed.' J.Buss Relativized Alternation and Space- Bounded Computation (especially if we will add implicitly) sounds better. Also from J. Buss - 'Independently in 1975, Baker,Gill, and Solovay exhibited oracles A, B, C, and D such that $P^{A} \ne NP^{A}$, $P^{B} = NP^{B}$, $P^{C} = NP^{C} \cap coNP^{C} \ne NP^{C}$ and $P^{D} \ne NP^{D} = coNP^{D}$. They suggested that their results give evidence of the difficulty of the unrelativized $P =? NP$ problem.