4
$\begingroup$

Is it known if there are two classes of languages $A$ and $B$ such that:

  1. $A$ and $B$ are defined wrt the exact same type of machine (e.g. 1-tape Deterministic Turing Machines, 2-tape Deterministic Turing Machines, 1-tape Nondeterministic Turing Machines, etc);

  2. neither $A$ or $B$ are defined wrt a restriction on space usage;

  3. $A = B$;

  4. there is an oracle $O$ for which $A^O \neq B^O$?

$\endgroup$
14
  • 1
    $\begingroup$ I don't understand. You have the same class of languages, somehow defined in different ways with respect to the same kind of Turing machine? Are you imagining something like A is "languages accepted by deterministic Turing machines in polynomial time" and B is "languages accepted by deterministic Turing machines that do XYZ" and it turns out that these are the same classes of languages? Can you give a concrete example of this? $\endgroup$ Feb 24, 2018 at 22:16
  • 1
    $\begingroup$ P and NP aren't languages: they're classes of languages. It's also not clear that the verifier definition of NP is "the same machine model" as the model defining P, since the deterministic TM doesn't accept the NP language: you need to do a projection. Anyway, P and EXP are trivial examples of things satisfying 1, 2 and 4. Do you have any concrete examples satisfying 1, 2 and 3? Because it's not clear to me that your requirements make sense. $\endgroup$ Feb 24, 2018 at 22:39
  • 1
    $\begingroup$ The question doesn't clearly define what it means for a class to be "defined wrt a type of machine" or for a class to be "defined wrt a restriction on space usage". I don't think that's well-defined. A language is a subset of $\{0,1\}^*$; a complexity class is a set of languages; it doesn't necessarily have to be defined in terms of any machine at all; and there are usually many ways to define any given complexity class (not always using the same notion of a "machine" in all cases). So I just don't think the requirements are well-specified. $\endgroup$
    – D.W.
    Feb 25, 2018 at 3:53
  • 3
    $\begingroup$ This was probably already said, but without proper formalization, this question is unanswerable. $\endgroup$
    – Ariel
    Feb 25, 2018 at 21:27
  • 1
    $\begingroup$ @GuilhermeRito The problem is that I don't think anyone here will be able to formalize this in a satisfactory manner. Categorizing different characterization of complexity classes is hard, as can be seen in the (at least for now) informal notion of semantic vs syntactic classes, and in this example we have a better intuition of whats going on. Thus, unfortunately, I find it hard to believe that someone will find a meaningful formalization of this. $\endgroup$
    – Ariel
    Feb 25, 2018 at 22:07

1 Answer 1

3
$\begingroup$

While the other answer answers the question as posed (at least, given your definition of 'type of machine'), I still think the question is rather ill-posed and that resolving this is a solution as well.

Problems with the current definition

First of all, as @D.W. mentioned in the comments, the claim 'Language class $X$ is defined w.r.t. machine $M$' is ill-posed. There is no need to define a class of languages with a machine at all. Even if we have a language which is commonly described w.r.t. some machine, such as $P$, there is nothing preventing us to give an equivalent definition that uses no machine at all! (Not sure if this is doable or has been done. Perhaps you can do something based on $\lambda$-calculus?)

The second problem is that oracle access is not a modifier/property of a language class! This follows immediately from the previous point: if I define a language without using a machine, how on earth am I able to use this oracle if I don't even have a machine?

The crucial mistake that leads to your problem is that a 'language' under oracle access actually depends on the definition of the language and a 'language' with oracle access is not invariant under the method you use to define the language. In fact, the often posed statement $P^O = NP^O$ is an example of really bad notation, as $P$ and $NP$ aren't actually languages here, but methods to define languages!

Let's make this precise: Let $\mathcal{X}$ be a 'definition method' for languages that can access oracles (for example, a set of machines and some acceptance rules) Let $L(\mathcal{X})$ be the language class that is defined by $\mathcal{X}$. Let $\mathcal{X}^O$ be the extension of $\mathcal{X}$ with access to the oracle $O$.

Rephrasing the question

Your question can now be rephrased as follows, let language classes $A$, $B$ such that:

  1. There exists an $\mathcal{X},\mathcal{Y}$ such that $A= L(\mathcal{X})$, $B = L(\mathcal{Y})$ and $\mathcal{X}$ and $\mathcal{Y}$ are 'of the same type'.
  2. $\mathcal{X}$ and $\mathcal{Y}$ are able to use unbounded space.
  3. $A=B$
  4. There exists an oracle $O$ such that $L(\mathcal{X}^O) \neq L(\mathcal{Y}^O)$

By combining 3 and 1, we can do without $A$, $B$ and focus on the machines:

  1. $\mathcal{X}$ and $\mathcal{Y}$ are 'of the same type' and are able to use unbounded space.
  2. There exists an oracle $O$ such that $L(\mathcal{X}^O) \neq L(\mathcal{Y}^O)$

Now, the question crucially depends on what 'the same type' means. If $\mathcal{X} = \mathcal{Y}$, then satisfying both 1 and 2 becomes impossible, as we now do have $\mathcal{X}^O = \mathcal{Y}^O$, so $L(\mathcal{X}^O) = L(\mathcal{Y}^O)$.

So, a necessary condition for statements 1 and 2 is the claim:

There exists an oracle $O$ such that $\mathcal{X}^O \neq \mathcal{Y}^O$.

You can define 'type' however you wish, but if two machines don't behave the same when I give them the same oracle, I don't consider those machines to be of the same type.

So, in conclusion, after rephrasing your question more formally and giving a property which I believe 'type' should adhere to, the answer to your question is actually no.

$\endgroup$
19
  • $\begingroup$ You might disagree with my conclusion, but I hope formally modelling the question makes it clear what it is actually about and that in the end it depends on how the machines behave, not the language classes. $\endgroup$
    – Discrete lizard
    Feb 25, 2018 at 11:27
  • $\begingroup$ The complexity class $\mathsf{P}^O$ consists of all languages accepted by polynomial time machines with access to an $O$-oracle, and $\mathsf{NP}^O$ can be defined in a similar fashion. These are well-defined complexity classes. $\endgroup$ Feb 25, 2018 at 11:44
  • 1
    $\begingroup$ @YuvalFilmus Yes, and it is precisely this 'standard notation' that is the source of OP's confusion. I can rephrase the 'more formal' bit into 'more clear', but I think my point stands. $\endgroup$
    – Discrete lizard
    Feb 25, 2018 at 11:50
  • 1
    $\begingroup$ @GuilhermeRito Sorry -- by "your version", I meant the version given in this answer. I agree that the concept you're looking for seems to be very hard to pin down, exactly. That's not a criticism, just an acceptance that you're trying to ask a subtle question where things that seem to make sense intuitively can be very hard to write down formally. $\endgroup$ Feb 25, 2018 at 13:22
  • 1
    $\begingroup$ @GuilhermeRito There are many equivalent definitions of NP. For most people, the most natural one is in terms of NTMs running in polynomial time -- after all, that's how the class got it's name... Honestly, it's pretty ridiculous to insist that NP is not defined in terms of NTMs. Anyway, you've now claimed in your two most recent comments that "the definition of co-NP is totally independent from any type of machine" and that it's defined in terms of Turing machines because NP is. I don't think there's anything more to discuss here. You're simply not making sense. $\endgroup$ Feb 25, 2018 at 19:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.